Stochastic gradient descent (SGD) — Hinglish notes

3.2.1 · AI-ML › Training Deep Networks

WHAT is SGD?

Teen flavors, batch size $∣ B ∣ = m$ ke hisaab se:

$m = N$ (pura data) → Full-batch / Batch GD
$m = 1$ → pure (online) SGD
$1 < m < N$ → mini-batch SGD (yahi sab actually use karte hain)

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

Asli objective, size $N$ ki poori dataset par average loss hai: $L (θ) = \frac{1}{N} \sum_{i = 1}^{N} ℓ_{i} (θ), \nabla L (θ) = \frac{1}{N} \sum_{i = 1}^{N} \nabla ℓ_{i} (θ) .$

Step — ek estimator banao. $m$ examples ka ek mini-batch $B$ uniformly at random chuno. Define karo: $g_{B} (θ) = \frac{1}{m} \sum_{i \in B} \nabla ℓ_{i} (θ) .$

Yeh step kyun? Hum ek sasta substitute chahte hain expensive full gradient ke liye.

Step — dikhao ki yeh unbiased hai. Kisi bhi randomly chosen index $i$ ke liye, $E_{i} [\nabla ℓ_{i} (θ)] = \sum_{i = 1}^{N} \frac{1}{N} \nabla ℓ_{i} (θ) = \nabla L (θ) .$ $m$ aisi i.i.d. draws ka average karne par mean same rehta hai: $E [g_{B} (θ)] = \nabla L (θ) .$

Yeh step kyun? Unbiasedness ka matlab hai "average par hum sahi (steepest-descent) direction mein point karte hain." Toh expectation mein, SGD bilkul wahi karta hai jo GD karta hai.

Step — noise ko quantify karo. Mini-batch estimator ki variance $m$ ke saath shrink hoti hai: $Var [g_{B}] = \frac{σ ^{2}}{m},$ jahan $σ^{2}$ per-example gradient variance hai.

Yeh step kyun? Yeh central trade-off hai: bada $m$ → kam noise par har step mein zyada cost; chota $m$ → sasta, noisy steps. $1/ m$ (na ki $1/ m^{2}$ ) ka matlab hai batch double karne se noise sirf half hoti hai → diminishing returns, aur yahi reason hai ki huge batches automatically better nahi hote.

Robbins–Monro kyun? $\sum η_{t} = \infty$ → tum phir bhi koi bhi distance travel kar sakte ho minimum tak pahunchne ke liye. $\sum η_{t}^{2} < \infty$ → step sizes itni tezi se shrink hoti hain ki noise eventually average out ho jaati hai aur tum bouncing band kar dete ho. Ek classic choice: $η_{t} = η_{0} / (1 + k t)$ .

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

Ek epoch = saare $N$ examples ka ek full sweep = $N / m$ updates.

Worked Examples

Common Mistakes (Steel-manned)

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho tum ek bade foggy valley mein sabse neecha point dhundh rahe ho, sirf apne paon ke neeche ki zameen ki slope feel karke. Poori valley ki slope ek saath check karna bahut thaka dene wala hai. Iske bajaye, tum sirf woh chota sa patch check karte ho jahan tum khade ho aur neecha ek step lete ho. Har patch thoda misleading hota hai, toh tum wobble karte ho — par agar tum step karte rehte ho aur dhire dhire chote steps lete ho, toh saari wobbling cancel ho jaati hai aur tum bottom par pahunch jaate ho. Ek chota patch check karna fast hai, toh tum tons of steps lete ho aur wahan jaldi pahunchte ho. Woh wobble tumhe choti khaiyon ko skip karne mein bhi madad karta hai jo asli bottom nahi hai.

Flashcards

SGD mein "stochastic" ka kya matlab hai?

Gradient ek randomly sampled mini-batch se estimate hota hai, jo har update ko true gradient ka ek noisy random estimate banata hai.

SGD update rule likho.

θ_{t + 1} = θ_{t} - η \nabla_{θ} L_{B_{t}} (θ_{t})

Kya mini-batch gradient, full gradient ka biased estimator hai?

Nahi — yeh unbiased hai:

E [g_{B}] = \nabla L (θ)

(uniform random sampling).

Mini-batch size

m

gradient-estimate variance ko kaise affect karta hai?

Variance

σ^{2} / m

ke roop mein scale hoti hai; std-dev

σ / m

ke roop mein → bade

m

ke liye diminishing returns.

Convergence ke liye Robbins–Monro conditions batao.

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

(min tak pahunch sako) aur

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

(noise average out ho jaaye).

Constant learning rate exact convergence kyun rokti hai?

Gradient noise kabhi gayab nahi hoti, toh parameters minimum ke aas-paas

\propto η

radius ki ball mein bounce karte rehte hain.

Updates ke terms mein ek epoch kya hota hai?

N / m

updates — saare

N

training examples ka ek full pass, size

m

ke batches mein.

SGD ki noise kabhi kabhi beneficial kyun hoti hai?

Yeh saddle points/sharp minima se escape karne mein madad karta hai aur ek implicit regularizer ka kaam karta hai jo flat, better-generalizing minima ki taraf bias karta hai.

Har epoch data shuffle kyun karo?

Mini-batch draws ko approximately i.i.d. rakhne ke liye aur ordered data ki wajah se correlated/biased updates se bachne ke liye.

Linear scaling rule kya hai?

Jab batch size

m

ko factor

k

se badhao, toh training dynamics similar rakhne ke liye learning rate

η

ko bhi

k

se scale karo.

Connections

Gradient Descent — SGD iska stochastic mini-batch variant hai.
Learning Rate Schedules — decay SGD ko converge karaati hai (Robbins–Monro).
Momentum and Nesterov — SGD ke noisy path ko smooth karte hain.
Adam and Adaptive Optimizers — SGD par built per-parameter learning rates.
Batch Size and Generalization — flat vs sharp minima.
Backpropagation — har example ke liye $\nabla ℓ_{i}$ kaise compute hota hai.
Bias-Variance Tradeoff — $σ^{2} / m$ variance intuition.