Adaptive restart for accelerated gradient schemes

DOI10.1007/s10208-013-9150-3zbMath1320.90061arXiv1204.3982OpenAlexW2127447444MaRDI QIDQ2355332

Emmanuel J. Candès, Brendan O'Donoghue

Publication date: 22 July 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

convex optimization first order methods accelerated gradient schemes

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06)

Related Items

Variational phase recovering without phase unwrapping in phase-shifting interferometry, On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent, Improving “Fast Iterative Shrinkage-Thresholding Algorithm”: Faster, Smarter, and Greedier, Parallel Nesterov Domain Decomposition Method for Elliptic Partial Differential Equations, An Iterative Reduction FISTA Algorithm for Large-Scale LASSO, An off-the-grid approach to multi-compartment magnetic resonance fingerprinting, Scheduled Restart Momentum for Accelerated Stochastic Gradient Descent, Active Neuron Least Squares: A Training Method for Multivariate Rectified Neural Networks, A Unifying Framework and Comparison of Algorithms for Non‐negative Matrix Factorisation, M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions, A speed restart scheme for a dynamics with Hessian-driven damping, A truncated three-term conjugate gradient method with complexity guarantees with applications to nonconvex regression problem, Practical perspectives on symplectic accelerated optimization, Robust obstacle reconstruction in an elastic medium, Spectral deferred correction method for Landau-Brazovskii model with convex splitting technique, Smooth over-parameterized solvers for non-smooth structured optimization, Fast gradient method for low-rank matrix estimation, FISTA is an automatic geometrically optimized algorithm for strongly convex functions, Unnamed Item, Convergence rate analysis of an extrapolated proximal difference-of-convex algorithm, A modified forward‐backward splitting methods for the sum of two monotone operators with applications to breast cancer prediction, A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems, Faster first-order primal-dual methods for linear programming using restarts and sharpness, The regularized stochastic Nesterov's accelerated quasi-Newton method with applications, A variable metric and Nesterov extrapolated proximal DCA with backtracking for a composite DC program, Proximal gradient method with extrapolation and line search for a class of non-convex and non-smooth problems, The Distributionally Robust Chance-Constrained Vehicle Routing Problem, Joint reconstruction of initial pressure distribution and spatial distribution of acoustic properties of elastic media with application to transcranial photoacoustic tomography, A projected gradient method for αℓ ₁ − βℓ ₂ sparsity regularization ^**, Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing, Accelerated Optimization in the PDE Framework Formulations for the Active Contour Case, Unnamed Item, Efficient Numerical Methods for Computing the Stationary States of Phase Field Crystal Models, On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES, An introduction to continuous optimization for imaging, Coherence Retrieval Using Trace Regularization, Parameterized Joint Reconstruction of the Initial Pressure and Sound Speed Distributions for Photoacoustic Computed Tomography, A deterministic rescaled perceptron algorithm, Algorithm 996, Sharpness, Restart, and Acceleration, A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions, A Single-Phase, Proximal Path-Following Framework, Accelerated First-Order Primal-Dual Proximal Methods for Linearly Constrained Composite Convex Programming, Backtracking Strategies for Accelerated Descent Methods with Smooth Composite Objectives, On Quasi-Newton Forward-Backward Splitting: Proximal Calculus and Convergence, Nonmonotone Enhanced Proximal DC Algorithms for a Class of Structured Nonsmooth DC Programming, Nonbifurcating Phylogenetic Tree Inference via the Adaptive LASSO, Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions, A dual approach for optimal algorithms in distributed optimization over networks, An Adaptive Gradient Method with Energy and Momentum, Scaled, Inexact, and Adaptive Generalized FISTA for Strongly Convex Optimization, A fast first-order optimization approach to elastoplastic analysis of skeletal structures, Additive Schwarz methods for convex optimization with backtracking, Projected shrinkage algorithm for box-constrained \(\ell _1\)-minimization, A secant-based Nesterov method for convex functions, 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, Conic optimization via operator splitting and homogeneous self-dual embedding, Accelerated proximal gradient method for bi-modulus static elasticity, Optimized first-order methods for smooth convex minimization, New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure, A parallel Tseng's splitting method for solving common variational inclusion applied to signal recovery problems, Adaptive restart of the optimized gradient method for convex optimization, Fast proximal algorithms for nonsmooth convex optimization, Robust hybrid zero-order optimization algorithms with acceleration via averaging in time, Combining fast inertial dynamics for convex optimization with Tikhonov regularization, 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, 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, Linear convergence of first order methods for non-strongly convex optimization, Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints, 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, Iteratively reweighted \(\ell _1\) algorithms with extrapolation, Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems, 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, Convergence rates of the heavy-ball method under the Łojasiewicz property, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, Activity Identification and Local Linear Convergence of Forward--Backward-type Methods, Acceleration of the PDHGM on partially strongly convex functions, 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, Convergence Rates of Inertial Forward-Backward Algorithms, How to choose biomarkers in view of parameter estimation, Optimization for deep learning: an overview, A generic online acceleration scheme for optimization algorithms via relaxation and inertia, An adaptive primal-dual framework for nonsmooth convex minimization, Convergence of first-order methods via the convex conjugate, Non-monotone Behavior of the Heavy Ball Method, An accelerated Uzawa method for application to frictionless contact problem, 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 point method for maximally monotone operators, Proximal extrapolated gradient methods for variational inequalities, 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, Parallel Nesterov's method for large-scale minimization of partially separable functions, 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, Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis, 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, Accelerated Residual Methods for the Iterative Solution of Systems of Equations, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity, 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, Proximal algorithms in statistics and machine learning, 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, Accelerating Nonnegative Matrix Factorization Algorithms Using Extrapolation, Restarting the accelerated coordinate descent method with a rough strong convexity estimate, Search Direction Correction with Normalized Gradient Makes First-Order Methods Faster, 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, 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, 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 General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization, A strongly convergent algorithm for solving common variational inclusion with application to image recovery problems, Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent, 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, Generalized self-concordant functions: a recipe for Newton-type methods, 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, An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization, Adaptive Euclidean maps for histograms: generalized Aitchison embeddings, 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

Uses Software

Cites Work