MARC

 008240612s2023      us  |||||||||||||||c||eng  d
■001000016933205
■00520240214101218
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798379958060
■035    ▼a(MiAaPQ)AAI30526094
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a519
■1001  ▼aHuang,  Kevin.
■24512▼aA  Modern  Treatise  on  Variational  Inequality  Problems:  Structures,  Algorithms,  and  Iteration  Complexities▼h[electronic  resource]
■260    ▼a[S.l.]:▼bUniversity  of  Minnesota.  ▼c2023
■260  1▼aAnn  Arbor  :▼bProQuest  Dissertations  &  Theses,  ▼c2023
■300    ▼a1  online  resource(200  p.)
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-02,  Section:  B.
■500    ▼aAdvisor:  Zhang,  Shuzhong.
■5021  ▼aThesis  (Ph.D.)--University  of  Minnesota,  2023.
■506    ▼aThis  item  must  not  be  sold  to  any  third  party  vendors.
■520    ▼aIn  this  thesis,  we  study  the  variational  inequality  (VI)  problem  with  the  methodology  of  designing  efficient  (or  optimal)  algorithms  and  analyzing  their  (sample/gradient)  iteration  complexities.  In  particular,  we  aim  to  explore  the  hidden  structures  in  VI  that  have  not  been  (fully)  studied  before  and  use  them  as  insights  to  guide  the  development  of  new  optimal  algorithms  that  align  with  the  modern  research  trends  in  both  VI  and  optimization.  We  start  from  the  first-order  methods,  where  acceleration  has  been  established  in  algorithms  such  as  extra-gradient  method,  optimistic  gradient  descent  ascent  method,  and  dual  extrapolation  method.  These  methods  are  known  as  optimal  in  the  sense  that  they  match  the  lower  iteration  complexity  bounds  established  for  first-order  methods  in  (strongly)  monotone  VI.  We  observe  that  these  acceleration  schemes  in  VI,  together  with  the  acceleration  schemes  used  in  optimization  such  as  Nesterov's  acceleration,  share  a  common  structure:  using  additional  sequence(s),  which  we  refer  to  it  as  ``extra  points'',  to  help  improve  the  convergence  of  the  main  sequence.  We  then  propose  a  general  guideline,  called  the  extra-point  approach,  to  construct  optimal  first-order  methods  via  a  more  systematic  way,  which  provides  flexibility  in  adopting  a  variety  of  extra  points/sequences  such  that  the  lower  bounds  take  effect.  Moving  towards  high-order  methods,  research  before  has  relied  on  using  high-order  Taylor  approximation  and  an  iterative  binary-search  in  solving  the  subproblems.  We  show  that  both  of  them  are  not  necessary  in  developing  high-order  methods,  and  the  key  lies  in  satisfying  a  high-order  Lipschitz  bound  for  any  approximation  operator  used  in  the  subroutine,  as  well  as  an  appropriate  order  of  regularization  to  eliminate  the  needs  of  binary-search.  The  proposed  unifying  framework  largely  relieves  the  demand  on  the  complicated  analysis  derived  for  different  methods  and  allows  us  to  focus  more  on  the  problem  structure  to  design  a  suitable  approximation  operator  in  the  algorithm.We  also  investigate  stochastic  algorithms  for  VI,  mainly  focusing  on  the  stochastic  approximation  (SA)  approach.  We  propose  stochastic  extensions  of  two  new  first-order  methods,  which  could  be  viewed  as  special  instances  following  the  aforementioned  extra-point  approach,  and  show  that  optimal  iteration  complexities  can  be  established  for  them,  in  both  situations  where  the  stochastic  errors  are  bounded  separately  or  they  are  reduced  together  with  the  deterministic  terms.  Application  is  discussed  using  the  example  of  black-box  saddle  point  problem  where  even  the  function  values  can  only  be  estimated  with  noises.  Using  a  smoothing  technique,  we  show  that  by  constructing  the  stochastic  zeroth-order  gradients,  the  previous  schemes  can  be  readily  applied  with  the  guarantee  on  sample  iteration  complexities.  Another  aspect  of  stochasticity  is  discussed  following  the  similar  line  of  research,  where  we  study  the  VI  problems  with  the  finite-sum  structure.  In  addition,  such  finite-sum  structure  consists  of  both  general  vector  mappings  and  gradient  mappings.  Developments  in  variance  reduced  algorithms  for  both  finite-sum  optimization  and  finite-sum  VI  have  been  found  recently,  but  none  has  focused  on  finite-sum  VI  with  optimization  structures.  We  propose  two  algorithms  for  both  monotone  and  strongly  monotone  VI  that  explicitly  make  use  of  such  optimization  structure  and  demonstrate  that  they  indeed  serve  as  a  bridge  between  these  two  problem  classes  and  are  able  to  perform  better  than  general  variance  reduced  VI  algorithms  when  such  structure  is  actually  present.  We  show  that  the  saddle  point  reformulation  of  a  finite-sum  optimization  with  finite-sum  constraints  immediately  take  the  aforementioned  forms  in  VI,  where  applications  are  commonly  seen  in  Neyman-Pearson  classification  in  machine  learning.Finally,  the  research  in  this  thesis  is  extended  to  non-monotone  VI  and  the  solution  methods  for  solving  it.  Without  the  monotonicity,  another  (weaker)  global  property  of  the  VI  problem,  the  existence  of  Minty  solution,  comes  to  play  a  central  role  in  the  convergence  of  accelerated  projection-type  methods.  With  a  slightly  worse  iteration  complexity  than  the  monotone  VI,  we  show  that  how  a  general  high-order  extra-gradient-type  method  using  the  concept  of  the  aforementioned  approximation  can  converge.  Furthermore,  when  the  existence  of  Minty  solution  is  no  longer  assumed,  very  little  can  be  said  in  general  about  the  convergence  of  these  projection-type  methods.  Alternatively,  we  use  these  methods  as  starting  points  and  derive  sufficient  conditions  that  characterize  various  structures  of  VI  where  they  can  converge  with  guaranteed  iteration  complexity  bounds.  This  approach  allows  us  to  extend  our  study  to  potentially  broader  VI  problem  classes  that  have  no  monotonicity  nor  Minty  solutions.
■590    ▼aSchool  code:  0130.
■650  4▼aApplied  mathematics.
■650  4▼aIndustrial  engineering.
■653    ▼aConvex  optimization
■653    ▼aIteration  complexities
■653    ▼aNumerical  methods
■653    ▼aVariational  inequalities
■690    ▼a0796
■690    ▼a0364
■690    ▼a0546
■71020▼aUniversity  of  Minnesota▼bIndustrial  and  Systems  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g85-02B.
■773    ▼tDissertation  Abstract  International
■790    ▼a0130
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16933205▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.
■980    ▼a202402▼f2024

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서