Source-linked AI summary
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
Lam M. Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, Martin Takáč
TL;DR
The paper addresses SGD convergence when uniformly bounded stochastic gradients conflict with strong convexity. It derives convergence results under Lipschitz continuity of individual realizations and diminishing step sizes, extending the analysis to Hogwild! with inconsistent reads and writes.
Problem
Classical SGD analyses assume uniformly bounded stochastic gradients, an assumption that contradicts strong convexity for sufficiently large distances from the optimum.
Method
The paper analyzes SGD with diminishing step sizes assuming strongly convex objectives and Lipschitz-continuous individual function realizations, then extends the framework to nonconvex realizations and asynchronous Hogwild!.
Results
The analysis derives a stochastic-gradient bound with specific constants under individual smoothness, proves almost sure SGD convergence, and gives sublinear expected-rate bounds covering Hogwild! with inconsistent reads and writes.
Takeaways & Limitations
The results provide convergence analysis for diminishing-learning-rate SGD and Hogwild! without requiring bounded stochastic gradients.
Takeaways & Limitations
The analysis assumes that the objective function F is strongly convex, with a unique optimal solution.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper replaces the bounded-stochastic-gradient assumption with conditions suited to strongly convex machine-learning objectives, then analyzes diminishing-step-size SGD and Hogwild!. It establishes convergence results under Lipschitz continuity of individual realizations, including extensions to non-convex component functions and inconsistent asynchronous updates.
- Motivation: For expected-risk problems, individual realizations have convex, Lipschitz-continuous gradients, enabling bounds on stochastic gradients without uniform boundedness.The resulting bound has the form E[∥∇f(w; ξ)∥2] ≤ M0[F(w) − F(w∗)] + N, and strong convexity yields a gradient-norm bound.
- Motivation: Uniformly bounded stochastic gradients contradict strong convexity for sufficiently large distances from the optimum.The paper motivates an alternative assumption because strong convexity implies gradient growth that cannot remain uniformly bounded.
- SGD contributions: The analysis proves almost-sure convergence of diminishing-step-size SGD and permits a larger initial-step-size bound than prior convergence-in-expectation analyses.The paper states that the allowable initial step size is larger than in Bottou et al. (2016) and Moulines and Bach (2011).
- Asynchronous optimization: The framework introduces a general vector-update recurrence covering diminishing-step-size Hogwild! and position-based updates under inconsistent shared-memory reads and writes.A delay parameter τ controls how far past updates influence the shared memory.
- Asynchronous optimization: The expected convergence upper bound is sublinear, O(1/t), while SGD improves this bound by a factor of 2 and tolerates τ as large as t/ln t asymptotically.The paper also reports experiments confirming the analysis and shows higher-order delay terms become smaller than the leading O(1/t) term after a threshold.
- Scope: The contributions extend to non-convex component functions, although the objective F remains strongly convex.The non-convex extension removes convexity of f(w; ξ), not the paper’s strong-convexity condition on F.
2. New Framework for Convergence Analysis of SGD
The framework replaces bounded stochastic gradients with per-realization smoothness, deriving almost-sure convergence and sublinear rates for SGD under strong convexity, including non-convex component functions.
- Assumptions: SGD is analyzed with i.i.d. samples and L-smooth stochastic objective realizations, with strong convexity of F as the principal objective assumption.The analysis initially also considers convex component functions, then removes that requirement in weaker results.
- Convergence With Probability One: Theorem 1 establishes almost-sure convergence for diminishing stepsizes under smoothness, convexity of realizations, and strong convexity of F, without bounded gradients.The stepsize sequence is required to satisfy the displayed summability conditions.
- Convergence Rates: Theorem 2 gives a sublinear convergence rate for the expected squared distance to the optimum under a diminishing stepsize schedule.The schedule uses ηt = α/[µ(t+E)] with α = 2 and η0 = 1/(2L).
- Without Convexity: Without convexity of component functions, Theorems 3 and 4 retain almost-sure convergence and the sublinear result under Assumptions 1 and 2.The corresponding initial learning-rate bound is η0 = 1/(2Lκ), where κ = L/µ.
- Comparison: The smoothness-based analysis permits η0 = 1/(2Lκ), whereas the compared Bottou et al. condition requires η0 ≤ 1/(2Lκ^2).Under component convexity, Theorem 2 instead uses η0 = 1/(2L).
3. Asynchronous Stochastic Optimization aka Hogwild!
The paper extends the smoothness-based SGD analysis to asynchronous Hogwild! updates with inconsistent shared-memory reads and writes, using a general filtered vector-update recurrence.
- Background: Hogwild! applies stochastic-gradient updates independently across processors to shared memory without locking, enabling better scaling than synchronous SGD.Prior analyses considered bounded gradients and, in some cases, consistent reads or single-entry updates.
- Convergence Analysis: The paper analyzes diminishing-step Hogwild! for the general stochastic problem, without bounded gradients, and extends the result to non-convex component functions.Only the expected objective F must remain strongly convex in the stated extension.
- Recursion: The recurrence models inconsistent reads as vectors assembled from mixed previous updates, while atomic entry reads and writes proceed in shared memory.The delay τ guarantees that updates through iteration t−τ are included in the read vector.
- Recursion: A general recurrence covers full-gradient Hogwild! and position-based updates that select one uniformly chosen non-zero gradient entry.The parameter D controls the filtered update pattern through diagonal 0/1 matrices.
- Special Cases: When D = 1 and τ = 0, the asynchronous recurrence reduces to SGD, and the resulting bound improves through the expected gradient support size.For D = 1, the support factor becomes E[|Dξ|].
- Results: The leading convergence-rate term is independent of delay τ, although smaller delay or sparsity improves second-order terms.The analysis allows a monotonically increasing delay, with additional terms of order O(1/t ln t).
4. Numerical Experiments
Experiments evaluate the proposed method on ijcnn1 and covtype, varying the fraction of updated non-zero gradient positions and the delay parameter τ. Across both datasets, τ ≤100 has little effect on the expected convergence rate.
- Experimental setup: Experiments use ℓ2-regularized logistic regression on ijcnn1 and covtype datasets.The datasets contain 91,701 and 406,709 training examples, respectively.
- Experimental setup: The experiments average results over 10 runs and select the step size according to Theorem 5.The step size uses η_t = 4/[µ(t+E)] with E determined by τ, L, D, and µ.
- Fraction of non-zero positions: For fractions v ∈ {1, 3/4, 2/3, 1/2, 1/3, 1/4}, each update selects a random subset of the gradient’s non-zero positions.Figures 1 and 3 plot training loss for these fractions with τ = 10, using coordinate updates and epochs as alternative horizontal axes.
- Asynchrony parameter: For τ ∈ {1, 10, 100}, the experiments use the whole non-zero gradient set for each update.Figures 2 and 4 examine these settings on ijcnn1 and covtype.
- Asynchrony parameter: τ ≤100 has little effect on the expected convergence rate.The analysis permits τ up to 524 for ijcnn1 and 1058 for covtype at the stated 50-epoch horizon.
5. Conclusion
The paper analyzes diminishing-step-size stochastic gradient methods for strongly convex objectives without bounded stochastic gradients, including Hogwild! as a special case. It proves almost sure SGD convergence and sublinear expected-rate bounds for a general recursion.
- 5. Conclusion: The analysis covers strongly convex stochastic gradient algorithms with diminishing step sizes and Lipschitz-continuous individual function realizations.It does not require bounds on stochastic gradient norms.
- 5. Conclusion: The paper proves almost sure convergence of SGD.
- 5. Conclusion: A general recursion receives sublinear upper bounds on its expected convergence rate and includes Hogwild! with inconsistent reads and writes.
- 5. Conclusion: The analysis provides intuition for convergence behavior observed in practice.
A. Review of Useful Theorems
This appendix reviews a general stochastic-recursion convergence theorem based on conditional expected descent with nonnegative error terms. It also states the assumptions and notation used for that theorem.
- A. Review of Useful Theorems: The reviewed result considers nonnegative, filtration-measurable sequences Y_k, Z_k, and W_k.
- A. Review of Useful Theorems: The sequences are indexed from k = 0, 1, … under an increasing filtration {F_k}.
- A. Review of Useful Theorems: Its key condition is E[Y_{k+1}|F_k] ≤ Y_k − Z_k + W_k for every k.The inequality expresses conditional decrease through Z_k with additive term W_k.
B.1. Proof of Lemma 1
The proof of Lemma 1 invokes assumptions on the stochastic objective and introduces N as twice the expected squared stochastic-gradient norm at the optimum.
- B.1. Proof of Lemma 1: Lemma 1 applies when Assumptions 2 and 3 hold for every w ∈ R^d.
- B.1. Proof of Lemma 1: The proof uses w* = arg min_w F(w) and a random variable ξ.
- B.1. Proof of Lemma 1: N is defined as 2E[||∇f(w*; ξ)||^2].Thus N measures the expected squared stochastic-gradient norm at the optimum, up to a factor of two.
B.2. Proof of Lemma 2
Lemma 2 is stated under Assumptions 1 and 2, using the optimizer w∗ and a noise-related constant defined through the stochastic gradient at w∗.
- Lemma 2 assumes Assumptions 1 and 2 for every w ∈ R^d.
- The optimizer is defined as w∗ = arg min_w F(w).
- The constant N is defined as 2E[∥∇f(w∗; ξ)∥2].
C. Analysis for Algorithm 1
The analysis of Algorithm 1 establishes almost-sure convergence and an expected convergence bound under diminishing stepsizes, while defining the support and collision quantities used for asynchronous analysis.
- The analysis of Algorithm 1 is conducted under Assumptions 1, 2, and 3.
- For i.i.d. samples, N equals 2E[∥∇f(w∗; ξ_t)∥2] for every iteration t.
- Theorem 1 gives sufficient stepsize conditions for almost-sure convergence to w∗.
- Theorem 2 uses η_t = α/[µ(t+E)] with α = 2 and E = 2αL/µ, subject to η_t ≤ 1/(2L).
- The support-collision quantity ∆ measures the probability that two stochastic-gradient supports intersect.
- Asynchronous reads and writes are modeled with atomic coordinate operations and a bounded delay τ, without requiring consistent reads.
D.2. Main Analysis
The main analysis develops lemmas for asynchronous masked updates and derives convergence bounds for read and actual vectors under diminishing stepsizes, extending the result beyond one assumption set.
- The proof develops preliminary lemmas that yield a recursive inequality for the convergence analysis.
- The asynchronous model uses a filtration containing prior samples, coordinate selections, and update masks.
- The analysis requires η_t ≤ 1/(4LD) and uses E = max{2τ, 4LαD/µ} for the diminishing stepsize schedule.
- Theorem 5 bounds both E[∥ŵ_t − w∗∥2] and E[∥w_t − w∗∥2] after t iterations, with t′ = t∆̄_D/D expected single-entry updates.
- The non-convex extension removes Assumption 3 by strengthening the condition on E to E ≥ 4L_καD/µ.
D.4. Sensitivity to τ
The τ-sensitivity analysis allows delay to grow with iteration count and obtains an expected convergence rate of 1/t + O(1/(t ln t)).
- The analysis permits an increasing delay τ(t), with E(t) = 2τ(t), while requiring τ(t) ≤ t.
- The expected convergence rate of read vectors is 1/t + O(1/(t ln t)).
- The stepsize uses η_t = α_t/[µ(t+2τ(t))] with 12 ≤ α_t ≤ α.
- The expected convergence rate of the actual iterates satisfies the same bound.
- Higher-order terms containing τ(t) are at most the leading term under the stated delay conditions.