Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning

By Francis R. Bach, Eric Moulines. 2011

875 citations recorded by the source corpus.

Subfields: Optimization & Training, Scaling & Learning Theory

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

In Scaling & Learning Theory

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, background): “Recent work has explored the non-asymptotic convergence properties of stochastic optimization algorithms (Bach & Moulines, 2011).”
No more pesky learning rates (2012, background): “Originally proposed as η ( t ) = O ( t − 1 ) in (Robbins & Monro, 1951), this form was recently analyzed in (Xu, 2011; Bach & Moulines, 2011) from a non-asymptotic perspective to understand how hyper-parameters like η 0 and γ aﬀect the convergence speed.”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “[14], Moulines and Bach [35], Needell and Ward [36], Needell et al.”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “asynchronous parallel constant step size Sgd) first introduced in Niu et al. (2011). We start by describing Hogwild in Algorithm 5, and then give our theoretical convergence and speedup results and their proofs.”
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, background): “For the general convex case, it was first proved in [MB11].”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “With a suitable choice of step-sizes, this gives the same asymptotic efficiency as Newton-like secondorder SGmethods and also leads to increased robustness of the convergence rate to the exact sequence of step sizes [2,47].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “In contrast to the centralized setting, where the convergence of SGD is well understood (Bach & Moulines, 2011; Rakhlin et al., 2012; Dekel et al., 2012), the analyses of SGD in non-centralized settings are often application speciﬁc and have been historically developed separately in different…”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “We mainly focus on proving convergence results on the Mahalanobis distance ‖F ′′(w?)(w −w?)‖2, which is the natural quantity in such a setting (Bach and Moulines, 2011; Bach and Moulines, 2013; Godichon and Saadane, 2017).”
Local SGD Converges Fast and Communicates Little (2018, background): “Convergence proofs for SGD [20] typically rely on averaging of the iterates [14, 18, 21], tough also convergence of the last iterate can be proven [25].”
D2: Decentralized Training over Decentralized Data (2018, background): “The SGD approahces [Ghadimi and Lan, 2013, Moulines and Bach, 2011, Nemirovski et al., 2009] is quite powerful for solving large-scale machine learning problems.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “Note that if T = 0 and n = 1 the proposed AD-PSGD reduces to the vanilla SGD algorithm (Nemirovski et al., 2009; Moulines and Bach, 2011; Ghadimi and Lan, 2013).”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, background): “ is a powerful approach for solving large scale machine learning. The well known convergence rate of stochastic gradient is O (1/ p K ) for convex problems and O (1/ K ) for strongly convex problems [Moulines and Bach, 2011, Nemirovski et al., 2009]. SGD is closely related to online learning algorit”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, background): “r large scale optimization. The well known convergence rate of stochastic gradient is O(1= p K) for convex problems and O(1=K) for strongly convex problems, for example, see [Nemirovski et al., 2009, Moulines and Bach, 2011]. A parallel algorithm to stochastic gradient is the dual averaging approach”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “For a theoretical analysis for convex functions we refer the reader to [66, 64, 65] and [87, 93] for SVM problems.”
DeltaGrad: Rapid retraining of machine learning models (2020, neutral): “See e.g., (Gladyshev, 1965; Amari, 1967; Kul’chitskiy & Mozgovoy, 1992; Bert-sekas & Tsitsiklis, 1996; Moulines & Bach, 2011; Karimi et al., 2016; Bottou et al., 2018; Gorbunov et al., 2019; Gower et al., 2019), etc, and references therein.”
Sparsified SGD with Memory (2018, background): “Convergence proofs for SGD [29] typically rely on averaging the iterates [23, 27, 30], though convergence of the last iterate can also be proven [34].”
Communication Compression for Decentralized Training (2018, methodology): “Stochastic gradient descent The Stocahstic Gradient Descent ( SGD ) [Ghadimi and Lan, 2013, Moulines and Bach, 2011, Nemirovski et al., 2009] - a stochastic variant of the gradient descent method - has been widely used for solving large scale machine learning problems [Bottou, 2010].”