15-10 — Gradient Descent and Modern Optimizers

Phase: Numerical Methods for ML | Subject: 15-10 Prerequisites: 15-01-floating-point-arithmetic.md, 15-04-backpropagation-implementation.md, 15-05-numerical-linear-algebra-ml.md, 04-03-derivatives.md, 04-08-optimization.md Next subject: 16-01-perceptron-model.md

Learning Objectives

By the end of this subject, you will be able to:

1. Derive and implement batch, stochastic, and mini-batch gradient descent algorithms
2. Analyze convergence rates for convex, strongly convex, and non-convex objectives
3. Design and justify learning rate schedules (step decay, cosine, warmup) for deep learning
4. Explain how momentum, Nesterov acceleration, and adaptive methods (RMSprop, Adam) improve convergence
5. Diagnose and mitigate common failure modes: vanishing/exploding gradients, poor conditioning, and saddle points

Core Content

Gradient Descent: The Fundamental Algorithm

For a differentiable objective $f(\mathbf{w})$, gradient descent iterates:

$$\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \nabla f(\mathbf{w}_t)$$

where $\alpha > 0$ is the learning rate (step size). The negative gradient $-\nabla f(\mathbf{w}_t)$ is the direction of steepest descent in the Euclidean norm.

⚠️ CRITICAL — The learning rate $\alpha$ is the single most important hyperparameter. Too large: divergence or oscillation. Too small: painfully slow convergence. The optimal fixed step size for a quadratic with Lipschitz gradient $L$ and strong convexity $\mu$ is $\alpha = 2/(L + \mu)$, but in practice $L$ and $\mu$ are unknown and the loss surface is non-quadratic.

Batch, Stochastic, and Mini-Batch GD

For empirical risk minimization with $N$ training examples:

$$f(\mathbf{w}) = \frac{1}{N}\sum_{i=1}^N \ell(\mathbf{w}; \mathbf{x}_i, y_i)$$

Batch Gradient Descent (BGD):

$$\mathbf{w}{t+1} = \mathbf{w}_t - \alpha \cdot \frac{1}{N}\sum{i=1}^N \nabla \ell(\mathbf{w}_t; \mathbf{x}_i, y_i)$$

• Uses the full dataset per step → exact gradient
• Cost per iteration: $O(N)$
• Deterministic convergence; guaranteed for convex $f$ with appropriate $\alpha$
• Impractical for large $N$ (e.g., ImageNet: $N = 1.28 \times 10^6$)

Stochastic Gradient Descent (SGD):

$$\mathbf{w}{t+1} = \mathbf{w}_t - \alpha \cdot \nabla \ell(\mathbf{w}_t; \mathbf{x}{i_t}, y_{i_t})$$

• Uses one randomly sampled example per step
• Cost per iteration: $O(1)$
• Gradient is an unbiased estimator of the true gradient: $\mathbb{E}[\nabla \ell(\mathbf{w}; \mathbf{x}_i, y_i)] = \nabla f(\mathbf{w})$
• Noisy updates → can escape saddle points and local minima, but high variance → slow convergence near optimum

Mini-Batch SGD:

$$\mathbf{w}{t+1} = \mathbf{w}_t - \alpha \cdot \frac{1}{B}\sum{i \in \mathcal{B}_t} \nabla \ell(\mathbf{w}_t; \mathbf{x}_i, y_i)$$

• Uses $B$ randomly sampled examples (typical: $B = 32, 64, 128, 256$)
• Cost per iteration: $O(B)$
• Variance of gradient estimate scales as $1/B$ (for i.i.d. sampling)
• Best of both worlds: faster than BGD, lower variance than SGD, GPU-efficient (parallelizes over batch)

⚠️ CRITICAL — The batch size matters deeply. Larger $B$ → more accurate gradient → can use larger learning rate. But the "generalization gap": very large batch training (e.g., $B=8192$) often finds sharper minima that generalize worse than small-batch training. Linear scaling rule: when you multiply $B$ by $k$, multiply $\alpha$ by $\sqrt{k}$ (for SGD) or $k$ (with appropriate normalization).

Convergence Analysis

Convex ($\mu = 0$), $L$-smooth: With step size $\alpha \leq 1/L$:

$$f(\bar{\mathbf{w}}_T) - f^ \leq \frac{|\mathbf{w}_0 - \mathbf{w}^|^2}{2\alpha T}$$

where $\bar{\mathbf{w}}T = \frac{1}{T}\sum{t=0}^{T-1} \mathbf{w}_t$ is the averaged iterate. Sublinear rate: $O(1/T)$.

$\mu$-strongly convex, $L$-smooth: With $\alpha \leq 1/L$:

$$|\mathbf{w}_T - \mathbf{w}^|^2 \leq (1 - \alpha\mu)^T |\mathbf{w}_0 - \mathbf{w}^|^2$$

Linear (geometric) rate: error shrinks by constant factor each iteration. To reach $|\mathbf{w}_T - \mathbf{w}^*| \leq \epsilon$: $T = O(\kappa \log(1/\epsilon))$ where $\kappa = L/\mu$.

Non-convex, $L$-smooth (deep learning): Convergence to a stationary point:

$$\min_{0 \leq t < T} |\nabla f(\mathbf{w}_t)|^2 \leq \frac{2L(f(\mathbf{w}_0) - f^*)}{T}$$

Also sublinear: $O(1/T)$ to reach $|\nabla f| \leq \epsilon$. This is the best we can guarantee for general non-convex problems — we converge to a point with small gradient (could be saddle, local min, or global min).

SGD convergence (convex): With step size $\alpha_t = 1/\sqrt{t}$ and bounded gradient variance $\mathbb{E}[|\nabla \ell - \nabla f|^2] \leq \sigma^2$:

$$\mathbb{E}[f(\bar{\mathbf{w}}_T)] - f^* \leq O\left(\frac{1}{\sqrt{T}}\right)$$

Slower than BGD's $O(1/T)$ due to gradient noise. But per-iteration cost is $B$ instead of $N$.

Learning Rate Schedules

Step decay: Reduce $\alpha$ by factor $\gamma$ every $k$ epochs. $\alpha_t = \alpha_0 \cdot \gamma^{\lfloor t/k \rfloor}$, e.g., $\alpha_0 = 0.1$, $\gamma = 0.1$, $k = 30$ epochs.

Exponential decay: $\alpha_t = \alpha_0 \cdot \gamma^t$.

Cosine annealing (Loshchilov & Hutter, 2017):

$$\alpha_t = \alpha_{\min} + \frac{1}{2}(\alpha_{\max} - \alpha_{\min})\left(1 + \cos\left(\frac{t}{T}\pi\right)\right)$$

Smoothly decreases from $\alpha_{\max}$ to $\alpha_{\min}$ over $T$ iterations. Often restarted (cosine annealing with warm restarts).

Warmup: Start with small $\alpha$ and linearly increase to target over first $k$ iterations. Critical for transformers and large models — prevents divergence in early iterations when weights are random and gradients are large or poorly scaled.

$$\alpha_t = \alpha_{\text{target}} \cdot \min\left(1, \frac{t}{k}\right)$$

Why learning rate decay works: In early training, large $\alpha$ enables rapid progress. As we approach the optimum, the gradient shrinks and the loss surface becomes locally quadratic — a smaller $\alpha$ prevents overshooting and allows fine-grained convergence.

Momentum

Standard SGD can oscillate in narrow valleys (high curvature in one direction, low in another). Momentum accumulates a velocity vector:

$$\mathbf{v}_{t+1} = \beta \mathbf{v}_t + \nabla f(\mathbf{w}_t)$$

$$\mathbf{w}{t+1} = \mathbf{w}_t - \alpha \mathbf{v}{t+1}$$

where $\beta \in [0, 1)$ (typically $\beta = 0.9$). Expanding:

$$\mathbf{v}t = \sum{i=0}^{t-1} \beta^i \nabla f(\mathbf{w}_{t-1-i})$$

The velocity is an exponentially weighted moving average of past gradients. Low-curvature directions accumulate (velocity grows), high-curvature oscillatory directions cancel out.

Nesterov Accelerated Gradient (NAG): A "lookahead" variant:

$$\mathbf{v}_{t+1} = \beta \mathbf{v}_t + \nabla f(\mathbf{w}_t - \alpha\beta\mathbf{v}_t)$$

$$\mathbf{w}{t+1} = \mathbf{w}_t - \alpha \mathbf{v}{t+1}$$

The gradient is evaluated at the "lookahead" position $\mathbf{w}_t - \alpha\beta\mathbf{v}_t$. This provides a correction term and achieves optimal convergence rate $O(1/T^2)$ for convex smooth functions (vs $O(1/T)$ for standard gradient descent).

Adaptive Methods: RMSprop and Adam

Momentum uses the same learning rate for all parameters, but different parameters have different curvature. Adaptive methods scale $\alpha$ per-parameter using historical gradient information.

RMSprop (Tieleman & Hinton, 2012): Maintains a moving average of squared gradients:

$$\mathbf{s}_{t+1} = \rho \mathbf{s}_t + (1 - \rho)(\nabla f(\mathbf{w}_t))^2$$

$$\mathbf{w}{t+1} = \mathbf{w}_t - \alpha \frac{\nabla f(\mathbf{w}_t)}{\sqrt{\mathbf{s}{t+1}} + \epsilon}$$

where $\rho \approx 0.9$, $\epsilon \approx 10^{-8}$ (prevents division by zero). Parameters with large gradients get smaller effective step sizes; parameters with small gradients get larger ones. This is especially effective for non-stationary objectives and sparse gradients (e.g., word embeddings, where most features are zero most of the time).

Adam (Kingma & Ba, 2015): Combines momentum with RMSprop's adaptive scaling:

$$\mathbf{m}_{t+1} = \beta_1 \mathbf{m}_t + (1 - \beta_1)\nabla f(\mathbf{w}_t)$$

$$\mathbf{v}_{t+1} = \beta_2 \mathbf{v}_t + (1 - \beta_2)(\nabla f(\mathbf{w}_t))^2$$

Where $\mathbf{m}_t$ is the first moment (mean) and $\mathbf{v}_t$ is the second moment (uncentered variance) of gradients.

Bias correction (because $\mathbf{m}_0 = \mathbf{v}_0 = \mathbf{0}$):

$$\hat{\mathbf{m}}_t = \frac{\mathbf{m}_t}{1 - \beta_1^t}, \quad \hat{\mathbf{v}}_t = \frac{\mathbf{v}_t}{1 - \beta_2^t}$$

Update:

$$\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \frac{\hat{\mathbf{m}}_t}{\sqrt{\hat{\mathbf{v}}_t} + \epsilon}$$

Default hyperparameters: $\alpha = 0.001$, $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-8}$.

⚠️ CRITICAL — Adam is not always the best choice. For well-tuned problems (e.g., image classification with CNNs), SGD with momentum often generalizes better than Adam. Adam's adaptive scaling can converge faster but sometimes finds solutions that generalize worse. Recent work (AdamW) decouples weight decay from Adam's adaptive gradient scaling, improving generalization. The optimizer choice interacts with the task: Adam for transformers/NLP, SGD+momentum for vision — but this is an empirical guideline, not a law.

The Conditioning Problem and Preconditioning

The effectiveness of gradient descent depends critically on conditioning. For a quadratic $f(\mathbf{w}) = \frac{1}{2}\mathbf{w}^T H \mathbf{w}$ with Hessian $H$:

Gradient descent: $\mathbf{w}_{t+1} = (I - \alpha H)\mathbf{w}_t$. Convergence depends on $\max_i |1 - \alpha \lambda_i|$ where $\lambda_i$ are eigenvalues of $H$.

The optimal convergence rate is $\frac{\kappa - 1}{\kappa + 1}$ where $\kappa = \lambda_{\max}/\lambda_{\min}$.

For $\kappa = 100$: rate $\approx 0.98$ per iteration (slow). For $\kappa = 1$: rate $= 0$ (instant convergence with $\alpha = 1/\lambda$).

Preconditioning transforms the problem: solve $\min_{\mathbf{z}} f(P\mathbf{z})$ where $P$ approximates $H^{-1/2}$. The Hessian of the transformed problem is $P^T H P$, and if $P \approx H^{-1/2}$, this approaches $I$ with $\kappa \approx 1$.

Adam and RMSprop can be viewed as diagonal preconditioners: they approximate $\operatorname{diag}(H)^{-1/2}$ using the running average of squared gradients. This is why they're robust to poor scaling of parameters.

Newton's method uses $P = H^{-1}$ (full preconditioning): $\mathbf{w}_{t+1} = \mathbf{w}_t - H^{-1}\nabla f(\mathbf{w}_t)$, achieving quadratic convergence near the optimum. But $H^{-1}$ is $O(n^3)$ for $n$ parameters — impossible for deep networks. This motivates quasi-Newton methods (L-BFGS) which approximate $H^{-1}$ using gradient history.

Key Terms

• Adam
• Bias correction
• Cosine annealing
• Exponentially weighted moving average
• Learning rate schedule
• Mini-batch SGD
• Momentum
• Nesterov acceleration
• Preconditioning
• Second moment (uncentered variance)

Worked Examples

Example 1: Convergence Rate for a Quadratic

Consider $f(x, y) = \frac{1}{2}(x^2 + 100y^2)$. Starting from $(x_0, y_0) = (10, 1)$, compute 3 iterations of gradient descent with $\alpha = 0.01$ (close to $1/L \approx 1/100 = 0.01$). Compare with the theoretical convergence rate.

Solution: $\nabla f = (x, 100y)$. $\mathbf{w}_0 = (10, 1)$.

$t=0$: $\mathbf{w}_1 = (10, 1) - 0.01(10, 100) = (9.9, 0)$.

$t=1$: $\nabla f(9.9, 0) = (9.9, 0)$. $\mathbf{w}_2 = (9.9, 0) - 0.01(9.9, 0) = (9.801, 0)$.

$t=2$: $\nabla f(9.801, 0) = (9.801, 0)$. $\mathbf{w}_3 = (9.801, 0) - 0.01(9.801, 0) = (9.703, 0)$.

After 3 iterations: $\mathbf{w}_3 = (9.703, 0)$, $f(\mathbf{w}_3) = \frac{1}{2}(9.703^2) = 47.07$.

Hessian: $H = \operatorname{diag}(1, 100)$. Eigenvalues: $\lambda_1 = 1$, $\lambda_2 = 100$. $\kappa = 100$.

For $x$-direction ($\lambda=1$): $1 - \alpha\lambda = 1 - 0.01 = 0.99$. After 3 steps: $10 \times 0.99^3 = 9.703$ ✓.

For $y$-direction ($\lambda=100$): $1 - \alpha\lambda = 1 - 1 = 0$. Converges in ONE step! $1 \times 0 = 0$ ✓.

The slow $x$-direction dominates convergence: rate $0.99$ per iteration. To reduce error by $10^{-3}$: need $k$ such that $0.99^k \leq 0.001$, so $k \geq \ln(1000)/\ln(1/0.99) \approx 688$ iterations. This is the curse of ill-conditioning — even in 2D!

Example 2: SGD Variance

For linear regression with $N=3$ points: $(x_1=1, y_1=2)$, $(x_2=2, y_2=4)$, $(x_3=3, y_3=6)$. Model $\hat{y} = wx$. Loss $f(w) = \frac{1}{3}\sum_{i=1}^3 (wx_i - y_i)^2$.

Compute the true gradient at $w=0$, the per-example stochastic gradients, and the variance of the SGD gradient estimator.

Solution: $\ell_i(w) = (w x_i - y_i)^2$, $\nabla \ell_i(w) = 2x_i(w x_i - y_i)$.

True gradient at $w=0$: $\nabla f(0) = \frac{1}{3}\sum_{i=1}^3 2x_i(0 - y_i) = \frac{1}{3}[2(1)(-2) + 2(2)(-4) + 2(3)(-6)]$ $= \frac{1}{3}[-4 - 16 - 36] = \frac{-56}{3} \approx -18.667$.

Per-example gradients at $w=0$: - $i=1$: $\nabla \ell_1(0) = 2(1)(0-2) = -4$ - $i=2$: $\nabla \ell_2(0) = 2(2)(0-4) = -16$ - $i=3$: $\nabla \ell_3(0) = 2(3)(0-6) = -36$

Unbiasedness check: $\mathbb{E}_{i \sim \text{Uniform}}[\nabla \ell_i] = \frac{1}{3}(-4 - 16 - 36) = -56/3$ ✓.

Variance of estimator: $\operatorname{Var}(\nabla \ell_i) = \mathbb{E}[(\nabla \ell_i - \mathbb{E}[\nabla \ell_i])^2]$ $= \frac{1}{3}[(-4+56/3)^2 + (-16+56/3)^2 + (-36+56/3)^2]$ $= \frac{1}{3}[(44/3)^2 + (8/3)^2 + (-52/3)^2] = \frac{1}{3} \cdot \frac{1936 + 64 + 2704}{9} = \frac{4704}{27} \approx 174.22$.

Standard deviation: $\sqrt{174.22} \approx 13.2$. Compared to the true gradient magnitude $18.67$ — the noise is enormous! This is why SGD needs decreasing step sizes: $\alpha_t \to 0$ must compensate for persistent gradient noise.

Mini-batch with $B=2$ reduces variance by factor $1/B$ (i.i.d. sampling): $\operatorname{Var}(\frac{1}{2}(\nabla \ell_i + \nabla \ell_j)) = \frac{174.22}{2} = 87.11$ (approximately — finite population correction applies for $N=3$).

Example 3: Adam vs SGD-Momentum — A Numerical Illustration

For the ill-conditioned quadratic $f(x, y) = \frac{1}{2}(x^2 + 100y^2)$, simulate 20 steps of SGD with momentum ($\beta=0.9$) and Adam ($\beta_1=0.9$, $\beta_2=0.999$) starting from $(10, 1)$. Use $\alpha = 0.1$ for both (with Adam's default bias correction). Track $f(\mathbf{w}_t) - f^*$.

Solution: Since this is a deterministic problem (full gradient, no noise), we can compute exact iterates.

SGD with momentum ($\beta=0.9$, $\alpha=0.1$):

Initialize $\mathbf{v}_0 = (0, 0)$, $\mathbf{w}_0 = (10, 1)$.

$t=0$: $\nabla f(10, 1) = (10, 100)$. $\mathbf{v}_1 = 0.9(0,0) + (10, 100) = (10, 100)$. $\mathbf{w}_1 = (10,1) - 0.1(10, 100) = (9, -9)$.

$t=1$: $\nabla f(9, -9) = (9, -900)$. $\mathbf{v}_2 = 0.9(10, 100) + (9, -900) = (18, -810)$. $\mathbf{w}_2 = (9, -9) - 0.1(18, -810) = (7.2, 72)$.

The $y$-coordinate oscillates wildly because momentum accumulates the large gradient in the high-curvature direction!

Continuing numerically (or via program), after 20 iterations with SGD+momentum: oscillations persist, slow convergence.

Adam ($\beta_1=0.9$, $\beta_2=0.999$, $\alpha=0.1$, $\epsilon=10^{-8}$):

The second-moment estimate $\mathbf{v}_t$ scales down the high-gradient $y$-direction: - $t=0$: $g = (10, 100)$. $m_1 = 0.1(10, 100) = (1, 10)$. $v_1 = 0.001(100, 10000) = (0.1, 10)$. Bias-corrected: $\hat{m}_1 = (1, 10)/(1-0.9) = (10, 100)$. $\hat{v}_1 = (0.1, 10)/(1-0.999) = (100, 10000)$. Update: $\mathbf{w}_1 = (10, 1) - 0.1(10/\sqrt{100+10^{-8}}, 100/\sqrt{10000+10^{-8}}) = (10, 1) - 0.1(1, 1) = (9.9, 0.9)$.

Adam immediately normalizes both directions to similar scale — the effective step in each direction is comparable! After 20 steps, Adam makes steady progress in both directions, converging much faster than SGD+momentum on this ill-conditioned problem.

Quiz

Q1: What does the concept of Bias correction primarily refer to in this subject?

A) A historical anecdote about Bias correction B) A computational error related to Bias correction C) The definition and application of Bias correction D) A visual representation of Bias correction

Correct: C)

• If you chose A: This is incorrect. Bias correction is defined as: the definition and application of bias correction. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Bias correction is defined as: the definition and application of bias correction. The other options describe different aspects that are not the primary focus.
• If you chose C: Bias correction is defined as: the definition and application of bias correction. The other options describe different aspects that are not the primary focus. Correct!
• If you chose D: This is incorrect. Bias correction is defined as: the definition and application of bias correction. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) f(\mathbf{w}) B) The inverse operation of the formula in question C) An unrelated formula from a different topic D) A simplified version of f(\mathbf{w})...

Correct: A)

• If you chose A: The formula f(\mathbf{w}) is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula f(\mathbf{w}) is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula f(\mathbf{w}) is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula f(\mathbf{w}) is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Preconditioning?

A) It is primarily a historical notation system B) It is used to preconditioning in mathematical analysis C) It is used only in advanced research contexts D) It replaces all other methods in this domain

Correct: B)

• If you chose A: This is incorrect. Preconditioning serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: Preconditioning serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose C: This is incorrect. Preconditioning serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Preconditioning serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Cosine annealing is TRUE?

A) Cosine annealing is not related to this subject B) Cosine annealing is an advanced topic beyond this subject's scope C) Cosine annealing is mentioned only as a historical footnote D) Cosine annealing is a fundamental concept covered in this subject

Correct: D)

• If you chose A: This is incorrect. Cosine annealing is a fundamental concept covered in this subject. This subject covers Cosine annealing as part of its core content.
• If you chose B: This is incorrect. Cosine annealing is a fundamental concept covered in this subject. This subject covers Cosine annealing as part of its core content.
• If you chose C: This is incorrect. Cosine annealing is a fundamental concept covered in this subject. This subject covers Cosine annealing as part of its core content.
• If you chose D: Cosine annealing is a fundamental concept covered in this subject. This subject covers Cosine annealing as part of its core content. Correct!

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) (1-\alpha)w_t$. C) An unrelated numerical value D) A different result from a common mistake

Correct: B)

• If you chose A: This is incorrect. The worked examples show that the result is (1-\alpha)w_t$.. The other options represent common errors.
• If you chose B: The worked examples show that the result is (1-\alpha)w_t$.. The other options represent common errors. Correct!
• If you chose C: This is incorrect. The worked examples show that the result is (1-\alpha)w_t$.. The other options represent common errors.
• If you chose D: This is incorrect. The worked examples show that the result is (1-\alpha)w_t$.. The other options represent common errors.

Q6: How are Cosine annealing and Exponentially weighted moving average related?

A) Cosine annealing and Exponentially weighted moving average are closely related concepts B) Cosine annealing is a special case of Exponentially weighted moving average C) Cosine annealing and Exponentially weighted moving average are completely unrelated topics D) Cosine annealing is the inverse of Exponentially weighted moving average

Correct: A)

• If you chose A: Both Cosine annealing and Exponentially weighted moving average are covered in this subject as interconnected topics. Correct!
• If you chose B: This is incorrect. Both Cosine annealing and Exponentially weighted moving average are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Cosine annealing and Exponentially weighted moving average are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Cosine annealing and Exponentially weighted moving average are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Learning rate schedule?

A) Learning rate schedule is always computed the same way in all contexts B) The main error with Learning rate schedule is using it when it is not needed C) A common mistake is confusing Learning rate schedule with a similar concept D) Learning rate schedule has no common misconceptions

Correct: C)

• If you chose A: This is incorrect. Students often confuse Learning rate schedule with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Learning rate schedule with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Learning rate schedule with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Learning rate schedule with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Mini-batch SGD?

A) Use Mini-batch SGD only in pure mathematics contexts B) Apply Mini-batch SGD to solve problems in this subject's domain C) Avoid Mini-batch SGD unless explicitly instructed D) Mini-batch SGD is not practically useful

Correct: B)

• If you chose A: This is incorrect. Mini-batch SGD is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: Mini-batch SGD is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose C: This is incorrect. Mini-batch SGD is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. Mini-batch SGD is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. For $f(w) = \frac{1}{2}w^2$, show that gradient descent with $\alpha = 1$ gives $w_{t+1} = -w_t$ (oscillation) and that $\alpha = 1/L = 1$ is the boundary of stability. What is the optimal $\alpha$ for fastest convergence on this problem?
   

   Click for answer

   $f'(w) = w$. Update: $w_{t+1} = w_t - \alpha w_t = (1-\alpha)w_t$. For $\alpha = 1$: $w_{t+1} = 0 \cdot w_t = 0$, which converges in one step! Wait — let me recompute: $w_{t+1} = w_t - 1 \cdot w_t = 0$. So $\alpha = 1$ is optimal, giving instant convergence. Actually, let me think about the stability range. $|1-\alpha| < 1 \implies 0 < \alpha < 2$. At $\alpha = 1$: instant convergence. At $\alpha = 2$: $w_{t+1} = -w_t$ (oscillation). So $\alpha=1$ is optimal, not the boundary. The boundary of stability is $\alpha = 2$ where $|1-\alpha| = 1$. For $\alpha > 2$: $|1-\alpha| > 1$, divergence. Optimal $\alpha$ for this problem: $\alpha = 1 = 1/L$ (since $L = \nabla^2 f = 1$).

2. Derive the expected gradient of the mini-batch estimator: $\mathbf{g}B = \frac{1}{B}\sum{i \in \mathcal{B}} \nabla \ell_i(\mathbf{w})$, where $\mathcal{B}$ is sampled uniformly without replacement. Show it's unbiased: $\mathbb{E}[\mathbf{g}_B] = \nabla f(\mathbf{w})$.
   

   Click for answer

   For sampling without replacement from $\{1,\ldots,N\}$: Let $I_j$ be the $j$-th index drawn. By symmetry, each index is equally likely: $P(I_j = i) = 1/N$. $\mathbb{E}[\mathbf{g}_B] = \mathbb{E}[\frac{1}{B}\sum_{j=1}^B \nabla \ell_{I_j}] = \frac{1}{B}\sum_{j=1}^B \mathbb{E}[\nabla \ell_{I_j}] = \frac{1}{B}\sum_{j=1}^B \frac{1}{N}\sum_{i=1}^N \nabla \ell_i = \frac{1}{N}\sum_{i=1}^N \nabla \ell_i = \nabla f(\mathbf{w})$. The result holds for both with and without replacement sampling. The variance with replacement is $\sigma^2/B$; without replacement is $\frac{\sigma^2}{B} \cdot \frac{N-B}{N-1}$ (slightly lower due to finite population correction).

3. Explain why Adam with default hyperparameters often outperforms SGD on problems with sparse gradients (like word embeddings), but may underperform on dense well-conditioned problems (like image classification).
   

   Click for answer

   **Sparse gradients (embeddings):** Most features are zero most of the time. A word embedding row only gets gradients when that word appears. SGD uses the same learning rate for frequently and rarely updated parameters — rare parameters get almost no updates. Adam's $\mathbf{v}_t$ (running average of squared gradients) naturally gives larger effective step sizes to parameters with small historical gradients (rare words) and smaller steps to frequently updated ones. This is precisely what's needed. **Dense, well-conditioned (CNNs):** All parameters get gradients every iteration. SGD+momentum with a well-tuned constant learning rate can find flatter minima that generalize better. Adam's per-parameter normalization can over-adapt to recent gradient noise and converge to sharper minima. The adaptive scaling provides less benefit when gradients are already well-scaled. This is why standard practice is: Adam for transformers/NLP, SGD+momentum for CNNs/vision. But AdamW (decoupled weight decay) has narrowed this gap significantly.

4. Show that Nesterov accelerated gradient on $f(x) = \frac{1}{2}x^2$ with $\beta = 0$ reduces to standard gradient descent. Find the convergence rate for the optimal $\beta$ when $f$ is $\mu$-strongly convex and $L$-smooth.
   

   Click for answer

   NAG: $v_{t+1} = \beta v_t + \nabla f(x_t - \alpha\beta v_t)$, $x_{t+1} = x_t - \alpha v_{t+1}$. With $\beta = 0$: $v_{t+1} = \nabla f(x_t)$, $x_{t+1} = x_t - \alpha \nabla f(x_t)$ — standard GD ✓. For $\mu$-strongly convex, $L$-smooth functions, NAG with optimal parameters achieves: $\|\mathbf{w}_T - \mathbf{w}^*\|^2 \leq \left(1 - \sqrt{\frac{\mu}{L}}\right)^T \|\mathbf{w}_0 - \mathbf{w}^*\|^2$. This is accelerated rate $O((1 - \sqrt{\mu/L})^T)$, compared to standard GD's $O((1 - \mu/L)^T)$. For $\kappa = 100$: GD rate $\approx 0.99$ per iteration, NAG rate $\approx 0.9$ per iteration — a dramatic improvement. NAG achieves the optimal first-order convergence rate for this class of problems.

5. Design a learning rate schedule for training a ResNet-50 on ImageNet for 90 epochs. Justify each design choice.
   

   Click for answer

   Standard recipe: - Epochs 0–5: Linear warmup from $\alpha=0$ to $\alpha=0.1$ (Reason: random initialization has poorly scaled gradients; warmup prevents early divergence) - Epochs 5–30: $\alpha=0.1$ (Reason: plateau at maximal LR for fast initial progress) - Epoch 30: $\alpha=0.01$ (divide by 10) - Epoch 60: $\alpha=0.001$ (divide by 10) - Epoch 80: $\alpha=0.0001$ (divide by 10) This is step decay with milestones at 30, 60, 80 epochs. Alternative: cosine annealing from 0–90 with $\alpha_{\max}=0.1$, $\alpha_{\min}=0$. Cosine is now preferred: smoother decay avoids the abrupt loss jumps at step boundaries and often achieves the same or better final accuracy without manual milestone tuning. Warmup is still used with cosine (e.g., 5-epoch linear warmup, then cosine decay).

Summary

Key takeaways:

• Batch GD uses full dataset per step ($O(N)$); SGD uses one example ($O(1)$) with noisy unbiased gradient estimates; mini-batch SGD ($O(B)$) balances efficiency and variance
• Convergence: strongly convex gives linear rate $O((1-\mu/L)^T)$; convex gives sublinear $O(1/T)$; non-convex guarantees convergence to stationary point at $O(1/T)$
• Learning rate schedules (step decay, cosine, warmup) are essential for deep learning — they balance rapid early progress with fine-grained convergence later
• Momentum ($\beta \approx 0.9$) accumulates velocity to dampen oscillations in narrow valleys; Nesterov acceleration achieves optimal $O(1/T^2)$ rate for convex smooth problems
• Adam combines momentum with adaptive per-parameter scaling via second moment estimates; default hyperparameters ($\alpha=0.001$, $\beta_1=0.9$, $\beta_2=0.999$) work well across many problems
• The condition number $\kappa = L/\mu$ (or effective eigenvalue spread) governs convergence speed — adaptive methods act as diagonal preconditioners approximating $\operatorname{diag}(H)^{-1/2}$
• Batch size is a critical tuning parameter: larger $B$ reduces gradient variance but may hurt generalization; linear scaling rule helps adjust learning rate when changing batch size

Pitfalls

• Using too large a learning rate and mistaking oscillation for "still training": When $\alpha > 2/L$, gradient descent diverges. When $\alpha$ is near the stability boundary, the loss oscillates — it may stay flat or even decrease on average but the parameter vector bounces without converging. If your training loss plateaus while the gradient norm stays large, your learning rate is likely too high, not too low. Reduce $\alpha$ and check if loss resumes decreasing.
• Forgetting bias correction in Adam — silently crippling early training: Adam's $\mathbf{m}_t$ and $\mathbf{v}_t$ are initialized to $\mathbf{0}$, so raw moment estimates are biased toward zero for early iterations. Without dividing by $(1-\beta_1^t)$ and $(1-\beta_2^t)$, the first few steps are scaled down by factors of $0.1$ and $0.001$ respectively, making early progress extremely slow. This is especially damaging with warmup, where small initial steps cascade. Most frameworks apply bias correction by default, but verify it's on if implementing from scratch.
• Applying Adam where SGD+momentum generalizes better (and vice versa): Adam's per-parameter adaptive scaling converges quickly on poorly conditioned or sparse-gradient problems (NLP, transformers), but its adaptive nature can converge to sharper minima that generalize worse on dense, well-conditioned problems (image classification with CNNs). SGD+momentum with careful tuning often finds flatter minima. The choice isn't universal — benchmark both on your specific task rather than defaulting to Adam.
• Omitting learning rate warmup for transformer training: Transformers with random initialization have poorly scaled gradients, especially in the early layers. Starting with a full learning rate often causes divergence or severe instability in the first few hundred steps. Linear warmup from $0$ to the target $\alpha$ over ~4000 steps (or a few epochs) is standard practice. The Post-LN vs Pre-LN architecture choice also affects warmup sensitivity — Pre-LN is more forgiving but still benefits from short warmup.
• Confusing batch size scaling rules: The linear scaling rule ($\alpha \propto B$) works up to moderate batch sizes (~8K for ImageNet), but at very large batch sizes ($B > 32K$), gradient noise reduction saturates and the rule fails without additional adjustments (LARS, LAMB optimizers). Also, the rule assumes the loss per example doesn't change with $B$ — if you use BatchNorm, the effective statistics change with batch size, breaking the scaling assumption. Test scaling behavior rather than trusting the rule blindly.

Next Steps

This concludes Section 15 (Numerical Methods for ML). Next is Phase 16: Neural Network Mathematics, starting with 16-01-perceptron-model.md — neuron models, activation functions, and the universal approximation theorem.