Noesis
3.2.1Training Deep Networks

Stochastic gradient descent (SGD)

1,995 words9 min readdifficulty · medium6 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHAT is SGD?

Three flavors, defined by batch size ∣B∣=m|\mathcal{B}| = m:

  • m=Nm = N (all data) → Full-batch / Batch GD
  • m=1m = 1 → pure (online) SGD
  • 1<m<N1 < m < N → mini-batch SGD (what everyone actually uses)

WHY does averaging a random sample work? (Derivation from scratch)

The true objective is the average loss over the whole dataset of size NN: L(θ)=1N∑i=1Nℓi(θ),∇L(θ)=1N∑i=1N∇ℓi(θ).L(\theta) = \frac{1}{N}\sum_{i=1}^{N} \ell_i(\theta), \qquad \nabla L(\theta) = \frac{1}{N}\sum_{i=1}^{N} \nabla \ell_i(\theta).

Step — build an estimator. Pick a mini-batch B\mathcal{B} of mm examples uniformly at random. Define gB(θ)=1m∑i∈B∇ℓi(θ).g_{\mathcal{B}}(\theta) = \frac{1}{m}\sum_{i \in \mathcal{B}} \nabla \ell_i(\theta).

Why this step? We want a cheap stand-in for the expensive full gradient.

Step — show it is unbiased. For any single randomly chosen index ii, Ei[∇ℓi(θ)]=∑i=1N1N∇ℓi(θ)=∇L(θ).\mathbb{E}_i[\nabla \ell_i(\theta)] = \sum_{i=1}^N \frac{1}{N}\nabla \ell_i(\theta) = \nabla L(\theta). Averaging mm such i.i.d. draws keeps the mean: E[gB(θ)]=∇L(θ).\mathbb{E}[g_{\mathcal{B}}(\theta)] = \nabla L(\theta).

Why this step? Unbiasedness means "on average we point in the right (steepest-descent) direction." So in expectation, SGD does exactly what GD does.

Step — quantify the noise. The variance of the mini-batch estimator shrinks with mm: Var⁡[gB]=σ2m,\operatorname{Var}[g_{\mathcal{B}}] = \frac{\sigma^2}{m}, where σ2\sigma^2 is the per-example gradient variance.

Why this step? This is the central trade-off: bigger mm → less noise but more cost per step; smaller mm → cheap, noisy steps. The 1/m1/m (not 1/m21/m^2) means doubling the batch only halves the noise → diminishing returns, which is exactly why huge batches aren't automatically better.

Why Robbins–Monro? ∑ηt=∞\sum \eta_t = \infty → you can still travel any distance to reach the minimum. ∑ηt2<∞\sum \eta_t^2 < \infty → step sizes shrink fast enough that noise eventually averages out and you stop bouncing. A classic choice: ηt=η0/(1+kt)\eta_t = \eta_0/(1+kt).

Figure — Stochastic gradient descent (SGD)

HOW to run it (algorithm)

initialize θ
for epoch in 1..E:
    shuffle dataset            # why: keep draws ~ i.i.d., break ordering bias
    for each mini-batch B:
        g = (1/m) Σ_{i∈B} ∇ℓ_i(θ)
        θ = θ − η · g

One epoch = one full sweep through all NN examples = N/mN/m updates.

Worked Examples

Common Mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine finding the lowest point in a huge foggy valley by feeling the ground slope under your feet. Checking the slope using the whole valley at once is exhausting. Instead, you check just the little patch you're standing on and take a step downhill. Each patch is a bit misleading, so you wobble — but if you keep stepping and slowly take smaller steps, all the wobbles cancel out and you end up at the bottom. Checking a small patch is fast, so you take tons of steps and get there quicker. That wobble even helps you skip over little ditches that aren't the real bottom.

Flashcards

What does the "stochastic" in SGD refer to?
The gradient is estimated from a randomly sampled mini-batch, making each update a noisy random estimate of the true gradient.
Write the SGD update rule.
θt+1=θt−η ∇θLBt(θt)\theta_{t+1} = \theta_t - \eta\,\nabla_\theta L_{\mathcal{B}_t}(\theta_t)
Is the mini-batch gradient a biased estimator of the full gradient?
No — it is unbiased: E[gB]=∇L(θ)\mathbb{E}[g_{\mathcal{B}}] = \nabla L(\theta) (uniform random sampling).
How does mini-batch size mm affect gradient-estimate variance?
Variance scales as σ2/m\sigma^2/m; std-dev as σ/m\sigma/\sqrt{m} → diminishing returns for large mm.
State the Robbins–Monro conditions for convergence.
∑tηt=∞\sum_t \eta_t = \infty (can reach the min) and ∑tηt2<∞\sum_t \eta_t^2 < \infty (noise averages out).
Why can a constant learning rate prevent exact convergence?
Gradient noise never disappears, so parameters bounce in a ball of radius ∝η\propto \eta around the minimum.
What is one epoch in terms of updates?
N/mN/m updates — one full pass through all NN training examples in batches of size mm.
Why is SGD's noise sometimes beneficial?
It helps escape saddle points/sharp minima and acts as an implicit regularizer biasing toward flat, better-generalizing minima.
Why shuffle data each epoch?
To keep mini-batch draws approximately i.i.d. and avoid correlated/biased updates from ordered data.
What is the linear scaling rule?
When increasing batch size mm by factor kk, scale the learning rate η\eta by kk to keep training dynamics similar.

Connections

Concept Map

exact but slow

sampled estimate

samples

averages gradients

proven

scales as

drives

points right way

sets step size

converges under

noise helps

special case m equals N

Loss L theta over N examples

Full-batch GD exact gradient

Stochastic Gradient Descent

Random mini-batch B size m

Estimator g_B

Unbiased E of g_B equals grad L

Variance sigma^2 over m

Noise vs cost trade-off

Update rule theta minus eta g_B

Learning rate eta

Robbins-Monro conditions

Escapes bad regions

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, deep network train karna matlab ek loss function L(θ)L(\theta) ko minimize karna hai — yaani woh sabse neeche wala point dhoondhna jahan galtiyan sabse kam ho. Agar hum poore dataset (millions of examples) ka gradient nikaal ke ek step lein, toh woh bilkul accurate hoga, par bohot slow. SGD kehta hai: har step pe sirf ek chhota random mini-batch utha lo, usi se gradient estimate karo, aur step maar do. Yeh estimate thoda noisy hota hai, par sasta hota hai — toh hum thousands of steps le sakte hain few expensive steps ke jagah.

Sabse important baat: yeh noisy gradient unbiased hota hai, matlab average mein woh sahi (true) gradient ki taraf hi point karta hai — E[gB]=∇L\mathbb{E}[g_{\mathcal{B}}] = \nabla L. Iska variance σ2/m\sigma^2/m hota hai, yaani batch size mm badhao toh noise kam, par sirf 1/m1/\sqrt{m} ke rate se — isliye bahut bada batch lene ka faayda kam hota jaata hai. Yeh trade-off hi SGD ka dil hai.

Ek aur interesting cheez: yeh noise sirf tolerate karne wali problem nahi hai, balki helpful bhi hai. Deep networks mein bohot saare saddle points aur sharp minima hote hain jahan normal gradient descent atak sakta hai. SGD ka wobble usse dhakka de kar bahar nikaal deta hai, aur woh flat minima ki taraf le jaata hai jo generalize better karte hain (regularization jaisa effect).

Practical tips yaad rakho: har epoch pe data shuffle karo (taaki batches i.i.d. rahein), aur learning rate ko dheere-dheere kam karo (Robbins–Monro conditions: ∑ηt=∞\sum \eta_t = \infty, ∑ηt2<∞\sum \eta_t^2 < \infty), warna constant η\eta ke saath model minimum ke aas-paas bounce karta rahega, exactly settle nahi hoga. Mnemonic: Sample, Slope, Step, Shrink.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,367 wordsD2Visual walkthroughThe derivation in pictures · 1,719 wordsD3Worked examplesEvery scenario covered · 2,645 wordsD4ExercisesGraded, full solutions · 3,106 wordsD5Question bankConcept traps, quick reveals · 1,477 words

Test yourself — Training Deep Networks

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Gradient descent and variants — convergence analysisMaths · 4.10.20Learning rate schedulingAI-ML · 3.2.6Momentum and Nesterov momentumAI-ML · 3.2.3Adam and AdamW optimizersAI-ML · 3.2.5Backpropagation — chain rule, gradient computationCoding · 5.6.8Bias-variance tradeoffAI-ML · 2.6.1Gradient descent intuition and update ruleAI-ML · 1.2.12Law of large numbersAI-ML · 1.3.14Central limit theoremAI-ML · 1.3.15Cost function (MSE) and gradient descent fittingAI-ML · 2.2.4Mini-batch gradient descentAI-ML · 3.2.2Momentum and Nesterov momentumAI-ML · 3.2.3