MARC

 008250123s2024        us                              c    eng  d
■001000017160376
■00520250211151007
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798382830643
■035    ▼a(MiAaPQ)AAI30994948
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aPatil,  Prathamesh.
■24510▼aTowards  Scalability  and  Robustness  for  Ranking,  Clustering,  and  Multi-Armed  Bandits
■260    ▼a[Sl]▼bUniversity  of  Pennsylvania▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a237  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-12,  Section:  A.
■500    ▼aAdvisor:  Khanna,  Sanjeev;Agarwal,  Shivani.
■5021  ▼aThesis  (Ph.D.)--University  of  Pennsylvania,  2024.
■520    ▼aIn  recent  years,  machine  learning  has  become  an  indispensable  tool  across  various  industry  domains,  revolutionizing  the  way  businesses  leverage  data  to  make  decisions.  One  of  the  key  factors  driving  the  success  of  machine  learning  is  the  explosion  of  big  data  which  has  enabled  the  development  of  increasingly  sophisticated  models.  However,  this  era  of  big  data  has  brought  with  it  a  unique  set  of  challenges:  prominently,  (a)  issues  regarding  data  quality,  and  (b)  scalability  of  learning  algorithms.  Addressing  these  challenges  is  essential  in  order  to  more  effectively  harness  the  synergy  between  big  data  and  machine  learning.This  dissertation  systematically  addresses  these  challenges  for  certain  foundational  learning  tasks:  ranking  from  pairwise  comparisons,  hierarchical  clustering,  and  online  learning  with  bandit  feedback.  For  each  of  these  problems,  we  present  an  essentially-complete  picture  through  algorithmic  upper-bounds,  and  complementary  lower-bounds  for  achieving  adversarial  robustness,  high  parallelizability  and  memory  efficiency.  More  specifically,We  study  the  problem  of  robust  estimation  for  the  popular  BTL  model  for  ranking  from  offline  data  in  a  very  general  adversarial  contamination  setting.  In  this  setting,  we  establish  exact  necessary  and  sufficient  conditions  for  identifiability,  showing  that  robustness  is  a  structural  property  of  the  underlying  topology  itself.  We  further  show  that  a  popular  class  of  comparison  graphs  -  Erdos-Renyi  graphs  -  is  highly  robust  to  contamination.  For  these  graphs,  we  also  design  an  estimation  algorithm  that  can  provably  recover  from  a  non-trivial  corruption  rate.We  then  consider  robust  ranking  in  the  online  setting  as  a  robust  regret  minimization  problem  for  dueling  bandits  in  a  very  general  adversarial  contamination  setting.  We  design  an  algorithm  that,  assuming  only  the  existence  of  a  Condorcet  winner,  achieves  low  regret  without  any  foreknowledge  of  the  extent  of  corruption  in  the  feedback.  Moreover,  we  show  that  this  regret  is  asymptotically  optimal  via  a  lower  bound.On  the  scalability  front,  we  consider  the  top-k  identification  problem  for  ranking  in  a  limited-adaptivity  setting.  When  the  preferences  satisfy  strong  stochastic  transitivity,  we  establish  a  lower  bound  on  the  sample-complexity  with  unrestricted  adaptivity,  and  show  that  just  3  adaptive  rounds  are  sufficient  to  achieve  it  (up  to  log  factors).  We  also  design  more  general  multi-round  algorithms  with  even  lower  sample  complexities,  establishing  a  non-trivial  upper-bound  on  the  round  vs  sample  complexity  tradeoff.We  then  consider  the  problem  of  scalable  minimum  cost  hierarchical  clustering  from  paired  similarity  data,  where  we  design  highly  parallel  and  memory-efficient  algorithms  in  the  massively  parallel  computing,  and  streaming  model,  respectively.  Both  algorithms  are  provably  optimal,  and  follow  as  a  consequence  of  novel  structural  properties  that  we  prove  about  the  clustering  cost  function  itself.  These  properties  and  consequently,  our  algorithmic  results,  also  extend  to  other  maximization  based  objectives  for  this  problem.Lastly,  we  consider  scalability  for  classical  stochastic  bandits  in  a  space-bounded  multi-pass  streaming  setting  where  we  uncover  a  surprising  phenomenon:  increasing  memory  beyond  a  constant  to  any  quantity  that  is  sublinear  in  the  number  of  arms  has  almost  no  effect  on  reducing  regret  in  the  worst  case.  We  design  a  constant-memory  algorithm  that  achieves  low  regret  -  both  worst-case  and  instance-dependent  -  in  a  given  fixed  number  of  passes,  and  prove  a  highly  technical  lower  bound  showing  it  is  not  possible  to  do  much  better  in  those  many  passes,  even  when  allowed  additional  superconstant  memory.
■590    ▼aSchool  code:  0175.
■650  4▼aComputer  science
■650  4▼aStatistics
■650  4▼aInformation  science
■653    ▼aMachine  learning
■653    ▼aScalability
■653    ▼aRobustness
■653    ▼aClustering
■653    ▼aMulti-armed  bandits
■690    ▼a0984
■690    ▼a0723
■690    ▼a0800
■690    ▼a0463
■71020▼aUniversity  of  Pennsylvania▼bComputer  and  Information  Science.
■7730  ▼tDissertations  Abstracts  International▼g85-12A.
■790    ▼a0175
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17160376▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서