Optimal Convergence Rates for Nesterov Acceleration

DOI10.1137/18M1186757zbMath1453.90117arXiv1805.05719OpenAlexW2994888550WikidataQ126559838 ScholiaQ126559838MaRDI QIDQ5206941

Aude Rondepierre, Charles Dossal, Jean-François Aujol

Publication date: 19 December 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.05719

zbMATH Keywords

optimizationrate of convergenceordinary differential equationsLyapunov functionsŁojasiewicz property

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Asymptotic properties of solutions to ordinary differential equations (34D05)

Related Items

Weak and linear convergence of a generalized proximal point algorithm with alternating inertial steps for a monotone inclusion problem ⋮ A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem ⋮ Convergence Rates of the Heavy Ball Method for Quasi-strongly Convex Optimization ⋮ From the Ravine Method to the Nesterov Method and Vice Versa: A Dynamical System Perspective ⋮ Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems ⋮ Fast convergence of inertial dynamics with Hessian-driven damping under geometry assumptions ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ Double inertial parameters forward-backward splitting method: Applications to compressed sensing, image processing, and SCAD penalty problems ⋮ Projection methods with alternating inertial steps for variational inequalities: weak and linear convergence ⋮ FISTA is an automatic geometrically optimized algorithm for strongly convex functions ⋮ Convergence rate of a relaxed inertial proximal algorithm for convex minimization ⋮ Inertial Newton algorithms avoiding strict saddle points ⋮ Convergence rates of the heavy-ball method under the Łojasiewicz property ⋮ The Nesterov accelerated gradient algorithm for auto-regressive exogenous models with random lost measurements: interpolation method and auxiliary model method ⋮ Optimal decay rates for semi-linear non-autonomous evolution equations with vanishing damping ⋮ Optimal convergence rates for damped inertial gradient dynamics with flat geometries ⋮ Convergence Rates of Damped Inertial Dynamics under Geometric Conditions and Perturbations ⋮ An extension of the second order dynamical system that models Nesterov's convex gradient method ⋮ Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance ⋮ Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization ⋮ Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions ⋮ Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems ⋮ Convergence results of two-step inertial proximal point algorithm ⋮ Convergence rates of first- and higher-order dynamics for solving linear ill-posed problems ⋮ Convergence rates of damped inerial dynamics from multi-degree-of-freedom system ⋮ On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping ⋮ Inertial projection and contraction algorithms with larger step sizes for solving quasimonotone variational inequalities ⋮ Proximal Gradient Methods for Machine Learning and Imaging

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Asymptotic for the perturbed heavy ball system with vanishing damping term
• Asymptotics for some vibro-impact problems with a linear dissipation term
• Error bounds and Hölder metric subregularity
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• On semi- and subanalytic geometry
• From error bounds to the complexity of first-order descent methods for convex functions
• Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity
• Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions
• On damped second-order gradient systems
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Stability of Over-Relaxations for the Forward-Backward Algorithm, Application to FISTA
• On the long time behavior of second order differential equations with asymptotically small dissipation
• 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 Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$
• Asymptotic for a second-order evolution equation with convex potential andvanishing damping term
• Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
• Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term