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 |
DOI | 10.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. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论