A Simple Practical Accelerated Method for Finite Sums

By Aaron Defazio. 2016

124 citations recorded by the source corpus.

We describe a novel optimization method for finite sums (such as empirical risk minimization problems) building on the recently introduced SAGA method. Our method achieves an accelerated convergence rate on strongly convex smooth problems. Our method has only one parameter (a step size), and is radically simpler than other accelerated methods for finite sums. Additionally it can be applied when the terms are non-smooth, yielding a method applicable in many areas where operator splitting methods would traditionally be applied.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis, 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 Numerical Analysis

In Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “For more examples of variance reduced methods in different settings, see Defazio (2016); Kone ˇ cn ´ y et al. (2016); Gower et al. (2018); Sebbouh et al. (2019).”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “While one could use any of recent fast algorithms for finite sums [17, 4, 19, 3] with comparable results, we highlight the consequences of applying the SVRG algorithm [6, 8] as a local solver in INEXACTDANE.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “A followup algorithm SAGA [26] and its simplification [25], modifies the SAG algorithm to achieve unbiased estimate of the gradients.”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “To overcome this problem, a new class of so-called variance-reduced methods was developed over the last 2–5years, including SAG [80], SDCA [76,82], SVRG/S2GD [37,40], minibatch SVRG/S2GD [39], and SAGA [13,14].”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “In such gradient operator setting, when the is only a single node, DSBA degenerates to the Point-SAGA method (Defazio, 2016).”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, methodology): “Unbiasedness is not necessary for the fast rates obtainable by SVR methods, both SAG [Schmidt et al., 2017] and Point-SAGA [Defazio, 2016] use biased steps, however biased methods are harder to analyze.”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “For finite-sum objectives, methods based on incremental/stochastic proximal updates were studied in Bertsekas (2011); Defazio (2016).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A followup algorithm SAGA [45] and its simplification [44], modifies the SAG algorithm to achieve unbiased estimate of the gradients.”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, background): “…and Zhang, 2013; Defazio et al., 2014) and their accelerated variants (Shalev-Shwartz and Zhang, 2013a; Frostig et al., 2015a; Lin et al., 2015; Defazio, 2016; Allen-Zhu, 2016) which offer near linear running time in the number of samples and condition number with log( n ) passes over the…”
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].”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, methodology): “[8] Aaron Defazio.”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, methodology): “10Essentially any accelerated variance reduced algorithm can be used instead of Katyusha, for example ASDCA [46], APCG [29], Point-SAGA [9], MiG [56], SAGA-SSNM [55] and others.”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “Accelerated variance-reduced method were developed in [26], [5], [28] and [29].”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, background): “, n as follows: g j = ∇fik(x) if ik=j, and g j =g k−1 j otherwise (see [9, 27] for details).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “To overcome this problem, a new class of so-called variance-reduced methods was developed over the last 8 years, including SAG [173], SDCA [178, 166], SVRG/S2GD [89, 97], minibatch SVRG/S2GD [96], and SAGA [34, 33].”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “One may also use the Catalyst framework [24, 34] and proximal point iteration [10, 28] to further accelerate when the problem is ill-conditioned.”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, background): “These stochastic gradients can be classified in two classes: variance reduced (VR) stochastic gradients [19, 20, 23, 29] and generic stochastic gradients, see e.”
On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization (2018, methodology): “These methods have been improved using accelerated variants (Shalev-Shwartz & Zhang, 2014; Frostig et al., 2015a; Lin et al., 2015; Defazio, 2016; Allen-Zhu, 2016).”
99% of Parallel Optimization is Inevitably a Waste of Time (2019, methodology): “One can also try to extend our analysis to methods with exact block-coordinate minimization or primal-dual and proximal methods such as Point-SAGA (Defazio, 2016), PDHG (Chambolle & Pock, 2011), DANE (Shamir et al., 2014), etc.”
Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice (2017, unknown): “, 2015b), SDPC (Zhang and Xiao, 2015), RPDG (Lan and Zhou, 2017), Point-SAGA (Defazio, 2016) and Katyusha (Allen-Zhu, 2017).”