Understanding the acceleration phenomenon via high-resolution differential equations

doi:10.1007/s10107-021-01681-8

CSpace

	Understanding the acceleration phenomenon via high-resolution differential equations
	Shi, Bin 1; Du, Simon S.2; Jordan, Michael, I 3; Su, Weijie J.4
	2022-09-01
发表期刊	MATHEMATICAL PROGRAMMING
ISSN	0025-5610
卷号	195 期号:1-2 页码:79-148
摘要	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.
关键词	Convex optimization First-order method Polyak's heavy ball method Nesterov's accelerated gradient methods Ordinary differential equation Lyapunov function Gradient minimization
DOI	10.1007/s10107-021-01681-8
收录类别	SCI
语种	英语
资助项目	NSF[CCF-1763314] ; NSF[DMS-1847415] ; Army Research Office[W911NF-17-1-0304]
WOS研究方向	Computer Science ; Operations Research & Management Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000871120400004
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/60805
专题	中国科学院数学与系统科学研究院
通讯作者	Shi, Bin
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, State Key Lab Sci & Engn Comp, Beijing, Peoples R China 2.Univ Washington, Seattle, WA 98195 USA 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.