A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

By Nicolas Le Roux, Mark W. Schmidt, Francis R. Bach. 2012

878 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, methodology): “In brief, they consisted of: • A logistic regression objective, chosen to be the same as one used in (Roux et al., 2012).”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “[10] Nicolas Le Roux, Mark Schmidt, and Francis Bach.”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, background): “(2015) describes a practical implementation of the stochastic average gradient (SAG) algorithm (Roux et al., 2012) for CRFs and proposes a non-uniform sampling scheme that boosts performance.”
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, methodology): “For general convex optimization, a set of important stochastic methods [RSB12, JZ13, DBLJ14, XZ14, AZ16] have been proposed to achieve exponential (linear) convergence rate with constant step size.”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “construct rf i(w k) at a later iteration. Such a functional form of f i occurs in logistic and least squares regression. Algorithm5.2has its origins in the stochastic average gradient (SAG) algorithm [139,90], where the stochastic direction is dened as g k 1 n rf j(w k) r f j(w [j ]) + Xn i=1 rf i(w”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “Another class of algorithms includes stochastic variation reduction techniques that include SVRG [Johnson and Zhang, 2013], SAGA [Roux et al., 2012] and their variants listed out in [Nguyen et al., 2017].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “The SAG algorithm stores an average of n gradients of functions f i evalueated at diﬀerent points in the history of the algorithm.”
New Insights and Perspectives on the Natural Gradient Method (2014, methodology): “And second, as we establish in Section 8, it is very often equivalent to the so-called Generalized Gauss-Newton matrix (GGN) (Schraudolph, 2002; Martens and Sutskever, 2012) discussed in Section 7, which is an established and well justified approximation of the Hessian that has been used in practica”
Practical Recommendations for Gradient-Based Training of Deep Architectures (2012, background): “More recently, several mathematically motivated algorithms (Nesterov, 2009; Le Roux et al. , 2012) have been proposed that incorporate some form of momentum and that also ensure much faster convergence (linear rather than sublinear) compared to stochastic gradient descent, at least for convex…”
Understanding intermediate layers using linear classifier probes (2016, methodology): “We have not yet tried those methods, but we are looking at trying the Stochastic Average Gradient, and Stochastic Variance-Reduced Gradient methods (Roux et al., 2012; Schmidt et al., 2013; Harikandeh et al., 2015).”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “An interesting question for further consideration is to what extent importance sampling can also help with stochastic optimization procedures such as SAG [8] and SDCA [17] which achieve faster convergence on finite data sets.”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “…Corollary 2 implies This result means that if we take m = O ( L Q /ǫ ) and s ≥ log(1 /ǫ ) / log(1 /ρ ), then The overall complexity (in terms of the number of component gradient evaluations) is (cid:0) (cid:1) Similar results for the case of R ( x ) ≡ 0 have been obtained in [RSB12, MZJ13, KR13].”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “We analyze the convergence rates of the proposed algorithms with respect to the number of iterations”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “3Note that a similar assumption appears in the first analysis of SAG published in [36] before its refinement in [50].”
ASAGA: Asynchronous Parallel SAGA (2016, background): “A flurry of randomized incremental algorithms have recently been proposed to solve (1) with a fast linear convergence rate, such as SAG [7], SDCA [16], SVRG [6] and SAGA [2].”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “Quantization and Variance Reduction Variance reduced methods (Roux et al., 2012; Johnson & Zhang, 2013; Shalev-Shwartz & Zhang, 2013; Defazio et al., 2014; Qu et al., 2015; Shalev-Shwartz, 2016; Qu et al., 2016; Csiba & Richtárik, 2015; Csiba et al., 2015; Nguyen et al., 2017; Gower et al., 2018; Zh”