Multiscale analysis of accelerated gradient methods
From MaRDI portal
Abstract: Accelerated gradient descent iterations are widely used in optimization. It is known that, in the continuous-time limit, these iterations converge to a second-order differential equation which we refer to as the accelerated gradient flow. Using geometric singular perturbation theory, we show that, under certain conditions, the accelerated gradient flow possesses an attracting invariant slow manifold to which the trajectories of the flow converge asymptotically. We obtain a general explicit expression in the form of functional series expansions that approximates the slow manifold to any arbitrary order of accuracy. To the leading order, the accelerated gradient flow reduced to this slow manifold coincides with the usual gradient descent. We illustrate the implications of our results on three examples.
Recommendations
- A variational perspective on accelerated methods in optimization
- Understanding the acceleration phenomenon via high-resolution differential equations
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A frequency-domain analysis of inexact gradient methods
- On the fast convergence of random perturbations of the gradient flow
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A variational perspective on accelerated methods in optimization
- An adjoint-based approach for finding invariant solutions of Navier-Stokes equations
- Analysis and design of optimization algorithms via integral quadratic constraints
- Attractors for infinite-dimensional non-autonomous dynamical systems
- Geometric singular perturbation theory for ordinary differential equations
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 799793 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Local bifurcations, center manifolds, and normal forms in infinite-dimensional dynamical systems
- Multiple time scale dynamics
- Normally hyperbolic invariant manifolds in dynamical systems
- Some methods of speeding up the convergence of iteration methods
- The fundamental theorem of algebra and complexity theory
- Where do inertial particles go in fluid flows?
Cited in
(5)- A convergence analysis of the perturbed compositional gradient flow: averaging principle and normal deviations
- Understanding the acceleration phenomenon via high-resolution differential equations
- Accuracy analysis of acceleration schemes for stiff multiscale problems
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A variational perspective on accelerated methods in optimization
This page was built for publication: Multiscale analysis of accelerated gradient methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124000)
