From the ravine method to the Nesterov method and vice versa: a dynamical system perspective
From MaRDI portal
(Redirected from Publication:5097023)
convergence ratesHessian driven dampinghigh resolution ODELyapunov analysisNesterov accelerated gradient methodproximal algorithmsRavine method
Dynamical systems in optimization and economics (37N40) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Management decision making, including multiple objectives (90B50) Convex programming (90C25)
Abstract: We revisit the Ravine method of Gelfand and Tsetlin from a dynamical system perspective, study its convergence properties, and highlight its similarities and differences with the Nesterov accelerated gradient method. The two methods are closely related. They can be deduced from each other by reversing the order of the extrapolation and gradient operations in their definitions. They benefit from similar fast convergence of values and convergence of iterates for general convex objective functions. We will also establish the high resolution ODE of the Ravine and Nesterov methods, and reveal an additional geometric damping term driven by the Hessian for both methods. This will allow us to prove fast convergence towards zero of the gradients not only for the Ravine method but also for the Nesterov method for the first time. We also highlight connections to other algorithms stemming from more subtle discretization schemes, and finally describe a Ravine version of the proximal-gradient algorithms for general structured smooth + non-smooth convex optimization problems.
Recommendations
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
- An extension of the second order dynamical system that models Nesterov's convex gradient method
- Optimal convergence rates for Nesterov acceleration
- Understanding the acceleration phenomenon via high-resolution differential equations
Cites work
- A continuous dynamical Newton-like approach to solving monotone inclusions
- A dynamical approach to an inertial forward-backward algorithm for convex minimization
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A second-order differential system with Hessian-driven damping; application to non-elastic shock laws
- A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
- Accelerated and inexact forward-backward algorithms
- An extension of the second order dynamical system that models Nesterov's convex gradient method
- Asymptotic behavior of Newton-like inertial dynamics involving the sum of potential and nonpotential terms
- Asymptotic for a second-order evolution equation with convex potential and vanishing damping term
- Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity
- Backward-forward algorithms for structured monotone inclusions in Hilbert spaces
- Continuous Newton-like inertial dynamics for monotone inclusions
- Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule
- Convergence rates of inertial forward-backward algorithms
- Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time
- Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
- Fast convex optimization via inertial dynamics with Hessian driven damping
- Finite convergence of proximal-gradient inertial algorithms combining dry friction with Hessian-driven damping
- Finite-time stabilization of continuous inertial dynamics combining dry friction with Hessian-driven damping
- First-order frameworks for continuous Newton-like dynamics governed by maximally monotone operators
- First-order optimization algorithms via inertial systems with Hessian driven damping
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3670030 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- New Proximal Point Algorithms for Convex Minimization
- Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators
- Newton-type inertial algorithms for solving monotone equations Governed by sums of potential and nonpotential operators
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- On the Convergence of the Proximal Point Algorithm for Convex Minimization
- On the long time behavior of second order differential equations with asymptotically small dissipation
- On the Long Time Behavior of Second Order Differential Equations with Asymptotically Small Dissipation
- Optimal convergence rates for Nesterov acceleration
- Optimized first-order methods for smooth convex minimization
- Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient
- Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
- Some methods of speeding up the convergence of iteration methods
- The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$
- THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
- Tikhonov regularization of a second order dynamical system with Hessian driven damping
- Understanding the acceleration phenomenon via high-resolution differential equations
Cited in
(18)- Accelerated gradient methods combining Tikhonov regularization with geometric damping driven by the Hessian
- From Halpern's fixed-point iterations to Nesterov's accelerated interpretations for root-finding problems
- Continuous Newton-like Methods Featuring Inertia and Variable Mass
- Fast convergence of inertial multiobjective gradient-like systems with asymptotic vanishing damping
- Near-optimal closed-loop method via Lyapunov damping
- On a class of second-order dynamical systems involving viscous and Hessian-driven damping
- From inertial systems to proximal flows: the large damping limit of implicit Hessian-driven dynamics
- Proximal subgradient norm minimization of ISTA and FISTA
- The application of Goeken-Johnson's Runge-Kutta methods in unconstrained convex optimization
- Revisiting Nesterov's acceleration via high-resolution differential equations
- On the application of explicit Runge-Kutta methods to the construction of stochastic gradient descent methods for convex optimization
- VFOSA: variance-reduced fast operator splitting algorithms for generalized equations
- On the structural monotone inclusion of continuous second-order dynamics combining dry friction and Hessian-driven damping.
- On the o(1/k^2) convergence rate analysis for general inertial gradient type method
- High-resolution inertial dynamics with time-rescaled gradients for nonsmooth convex optimization
- Accelerated optimization through time-scale analysis of inertial dynamics with asymptotic vanishing and Hessian-driven dampings
- Comparative analysis of accelerated gradient algorithms for convex optimization: high and super resolution ODE approach
- Plug-and-play image restoration with flow matching: a continuous viewpoint
This page was built for publication: From the ravine method to the Nesterov method and vice versa: a dynamical system perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097023)
