Optimization — SGD, momentum, Adam — derivations: Exercises

5.6.9 · D4 · Coding › Machine Learning (Aerospace Applications) › Optimization — SGD, momentum, Adam — derivations

Poore note mein symbols ka wahi matlab hai jo parent note ne define kiya hai. Ek naming warning pehle se: is chapter mein letter $v$ do alag cheezein ke liye use hota hai, aur unhe mix karna confusion ka #1 source hai — isliye hum yahan dono ko apna alag naam dete hain aur kabhi bhi bare $v_{t}$ nahi likhenge.

Definition Symbol dictionary (pehle samjho, phir use karo)

$θ$ — woh parameter jise hum tune karte hain. Ek bead ko wire par socho; uski position $θ$ hai.
$L (θ)$ — loss, position $θ$ ke upar hill ki height. Hum valley chahte hain.
$g_{t} = \nabla L (θ_{t})$ — step $t$ par gradient: ek arrow jo upar hill ki taraf point karta hai. Hum doosri taraf chalte hain.
$η$ — learning rate: kitna lamba stride lete hain (ek positive number).
$u_{t}$ — momentum velocity (parent note mein yeh $v_{t}$ tha; hum ise yahan $u_{t}$ rename karte hain taaki Adam ke second moment se kabhi confuse na ho). Yeh past gradients ki running memory hai: $u_{t} = β u_{t - 1} + g_{t}$ .
$β$ — momentum decay rate ( $[0, 1)$ mein ek number): har step mein kitna fraction purani velocity rakha jaata hai. Bada $β$ = lambi memory. Typical $β = 0.9$ .
$m_{t}$ — Adam ka first moment: gradient $g_{t}$ ka ek average.
$s_{t}$ — Adam ka second moment (parent note mein ise $v_{t}$ kaha tha; hum ise $s_{t}$ rename karte hain taaki momentum ki velocity se clash na ho). Yeh gradient squared, $g_{t}^{2}$ , ka average hai.
$β_{1}$ — Adam ka decay rate first moment $m_{t}$ ke liye (typical $0.9$ ).
$β_{2}$ — Adam ka decay rate second moment $s_{t}$ ke liye (typical $0.999$ , matlab bahut lambi memory).
$ϵ$ — ek tiny positive safety constant (typical $1 0^{- 8}$ ) jo square root ke andar add hota hai taaki hum kabhi zero se divide na karein.
$\overset{m}{^}_{t}, \overset{s}{^}_{t}$ — bias-corrected first aur second moments, rescale kiye gaye taaki early steps shrink na hon.

Level 1 — Recognition

L1.1 Kaunsi direction?

Aap $θ$ par khade ho aur gradient $g = + 3$ hai (loss upar jaata hai jab $θ$ badhta hai). $η = 0.1$ ke saath, kya plain gradient descent $θ$ ko left (chhota) ya right (bada) move karega, aur $θ_{0} = 5$ se kaunsi value par jaayega?

Recall Solution

WHAT: update hai $θ_{1} = θ_{0} - η g$ . WHY: $- g$ downhill point karta hai; positive $g$ matlab uphill right ki taraf hai, toh hum left step karte hain. $θ_{1} = 5 - 0.1 \cdot 3 = 4.7.$ Left move karta hai (chhota), $θ_{1} = 4.7$ tak. ✔

L1.2 Term ka naam batao

$θ_{t + 1} = θ_{t} - η u_{t}$ mein jahan $u_{t} = β u_{t - 1} + g_{t}$ , $β$ ko kya kaha jaata hai aur $β = 0$ se kya collapse hota hai?

Recall Solution

$β$ ko momentum coefficient (ek decay/memory factor) kehte hain. $β = 0$ ke saath: $u_{t} = 0 \cdot u_{t - 1} + g_{t} = g_{t} \Rightarrow θ_{t + 1} = θ_{t} - η g_{t},$ jo plain SGD hai. Toh bina memory ke momentum hai hi SGD. ✔

Level 2 — Application

L2.1 Quadratic par ek SGD step

$L (θ) = \frac{1}{2} θ^{2}$ , toh $g = θ$ . $θ_{0} = 2$ , $η = 0.1$ se $θ_{1}$ aur $θ_{2}$ calculate karo.

Recall Solution

WHAT: $θ_{t + 1} = θ_{t} - η g_{t}$ apply karo jahan $g_{t} = θ_{t}$ . WHY $g = θ$ : $L = \frac{1}{2} θ^{2}$ differentiate karne par $\frac{d L}{d θ} = θ$ milta hai — position $θ$ par parabola ka slope exactly $θ$ hai, toh gradient literally wahi hai jahan aap khade ho. $g_{0} = θ_{0} = 2$ : $θ_{1} = 2 - 0.1 \cdot 2 = 1.8$ . WHY exactly $0.9 \times$ shrink hua: $g_{t} = θ_{t}$ substitute karne par rule banta hai $θ_{t + 1} = θ_{t} - η θ_{t} = (1 - η) θ_{t}$ — har step $θ$ ko same factor se scale karta hai. $g_{1} = θ_{1} = 1.8$ : $θ_{2} = 1.8 - 0.1 \cdot 1.8 = 1.62$ . Toh $θ_{t} = 2 \cdot 0. 9^{t}$ — $θ = 0$ ki valley ki taraf ek clean geometric decay. ✔

L2.2 Do momentum steps

Same $L$ , $θ_{0} = 2$ , $η = 0.1$ , $β = 0.9$ , $u_{- 1} = 0$ . $θ_{1}$ aur $θ_{2}$ compute karo, aur $θ_{2}$ ko SGD ke $1.62$ se compare karo.

Recall Solution

WHAT: $u_{t} = β u_{t - 1} + g_{t}$ chalao phir $θ_{t + 1} = θ_{t} - η u_{t}$ . Step 0: $g_{0} = 2$ , $u_{0} = 0.9 \cdot 0 + 2 = 2$ , $θ_{1} = 2 - 0.1 \cdot 2 = 1.8$ . WHY step 0 SGD se match karta hai: $u_{- 1} = 0$ ke saath koi stored velocity nahi hai, toh pehli velocity $u_{0}$ bas $g_{0}$ hai — momentum ke paas pehli move mein kuch extra add karne ko nahi hai. Step 1: $g_{1} = 1.8$ , $u_{1} = 0.9 \cdot 2 + 1.8 = 3.6$ , $θ_{2} = 1.8 - 0.1 \cdot 3.6 = 1.44$ . WHY step 1 aage nikal jaata hai: $u_{1}$ purani velocity ka $0.9 \times$ ( $= 1.8$ ) aur fresh gradient ( $1.8$ ) add karta hai, toh velocity $3.6$ raw gradient se almost double hai — ball consistent downhill direction mein speed pakad chuka hai. Momentum $1.44$ pahuncha vs SGD ka $1.62$ — faster, kyunki $u_{1}$ ne pehla gradient accumulate kiya. ✔

L2.3 Ek Adam step

Same $L$ , $θ_{0} = 2$ , $η = 0.1$ , $β_{1} = 0.9, β_{2} = 0.999, ϵ = 1 0^{- 8}$ . $θ_{1}$ compute karo.

Recall Solution

WHAT: do moments compute karo, bias-correct karo, phir step lo. $g_{0} = 2$ . $m_{0} = (1 - 0.9) \cdot 2 = 0.2$ , bias-correct: $\overset{m}{^}_{0} = \frac{0.2}{1 - 0.9} = 2$ . WHY correction: $m_{0}$ $0$ se shuru hota hai, toh ek single update sirf $(1 - β_{1}) g = 0.2$ tak pahunchta hai — true gradient $2$ ka ek shrunken version. $1 - β_{1} = 0.1$ se divide karne par woh exact shrink undo hota hai aur honest estimate $\overset{m}{^}_{0} = 2$ milta hai. $s_{0} = (1 - 0.999) \cdot 2^{2} = 0.004$ , bias-correct: $\overset{s}{^}_{0} = \frac{0.004}{1 - 0.999} = 4$ , toh $\overset{s}{^}_{0} = 2$ . WHY $\overset{s}{^}_{0}$ se divide karte hain: $\overset{s}{^}_{0} = 4$ estimates karta hai $g^{2}$ ko, toh $\overset{s}{^}_{0} = 2 = ∣ g ∣$ — isse divide karne par gradient ka size cancel ho jaata hai, sirf uska sign bachta hai. $θ_{1} = 2 - 0.1 \cdot \frac{2}{2 + 1 0 ^{- 8}} \approx 2 - 0.1 = 1.9.$ Adam ka pehla step $\approx η \cdot sign (g) = 0.1$ hai — magnitude-independent. ✔

Neeche wali figure padhna. Horizontal axis parameter $θ$ hai, vertical axis loss $L = \frac{1}{2} θ^{2}$ hai (woh pale chalk parabola). Teeno optimizers $θ_{0} = 2$ se start karte hain (top right). Teen coloured dotted-with-dots tracks successive positions dikhate hain: blue = SGD, pink = Momentum, yellow = Adam. Har track ko true parabola se thoda upar draw kiya gaya hai taaki aap inhe alag kar sako — vertical offset sirf cosmetic hai, real $θ$ ke liye horizontal position padho. Takeaway: dekho pink Momentum dots kaise aage pull karte hain (har step mein zyada left land karte hain) jabki blue SGD peeche rehta hai, aur yellow Adam deliberately ek modest, evenly-scaled pehla stride leta hai — teeno L2 answers visual form mein.

Figure — Optimization — SGD, momentum, Adam — derivations

Level 3 — Analysis

L3.1 $1/ (1 - β)$ amplification

Steady slope par gradient constant $g$ hai. Dikhao ki momentum velocity $u_{\infty} = \frac{g}{1 - β}$ tak converge karti hai aur $β = 0.9$ ke liye evaluate karo.

Recall Solution

WHAT: $u_{t} = β u_{t - 1} + g$ ko $u_{- 1} = 0$ se unroll karo: $u_{t} = \sum_{k = 0}^{t} β^{k} g = g \frac{1 - β ^{t + 1}}{1 - β} .$ WHY woh sum: har step purani velocity ka $β$ -fraction rakhta hai aur fresh $g$ add karta hai — ek geometric series (dekho Exponential Moving Average). $t \to \infty$ ke saath, $β^{t + 1} \to 0$ (kyunki $0 \leq β < 1$ ), toh $u_{\infty} = \frac{g}{1 - β}$ . $β = 0.9$ ke liye: $u_{\infty} = \frac{g}{0.1} = 10 g$ — steady directions par 10× effective learning rate. ✔

L3.2 Oscillation cancellation

Maano ek coordinate ka gradient alternate karta hai: $g_{t} = (- 1)^{t} a$ (steep ravine wall bouncing). $β = 0.9$ , $a = 1$ , $u_{- 1} = 0$ ke saath $u_{1}, u_{2}, u_{3}$ compute karo, aur explain karo ki same-sign case ki tulna mein running velocity ka kya hota hai.

Recall Solution

$g_{0} = + 1, g_{1} = - 1, g_{2} = + 1, g_{3} = - 1$ . $u_{0} = 0.9 \cdot 0 + 1 = 1.0$ $u_{1} = 0.9 \cdot 1.0 - 1 = - 0.1$ $u_{2} = 0.9 \cdot (- 0.1) + 1 = 0.91$ $u_{3} = 0.9 \cdot 0.91 - 1 = - 0.181$ Pehle entry $u_{0} = 1.0$ ke baad, velocity magnitude chhoti rehti hai ( $u_{1}$ se yeh approximately $\pm 0.1$ aur $\pm 0.91$ ke beech bounce karti hai) kyunki opposite-sign gradients baar baar cancel ho jaate hain. Same-sign case mein yeh badhkar $u_{\infty} = 10$ ki taraf jaati. Yahi hai kaise momentum oscillations ko damp karta hai aur consistent directions mein accelerate karta hai. ✔

L3.3 Kyun SGD saddle se escape karta hai

Saddle point par $\nabla L = 0$ , toh full-batch GD ka update $θ - η \cdot 0 = θ$ hai — woh kabhi move nahi karta. $E [g_{t}] = \nabla L$ use karke explain karo ki SGD mini-batch step generally kyun move karta hai.

Recall Solution

Mini-batch gradient $g_{t}$ unbiased hai: saddle par $E [g_{t}] = \nabla L (θ_{t}) = 0$ . Lekin unbiased ka matlab sirf average zero hai — actual $g_{t}$ mein nonzero variance hoti hai, toh ek typical draw mein $g_{t} \neq = 0$ hoga. Woh random kick $θ$ ko saddle se kisi direction mein push karta hai; agar woh downhill escape direction par land kare (saddle par hamesha ek hoti hai) toh loss drop ho jaata hai. Dekho Saddle Points and Loss Landscapes. Isliye SGD ka noise ek feature hai, bug nahi. ✔

Level 4 — Synthesis

L4.1 Adam ki bias correction derive karo

$m_{0} = 0$ aur mean $g$ ke stationary gradients ke saath, dikhao ki $E [m_{t}] = g (1 - β_{1}^{t})$ aur isliye hum $(1 - β_{1}^{t})$ se kyun divide karte hain.

Recall Solution

WHAT: $m_{t} = β_{1} m_{t - 1} + (1 - β_{1}) g_{t}$ ko $m_{0} = 0$ se unroll karo: $m_{t} = (1 - β_{1}) \sum_{k = 0}^{t - 1} β_{1}^{k} g_{t - k} .$ WHY: har naya gradient $(1 - β_{1})$ weight ke saath aata hai aur purane $β_{1}$ se decay karte hain. $E [g_{t - k}] = g$ ke saath expectation lo:

=(1-\beta_1)\,g\cdot\frac{1-\beta_1^{t}}{1-\beta_1}=g\,(1-\beta_1^{t}).$$ Kyunki chhote $t$ ke liye $1-\beta_1^{t}<1$ hai, raw $m_t$ $g$ ko **underestimate** karta hai (0 ki taraf biased). Divide karne par: $$\hat m_t=\frac{m_t}{1-\beta_1^{t}} \;\Rightarrow\; \mathbb{E}[\hat m_t]=g.$$ Same algebra $\hat s_t=s_t/(1-\beta_2^{t})$ deta hai. ✔

L4.2 Bias-correction shrink factor

$β_{1} = 0.9$ ke liye bias correction pehle-step first moment ko kitna inflate karta hai (matlab factor $1/ (1 - β_{1}^{1})$ )? Aur $t = 1$ par $β_{2} = 0.999$ ke saath second moment ke liye?

Recall Solution

First moment, $t = 1$ : $\frac{1}{1 - 0. 9 ^{1}} = \frac{1}{0.1} = 10$ . Second moment, $t = 1$ : $\frac{1}{1 - 0.99 9 ^{1}} = \frac{1}{0.001} = 1000$ . Yeh exactly wahi inflations hain jo humne L2.3 mein use kiye: $m_{0} = 0.2 \to \overset{m}{^}_{0} = 2$ ( $\times 10$ ) aur $s_{0} = 0.004 \to \overset{s}{^}_{0} = 4$ ( $\times 1000$ ). ✔

Neeche wali figure padhna. Horizontal axis step counter $t$ hai; vertical axis (log scale par, toh equal spacing equal multiplying factor matlab hai) bias correction ka inflation factor $1/ (1 - β^{t})$ hai. Pink first-moment factor $1/ (1 - 0. 9^{t})$ hai; blue second-moment factor $1/ (1 - 0.99 9^{t})$ hai. Yellow dashed line at 1 matlab "koi correction ki zaroorat nahi." Takeaway: $t = 1$ par pink factor $10 \times$ hai aur blue ek bada $1000 \times$ — wildly different — lekin dono curves yellow line ki taraf slide karte hain jab $t$ badhta hai, toh correction training shuru hone ke baad quietly khud ko switch off kar leta hai. Isliye ise skip karna sirf pehle kuch steps ko hurt karta hai.

L4.3 Noise-only coordinate par Adam

Ek coordinate zero-mean noise receive karta hai: gradients $g_{t}$ jahan $E [g_{t}] = 0$ , $E [g_{t}^{2}] = σ^{2} > 0$ . Argue karo ki long-run Adam step $\to 0$ jaata hai, aur steady-gradient coordinate se contrast karo jahan step $\to η$ jaata hai.

Recall Solution

Noise case: $\overset{m}{^}_{t} \to E [g] = 0$ lekin $\overset{s}{^}_{t} \to E [g^{2}] = σ^{2} > 0$ . $step = η \frac{m ^ _{t}}{s ^ _{t} + ϵ} \to η \frac{0}{σ} = 0.$ Steady case ( $g_{t} = g$ ): $\overset{m}{^}_{t} \to g$ , $\overset{s}{^}_{t} \to g^{2}$ , toh $step \to η \frac{g}{∣ g ∣} = η sign (g) .$ Adam consistent directions par trust karta hai (unit step) aur pure noise ko ignore karta hai (zero step) — ek per-coordinate signal-to-noise filter. ✔

Level 5 — Mastery

L5.1 One-step descent guarantee

First-order Taylor Expansion $L (θ - η g) \approx L (θ) - η g^{⊤} g$ use karke jahan $g = \nabla L (θ)$ , dikhao ki loss strictly decrease hota hai (first order tak) jab bhi $g \neq = 0$ aur $η > 0$ . Guarantee kya tod deta hai?

Recall Solution

WHAT: GD update $Δ θ = - η g$ ko Taylor expansion mein substitute karo: $L (θ - η g) \approx L (θ) - η g^{⊤} g = L (θ) - η ∥ g ∥^{2} .$ Yahan $g^{⊤} g = ∥ g ∥^{2}$ ek vector ki squared length ki definition hai (ek identity, Cauchy–Schwarz inequality nahi — steepest-descent direction ne Cauchy–Schwarz parent note mein wahan use kiya tha; yeh step ek plain dot-product-with-itself hai). WHY decrease hota hai: $∥ g ∥^{2} \geq 0$ aur $0$ tabhi hota hai jab $g = 0$ . $g \neq = 0, η > 0$ ke saath, change $- η ∥ g ∥^{2} < 0$ hai, toh $L$ drop karta hai. Kya tod deta hai guarantee: approximation sirf first-order hai; agar $η$ bada ho toh ignored second-order (curvature) term dominate kar sakta hai aur $L$ badh sakta hai — L1/L3 traps ka overshoot. ✔

L5.2 Quadratic par convergence rate

$L = \frac{1}{2} θ^{2}$ ke liye (toh $g = θ$ ), SGD map hai $θ_{t + 1} = (1 - η) θ_{t}$ . Kis $η$ ke liye $θ_{t} \to 0$ hoga, aur kaunsa $η$ fastest convergence deta hai? Saare cases cover karo including $η = 1$ , $η = 2$ , aur non-positive $η \leq 0$ .

Recall Solution

WHAT: linear map ko closed form mein iterate karo. Kyunki har step constant $r = 1 - η$ se multiply karta hai, $t$ steps ke baad $θ_{t} = (1 - η)^{t} θ_{0} = r^{t} θ_{0} .$ WHY multiplier $r$ sab decide karta hai: $r^{t} θ_{0} \to 0$ exactly tab hoga jab $r^{t}$ powers shrink honge, matlab jab $∣ r ∣ < 1$ ho. Solve karo $∣1 - η ∣ < 1$ : $- 1 < 1 - η < 1 ⟹ 0 < η < 2.$ Ab multiplier $r = 1 - η$ ka har case walk karo:

$η \leq 0$ (non-positive rate): $r = 1 - η \geq 1$ , toh $∣ r ∣ \geq 1$ aur $∣ θ_{t} ∣$ kabhi nahi shrinks. Actually $η < 0$ $+ g$ (uphill) direction mein step karta hai — pure gradient ascent, loss badhta hai. $η = 0$ se $r = 1$ milta hai: $θ_{t} = θ_{0}$ hamesha ke liye frozen. Toh $η > 0$ mandatory hai.
$0 < η < 1$ : $0 < r < 1$ — smooth monotone shrink $0$ ki taraf (hamara L2.1 case, $r = 0.9$ ).
$η = 1$ : $r = 0$ , toh $θ_{1} = 0 \cdot θ_{0} = 0$ — one-step convergence, possible fastest.
$1 < η < 2$ : $- 1 < r < 0$ — converge phir bhi karta hai, lekin $θ_{t}$ har step sign alternate karta hai (oscillating shrink).
$η = 2$ : $r = - 1$ , toh $θ_{t} = (- 1)^{t} θ_{0}$ — hamesha bounce karta hai, magnitude kabhi nahi shrinks (marginal, no convergence).
$η > 2$ : $∣ r ∣ > 1$ — diverge karta hai, $∣ θ_{t} ∣$ bina bound ke badhta hai.

Summary: converges $⟺ 0 < η < 2$ ; fastest at $η = 1$ ; frozen at $η = 0$ ; $η < 0$ ke liye ascent; marginal bounce at $η = 2$ ; $η > 2$ ke liye diverges. ✔

L5.3 Synthesize: optimizer chunno

Ek aerospace CFD surrogate net mein hai (a) noisy mini-batch gradient, (b) ek deep ravine loss valley, aur (c) layers jinke gradient magnitudes $\sim 1 0^{3}$ se differ karte hain. Kaunsa single optimizer teeno address karta hai aur har ek ka mechanism kya hai?

Recall Solution

Adam. Mechanism-by-mechanism:

(a) Noise → first moment $\overset{m}{^}_{t}$ (gradients ka Exponential Moving Average) zero-mean noise average out karta hai, bilkul momentum ki tarah.
(b) Ravine → same momentum-like averaging consistent along-valley direction mein accelerate karta hai aur oscillating across-valley direction cancel karta hai (L3.2).
(c) $1 0^{3}$ scale mismatch → $\overset{s}{^}_{t}$ se divide karna har coordinate ko $\sim η$ step tak rescale karta hai, toh $1 0^{3}$ -bade gradients explode nahi karte aur tiny wale stall nahi karte (L4.3). Ek optimizer, teen mechanisms. Woh combination isliye hai ki Adam aise nets ke liye default hai. ✔

Recall Self-test checklist

$θ_{0} = 2, η = 0.1$ ke saath $\frac{1}{2} θ^{2}$ par one-step SGD ::: $θ_{1} = 1.8$ Momentum $θ_{2}$ (same setup, $β = 0.9$ ) ::: $1.44$ Adam $θ_{1}$ (same setup) ::: $1.9$ $β = 0.9$ ke liye Momentum steady-slope amplification ::: $10 \times$ Adam first-step second-moment inflation, $β_{2} = 0.999$ ::: $1000 \times$ SGD $\frac{1}{2} θ^{2}$ par kis $η$ ke liye converge karta hai? ::: $0 < η < 2$ , fastest at $η = 1$ ; $η \leq 0$ ya $η \geq 2$ ke liye diverges/ascends