Stochastic Gradient Descent

Why we need something beyond full gradient descent

Suppose you are minimizing a loss over a dataset of N examples:

• •Data: {(xᵢ, yᵢ)}ᵢ₌₁ᴺ
• •Model parameters: θ (can be a vector of weights, or millions of neural network parameters)
• •Per-example loss: ℓᵢ(θ) = ℓ(θ; xᵢ, yᵢ)

A standard objective in supervised learning is the empirical risk (average loss):

L(θ) = (1/N) ∑ᵢ₌₁ᴺ ℓᵢ(θ)

Full-batch gradient descent computes the exact gradient of L:

∇L(θ) = (1/N) ∑ᵢ₌₁ᴺ ∇ℓᵢ(θ)

and then updates:

θₜ₊₁ = θₜ − ηₜ ∇L(θₜ)

This is conceptually simple, but computationally expensive when N is large, because each step requires scanning the whole dataset.

Definition: SGD in one sentence

Stochastic Gradient Descent (SGD) is gradient descent where the gradient ∇L(θ) is replaced by a stochastic (random) estimator ĝₜ computed from a randomly sampled single example or a mini-batch.

The SGD update is:

θₜ₊₁ = θₜ − ηₜ ĝₜ

where ĝₜ ≈ ∇L(θₜ) but is computed cheaply.

The stochastic gradient estimator ĝₜ

At iteration t, we sample:

• •Single-example SGD: pick iₜ uniformly from {1,…,N}
• •ĝₜ = ∇ℓᵢₜ(θₜ)

• •Mini-batch SGD: pick a batch Bₜ ⊂ {1,…,N} of size |Bₜ| = m
• •ĝₜ = (1/m) ∑_{i ∈ Bₜ} ∇ℓᵢ(θₜ)

Mini-batches are the modern default.

Why this is even “correct”: unbiasedness via expectation

A key idea is that ĝₜ is often an unbiased estimator of the true gradient.

Assume iₜ is uniform. Then:

E[ĝₜ | θₜ] = E[∇ℓᵢₜ(θₜ) | θₜ]

Because iₜ is uniform:

E[∇ℓᵢₜ(θₜ) | θₜ]

= (1/N) ∑ᵢ₌₁ᴺ ∇ℓᵢ(θₜ)

= ∇L(θₜ)

So, on average, SGD points in the same direction as full gradient descent.

For a mini-batch sampled uniformly (with or without replacement), you similarly get:

E[ĝₜ | θₜ] = ∇L(θₜ)

What prerequisites does SGD really depend on?

You listed that the learner already knows Gradient Descent and Expected Value. To understand SGD deeply, it also helps to have:

• •Derivatives and partial derivatives (∂/∂θⱼ)
• •Gradients ∇L(θ) (vector of partial derivatives)
• •Loss functions ℓ(θ; x, y)
• •Basic probability language (random sampling, variance)

SGD is not a different kind of optimization step; it’s the same step using a randomized gradient estimate.

Intuition: the “noise” is a feature, not only a bug

SGD introduces gradient noise:

ĝₜ = ∇L(θₜ) + ξₜ

where E[ξₜ | θₜ] = 0.

This noise has two major effects:

1. 1)Cheaper steps: each update is far less expensive than summing over N examples.
2. 2)Exploration: noise can help move through flat regions or escape shallow/poor minima in nonconvex landscapes (common in deep learning).

But noise also causes:

• •Less smooth progress
• •Need for careful learning-rate selection
• •Different convergence behavior (often to a neighborhood unless ηₜ decreases)

That tension—cheap noisy steps vs stable accurate steps—is the heart of SGD.

Why mini-batches exist (not just “because GPUs”)

Single-example SGD is maximally noisy: one example can be atypical, leading to a gradient that points away from the true average direction.

Mini-batches reduce noise by averaging several example gradients.

Let Bₜ be a mini-batch of size m. Define:

ĝₜ = (1/m) ∑_{i ∈ Bₜ} ∇ℓᵢ(θₜ)

This is still stochastic (depends on which batch you drew), but typically has smaller variance than a single-example gradient.

A variance viewpoint (the key conceptual lever)

Think of per-example gradients as random vectors:

G = ∇ℓᵢ(θ)

where i is a random index uniform over {1,…,N}. Then:

E[G] = ∇L(θ)

The mini-batch gradient is an average of m i.i.d. (approximately i.i.d.) samples:

ĝ = (1/m) ∑_{k=1}^m Gₖ

A core statistical fact: averaging reduces variance.

Very informally (scalar intuition), if Var(G) = σ², then:

Var(ĝ) = σ² / m

For vectors, you can think in terms of covariance matrices; the same “divide by m” scaling appears under independence assumptions.

Practical meaning:

• •Larger batch → less noisy updates → more stable training
• •Smaller batch → noisier updates → cheaper per step + sometimes better generalization

Why the noise can help (conceptual clarity)

It’s tempting to view noise as purely harmful. But in large nonconvex problems (deep nets), the objective surface has:

• •many flat regions (small ‖∇L‖)
• •saddle points (directions of both upward and downward curvature)
• •many local minima of varying “sharpness”

Noise can:

• •kick the iterate out of saddle points
• •prevent over-committing to sharp minima
• •act like a kind of implicit regularization (not guaranteed, but often observed)

A useful mental model is that SGD behaves like gradient descent plus random perturbations.

Epochs, iterations, and data order

Terminology you will see constantly:

• •Iteration / step: one parameter update (one mini-batch processed)
• •Epoch: one full pass through the dataset (N examples), often by shuffling and then batching

If batch size is m, then steps per epoch ≈ N/m.

A common training loop:

1. 1)Shuffle data (to avoid correlated batches)
2. 2)Split into mini-batches
3. 3)For each mini-batch B:

• •compute ĝ
• •update θ ← θ − η ĝ

The shuffle matters: if data are ordered (e.g., all cats then all dogs), batches become biased and SGD can behave poorly.

Comparing full-batch, mini-batch, and single-example

A subtle but important point: “SGD” often means “mini-batch SGD”

In modern ML, people say “SGD” even when m = 128 or 1024. The defining feature is still the same: ĝₜ is computed from a random subset, not the full dataset.

Measuring noise with the gradient norm

A quick diagnostic idea:

• •If ‖ĝₜ‖ fluctuates wildly across batches, you likely have high gradient noise.
• •Increasing batch size, using momentum, or lowering η can stabilize.

But there is no universal best setting: compute budget, model size, and data complexity all interact.

Why learning rate matters more in SGD than in full-batch GD

In full-batch GD, the gradient is deterministic for a given θ. In SGD, the update direction changes randomly each step.

If η is too large, noise can cause the iterates to bounce around or diverge.

If η is too small, progress becomes extremely slow.

So in SGD, η is not just “step size”; it controls the trade-off between:

• •moving quickly toward low loss
• •averaging out gradient noise

A useful decomposition: drift + noise

Write:

ĝₜ = ∇L(θₜ) + ξₜ, with E[ξₜ|θₜ] = 0.

Then the update is:

θₜ₊₁

= θₜ − ηₜ ∇L(θₜ) − ηₜ ξₜ

You can read this as:

• •−ηₜ ∇L(θₜ): the “drift” toward lower loss
• •−ηₜ ξₜ: the random walk component (scaled by ηₜ)

If ηₜ stays constant, the random component never truly disappears; you often converge to a neighborhood around a minimizer.

If ηₜ decays (ηₜ ↓ 0), noise influence shrinks and you can converge more tightly.

Classical convergence intuition (high level)

Under convexity and smoothness assumptions (and unbiased gradients with bounded variance), SGD can achieve convergence rates like:

• •with diminishing ηₜ, convergence in expectation to the optimum
• •with constant η, convergence to a ball whose radius depends on η and gradient variance

You don’t need the full proofs to use SGD, but the intuition is essential:

• •Constant η is good for fast training and tracking nonstationarity, but leaves residual noise.
• •Decaying ηₜ improves final convergence but can slow late-stage training.

Learning-rate schedules (what people do)

Common schedules:

1. 1)Step decay: η drops by a factor (e.g., ×0.1) at fixed epochs.
2. 2)Cosine decay: smooth decay from η₀ to near 0.
3. 3)Warmup: start with a small η and increase over the first few epochs.

Warmup helps when early gradients are unstable (common in deep nets).

Batch size and learning rate are linked

Bigger batches reduce gradient variance, so you can often use larger η.

A rough heuristic sometimes used is “linear scaling”:

η ∝ m

when increasing batch size m, at least within some range.

But this is not a law; it depends on model, optimizer (momentum/Adam), and data.

Momentum (brief, because it often comes with SGD)

Many practitioners mean “SGD with momentum.” Momentum reduces variance by averaging gradients over time.

A standard momentum form:

vₜ₊₁ = β vₜ + ĝₜ

θₜ₊₁ = θₜ − η vₜ₊₁

with β ∈ [0,1). Typical β is 0.9.

Conceptually:

• •If gradients point consistently in one direction, momentum accelerates.
• •If gradients oscillate due to noise, momentum damps oscillation.

Even if you don’t use momentum in a first implementation, you should recognize it as a key stabilization tool.

Convergence “look and feel” in practice

When you plot training loss vs steps:

• •Full-batch GD: smoother curve; each step expensive
• •SGD: noisy curve; each step cheap

Often you care about loss vs wall-clock time, not loss vs number of steps.

SGD wins because it can take many more steps per second.

When SGD is especially appropriate

SGD shines when:

• •N is large (millions of examples)
• •model is large (deep nets)
• •you need frequent updates (online/streaming)
• •exact gradients are too costly

When full-batch methods may be fine:

• •small N
• •strongly convex objective with cheap exact gradients
• •you want very stable deterministic progress

A practical checklist for stability

If training diverges or is wildly unstable:

• •Reduce η (most common fix)
• •Increase batch size m
• •Add momentum (or reduce β if already using it)
• •Normalize inputs / use batch norm (modeling choice)
• •Check for exploding gradients (clip ‖g‖)

SGD is simple, but its behavior is tightly coupled to these choices.

Why linear regression is the perfect “glass box” example

Linear regression lets you see SGD without distractions:

• •the loss is convex
• •gradients have a closed form
• •you can compute both full and stochastic gradients

Yet the training loop is structurally the same as in deep learning.

Empirical risk minimization template

Most ML training loops fit this template:

L(θ) = (1/N) ∑ᵢ ℓᵢ(θ)

SGD uses the per-example (or per-batch) gradient to approximate ∇L.

This same structure appears in:

• •classification with cross-entropy
• •matrix factorization
• •neural networks (backprop computes ∇ℓᵢ)

So once SGD is clear, “training deep networks” becomes less mysterious: the core loop is the same, only the gradient computation is more complex.

Practical hyperparameters: what you actually tune

The big three:

1. 1)Learning rate η
2. 2)Batch size m
3. 3)Number of epochs / steps

Secondary but common:

• •shuffle strategy
• •momentum β
• •weight decay (ℓ² regularization)

A compact comparison of trade-offs:

Interpreting “generalization” effects

Empirically, small-batch SGD often finds solutions that generalize better than large-batch training for the same compute.

One intuitive story: noise biases the optimizer toward flatter minima (regions where small parameter changes don’t increase loss much). Flatter minima often correlate with better generalization.

This is not a universal theorem, but it’s a useful working intuition.

Connections to the nodes you unlock

SGD is the workhorse behind many advanced methods:

• •Deep Learning: training neural networks is essentially repeated mini-batch SGD updates using backprop gradients.
• •Policy Gradient Methods: gradients are estimated from sampled trajectories; the stochasticity is fundamental (you can’t enumerate all futures).
• •Diffusion Models: training score networks uses mini-batch SGD over noisy samples and time steps.
• •Meta-Learning: algorithms like MAML involve differentiating through SGD steps; the SGD update itself becomes part of the computation graph.

A final conceptual anchor

If you remember only one thing:

SGD is not “a different update rule.” It is gradient descent using a random estimate of the gradient.

Everything else—mini-batches, schedules, momentum, stability tricks—is about managing the consequences of that randomness.