The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than $1/k^2$

DOI10.1137/15M1046095zbMath1346.49048arXiv1510.08740OpenAlexW1837565340MaRDI QIDQ2817843

Publication date: 2 September 2016

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

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

zbMATH Keywords

convex optimization differential inclusion forward-backward method Nesterov method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical methods based on nonlinear programming (49M37) Ordinary differential inclusions (34A60)

Related Items

Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling ⋮ Convergence results of a new monotone inertial forward-backward splitting algorithm under the local Hölder error bound condition ⋮ Accelerated methods with fastly vanishing subgradients for structured non-smooth minimization ⋮ Accelerated modified inertial Mann and viscosity algorithms to find a fixed point of $\alpha$-inverse strongly monotone operators ⋮ First-order optimization algorithms via inertial systems with Hessian driven damping ⋮ First-order inertial algorithms involving dry friction damping ⋮ Stochastic gradient Hamiltonian Monte Carlo for non-convex learning ⋮ Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics ⋮ Nesterov’s accelerated gradient method for nonlinear ill-posed problems with a locally convex residual functional ⋮ Convergence analysis of two-step inertial Douglas-Rachford algorithm and application ⋮ Reflected three-operator splitting method for monotone inclusion problem ⋮ Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging ⋮ Convergence rates of a dual gradient method for constrained linear ill-posed problems ⋮ Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems ⋮ Improving “Fast Iterative Shrinkage-Thresholding Algorithm”: Faster, Smarter, and Greedier ⋮ Iterative method with inertial terms for nonexpansive mappings: applications to compressed sensing ⋮ Combining fast inertial dynamics for convex optimization with Tikhonov regularization ⋮ A fast two-point gradient algorithm based on sequential subspace optimization method for nonlinear ill-posed problems ⋮ First-order frameworks for continuous Newton-like dynamics governed by maximally monotone operators ⋮ From the Ravine Method to the Nesterov Method and Vice Versa: A Dynamical System Perspective ⋮ Forward-Backward Envelope for the Sum of Two Nonconvex Functions: Further Properties and Nonmonotone Linesearch Algorithms ⋮ A strong convergence result involving an inertial forward-backward algorithm for monotone inclusions ⋮ Unnamed Item ⋮ Convergence rate of inertial proximal algorithms with general extrapolation and proximal coefficients ⋮ On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng's modified forward-backward methods with inertial effects ⋮ Unnamed Item ⋮ Alternating forward-backward splitting for linearly constrained optimization problems ⋮ Quasi-Nonexpansive Iterations on the Affine Hull of Orbits: From Mann's Mean Value Algorithm to Inertial Methods ⋮ Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3 ⋮ Generalized forward-backward splitting with penalization for monotone inclusion problems ⋮ Unnamed Item ⋮ Continuum Limits of Nonlocal $p$-Laplacian Variational Problems on Graphs ⋮ Behavior of accelerated gradient methods near critical points of nonconvex functions ⋮ Convergence rate of a relaxed inertial proximal algorithm for convex minimization ⋮ New inertial forward-backward algorithm for convex minimization with applications ⋮ Finite Convergence of Proximal-Gradient Inertial Algorithms Combining Dry Friction with Hessian-Driven Damping ⋮ Analysis of a heuristic rule for the IRGNM in Banach spaces with convex regularization terms ⋮ Activity Identification and Local Linear Convergence of Forward--Backward-type Methods ⋮ The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$ ⋮ On FISTA with a relative error rule ⋮ Applying FISTA to optimization problems (with or) without minimizers ⋮ Fast convergence of inertial gradient dynamics with multiscale aspects ⋮ Convergence Rates of Inertial Forward-Backward Algorithms ⋮ Convergence of damped inertial dynamics governed by regularized maximally monotone operators ⋮ Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient ⋮ Unnamed Item ⋮ Inertial approximation method for split variational inclusion problem in Banach spaces ⋮ A generic online acceleration scheme for optimization algorithms via relaxation and inertia ⋮ A fast two-point gradient method for solving non-smooth nonlinear ill-posed problems ⋮ Variable metric techniques for forward-backward methods in imaging ⋮ Numerical computations of split Bregman method for fourth order total variation flow ⋮ Convergence of first-order methods via the convex conjugate ⋮ Newton-like Inertial Dynamics and Proximal Algorithms Governed by Maximally Monotone Operators ⋮ Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization ⋮ A note on the minimization of a Tikhonov functional with ℓ¹-penalty ⋮ Convergence Rates of Damped Inertial Dynamics under Geometric Conditions and Perturbations ⋮ A duality based approach to the minimizing total variation flow in the space $H^{-s}$ ⋮ Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping ⋮ Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators ⋮ An explicit algorithm for solving monotone variational inequalities ⋮ An inertial proximal-gradient penalization scheme for constrained convex optimization problems ⋮ On the proximal gradient algorithm with alternated inertia ⋮ Fast convergence of generalized forward-backward algorithms for structured monotone inclusions ⋮ Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions ⋮ Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions ⋮ On the interplay between acceleration and identification for the proximal gradient algorithm ⋮ Heuristic rule for non-stationary iterated Tikhonov regularization in Banach spaces ⋮ Accelerated Residual Methods for the Iterative Solution of Systems of Equations ⋮ Inertial Variable Metric Techniques for the Inexact Forward--Backward Algorithm ⋮ Convergence Rate Analysis of Inertial Krasnoselskii–Mann Type Iteration with Applications ⋮ Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity ⋮ Lagrangian penalization scheme with parallel forward-backward splitting ⋮ Functional penalised basis pursuit on spheres ⋮ New convergence results for inertial Krasnoselskii-Mann iterations in Hilbert spaces with applications ⋮ An accelerated homotopy perturbation iteration for nonlinear ill-posed problems in Banach spaces with uniformly convex penalty ⋮ Continuous Newton-like inertial dynamics for monotone inclusions ⋮ Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule ⋮ New analysis of linear convergence of gradient-type methods via unifying error bound conditions ⋮ On DC based methods for phase retrieval ⋮ A proximal regularized Gauss-Newton-Kaczmarz method and its acceleration for nonlinear ill-posed problems ⋮ Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces ⋮ Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates ⋮ Second order asymptotical regularization methods for inverse problems in partial differential equations ⋮ A new proximal iterative hard thresholding method with extrapolation for $\ell _0$ minimization ⋮ Damped inertial dynamics with vanishing Tikhonov regularization: strong asymptotic convergence towards the minimum norm solution ⋮ Convergence rates of forward-Douglas-Rachford splitting method ⋮ A minimization approach for constructing generalized barycentric coordinates and its computation ⋮ Convergence analysis of projection method for variational inequalities ⋮ Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order $o(1/k^2)$ ⋮ Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems ⋮ The two-point gradient methods for nonlinear inverse problems based on Bregman projections ⋮ Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimization ⋮ Regularization of inverse problems by two-point gradient methods in Banach spaces ⋮ Understanding the acceleration phenomenon via high-resolution differential equations ⋮ A control-theoretic perspective on optimal high-order optimization ⋮ Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions ⋮ Time-varying continuous-time optimisation with pre-defined finite-time stability ⋮ Tikhonov Regularization of a Perturbed Heavy Ball System with Vanishing Damping ⋮ A fast continuous time approach with time scaling for nonsmooth convex optimization ⋮ A nested primal-dual FISTA-like scheme for composite convex optimization problems ⋮ Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function ⋮ Unnamed Item ⋮ 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 ⋮ Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates ⋮ Accelerated dynamics with dry friction via time scaling and averaging of doubly nonlinear evolution equations ⋮ A data-driven Kaczmarz iterative regularization method with non-smooth constraints for ill-posed problems ⋮ Deterministic neural networks optimization from a continuous and energy point of view ⋮ Accelerated smoothing hard thresholding algorithms for $\ell_0$ regularized nonsmooth convex regression problem ⋮ Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme ⋮ A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems ⋮ Smoothing accelerated proximal gradient method with fast convergence rate for nonsmooth convex optimization beyond differentiability ⋮ Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping ⋮ Accelerated gradient methods combining Tikhonov regularization with geometric damping driven by the Hessian ⋮ Fast optimization via inertial dynamics with closed-loop damping ⋮ A Projected Nesterov–Kaczmarz Approach to Stellar Population-Kinematic Distribution Reconstruction in Extragalactic Archaeology ⋮ From Halpern's fixed-point iterations to Nesterov's accelerated interpretations for root-finding problems ⋮ Fast convex optimization via a third-order in time evolution equation: TOGES-V an improved version of TOGES* ⋮ On inertial iterated Tikhonov methods for solving ill-posed problems ⋮ A Riemannian Proximal Newton Method ⋮ Convergence analysis of a two-point gradient method for nonlinear ill-posed problems ⋮ Unnamed Item ⋮ Inertial methods for fixed point problems and zero point problems of the sum of two monotone mappings ⋮ A new Kaczmarz-type method and its acceleration for nonlinear ill-posed problems ⋮ An accelerated sequential subspace optimization method based on homotopy perturbation iteration for nonlinear ill-posed problems ⋮ Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings ⋮ Hessian Barrier Algorithms for Linearly Constrained Optimization Problems ⋮ Fast Proximal Methods via Time Scaling of Damped Inertial Dynamics ⋮ On Quasi-Newton Forward-Backward Splitting: Proximal Calculus and Convergence ⋮ Adaptive FISTA for Nonconvex Optimization ⋮ Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs ⋮ Unnamed Item ⋮ Accelerated Iterative Regularization via Dual Diagonal Descent ⋮ ACCELERATED PROJECTION-BASED FORWARD-BACKWARD SPLITTING ALGORITHMS FOR MONOTONE INCLUSION PROBLEMS ⋮ Analysis of a generalized regularized Gauss–Newton method under heuristic rule in Banach spaces ⋮ Weak convergence for variational inequalities with inertial-type method ⋮ Fast convex optimization via a third-order in time evolution equation ⋮ Strong convergence of inertial forward–backward methods for solving monotone inclusions

Cites Work