Stochastic Gradient Descent › SGD Convergence Properties

The theoretical convergence guarantees of SGD depend on properties of the loss function and on how the learning rate is set.

For convex loss functions, classical optimization theory provides clean convergence results. The key insight is that we need the learning rates to sum to infinity (so the optimizer can travel as far as needed), but the sum of their squares must be finite (so step sizes shrink fast enough to prevent endless oscillation). Formally, if the loss is convex and the learning rates $\{\eta_t\}$ satisfy the Robbins-Monro conditions:

$$\sum_{t=1}^{\infty} \eta_t = \infty$$ $$\sum_{t=1}^{\infty} \eta_t^2 < \infty$$

where:

• $\eta_t$: the learning rate at iteration $t$
• $\sum_{t=1}^{\infty} \eta_t = \infty$: the divergence condition, which ensures the optimizer is not trapped in any finite region of parameter space
• $\sum_{t=1}^{\infty} \eta_t^2 < \infty$: the square-summability condition, which ensures that accumulated gradient noise does not prevent convergence

Then SGD converges to the global minimum with probability one. The classic schedule satisfying both conditions is:

$$\eta_t = \frac{c}{t + t_0}$$

where:

• $c > 0$: a positive constant that sets the scale of the learning rate
• $t_0 \geq 0$: an optional offset that prevents the learning rate from being excessively large at $t = 0$

This polynomial decay satisfies the divergence condition (the harmonic series $\sum_t 1/t$ diverges) and the square-summability condition (the series $\sum_t 1/t^2$ converges).

In practice, neural networks have non-convex losses. The Robbins-Monro theory does not directly apply. But the spirit carries over: a decaying learning rate helps SGD settle into a minimum rather than bouncing around it.

For non-convex losses (the realistic case for neural networks), the convergence theory is weaker. SGD is guaranteed to converge to a stationary point, a point where the gradient is zero. But a stationary point might be a local minimum, a saddle point, or even a local maximum (though the last case is rare and unstable in practice).

The surprising insight from empirical and theoretical work is that for overparameterized neural networks, almost all local minima have similar loss values. The loss landscape has many valleys, but they are all roughly equally deep. This means that SGD almost always finds a solution with good test performance, even though it is not guaranteed to find the globally optimal parameters.

The noise in mini-batch gradient estimates can help optimization and generalization rather than merely disrupting updates.

Escaping shallow minima. The random fluctuations in SGD gradient estimates can push the optimizer out of sharp, narrow minima. Wide, flat minima are more robust to noise (the gradient stays small even with perturbations), so SGD naturally gravitates toward them over time. This "implicit regularization" toward flat minima is thought to be a major reason why SGD generalizes well.

Saddle point escape. In high-dimensional loss landscapes, saddle points are far more common than local minima. At a saddle point, the gradient is zero, but the loss can be decreased by moving in at least one direction. SGD noise provides random perturbations that break the symmetry at saddle points, allowing the optimizer to continue making progress. We revisit saddle points in more detail later.

Noise as regularization. The SGD noise is equivalent to a form of regularization on the loss function. Specifically, training with SGD of batch size $B$ and learning rate $\eta$ approximately minimizes a regularized version of the loss with regularization strength proportional to $\eta / B$. Smaller batches or larger learning rates introduce more noise and thus more implicit regularization.