Source-linked AI summary
Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
Mark Schmidt, Nicolas Le Roux
TL;DR
The paper studies whether stochastic gradient descent can avoid decreasing step sizes when optimizing a smooth convex function formed by averaging differentiable components. It analyzes a strong growth condition and shows that a sufficiently small constant step size yields O(1/k) convergence for convex objectives and linear convergence for strongly convex objectives.
Problem
Stochastic gradient descent traditionally requires decreasing step sizes for convergence, producing slower rates than constant-step deterministic methods.
Method
The paper analyzes stochastic gradient descent under a strong growth condition bounding individual gradients relative to the average gradient.
Results
O(1/k) convergence is obtained for convex objectives, while strongly convex objectives achieve an expected linear convergence rate with a sufficiently small constant step size.
Takeaways & Limitations
Under the stated assumptions, stochastic gradient descent can use a constant step size and attain the convergence rates associated with deterministic gradient methods.
Takeaways & Limitations
The strong growth condition is very strong, is not satisfied in most applications, and requires all residuals to be zero at solutions in nonlinear least squares.
Abstract
from arXiv · showhide
We consider optimizing a function smooth convex function $f$ that is the average of a set of differentiable functions $f_i$, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient $f_i'$ is bounded by a linear function of the norm of the average gradient $f'$. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an $O(1/k)$ convergence rate, and has a linear convergence rate if $g$ is strongly-convex.
1 Deterministic vs. Stochastic Gradient Descent
The section contrasts stochastic and deterministic gradient descent: stochastic updates have iteration cost independent of N but traditionally require decreasing step sizes, whereas the paper shows that a strong growth condition enables deterministic-like rates with a sufficiently small constant step size.
- Stochastic gradient iterations cost independently of N because each update uses one uniformly sampled data point.
- O(1/√k) expected error is obtained by stochastic gradient descent on convex objectives with decreasing step sizes.
- O(1/k) error is achieved by deterministic gradient descent with a constant step size on convex objectives.
- For strongly convex objectives, decreasing-step stochastic descent has O(1/k) error, while constant-step deterministic descent converges linearly.
- A strong growth condition on individual gradients lets stochastic gradient descent with a sufficiently small constant step size attain the deterministic method’s convergence rates in expectation.
2 A Strong Growth Condition
The strong growth condition bounds every individual gradient by a linear function of the average gradient, but it is restrictive and often fails in applications.
- The condition bounds the norms of individual gradients by a linear function of the norm of the average gradient.
- Any optimal solution must also be a stationary point for every individual function under this condition.
- In nonlinear least squares, the condition requires all residuals to be zero at the solution.
- Under the condition, prior work established constant-step convergence for deterministic incremental gradient methods.
3 Error Properties
The stochastic iteration is represented as an exact full-gradient step plus a random error whose conditional mean is zero and whose variance can be bounded using the strong growth condition.
- The stochastic update is rewritten as a constant-step full-gradient iteration with an additive gradient error.
- Uniform sampling makes the stochastic gradient error have mean zero.
- The analysis bounds the error variance in terms of the norm of the full gradient using the strong growth condition.
4 Upper Bound on Progress
Using smoothness and the inexact-gradient representation, the analysis derives an upper bound on one-step objective progress in terms of the full gradient and stochastic error.
- Lipschitz continuity of the gradient supplies the basic inequality used to bound the next objective value.
- The update displacement equals the negative step size times the full gradient plus the error.
- The resulting progress bound depends on the squared norm of the combined full gradient and error.
5 Descent Property
For a sufficiently small constant step size, the expected objective value decreases after each stochastic gradient iteration. This descent holds whenever the current iterate is not a minimizer and the step size satisfies the stated bound.
- Descent guarantee: A sufficiently small constant step size makes E[f(xk+1)] less than f(xk).The result follows by taking expectations of the one-step bound under the specified error assumptions.
- Descent guarantee: The descent condition converts the stochastic update into an expected objective-decreasing procedure despite its per-iteration randomness.
- Descent guarantee: If xk is not a minimizer, the stochastic iteration is expected to decrease the objective for every step size satisfying the derived condition.
6 Linear Convergence for Strongly Convex Objectives
For strongly convex objectives, the analysis converts the descent inequality into a geometric bound on expected suboptimality. As B approaches one, the resulting rate approaches the deterministic rate (1 − µ/L)^k.
- Rate derivation: The proof applies strong convexity at xk and minimizes the resulting inequality with respect to the minimizer x∗.
- Rate derivation: Subtracting f(x∗), taking expectations over the error sequence, and applying the resulting recursion yields geometric decay.
- Linear convergence result: ρ < 1 implies that E[f(xk)] − f(x∗) decreases geometrically with iteration number k.
- Linear convergence result: As B approaches one, the stochastic method approaches the deterministic rate (1 − µ/L)^k with step size 1/L.
7 Sublinear O(1/k) Convergence for Convex Objectives
For convex objectives that are not necessarily strongly convex, assuming a minimizer exists, the analysis uses a constant step size to derive an O(1/k) error bound. The proof combines convexity, expectation bounds, telescoping, and monotonicity of expected objective values.
- Sublinear convergence result: For convex f with at least one minimizer x∗, the analysis uses step size α = 1/LB^2 to establish O(1/k) error.
- Proof construction: Convexity bounds the gradient inner product involving xk and x∗, which is substituted into the one-step objective inequality.
- Proof construction: Taking expectations and choosing β = 1 − 1/LB^2 cancels all terms involving ∥f′(xk)∥.
- Proof construction: Summing the per-iteration error from k = 0 to n − 1 and using (1 − β)/α = L produces the aggregate bound.
- Sublinear convergence result: Because E[f(xk+1)] is non-increasing, the summed terms are at least k times the final term, yielding the sublinear rate.