Optimization — SGD, momentum, Adam — derivations

---

1. Gradient Descent — the ancestor

Derivation from first principles. Take a small step $\Delta\theta$. First-order Taylor: $L(\theta+\Delta\theta)\approx L(\theta)+\nabla L(\theta)^\top \Delta\theta.$ We want $L$ to decrease the most for a fixed step size $\|\Delta\theta\|=\eta$. The change is $\nabla L^\top \Delta\theta$; by Cauchy–Schwarz this is most negative when $\Delta\theta$ is anti-parallel to $\nabla L$:

\boxed{\theta_{t+1}=\theta_t-\eta\,\nabla L(\theta_t)}$$ (In practice we absorb the norm into $\eta$, giving the un-normalized rule.) > [!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:** each step reduces $L$ as long as $\eta$ is small enough that the linear > approximation holds. --- ## 2. Stochastic Gradient Descent (SGD) > [!intuition] WHAT changes > Full gradient over $N$ samples costs $O(N)$ per step. Instead, pick a **mini-batch** $B$ and use > $$\nabla L \approx g_t=\frac{1}{|B|}\sum_{i\in B}\nabla \ell_i(\theta_t).$$ > This is an ==unbiased estimate==: $\mathbb{E}[g_t]=\nabla L(\theta_t)$. **WHY unbiased.** If $B$ is sampled uniformly, $\mathbb{E}[\nabla\ell_i]=\frac1N\sum_j\nabla\ell_j =\nabla L$. So on average we still go downhill — but each step has **noise**. > [!formula] SGD update > $$\theta_{t+1}=\theta_t-\eta\,g_t$$ > **HOW noise helps/hurts:** noise lets us escape shallow local minima and saddle points, but it > also makes the path zig-zag; hence we often **decay** $\eta$ over time: $\eta_t=\eta_0/(1+kt)$. > [!mistake] Steel-man: "SGD is just a worse GD, always use full batch." > **Why it feels right:** full gradient is exact, so surely exact is better. > **The fix:** exact gradient is expensive *and* deterministic — it gets **stuck** at saddle points > (common in high-dim nets). SGD's variance is a feature: it perturbs you off saddles and gives many > more updates per second. Convergence-per-wall-clock beats convergence-per-step. --- ## 3. Momentum — remembering the past > [!intuition] WHY momentum > SGD in a **ravine** (steep in one direction, shallow in another) oscillates across the steep walls > and crawls along the shallow floor. We want to ==cancel oscillations and accelerate consistent > directions==. Idea: keep a running "velocity" like a ball rolling downhill. **Derivation.** Let velocity $v$ accumulate gradients with decay $\beta\in[0,1)$: $$v_t=\beta v_{t-1}+g_t,\qquad \theta_{t+1}=\theta_t-\eta v_t.$$ Unroll it (with $v_{-1}=0$): $$v_t=\sum_{k=0}^{t}\beta^{\,k} g_{t-k}.$$ This is an ==exponentially weighted sum== of past gradients. In directions where $g$ keeps the same sign, terms **add** → speed builds up; in oscillating directions signs alternate → they **cancel**. **Effective step size on a consistent slope.** If $g_t=g$ constant, the geometric series gives $v_\infty=\frac{g}{1-\beta}$, so the step is amplified by $\frac{1}{1-\beta}$. With $\beta=0.9$ that's a **10×** effective learning rate along steady directions. ![[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 > Different parameters may need different learning rates (some gradients are huge, some tiny — > think weights in early vs late aircraft-sensor-net layers). Adam combines **momentum** (1st moment) > with a **per-parameter scaling** by gradient magnitude (2nd moment), so every coordinate gets its > own adaptive step. **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])$$ Here $g_t^2$ is element-wise. **Step 2 — WHY bias correction.** With $m_0=0$, unrolling gives $m_t=(1-\beta_1)\sum_{k=0}^{t-1}\beta_1^{k} g_{t-k}$. If gradients are ~stationary with mean $g$, $$\mathbb{E}[m_t]=g\,(1-\beta_1)\sum_{k=0}^{t-1}\beta_1^k=g\,(1-\beta_1^t).$$ So $m_t$ is **biased toward zero** early on (factor $1-\beta_1^t<1$). We divide it out: $$\hat m_t=\frac{m_t}{1-\beta_1^{t}},\qquad \hat v_t=\frac{v_t}{1-\beta_2^{t}}.$$ Same argument for $v_t$. This is the ==bias-correction== that makes early steps sane. **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 the scaling helps:** dividing by $\sqrt{\hat v_t}$ makes the step roughly > $\pm\eta$ regardless of gradient scale — big-gradient params don't explode, tiny-gradient params > don't stall. It's like a per-coordinate ==signal-to-noise== normalization. > [!example] Why $\sqrt{\hat v_t}$ gives a signal-to-noise step > Suppose a coordinate has steady gradient $g$: then $\hat m_t\to g$, $\hat v_t\to g^2$, so the update > is $-\eta\,\frac{g}{|g|}=\mp\eta$ — a unit step in the right direction. > If the gradient is pure noise with mean 0: $\hat m_t\to 0$ but $\hat v_t\to \text{Var}$, so the step > $\to 0$. **Why this step?** Adam trusts consistent directions and ignores noisy ones — exactly what > we want. --- ## 5. Worked mini-example (one parameter) > [!example] SGD vs Momentum vs Adam for one step > Let $L(\theta)=\tfrac12\theta^2$, so $g=\theta$. Start $\theta_0=2$, $\eta=0.1$. > > **SGD:** $\theta_1=2-0.1\cdot 2=1.8$. *Why:* 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$. > *Why:* velocity accumulates → **bigger** 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$, so $\theta_1=1.9$. > *Why this step?* After bias correction Adam's first step $\approx \eta\cdot\text{sign}(g)$ — a clean > unit-scaled step, independent of the gradient magnitude. --- #flashcards/coding Why is the negative gradient the steepest-descent direction? ::: By Cauchy–Schwarz the linear change $\nabla L^\top\Delta\theta$ is most negative when $\Delta\theta \parallel -\nabla L$. What makes the SGD mini-batch gradient a valid substitute for the true gradient? ::: It is unbiased: $\mathbb{E}[g_t]=\nabla L(\theta_t)$ under uniform sampling. Why does momentum accelerate consistent directions by $1/(1-\beta)$? ::: Constant gradient gives geometric sum $v_\infty=g/(1-\beta)$; with $\beta=0.9$ that's 10×. Why does momentum damp oscillations? ::: In alternating-sign directions the exponentially weighted past gradients cancel. What two moments does Adam track? ::: 1st moment $m_t=\mathbb{E}[g]$ (momentum) and 2nd moment $v_t=\mathbb{E}[g^2]$ (magnitude). Why does Adam need bias correction? ::: With $m_0=v_0=0$, EMAs are biased toward 0 early: $\mathbb{E}[m_t]=g(1-\beta_1^t)$; divide by $1-\beta_1^t$. What does dividing by $\sqrt{\hat v_t}$ achieve? ::: A per-coordinate step of size ~$\eta$ regardless of gradient scale; noise-only directions get ~0 step. Steel-man: why full-batch GD can be worse than SGD? ::: It's expensive and deterministic — gets stuck at saddle points; SGD noise escapes them and gives more updates/sec. Adam default hyperparameters? ::: $\beta_1=0.9,\ \beta_2=0.999,\ \epsilon=10^{-8}$. --- > [!recall]- Feynman: explain to a 12-year-old > Imagine you're blindfolded on a hilly field and want the lowest point. > **SGD:** feel the slope under your feet and take a step downhill — but your feet are a bit wobbly, so > you zig-zag. **Momentum:** you're now a rolling ball — if you keep going the same way you speed up, > and if you keep bouncing side to side those bounces cancel out. **Adam:** you also *remember how bumpy > each direction has been* — in super-bumpy directions you take tiny careful steps, in smooth directions > you stride confidently. That's it — all three are just clever ways to decide **which way and how big** > to step. > [!mnemonic] > **"Slope, Speed, Smart."** — **S**GD follows the **slope**, **M**omentum builds **speed**, > **A**dam is **smart** (adapts each coordinate). > For Adam order: **"Moments, Bias, Step"** ($m,v \to$ correct $\to \hat m/\sqrt{\hat v}$). ## Connections - [[Gradient Descent]] — the ancestor rule all optimizers modify - [[Backpropagation]] — where the gradients $g_t$ actually come from - [[Learning Rate Scheduling]] — decaying $\eta_t$ for SGD convergence - [[Exponential Moving Average]] — the math behind momentum & Adam's moments - [[Saddle Points and Loss Landscapes]] — why noise/adaptivity matter - [[Surrogate Models for CFD]] — aerospace ML use-case with huge datasets → SGD/Adam essential - [[Taylor Expansion]] — first-principles basis of the descent step ## 🖼️ 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] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Socho tumhe ek hilly maidan me sabse neeche wale point tak jaana hai, par aankh band hai. Tum bas > pairon ke neeche ki **slope** feel kar sakte ho. **SGD** yahi karta hai — poora dataset dekhne ke > bajaye ek chhota mini-batch se gradient estimate karta hai (jo average me sahi hota hai, isliye > "unbiased"), aur uske ulti direction me chhota step leta hai. Fayda: fast aur saddle points se bach > jaata hai; nuksaan: raasta zig-zag karta hai. > > **Momentum** ka idea hai ek gend (ball) ki tarah rolling. Jis direction me gradient baar-baar same > sign ka aata hai, wahan velocity $v=\beta v+g$ me jama hoti jaati hai aur speed $1/(1-\beta)$ guna > badh jaati hai ($\beta=0.9$ pe 10x!). Jahan oscillation hai (alternate signs), wahan purane gradients > cancel ho jaate hain. Isliye ravine (ek taraf steep, doosri taraf flat) me momentum smooth aur fast > chalta hai. > > **Adam** sabse smart hai. Ye do cheezein yaad rakhta hai: pehla moment $m$ (momentum jaisa average > gradient) aur doosra moment $v$ (gradient ka square, yani magnitude). Fir har parameter ko uski apni > learning rate deta hai: step $=\eta\,\hat m/\sqrt{\hat v}$. Matlab jis direction me gradient bada hai > wahan chhota careful step, jahan chhota hai wahan bada step. Ek important trick hai **bias correction** > — shuru me $m,v$ zero se start hote hain to ve chhote (biased) aa jaate hain, isliye $1-\beta^t$ se > divide karke theek karte hain. Aerospace ML me (CFD surrogate, RUL prediction) data bahut bada hota > hai, isliye ye teeno optimizers practically zaroori hain. ![[audio/5.6.09-Optimization-—-SGD,-momentum,-Adam-—-derivations.mp3]]