A Universal Catalyst for First-Order Optimization

By Hongzhou Lin, Julien Mairal, Zaïd Harchaoui. 2015

406 citations recorded by the source corpus.

We introduce a generic scheme for accelerating first-order optimization methods in the sense of Nesterov, which builds upon a new analysis of the accelerated proximal point algorithm. Our approach consists of minimizing a convex objective by approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. This strategy applies to a large class of algorithms, including gradient descent, block coordinate descent, SAG, SAGA, SDCA, SVRG, Finito/MISO, and their proximal variants. For all of these methods, we provide acceleration and explicit support for non-strongly convex objectives. In addition to theoretical speed-up, we also show that acceleration is useful in practice, especially for ill-conditioned problems where we measure significant improvements.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “Related work in this context includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting [1, 23, 46].”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “We also note that acceleration schemes have been proposed for both SAG and SDCA (Lin et al., 2015; ShalevShwartz and Zhang, 2016), though they have not been tested yet for training CRFs.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “Acceleration ideas have been applied in a variety of other contexts as well, including for the minimization of nonsmooth convex functions; see [94].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Other related work includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting [1, 19, 10].”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “2 of [10], the total number of INEXACTDANE iterations required to achieve an -accurate solution is”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “A general method, referred to as Universal Catalyst [53, 37], eﬀectively enables conversion of a number of the algorithms mentioned in the previous sections to their ‘ac-celerated’ variants.”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “Finally, the recently proposed generic scheme for accelerating first-order optimization methods in the sense of Nesterov from [24] applies directly to the FW variants given their global linear convergence rate that we proved.”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, methodology): “Accelerating these methods using the Catalyst framework [10] ensures that for -strongly convex objectives we have E ⇥ F (x(k)) F (x⇤) < ✏ after k = O m+m log 2 ✏0”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, background): “, 2014a], SVRG-like [Johnson and Zhang, 2013], Dual [Shalev-Shwartz and Zhang, 2013], Catalyst [Lin et al., 2015] or SARAH-like [Nguyen et al.”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, positive): “We show in Section 5 that these incremental algorithms can be easily accelerated using a simple extension of the “catalyst” framework of [7], thus leading to an algorithm which is always superior to accelerated batch algorithms.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “• Catalyst [21] on top of SVRG.”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, background): “On top of that, AIDE uses the idea of universal catalyst (Lin et al., 2015) and adds an extra quadratic term to improve the strong-convexity of the objective for faster convergence, i.e., in order to solve (15), AIDE solves multiple instances of the “augmented large minibatch” problems of the…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A general method, referred to as Universal Catalyst [99, 63], effectively enables conversion of a number of the algorithms mentioned in the previous sections to their ‘accelerated’ variants.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, background): “algorithms whose running time is favorable in n and d, but scale at best in √ κ [15, 22, 14, 4].”
Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity (2015, methodology): “The crucial observation here is that, although in the single-machine setting, the acceleration scheme of [8, 14] only helps when κ ≥ N , in the distributed setting, it helps to reduce the rounds as long as κ is larger than the number of local samples n.”
Distributed block-diagonal approximation methods for regularized empirical risk minimization (2017, methodology): “Their techniques derived from Shalev-Shwartz and Zhang (2016) is similar to the Catalyst framework for convex optimization (Lin et al. 2015).”
Accelerated Methods for Non-Convex Optimization (2016, background): “The estimate sequence ideas of Nesterov [23] and proximal point proofs [20, 31, 9] show how to view accelerated gradient descent as a trade-off between building function lower”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “…another crucial insight we obtain here is that, although in the singlemachine setting, the acceleration scheme of Frostig et al. (2015) and (Lin et al., 2015) only helps to reduce the time complexity when κ ≥ N by choosing σ = Θ(N), in the distributed setting, it helps to reduce the rounds…”