Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3

DOI10.1051/cocv/2017083zbMath1437.49045arXiv1706.05671OpenAlexW2963022670MaRDI QIDQ5107904

Hassan Riahi, Zaki Chbani, Hedy Attouch

Publication date: 29 April 2020

Published in: ESAIM: Control, Optimisation and Calculus of Variations (Search for Journal in Brave)

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

zbMATH Keywords

subcritical casestructured convex optimizationNesterov methodaccelerated gradient methodFISTAinertial forward-backward algorithmsvanishing dampingproximal-based methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical methods based on nonlinear programming (49M37)

Related Items (56)

Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling ⋮ Continuous dynamics related to monotone inclusions and non-smooth optimization problems ⋮ First-order optimization algorithms via inertial systems with Hessian driven damping ⋮ First-order inertial algorithms involving dry friction damping ⋮ Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics ⋮ Fast inertial dynamic algorithm with smoothing method for nonsmooth convex optimization ⋮ Unnamed Item ⋮ Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ From the Ravine Method to the Nesterov Method and Vice Versa: A Dynamical System Perspective ⋮ Accelerated differential inclusion for convex optimization ⋮ Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping ⋮ On the strong convergence of the trajectories of a Tikhonov regularized second order dynamical system with asymptotically vanishing damping ⋮ Accelerated dynamics with dry friction via time scaling and averaging of doubly nonlinear evolution equations ⋮ Unnamed Item ⋮ 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 ⋮ Convergence rate of inertial proximal algorithms with general extrapolation and proximal coefficients ⋮ A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization ⋮ Inertial Newton algorithms avoiding strict saddle points ⋮ Convergence of inertial dynamics driven by sums of potential and nonpotential operators with implicit Newton-like damping ⋮ Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping ⋮ Fast optimization via inertial dynamics with closed-loop damping ⋮ A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem ⋮ Fast convex optimization via a third-order in time evolution equation: TOGES-V an improved version of TOGES* ⋮ Second order splitting dynamics with vanishing damping for additively structured monotone inclusions ⋮ Finite Convergence of Proximal-Gradient Inertial Algorithms Combining Dry Friction with Hessian-Driven Damping ⋮ Optimal convergence rates for damped inertial gradient dynamics with flat geometries ⋮ The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$ ⋮ Applying FISTA to optimization problems (with or) without minimizers ⋮ Fast convergence of inertial gradient dynamics with multiscale aspects ⋮ Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient ⋮ Newton-like Inertial Dynamics and Proximal Algorithms Governed by Maximally Monotone Operators ⋮ Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization ⋮ Proximal alternating penalty algorithms for nonsmooth constrained convex optimization ⋮ Tikhonov regularization of a second order dynamical system with Hessian driven damping ⋮ Convergence Rates of Damped Inertial Dynamics under Geometric Conditions and Perturbations ⋮ Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping ⋮ An extension of the second order dynamical system that models Nesterov's convex gradient method ⋮ 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 ⋮ A second-order adaptive Douglas-Rachford dynamic method for maximal \(\alpha\)-monotone operators ⋮ Optimal Convergence Rates for Nesterov Acceleration ⋮ A second-order dynamical approach with variable damping to nonconvex smooth minimization ⋮ On the convergence of a class of inertial dynamical systems with Tikhonov regularization ⋮ Continuous Newton-like inertial dynamics for monotone inclusions ⋮ Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule ⋮ Convergence Rates of Inertial Primal-Dual Dynamical Methods for Separable Convex Optimization Problems ⋮ Fast Proximal Methods via Time Scaling of Damped Inertial Dynamics ⋮ From differential equation solvers to accelerated first-order methods for convex optimization ⋮ A control-theoretic perspective on optimal high-order optimization ⋮ Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition ⋮ Accelerated Iterative Regularization via Dual Diagonal Descent ⋮ Generalized Momentum-Based Methods: A Hamiltonian Perspective ⋮ Tikhonov Regularization of a Perturbed Heavy Ball System with Vanishing Damping ⋮ Fast convex optimization via a third-order in time evolution equation ⋮ On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Optimized first-order methods for smooth convex minimization
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Introductory lectures on convex optimization. A basic course.
• Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity
• Performance of first-order methods for smooth convex minimization: a novel approach
• Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule
• On damped second-order gradient systems
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS^*
• The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than $1/k^2$
• Accelerated and Inexact Forward-Backward Algorithms
• Convex Optimization in Normed Spaces
• Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time
• 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
• New Proximal Point Algorithms for Convex Minimization
• On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
• Optimisation and asymptotic stability
• Convergence Rates of Inertial Forward-Backward Algorithms
• Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• Convex analysis and monotone operator theory in Hilbert spaces

This page was built for publication: Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3