MARC

 008250123s2024        us                              c    eng  d
■001000017161412
■00520250211151353
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798382842714
■035    ▼a(MiAaPQ)AAI31243432
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a519
■1001  ▼aJiang,  Liwei.▼0(orcid)0009-0005-3287-9966
■24510▼aSaddle  Avoidance,  Asymptotic  Normality,  and  Exponential  Acceleration  in  Nonsmooth  Optimization
■260    ▼a[Sl]▼bCornell  University▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a311  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-12,  Section:  B.
■500    ▼aAdvisor:  Davis,  Damek.
■5021  ▼aThesis  (Ph.D.)--Cornell  University,  2024.
■520    ▼aOptimization-based  algorithms  are  the  foundation  for  empirically  successful  methods  in  modern  fields,  such  as  artificial  intelligence  and  data  science.  Although  classical  optimization  theory  provides  guarantees  for  functions  with  smoothness  or  convexity,  a  significant  portion  of  modern  problems  do  not  possess  any  of  these.  Despite  the  worst-case  examples  where  efficient  algorithms  are  unavailable,  typical  nonsmoothness  arises  with  a  "partly  smooth"  structure,  meaning  that  they  are  well-behaved  relative  to  a  smooth  "active  manifold."This  thesis  develops  and  analyzes  first-order  algorithms  based  on  the  aforementioned  nonsmooth  structure.  We  first  develop  two  regularity  conditions  describing  how  sub-gradients  interact  with  active  manifolds  and  then  show  that  they  hold  for  a  broad  and  generic  class  of  functions.  With  these  cornerstones,  we  demonstrate  that  when  randomly  perturbed  or  equipped  with  stochastic  noise,  subgradient  methods  only  converge  to  minimizers  of  generic,  Clarke  regular  semialgebraic  problems.  When  convergence  to  a  certain  minimizer  is  known,  we  demonstrate  that  stochastic  (projected)  subgradient  methods  have  asymptotic  normality,  making  them  asymptotically  optimal  algorithms  in  the  locally  minimax  sense  of  Hajek  and  Le  Cam.These  findings  culminate  with  a  new  first-order  algorithm-NTDescent-which  exhibits  local  nearly  linear  convergence  on  typical  nonsmooth  functions  with  quadratic  growth.  The  convergence  rate  of  NTDescent  depends  only  on  the  function's  intrinsic  quantities  but  not  the  problem's  underlying  dimension.
■590    ▼aSchool  code:  0058.
■650  4▼aApplied  mathematics
■650  4▼aStatistics
■653    ▼aAsymptotic  normality
■653    ▼aFirst-order  method
■653    ▼aLinear  convergence
■653    ▼aNonsmooth  optimization
■653    ▼aParameter-free
■653    ▼aSaddle  point  avoidance
■690    ▼a0796
■690    ▼a0364
■690    ▼a0463
■71020▼aCornell  University▼bOperations  Research  and  Information  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g85-12B.
■790    ▼a0058
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17161412▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books