Optimization — SGD, momentum, Adam — derivations

5.6.9 · Coding › Machine Learning (Aerospace Applications)

---

1. Gradient Descent — the ancestor

First principles se derivation. Ek chhota sa step $\Delta \theta$ lo. First-order Taylor: $L(\theta +\Delta \theta )\approx L(\theta )+\nabla L(\theta {)}^{\top }\Delta \theta .$ Hum chahte hain ki fixed step size $\Vert \Delta \theta \Vert =\eta$ ke liye $L$ sabse zyada decrease ho. Change hai $\nabla L^{\top }\Delta \theta$; Cauchy–Schwarz ke hisaab se yeh tab sabse zyada negative hoga jab $\Delta \theta$, $\nabla L$ ke anti-parallel ho:

\boxed{\theta_{t+1}=\theta_t-\eta\,\nabla L(\theta_t)}$$ (Practice mein hum norm ko $\eta$ mein absorb kar lete hain, jisse un-normalized rule milta hai.) > [!formula] Batch Gradient Descent > $$\theta_{t+1}=\theta_t-\eta\,\nabla L(\theta_t),\qquad \eta>0 \text{ is the learning rate}$$ > **WHY it works:** har step $L$ ko reduce karta hai jab tak $\eta$ itna chhota ho ki linear > approximation hold kare. --- ## 2. Stochastic Gradient Descent (SGD) > [!intuition] WHAT badalta hai > $N$ samples par full gradient ka cost $O(N)$ per step hai. Iske bajaye, ek **mini-batch** $B$ pick karo aur use karo > $$\nabla L \approx g_t=\frac{1}{|B|}\sum_{i\in B}\nabla \ell_i(\theta_t).$$ > Yeh ek ==unbiased estimate== hai: $\mathbb{E}[g_t]=\nabla L(\theta_t)$. **WHY unbiased.** Agar $B$ uniformly sample kiya gaya ho, toh $\mathbb{E}[\nabla\ell_i]=\frac1N\sum_j\nabla\ell_j =\nabla L$. Toh average par hum phir bhi downhill jaate hain — lekin har step mein **noise** hoti hai. > [!formula] SGD update > $$\theta_{t+1}=\theta_t-\eta\,g_t$$ > **HOW noise helps/hurts:** noise hume shallow local minima aur saddle points se escape karne deti hai, lekin yeh > path ko bhi zig-zag banati hai; isliye hum aksar $\eta$ ko time ke saath **decay** karte hain: $\eta_t=\eta_0/(1+kt)$. > [!mistake] Steel-man: "SGD sirf ek worse GD hai, always full batch use karo." > **Why it feels right:** full gradient exact hai, toh surely exact better hoga. > **The fix:** exact gradient expensive *bhi* hai aur deterministic bhi — yeh saddle points par **stuck** ho jaata hai > (high-dim nets mein common). SGD ki variance ek feature hai: yeh aapko saddles se perturb kar ke hatata hai aur > per second bahut zyada updates deta hai. Convergence-per-wall-clock, convergence-per-step ko beat karta hai. --- ## 3. Momentum — past ko yaad rakhna > [!intuition] WHY momentum > SGD ek **ravine** mein (ek direction mein steep, doosre mein shallow) steep walls ke across oscillate karta hai > aur shallow floor par crawl karta hai. Hum chahte hain ki ==oscillations cancel ho aur consistent directions > accelerate hon==. Idea: ek rolling ball ki tarah running "velocity" maintain karo. **Derivation.** Velocity $v$ ko decay $\beta\in[0,1)$ ke saath gradients accumulate karne do: $$v_t=\beta v_{t-1}+g_t,\qquad \theta_{t+1}=\theta_t-\eta v_t.$$ Isse unroll karo (with $v_{-1}=0$): $$v_t=\sum_{k=0}^{t}\beta^{\,k} g_{t-k}.$$ Yeh past gradients ka ==exponentially weighted sum== hai. Jin directions mein $g$ ka sign same rehta hai, terms **add** hoti hain → speed badhti hai; oscillating directions mein signs alternate hote hain → woh **cancel** ho jaate hain. **Consistent slope par effective step size.** Agar $g_t=g$ constant ho, toh geometric series deta hai $v_\infty=\frac{g}{1-\beta}$, toh step $\frac{1}{1-\beta}$ se amplify ho jaata hai. $\beta=0.9$ ke saath yeh steady directions mein **10×** effective learning rate hai. ![[5.6.09-Optimization-—-SGD,-momentum,-Adam-—-derivations.png]] > [!formula] SGD with Momentum > $$v_t=\beta v_{t-1}+g_t,\qquad \theta_{t+1}=\theta_t-\eta\, v_t,\quad \beta\approx0.9$$ --- ## 4. Adam — Adaptive Moment Estimation > [!intuition] WHY Adam > Alag-alag parameters ko alag-alag learning rates ki zaroorat ho sakti hai (kuch gradients bahut bade hote hain, kuch tiny — > socho early vs late aircraft-sensor-net layers mein weights). Adam **momentum** (1st moment) ko gradient magnitude se > **per-parameter scaling** (2nd moment) ke saath combine karta hai, taaki har coordinate apna adaptive step le sake. **Step 1 — moments (exponential moving averages).** $$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t \quad(\text{estimate of }\mathbb{E}[g])$$ $$v_t=\beta_2 v_{t-1}+(1-\beta_2)g_t^2 \quad(\text{estimate of }\mathbb{E}[g^2])$$ Yahan $g_t^2$ element-wise hai. **Step 2 — WHY bias correction.** $m_0=0$ ke saath, unrolling deta hai $m_t=(1-\beta_1)\sum_{k=0}^{t-1}\beta_1^{k} g_{t-k}$. Agar gradients ~stationary hain mean $g$ ke saath, toh $$\mathbb{E}[m_t]=g\,(1-\beta_1)\sum_{k=0}^{t-1}\beta_1^k=g\,(1-\beta_1^t).$$ Toh $m_t$ initially **zero ki taraf biased** hota hai (factor $1-\beta_1^t<1$). Hum isse divide kar lete hain: $$\hat m_t=\frac{m_t}{1-\beta_1^{t}},\qquad \hat v_t=\frac{v_t}{1-\beta_2^{t}}.$$ $v_t$ ke liye bhi same argument. Yahi ==bias-correction== hai jo early steps ko sane banata hai. **Step 3 — the update.** $$\boxed{\theta_{t+1}=\theta_t-\eta\,\frac{\hat m_t}{\sqrt{\hat v_t}+\epsilon}}$$ > [!formula] Adam (full) > $$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t,\quad v_t=\beta_2 v_{t-1}+(1-\beta_2)g_t^2$$ > $$\hat m_t=\frac{m_t}{1-\beta_1^t},\quad \hat v_t=\frac{v_t}{1-\beta_2^t},\quad > \theta_{t+1}=\theta_t-\eta\frac{\hat m_t}{\sqrt{\hat v_t}+\epsilon}$$ > Defaults: $\beta_1=0.9,\ \beta_2=0.999,\ \epsilon=10^{-8}$. > **HOW scaling help karta hai:** $\sqrt{\hat v_t}$ se divide karne par step roughly > $\pm\eta$ rehta hai gradient scale se independent — big-gradient params explode nahi karte, tiny-gradient params > stall nahi karte. Yeh ek per-coordinate ==signal-to-noise== normalization jaisa hai. > [!example] $\sqrt{\hat v_t}$ kyun signal-to-noise step deta hai > Suppose karo ek coordinate mein steady gradient $g$ hai: toh $\hat m_t\to g$, $\hat v_t\to g^2$, toh update > hai $-\eta\,\frac{g}{|g|}=\mp\eta$ — sahi direction mein ek unit step. > Agar gradient pure noise hai mean 0 ke saath: $\hat m_t\to 0$ lekin $\hat v_t\to \text{Var}$, toh step > $\to 0$. **Yeh step kyun?** Adam consistent directions par trust karta hai aur noisy ones ko ignore — exactly wohi jo > hum chahte hain. --- ## 5. Worked mini-example (one parameter) > [!example] SGD vs Momentum vs Adam for one step > Lo $L(\theta)=\tfrac12\theta^2$, toh $g=\theta$. Start $\theta_0=2$, $\eta=0.1$. > > **SGD:** $\theta_1=2-0.1\cdot 2=1.8$. *Kyun:* plain gradient step. > > **Momentum** ($\beta=0.9$, $v_{-1}=0$): $v_0=0.9\cdot0+2=2$, $\theta_1=2-0.1\cdot2=1.8$. > Next step $g_1=1.8$: $v_1=0.9\cdot2+1.8=3.6$, $\theta_2=1.8-0.1\cdot3.6=1.44$. > *Kyun:* velocity accumulate hoti hai → **bada** second step (1.8→1.44 vs SGD 1.8→1.62). > > **Adam** ($\beta_1=0.9,\beta_2=0.999$): $m_0=0.1\cdot2=0.2$, $\hat m_0=0.2/(1-0.9)=2$; > $v_0=0.001\cdot4=0.004$, $\hat v_0=0.004/(1-0.999)=4$; $\hat v_0^{1/2}=2$. > Step $=0.1\cdot 2/2=0.1$, toh $\theta_1=1.9$. > *Yeh step kyun?* Bias correction ke baad Adam ka pehla step $\approx \eta\cdot\text{sign}(g)$ hota hai — ek clean > unit-scaled step, gradient magnitude se independent. --- #flashcards/coding Negative gradient steepest-descent direction kyun hai? ::: Cauchy–Schwarz ke hisaab se linear change $\nabla L^\top\Delta\theta$ tab sabse zyada negative hota hai jab $\Delta\theta \parallel -\nabla L$. SGD mini-batch gradient true gradient ka valid substitute kyun hai? ::: Yeh unbiased hai: uniform sampling ke under $\mathbb{E}[g_t]=\nabla L(\theta_t)$. Momentum consistent directions ko $1/(1-\beta)$ se kyun accelerate karta hai? ::: Constant gradient geometric sum deta hai $v_\infty=g/(1-\beta)$; $\beta=0.9$ ke saath yeh 10× hai. Momentum oscillations ko kyun damp karta hai? ::: Alternating-sign directions mein exponentially weighted past gradients cancel ho jaate hain. Adam kaun se do moments track karta hai? ::: 1st moment $m_t=\mathbb{E}[g]$ (momentum) aur 2nd moment $v_t=\mathbb{E}[g^2]$ (magnitude). Adam ko bias correction ki zaroorat kyun hai? ::: $m_0=v_0=0$ ke saath, EMAs early mein 0 ki taraf biased hote hain: $\mathbb{E}[m_t]=g(1-\beta_1^t)$; $1-\beta_1^t$ se divide karo. $\sqrt{\hat v_t}$ se divide karna kya achieve karta hai? ::: Har coordinate mein $\sim\eta$ size ka step milta hai gradient scale se independent; noise-only directions mein $\sim 0$ step milta hai. Steel-man: full-batch GD SGD se worse kyun ho sakta hai? ::: Yeh expensive aur deterministic hai — saddle points par stuck ho jaata hai; SGD noise unhe escape karta hai aur zyada updates/sec deta hai. Adam ke default hyperparameters kya hain? ::: $\beta_1=0.9,\ \beta_2=0.999,\ \epsilon=10^{-8}$. --- > [!recall]- Feynman: ek 12-saal ke bacche ko explain karo > Socho tum ek hilly field mein aankhon par patti baandh ke sabse neeche ka point dhundh rahe ho. > **SGD:** apne pairon ke neeche slope feel karo aur downhill step lo — lekin tere pair thode wobbly hain, toh > tum zig-zag karte ho. **Momentum:** ab tum ek rolling ball ho — agar tum usi direction mein jaate raho toh speed badhti hai, > aur agar tum side-to-side bounce karte raho toh woh bounces cancel ho jaate hain. **Adam:** tum yeh bhi *yaad rakhte ho ki > har direction kitni bumpy rahi hai* — super-bumpy directions mein tum tiny careful steps lete ho, smooth directions mein > tum confidently stride karte ho. Bas yahi hai — teeno sirf decide karne ke clever tarike hain ki **kis direction mein aur > kitna bada** step lena hai. > [!mnemonic] > **"Slope, Speed, Smart."** — **S**GD **slope** follow karta hai, **M**omentum **speed** build karta hai, > **A**dam **smart** hai (har coordinate ko adapt karta hai). > Adam ki order ke liye: **"Moments, Bias, Step"** ($m,v \to$ correct $\to \hat m/\sqrt{\hat v}$). ## Connections - [[Gradient Descent]] — woh ancestor rule jise sab optimizers modify karte hain - [[Backpropagation]] — yahan se gradients $g_t$ actually aate hain - [[Learning Rate Scheduling]] — SGD convergence ke liye $\eta_t$ decay karna - [[Exponential Moving Average]] — momentum aur Adam ke moments ke peeche ka math - [[Saddle Points and Loss Landscapes]] — kyun noise/adaptivity matter karti hai - [[Surrogate Models for CFD]] — aerospace ML use-case jisme huge datasets hain → SGD/Adam essential - [[Taylor Expansion]] — descent step ka first-principles basis ## 🖼️ Concept Map ```mermaid flowchart TD L[Minimize loss L theta] -->|solve grad L = 0 infeasible| GD[Gradient Descent] Taylor[First-order Taylor + Cauchy-Schwarz] -->|derives| GD GD -->|step anti-parallel to grad| Rule[theta = theta - eta grad L] Rule -->|full batch costs O of N| SGD[Stochastic Gradient Descent] Batch[Mini-batch estimate g_t] -->|unbiased of grad L| SGD SGD -->|adds noise| Noise[Gradient noise] Noise -->|escapes saddles and minima| Benefit[Faster per wall-clock] Noise -->|causes zig-zag| Decay[Decay learning rate eta_t] Ravine[Ravine geometry] -->|motivates| Momentum[Momentum] SGD -->|remembers past gradients| Momentum Momentum -->|adaptive rates extend to| Adam[Adam] ```