MARC

 008250123s2024        us                              c    eng  d
■001000017162298
■00520250211151956
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798382806686
■035    ▼a(MiAaPQ)AAI31329144
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aPeng,  Binghui.
■24510▼aLearning  Through  the  Lens  of  Computation
■260    ▼a[Sl]▼bColumbia  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a245  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-12,  Section:  B.
■500    ▼aAdvisor:  Papadimitriou,  Christos;Chen,  Xi.
■5021  ▼aThesis  (Ph.D.)--Columbia  University,  2024.
■520    ▼aOne  of  the  major  mysteries  in  science  is  the  remarkable  success  of  machine  learning.  While  its  empirical  achievements  have  captivated  the  field,  our  theoretical  comprehension  lags  significantly  behind.  This  thesis  seeks  for  advancing  our  theoretical  understanding  of  learning  and  intelligence  from  a  computational  perspective.  By  studying  fundamental  learning,  optimization  and  decision  making  tasks,  we  aspire  to  shed  lights  on  the  impact  of  computation  for  artificial  intelligence.The  first  part  of  this  thesis  concerns  the  space  resource  needed  for  learning.  By  studying  the  fundamental  role  of  memory  for  continual  learning,  online  decision  making  and  convex  optimization,  we  find  both  continual  learning  and  efficient  convex  optimization  require  a  lot  of  memory;  while  for  decision  making,  exponential  savings  are  possible.  More  concretely, •  We  prove  there  is  no  memory  deduction  in  continual  learning,  unless  the  continual  learner  takes  multiple  passes  over  the  sequence  of  environments; •  We  prove  in  order  to  optimize  a  convex  function  in  the  most  iteration  efficient  way,  an  algorithm  must  use  a  quadratic  amount  of  space;•  We  show  polylogarithmic  space  is  sufficient  for  making  near  optimal  decisions  in  an  oblivious  adversary  environment;  in  a  sharp  contrast,  a  quadratic  saving  is  both  sufficient  and  necessary  to  achieve  vanishing  regret  in  an  adaptive  adversarial  environment.The  second  part  of  this  thesis  uses  learning  as  a  tool,  and  resolves  a  series  of  long-standing  open  questions  in  algorithmic  game  theory.  By  giving  an  exponential  faster  no-swap-regret  learning  algorithm,  we  obtain  algorithms  that  achieve  near-optimal  computation/communication/iteration  complexity  for  computing  an  approximate  correlated  equilibrium  in  a  normal-form  game,  and  we  give  the  first  polynomial-time  algorithm  for  computing  approximate  normal-form  correlated  equilibria  in  imperfect  information  games  (including  Bayesian  and  extensive-form  games).
■590    ▼aSchool  code:  0054.
■650  4▼aComputer  science
■650  4▼aComputer  engineering
■653    ▼aAlgorithm
■653    ▼aComplexity
■653    ▼aGame  theory
■653    ▼aMachine  learning
■653    ▼aDecision  making
■690    ▼a0984
■690    ▼a0464
■690    ▼a0800
■71020▼aColumbia  University▼bComputer  Science.
■7730  ▼tDissertations  Abstracts  International▼g85-12B.
■790    ▼a0054
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17162298▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서