Catalyst acceleration for first-order convex optimization: from theory to practice
From MaRDI portal
Abstract: We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact accelerated proximal point algorithm for minimizing a convex objective function, and consists of approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. One of the keys to achieve acceleration in theory and in practice is to solve these sub-problems with appropriate accuracy by using the right stopping criterion and the right warm-start strategy. We give practical guidelines to use Catalyst and present a comprehensive analysis of its global complexity. We show that Catalyst applies to a large class of algorithms, including gradient descent, block coordinate descent, incremental algorithms such as SAG, SAGA, SDCA, SVRG, MISO/Finito, and their proximal variants. For all of these methods, we establish faster rates using the Catalyst acceleration, for strongly convex and non-strongly convex objectives. We conclude with extensive experiments showing that acceleration is useful in practice, especially for ill-conditioned problems.
Recommendations
- Adaptive Catalyst for Smooth Convex Optimization
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Adaptive restart of the optimized gradient method for convex optimization
- Convergence rates of accelerated proximal gradient algorithms under independent noise
- Katyusha: the first direct acceleration of stochastic gradient methods
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A proximal stochastic gradient method with progressive variance reduction
- A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
- A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS*
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- An accelerated inexact proximal point algorithm for convex minimization
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- An optimal randomized incremental gradient method
- Convergence of some algorithms for convex minimization
- Convex optimization algorithms
- Descentwise inexact proximal algorithms for smooth optimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- First-order methods of smooth convex optimization with inexact oracle
- Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3678487 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3341597 (Why is no real title available?)
- scientific article; zbMATH DE number 3192366 (Why is no real title available?)
- Incremental majorization-minimization optimization with application to large-scale machine learning
- Inexact and accelerated proximal point algorithms
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Katyusha: the first direct acceleration of stochastic gradient methods
- Minimizing finite sums with the stochastic average gradient
- Monotone Operators and the Proximal Point Algorithm
- New Proximal Point Algorithms for Convex Minimization
- Numerical methods for nondifferentiable convex optimization
- On lower and upper bounds in smooth and strongly convex optimization
- On the Convergence of the Proximal Point Algorithm for Convex Minimization
- Optimization with sparsity-inducing penalties
- Practical Aspects of the Moreau--Yosida Regularization: Theoretical Preliminaries
- Regularization and Variable Selection Via the Elastic Net
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- Vector extrapolation methods with applications
Cited in
(53)- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- An optimal randomized incremental gradient method
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Understanding the acceleration phenomenon via high-resolution differential equations
- Accelerated proximal envelopes: application to componentwise methods
- On the computational efficiency of catalyst accelerated coordinate descent
- Accelerating variance-reduced stochastic gradient methods
- Oracle complexity separation in convex optimization
- Accelerating incremental gradient optimization with curvature information
- Inexact first-order primal-dual algorithms
- Accelerated methods for saddle-point problem
- Accelerated proximal point method for maximally monotone operators
- Fast gradient descent for convex minimization problems with an oracle producing a ( , L)-model of function at the requested point
- Provable accelerated gradient method for nonconvex low rank optimization
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Inexact successive quadratic approximation for regularized optimization
- An accelerated variance reducing stochastic method with Douglas-Rachford splitting
- Accelerated meta-algorithm for convex optimization problems
- One-step optimization method for equilibrium problems
- Revisiting EXTRA for Smooth Distributed Optimization
- Katyusha: the first direct acceleration of stochastic gradient methods
- A generic online acceleration scheme for optimization algorithms via relaxation and inertia
- The approximate duality gap technique: a unified theory of first-order methods
- Utilizing second order information in minibatch stochastic variance reduced proximal iterations
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
- Distributed Learning with Sparse Communications by Identification
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Katyusha: the first direct acceleration of stochastic gradient methods
- Accelerated extra-gradient descent: a novel accelerated first-order method
- Robustness of Accelerated First-Order Algorithms for Strongly Convex Optimization Problems
- A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes
- Convergence of Recursive Stochastic Algorithms Using Wasserstein Divergence
- scientific article; zbMATH DE number 7625177 (Why is no real title available?)
- Fast convergence of generalized forward-backward algorithms for structured monotone inclusions
- Bregman proximal point algorithm revisited: a new inexact version and its inertial variant
- Contracting proximal methods for smooth convex optimization
- Estimate sequences for stochastic composite optimization: variance reduction, acceleration, and robustness to noise
- On convergence of distributed approximate Newton methods: globalization, sharper bounds and beyond
- Black-box reductions for zeroth-order gradient algorithms to achieve lower query complexity
- scientific article; zbMATH DE number 7164767 (Why is no real title available?)
- An inexact variable metric proximal point algorithm for generic quasi-Newton acceleration
- Generalized momentum-based methods: a Hamiltonian perspective
- Accelerated variance-reduced methods for saddle-point problems
- Principled analyses and design of first-order methods with inexact proximal operators
- Adaptive proximal SGD based on new estimating sequences for sparser ERM
- Adaptive Catalyst for Smooth Convex Optimization
- A proximal-gradient method for problems with overlapping group-sparse regularization: support identification complexity
- On the fast convergence of minibatch heavy ball momentum
- Accelerated algorithms for convex and non-convex optimization on manifolds
- New penalized stochastic gradient methods for linearly constrained strongly convex optimization
- An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems
- Accelerated proximal algorithms with a correction term for monotone inclusions
This page was built for publication: Catalyst acceleration for first-order convex optimization: from theory to practice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558545)
