Stochastic Gradient Descent

⚡ Key Takeaways

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.

💡 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: $\mathbb{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.

DefinitionThe Finite-Sum Objective and the SGD Update

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

1

\quad F(w) = \frac{1}{n}\sum_{i=1}^{n} f_i(w), \qquad w \in \mathbb{R}^d

Derivation hint: In supervised learning, $f_i(w) = \ell(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 $\mathbb{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:

2

\quad w_{t+1} = w_t - \eta_t \,\nabla f_{i_t}(w_t)

Derivation hint: Replace the full gradient $\nabla F$ in ordinary gradient descent $w_{t+1}=w_t-\eta_t\nabla F(w_t)$ by the single-sample estimate $\nabla f_{i_t}$ . Here $\eta_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$ :

3

\quad w_{t+1} = w_t - \eta_t \,\frac{1}{|B_t|}\sum_{i \in B_t} \nabla f_i(w_t)

Derivation hint: Averaging $b$ unbiased estimators keeps the estimator unbiased but divides its variance by $b$ (under independent sampling).

TheoremUnbiasedness of the Stochastic Gradient

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

4

\quad \mathbb{E}_{i_t}\!\left[\nabla f_{i_t}(w_t) \mid w_t\right] = \frac{1}{n}\sum_{i=1}^n \nabla f_i(w_t) = \nabla F(w_t)

Derivation hint: 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.

TheoremConvergence of SGD, Convex Case

Let each $f_i$ be convex and the stochastic gradients have bounded second moment $\mathbb{E}\|\nabla f_{i_t}(w_t)\|^2 \le G^2$ . Let $w^\star$ be a minimizer and $w_t$ the iterates with $R = \|w_1 - w^\star\|$ . Using a decreasing step size, the averaged iterate $\bar{w}_T = \frac{1}{T}\sum_{t=1}^T w_t$ satisfies:

5

\quad \mathbb{E}\!\left[F(\bar{w}_T)\right] - F(w^\star) \;\le\; \frac{R^2}{2\eta T} + \frac{\eta G^2}{2}

with constant step $\eta$ , minimized at $\eta = R/(G\sqrt{T})$ giving an $O(RG/\sqrt{T})$ rate. Derivation hint: Expand $\|w_{t+1}-w^\star\|^2$ , take conditional expectation, apply convexity $F(w_t)-F(w^\star)\le \langle \nabla F(w_t), w_t-w^\star\rangle$ , telescope, and divide by $T$ .

ProofConvergence 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^\star\|^2 = \|w_t - \eta\nabla f_{i_t}(w_t) - w^\star\|^2.

Expanding the square:

\|w_{t+1}-w^\star\|^2 = \|w_t-w^\star\|^2 - 2\eta\langle \nabla f_{i_t}(w_t),\, w_t-w^\star\rangle + \eta^2\|\nabla f_{i_t}(w_t)\|^2.

Step 2 — Take conditional expectation. Conditioning on $w_t$ and using unbiasedness [4], $\mathbb{E}[\nabla f_{i_t}(w_t)\mid w_t] = \nabla F(w_t)$ , and the bounded-moment assumption:

\mathbb{E}[\|w_{t+1}-w^\star\|^2\mid w_t] \le \|w_t-w^\star\|^2 - 2\eta\langle \nabla F(w_t), w_t-w^\star\rangle + \eta^2 G^2.

Step 3 — Apply convexity. For convex $F$ , $\langle \nabla F(w_t), w_t-w^\star\rangle \ge F(w_t)-F(w^\star)$ . Substituting and rearranging:

2\eta\big(F(w_t)-F(w^\star)\big) \le \|w_t-w^\star\|^2 - \mathbb{E}[\|w_{t+1}-w^\star\|^2\mid w_t] + \eta^2 G^2.

Step 4 — Take total expectation and telescope. Summing $t=1,\dots,T$ , the distance terms telescope:

2\eta\sum_{t=1}^T \big(\mathbb{E}[F(w_t)]-F(w^\star)\big) \le \|w_1-w^\star\|^2 - \mathbb{E}[\|w_{T+1}-w^\star\|^2] + T\eta^2 G^2 \le R^2 + T\eta^2 G^2.

Step 5 — Use Jensen and average. Since $F$ is convex, $F(\bar w_T) \le \frac{1}{T}\sum_t F(w_t)$ . Dividing through by $2\eta T$ yields exactly [5]. $\blacksquare$

∎

HR

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(\theta)=\alpha$ using noisy measurements. Their iteration $x_{n+1}=x_n - a_n\big(y_n-\alpha\big)$ , 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.

🧠 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 $\eta_t$ controls step length: large early steps cover ground fast; shrinking later steps let the hiker settle precisely. This is why schedules like $\eta_t \propto 1/t$ or "warmup then decay" work — they balance exploration against convergence.

Figure

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

ExampleLinear Regression with One SGD Step

Given: Fit $h_w(x) = w_1 x + w_0$ by minimizing squared error. Component loss $f_i(w) = \tfrac12 (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 $\eta = 0.1$ .

Step 1 — Prediction and residual.

h_w(2) = 1.0(2) + 0.5 = 2.5, \qquad r = h_w(2) - y = 2.5 - 5 = -2.5.

Step 2 — Component gradient.

\frac{\partial f_i}{\partial w_0} = r = -2.5, \qquad \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$ . ✓

\boxed{w_0 = 0.75,\quad w_1 = 1.5 \ \text{(dimensionless parameter units)}}

ExampleChoosing a Step Size from the Convergence Bound

Given: A convex problem with $R = \|w_1 - w^\star\| = 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.

\eta^\star = \frac{R}{G\sqrt{T}} = \frac{4}{3\sqrt{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):

\mathbb{E}[F(\bar w_T)] - F(w^\star) \le \frac{RG}{\sqrt{T}} = \frac{4 \times 3}{100} = 0.12.

Step 3 — Scaling check. To halve the gap to $0.06$ we need $\sqrt{T}$ to double, i.e. $T \to 40{,}000$ — four times as many iterations. The $1/\sqrt{T}$ rate is the price of stochasticity.

\boxed{\eta^\star \approx 0.0133,\qquad \text{gap} \le 0.12 \ \text{(loss units)}}

⚠️ Common mistake

"SGD converges to the exact minimum." With a constant learning rate, SGD does not converge to $w^\star$ ; it converges to a noise ball around it whose radius scales like $\sqrt{\eta}\,\sigma$ , where $\sigma$ is the gradient noise scale. To reach the exact minimizer you must decay the step size (Robbins–Monro conditions: $\sum_t \eta_t = \infty$ , $\sum_t \eta_t^2 < \infty$ ). A constant rate gives fast initial progress but residual oscillation.

⚠️ Common mistake

"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.

CounterexampleUnbiasedness 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 $\mathbb{E}_{i_t}[\nabla f_{i_t}(w_t)] \ne \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:

\mathbb{E}\!\left[\tfrac{1}{n p_{i_t}}\nabla f_{i_t}(w)\right] = \sum_i p_i \cdot \tfrac{1}{n p_i}\nabla f_i(w) = \tfrac1n\sum_i \nabla f_i(w) = \nabla F(w).

connection

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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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 ( $\mathbb{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].

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also