Restarting the accelerated coordinate descent method with a rough strong convexity estimate
From MaRDI portal
Publication:2301128
Abstract: We propose new restarting strategies for the accelerated coordinate descent method. Our main contribution is to show that for a well chosen sequence of restarting times, the restarted method has a nearly geometric rate of convergence. A major feature of the method is that it can take profit of the local quadratic error bound of the objective function without knowing the actual value of the error bound. We also show that under the more restrictive assumption that the objective function is strongly convex, any fixed restart period leads to a geometric rate of convergence. Finally, we illustrate the properties of the algorithm on a regularized logistic regression problem and on a Lasso problem.
Recommendations
- Adaptive restart for accelerated gradient schemes
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Accelerated, parallel, and proximal coordinate descent
- Adaptive restart of the optimized gradient method for convex optimization
- A simple nearly optimal restart scheme for speeding up first-order methods
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Accelerated, parallel, and proximal coordinate descent
- Adaptive restart for accelerated gradient schemes
- Adaptive restart of accelerated gradient methods under local quadratic growth condition
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Error bounds for solutions of linear equations and inequalities
- Error bounds, quadratic growth, and linear convergence of proximal methods
- From error bounds to the complexity of first-order descent methods for convex functions
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 6378119 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Katyusha: the first direct acceleration of stochastic gradient methods
- Linear convergence of first order methods for non-strongly convex optimization
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Parallel coordinate descent methods for big data optimization
- Pathwise coordinate optimization
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Stochastic intermediate gradient method for convex optimization problems
Cited in
(26)- Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions
- An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
- A piecewise conservative method for unconstrained convex optimization
- Restarting Frank-Wolfe: faster rates under Hölderian error bounds
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Generalized self-concordant functions: a recipe for Newton-type methods
- Adaptive restart for accelerated gradient schemes
- A simple nearly optimal restart scheme for speeding up first-order methods
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Sharpness, restart, and acceleration
- Adaptive restart of accelerated gradient methods under local quadratic growth condition
- A dual approach for optimal algorithms in distributed optimization over networks
- A generic coordinate descent solver for non-smooth convex optimisation
- Universal intermediate gradient method for convex problems with inexact oracle
- Scaled, inexact, and adaptive generalized FISTA for strongly convex optimization
- Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems
- Practical perspectives on symplectic accelerated optimization
- A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems
- Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
- First-order methods for convex optimization
- Coordinate descent methods beyond smoothness and separability
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- A guide to stochastic optimisation for large-scale inverse problems
- An adaptive parameter-free and projection-free restarting level set method for constrained convex optimization under the error bound condition
This page was built for publication: Restarting the accelerated coordinate descent method with a rough strong convexity estimate
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301128)
