72. Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions
Invited abstract in session WF-2: Recent advances in computer-aided analyses of optimization algorithms II, stream Conic optimization: theory, algorithms and applications.
Wednesday, 16:20 - 18:00Room: M:O
Authors (first author is the speaker)
| 1. | Teodor Rotaru
|
| Electrical Engineering, KU Leuven | |
| 2. | François Glineur
|
| ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain) | |
| 3. | Panagiotis Patrinos
|
| Electrical Engineering, KU Leuven |
Abstract
We derive exact worst-case convergence rates on the minimum gradient norm of the gradient descent iterates with constant stepsizes. Our analysis covers all possible stepsizes and arbitrary upper/lower bounds on the objective function’s curvature, thus including convex, strongly convex, and weakly convex (hypoconvex) objective functions.
Unlike prior approaches, relying solely on inequalities connecting consecutive iterations, our analysis employs inequalities involving an iterate and its two predecessors. While this complicates the proofs to some extent, it enables to achieve, for the first time, an exact full-range analysis of gradient descent for any constant stepsizes, (covering, in particular, normalized stepsizes greater than one), whereas the literature contained only conjectured rates of this type.
Our analysis accommodates arbitrary bounds on both the upper and lower curvatures of the smooth objective function. In the nonconvex case, this extends existing partial results that are valid only for gradient Lipschitz functions (i.e., where lower and upper bounds on curvature are equal), leading to improved rates for weakly convex functions.
From our exact rates, we deduce the optimal constant stepsize for gradient descent. Leveraging our analysis, we furthermore introduce a new variant of gradient descent based on a unique, fixed sequence of variable stepsizes, demonstrating its superiority over any constant stepsize schedule in the (strongly) convex case.
Keywords
- Complexity and efficiency of optimization algorithms
- SS - Conic Optimization and Applications
Status: accepted
Back to the list of papers