Composing Optimized Stepsize Schedules for Gradient Descent

• 成果类型: Article; Early Access
• 署名作者: Grimmer, Benjamin; Shu, Kevin; Wang, Alex L.
• 署名单位: Johns Hopkins University; California Institute of Technology; Purdue University System; Purdue University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0764
• 发表日期: 2025-11-04
• 关键词: gradient descent; performance estimation; silver stepsizes; H-duality; worst-case performance; 1st-order methods

摘要

Recent works by Altschuler and Parrilo and Grimmer, Shu, Wang have shown that it is possible to accelerate the convergence of gradient descent on smooth convex functions, even without momentum, just by picking special stepsizes. In this paper, we provide a general theory for composing stepsize schedules, capturing all recent advances in this area and more. We propose three notions of composable stepsize schedules with elementary associated composition operations for combining them. From these operations, in addition to recovering recent works, we construct three highly optimized sequences of stepsize schedules. We first construct optimized stepsize schedules of every length, generalizing the exponentially spaced silver stepsizes of Altschuler and Parrilo. We then construct highly optimized stepsize schedules for minimizing final objective gap or gradient norm, improving on prior rates by constants and, more importantly, matching or beating the numerically computed minimax optimal schedules of Das Gupta, Van Parys, Ryu. We conjecture that these schedules are in fact minimax (information theoretic) optimal. Several novel tertiary results follow from our theory, including recovery of the recent dynamic gradient norm minimizing short stepsizes of Rotaru, Glineur, Patrinos and extending them to objective gap minimization.