SGD and Hogwild! Convergence Without the Bounded Gradients Assumption

By Lam M. Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, Martin Takác. 2018

251 citations recorded by the source corpus.

Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime, which results in more relaxed conditions than those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate.

Subfields: Computational Theory and Mathematics, Economics and Econometrics, Finance, 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 Computational Theory and Mathematics

In Economics and Econometrics

In Finance

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…2017]. of shows (cid:107) (cid:107) However, a recent line work that these assumptions might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et…”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “However, this assumption often does not hold, such as in the case when f is strongly convex (Nguyen et al., 2018).”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “However, in the unconstrained setting, this assumption contradicts the assumption of strong convexity (Nguyen et al., 2018; Gower et al., 2019).”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, background): “of the uniform boundedness of the gradient allowing arbitrarily different gradients of local functions in heterogenous settings as done for SGD in [25], [44] is”
SGD: General Analysis and Improved Rates (2019, methodology): “…to prove the convergence of SGD is uniform boundedness of the stochastic gradients 3 : there exist 0 < c < ∞ such that E (cid:107)∇ f v ( x ) 2 ≤ c for all x . does However, this assumption often not hold, such as in the case when f is strongly convex (Bottou et al., 2018; Nguyen et al., 2018).”
On the Acceleration of L-BFGS with Second-Order Information and Stochastic Batches (2018, unknown): “Because of λ -strong convexity, F satisﬁes: In addition, we should remark here that Assumption 2 is different to the standard assumption in [3] in the sense that we do not require a bounded stochastic gradient assumption since such assumption is barely correct in both theory and practice [25].”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, methodology): “For instance, our analysis covers as special cases vanilla SGD methods from (Nguyen et al., 2018) and (Gower et al.”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, background): “…gradient as sup i ∈ [ n ] (cid:107)∇ f ( w ; i ) (cid:107) ≤ G for ∀ w ∈ dom ( F ) (the domain of F ), then it is easy to show that µ 2 w − w 2 ≤ F ( w ) − F ( w (cid:63) ) ≤ µ (cid:107)∇ F ( w ) 2 ≤ G 2 2 µ for all w ∈ dom ( F ), where w (cid:63) is the unique minimizer of F (Nguyen et al., 2018).”
The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory (2018, background): “Concurrent work [17, 22] provides significantly more general analyses of iterative processes under asynchrony, covering several important optimization algorithms.”
Unified Optimal Analysis of the (Stochastic) Gradient Method (2019, unknown): “(Schmidt and Roux, 2013; Bertsekas and Tsitsiklis, 1996; Bottou et al., 2018; Nguyen et al., 2018).”
Communication-efficient federated learning (2021, unknown): “While assumptions 1 through 3 may not accurately reflect practical FL systems, particularly when training deep models, and can even be in conflict (28), they are often employed in distributed learning studies (24, 25).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, background): “However, for large classes of convex functions, it has been shown that these assumptions do not to hold [20, 31].”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, methodology): “Unfortunately, requiring each f i to be Lipschitz contradicts strong convexity (Nguyen et al., 2018) and is furthermore not satisﬁed in least square regression, matrix factorization, or for neural networks with smooth activations.”
Decentralized Federated Averaging (2021, methodology): “A particular idea is leveraging unbounded gradient convergence analysis [57], [58], and the core technique is using the inequality for functions with the Lipschitz gradient established in [59].”
Distributed learning with compressed gradients (2018, background): “Even though this assumption is valid for a certain classes of optimization problems, it is always violated when the objective function is strongly convex [15].”
New Convergence Aspects of Stochastic Gradient Algorithms (2018, background): “Asynchronous Stochastic Optimization aka Hogwild! Hogwild! Recht et al. (2011) is an asynchronous stochastic optimization method where writes to and reads from vector positions in shared memory can be inconsistent (this corresponds to (13) as we shall see).”
SGD without Replacement: Sharper Rates for General Smooth Convex Functions (2019, background): “SGD has been extensively studied in literature and a vast number of results are known in many different settings, most prominent being that of convex optimization (Benaı̈m, 1999; Borkar, 2009; Kushner & Yin, 2003; Bubeck, 2015; Bottou et al., 2018; Schmidt & Roux, 2013; Gower et al., 2019; Nguyen et”