Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) is an iterative optimization algorithm that minimizes an objective function by taking steps in the direction of the negative gradient estimated from one or a few randomly sampled data points rather than the full dataset. Key result: despite using noisy gradient estimates, SGD converges (in expectation) to a minimizer for convex problems and to good solutions for non-convex ones, at vastly lower per-iteration cost. Where it applies: machine learning, deep neural network training, large-scale convex optimization, online learning. Who/when: rooted in the Robbins–Monro stochastic approximation method (1951); now the workhorse of modern deep learning.

Stochastic Gradient Descent solves optimization problems of the form $min_{w} F (w) = \frac{1}{n} \sum_{i = 1}^{n} f_{i} (w)$ — a sum (or average) of many component functions, typically one per training example. Instead of computing the exact gradient $\nabla F (w)$ , which requires a full pass over all $n$ data points, SGD picks a random index $i$ and uses $\nabla f_{i} (w)$ as a cheap, unbiased estimate. This matters enormously because in machine learning $n$ can be millions or billions; a single full-batch gradient step is prohibitively expensive, whereas SGD makes progress after seeing just one example. The surprising fact is that the noise in the gradient estimate, far from being merely a tolerated nuisance, often helps: it lets the iterate escape shallow local minima and saddle points and is conjectured to bias training toward flatter, better-generalizing solutions.

The Core Insight

The true gradient of an average is the average of gradients. Therefore a single randomly chosen gradient is an unbiased estimator of the true gradient: $E_{i} [\nabla f_{i} (w)] = \nabla F (w)$ . You can replace an expensive exact gradient with a cheap noisy one and still, on average, move downhill. Trade per-step accuracy for a massive increase in the number of steps — and win.

Formal Statement

The Finite-Sum Objective and the SGD Update

We seek to minimize an objective that is a finite average of component functions:

F (w) = \frac{1}{n} i = 1 \sum n f_{i} (w), w \in R^{d}

⟳In supervised learning,

f_{i} (w) = ℓ (h_{w} (x_{i}), y_{i})

is the loss of model

h_{w}

on the

i

-th training pair

(x_{i}, y_{i})

; the average is the empirical risk.

The symbols:

$w$ — the parameter vector (weights) being optimized, in $R^{d}$ .
$F$ — the full objective (empirical risk / total loss).
$f_{i}$ — the loss contributed by the $i$ -th data point.
$n$ — number of training examples.
$d$ — number of parameters.

The SGD update rule at iteration $t$ samples an index $i_{t}$ uniformly at random from ${1, \dots, n}$ and steps:

w_{t + 1} = w_{t} - η_{t} \nabla f_{i_{t}} (w_{t})

⟳Replace the full gradient

\nabla F

in ordinary gradient descent

w_{t + 1} = w_{t} - η_{t} \nabla F (w_{t})

by the single-sample estimate

\nabla f_{i_{t}}

Here $η_{t} > 0$ is the learning rate (step size) at step $t$ . The mini-batch variant averages over a random subset $B_{t} \subseteq {1, \dots, n}$ of size $b$ :

w_{t + 1} = w_{t} - η_{t} \frac{1}{∣ B _{t} ∣} i \in B_{t} \sum \nabla f_{i} (w_{t})

⟳Averaging

b

unbiased estimators keeps the estimator unbiased but divides its variance by

b

(under independent sampling).

Unbiasedness of the Stochastic Gradient

If $i_{t}$ is sampled uniformly from ${1, \dots, n}$ , then the stochastic gradient is unbiased:

E_{i_{t}} [\nabla f_{i_{t}} (w_{t}) ∣ w_{t}] = \frac{1}{n} i = 1 \sum n \nabla f_{i} (w_{t}) = \nabla F (w_{t})

⟳Expectation over a uniform discrete index is the arithmetic mean of the values; linearity of the gradient turns the mean of gradients into the gradient of the mean.

Convergence of SGD, Convex Case

Let each $f_{i}$ be convex and the stochastic gradients have bounded second moment $E ∥\nabla f_{i_{t}} (w_{t}) ∥^{2} \leq G^{2}$ . Let $w^{⋆}$ be a minimizer and $w_{t}$ the iterates with $R = ∥ w_{1} - w^{⋆} ∥$ . Using a decreasing step size, the averaged iterate $\overset{w}{ˉ}_{T} = \frac{1}{T} \sum_{t = 1}^{T} w_{t}$ satisfies:

E [F (\overset{w}{ˉ}_{T})] - F (w^{⋆}) \leq \frac{R ^{2}}{2 η T} + \frac{η G ^{2}}{2}

with constant step $η$ , minimized at $η = R / (G T)$ giving an $O (R G / T)$ rate.

⟳Expand

∥ w_{t + 1} - w^{⋆} ∥^{2}

, take conditional expectation, apply convexity

F (w_{t}) - F (w^{⋆}) \leq ⟨ \nabla F (w_{t}), w_{t} - w^{⋆} ⟩

, telescope, and divide by

T

Why It Holds / Derivation

Convergence Bound for Convex SGD

Step 1 — One-step distance recursion. Start from the squared distance to the optimum and substitute the update [2]:

∥ w_{t + 1} - w^{⋆} ∥^{2} = ∥ w_{t} - η \nabla f_{i_{t}} (w_{t}) - w^{⋆} ∥^{2} .

Expanding the square:

∥ w_{t + 1} - w^{⋆} ∥^{2} = ∥ w_{t} - w^{⋆} ∥^{2} - 2 η ⟨ \nabla f_{i_{t}} (w_{t}), w_{t} - w^{⋆} ⟩ + η^{2} ∥\nabla f_{i_{t}} (w_{t}) ∥^{2} .

Step 2 — Take conditional expectation. Conditioning on

w_{t}

and using unbiasedness [4],

E [\nabla f_{i_{t}} (w_{t}) ∣ w_{t}] = \nabla F (w_{t})

, and the bounded-moment assumption:

E [∥ w_{t + 1} - w^{⋆} ∥^{2} ∣ w_{t}] \leq ∥ w_{t} - w^{⋆} ∥^{2} - 2 η ⟨ \nabla F (w_{t}), w_{t} - w^{⋆} ⟩ + η^{2} G^{2} .

Step 3 — Apply convexity. For convex

F

⟨ \nabla F (w_{t}), w_{t} - w^{⋆} ⟩ \geq F (w_{t}) - F (w^{⋆})

. Substituting and rearranging:

2 η (F (w_{t}) - F (w^{⋆})) \leq ∥ w_{t} - w^{⋆} ∥^{2} - E [∥ w_{t + 1} - w^{⋆} ∥^{2} ∣ w_{t}] + η^{2} G^{2} .

Step 4 — Take total expectation and telescope. Summing

t = 1, \dots, T

, the distance terms telescope:

2 η t = 1 \sum T (E [F (w_{t})] - F (w^{⋆})) \leq ∥ w_{1} - w^{⋆} ∥^{2} - E [∥ w_{T + 1} - w^{⋆} ∥^{2}] + T η^{2} G^{2} \leq R^{2} + T η^{2} G^{2} .

Step 5 — Use Jensen and average. Since

F

is convex,

F (\overset{w}{ˉ}_{T}) \leq \frac{1}{T} \sum_{t} F (w_{t})

. Dividing through by

2 η T

yields exactly [5].

■

Herbert Robbins & Sutton Monro | 1951

The mathematical ancestor of SGD is the Robbins–Monro stochastic approximation method. Herbert Robbins (1915–2001), an American statistician, and his student Sutton Monro published "A Stochastic Approximation Method" in the Annals of Mathematical Statistics (1951). They studied the problem of finding the root of a function $M (x)$ that can only be observed with random noise — solving $M (θ) = α$ using noisy measurements. Their iteration $x_{n + 1} = x_{n} - a_{n} (y_{n} - α)$ , with step sizes satisfying $\sum a_{n} = \infty$ and $\sum a_{n}^{2} < \infty$ , is precisely the convergence condition that modern SGD learning-rate schedules respect. Robbins also co-founded the field of empirical Bayes and made deep contributions to sequential analysis. SGD is the gradient-flavored special case of their general scheme: estimating the zero of the gradient (i.e., a stationary point) from noisy gradient observations.

Building Intuition

Picture a hiker descending a foggy mountain at night. Full-batch gradient descent is a hiker who, before each step, painstakingly surveys the entire surrounding terrain to find the steepest downhill direction — accurate but agonizingly slow. SGD is a hiker who glances at just one patch of ground near their feet and steps that way immediately. Any single glance might point slightly wrong, but over many quick steps the errors average out and the hiker descends — far faster overall because they take a thousand quick steps in the time the careful hiker takes one.

The noise is not purely harmful. Near a narrow crevice (a sharp minimum), the random jitter knocks the SGD hiker out, so they tend to settle in wide, flat valleys (flat minima), which in machine learning correlate with better generalization. The learning rate $η_{t}$ controls step length: large early steps cover ground fast; shrinking later steps let the hiker settle precisely. This is why schedules like $η_{t} \propto 1/ t$ or "warmup then decay" work — they balance exploration against convergence.

SGD vs. full-batch gradient descent trajectories on a loss surface contour map

Worked Examples

Linear Regression with One SGD Step

Given: Fit

h_{w} (x) = w_{1} x + w_{0}

by minimizing squared error. Component loss

f_{i} (w) = \frac{1}{2} (w_{1} x_{i} + w_{0} - y_{i})^{2}

. Current parameters

w_{0} = 0.5

w_{1} = 1.0

. Sampled point

(x_{i}, y_{i}) = (2, 5)

. Learning rate

η = 0.1

. Step 1 — Prediction and residual.

h_{w} (2) = 1.0 (2) + 0.5 = 2.5, r = h_{w} (2) - y = 2.5 - 5 = - 2.5.

Step 2 — Component gradient.

\frac{\partial f _{i}}{\partial w _{0}} = r = - 2.5, \frac{\partial f _{i}}{\partial w _{1}} = r x_{i} = - 2.5 \times 2 = - 5.0.

Step 3 — SGD update via [2].

w_{0} \leftarrow 0.5 - 0.1 (- 2.5) = 0.5 + 0.25 = 0.75,

w_{1} \leftarrow 1.0 - 0.1 (- 5.0) = 1.0 + 0.5 = 1.5.

Step 4 — Check. New prediction

h_{w} (2) = 1.5 (2) + 0.75 = 3.75

, closer to target

5

than the old

2.5

. ✓

w_{0} = 0.75, w_{1} = 1.5 (dimensionless parameter units)

Choosing a Step Size from the Convergence Bound

Given: A convex problem with

R = ∥ w_{1} - w^{⋆} ∥ = 4

, gradient-norm bound

G = 3

, and a budget of

T = 10, 000

iterations. Use the optimal constant step from Theorem [5]. Step 1 — Optimal learning rate.

η^{⋆} = \frac{R}{G T} = \frac{4}{3 10000} = \frac{4}{3 \times 100} = \frac{4}{300} \approx 0.0133.

Step 2 — Resulting optimality gap. Plugging into [5] (both terms equal at the optimum):

E [F (\overset{w}{ˉ}_{T})] - F (w^{⋆}) \leq \frac{R G}{T} = \frac{4 \times 3}{100} = 0.12.

Step 3 — Scaling check. To halve the gap to

0.06

we need

T

to double, i.e.

T \to 40, 000

— four times as many iterations. The

1/ T

rate is the price of stochasticity.

η^{⋆} \approx 0.0133, gap \leq 0.12 (loss units)

Common Misconceptions

"SGD converges to the exact minimum." With a constant learning rate, SGD does not converge to

w^{⋆}

; it converges to a noise ball around it whose radius scales like

η σ

, where

σ

is the gradient noise scale. To reach the exact minimizer you must decay the step size (Robbins–Monro conditions:

\sum_{t} η_{t} = \infty

\sum_{t} η_{t}^{2} < \infty

). A constant rate gives fast initial progress but residual oscillation. "A bigger batch is always better." Larger batches reduce gradient variance and allow larger learning rates, but they (a) cost more per step, (b) often generalize worse (the "large-batch generalization gap"), and (c) give diminishing returns — variance drops only as

1/ b

. There is no universal optimum; the right batch size depends on hardware, problem, and the noise's regularizing benefit.

Unbiasedness Fails Without Uniform Sampling

Suppose you sample indices non-uniformly — say always picking the data points with the largest current loss (a naive "hard mining" scheme) — but still average plain gradients. Then $E_{i_{t}} [\nabla f_{i_{t}} (w_{t})] \neq = \nabla F (w_{t})$ , because the sampling probabilities $p_{i}$ are not $1/ n$ . The estimator becomes biased, and the convergence proof in [4]–[5] collapses: SGD may converge to the wrong point or not at all. To fix importance/non-uniform sampling you must reweight each gradient by $\frac{1}{n p _{i}}$ to restore unbiasedness:

E [\frac{1}{n p _{i_{t}}} \nabla f_{i_{t}} (w)] = i \sum p_{i} \cdot \frac{1}{n p _{i}} \nabla f_{i} (w) = \frac{1}{n} i \sum \nabla f_{i} (w) = \nabla F (w) .

Connections

SGD sits at the crossroads of several fields. It is a noisy special case of Gradient Descent, inheriting its first-order, derivative-based philosophy but trading exactness for speed. Its theoretical foundation is Stochastic Approximation (Robbins–Monro), and its analysis draws on Convex Optimization (for the convex rate [5]) and Martingale Theory (for almost-sure convergence proofs). In deep learning, the gradients $\nabla f_{i}$ are computed by Backpropagation, making SGD the optimizer that consumes what backprop produces. The continuous-time limit of SGD is a Stochastic Differential Equation — an overdamped Langevin diffusion — which links it to statistical physics and to Markov Chain Monte Carlo sampling. Variants like momentum connect it to Heavy-Ball Method and Nesterov acceleration, while adaptive schemes such as Adam blend it with per-coordinate scaling.

Real-World Applications

Deep neural network training. SGD (and its variants Adam, RMSProp, AdamW) trains essentially every modern model — ResNets for vision, Transformers for language, diffusion models for images. GPT-class and image-generation systems are all SGD-trained.
Large-scale logistic regression / linear models at companies like Google and Facebook for click-through-rate prediction over billions of examples, where full-batch gradients are infeasible.
Recommender systems — matrix factorization for Netflix/Spotify-style recommendations is trained by SGD over observed user–item ratings, updating latent factors one rating at a time.
Online learning and streaming data — SGD naturally handles data arriving sequentially (one example per update), used in adaptive spam filters and real-time bidding.
Reinforcement learning — policy-gradient and Q-learning updates are stochastic gradient steps on sampled trajectories (e.g., AlphaGo, robotics controllers).
Word embeddings — Word2Vec and GloVe learn vector representations via SGD over enormous text corpora using negative sampling.
Support Vector Machines at scale — the Pegasos algorithm solves the SVM objective by projected SGD, enabling training on datasets too large for quadratic-programming solvers.

Historical Development

1847 — Augustin-Louis Cauchy introduces the method of steepest descent (gradient descent), the deterministic ancestor.
1951 — Herbert Robbins and Sutton Monro publish "A Stochastic Approximation Method," establishing the iteration and step-size conditions underlying SGD.
1952 — Jacob Kiefer and Jack Wolfowitz extend stochastic approximation to gradient-free optimization (the Kiefer–Wolfowitz procedure).
1958 — Frank Rosenblatt's Perceptron learning rule is, in effect, an early online SGD step on a hinge-like loss.
1960s–1980s — Stochastic approximation matures in control theory; convergence theory (Ljung, Kushner, Clark) via the "ODE method" is developed.
1986 — Rumelhart, Hinton, and Williams popularize backpropagation, providing efficient $\nabla f_{i}$ for neural networks and reviving SGD for learning.
1998 — Léon Bottou and Yann LeCun champion SGD for large-scale learning; mini-batching and practical tricks become standard.
2010–2011 — Adaptive methods emerge: AdaGrad (Duchi, Hazan, Singer) and RMSProp (Hinton, unpublished) per-coordinate scaling.
2014 — Kingma and Ba introduce Adam, combining momentum with adaptive scaling; it becomes the default optimizer for deep learning.

Subtleties & Limits

Several deep questions about SGD remain only partially understood. (1) Why does SGD generalize so well in deep, overparameterized networks? The "implicit regularization" / "flat-minima" hypothesis — that SGD noise biases solutions toward flat regions with low test error — is supported empirically but lacks a complete theory. (2) Non-convex convergence guarantees are weak: for general non-convex $F$ , SGD provably reaches only an approximate stationary point ( $E ∥\nabla F ∥^{2}$ small), not a global minimum, yet in practice it finds excellent solutions. (3) The optimal learning-rate schedule — warmup, cosine decay, cyclic rates — is largely heuristic; principled, problem-adaptive schedules are an active research frontier. (4) The role of the noise covariance: the structure (not just magnitude) of SGD's gradient noise appears to matter for which minima are selected, and characterizing this anisotropic noise remains open. (5) Edge of stability: modern training often runs at learning rates where classical theory predicts divergence, yet loss still decreases — a phenomenon ("edge of stability") not explained by [5].