Factor-2 acceleration of accelerated gradient methods
From MaRDI portal
Publication:6073850
Abstract: The optimized gradient method (OGM) provides a factor- speedup upon Nesterov's celebrated accelerated gradient method in the convex (but non-strongly convex) setup. However, this improved acceleration mechanism has not been well understood; prior analyses of OGM relied on a computer-assisted proof methodology, so the proofs were opaque for humans despite being verifiable and correct. In this work, we present a new analysis of OGM based on a Lyapunov function and linear coupling. These analyses are developed and presented without the assistance of computers and are understandable by humans. Furthermore, we generalize OGM's acceleration mechanism and obtain a factor- speedup in other setups: acceleration with a simpler rational stepsize, the strongly convex setup, and the mirror descent setup.
Recommendations
- Generalizing the optimized gradient method for smooth convex minimization
- A Lyapunov analysis of accelerated methods in optimization
- On the convergence analysis of the optimized gradient method
- Understanding the acceleration phenomenon via high-resolution differential equations
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
Cites work
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A variational perspective on accelerated methods in optimization
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated proximal point method for maximally monotone operators
- Accelerating the cubic regularization of Newton's method on convex problems
- Adaptive restart of the optimized gradient method for convex optimization
- An optimal gradient method for smooth strongly convex minimization
- Analysis and design of optimization algorithms via integral quadratic constraints
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- Convergence rates of the heavy ball method for quasi-strongly convex optimization
- Convex Analysis
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Efficient first-order methods for convex minimization: a constructive approach
- Exact worst-case performance of first-order methods for composite convex optimization
- Generalizing the optimized gradient method for smooth convex minimization
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- Information-based complexity of linear operator equations
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Introductory lectures on convex optimization. A basic course.
- Katyusha: the first direct acceleration of stochastic gradient methods
- Large-scale convex optimization. Algorithms \& analyses via monotone operators
- Linear coupling: an ultimate unification of gradient and mirror descent
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- On optimality of Krylov's information when solving linear operator equations
- On the convergence analysis of the optimized gradient method
- On the convergence rate of the Halpern-iteration
- On the oracle complexity of smooth strongly convex minimization
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- Optimal convergence rates for Nesterov acceleration
- Optimized first-order methods for smooth convex minimization
- Performance of first-order methods for smooth convex minimization: a novel approach
- Potential-function proofs for gradient methods
- Primal-dual subgradient methods for convex problems
- Relatively smooth convex optimization by first-order methods, and applications
- Smooth minimization of non-smooth functions
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- The exact information-based complexity of smooth convex minimization
- Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems
- Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
- Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation
Cited in
(7)- A Lyapunov analysis of accelerated methods in optimization
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- Provably faster gradient descent via long steps
- Accelerated minimax algorithms flock together
- A C-FISTA-type Krasnosel'skiĭ-Mann iteration with applications to TV-based denoising problem and image in-painting
- A new strongly convergent adaptive inertial subgradient extragradient method with convergence rates
- Computer-assisted design of accelerated composite optimization methods: OptISTA
This page was built for publication: Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073850)
