SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

By Aaron Defazio, Francis R. Bach, Simon Lacoste-Julien. 2014

2,012 citations recorded by the source corpus.

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for composite objectives where a proximal operator is used on the regulariser. Unlike SDCA, SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem. We give experimental results showing the effectiveness of our method.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

On Mutual Information Maximization for Representation Learning (2019, methodology): “Despite the fact that MI is maximized by any instantiation of g1 and g2, IEST and downstream accuracy increase (3)Using SAGA (Defazio et al., 2014), as implemented in scikit-learn (Pedregosa et al.”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Some popular examples of variance reduced algorithms are SAG (Schmidt et al., 2017), SAGA (Defazio et al., 2014), SVRG (Johnson & Zhang, 2013) and SARAH (Nguyen et al., 2017).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “The overall objective is typically minimized using stochastic ﬁrst-order methods such as stochastic gradient descent (SGD) or its variance-reduced ver-∗ sions (Schmidt et al., 2017; Johnson and Zhang, 2013; Defazio et al., 2014).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Variance-reduction (VR) methods [18, 35, 72] are relatively new variants of SGD that improve its slow convergence rate.”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, background): “Nowadays, two main stochastic variance reduction algorithm considered in the literature are SAGA (Defazio et al., 2014) and SVRG (Johnson and Zhang, 2013).”
Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, neutral): “It would be interesting to combine our quantitative analysis with the constraints on the data distribution, which might give adaptive calibration functions (in analogy to adaptive convergence rates in convex optimization: for example, SAGA [9] has a linear convergence rate for strongly convex object”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “We note that Sdca requires the knowledge of an explicit µ-strongly convex regularizer in (1), whereas Sag / Saga are adaptive to any local strong convexity of f (Schmidt et al., 2016; Defazio et al., 2014).”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, background): “ algorithms, because their common point is to use memory to reduce the variance of the gradient as they get closer from the optimum. Johnson and Zhang [4] coined the name with SVRG and Defazio et al. [3] uniﬁed the family. SDCA is one member of this family that has not been applied yet to CRFs. Simi”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, methodology): “Adapting the Lyapunov function method from [4], we define upper bounds Hi ≥ ‖αi − f ′ i(w)‖(2) such that Hi → 0 as w → w∗.”
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, neutral): “1) 1 β O( β α) SAG [RSB12] 1 2n·β O( n·β α ) SVRG [JZ13] 1 10β O(n+ β α) SAGA [DBLJ14] 1 3β O(n+ β α) Katyusha [AZ16] (momentum) adaptive O(n+ √ n·β α ) Remarkably, in the interpolated regime, Theorem 1 implies that SGD obtains the benefits of variance reduction “for free" without the need for any m”
Optimization Methods for Large-Scale Machine Learning (2016, background): “14), referred to as SAGA [43], is given in Algorithm 5.”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “In optimization, they were used for ﬁnite-sum minimization by SVRG (Johnson and Zhang, 2013; Zhang et al., 2013) and then in SAGA (Defazio et al., 2014) to simplify the linearly convergent method SAG (Schmidt et al., 2017).”
Natural Compression for Distributed Deep Learning (2019, background): “, variants utilizing minibatching [14], importance sampling [20, 25], momentum [34], or variance reduction [24, 7]), is the cost of communication of the typically dense gradient vector gi(x), and in a parameter-sever implementation with a master node, also the cost of broadcasting the aggregated gra”
D2: Decentralized Training over Decentralized Data (2018, methodology): “with a similar convergence rate like C-PSGD. Variance blackuction technology There have been many methods developed for blackucing the variance in SGD, including SVRG [Johnson and Zhang, 2013], SAGA [Defazio et al., 2014], SAG [Schmidt et al., 2017], MISO [Mairal, 2015], and mS2GD [Konecnˇy et al., ”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “Another recent trend in the literature has been to use variance-reduction techniques [31, 14, 8] that exploit the finite-sum structure of the loss function in machine-learning applications.”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “While one could use any of recent fast algorithms for ﬁnite sums [17, 4, 19, 3] with comparable results, we highlight the consequences of applying the S VRG algorithm [6, 8] as a local solver in I NEXACT D ANE .”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The ﬁrst attempt to unify algorithms such as SVRG and SAG/SAGA already appeared in the SAGA paper [26], where the authors interpret SAGA as a midpoint between SAG and SVRG. Recent work [76] presents a general algorithm, which recovers SVRG, SAGA, SAG and GD as special cases, and obtains an…”