The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$

Abstract

The {\it forward-backward algorithm} is a powerful tool for solving optimization problems with a {\it additively separable} and {\it smooth} + {\it nonsmooth} structure. In the convex setting, a simple but ingenious acceleration scheme developed by Nesterov has been proved useful to improve the theoretical rate of convergence for the function values from the standard $\mathcal{O}(k^{-1})$ down to $\mathcal{O}(k^{-2})$. In this short paper, we prove that the rate of convergence of a slight variant of Nesterov's accelerated forward-backward method, which produces {\it convergent} sequences, is actually $o(k^{-2})$, rather than $\mathcal{O}(k^{-2})$. Our arguments rely on the connection between this algorithm and a second-order differential inclusion with vanishing damping.

Cited by in corpus (40)

• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• From differential equation solvers to accelerated first-order methods for convex optimization
• Direct Runge-Kutta Discretization Achieves Acceleration
• Quantitative convergence analysis of iterated expansive, set-valued mappings
• Full Waveform Inversion with Adaptive Regularization
• Nesterov's Accelerated Gradient Method for Nonlinear Ill-Posed Problems with a Locally Convex Residual Functional
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Convergence Analysis of Projection Method for Variational Inequalities
• An inertial three-operator splitting algorithm with applications to image inpainting
• Local and Global Convergence of a General Inertial Proximal Splitting Scheme
• Weak Convergence for Variational Inequalities with Inertial-Type Method
• Quasinonexpansive Iterations on the Affine Hull of Orbits: From Mann's Mean Value Algorithm to Inertial Methods
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Numerical computations of split Bregman method for fourth order total variation flow
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Accelerated iterative regularization via dual diagonal descent
• A Doubly Accelerated Inexact Proximal Point Method for Nonconvex Composite Optimization Problems
• Functional Penalised Basis Pursuit on Spheres
• Convex optimization via inertial algorithms with vanishing Tikhonov regularization: fast convergence to the minimum norm solution
• Strong convergence of modified inertial Mann algorithms for nonexpansive mappings
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Hessian barrier algorithms for linearly constrained optimization problems
• Faster Convergence in Deep-Predictive-Coding Networks to Learn Deeper Representations
• A Generic online acceleration scheme for Optimization algorithms via Relaxation and Inertia
• Accelerated projection-based forward-backward splitting algorithms for monotone inclusion problems
• On the Interplay between Acceleration and Identification for the Proximal Gradient algorithm
• A note on the minimization of a Tikhonov functional with ${\ell }^1$-penalty
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• Inertial primal-dual methods for linear equality constrained convex optimization problems
• Non-Stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• Applying FISTA to optimization problems (with or) without minimizers
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems
• Fast convergence of generalized forward-backward algorithms for structured monotone inclusions
• Accelerated forward-backward method with fast convergence rate for nonsmooth convex optimization beyond differentiability
• Inertial Three-Operator Splitting Method and Applications
• Projection Neural Network for a Class of Sparse Regression Problems with Cardinality Penalty
• Monotone Inclusions, Acceleration and Closed-Loop Control
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• Second order asymptotical regularization methods for inverse problems in partial differential equations