Adaptive restart for accelerated gradient schemes
From MaRDI portal
Publication:2355332
Abstract: In this paper we demonstrate a simple heuristic adaptive restart technique that can dramatically improve the convergence rate of accelerated gradient schemes. The analysis of the technique relies on the observation that these schemes exhibit two modes of behavior depending on how much momentum is applied. In what we refer to as the 'high momentum' regime the iterates generated by an accelerated gradient scheme exhibit a periodic behavior, where the period is proportional to the square root of the local condition number of the objective function. This suggests a restart technique whereby we reset the momentum whenever we observe periodic behavior. We provide analysis to show that in many cases adaptively restarting allows us to recover the optimal rate of convergence with no prior knowledge of function parameters.
Recommendations
- Adaptive restart of the optimized gradient method for convex optimization
- A simple nearly optimal restart scheme for speeding up first-order methods
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Sharpness, restart, and acceleration
- An adaptive accelerated first-order method for convex optimization
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Compressed sensing
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Introductory lectures on convex optimization. A basic course.
- Methods of conjugate gradients for solving linear systems
- Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage
- On parallel complexity of nonsmooth convex optimization
- ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Stable signal recovery from incomplete and inaccurate measurements
- Templates for convex cone problems with applications to sparse signal recovery
Cited in
(only showing first 100 items - show all)- New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure
- Adaptive restart of the optimized gradient method for convex optimization
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- An adaptive three-term conjugate gradient method based on self-scaling memoryless BFGS matrix
- Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
- Acceleration of the PDHGM on partially strongly convex functions
- How to choose biomarkers in view of parameter estimation
- Convergence of first-order methods via the convex conjugate
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- Acceleration of the imaginary time method for spectrally computing the stationary states of Gross-Pitaevskii equations
- Accelerated proximal gradient method for elastoplastic analysis with von Mises yield criterion
- Linear convergence rates for variants of the alternating direction method of multipliers in smooth cases
- A proximal difference-of-convex algorithm with extrapolation
- Universal method for stochastic composite optimization problems
- Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity
- Proximal algorithms in statistics and machine learning
- On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems
- 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
- Stochastic optimization with adaptive restart: a framework for integrated local and global learning
- On the interplay between acceleration and identification for the proximal gradient algorithm
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- An accelerated IRNN-iteratively reweighted nuclear norm algorithm for nonconvex nonsmooth low-rank minimization problems
- A dual reformulation and solution framework for regularized convex clustering problems
- Bounds for the tracking error of first-order online optimization methods
- Functional penalised basis pursuit on spheres
- Is there an analog of Nesterov acceleration for gradient-based MCMC?
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
- An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
- Accelerated information gradient flow
- An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing
- An improved linear convergence of FISTA for the LASSO problem with application to CT image reconstruction
- Sobolev gradients for the Möbius energy
- An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems
- A piecewise conservative method for unconstrained convex optimization
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- A strongly convergent algorithm for solving common variational inclusion with application to image recovery problems
- Alternating direction based method for optimal control problem constrained by Stokes equation
- Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems
- Understanding the acceleration phenomenon via high-resolution differential equations
- From differential equation solvers to accelerated first-order methods for convex optimization
- High-performance optimal incentive-seeking in transactive control for traffic congestion
- Online optimization of switched LTI systems using continuous-time and hybrid accelerated gradient flows
- The superiorization method with restarted perturbations for split minimization problems with an application to radiotherapy treatment planning
- On consistency and sparsity for high-dimensional functional time series with application to autoregressions
- Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
- Restarting Frank-Wolfe: faster rates under Hölderian error bounds
- Additive Schwarz methods for convex optimization with backtracking
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- Convergence results of a new monotone inertial forward-backward splitting algorithm under the local Hölder error bound condition
- Accelerated proximal gradient method for bi-modulus static elasticity
- A parallel Tseng's splitting method for solving common variational inclusion applied to signal recovery problems
- Optimization for deep learning: an overview
- An adaptive primal-dual framework for nonsmooth convex minimization
- An accelerated Uzawa method for application to frictionless contact problem
- Accelerated proximal point method for maximally monotone operators
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Nesterov-aided stochastic gradient methods using Laplace approximation for Bayesian design optimization
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Generalized self-concordant functions: a recipe for Newton-type methods
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- Adaptive Euclidean maps for histograms: generalized Aitchison embeddings
- A fast first-order optimization approach to elastoplastic analysis of skeletal structures
- Projected shrinkage algorithm for box-constrained \(\ell _1\)-minimization
- A secant-based Nesterov method for convex functions
- Combining fast inertial dynamics for convex optimization with Tikhonov regularization
- Linear convergence of first order methods for non-strongly convex optimization
- Iteratively reweighted \(\ell _1\) algorithms with extrapolation
- Efficient, certifiably optimal clustering with applications to latent variable graphical models
- Enhanced proximal DC algorithms with extrapolation for a class of structured nonsmooth DC minimization
- Fast proximal algorithms for nonsmooth convex optimization
- Robust hybrid zero-order optimization algorithms with acceleration via averaging in time
- Accelerated additive Schwarz methods for convex optimization with adaptive restart
- An engineering interpretation of Nesterov's convex minimization algorithm and time integration: application to optimal fiber orientation
- A proximal algorithm with backtracked extrapolation for a class of structured fractional programming
- Fast gradient methods for uniformly convex and weakly smooth problems
- Proximal gradient methods for general smooth graph total variation model in unsupervised learning
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- Convergence rates of the heavy-ball method under the Łojasiewicz property
- A simple nearly optimal restart scheme for speeding up first-order methods
- A smoothing proximal gradient algorithm with extrapolation for the relaxation of \({\ell_0}\) regularization problem
- Majorization-minimization-based Levenberg-Marquardt method for constrained nonlinear least squares
- Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
- Activity identification and local linear convergence of forward-backward-type methods
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Optimized first-order methods for smooth convex minimization
- Non-monotone Behavior of the Heavy Ball Method
- Accelerating nonnegative matrix factorization algorithms using extrapolation
- Search direction correction with normalized gradient makes first-order methods faster
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Convergence rates of inertial forward-backward algorithms
- A generic online acceleration scheme for optimization algorithms via relaxation and inertia
- A general distributed dual coordinate optimization framework for regularized loss minimization
- Linear coupling: an ultimate unification of gradient and mirror descent
- Proximal extrapolated gradient methods for variational inequalities
- Accelerated residual methods for the iterative solution of systems of equations
- Coherence retrieval using trace regularization
- Parameterized joint reconstruction of the initial pressure and sound speed distributions for photoacoustic computed tomography
This page was built for publication: Adaptive restart for accelerated gradient schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355332)
