Finito: A faster, permutable incremental gradient method for big data problems

By Aaron Defazio, Justin Domke, Tibério S. Caetano. 2014

172 citations recorded by the source corpus.

Recent advances in optimization theory have shown that smooth strongly convex finite sums can be minimized faster than by treating them as a black box "batch" problem. In this work we introduce a new method in this class with a theoretical convergence rate four times faster than existing methods, for sums with sufficiently many terms. This method is also amendable to a sampling without replacement scheme that in practice gives further speed-ups. We give empirical results showing state of the art performance.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, 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 Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “SAGA can be seen to perform similar to the non-permuted Finito case, and to SDCA.”
Distributed optimization with arbitrary local solvers (2015, background): “Algorithms such as SAG [54], SAGA [16] and others [17, 55] come at the cost of extra memory requirements — they have to store a gradient for each training example.”
Stochastic Variance Reduction for Nonconvex Optimization (2016, methodology): “The Svrg algorithm of (Johnson & Zhang, 2013) is particularly attractive here because of its low storage requirement in comparison to the algorithms in (Schmidt et al., 2013; Defazio et al., 2014a).”
A Universal Catalyst for First-Order Optimization (2015, methodology): “More importantly, it also applies to incremental algorithms such as SA G [24], SAGA [6], Finito/MISO [7, 14], SDCA [25], and SVRG [27].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “t proposition, the method achieves a fast convergence rate when T ≥2L/µ, but may diverge if T is small. Note that at the same time as us, a similar result was independently obtained by Defazio et al. [18], where a reﬁned analysis provides a slightly better rate, namely the constant 1/3 in (3.9) may ”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, methodology): “Also closely related are dual methods such as SDCA [26] and Finito [6], and in its convex incarnation MISO [15]; a more precise relation between these dual methods and VR stochastic methods is described in Defazio’s thesis [4].”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, methodology): “…upon the non-streaming variance reduction framework have been developed, they can generally be characterized into one of several classes: SAGA-like [Defazio et al., 2014a], SVRG-like [Johnson and Zhang, 2013], Dual [Shalev-Shwartz and Zhang, 2013], Catalyst [Lin et al., 2015] or SARAH-like [Nguyen…”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, neutral): “aster than that of r f (x ), SGD is suitable for large-scale machine learning tasks. Variance Reduction. Recently, the convergence speed of SGD has been improved with the variance-reduction technique [8, 10, 11, 15, 22, 23, 28{30, 32, 33]. In all of these cited results, the authors have, in one way ”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Algorithms such as SAG [158], SAGA [45] and others [159, 46] come at the cost of extra memory requirements—they have to store a gradient for each training example.”
A Simple Practical Accelerated Method for Finite Sums (2016, methodology): “This is sometimes called the big data setting [Defazio et al., 2014b].”
Variance Reduction for Faster Non-Convex Optimization (2016, methodology): “…global minimum) for problem (1.1) has received lots of attentions across machine learning and optimization communities; many ﬁrst-order methods [6, 7, 15, 19, 22, 25, 27] as well as their Algorithm 1 The simpliﬁed SVRG method in the non-convex setting Input: x φ a starting vector, S number of…”
Automated Inference with Adaptive Batches (2017, methodology): “…enjoy a provably faster convergence rate than SGD and have been shown to outperform SGD on convex problems (Defazio et al., 2014a; Johnson and Zhang, 2013; Schmidt et al., 2013; Defazio et al., 2014b), as well as in parallel (Reddi et al., 2015) and distributed settings (De and Goldstein, 2016).”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “The stochastic gradient method and its variance-reduced variants (e.g., SAG (Roux et al., 2012), SAGA (Defazio et al., 2014a), SVRG (Johnson and Zhang, 2013), and SARAH (Nguyen et al., 2017)) for solving (P) under strong convexity and smoothness structures usually have theoretically linear convergen”
A Generic Approach for Escaping Saddle points (2017, background): “[7] Aaron J Defazio, Tibério S Caetano, and Justin Domke.”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “…et al., 2017), stochastic average gradient algorithms (Roux et al., 2012; Defazio et al., 2014a), stochastic majorization-minimization algorithms (Defazio et al., 2014b; Mairal, 2013), hybrid methods (Konecn`y and Richt´arik, 2013), and dual coordinate methods (Shalev-Shwartz and Zhang, 2013,…”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, methodology): “…design of variance-reduced (VR) stochastic gradient methods, such as SAG [33], SDCA [34, 32], SVRG [11], S2GD [13], SAGA [7], MISO [17] and FINITO [8] and SARAH [22], which operate by modifying the classical stochastic gradient direction in each step of the training SVRG max n, (1+ 4 / 3 ) L max…”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “While a comparison to SAGA seems natural as it also does not have a double loop structure, we position our loopless methods for applications where the high memory requirements of SAGA prevent it to be applied.”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “The first variance reduced method for empirical risk minimization is the stochastic average gradient (SAG) method of Schmidt, Le Roux and Bach [29], closely followed by Finito [7] andMiso [18].”