MARC

 008240612s2023      us  |||||||||||||||c||eng  d
■001000016932886
■00520240214101124
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798379603281
■035    ▼a(MiAaPQ)AAI30484941
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a004
■1001  ▼aVenkat,  Prayaag.▼0(orcid)0000-0002-1366-8646
■24510▼aSemi-Definite  Programming  for  Statistical  Estimation:  Power  and  Limitations▼h[electronic  resource]
■260    ▼a[S.l.]:▼bHarvard  University.  ▼c2023
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2023
■300    ▼a1  online  resource(250  p.)
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  84-12,  Section:  B.
■500    ▼aAdvisor:  Barak,  Boaz.
■5021  ▼aThesis  (Ph.D.)--Harvard  University,  2023.
■506    ▼aThis  item  must  not  be  sold  to  any  third  party  vendors.
■520    ▼aThe  goal  of  this  thesis  to  contribute  towards  a  computational  complexity  theory  of  statistical  inference  problems.  In  recent  years,  researchers  have  built  evidence  in  favor  of  an  emerging  hypothesis  that  the  class  of  semi-definite  programming  (SDP)  algorithms  is  optimal  among  for  computationally  efficient  algorithms  for  a  certain  family  of  estimation  problems.  In  this  thesis,  we  present  four  main  research  efforts  that  refine  this  hypothesis  and  initiate  preliminary  efforts  to  go  beyond  it:•  Optimal  algorithms  for  private  and  robust  estimation:  We  give  the  first  polynomial-time  algorithms  for  privately  and  robustly  estimating  a  Gaussian  distribution  with  optimal  dependence  on  the  dimension  in  the  sample  complexity.  This  adds  the  fundamental  problem  of  private  statistical  estimation  to  a  growing  list  of  problems  for  which  SDPs  are  optimal  among  polynomial-time  algorithms.•  Limitations  of  SDPs:  Given  independent  standard  Gaussian  points  in  dimension  d,  for  what  values  of  (n,  d)  does  there  exist  with  high  probability  an  origin-symmetric  ellipsoid  that  simultaneously  passes  through  all  of  the  points?  Based  on  strong  numerical  evidence,  it  was  conjectured  that  the  ellipsoid  fitting  problem  transitions  from  feasible  to  infeasible  as  the  number  of  points  n  increases,  with  a  sharp  threshold  at  n  ∼  d  2/4;  we  resolve  this  conjecture  up  to  logarithmic  factors.  A  corollary  of  this  result  is  that  a  canonical  SDP-based  algorithm  fails  to  successfully  solve  inference  problems  involving  low-rank  matrix  decompositions,  independent  component  analysis,  and  principal  component  analysis.•  New  algorithms  for  discrepancy  certification:  We  initiate  the  study  of  the  algorithmic  problem  of  certifying  lower  bounds  on  the  discrepancy  of  random  matrices,  which  has  connections  to  conjecturally-hard  average-case  problems  such  as  negatively-spiked  PCA,  the  number-balancing  problem  and  refuting  random  constraint  satisfaction  problems.  We  give  the  first  polynomial-time  algorithms  with  non-trivial  guarantees,  strictly  outperforming  a  canonical  SDP-based  algorithm.  Our  algorithms  are  among  the  first  to  harness  the  power  of  lattice  basis  reduction  techniques  to  solve  statistical  estimation  problems.•  Fast  spectral  algorithms:  We  study  the  algorithmic  problem  of  estimating  the  mean  of  a  heavy-tailed  random  vector  in  high  dimensions  given  i.i.d.  samples.  The  goal  is  to  design  an  efficient  estimator  that  attains  the  optimal  sub-gaussian  error  bound,  only  assuming  that  the  random  vector  has  bounded  mean  and  covariance.  Polynomial-time  solutions  to  this  problem  were  known  but  have  high  runtime  due  to  the  use  of  SDPs.  We  give  a  fast  spectral  algorithm  for  this  problem  that  also  has  optimal  statistical  performance.  Our  work  establishes  yet  another  fundamental  statistical  estimation  problem  for  which  the  power  of  SDPs  is  matched  by  simpler,  more  practical  algorithms.
■590    ▼aSchool  code:  0084.
■650  4▼aComputer  science.
■650  4▼aComputer  engineering.
■653    ▼aComputational  complexity
■653    ▼aSemi-definite  programming
■653    ▼aPolynomial-time  algorithms
■653    ▼aPractical  algorithms
■653    ▼aGaussian  distribution
■690    ▼a0984
■690    ▼a0464
■71020▼aHarvard  University▼bEngineering  and  Applied  Sciences  -  Computer  Science.
■7730  ▼tDissertations  Abstracts  International▼g84-12B.
■773    ▼tDissertation  Abstract  International
■790    ▼a0084
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16932886▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.
■980    ▼a202402▼f2024

Preview

Export

ChatGPT Discussion

AI Recommended Related Books