MARC

 008250123s2024        us                              c    eng  d
■001000017162735
■00520250211152047
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798342103176
■035    ▼a(MiAaPQ)AAI31345209
■035    ▼a(MiAaPQ)Purdue25655379
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a330
■1001  ▼aDexter,  Gregory.
■24510▼aMatrix  Sketching  in  Optimization
■260    ▼a[Sl]▼bPurdue  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a199  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  86-04,  Section:  B.
■500    ▼aAdvisor:  Drineas,  Petros;Khanna,  Rajiv.
■5021  ▼aThesis  (Ph.D.)--Purdue  University,  2024.
■520    ▼aContinuous  optimization  is  a  fundamental  topic  both  in  theoretical  computer  science  and  applications  of  machine  learning.  Meanwhile,  an  important  idea  in  the  development  modern  algorithms  it  the  use  of  randomness  to  achieve  empirical  speedup  and  improved  theoretical  runtimes.  Stochastic  gradient  descent  (SGD)  and  matrix-multiplication  time  linear  program  solvers  [1]  are  two  important  examples  of  such  achievements.  Matrix  sketching  and  related  ideas  provide  a  theoretical  framework  for  the  behavior  of  random  matrices  and  vectors  that  arise  in  these  algorithms,  thereby  provide  a  natural  way  to  better  understand  the  behavior  of  such  randomized  algorithms.  In  this  dissertation,  we  consider  three  general  problems  in  this  area:1.  Linear  Programming:  Interior  point  methods  (IPMs)  are  a  common  approach  for  solving  linear  programs  (LPs)  with  strong  theoretical  guarantees  and  solid  empirical  performance.  The  time  complexity  of  these  methods  is  dominated  by  the  cost  of  solv-  ing  a  linear  system  of  equations  at  each  iteration.  In  common  applications  of  linear  programming,  particularly  in  machine  learning  and  scientific  computing,  the  size  of  this  linear  system  can  become  prohibitively  large,  requiring  the  use  of  iterative  solvers,  which  provide  an  approximate  solution  to  the  linear  system.  However,  approximately  solving  the  linear  system  at  each  iteration  of  an  IPM  invalidates  the  theoretical  guar-  antees  of  common  IPM  analyses.  To  remedy  this,  we  theoretically  and  empirically  analyze  (slightly  modified)  predictor-correctorIPMs  when  using  approximate  linear  solvers:  our  approach  guarantees  that,  when  certain  conditions  are  satisfied,  the  num-  ber  of  IPM  iterations  does  not  increase  and  that  the  final  solution  remains  feasible.  We  also  provide  practical  instantiations  of  approximate  linear  solvers  that  satisfy  these  conditions  for  special  classes  of  constraint  matrices  using  randomized  linear  algebra.2.  Eigenvalue  Estimation:  We  study  the  problem  of  approximating  the  eigenspectrum  of  a  symmetric  matrix  A  ∈  R  with  bounded  entries  (i.e..  ||A||s≤  1).  We  present  a  simple  sublinear  time  algorithm  that  approximates  all  eigenvalues  of  A  up  to  additive  error  ten  using  those  of  a  randomly  sampled()x()  principal  submatrix.  Our  result  can  be  viewed  as  a  concentration  bound  on  the  complete  eigenspectrum  of  a  random  submatrix,  significantly  extending  known  bounds  on  just  the  singular  values  (the  magnitudes  of  the  eigenvalues).  We  give  improved  error  bounds  of  ennz(A)  and  Ar  when  the  rows  of  A  can  be  sampled  with  probabilities  proportional  to  their  sparsities  or  their  squared  l2  norms  respectively.  Here  nnz(A)  is  the  number  of  non-zero  entries  in  A  and  AF  is  its  Frobenius  norm.  Even  for  the  strictly  easier  problems  of  approximating  the  singular  values  or  testing  the  existence  of  large  negative  eigenvalues  [2],  our  results  are  the  first  that  take  advantage  of  non-uniform  sampling  to  give  improved  error  bounds.  From  a  technical  perspective,  our  results  require  several  new  eigenvalue  concentration  and  perturbation  bounds  for  matrices  with  bounded  entries.  Our  non-uniform  sampling  bounds  require  a  new  algorithmic  approach,  which  judiciously  zeroes  out  entries  of  a  randomly  sampled  submatrix  to  reduce  variance,  before  computing  the  eigenvalues  of  that  submatrix  as  estimates  for  those  of  A.  We  complement  our  theoretical  results  with  numerical  simulations,  which  demonstrate  the  effectiveness  of  our  algorithms  in  practice.
■590    ▼aSchool  code:  0183.
■650  4▼aSparsity
■650  4▼aComputer  science
■650  4▼aNeural  networks
■650  4▼aProbability
■650  4▼aLinear  programming
■650  4▼aData  science
■650  4▼aEigenvalues
■650  4▼aOptimization  algorithms
■650  4▼aLinear  algebra
■690    ▼a0984
■690    ▼a0800
■71020▼aPurdue  University.
■7730  ▼tDissertations  Abstracts  International▼g86-04B.
■790    ▼a0183
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17162735▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서