A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
arXiv:2106.10439
Abstract
Since Nesterov's seminal 1983 work, many accelerated first-order optimization methods have been proposed, but their analyses lacks a common unifying structure. In this work, we identify a geometric structure satisfied by a wide range of first-order accelerated methods. Using this geometric insight, we present several novel generalizations of accelerated methods. Most interesting among them is a method that reduces the squared gradient norm with rate in the prox-grad setup, faster than the rates of Nesterov's FGM or Kim and Fessler's FPGM-m.
References in corpus (12)
- Proximal Splitting Methods in Signal Processing
- Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- Generalizing the optimized gradient method for smooth convex minimization
- From Nesterov's Estimate Sequence to Riemannian Acceleration
- Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
- A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent
- Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with Rate on Squared Gradient Norm
- Scaled Relative Graph of Normal Matrices
- Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization