Understanding the acceleration phenomenon via high-resolution differential equations
Shi, Bin2; Du, Simon S.1; Jordan, Michael, I3; Su, Weijie J.4
刊名MATHEMATICAL PROGRAMMING
2022-09-01
卷号195期号:1-2页码:79-148
关键词Convex optimization First-order method Polyak's heavy ball method Nesterov's accelerated gradient methods Ordinary differential equation Lyapunov function Gradient minimization
ISSN号0025-5610
DOI10.1007/s10107-021-01681-8
英文摘要Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODES do not distinguish between two fundamentally different algorithms-Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method-we study an alternative limiting process that yields high-resolution ODEs. We show that these ODES permit a general Lyapunov function framework for the analysis of convergence in both continuous and discrete time. We also show that these ODEs are more accurate surrogates for the underlying algorithms; in particular, they not only distinguish between NAG-SC and Polyak's heavy-ball method, but they allow the identification of a term that we refer to as "gradient correction" that is present in NAG-SC but not in the heavy-ball method and is responsible for the qualitative difference in convergence of the two methods. We also use the high-resolution ODE framework to study Nesterov's accelerated gradient method for (non-strongly) convex functions, uncovering a hitherto unknown result-that NAG-C minimizes the squared gradient norm at an inverse cubic rate. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates of NAG-C for smooth convex functions.
资助项目NSF[CCF-1763314] ; NSF[DMS-1847415] ; Army Research Office[W911NF-17-1-0304]
WOS研究方向Computer Science ; Operations Research & Management Science ; Mathematics
语种英语
出版者SPRINGER HEIDELBERG
WOS记录号WOS:000871120400004
内容类型期刊论文
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/60804]  
专题中国科学院数学与系统科学研究院
通讯作者Shi, Bin
作者单位1.Univ Washington, Seattle, WA 98195 USA
2.Chinese Acad Sci, Acad Math & Syst Sci, State Key Lab Sci & Engn Comp, Beijing, Peoples R China
3.Univ Calif Berkeley, Berkeley, CA 94720 USA
4.Univ Penn, Philadelphia, PA 19104 USA
推荐引用方式
GB/T 7714
Shi, Bin,Du, Simon S.,Jordan, Michael, I,et al. Understanding the acceleration phenomenon via high-resolution differential equations[J]. MATHEMATICAL PROGRAMMING,2022,195(1-2):79-148.
APA Shi, Bin,Du, Simon S.,Jordan, Michael, I,&Su, Weijie J..(2022).Understanding the acceleration phenomenon via high-resolution differential equations.MATHEMATICAL PROGRAMMING,195(1-2),79-148.
MLA Shi, Bin,et al."Understanding the acceleration phenomenon via high-resolution differential equations".MATHEMATICAL PROGRAMMING 195.1-2(2022):79-148.
个性服务
查看访问统计
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。


©版权所有 ©2017 CSpace - Powered by CSpace