Chapter 2 — Derivations

Optimization interviews are derivation interviews. The interviewer writes a Hessian's eigenvalues, an update rule or a constraint on the board and asks you to produce the step size limit, the rate, the bias correction or the multiplier, by hand, while explaining each line. They ask because these derivations are short and they separate people who know the recipe from people who know why it works: the $2/\lambda_{\max}$ cliff, the $(\kappa - 1)/(\kappa + 1)$ rate, the $1/B$ variance of a minibatch, Adam's $(1 - \beta^{t})$ and Newton's one-step landing all fall out of four algebra moves. This tab has those four moves (plus one for constraints), the chapter's 25 formulas, and 20 cards. Each card states a result, derives it with every step shown, checks the answer on the six-order ETA toy or the 10,000-order simulation, and names the slip candidates make and the way the question is asked. Practice by covering everything below a card's Statement, deriving it on a blank page against a timer, then checking. The protocol at the end says how.

The toolkit

Every card checks itself on the six-order toy from Section 1. Features are centered, so the intercept is fixed at $\bar y = 21$ and the loss is a bowl in two weights, $w = (w_{\text{km}}, w_{\text{items}})$ . The facts every card reuses:

L(\mathbf w) = \tfrac16\lVert\tilde{\mathbf y} - D\mathbf w\rVert^2, \quad \mathbf w^\star = (3,\, 2), \quad L^\star = \tfrac{10}{6} = 1.667, \quad H = \tfrac13\begin{pmatrix}10 & 5\\ 5 & 10\end{pmatrix}, \quad \lambda = 5 \text{ along } (1,1),\;\; \tfrac53 \text{ along } (1,-1)

$L(\mathbf w)$: the loss at weights $\mathbf w$ : mean squared ETA miss over the six orders (‖·‖ = length)
$\mathbf w$: the weight vector $(w_{\text{km}}, w_{\text{items}})$ : minutes per km and per item (bold = vector)
$\tilde{\mathbf y}$: the six delivery times minus their 21-minute average (tilde = centered)
$D$: the 6 × 2 matrix of centered features: one row per order, columns km and items
$\mathbf w^\star$: the best weights, the bottom of the bowl (star = the optimum)
$L^\star$: the lowest loss reachable, at $\mathbf w^\star$
$H$: the Hessian: matrix of second derivatives, the bowl's curvature in every direction
$\lambda$: an eigenvalue of $H$ : the curvature along one of the bowl's own axes

At $w = 0$ the loss is 33.3 and the gradient is (−13.3, −11.7). A plain $L(\cdot )$ with an argument is the loss; a bare $L$ in a rate or a step size is the smoothness constant, the largest curvature ( $\lambda_{\max} = 5$ on the toy), and $\mu$ is the smallest (5/3). Every derivation in this tab uses some combination of four moves. Hook: TRUE.

T · Taylor-expand. Near any point the loss is a line (first order) or a bowl (second order); most results come from bounding or minimizing that bowl.

L(\mathbf w + \mathbf d) \approx L(\mathbf w) + \nabla L(\mathbf w)^\top\mathbf d + \tfrac12\,\mathbf d^\top H\,\mathbf d

$L(\mathbf w + \mathbf d)$: the loss after moving from $\mathbf w$ by the step $\mathbf d$
$\mathbf d$: a small step (displacement) in weight space
$\nabla L(\mathbf w)$: the gradient at $\mathbf w$ : the vector of slopes, one per weight; points uphill
$\nabla L(\mathbf w)^\top\mathbf d$: the first-order change: gradient dotted with the step (⊤ = transpose: rows become columns)
$\mathbf d^\top H\,\mathbf d$: the second-order term: how sharply the bowl bends along $\mathbf d$

R · Rotate to the eigenbasis. Write $H = Q\Lambda Q^\top$ and measure the error $z = Q^\top(w - w^*)$ along the bowl's own axes; a quadratic becomes independent 1-D problems, one per eigenvalue.

L(\mathbf w) = L^\star + \tfrac12(\mathbf w - \mathbf w^\star)^\top H(\mathbf w - \mathbf w^\star) = L^\star + \tfrac12\sum_i \lambda_i z_i^2

$\mathbf w - \mathbf w^\star$: the error: how far the weights sit from the optimum
$\sum_i$: add up over the bowl's axes (eigen-directions) $i$
$\lambda_i$: the curvature along axis $i$ (5 or 5/3 on the toy)
$z_i$: the error measured along axis $i$ : entry $i$ of $Q^\top(\mathbf w - \mathbf w^\star)$

U · Unroll the recursion. A linear update repeated $k$ times is a power, and the inputs it accumulates are a geometric series.

e_{k+1} = a\,e_k + b_k \;\Rightarrow\; e_k = a^k e_0 + \sum_{j=0}^{k-1} a^{k-1-j}\,b_j, \qquad \sum_{j=0}^{k-1} a^j = \frac{1 - a^k}{1 - a}

$e$: the quantity being tracked (an error, a buffer, a second moment); subscript = step
$k$: the step number; also how many times the update repeats
$a$: the fixed factor multiplying it every step
$b$: the input (kick) added each step; subscript = which step
$j$: the step an earlier input came from
$\sum_{j=0}^{k-1}$: add up over steps $j = 0$ to $k - 1$

E · Expectation and variance of averages. Expectation is linear; independent terms add their variances, so a mean of $B$ independent draws has variance $\sigma^{2}/B$ .

\mathbb E\Big[\frac1B\sum_{j=1}^{B} X_j\Big] = \mathbb E[X], \qquad \text{Var}\Big(\frac1B\sum_{j=1}^{B} X_j\Big) = \frac{\sigma^2}{B} \;\;(\text{independent}), \qquad \text{Var}(aX + Y) = a^2\text{Var}(X) + \text{Var}(Y) \;\;(X \perp Y)

$\mathbb E$: expectation: the average over repeated random draws
$\text{Var}$: variance: the average squared spread around the mean
$B$: the number of independent draws averaged (later: the minibatch size)
$\sum_{j=1}^{B}$: add up over the $B$ draws
$X_j$: the $j$ -th random draw, e.g. one order's gradient
$X$: a single random draw of the same kind
$\sigma^2$: the variance of one draw
$a$: here: any constant multiplier
$Y$: a second random quantity, independent of $X$ ( $\perp$ = independent)
$\frac1B$: the average: divide the sum by the $B$ draws

+L · Write the Lagrangian (Cards 15–16). A constraint becomes a price $\mu$ ; at the optimum the loss's pull and the constraint's push balance, and the push is non-zero only when the constraint binds. For a kink like $\lvert w\rvert$ , the same balance uses the subgradient.

\mathcal L(\mathbf w, \mu) = L(\mathbf w) + \mu\,g(\mathbf w), \qquad \nabla L + \mu\nabla g = \mathbf 0,\;\; g \le 0,\;\; \mu \ge 0,\;\; \mu\,g = 0

$\mathcal L(\mathbf w, \mu)$: the Lagrangian: the loss plus the constraint, priced at $\mu$
$\mu$: here: the multiplier, the constraint's price per unit (not the smallest curvature)
$g(\mathbf w)$: the constraint function: allowed weights have $g(\mathbf w) \le 0$
$g$: the same constraint, written without its argument
$\nabla L$: the loss's gradient; its downhill pull is $-\nabla L$
$\nabla g$: the constraint's gradient: the direction that violates it fastest

Formula sheet

Gradients and curvature

MSE: gradient and Hessian

L(\mathbf w) = \tfrac1n\lVert\mathbf y - X\mathbf w\rVert^2, \qquad \nabla L = -\tfrac2n X^\top(\mathbf y - X\mathbf w), \qquad H = \tfrac2n X^\top X

$L(\mathbf w)$: the MSE loss at weights $\mathbf w$ (‖·‖² = squared length: sum of squared misses)
$n$: the number of orders (rows)
$\mathbf y$: the vector of actual delivery times, one per order (bold = vector)
$X$: the feature matrix: one row per order, one column per feature
$\mathbf w$: the weight vector: minutes per unit of each feature
$\nabla L$: the gradient: vector of slopes of the loss, one per weight; points uphill
$X^\top$: $X$ transposed (rows become columns)
$H$: the Hessian: matrix of second derivatives, the loss bowl's curvature
$X^\top X$: the features' cross-product matrix: how features co-vary across orders
$\tfrac1n$: the average over the $n$ orders
$\tfrac2n$: the 2 from differentiating the square, averaged over $n$ orders

Logistic loss: gradient and Hessian

\nabla L = \tfrac1n X^\top(\mathbf p - \mathbf y), \qquad H = \tfrac1n X^\top S X, \qquad S = \operatorname{diag}\big(p_i(1 - p_i)\big), \qquad p_i = \sigma(\mathbf x_i^\top\mathbf w)

$\mathbf p$: the vector of predicted late-probabilities, one per order
$\mathbf y$: here: the 0/1 labels, 1 if the order was late
$S$: diagonal matrix of per-order weights $p_i(1 - p_i)$ : most weight on unsure predictions
$p_i$: the predicted probability that order $i$ is late
$\sigma$: the sigmoid: squashes a score into a probability between 0 and 1
$\mathbf x_i$: order $i$ 's feature vector (row $i$ of $X$ )

Smoothness, strong convexity, condition number

\mu I \preceq \nabla^2 L(\mathbf w) \preceq L\,I, \qquad \kappa = \frac{L}{\mu} = \frac{\lambda_{\max}}{\lambda_{\min}}, \qquad \text{two standardized features with correlation } r:\; \kappa = \frac{1 + r}{1 - r}, \qquad \text{ridge } \tfrac\lambda2\lVert\mathbf w\rVert^2:\; \kappa_\lambda = \frac{\lambda_{\max} + \lambda}{\lambda_{\min} + \lambda}

$\mu$: strong-convexity constant: the smallest curvature of the loss (5/3 on the toy)
$I$: the identity matrix: curvature 1 in every direction
$\preceq$: matrix "at most": the gap is a curvature ≥ 0 in every direction
$\nabla^2 L(\mathbf w)$: the Hessian at $\mathbf w$ : all second derivatives of the loss
$L$: with an argument, the loss; bare, the smoothness constant: largest curvature (5 on the toy)
$\kappa$: condition number: largest over smallest curvature; how stretched the bowl is
$\lambda_{\max}$: the Hessian's largest eigenvalue: curvature along the steepest axis
$\lambda_{\min}$: the smallest eigenvalue: curvature along the flattest axis
$r$: the correlation between the two features (0.5 on the toy)
$\lambda$: here: the ridge penalty strength, not an eigenvalue
$\lVert\mathbf w\rVert^2$: squared length of the weight vector: sum of squared weights
$\kappa_\lambda$: the condition number after adding the ridge penalty
$\tfrac\lambda2$: half the ridge strength (the ½ cancels the 2 from differentiating)

Step size and rates

Descent lemma

L(\mathbf w - \eta\nabla L) \le L(\mathbf w) - \eta\Big(1 - \frac{L\eta}{2}\Big)\lVert\nabla L\rVert^2, \qquad \eta = \frac1L:\;\; \text{drop} \ge \frac{\lVert\nabla L\rVert^2}{2L}

$\eta$: the step size (learning rate)
$L(\mathbf w - \eta\nabla L)$: the loss after one gradient-descent step
$\lVert\nabla L\rVert^2$: squared length of the gradient: sum of squared slopes
$\frac1L$: the step $1/L$ : one over the largest curvature

GD on a quadratic, one eigen-mode at a time

z_{k,i} = (1 - \eta\lambda_i)^k z_{0,i}, \qquad \text{converges} \iff 0 < \eta < \frac{2}{\lambda_{\max}}, \qquad \text{no oscillation} \iff \eta \le \frac{1}{\lambda_{\max}}

$z_{k,i}$: the error along eigen-axis $i$ after $k$ steps
$z_{0,i}$: the starting error along axis $i$
$\lambda_i$: the curvature (eigenvalue of $H$ ) along axis $i$
$k$: the number of steps taken

Best fixed step and its rate

\eta^\star = \frac{2}{\lambda_{\max} + \lambda_{\min}}, \qquad \rho^\star = \frac{\kappa - 1}{\kappa + 1}, \qquad \eta = \frac{1}{\lambda_{\max}} \Rightarrow \rho = 1 - \frac1\kappa

$\eta^\star$: the best fixed step size
$\rho^\star$: the rate at that step: the error shrinks by this factor each step
$\rho$: the rate (per-step shrink factor) at a given step size
$\frac1\kappa$: one over the condition number

Iterations to accuracy $\varepsilon$

k = \frac{\ln(1/\varepsilon)}{\ln(1/\rho)} \le \frac\kappa2\ln\frac1\varepsilon \quad(\text{distance at } \eta^\star;\ \text{the loss needs about half, since it shrinks by } \rho^2)

$\varepsilon$: the target accuracy: the fraction of the starting error allowed to remain
$\frac\kappa2$: half the condition number
$\frac1\varepsilon$: one over the target accuracy (e.g. $10^6$ )

PL inequality and the linear rate

\lVert\nabla L(\mathbf w)\rVert^2 \ge 2\mu\big(L(\mathbf w) - L^\star\big) \;\Rightarrow\; L(\mathbf w_k) - L^\star \le \Big(1 - \frac{\mu}{L}\Big)^k\big(L(\mathbf w_0) - L^\star\big) \quad(\eta = 1/L)

$L^\star$: the lowest possible loss
$L(\mathbf w) - L^\star$: the excess loss: how far above the best loss we are
$\mathbf w_k$: the weights after $k$ steps
$\mathbf w_0$: the starting weights

Convex and smooth: the sublinear rate; non-convex: a small gradient, not a minimum

L(\mathbf w_k) - L^\star \le \frac{L\,\lVert\mathbf w_0 - \mathbf w^\star\rVert^2}{2k} \quad(\eta = 1/L)

$\mathbf w^\star$: the optimal weights (star = the optimum)
$\lVert\mathbf w_0 - \mathbf w^\star\rVert^2$: squared distance from the start to the optimum

\min_{j<k}\lVert\nabla L(\mathbf w_j)\rVert^2 \le \frac{2L\,\big(L(\mathbf w_0) - L^\star\big)}{k} \quad(\eta = 1/L) \;\Rightarrow\; O(1/\varepsilon^2) \text{ steps to } \lVert\nabla L\rVert \le \varepsilon

$\min_{j<k}$: the smallest over all steps $j$ before step $k$
$\mathbf w_j$: the weights at step $j$
$O$: big-O: grows like what's inside, ignoring constant factors
$\varepsilon$: here: the target size for the gradient's length

Rates at a glance

\begin{aligned} \text{GD, strongly convex:}&\quad (1 - 1/\kappa)^k &&\text{linear}\\ \text{Heavy ball (quadratic) / Nesterov:}&\quad \Big(\tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\Big)^k \,/\, (1 - 1/\sqrt\kappa)^k &&\text{linear, } \sqrt\kappa \text{ faster}\\ \text{GD, convex, smooth:}&\quad O(1/k) &&\text{sublinear}\\ \text{Subgradient, convex, non-smooth:}&\quad O(1/\sqrt k) &&\text{sublinear}\\ \text{SGD, strongly convex, } \eta_t = c/t \;(2c\mu > 1):&\quad O(1/t) &&\text{sublinear}\\ \text{SGD, convex:}&\quad O(1/\sqrt t) &&\text{sublinear}\\ \text{Newton, near a non-degenerate minimum:}&\quad \lVert\mathbf e_{k+1}\rVert \le C\,\lVert\mathbf e_k\rVert^2 &&\text{quadratic} \end{aligned}

$\eta_t$: the step size at step $t$
$t$: the step number (SGD's usual letter)
$c$: the constant in the decaying step $\eta_t = c/t$
$\mathbf e$: the error vector $\mathbf w - \mathbf w^\star$ ; subscript = step
$C$: a constant set by the loss's third derivatives near the minimum
$\sqrt\kappa$: square root of the condition number: what momentum improves the rate to
$\sqrt k$: the square root of the step count
$\sqrt t$: the square root of the step number

Stochastic gradients

Minibatch gradient: mean and variance

\mathbb E[\mathbf g_B] = \nabla L, \qquad \mathbb E\lVert\mathbf g_B - \nabla L\rVert^2 = \frac{\operatorname{tr}\Sigma}{B}\;\;(\text{with replacement}), \qquad \frac{\operatorname{tr}\Sigma}{B}\cdot\frac{N - B}{N - 1}\;\;(\text{without})

$\mathbb E$: expectation: the average over all the ways the minibatch could be drawn
$\mathbf g_B$: the minibatch gradient: average gradient over $B$ randomly drawn orders
$B$: the minibatch size
$\Sigma$: covariance of one order's gradient around the full gradient
$\operatorname{tr}\Sigma$: its trace: total gradient variance, summed over all weights
$N$: the number of training rows (orders)

SGD's noise floor (constant $\eta$ )

\mathbb E[L] - L^\star = \frac{\eta\,\sigma^2}{2B(2 - \eta\lambda)} \approx \frac{\eta\,\sigma^2}{4B} \;\;(\text{one mode}), \qquad \approx \frac{\eta}{4B}\operatorname{tr}\Sigma(\mathbf w^\star) \;\;(\text{all modes, small } \eta)

$\mathbb E[L]$: the average loss SGD hovers at, over its random path
$\sigma^2$: the gradient-noise variance of one order along this mode
$\lambda$: here: the curvature of this mode
$\operatorname{tr}\Sigma(\mathbf w^\star)$: total gradient noise at the optimum: left over even where the mean gradient is 0

Robbins–Monro conditions and the $c/t$ schedule

\sum_t \eta_t = \infty, \quad \sum_t \eta_t^2 < \infty; \qquad \eta_t = \frac ct:\;\; \mathbb E[e_t^2] \approx \frac{c^2\sigma^2}{B(2c\lambda - 1)}\cdot\frac1t \;\;(2c\lambda > 1), \quad \propto t^{-2c\lambda} \;\;(2c\lambda < 1)

$\sum_t$: add up over all steps $t$
$e_t$: the error (distance from the optimum) along one mode at step $t$
$\frac ct$: the decaying step: the constant $c$ over the step number $t$
$\frac1t$: one over the step number

Linear scaling rule and the critical batch size

(B, \eta) \to (kB, k\eta) \text{ keeps } \frac{\eta}{B} \text{ fixed while } k\eta < \frac{2}{\lambda_{\max}}, \qquad B_{\text{noise}} = \frac{\operatorname{tr}\Sigma}{\lVert\nabla L\rVert^2}, \qquad \text{steps} \propto 1 + \frac{B_{\text{noise}}}{B}

$k$: here: the factor both batch size and step are scaled by
$B_{\text{noise}}$: the critical batch size: beyond it, bigger batches stop saving steps

Momentum and adaptive methods

Heavy ball and Nesterov

\begin{aligned} \text{Heavy ball:}&\quad \mathbf v_{k+1} = \beta\mathbf v_k + \nabla L(\mathbf w_k), \quad \mathbf w_{k+1} = \mathbf w_k - \eta\mathbf v_{k+1}, \quad \text{steady step } \frac{\eta}{1 - \beta}\lVert\nabla L\rVert,\ \text{window} \approx \frac{1}{1 - \beta}\\ \text{Nesterov:}&\quad \mathbf v_{k+1} = \beta\mathbf v_k + \nabla L(\mathbf w_k - \eta\beta\mathbf v_k), \quad \mathbf w_{k+1} = \mathbf w_k - \eta\mathbf v_{k+1} \end{aligned}

$\mathbf v$: the momentum buffer (velocity): a decaying sum of past gradients
$\beta$: the momentum coefficient: share of the buffer kept each step (e.g. 0.9)
$\nabla L(\mathbf w_k - \eta\beta\mathbf v_k)$: Nesterov's look-ahead gradient, taken where momentum is about to carry you

Optimal heavy ball on a quadratic

\eta^\star = \frac{4}{(\sqrt{L} + \sqrt{\mu})^2}, \qquad \beta^\star = \Big(\frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\Big)^2, \qquad \rho = \sqrt{\beta^\star} = \frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}

$\eta^\star$: here: the best step size for heavy ball
$\beta^\star$: the best momentum coefficient
$\rho$: here: heavy ball's rate, the error's shrink factor per step

Adam with bias correction

\mathbf m_t = \beta_1\mathbf m_{t-1} + (1 - \beta_1)\mathbf g_t, \quad \mathbf v_t = \beta_2\mathbf v_{t-1} + (1 - \beta_2)\mathbf g_t^2, \quad \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}, \quad \mathbf w_t = \mathbf w_{t-1} - \eta\,\frac{\hat{\mathbf m}_t}{\sqrt{\hat{\mathbf v}_t} + \epsilon}

$\mathbf m$: Adam's first moment: running average of the gradients (the direction)
$\mathbf v$: here: Adam's second moment: running average of squared gradients
$\mathbf g_t$: the minibatch gradient at step $t$ (squared entry by entry in $\mathbf v_t$ )
$\beta_1$: the first moment's decay rate (typically 0.9)
$\beta_2$: the second moment's decay rate (typically 0.999)
$\hat{\mathbf m}_t$: the bias-corrected first moment (hat = corrected estimate)
$\hat{\mathbf v}_t$: the bias-corrected second moment
$\epsilon$: a tiny constant (like $10^{-8}$ ) that prevents dividing by zero

L2 penalty vs decoupled weight decay (AdamW)

\text{Adam + L2: } \mathbf g_t = \nabla L + \lambda\mathbf w \text{ enters } \mathbf m, \mathbf v; \qquad \text{AdamW: } \mathbf w_t = (1 - \eta\lambda)\,\mathbf w_{t-1} - \eta\,\frac{\hat{\mathbf m}_t}{\sqrt{\hat{\mathbf v}_t} + \epsilon} \;\;(\mathbf g_t = \nabla L)

$\lambda$: here: the weight-decay (L2 penalty) strength

Second-order methods

Newton's step

\mathbf w_{k+1} = \mathbf w_k - H(\mathbf w_k)^{-1}\nabla L(\mathbf w_k), \qquad |e_{k+1}| \le \frac{M}{2m}\,e_k^2 \;\;(\text{1-D, } f'' \ge m > 0,\ |f'''| \le M)

$H(\mathbf w_k)^{-1}$: the inverse Hessian at the current weights ( $^{-1}$ = matrix inverse: undoes $H$ )
$e$: the 1-D error: distance from the minimum; subscript = step
$m$: a floor on the curvature $f''$ near the minimum
$M$: a cap on the size of the third derivative $f'''$
$f''$: the second derivative (curvature) of the 1-D loss $f$
$f'''$: the third derivative: how fast the curvature itself changes

Gauss–Newton and IRLS

\text{GN: } \mathbf w^{+} = \mathbf w - (J^\top J)^{-1}J^\top\mathbf r, \qquad \text{IRLS: } \mathbf w^{+} = (X^\top SX)^{-1}X^\top S\,\mathbf z, \quad z_i = \mathbf x_i^\top\mathbf w + \frac{y_i - p_i}{p_i(1 - p_i)}

$\mathbf w^{+}$: the weights after one step
$J$: the Jacobian: how each residual changes with each weight
$J^\top J$: Gauss–Newton's curvature estimate, from first derivatives only
$\mathbf r$: the residuals (misses), one per order
$(X^\top SX)^{-1}$: inverse of the curvature-weighted cross-product matrix
$\mathbf z$: IRLS's working response, one entry per order
$z_i$: order $i$ 's working response: current score plus a scaled residual
$y_i$: order $i$ 's 0/1 label (1 = late)

BFGS: secant condition and inverse-Hessian update

B_{k+1}\mathbf s_k = \mathbf y_k, \qquad \mathbf s_k = \mathbf w_{k+1} - \mathbf w_k, \quad \mathbf y_k = \nabla L_{k+1} - \nabla L_k, \qquad H^{-1}_{k+1} = (I - \rho\,\mathbf s\mathbf y^\top)H^{-1}_k(I - \rho\,\mathbf y\mathbf s^\top) + \rho\,\mathbf s\mathbf s^\top, \quad \rho = \frac{1}{\mathbf y^\top\mathbf s}

$B_{k+1}$: BFGS's Hessian estimate after step $k$ (not a batch size)
$\mathbf s$: the last change in weights; subscript = step
$\mathbf y$: here: the last change in gradient (not the labels); subscript = step
$\nabla L_{k+1}$: the gradient at step $k + 1$
$H^{-1}$: BFGS's running estimate of the inverse Hessian; subscript = step
$\rho$: here: the scaling $1/(\mathbf y^\top\mathbf s)$ , not a rate

In words: BFGS keeps an estimate of $H^{-1}$ that agrees with the most recent change in gradient per change in weights; L-BFGS stores only the last $m$ pairs $(s, y)$ , typically 5–20, and never forms the matrix.

Landscapes and constraints

Stationary points and saddle escape

\nabla L = \mathbf 0:\;\; L(\mathbf w + \mathbf d) \approx L(\mathbf w) + \tfrac12\sum_i\lambda_i z_i^2; \qquad \text{GD along } \lambda < 0:\;\; k_{\text{escape}} \approx \frac{\ln(z_{\text{target}}/z_0)}{\ln(1 + \eta|\lambda|)}

$\mathbf d$: a small step away from the stationary point
$L(\mathbf w + \mathbf d)$: the loss after that small step
$z_i$: here: the step's component along eigen-axis $i$
$\lambda$: here: a negative eigenvalue, the curvature along a downhill-bending axis
$k_{\text{escape}}$: the number of steps GD needs to leave the saddle
$z_{\text{target}}$: the distance from the saddle that counts as escaped
$z_0$: the starting distance along that axis
$\sum_i$: add up over the Hessian's eigen-axes $i$

Stability selection and GD's implicit gradient penalty

\text{GD can settle at } \mathbf w^\star \text{ only if } \lambda_{\max}\big(H(\mathbf w^\star)\big) < \frac{2}{\eta}, \qquad \text{GD follows the flow of } \tilde L = L + \frac{\eta}{4}\lVert\nabla L\rVert^2 \;\text{to second order}

$H(\mathbf w^\star)$: the Hessian at the minimum $\mathbf w^\star$
$\tilde L$: the modified loss GD actually follows (tilde = modified)

Lagrangian and KKT (for $g(w) \le 0$ )

\nabla L(\mathbf w) + \mu\nabla g(\mathbf w) = \mathbf 0, \qquad g(\mathbf w) \le 0, \qquad \mu \ge 0, \qquad \mu\,g(\mathbf w) = 0, \qquad \frac{dL^\star}{dc} = -\mu \;\;(\text{for } g = h(\mathbf w) - c)

$\mu$: here: the Lagrange multiplier, the constraint's price
$g(\mathbf w)$: the constraint function: allowed weights have $g(\mathbf w) \le 0$
$\frac{dL^\star}{dc}$: how fast the best loss changes as you loosen the cap $c$ : a slope, not a fraction to divide
$c$: here: the cap in the constraint
$h(\mathbf w)$: the constrained quantity, capped at $c$
$g$: the constraint, written without its argument

Proximal operators: soft-thresholding, ISTA, projection

\text{prox}_{t|\cdot|}(z) = \text{sign}(z)\max(|z| - t,\, 0), \qquad \mathbf w^{+} = \text{prox}_{\eta\lambda\lVert\cdot\rVert_1}\big(\mathbf w - \eta\nabla f(\mathbf w)\big), \qquad \text{prox}_{\iota_C} = \Pi_C, \qquad \text{prox}_{\frac t2\lVert\cdot\rVert^2}(\mathbf z) = \frac{\mathbf z}{1 + t}

$\text{prox}_{t|\cdot|}(z)$: the prox of $t|\cdot|$ : the point near $z$ that also keeps $t|w|$ small
$z$: the input value being shrunk
$t$: here: the threshold, how far toward 0 the input is pulled
$\text{sign}$: +1 for a positive input, −1 for a negative one
$\text{prox}_{\eta\lambda\lVert\cdot\rVert_1}$: the prox of the L1 penalty at strength $\eta\lambda$ : soft-thresholding
$\lambda$: here: the lasso (L1) penalty strength
$f$: the smooth part of the loss (the squared error)
$\text{prox}_{\iota_C}$: the prox of $\iota_C$ , the set's indicator (0 inside $C$ , ∞ outside)
$\Pi_C$: projection: the nearest point inside the allowed set $C$
$\text{prox}_{\frac t2\lVert\cdot\rVert^2}(\mathbf z)$: the prox of a squared L2 penalty: shrinks $\mathbf z$ toward 0
$\mathbf z$: here: the input vector being shrunk

Cards

Stars: ★ = asked often, ★★ = asked at senior level, ★★★ = research level.

Card 1 · Steepest descent is −∇L ★

Statement. Among all directions of unit length, the loss falls fastest along the negative gradient, and its slope there is $-\lVert \nabla L\rVert$ . So a small step $w - \eta\nabla L$ lowers the loss by about $\eta\lVert \nabla L\rVert ^{2}$ .

\min_{\lVert\mathbf u\rVert = 1}\;\nabla L(\mathbf w)^\top\mathbf u = -\lVert\nabla L(\mathbf w)\rVert \quad\text{at}\quad \mathbf u^\star = -\frac{\nabla L(\mathbf w)}{\lVert\nabla L(\mathbf w)\rVert}

$\min_{\lVert\mathbf u\rVert = 1}$: the smallest value over all directions of length 1 (‖·‖ = length)
$\mathbf u$: a direction of unit length in weight space (bold = vector)
$\nabla L(\mathbf w)$: the gradient at $\mathbf w$ : one slope per weight; points uphill
$\mathbf w$: the weight vector $(w_{\text{km}}, w_{\text{items}})$ of the six-order ETA toy
$L$: with an argument, the loss; bare, the smoothness constant: largest curvature (5 on the toy)
$\nabla L(\mathbf w)^\top\mathbf u$: the slope of the loss along $\mathbf u$ (⊤ = transpose, making a dot product)
$\lVert\nabla L(\mathbf w)\rVert$: the gradient's length
$\mathbf u^\star$: the steepest-downhill direction (star = the optimum)

Derivation.

First-order Taylor: the slope of the loss along a unit direction $u$ (the directional derivative) is the dot product of the gradient with $u$ .

D_{\mathbf u}L(\mathbf w) = \lim_{t\to 0}\frac{L(\mathbf w + t\mathbf u) - L(\mathbf w)}{t} = \nabla L(\mathbf w)^\top\mathbf u

$D_{\mathbf u}L(\mathbf w)$: the directional derivative: how fast the loss changes moving along $\mathbf u$
$L(\mathbf w)$: the loss (mean squared ETA miss) at weights $\mathbf w$
$t$: a small distance moved along $\mathbf u$
$L(\mathbf w + t\mathbf u)$: the loss after moving distance $t$ along $\mathbf u$

Cauchy–Schwarz bounds any dot product by the product of the lengths, so no unit direction can do better than $-\lVert \nabla L\rVert$ .

\nabla L^\top\mathbf u \;\ge\; -\lVert\nabla L\rVert\,\lVert\mathbf u\rVert = -\lVert\nabla L\rVert

$\nabla L$: the gradient, argument dropped
$\lVert\nabla L\rVert$: the gradient's length
$\lVert\mathbf u\rVert$: the length of $\mathbf u$ , which is 1

Equality in Cauchy–Schwarz holds only when the vectors are parallel; here, opposite. Substituting confirms the bound is reached.

\nabla L^\top\Big(-\frac{\nabla L}{\lVert\nabla L\rVert}\Big) = -\frac{\lVert\nabla L\rVert^2}{\lVert\nabla L\rVert} = -\lVert\nabla L\rVert

A step of length $\eta\lVert \nabla L\rVert$ in that direction is the gradient-descent step. Taylor again gives its first-order effect: a decrease of $\eta\lVert \nabla L\rVert ^{2}$ , which beats any second-order term once $\eta$ is small enough.

L(\mathbf w - \eta\nabla L) = L(\mathbf w) - \eta\lVert\nabla L\rVert^2 + O(\eta^2)

$L(\mathbf w - \eta\nabla L)$: the loss after one gradient-descent step
$\eta$: the step size (learning rate)
$O(\eta^2)$: terms that shrink like $\eta^2$ or faster: negligible for small steps

Check on the toy at $w = 0$ . The gradient is (−13.33, −11.67) with length 17.72, so the steepest direction raises both weights. Its slope beats moving along the km axis alone.

\mathbf u^\star = \frac{(13.33,\; 11.67)}{17.72} = (0.753,\; 0.658), \qquad D_{\mathbf u^\star}L = -17.72 \;<\; D_{\mathbf e_1}L = -13.33

$D_{\mathbf u^\star}L$: the loss's slope along the steepest direction, at $w = 0$
$D_{\mathbf e_1}L$: the slope along the km axis alone ( $\mathbf e_1$ = unit vector along km)

"Steepest" depends on how you measure step length. If length is measured as $\sqrt{u^\top Pu}$ for a positive-definite $P$ , the Lagrangian of the same problem gives a preconditioned direction. $P = I$ is gradient descent, $P = H$ is Newton (Card 14), and a diagonal $P$ built from gradient sizes is roughly Adam (Card 12).

\min_{\mathbf u}\;\nabla L^\top\mathbf u \;\;\text{s.t.}\;\; \mathbf u^\top P\,\mathbf u = 1 \;\Rightarrow\; \nabla L + 2\nu P\mathbf u = \mathbf 0 \;\Rightarrow\; \mathbf u^\star \propto -P^{-1}\nabla L

$\min_{\mathbf u}$: the smallest value over all directions $\mathbf u$
$P$: a positive-definite matrix that sets how step length is measured
$\mathbf u^\top P\,\mathbf u$: the squared step length measured with $P$
$\nu$: the Lagrange multiplier for the length constraint
$P^{-1}$: the inverse of $P$ (undoes $P$ ): the preconditioner applied to the gradient

Key move. T (first-order Taylor), then Cauchy–Schwarz.

Common slip. Saying the gradient "points at the minimum". It points steepest uphill locally: on the toy, the direction from 0 to the minimum is $(3, 2)/\sqrt{13}$ , which is not parallel to (13.3, 11.7). A second slip is treating the first-order decrease as the actual decrease; at $\eta = 0.1$ it predicts a loss of 1.94, while the true loss after the step is 9.77 (Card 2 explains the gap).

How it's asked. "Why do we subtract the gradient, and why is that guaranteed to help?" (Q3). Strong answer: Cauchy–Schwarz in one line, the $\eta\lVert \nabla L\rVert ^{2}$ first-order decrease, then "only for small enough $\eta$ : the curvature decides how small (Card 2)". Research-level add: steepest descent is norm-dependent, which is the door to preconditioning, Newton and Adam.

Card 2 · The descent lemma ★★

Statement. If the gradient is L-Lipschitz (no curvature exceeds $L$ in size), a gradient step is guaranteed to lower the loss for any $0 < \eta < 2/L$ , and $\eta = 1/L$ gives the largest guaranteed drop.

L(\mathbf w - \eta\nabla L) \le L(\mathbf w) - \eta\Big(1 - \frac{L\eta}{2}\Big)\lVert\nabla L\rVert^2, \qquad \eta = \frac1L:\;\; L(\mathbf w - \tfrac1L\nabla L) \le L(\mathbf w) - \frac{\lVert\nabla L\rVert^2}{2L}

$L(\mathbf w - \tfrac1L\nabla L)$: the loss after a step of size $1/L$
$\lVert\nabla L\rVert^2$: the squared gradient length: sum of squared slopes
$\frac1L$: the step $1/L$ : one over the largest curvature
$\tfrac1L$: the step $1/L$ , written small

Derivation.

Smoothness means the gradient can't change faster than $L$ per unit of distance. For a twice-differentiable loss, that is the same as every Hessian eigenvalue lying between $-L$ and $L$ ; for a convex loss, simply at most $L$ . The lemma below uses only the upper side.

\lVert\nabla L(\mathbf v) - \nabla L(\mathbf w)\rVert \le L\,\lVert\mathbf v - \mathbf w\rVert \quad\text{for all } \mathbf v, \mathbf w

$\mathbf v$: any other weight vector
$\lVert\mathbf v - \mathbf w\rVert$: the distance between the two weight vectors

Write the exact change in loss along the segment from $w$ to $v$ (the fundamental theorem of calculus).

L(\mathbf v) - L(\mathbf w) = \int_0^1 \nabla L\big(\mathbf w + t(\mathbf v - \mathbf w)\big)^\top(\mathbf v - \mathbf w)\,dt

$L(\mathbf v)$: the loss at $\mathbf v$
$t$: here: the fraction of the way from $\mathbf w$ to $\mathbf v$ , 0 to 1
$\int_0^1$: add up continuously over $t$ from 0 to 1
$dt$: a tiny slice of $t$ (the integration variable)

Subtract the tangent-line prediction $\nabla L(w)^\top(v - w)$ from both sides, then bound the leftover with Cauchy–Schwarz and smoothness: at fraction $t$ of the way, the gradient has moved by at most $Lt\lVert v - w\rVert$ .

L(\mathbf v) - L(\mathbf w) - \nabla L(\mathbf w)^\top(\mathbf v - \mathbf w) = \int_0^1\big[\nabla L(\mathbf w + t(\mathbf v - \mathbf w)) - \nabla L(\mathbf w)\big]^\top(\mathbf v - \mathbf w)\,dt \le \int_0^1 L\,t\,\lVert\mathbf v - \mathbf w\rVert^2\,dt = \frac L2\lVert\mathbf v - \mathbf w\rVert^2

$\frac L2$: half the smoothness constant: the bounding bowl's curvature over 2

That gives a quadratic upper bound on the loss: a bowl of curvature $L$ sitting on the tangent line, which the loss can never rise above.

L(\mathbf v) \le L(\mathbf w) + \nabla L(\mathbf w)^\top(\mathbf v - \mathbf w) + \frac L2\lVert\mathbf v - \mathbf w\rVert^2

Plug in the gradient step $v = w - \eta\nabla L(w)$ .

L(\mathbf w - \eta\nabla L) \le L(\mathbf w) - \eta\lVert\nabla L\rVert^2 + \frac{L\eta^2}{2}\lVert\nabla L\rVert^2 = L(\mathbf w) - \eta\Big(1 - \frac{L\eta}{2}\Big)\lVert\nabla L\rVert^2

The guaranteed drop $\eta(1 - L\eta/2)\lVert \nabla L\rVert ^{2}$ is positive exactly when $0 < \eta < 2/L$ . Maximize it over $\eta$ by setting its derivative to zero.

\frac{d}{d\eta}\Big[\eta - \frac{L\eta^2}{2}\Big] = 1 - L\eta = 0 \;\Rightarrow\; \eta = \frac1L, \qquad \text{guaranteed drop} = \frac{\lVert\nabla L\rVert^2}{2L}

$\frac{d}{d\eta}$: how fast the bracket changes as you nudge the step size: a slope, not a fraction to divide

Check on the toy at $w = 0$ : $L = 5$ and $\lVert \nabla L\rVert ^{2} = 313.9$ . The lemma promises a drop of at least 31.39; the actual step with $\eta = 1/L = 0.2$ takes the loss from 33.33 to 1.852, a drop of 31.48. The bound is nearly tight because the gradient points almost along the steep eigenvector.

\frac{\lVert\nabla L\rVert^2}{2L} = \frac{313.9}{10} = 31.39 \;\le\; 33.33 - 1.852 = 31.48

Why the first-order prediction in Card 1 over-promised: on a quadratic the second-order term is exact. At $\eta = 0.1$ , the linear model predicts 1.94; adding $\tfrac12\eta^{2}g^\top Hg = \tfrac12(0.01)(1{,}565)$ restores the true 9.77.

L(\mathbf w - \eta\mathbf g) = L(\mathbf w) - \eta\lVert\mathbf g\rVert^2 + \tfrac12\eta^2\mathbf g^\top H\mathbf g = 33.333 - 31.389 + 7.824 = 9.768

$\mathbf g$: the gradient at $w = 0$ : (−13.33, −11.67)
$H$: the Hessian: the toy bowl's curvature matrix
$\mathbf g^\top H\mathbf g$: the curvature along the gradient times its squared length (1,565)

The same inequality makes backtracking (Armijo) line search safe. Accept $\eta$ when the loss drops by at least $c\cdot \eta\lVert \nabla L\rVert ^{2}$ ; by step 5 that holds whenever $1 - L\eta/2 \ge c$ , so halving from any start stops at a step no smaller than $\min(\eta_{0}, (1 - c)/L)$ . On the toy, starting at $\eta = 1$ with $c = 10^{-4}$ , the search rejects 1 and 0.5 and accepts 0.25 (loss 3.76).

\eta\Big(1 - \frac{L\eta}{2}\Big) \ge c\,\eta \iff \eta \le \frac{2(1 - c)}{L}

$c$: Armijo's required fraction of the predicted drop (here $10^{-4}$ )

Key move. T, with the integral form of the remainder (step 3).

Common slip. Reading the lemma as " $\eta$ must be below 1/L". Any $\eta$ below $2/L$ still decreases the loss; $1/L$ only maximizes the guaranteed drop. A second slip is confusing an L-smooth loss (Lipschitz gradient) with a Lipschitz loss.

How it's asked. "Prove gradient descent with step $1/L$ decreases the loss at every step." (Section 2, Q3 follow-up.) Strong answer: the three-line quadratic upper bound, then point out that summing this inequality is how every rate in Card 7 is proved, and that line search is the practical answer when $L$ is unknown.

Card 3 · Convexity tests, and the Hessians of MSE and logistic loss ★

Statement. For a twice-differentiable function, three tests are equivalent: the chord lies above the curve, the tangent lies below it, and the Hessian is positive semi-definite everywhere. MSE and logistic loss both pass.

\underbrace{f(\theta\mathbf w + (1 - \theta)\mathbf v) \le \theta f(\mathbf w) + (1 - \theta)f(\mathbf v)}_{\text{chord above}} \iff \underbrace{f(\mathbf v) \ge f(\mathbf w) + \nabla f(\mathbf w)^\top(\mathbf v - \mathbf w)}_{\text{tangent below}} \iff \underbrace{\nabla^2 f \succeq 0}_{\text{curvature up}}

$f$: any twice-differentiable function of the weights, such as the loss
$\theta$: the mixing fraction between $\mathbf w$ and $\mathbf v$ , from 0 to 1
$\nabla f$: the gradient of $f$ : its vector of slopes
$\nabla^2 f$: the Hessian of $f$ : all its second derivatives
$\succeq$: "is positive semi-definite": curvature ≥ 0 in every direction

H_{\text{MSE}} = \tfrac2n X^\top X, \qquad H_{\text{logistic}} = \tfrac1n X^\top SX, \quad S = \operatorname{diag}\big(p_i(1 - p_i)\big)

$H_{\text{MSE}}$: the Hessian of the mean-squared-error loss
$H_{\text{logistic}}$: the Hessian of the logistic (late-order) loss
$n$: the number of orders
$X$: the feature matrix, one row per order
$X^\top X$: the features' cross-product matrix (⊤ = transpose)
$S$: diagonal matrix of per-order weights $p_i(1 - p_i)$
$p_i$: the predicted probability that order $i$ is late
$\tfrac1n$: the average over the $n$ orders
$\tfrac2n$: the 2 from differentiating the square, averaged over $n$ orders

Derivation.

Chord ⇒ tangent. Take the chord point a fraction $t$ of the way from $w$ to $v$ , rearrange, and let $t \to 0$ ; the left side becomes the directional derivative.

f(\mathbf w + t(\mathbf v - \mathbf w)) \le f(\mathbf w) + t\big(f(\mathbf v) - f(\mathbf w)\big) \;\Rightarrow\; \frac{f(\mathbf w + t(\mathbf v - \mathbf w)) - f(\mathbf w)}{t} \le f(\mathbf v) - f(\mathbf w) \;\xrightarrow{\;t \to 0\;}\; \nabla f(\mathbf w)^\top(\mathbf v - \mathbf w) \le f(\mathbf v) - f(\mathbf w)

$\xrightarrow{\;t \to 0\;}$: as $t$ shrinks to 0, the left side becomes the slope toward $\mathbf v$

Tangent ⇒ chord. Let $z = \theta w + (1 - \theta)v$ . Write the tangent inequality at $z$ toward $w$ and toward $v$ , weight them by $\theta$ and $1 - \theta$ , and add. The gradient terms cancel because $\theta(w - z) + (1 - \theta)(v - z) = 0$ .

\theta f(\mathbf w) + (1 - \theta)f(\mathbf v) \ge f(\mathbf z) + \nabla f(\mathbf z)^\top\big[\theta(\mathbf w - \mathbf z) + (1 - \theta)(\mathbf v - \mathbf z)\big] = f(\mathbf z)

$\mathbf z$: the mixed point $\theta\mathbf w + (1 - \theta)\mathbf v$ on the chord

Curvature up ⇒ tangent. Second-order Taylor with the exact (Lagrange) remainder at some point $\xi$ on the segment; a PSD Hessian makes the remainder non-negative.

f(\mathbf v) = f(\mathbf w) + \nabla f(\mathbf w)^\top(\mathbf v - \mathbf w) + \tfrac12(\mathbf v - \mathbf w)^\top\nabla^2 f(\boldsymbol\xi)(\mathbf v - \mathbf w) \;\ge\; f(\mathbf w) + \nabla f(\mathbf w)^\top(\mathbf v - \mathbf w)

$\boldsymbol\xi$: some point on the segment from $\mathbf w$ to $\mathbf v$ (Taylor's exact remainder)

Tangent ⇒ curvature up. Write the tangent inequality at $w$ toward $v$ and at $v$ toward $w$ , and add: the gradient is monotone. Put $v = w + td$ , divide by $t^{2}$ , and let $t \to 0$ .

\big(\nabla f(\mathbf v) - \nabla f(\mathbf w)\big)^\top(\mathbf v - \mathbf w) \ge 0 \;\xrightarrow{\;\mathbf v = \mathbf w + t\mathbf d,\;\; \div\, t^2,\;\; t \to 0\;}\; \mathbf d^\top\nabla^2 f(\mathbf w)\,\mathbf d \ge 0

$\mathbf d$: any direction in weight space
$\xrightarrow{\;\mathbf v = \mathbf w + t\mathbf d,\;\; \div\, t^2,\;\; t \to 0\;}$: substitute, divide by $t^2$ , and shrink $t$ to 0

MSE. Differentiate twice. The quadratic form is a squared length, so it is never negative; it is strictly positive for every $d \ne 0$ exactly when $X$ has full column rank, which makes the loss strongly convex with a unique minimum.

\nabla L = -\tfrac2n X^\top(\mathbf y - X\mathbf w), \qquad \nabla^2 L = \tfrac2n X^\top X, \qquad \mathbf d^\top\big(\tfrac2n X^\top X\big)\mathbf d = \tfrac2n\lVert X\mathbf d\rVert^2 \ge 0

$\mathbf y$: the vector of actual delivery times
$\nabla^2 L$: the Hessian of the loss: all its second derivatives
$\lVert X\mathbf d\rVert^2$: the squared length of $X\mathbf d$ : never negative

Toy check: $H = (1/3)[[10, 5], [5, 10]]$ has eigenvalues 5 and 5/3, both positive, so $\mu = 5/3$ and the bowl has one bottom at (3, 2).
Logistic loss, one example. With score $z = x^\top w$ and $p = \sigma(z)$ , use $\sigma' = \sigma(1 - \sigma)$ . The derivative with respect to the score collapses to "prediction minus label".

\ell(z) = -y\log\sigma(z) - (1 - y)\log\big(1 - \sigma(z)\big), \qquad \frac{d\ell}{dz} = -y(1 - \sigma) + (1 - y)\,\sigma = \sigma(z) - y, \qquad \frac{d^2\ell}{dz^2} = \sigma(1 - \sigma) > 0

$\ell(z)$: one order's logistic loss, as a function of its score
$z$: the order's score $\mathbf x^\top\mathbf w$
$y$: the order's label: 1 if late, 0 if on time
$\sigma$: the sigmoid, turning a score into a late-probability
$\frac{d\ell}{dz}$: how fast the loss changes as you nudge the score $z$ : a slope, not a fraction
$\frac{d^2\ell}{dz^2}$: the loss's curvature in the score

Chain rule through $z = x^\top w$ (an affine map), then average over examples. Each term in the quadratic form is a non-negative weight times a square.

\nabla L = \frac1n\sum_i (p_i - y_i)\,\mathbf x_i = \frac1n X^\top(\mathbf p - \mathbf y), \qquad \nabla^2 L = \frac1n\sum_i p_i(1 - p_i)\,\mathbf x_i\mathbf x_i^\top = \frac1n X^\top SX, \qquad \mathbf d^\top\nabla^2 L\,\mathbf d = \frac1n\sum_i p_i(1 - p_i)(\mathbf x_i^\top\mathbf d)^2 \ge 0

$\sum_i$: add up over every order $i$
$y_i$: order $i$ 's label (1 = late)
$\mathbf x_i$: order $i$ 's feature vector
$\mathbf p$: the vector of predicted late-probabilities
$\mathbf y$: here: the vector of 0/1 late labels
$\frac1n$: the average over the $n$ orders

That is the SAM hook in action: each $\ell$ is convex in its score, the score is an Affine function of $w$ , and a non-negative Sum of convex functions is convex. Check on the late-order model (standardized km and items): the Hessian at the MLE has eigenvalues 0.0753, 0.0326 and 0.00273, all positive, $\kappa = 27.5$ . The weights $p(1 - p)$ vanish as predictions approach 0 or 1, so logistic loss is convex but not strongly convex everywhere; on separable data no minimizer exists (Ch 3).
The trap: squared error on a sigmoid output is not convex. Take $y = 0$ , so the per-example loss is $\sigma(z)^{2}$ , and use $\sigma'' = \sigma'(1 - 2\sigma)$ .

\frac{d^2}{dz^2}\,\sigma(z)^2 = 2\sigma'^2 + 2\sigma\sigma'' = 2\sigma'\sigma\big[(1 - \sigma) + (1 - 2\sigma)\big] = 2\sigma'\sigma\,(2 - 3\sigma) < 0 \quad\text{when } \sigma > \tfrac23

$\frac{d^2}{dz^2}$: the second derivative (curvature) with respect to the score $z$
$\sigma(z)^2$: squared error on a sigmoid output when the label is 0
$\sigma'$: the sigmoid's slope, $\sigma(1 - \sigma)$
$\sigma''$: the sigmoid's second derivative, $\sigma'(1 - 2\sigma)$

Because the score is linear in $w$ , the loss along any line through weight space has this shape, so it is non-convex in $w$ .

Key move. T (first and second order); SAM for the logistic case.

Common slip. Checking convexity in the inputs instead of the weights. Also: dropping $S$ and writing the logistic Hessian as $X^\top X$ , or claiming logistic loss is strongly convex.

How it's asked. "Show that the MSE and logistic losses are convex in $w$ . Is MSE on a sigmoid output convex?" (Q16; also Q6.) Strong answer: Hessian PSD for both, the sign change at $\sigma = 2/3$ for the trap, and the remark that $X^\top SX$ is exactly the weighted design matrix IRLS solves with (Card 14).

Card 4 · For a convex function, local = global ★

Statement. For a convex function every local minimum is a global minimum, the set of minimizers is convex, a strictly convex function has at most one minimizer, and for a differentiable convex function any point with zero gradient is a global minimum.

f \text{ convex},\;\; \mathbf w_0 \text{ a local min} \;\Rightarrow\; f(\mathbf w_0) \le f(\mathbf v) \;\;\forall\,\mathbf v

$\mathbf w_0$: a local minimum: no nearby point is lower

Derivation.

Suppose $w_{0}$ is a local minimum: no point within distance $r$ is lower. Suppose, for contradiction, some $w_{1}$ anywhere is strictly lower.

f(\mathbf w_0) \le f(\mathbf w) \;\;\text{whenever } \lVert\mathbf w - \mathbf w_0\rVert < r, \qquad f(\mathbf w_1) < f(\mathbf w_0)

$r$: the radius of the neighborhood where $\mathbf w_0$ is lowest
$\mathbf w_1$: a hypothetical point, anywhere, that is strictly lower

Walk along the chord from $w_{0}$ toward $w_{1}$ . Convexity (chord above) puts every point of it strictly below $f(w_{0})$ .

\mathbf z_t = (1 - t)\mathbf w_0 + t\,\mathbf w_1: \qquad f(\mathbf z_t) \le (1 - t)f(\mathbf w_0) + t\,f(\mathbf w_1) < f(\mathbf w_0) \quad\text{for every } t \in (0, 1]

$\mathbf z_t$: the point a fraction $t$ of the way from $\mathbf w_0$ to $\mathbf w_1$

For small enough $t$ , $z_t$ lies inside the radius $r$ , contradicting step 1. So no lower $w_{1}$ exists.

t < \frac{r}{\lVert\mathbf w_1 - \mathbf w_0\rVert} \;\Rightarrow\; \lVert\mathbf z_t - \mathbf w_0\rVert = t\,\lVert\mathbf w_1 - \mathbf w_0\rVert < r \;\text{ and }\; f(\mathbf z_t) < f(\mathbf w_0)

The minimizers form a convex set: if $w_{0}$ and $w_{1}$ both reach $f^*$ , the chord inequality gives $f(z_t) \le f^*$ , so every point between them is a minimizer too.

f(\mathbf z_t) \le (1 - t)f^\star + t f^\star = f^\star \;\Rightarrow\; f(\mathbf z_t) = f^\star

$f^\star$: the minimum value of $f$

Strict convexity (strict chord inequality for $w \ne v$ ) rules out two distinct minimizers: their midpoint would be lower than the minimum.

f\big(\tfrac12\mathbf w_0 + \tfrac12\mathbf w_1\big) < \tfrac12 f^\star + \tfrac12 f^\star = f^\star

Zero gradient ⇒ global minimum, from the tangent test (Card 3).

\nabla f(\mathbf w) = \mathbf 0 \;\Rightarrow\; f(\mathbf v) \ge f(\mathbf w) + \mathbf 0^\top(\mathbf v - \mathbf w) = f(\mathbf w) \quad\forall\,\mathbf v

Check on the toy: $H$ is positive definite ( $\mu = 5/3$ ), so the loss is strictly convex and (3, 2) is its only minimum; gradient descent from any start with a stable $\eta$ lands there. The underdetermined toy of Card 18 (10 weights, 6 orders) is convex but not strictly: a whole flat valley of weight vectors all reach the same zero training loss.

Key move. The chord inequality itself (the definition of convexity); T for step 6.

Common slip. "Convex means a unique minimum" (that needs strict convexity) and "convex means a minimum exists". The function $e^{w}$ is convex with no minimizer, and logistic loss on perfectly separable data keeps falling as $\lVert w\rVert \to \infty$ (Q37).

How it's asked. "A teammate worries our linear ETA model could get stuck in a local minimum like their neural nets. Convince them it can't." (Q6, Q16.) Strong answer: the three-line chord proof, plus the two caveats (existence, uniqueness) and the reminder that convexity is in the weights.

Card 5 · GD on a quadratic in the eigenbasis ★

Statement. On a quadratic loss the error $e = w - w^*$ evolves as a matrix power. In the Hessian's eigenbasis each coordinate shrinks independently by $(1 - \eta\lambda_{i})$ per step, so gradient descent converges from every start if and only if $0 < \eta < 2/\lambda_{\max}$ .

\mathbf e_k = (I - \eta H)^k\,\mathbf e_0, \qquad z_{k,i} = (1 - \eta\lambda_i)^k z_{0,i}, \qquad \text{converges for every start} \iff 0 < \eta < \frac{2}{\lambda_{\max}}

$\mathbf e$: the error vector: current weights minus the optimum; subscript = step
$I$: the identity matrix
$k$: the number of steps
$z_{k,i}$: the error along eigen-axis $i$ after $k$ steps
$z_{0,i}$: the starting error along axis $i$
$\lambda_i$: the curvature (eigenvalue of $H$ ) along axis $i$
$\lambda_{\max}$: the largest eigenvalue: the steepest axis's curvature

Derivation.

MSE is exactly a quadratic around its minimum. Write $y - Xw = r^* - Xe$ , where $r^*$ is the residual at $w^*$ . The cross term vanishes because the residual is orthogonal to every column ( $X^\top r^* = 0$ , the normal equation; Ch 1, Section 3).

L(\mathbf w) = \tfrac1n\lVert\mathbf r^\star - X\mathbf e\rVert^2 = \tfrac1n\lVert\mathbf r^\star\rVert^2 - \tfrac2n\mathbf e^\top\underbrace{X^\top\mathbf r^\star}_{=\,\mathbf 0} + \tfrac1n\lVert X\mathbf e\rVert^2 = L^\star + \tfrac12\,\mathbf e^\top H\mathbf e, \qquad \nabla L = H\mathbf e

$\mathbf r^\star$: the residuals (misses) at the optimum $\mathbf w^\star$
$L^\star$: the lowest loss, at the optimum

A gradient step in error coordinates is multiplication by $I - \eta H$ ; unroll it.

\mathbf e_{k+1} = \mathbf e_k - \eta H\mathbf e_k = (I - \eta H)\,\mathbf e_k \;\Rightarrow\; \mathbf e_k = (I - \eta H)^k\,\mathbf e_0

Rotate: with $H = Q\Lambda Q^\top$ and $z = Q^\top e$ , the matrix becomes diagonal, so each eigen-direction ("mode") is its own 1-D problem.

\mathbf z_{k+1} = Q^\top(I - \eta Q\Lambda Q^\top)Q\,\mathbf z_k = (I - \eta\Lambda)\,\mathbf z_k \;\Rightarrow\; z_{k,i} = (1 - \eta\lambda_i)^k z_{0,i}

$Q$: matrix whose columns are $H$ 's eigenvectors (the bowl's axes)
$\Lambda$: diagonal matrix of the eigenvalues $\lambda_i$
$\mathbf z$: the error in eigen-coordinates, $Q^\top\mathbf e$

Read off each mode's fate from its factor $1 - \eta\lambda_{i}$ . The mode with the largest $\lambda$ hits the cliff first, so stability for every start needs $\eta < 2/\lambda_{\max}$ .

1 - \eta\lambda_i \in \begin{cases} (0,\, 1) & \eta < 1/\lambda_i \quad\text{monotone}\\ \{0\} & \eta = 1/\lambda_i \quad\text{done in one step}\\ (-1,\, 0) & 1/\lambda_i < \eta < 2/\lambda_i \quad\text{oscillates, converges}\\ (-\infty,\, -1] & \eta \ge 2/\lambda_i \quad\text{diverges (bounces forever at equality)}\end{cases}

The loss per mode is $\tfrac12\lambda_{i}z_{i}^{2}$ , so each mode's loss shrinks by the square of its factor. That is why "steps to $10^{-6}$ " depends on whether you measure distance or loss: on the raw 10k model it is 991 steps by distance and 496 by loss (Card 7).

L(\mathbf w_k) - L^\star = \tfrac12\sum_i\lambda_i\,(1 - \eta\lambda_i)^{2k}\,z_{0,i}^2

$\mathbf w_k$: the weights after $k$ steps
$\sum_i$: add up over the eigen-axes $i$

Check on the toy. Its Hessian is a scaled correlation matrix with $r = 0.5$ , whose eigenvalues are $1 \pm r$ . That gives $\lambda = 5$ along $(1, 1)/\sqrt{2}$ ("more of both"), $\lambda = 5/3$ along $(1, -1)/\sqrt{2}$ ("trade distance for items"), $\kappa = 3$ and a cliff at 0.4.

H = \tfrac{10}{3}\begin{pmatrix} 1 & \tfrac12\\ \tfrac12 & 1\end{pmatrix}, \qquad \lambda = \tfrac{10}{3}\big(1 \pm \tfrac12\big) = 5,\; \tfrac53, \qquad \kappa = \frac{1 + r}{1 - r} = 3, \qquad \eta_{\max} = \frac25 = 0.4

$\lambda$: the toy Hessian's two eigenvalues
$\kappa$: the condition number $\lambda_{\max}/\lambda_{\min}$ : how stretched the bowl is
$r$: the correlation between km and items on the toy (0.5)
$\eta_{\max}$: the cliff: the largest step that still converges

One step at $\eta = 0.3$ by hand. From $w_{0} = 0$ the error is $e_{0} = (-3, -2)$ , which is $-5/\sqrt{2}$ along the steep axis and $-1/\sqrt{2}$ along the flat one. Both factors have size 0.5 (−0.5 and +0.5).

\mathbf e_1 = (-0.5)\Big(-\tfrac{5}{\sqrt2}\Big)\frac{(1, 1)}{\sqrt2} + (0.5)\Big(-\tfrac{1}{\sqrt2}\Big)\frac{(1, -1)}{\sqrt2} = (1.25,\; 1.25) + (-0.25,\; 0.25) = (1.0,\; 1.5) \;\Rightarrow\; \mathbf w_1 = (4.0,\; 3.5)

$\mathbf w_1$: the weights after one step from $\mathbf w_0 = 0$

The simulation's first iterate at $\eta = 0.3$ is (4.0, 3.5). At $\eta = 0.2 = 1/\lambda_{\max}$ the steep factor is 0, so one step leaves pure flat-mode error and $w_{1} = (2.67, 2.33)$ (Drill 3). At $\eta = 0.41$ the steep factor is −1.05: the iterates bounce (5.47, 4.78), (0.19, −0.71), (5.88, 4.91) and the loss grows every step.

Key move. R, then U.

Common slip. Using the eigenvalues of $X^\top X$ instead of $(2/n)X^\top X$ (the factor $2/n$ is part of the Hessian under this book's $1/n$ MSE convention). Also: thinking $\eta = 2/\lambda_{\max}$ exactly still converges (the factor is −1: it bounces forever), and thinking standardizing removes $\kappa$ (the correlation stays: $\kappa = 3$ on the toy even with equal variances).

How it's asked. "Prove that gradient descent on a quadratic diverges if $\eta > 2/\lambda_{\max}$ ." (Q14; Drills 1, 3; Q4.) Strong answer: rotate, unroll, read off the worst mode; then add that for a non-quadratic loss the same holds locally with the Hessian at the minimum, and quote the hook " $1/\lambda$ smooth, $2/\lambda$ the cliff".

Card 6 · The best fixed step and the (κ − 1)/(κ + 1) rate ★★

Statement. The fixed step that makes the slowest mode as fast as possible balances the flattest and steepest modes, and its rate depends only on the condition number.

\eta^\star = \arg\min_\eta\;\max_i|1 - \eta\lambda_i| = \frac{2}{\lambda_{\max} + \lambda_{\min}}, \qquad \rho^\star = \frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \frac{\kappa - 1}{\kappa + 1}

$\eta^\star$: the best fixed step size
$\arg\min_\eta$: the value of $\eta$ that makes what follows smallest
$\max_i$: the largest over all eigen-axes $i$
$\lambda_{\min}$: the smallest eigenvalue: the flattest axis's curvature
$\rho^\star$: the best rate: the error shrinks by this factor per step

Derivation.

By Card 5, the error after $k$ steps is governed by the worst mode. Because $1 - \eta\lambda$ is linear in $\lambda$ , its absolute value over the interval $[\lambda_{\min}, \lambda_{\max}]$ peaks at an endpoint, so only the two extreme eigenvalues matter.

\rho(\eta) = \max_i|1 - \eta\lambda_i| = \max\big(|1 - \eta\lambda_{\min}|,\; |1 - \eta\lambda_{\max}|\big)

$\rho(\eta)$: the rate at step size $\eta$ : the worst mode's shrink factor

As $\eta$ grows, the flat mode's factor falls toward 0 while the steep mode's factor, once past $1/\lambda_{\max}$ , grows in size on the negative side. The maximum of a falling and a rising function is smallest where they cross: the flat factor positive, the steep factor its mirror image.

1 - \eta\lambda_{\min} = -(1 - \eta\lambda_{\max}) \;\Rightarrow\; \eta^\star = \frac{2}{\lambda_{\max} + \lambda_{\min}}

Substitute back to get the rate, then divide top and bottom by $\lambda_{\min}$ .

\rho^\star = 1 - \frac{2\lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \frac{\kappa - 1}{\kappa + 1}, \qquad \kappa = \frac{\lambda_{\max}}{\lambda_{\min}}

Compare the common default $\eta = 1/\lambda_{\max}$ ( $= 1/L$ ): the steep mode is killed in one step and the flat one shrinks by $1 - 1/\kappa$ . For large $\kappa$ that is about half as fast in log terms, but it needs no knowledge of $\lambda_{\min}$ .

\eta = \frac{1}{\lambda_{\max}} \;\Rightarrow\; \rho = \max\Big(1 - \frac{\lambda_{\min}}{\lambda_{\max}},\; 0\Big) = 1 - \frac1\kappa

$\rho$: the rate at this step size
$\frac1\kappa$: one over the condition number

The best step hugs the cliff. Its ratio to $\eta_{\max} = 2/\lambda_{\max}$ is $\kappa/(\kappa + 1)$ , so for a badly conditioned bowl any overestimate of the step by a fraction of a percent diverges. That is why practitioners keep a margin.

\frac{\eta^\star}{\eta_{\max}} = \frac{\lambda_{\max}}{\lambda_{\max} + \lambda_{\min}} = \frac{\kappa}{\kappa + 1}

Checks. Toy: $\eta^* = 0.3$ with both factors of size 0.5 (the simulation's mode factors at $\eta = 0.3$ are −0.5 and 0.5). Raw 10k model (intercept, km, items): $\lambda = 49.9$ and 0.348, $\kappa = 143$ , $\eta^* = 0.0398$ , just under the cliff at 0.0401, $\rho = 0.986$ . Standardized 10k: $\kappa = 2.15$ , $\eta^* = 0.5$ , $\rho = 0.364$ .

\text{toy: } \eta^\star = \frac{2}{5 + 5/3} = 0.3,\;\; \rho^\star = \frac{3 - 1}{3 + 1} = 0.5 \qquad \text{raw 10k: } \eta^\star = \frac{2}{49.9 + 0.348} = 0.0398,\;\; \rho^\star = \frac{143.4 - 1}{143.4 + 1} = 0.986

Key move. R (only the extreme modes matter), then balance them.

Common slip. Calling $1/\lambda_{\max}$ the optimal step (it is optimal only for killing the steep mode). Computing $\kappa$ from the singular values of $X$ instead of the eigenvalues of $X^\top X$ : forming $X^\top X$ squares the condition number.

How it's asked. "The Hessian's eigenvalues are 50 and 0.5. What fixed step would you use, what rate does it give, and how many steps to shrink the error by $10^{6}$ ?" (Q15, Drill 2.) Answer: $\eta^* = 2/50.5 = 0.0396$ , $\rho = 99/101 = 0.980$ , about 691 steps. Strong answer adds that $\eta^*$ is 1% below the cliff and that momentum improves the rate by a factor of about $\sqrt{\kappa} = 10$ (Card 11). The realized saving is smaller: the simulation needs 93 heavy-ball steps against 691 for GD, 7.4× fewer, because of the $k\cdot \rho^{k}$ transient (Drill 4).

Card 7 · Iteration complexity: linear vs sublinear ★★

Statement. On a strongly convex, smooth loss gradient descent converges linearly: the error shrinks by a constant factor per step, so the step count grows like $\kappa\cdot \ln(1/\varepsilon)$ . Without strong convexity the guarantee is sublinear, $1/k$ . Without convexity at all, only the gradient is guaranteed to shrink: $\min_{j}\lVert \nabla L(w_{j})\rVert ^{2} \le 2L(L(w_{0}) - L^*)/k$ (step 10).

k = \frac{\ln(1/\varepsilon)}{\ln(1/\rho)} \le \frac\kappa2\ln\frac1\varepsilon \;\;(\eta^\star, \text{distance}), \qquad L(\mathbf w_k) - L^\star \le \Big(1 - \frac1\kappa\Big)^k\big(L(\mathbf w_0) - L^\star\big)\;\;(\eta = \tfrac1L), \qquad L(\mathbf w_k) - L^\star \le \frac{L\lVert\mathbf w_0 - \mathbf w^\star\rVert^2}{2k}\;\;(\text{convex})

$k$: the number of steps needed (or taken)
$\varepsilon$: the target accuracy: the fraction of the starting error left
$\mathbf w_0$: the starting weights
$\mathbf w^\star$: the optimal weights (star = the optimum)
$L(\mathbf w_k) - L^\star$: the excess loss after $k$ steps
$\frac\kappa2$: half the condition number
$\frac1\varepsilon$: one over the target accuracy (e.g. $10^6$ )

Derivation.

Distance on a quadratic. Rotation preserves length, so the error norm is bounded by the worst factor to the k-th power. Solve $\rho^{k} \le \varepsilon$ for $k$ .

\lVert\mathbf e_k\rVert = \Big(\sum_i(1 - \eta\lambda_i)^{2k}z_{0,i}^2\Big)^{1/2} \le \rho^k\lVert\mathbf e_0\rVert \le \varepsilon\,\lVert\mathbf e_0\rVert \iff k \ge \frac{\ln(1/\varepsilon)}{\ln(1/\rho)}

$\lVert\mathbf e_k\rVert$: the distance from the optimum after $k$ steps
$\rho$: the per-step shrink factor of the worst mode

With $\rho = (\kappa - 1)/(\kappa + 1)$ , expand the logarithm. Every term is positive, so $\ln(1/\rho) \ge 2/\kappa$ , which turns step 1 into the $\kappa/2$ rule.

\ln\frac1\rho = \ln\frac{1 + 1/\kappa}{1 - 1/\kappa} = 2\Big(\frac1\kappa + \frac{1}{3\kappa^3} + \frac{1}{5\kappa^5} + \dots\Big) \ge \frac2\kappa \;\Rightarrow\; k \le \frac\kappa2\ln\frac1\varepsilon

$\frac1\rho$: one over the rate
$\frac2\kappa$: two over the condition number

Check on the raw 10k model ( $\kappa = 143$ , $\varepsilon = 10^{-6}$ ): the formula gives 991 steps by distance, and the simulation needs exactly 991. The loss shrinks by $\rho^{2}$ per step (Card 5, step 5), so the loss criterion needs half: 495 in theory, 496 in the simulation.

k \approx \frac{143.4}{2}\,\ln 10^{6} = 71.7 \times 13.82 = 991 \;\;(\text{distance}), \qquad \approx 495 \;\;(\text{loss})

Beyond quadratics, start from strong convexity (the loss sits above a bowl of curvature $\mu$ on its tangent) and minimize both sides over $v$ . The right side is smallest at $v = w - \nabla L/\mu$ , and the left side's minimum is $L^*$ . The result is the PL (Polyak–Łojasiewicz) inequality: a large excess loss forces a large gradient.

L(\mathbf v) \ge L(\mathbf w) + \nabla L(\mathbf w)^\top(\mathbf v - \mathbf w) + \frac\mu2\lVert\mathbf v - \mathbf w\rVert^2 \;\xrightarrow{\;\min_{\mathbf v}\;}\; L^\star \ge L(\mathbf w) - \frac{\lVert\nabla L(\mathbf w)\rVert^2}{2\mu}

$\mu$: the strong-convexity constant: the smallest curvature (5/3 on the toy)
$\xrightarrow{\;\min_{\mathbf v}\;}$: minimize both sides over $\mathbf v$
$\frac\mu2$: half the smallest curvature

Combine PL with the descent lemma at $\eta = 1/L$ (Card 2), subtract $L^*$ from both sides, and unroll.

L(\mathbf w_{k+1}) - L^\star \le L(\mathbf w_k) - L^\star - \frac{\lVert\nabla L\rVert^2}{2L} \le \Big(1 - \frac\mu L\Big)\big(L(\mathbf w_k) - L^\star\big) \;\Rightarrow\; L(\mathbf w_k) - L^\star \le \Big(1 - \frac1\kappa\Big)^k\big(L(\mathbf w_0) - L^\star\big)

$\frac\mu L$: smallest over largest curvature, which is $1/\kappa$

Since $\ln(1/(1 - 1/\kappa)) \ge 1/\kappa$ , this needs at most $\kappa\cdot \ln(1/\varepsilon)$ steps. The proof used only the PL inequality, not convexity, which is why some non-convex, overparameterized problems still converge linearly.

Convex but not strongly convex. Use the tangent at $w_{k}$ toward $w^*$ (convexity), then the descent lemma, and complete the square.

L(\mathbf w_{k+1}) - L^\star \le \nabla L^\top(\mathbf w_k - \mathbf w^\star) - \frac{1}{2L}\lVert\nabla L\rVert^2 = \frac L2\Big(\lVert\mathbf w_k - \mathbf w^\star\rVert^2 - \big\lVert\mathbf w_k - \mathbf w^\star - \tfrac1L\nabla L\big\rVert^2\Big) = \frac L2\Big(\lVert\mathbf w_k - \mathbf w^\star\rVert^2 - \lVert\mathbf w_{k+1} - \mathbf w^\star\rVert^2\Big)

Sum over $k$ steps: the right side telescopes. The losses never increase (Card 2), so the last one is at most the average.

k\big(L(\mathbf w_k) - L^\star\big) \le \sum_{j=1}^{k}\big(L(\mathbf w_j) - L^\star\big) \le \frac L2\lVert\mathbf w_0 - \mathbf w^\star\rVert^2 \;\Rightarrow\; L(\mathbf w_k) - L^\star \le \frac{L\,\lVert\mathbf w_0 - \mathbf w^\star\rVert^2}{2k}

$\sum_{j=1}^{k}$: add up over steps $j = 1$ to $k$
$\mathbf w_j$: the weights after step $j$

A flat bottom in action: $f(w) = w^{4}$ has zero curvature at its minimum, so no $\mu$ exists. With $\eta = 0.1$ from $w_{0} = 1$ , the quantity $1/w^{2}$ grows by about $8\eta$ per step.

w_{k+1} = w_k(1 - 4\eta w_k^2) \;\Rightarrow\; \frac{1}{w_{k+1}^2} = \frac{1}{w_k^2(1 - 4\eta w_k^2)^2} \approx \frac{1}{w_k^2} + 8\eta \;\Rightarrow\; w_k \approx \frac{1}{\sqrt{8\eta k}},\quad f(w_k) \approx \frac{1}{64\,\eta^2k^2}

$w$: the single weight of the 1-D example; subscript = step
$f(w_k)$: the loss $w_k^4$ after $k$ steps

The simulation gives $w = 0.303$ , 0.109 and 0.0352 after 10, 100 and 1,000 steps (approximation: 0.354, 0.112, 0.0354), and the log-log slope of the loss is −2.00. That is faster than the worst-case $1/k$ bound, yet still sublinear: there is no constant factor per step.

Worst-case counts are upper bounds; where the initial error sits matters. On the toy at $\eta = 0.1$ the flat factor is 0.833, which suggests about 38 steps for a $10^{6}$ loss reduction, but the simulation needs 27. The flat mode starts with only 0.417 of the 31.67 excess loss, so it needs a smaller reduction.

\underbrace{\tfrac12\cdot 5\cdot\big(\tfrac{5}{\sqrt2}\big)^2}_{\text{steep: } 31.25} + \underbrace{\tfrac12\cdot\tfrac53\cdot\big(\tfrac{1}{\sqrt2}\big)^2}_{\text{flat: } 0.417} = 31.67, \qquad 0.417\times(0.833^2)^k \le 10^{-6}\times 31.67 \iff k \ge 26.01 \;\Rightarrow\; 27 \text{ steps}

At $\eta = 0.3$ both factors have size 0.5, so the loss shrinks by exactly 0.25 per step: $\ln(10^{6})/\ln 4 = 9.97$ , and the simulation takes 10 steps.

No convexity at all. The descent lemma at $\eta = 1/L$ still holds for any L-smooth loss. Rearrange it so each step's squared gradient is paid for by a drop in loss, then sum: the losses telescope, and the total drop can't exceed $L(w_{0}) - L^*$ ( $L^*$ is any lower bound on the loss).

\frac{1}{2L}\lVert\nabla L(\mathbf w_j)\rVert^2 \le L(\mathbf w_j) - L(\mathbf w_{j+1}) \;\Rightarrow\; \frac{k}{2L}\min_{j<k}\lVert\nabla L(\mathbf w_j)\rVert^2 \le \sum_{j=0}^{k-1}\frac{\lVert\nabla L(\mathbf w_j)\rVert^2}{2L} \le L(\mathbf w_0) - L^\star \;\Rightarrow\; \min_{j<k}\lVert\nabla L(\mathbf w_j)\rVert^2 \le \frac{2L\big(L(\mathbf w_0) - L^\star\big)}{k}

$\min_{j<k}$: the smallest over all steps before step $k$
$\sum_{j=0}^{k-1}$: add up over steps $j = 0$ to $k - 1$
$L^\star$: here: any lower bound on the loss
$j$: a step index, from 0 to $k - 1$

So $\lVert \nabla L\rVert \le \varepsilon$ within $2L(L(w_{0}) - L^*)/\varepsilon^{2}$ steps: a nearly stationary point, which may be a saddle or a poor local minimum. Check on the double well $f = w^{4} - 3w^{2} + w$ from $w_{0} = 2$ with $L = 42$ (the largest $\lvert f''\rvert$ on [−2, 2], where GD stays): the bound after 50 steps is 2 · 42 · (6 + 3.514)/50 = 16.0, the smallest squared slope seen is $1.2 \times 10^{-10}$ , and GD has stopped at the local minimum 1.13.

Key move. U for the linear rate, T (via the descent lemma) for the general, convex and non-convex cases.

Common slip. Quoting " $\kappa \log(1/\varepsilon)$ " without saying which step size and which criterion: distance and loss differ by a factor of 2, and $\eta^*$ vs $1/L$ by another. Calling a $1/k^{2}$ curve "linear convergence" because it looks fast. Reading the non-convex bound as "GD finds a minimum": it bounds the smallest gradient seen, nothing more.

How it's asked. "How many steps to reach $10^{-6}$ , and how does that change with $\kappa$ ?" (Q15, WP1.) Strong answer: name the criterion, give $\ln(1/\varepsilon)/\ln(1/\rho)$ and its $\kappa/2$ approximation, then the hook "sublinear crawls, linear adds digits, quadratic doubles them", and the note that the realized count depends on where the initial error sits.

Card 8 · The minibatch gradient: unbiased, variance σ²/B ★

Statement. A gradient averaged over $B$ examples drawn uniformly is an unbiased estimate of the full gradient. Its covariance falls as $1/B$ when drawing with replacement, and by an extra finite-population factor without replacement.

\mathbf g_B = \frac1B\sum_{j=1}^{B}\nabla\ell_{I_j}(\mathbf w): \qquad \mathbb E[\mathbf g_B] = \mathbf G = \nabla L(\mathbf w), \qquad \text{Cov}(\mathbf g_B) = \frac{\Sigma}{B}\;\;(\text{with}), \qquad \frac{\Sigma}{B}\cdot\frac{N - B}{N - 1}\;\;(\text{without})

$\mathbf g_B$: the minibatch gradient: an average over $B$ randomly drawn orders
$B$: the minibatch size
$\sum_{j=1}^{B}$: add up over the $B$ draws
$\nabla\ell_{I_j}$: the gradient of the $j$ -th drawn order's loss ( $I_j$ = its row, uniform at random)
$\mathbb E$: expectation: the average over all the ways the batch could be drawn
$\mathbf G$: the full gradient over all $N$ orders
$\text{Cov}$: covariance matrix: the estimate's spread, per weight and between weights
$\Sigma$: per-order gradient covariance: how much single orders' gradients scatter
$N$: the number of training rows (10,000 orders)
$\frac1B$: the average: divide the sum by the $B$ draws

Here $\Sigma = (1/N)\sum_{i}(\nabla\ell_{i} - G)(\nabla\ell_{i} - G)^\top$ is the per-example gradient covariance over the $N$ training rows.

Derivation.

One uniformly drawn example is unbiased: its expectation is the average over all $N$ rows, which is the full gradient.

\mathbb E[\nabla\ell_I] = \sum_{i=1}^{N}\frac1N\,\nabla\ell_i = \nabla L = \mathbf G

$\nabla\ell_I$: the gradient of one uniformly drawn order's loss
$\nabla\ell_i$: the gradient of order $i$ 's loss
$\sum_{i=1}^{N}$: add up over all $N$ orders
$\frac1N$: each order's chance of being drawn: one in $N$

An average of $B$ such draws is still unbiased, by linearity of expectation.

\mathbb E[\mathbf g_B] = \frac1B\sum_{j=1}^{B}\mathbb E[\nabla\ell_{I_j}] = \mathbf G

With replacement, the draws are independent, so their covariances add and the $1/B^{2}$ from the average leaves $\Sigma/B$ . Taking the trace gives the expected squared error of the estimate.

\text{Cov}(\mathbf g_B) = \frac{1}{B^2}\sum_{j=1}^{B}\text{Cov}(\nabla\ell_{I_j}) = \frac{\Sigma}{B}, \qquad \mathbb E\lVert\mathbf g_B - \mathbf G\rVert^2 = \frac{\operatorname{tr}\Sigma}{B}

$\operatorname{tr}\Sigma$: total gradient variance: the trace (sum of the diagonal) of $\Sigma$

Without replacement, the draws are negatively correlated: drawing a large gradient makes the remaining ones smaller on average. Work with one coordinate of variance $\sigma^{2}$ . If you drew all $N$ rows, the sum would be fixed, so its variance is zero; that pins down the covariance $c$ between any two distinct draws.

0 = \text{Var}\Big(\sum_{j=1}^{N}X_j\Big) = N\sigma^2 + N(N - 1)\,c \;\Rightarrow\; c = -\frac{\sigma^2}{N - 1}

$\text{Var}$: variance: the average squared spread around the mean
$\sum_{j=1}^{N}$: add up over all $N$ draws
$X_j$: one coordinate of the $j$ -th draw's gradient
$\sigma^2$: the variance of one draw's coordinate
$c$: the covariance between two distinct draws (negative)

The variance of the mean of the first $B$ draws then has $B$ variance terms and $B(B - 1)$ covariance terms.

\text{Var}\Big(\frac1B\sum_{j=1}^{B}X_j\Big) = \frac{1}{B^2}\Big[B\sigma^2 - B(B - 1)\frac{\sigma^2}{N - 1}\Big] = \frac{\sigma^2}{B}\cdot\frac{N - B}{N - 1}

At $B = N$ the factor is 0: the "minibatch" is the full batch.

Check on the 10k orders at $w = 0$ (standardized features): $\operatorname{tr} \Sigma = 8{,}330$ . For $B = 32$ the formula gives 259.5 and 2,000 measured draws give 275.4; for $B = 1{,}024$ , 7.30 vs 7.07. The log-log slope of variance against $B$ is −1.02. Drill 6 ( $B = 1{,}000$ of $N = 10{,}000$ ) gives a factor of 0.900 (simulated: 0.902).

\frac{8{,}330}{32}\cdot\frac{9{,}968}{9{,}999} = 259.5 \;\;(\text{measured } 275.4), \qquad \frac{N - B}{N - 1} = \frac{9{,}000}{9{,}999} = 0.900

The noise does not vanish at the optimum: at $w^*$ the full gradient is zero but $\operatorname{tr} \Sigma = 109$ . That leftover noise is what sets SGD's floor (Card 9).
Importance sampling keeps the estimate unbiased if each draw is reweighted by $1/(Np_{i})$ . Its second moment is a weighted sum that, by Cauchy–Schwarz (or a Lagrangian on $\sum p_{i} = 1$ ), is smallest when $p_{i}$ is proportional to the gradient's size.

\mathbb E_{I \sim p}\Big[\frac{\nabla\ell_I}{Np_I}\Big] = \sum_i p_i\frac{\nabla\ell_i}{Np_i} = \mathbf G, \qquad \mathbb E\Big\lVert\frac{\nabla\ell_I}{Np_I}\Big\rVert^2 = \frac{1}{N^2}\sum_i\frac{\lVert\nabla\ell_i\rVert^2}{p_i} \ge \Big(\frac1N\sum_i\lVert\nabla\ell_i\rVert\Big)^2

$\mathbb E_{I \sim p}$: average when row $I$ is drawn with probabilities $p$ ( $\sim$ = is distributed as)
$p_i$: the probability of drawing order $i$
$p_I$: the drawn row's probability
$\sum_i$: add up over all orders $i$
$\lVert\nabla\ell_i\rVert$: the size of order $i$ 's gradient

Drill 19: 90% of gradients of size 1 and 10% of size 9 give a second moment of 0.9 + 8.1 = 9.0 under uniform sampling and $(0.9 + 0.9)^{2} = 3.24$ under the optimal weights, a 2.78× reduction. On the 10k orders the gradient variance falls from 8,330 to 3,558 (2.34×).

Key move. E.

Common slip. Saying the standard deviation falls as $1/B$ (it falls as $1/\sqrt{B}$ ; the variance falls as $1/B$ ). Forgetting the finite-population factor. Assuming unbiasedness survives any sampling scheme: it needs uniform sampling, or explicit reweighting; reading rows in stored order biases the gradient (Section 10).

How it's asked. "Show the minibatch gradient is unbiased and derive its variance. What changes without replacement?" (Q17; Q7, Drill 6, Drill 19.) Strong answer: steps 1–5, the $B = N$ sanity check, and "unbiased, cheap, noisy": the noise floor at $w^*$ comes from $\operatorname{tr} \Sigma(w^*) > 0$ , not from the gradient.

Card 9 · SGD's noise floor and Robbins–Monro ★★

Statement. On a 1-D quadratic $L = (\lambda/2)w^{2}$ with gradient noise of variance $\sigma^{2}/B$ , SGD with a constant step does not converge: it settles at an excess loss proportional to $\eta/B$ . Only a decaying step with $\sum\eta_{t} = \infty$ and $\sum\eta_{t}^{2} < \infty$ removes the floor.

\mathbb E[L] - L^\star \;\to\; \frac{\eta\,\sigma^2}{2B(2 - \eta\lambda)} \approx \frac{\eta\,\sigma^2}{4B}, \qquad \text{converges to } 0 \text{ if } \sum_t\eta_t = \infty,\;\; \sum_t\eta_t^2 < \infty

$\mathbb E[L] - L^\star$: the average excess loss SGD settles at: the noise floor
$\sigma^2$: here: the per-order gradient-noise variance along this mode
$\lambda$: the curvature of the 1-D quadratic mode
$\sum_t$: add up over all steps $t$
$\eta_t$: the step size at step $t$

Derivation.

Model the slowest mode near the minimum ( $w^* = 0$ ). The minibatch gradient is the true gradient plus zero-mean noise $\xi$ with variance $\sigma^{2}/B$ , independent of the current $w$ and across steps.

g_k = \lambda w_k + \xi_k, \qquad \mathbb E[\xi_k] = 0, \qquad \text{Var}(\xi_k) = \frac{\sigma^2}{B}

$g$: the 1-D minibatch gradient; subscript = step
$w$: the single weight of this 1-D mode, optimum at 0; subscript = step
$\xi$: the gradient noise: zero mean, variance $\sigma^2/B$ ; subscript = step

The update is a contraction plus a kick.

w_{k+1} = w_k - \eta g_k = (1 - \eta\lambda)\,w_k - \eta\,\xi_k

The mean contracts to zero exactly as in full-batch GD (Card 5).

\mathbb E[w_{k+1}] = (1 - \eta\lambda)\,\mathbb E[w_k] \;\Rightarrow\; \mathbb E[w_k] = (1 - \eta\lambda)^k w_0 \to 0

The second moment does not. Square the update and take expectations; the cross term vanishes because $\xi_{k}$ is independent of $w_{k}$ .

\mathbb E[w_{k+1}^2] = (1 - \eta\lambda)^2\,\mathbb E[w_k^2] - 2\eta(1 - \eta\lambda)\underbrace{\mathbb E[w_k\xi_k]}_{0} + \eta^2\frac{\sigma^2}{B}

This is a linear recursion $v \leftarrow a\cdot v + b$ with $a = (1 - \eta\lambda)^{2} < 1$ ; unrolled, it converges to the fixed point $b/(1 - a)$ , the sum of a geometric series.

v_\infty = \frac{\eta^2\sigma^2/B}{1 - (1 - \eta\lambda)^2} = \frac{\eta^2\sigma^2/B}{\eta\lambda(2 - \eta\lambda)} = \frac{\eta\,\sigma^2}{B\,\lambda\,(2 - \eta\lambda)}

$v_\infty$: the long-run second moment $\mathbb E[w^2]$ that SGD settles at

Convert to loss. The curvature $\lambda$ cancels for small $\eta\lambda$ : the floor depends on $\eta/B$ and the noise, not on how steep the mode is.

\mathbb E[L] - L^\star = \frac\lambda2\,v_\infty = \frac{\eta\,\sigma^2}{2B(2 - \eta\lambda)} \approx \frac{\eta\,\sigma^2}{4B} \quad(\eta\lambda \ll 1)

$\frac\lambda2$: half the mode's curvature

Check (WP2: $\lambda = 1$ , $\sigma^{2} = 4$ ). At $\eta = 0.1$ , $B = 1$ the formula gives 0.4/3.8 = 0.105, and the simulation gives 0.105. Across all twelve $(\eta, B)$ pairs from $\eta = 0.01$ to 0.3 and $B = 1$ to 16, simulation and formula agree within 1.2%.
Many dimensions: rotate to the eigenbasis and apply step 6 to each mode, whose noise variance is that mode's diagonal entry of $\Sigma$ in the rotated basis. The diagonal entries sum to the trace, which rotation does not change.

\mathbb E[L] - L^\star \approx \sum_i\frac{\eta\,\sigma_i^2}{4B} = \frac{\eta}{4B}\operatorname{tr}\Sigma(\mathbf w^\star) = \frac{0.03}{4\times 8}\times 109 = 0.102 \;\;(\text{10k orders, } \eta = 0.03,\ B = 8;\ \text{simulated } 0.106)

$\sum_i$: add up over the eigen-axes $i$
$\sigma_i^2$: the noise variance along eigen-axis $i$
$\operatorname{tr}\Sigma(\mathbf w^\star)$: total gradient noise at the optimum (109 on the 10k orders)

The theory is for small $\eta$ . At $\eta = 0.1$ , $B = 1$ on the 10k orders the simulated floor is 8.24 against 3.06 from the exact per-mode formula, because real per-example noise grows with the distance from $w^*$ (multiplicative noise), which step 1 assumed away.

Robbins–Monro. With a step $\eta_{t}$ that changes over time, the mean term is a product of contractions, and it reaches zero from any start only if the steps sum to infinity (since $\ln(1 - x) \approx -x$ ). Each step also injects noise $\eta_{t}^{2}\sigma^{2}/B$ ; the total injected noise stays finite only if $\sum\eta_{t}^{2} < \infty$ . The schedule $\eta_{t} = c/t$ satisfies both.

\mathbb E[w_t] = \prod_{s < t}(1 - \eta_s\lambda)\;w_0 \to 0 \iff \sum_s\eta_s = \infty, \qquad v_{t+1} = (1 - \eta_t\lambda)^2\,v_t + \eta_t^2\,\frac{\sigma^2}{B}

$\prod_{s < t}$: multiply together over all steps $s$ before $t$
$\eta_s$: the step size at step $s$
$\sum_s$: add up over all steps $s$
$v$: the second moment $\mathbb E[w^2]$ ; subscript = step
$t$: the step number

The rate under $\eta_{t} = c/t$ . Keep first-order terms in $1/t$ and try $v_t = A/t$ . Using $A/(t + 1) \approx A/t - A/t^{2}$ and matching the $1/t^{2}$ terms gives $A$ , valid when $2c\lambda > 1$ .

v_{t+1} \approx \Big(1 - \frac{2c\lambda}{t}\Big)v_t + \frac{c^2\sigma^2}{Bt^2} \;\Rightarrow\; -A = -2c\lambda A + \frac{c^2\sigma^2}{B} \;\Rightarrow\; A = \frac{c^2\sigma^2}{B(2c\lambda - 1)}

$c$: the constant in the schedule $\eta_t = c/t$
$A$: the constant in the trial solution $v_t = A/t$

If $2c\lambda < 1$ , the contraction itself is too slow: the product in step 9 decays only like $t^{-2c\lambda}$ , and that sets the rate. Drill 17 ( $\lambda = 1$ ): $c = 1$ gives a log-log slope of −1.00 (simulated −1.0007), $c = 0.25$ gives −0.5 (simulated −0.498). WP2's decay run ( $c = 1$ , $\lambda = 1$ , $\sigma^{2} = 4$ , $B = 1$ ) has $A = 4$ , so the excess loss is $\sigma^{2}/(2t)$ , $2.0 \times 10^{-5}$ at the end of the run against $1.98 \times 10^{-5}$ simulated.

Key move. E for the cross term and the noise, U for the geometric-series fixed point.

Common slip. Calling the plateau "convergence". Writing the floor as $\propto \eta$ and forgetting $B$ (or vice versa). Claiming any $1/t$ schedule gives the $1/t$ rate: it needs $2c\lambda > 1$ on the slowest mode, which is why $c$ is tuned.

How it's asked. "SGD on the 10k ETA data flattens 5% above the full-batch optimum and more epochs don't help. Why, and what do you do?" (Q18, Q11, WP2, Drill 17.) Strong answer: derive the floor, say " $\propto \eta/B$ ", give the fixes (decay the step, grow the batch late, or average iterates: on the 10k set, averaging the last half of a constant- $\eta$ run cuts the excess from 0.0373 to $5.8 \times 10^{-6}$ ), and state the small- $\eta$ caveat.

Card 10 · Momentum as an EMA; the effective step ★

Statement. The momentum buffer is an exponentially weighted sum of past gradients. On a steady slope the steps grow to $\eta/(1 - \beta)$ times the gradient, and the buffer remembers about $1/(1 - \beta)$ recent gradients.

\mathbf v_{k+1} = \beta\mathbf v_k + \mathbf g_k,\quad \mathbf w_{k+1} = \mathbf w_k - \eta\mathbf v_{k+1} \;\Rightarrow\; \mathbf v_{k+1} = \sum_{j=0}^{k}\beta^j\mathbf g_{k-j}, \qquad \text{steady } \mathbf g:\;\; \Delta\mathbf w \to -\frac{\eta}{1 - \beta}\,\mathbf g

$\mathbf v$: the momentum buffer (velocity): a decaying sum of past gradients
$\beta$: the momentum coefficient: share of the buffer kept each step (e.g. 0.9)
$\mathbf g$: the minibatch gradient; subscript = step
$\sum_{j=0}^{k}$: add up over gradients from $j = 0$ to $k$ steps ago
$\beta^j$: the weight on the gradient from $j$ steps ago
$\Delta\mathbf w$: the change in the weights per step
$j$: how many steps ago a gradient was taken

Derivation.

Unroll the buffer from $v_{0} = 0$ : the gradient from $j$ steps ago carries weight $\beta^{j}$ .

\mathbf v_{k+1} = \mathbf g_k + \beta\mathbf g_{k-1} + \beta^2\mathbf g_{k-2} + \dots + \beta^k\mathbf g_0 = \sum_{j=0}^{k}\beta^j\,\mathbf g_{k-j}

On a constant gradient the sum is a geometric series; the step approaches $\eta/(1 - \beta)$ times $g$ .

\mathbf v_{k+1} = \mathbf g\sum_{j=0}^{k}\beta^j = \frac{1 - \beta^{k+1}}{1 - \beta}\,\mathbf g \;\to\; \frac{\mathbf g}{1 - \beta}

The window. The weights sum to $1/(1 - \beta)$ , and their average age is $\beta/(1 - \beta)$ ; either way, the buffer remembers on the order of $1/(1 - \beta)$ steps: 10 for $\beta = 0.9$ , 100 for $\beta = 0.99$ .

\sum_{j\ge 0}\beta^j = \frac{1}{1 - \beta}, \qquad \frac{\sum_j j\,\beta^j}{\sum_j\beta^j} = \frac{\beta/(1 - \beta)^2}{1/(1 - \beta)} = \frac{\beta}{1 - \beta}

$\sum_{j\ge 0}$: add up over all past steps $j$
$\sum_j$: add up over all $j$

Zigzags cancel. If the gradient alternates sign (bouncing across a ravine), try a steady alternating solution of size $a$ : it is damped by $1 + \beta$ , while a consistent push is amplified by $1/(1 - \beta)$ . For $\beta = 0.9$ the along-valley direction gains 19 times more than the across-valley bounce.

\mathbf g_k = (-1)^k\mathbf g:\;\; \mathbf v_{k+1} = (-1)^k\mathbf a \;\Rightarrow\; \mathbf a = -\beta\mathbf a + \mathbf g \;\Rightarrow\; \mathbf a = \frac{\mathbf g}{1 + \beta}, \qquad \frac{1/(1 - \beta)}{1/(1 + \beta)} = \frac{1 + \beta}{1 - \beta} = 19

$\mathbf a$: the size of the steady alternating buffer

The classical (Polyak) form is the same algorithm: substitute $w_{k} - w_{k-1} = -\eta v_{k}$ .

\mathbf w_{k+1} = \mathbf w_k - \eta(\beta\mathbf v_k + \mathbf g_k) = \mathbf w_k - \eta\,\mathbf g_k + \beta(\mathbf w_k - \mathbf w_{k-1})

The EMA form used by Adam, $m \leftarrow \beta m + (1 - \beta)g$ , is the same buffer scaled by $(1 - \beta)$ , so it averages instead of summing; with that form the effective step stays $\eta$ . The two conventions mean the same $\beta$ gives different step sizes.

\mathbf m_{k+1} = \beta\mathbf m_k + (1 - \beta)\mathbf g_k \;\Rightarrow\; \mathbf m_{k+1} = (1 - \beta)\,\mathbf v_{k+1}

$\mathbf m$: the EMA-form buffer (Adam's convention): averages instead of summing

Check (Drill 5): $\eta = 0.01$ and $\beta = 0.9$ on a constant slope give an eventual step of $0.1\cdot g$ , ten times what the colleague expected; the simulation agrees.

Key move. U.

Common slip. Thinking the step is still $\eta$ after adding momentum. Raising $\beta$ from 0.9 to 0.99 at fixed $\eta$ multiplies the effective step by 10, which is the usual reason a run that got faster with momentum then starts to oscillate (Q9). Mixing the PyTorch and EMA conventions when copying hyperparameters.

How it's asked. "We set lr = 0.01 and momentum = 0.9 and the loss started swinging when we raised momentum to 0.99. Explain." (Q9, Drill 5.) Strong answer: the buffer is a geometric sum, the effective step is $\eta/(1 - \beta)$ , so scale $\eta$ by $(1 - \beta)$ when raising $\beta$ ; and the hook " $\beta$ is memory: window $1/(1 - \beta)$ , step $\eta/(1 - \beta)$ ".

Card 11 · Heavy ball on a quadratic: optimal β and the √κ rate ★★★

Statement. On a quadratic with eigenvalues in $[\mu, L]$ , heavy-ball momentum with the step and momentum below makes every mode contract at the same rate $\sqrt{\beta}$ , which replaces $\kappa$ by $\sqrt{\kappa}$ in the rate.

\eta^\star = \frac{4}{(\sqrt L + \sqrt\mu)^2}, \qquad \beta^\star = \Big(\frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\Big)^2, \qquad \rho_{\text{HB}} = \sqrt{\beta^\star} = \frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}

$\eta^\star$: here: the best step size for heavy ball
$\beta^\star$: the best momentum coefficient
$\rho_{\text{HB}}$: heavy ball's rate: the error's shrink factor per step
$\sqrt L$: square root of the largest curvature
$\sqrt\mu$: square root of the smallest curvature
$\sqrt\kappa$: square root of the condition number

Derivation.

Use the classical form (Card 10, step 5) in error coordinates and rotate; each mode with eigenvalue $\lambda$ follows a second-order recursion.

e_{k+1} = e_k - \eta\lambda e_k + \beta(e_k - e_{k-1}) = (1 + \beta - \eta\lambda)\,e_k - \beta\,e_{k-1}

$e$: the error along one eigen-axis; subscript = step
$\lambda$: that axis's curvature (eigenvalue)

Write it as a 2 × 2 linear system. Its eigenvalues $r$ solve the characteristic equation, and the mode shrinks like $\lvert r\rvert ^{k}$ .

\begin{pmatrix} e_{k+1}\\ e_k\end{pmatrix} = \begin{pmatrix} 1 + \beta - \eta\lambda & -\beta\\ 1 & 0\end{pmatrix}\begin{pmatrix} e_k\\ e_{k-1}\end{pmatrix}, \qquad r^2 - (1 + \beta - \eta\lambda)\,r + \beta = 0

$r$: a root of the characteristic equation: the mode shrinks like $|r|^k$

The product of the two roots is $\beta$ . When the roots are a complex-conjugate pair they have equal size, so both have size $\sqrt{\beta}$ , whatever $\lambda$ is. That is the whole trick: inside this regime the rate does not depend on the curvature.

r_1 r_2 = \beta, \quad r_2 = \bar r_1 \;\Rightarrow\; |r_1| = |r_2| = \sqrt\beta

$\bar r_1$: the complex conjugate of $r_1$ (here bar = conjugate, not mean)
$\sqrt\beta$: the size of each root: heavy ball's rate per step

The roots are complex (or a repeated real pair, still of size $\sqrt{\beta}$ ) when the discriminant is not positive, which is a band of curvatures.

(1 + \beta - \eta\lambda)^2 \le 4\beta \iff -2\sqrt\beta \le 1 + \beta - \eta\lambda \le 2\sqrt\beta \iff (1 - \sqrt\beta)^2 \le \eta\lambda \le (1 + \sqrt\beta)^2

Fit the whole spectrum $[\mu, L]$ into the band with the smallest $\beta$ by putting the two ends exactly on its edges. Take square roots, then add and subtract the two equations.

\eta\mu = (1 - \sqrt\beta)^2,\quad \eta L = (1 + \sqrt\beta)^2 \;\Rightarrow\; \sqrt{\eta L} + \sqrt{\eta\mu} = 2, \qquad \sqrt{\eta L} - \sqrt{\eta\mu} = 2\sqrt\beta

Solve for $\eta$ and $\beta$ .

\eta^\star = \frac{4}{(\sqrt L + \sqrt\mu)^2}, \qquad \sqrt{\beta^\star} = \frac{\sqrt L - \sqrt\mu}{\sqrt L + \sqrt\mu} = \frac{\sqrt\kappa - 1}{\sqrt\kappa + 1}

The speedup in step counts is the ratio of log-rates. By the expansion in Card 7, $\ln(1/\rho) \approx 2/\sqrt{\kappa}$ for heavy ball and $2/\kappa$ for GD.

\frac{k_{\text{GD}}}{k_{\text{HB}}} = \frac{\ln(1/\rho_{\text{HB}})}{\ln(1/\rho_{\text{GD}})} \approx \frac{2/\sqrt\kappa}{2/\kappa} = \sqrt\kappa

$k_{\text{GD}}$: steps plain GD needs
$k_{\text{HB}}$: steps heavy ball needs
$\rho_{\text{GD}}$: GD's rate at its best fixed step

Checks. Toy ( $\kappa = 3$ ): $\beta^* = 0.0718$ (tiny, because the toy is well conditioned), $\eta^* = 0.322$ , $\rho = 0.268$ against GD's 0.5; 7 steps to tolerance instead of 10. Raw 10k model ( $\kappa = 143$ ): $\beta^* = 0.715$ , $\eta^* = 0.0682$ , $\rho = 0.846$ against GD's 0.986; the ratio of log-rates is $12.0 = \sqrt{\kappa}$ .
Why the realized speedup is smaller. At the two edges the discriminant is exactly zero, so those modes have a repeated root, and a repeated root adds a factor of $k$ to the solution. On the 10k run that turns $\sqrt{\kappa} = 12$ into 7.0× fewer steps under the loss criterion (496 → 71) and 8.8× by distance (991 → 112). In Drill 4 ( $\kappa = 100$ , $\rho = 9/11$ ) the rate formula says 69 steps but the simulation needs 93.

\text{repeated root } r = \sqrt\beta:\quad e_k = (a + b\,k)\,\beta^{k/2} \;\Rightarrow\; \text{need } k\,\rho^k \lesssim \varepsilon, \;\text{not } \rho^k \le \varepsilon

$a$: a constant set by the mode's starting error
$b$: a constant: the weight on the extra factor $k$
$\lesssim$: is at most about

Key move. R, then U on a 2 × 2 recursion (its characteristic roots).

Common slip. Forgetting the square: $\beta^* = ((\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1))^{2}$ , and the rate is its square root. Promising exactly $\sqrt{\kappa}$ times fewer steps. Assuming the quadratic tuning carries over to any convex loss: heavy ball has no such global guarantee off quadratics; Nesterov does (rate $1 - 1/\sqrt{\kappa}$ with $\eta = 1/L$ and $\beta = (\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1)$ ).

How it's asked. "With $\kappa \approx 143$ on the raw 10k model, what momentum would you pick, and what rate does it buy?" (Q27, Drill 4, WP1.) Strong answer: $\beta^* = 0.715$ and $\rho = 0.846$ , the complex-root argument for why every mode shares $\sqrt{\beta}$ , the $k\cdot \rho^{k}$ caveat, and the Nesterov alternative (theory rate 0.916, 76 steps on the 10k run). Research-level add: conjugate gradient reaches the same $\sqrt{\kappa}$ rate without knowing $\mu$ or $L$ , and finishes any d-dimensional quadratic in $d$ steps (3 on the raw 10k model), so the $\sqrt{\kappa}$ "speed limit" is a statement about problems with more dimensions than steps.

Card 12 · Adam's bias correction ★★

Statement. Adam's moving averages start at zero, so early on they are biased toward zero by a factor $(1 - \beta^{t})$ . Dividing by that factor makes them unbiased estimators of the gradient's mean and mean square when the gradient's distribution is stationary.

\mathbf m_0 = \mathbf 0 \;\Rightarrow\; \mathbb E[\mathbf m_t] = (1 - \beta_1^t)\,\mathbb E[\mathbf g], \qquad \hat{\mathbf m}_t = \frac{\mathbf m_t}{1 - \beta_1^t} \text{ is unbiased}; \qquad \text{same for } \mathbf v_t \text{ with } \beta_2 \text{ and } \mathbf g^2

$\mathbf m$: Adam's first moment: running average of the gradients; subscript = step
$\beta_1$: the first moment's decay rate (typically 0.9)
$\beta_1^t$: what is left of the zero start after $t$ steps
$t$: the step number
$\mathbb E[\mathbf g]$: the gradient's true mean, assumed the same every step
$\hat{\mathbf m}_t$: the bias-corrected first moment (hat = corrected estimate)
$\mathbf v$: here: Adam's second moment: running average of squared gradients
$\beta_2$: the second moment's decay rate (typically 0.999)
$\mathbf g^2$: the gradient squared entry by entry

Derivation.

Unroll the moving average from $m_{0} = 0$ : the gradient from step $i$ gets weight $(1 - \beta_{1})\beta_{1}^{t-i}$ .

\mathbf m_t = \beta_1\mathbf m_{t-1} + (1 - \beta_1)\mathbf g_t = (1 - \beta_1)\sum_{i=1}^{t}\beta_1^{\,t-i}\,\mathbf g_i

$\sum_{i=1}^{t}$: add up over steps $i = 1$ to $t$
$\beta_1^{\,t-i}$: the weight on step $i$ 's gradient: smaller the older it is
$i$: the step a gradient came from

Take expectations, assuming every $g_{i}$ has the same mean (stationarity). The weights form a finite geometric series that sums to $1 - \beta_{1}^{t}$ , not 1: the missing weight is what the zero start "used up".

\mathbb E[\mathbf m_t] = (1 - \beta_1)\,\mathbb E[\mathbf g]\sum_{j=0}^{t-1}\beta_1^{\,j} = (1 - \beta_1)\,\mathbb E[\mathbf g]\,\frac{1 - \beta_1^t}{1 - \beta_1} = (1 - \beta_1^t)\,\mathbb E[\mathbf g]

$\sum_{j=0}^{t-1}$: add up over $j = 0$ to $t - 1$
$\beta_1^{\,j}$: the $j$ -th term of the geometric series

Divide by the missing factor; the same algebra applies to $v$ with $\beta_{2}$ and $g^{2}$ .

\mathbb E[\hat{\mathbf m}_t] = \frac{\mathbb E[\mathbf m_t]}{1 - \beta_1^t} = \mathbb E[\mathbf g], \qquad \mathbb E[\hat{\mathbf v}_t] = \frac{\mathbb E[\mathbf v_t]}{1 - \beta_2^t} = \mathbb E[\mathbf g^2]

$\hat{\mathbf v}_t$: the bias-corrected second moment

Check: with $\beta_{1} = 0.9$ , after 10 steps the weights sum to $1 - 0.9^{10} = 0.651$ (over 200,000 simulated runs with noisy gradients of mean 1 and standard deviation 2, the average $m_{10}$ is 0.650).

What goes wrong at step 1 without correction. The two biases do not cancel, because $m$ is off by $(1 - \beta_{1})$ but $\sqrt{v}$ only by $\sqrt{1 - \beta_{2}}$ . The first step is 3.16 times too large; with correction it is exactly $\eta$ in the direction of the gradient's sign.

\frac{m_1}{\sqrt{v_1}} = \frac{(1 - \beta_1)\,g_1}{\sqrt{(1 - \beta_2)\,g_1^2}} = \frac{0.1}{\sqrt{0.001}}\,\text{sign}(g_1) = 3.16\,\text{sign}(g_1), \qquad \frac{\hat m_1}{\sqrt{\hat v_1}} = \frac{g_1}{|g_1|} = \text{sign}(g_1)

$m$: one weight's first moment, uncorrected; subscript = step
$v$: one weight's second moment, uncorrected; subscript = step
$g$: one weight's gradient; subscript = step
$\text{sign}$: +1 for a positive input, −1 for a negative one
$\hat m$: one weight's bias-corrected first moment
$\hat v$: one weight's bias-corrected second moment

A half-fixed Adam that corrects $m$ but not $v$ inflates its step by $1/\sqrt{1 - \beta_{2}^{t}}$ , which fades slowly because $\beta_{2}$ is close to 1 (Drill 8).

\frac{\hat m_t}{\sqrt{v_t}} = \frac{\hat m_t}{\sqrt{\hat v_t}}\cdot\frac{1}{\sqrt{1 - \beta_2^t}}, \qquad \frac{1}{\sqrt{1 - 0.999^t}} = 10.0,\;\; 3.24,\;\; 1.26 \quad(t = 10,\ 100,\ 1{,}000)

Adam is invariant to rescaling the gradient: multiply every gradient by $c$ and both $\hat m$ and $\sqrt{\hat v}$ scale by $\lvert c\rvert$ , so the step is unchanged (up to $\varepsilon$ ). Multiplying the 10k loss by 1,000 changes Adam's trajectory by at most $1.5 \times 10^{-9}$ .

\mathbf g \to c\,\mathbf g \;\Rightarrow\; \hat{\mathbf m}_t \to c\,\hat{\mathbf m}_t,\;\; \sqrt{\hat{\mathbf v}_t} \to |c|\sqrt{\hat{\mathbf v}_t} \;\Rightarrow\; \Delta\mathbf w = -\eta\frac{\hat{\mathbf m}_t}{\sqrt{\hat{\mathbf v}_t} + \epsilon} \;\text{unchanged}

$c$: the factor every gradient is multiplied by
$\epsilon$: Adam's tiny constant that prevents dividing by zero

It is not invariant to a feature's units. Measuring a feature in units $c$ times smaller (meters instead of km) multiplies the feature by $c$ , which divides the right weight by $c$ , multiplies its gradient by $c$ and its curvature by $c^{2}$ . GD's usable step for that weight therefore scales as $1/c^{2}$ , while Adam's step is about $\eta$ per weight in whatever units the weight has, so the needed step scales as $1/c$ . For meters ( $c = 1{,}000$ ) the step disparity falls from $10^{6}$ under GD to $10^{3}$ under Adam, not to 1.

x \to c\,x:\quad w^\star \to \frac{w^\star}{c}, \quad \frac{\partial L}{\partial w} \to c\,\frac{\partial L}{\partial w}, \quad \lambda \to c^2\lambda \;\Rightarrow\; \eta_{\text{GD}} \propto \frac{1}{c^2}, \qquad \eta_{\text{Adam}} \propto \frac1c

$x$: one feature, e.g. distance
$c$: here: the unit-change factor (1,000 for km → meters)
$w^\star$: the optimal weight on that feature
$\frac{\partial L}{\partial w}$: how fast the loss changes as you nudge that weight, holding the rest fixed
$\lambda$: the curvature along that weight
$\eta_{\text{GD}}$: the usable GD step for that weight
$\eta_{\text{Adam}}$: Adam's needed step for that weight
$\frac1c$: one over the unit-change factor

Key move. U (finite geometric series), then E (linearity).

Common slip. Dividing by $(1 - \beta_{1})$ instead of $(1 - \beta_{1}^{t})$ . Believing the correction matters all through training: for $m$ it fades within about $1/(1 - \beta_{1}) = 10$ steps, for $v$ within thousands. Saying Adam makes feature scaling unnecessary (step 7).

How it's asked. "Write Adam's update from memory and explain every line, especially the bias correction." (Q19; Drills 7–8; Q31.) Strong answer: steps 1–4, the four D's (Direction, Denominator, Debias, Decay), and why warmup still helps after correction: the early $\hat v$ is an average of very few squared gradients, so it is noisy, which is the motivation for RAdam.

Card 13 · L2 penalty vs decoupled weight decay ★★

Statement. Under plain SGD, adding $(\lambda/2)\lVert w\rVert ^{2}$ to the loss is the same as shrinking the weights by $(1 - \eta\lambda)$ every step. Under Adam the two differ: the penalty's gradient $\lambda w$ is divided by $\sqrt{\hat v}$ , so it stops acting as uniform decay. AdamW applies the decay outside the adaptive step.

\text{SGD: } \mathbf w - \eta(\nabla L + \lambda\mathbf w) = (1 - \eta\lambda)\,\mathbf w - \eta\nabla L \qquad \text{AdamW: } \mathbf w \leftarrow (1 - \eta\lambda)\,\mathbf w - \eta\,\frac{\hat{\mathbf m}}{\sqrt{\hat{\mathbf v}} + \epsilon}

$\lambda$: here: the weight-decay (L2 penalty) strength
$\hat{\mathbf m}$: the bias-corrected first moment
$\hat{\mathbf v}$: the bias-corrected second moment

Derivation.

The penalty $(\lambda/2)\lVert w\rVert ^{2}$ has gradient $\lambda w$ . Under SGD, regroup the update: the penalty becomes a multiplicative shrink, so "L2" and "weight decay" are the same thing.

\mathbf w_{k+1} = \mathbf w_k - \eta\big(\nabla L(\mathbf w_k) + \lambda\mathbf w_k\big) = (1 - \eta\lambda)\,\mathbf w_k - \eta\nabla L(\mathbf w_k)

Under Adam with an L2 penalty, the penalized gradient $\tilde g = \nabla L + \lambda w$ is what enters both moments, so the penalty is normalized coordinate by coordinate along with the data gradient.

\Delta w_j = -\eta\,\frac{\widehat{\text{EMA}}\big[\partial_jL + \lambda w_j\big]}{\sqrt{\widehat{\text{EMA}}\big[(\partial_jL + \lambda w_j)^2\big]} + \epsilon}

$\Delta w_j$: the change in weight $j$ this step
$\widehat{\text{EMA}}$: a bias-corrected moving average, as Adam forms $\hat m$ and $\hat v$
$\partial_jL$: the loss's slope in weight $j$ , holding the others fixed
$w_j$: weight $j$ : one coordinate of $\mathbf w$ , e.g. the km weight

Take the extreme case, a weight with zero data gradient. The update is unchanged by rescaling $\lambda$ (numerator and denominator both scale by $\lambda$ ), so once $\lambda\lvert w\rvert \gg \varepsilon$ the penalty's strength drops out entirely.

\partial_jL = 0:\quad \Delta w_j = -\eta\,\frac{\lambda\,\widehat{\text{EMA}}[w_j]}{\lambda\sqrt{\widehat{\text{EMA}}[w_j^2]} + \epsilon} \approx -\eta\,\frac{\widehat{\text{EMA}}[w_j]}{\sqrt{\widehat{\text{EMA}}[w_j^2]}}

Drill 9 ( $w_{0} = 1$ , $\eta = 10^{-3}$ , $\lambda = 0.1$ ). AdamW shrinks geometrically. Adam + L2 first moves about $\eta$ per step (the first 100 steps average 0.000983), reaching 0.902 after 100 steps; then $\hat v$ remembers the larger earlier values of $w$ , the ratio in step 3 falls below 1, and the steps slow: 0.258 after 1,000 steps, 0.021 after 2,000, never crossing 0. The trajectory is the same for $\lambda = 10^{-3}$ , 0.1 and 1.

\text{AdamW: } w_{1000} = \big(1 - 10^{-3}\times 0.1\big)^{1000} = e^{1000\ln(1 - 10^{-4})} \approx e^{-0.1} = 0.905 \qquad \text{Adam + L2: } w_{1000} = 0.258

$w_{1000}$: the weight after 1,000 steps (it started at 1)
$e$: Euler's number, 2.718…

Where each one converges. Adam + L2 can only stop where its moment $\hat m$ averages to zero, which means the penalized gradient is zero: the ordinary ridge solution, whatever the per-weight denominators are.

\text{Adam + L2:}\quad \mathbb E[\hat{\mathbf m}] = \mathbf 0 \iff \nabla L(\mathbf w) + \lambda\mathbf w = \mathbf 0 \quad(\text{ridge})

AdamW stops where the adaptive step balances the decay. At that point $\hat m \approx \nabla L$ , so multiplying through by $\sqrt{\hat v_{j}}$ shows AdamW solves a ridge problem whose strength differs per weight: $\lambda\sqrt{\hat v_{j}}$ . Here $\sqrt{\hat v_{j}}$ includes the minibatch noise, so it stays well above zero even where the mean gradient vanishes.

\text{AdamW:}\quad \frac{\partial_jL}{\sqrt{\hat v_j}} + \lambda w_j = 0 \iff \partial_jL + \big(\lambda\sqrt{\hat v_j}\big)\,w_j = 0

$\hat v_j$: weight $j$ 's bias-corrected second moment: its mean squared gradient

Check on the raw 10k model ( $\lambda = 0.1$ , decay on km and items only). Ridge gives (6.214, 2.972, 1.963) for (intercept, km, items); Adam + L2 gives (6.213, 2.972, 1.963), the same to 3–4 digits. AdamW gives (6.692, 2.888, 1.893): with $\sqrt{\hat v} = 4.51$ for km and 3.82 for items, its effective ridge strengths are 0.451 and 0.382, so it shrinks both weights more, the high-gradient-RMS one (km) most.

Key move. U (regroup the repeated update), plus the fixed-point argument in steps 5–6.

Common slip. "AdamW over-shrinks low-gradient weights": relative to L2-in-Adam its effective strength is $\lambda\sqrt{\hat v_{j}}$ instead of $\lambda$ , so it shrinks a weight more than the L2 version only when that weight's $\sqrt{\hat v}$ is above 1, and less when it is below 1. Treating torch.optim.Adam(weight_decay=…) as AdamW: it adds $\lambda w$ to the gradient, which is the L2 version. In PyTorch's AdamW the decay is multiplied by the learning rate, so a learning-rate schedule also schedules the decay.

How it's asked. "A colleague used Adam with weight_decay = 0.01, switched to AdamW and results changed. Why?" (Q20, Drill 9.) Strong answer: steps 1–3, the fixed points in 5–6, the PyTorch gotcha, and that the LLM recipe uses AdamW with decay 0.1.

Card 14 · Newton: one step on a quadratic, quadratic convergence, Newton = IRLS ★★

Statement. Newton's method minimizes the local quadratic model. It lands exactly on the minimum of a quadratic in one step, near a non-degenerate minimum the error squares every step, and for logistic regression each Newton step is a weighted least-squares solve (IRLS).

\mathbf w_{k+1} = \mathbf w_k - H(\mathbf w_k)^{-1}\nabla L(\mathbf w_k), \qquad |e_{k+1}| \le \frac{M}{2m}\,e_k^2, \qquad \text{logistic: } \mathbf w_{k+1} = (X^\top SX)^{-1}X^\top S\,\mathbf z

$H(\mathbf w_k)^{-1}$: the inverse Hessian at the current weights ( $^{-1}$ = matrix inverse)
$e$: the 1-D error: distance from the minimum; subscript = step
$M$: a cap on the third derivative $|f'''|$ near the minimum
$m$: a floor on the curvature $f''$ near the minimum
$(X^\top SX)^{-1}$: inverse of the curvature-weighted cross-product matrix
$\mathbf z$: IRLS's working response, one entry per order

Derivation.

Second-order Taylor gives a bowl around the current point. Set its gradient in the step $d$ to zero.

m(\mathbf d) = L(\mathbf w) + \nabla L^\top\mathbf d + \tfrac12\mathbf d^\top H\mathbf d, \qquad \nabla_{\mathbf d}\,m = \nabla L + H\mathbf d = \mathbf 0 \;\Rightarrow\; \mathbf d = -H^{-1}\nabla L

$m(\mathbf d)$: the local quadratic model of the loss around $\mathbf w$
$\mathbf d$: the step to take
$\nabla_{\mathbf d}\,m$: the model's gradient with respect to the step
$H^{-1}$: the inverse Hessian (undoes $H$ )

On a quadratic the model is the loss itself, and the gradient is $H(w - w^*)$ , so one step lands on $w^*$ from anywhere.

\mathbf w - H^{-1}\nabla L = \mathbf w - H^{-1}H(\mathbf w - \mathbf w^\star) = \mathbf w^\star

Toy check from $w = 0$ . Invert the 2 × 2 Hessian (determinant 75/9) and apply it to the gradient.

H^{-1} = \begin{pmatrix} 0.4 & -0.2\\ -0.2 & 0.4\end{pmatrix}, \qquad \mathbf w_1 = \mathbf 0 - H^{-1}\begin{pmatrix} -13.33\\ -11.67\end{pmatrix} = \begin{pmatrix} 5.33 - 2.33\\ -2.67 + 4.67\end{pmatrix} = \begin{pmatrix} 3\\ 2\end{pmatrix}

$\mathbf w_1$: the weights after one Newton step from 0

In the eigenbasis, Newton is gradient descent with a separate step $1/\lambda_{i}$ for each mode, so every mode's factor is 0 and $\kappa$ no longer matters. The same property makes Newton invariant to any linear change of feature units.
Quadratic convergence in 1-D. Newton minimizes $f$ by finding a root of $\phi = f'$ . Expand $\phi$ around the current $w$ and evaluate at the root $w^*$ , keeping the exact remainder at some $\xi$ between them.

0 = \varphi(w^\star) = \varphi(w) + \varphi'(w)(w^\star - w) + \tfrac12\varphi''(\xi)(w^\star - w)^2

$\varphi$: $f'$ , the slope of the 1-D loss; Newton seeks its root
$\varphi'$: its derivative, the curvature $f''$
$\varphi''$: its second derivative, $f'''$
$w$: the current 1-D weight
$w^\star$: the minimum, where $\varphi = 0$
$\xi$: some point between $w$ and $w^\star$ (Taylor's exact remainder)

Divide by $\phi'(w)$ and rearrange: the new error is the old error squared, times a ratio of derivatives. If $f'' \ge m > 0$ and $\lvert f'''\rvert \le M$ near $w^*$ , that ratio is at most $M/(2m)$ .

\underbrace{w - \frac{\varphi(w)}{\varphi'(w)}}_{w_{k+1}} - w^\star = \frac{\varphi''(\xi)}{2\varphi'(w)}\,(w - w^\star)^2 \;\Rightarrow\; |e_{k+1}| \le \frac{M}{2m}\,e_k^2

Check with $\sqrt{2}$ (Drill 11): Newton on $x^{2} - 2$ averages $x$ and $2/x$ , and the error identity is exact. From $x_{0} = 1$ the errors are 0.414, 0.0858, 0.00245, $2.12 \times 10^{-6}$ and $1.59 \times 10^{-12}$ : correct digits roughly double each step (1, 2, 5, 11).

x_{k+1} = x_k - \frac{x_k^2 - 2}{2x_k} = \frac12\Big(x_k + \frac{2}{x_k}\Big), \qquad x_{k+1} - \sqrt2 = \frac{(x_k - \sqrt2)^2}{2x_k}

$x$: the current guess for $\sqrt2$ ; subscript = step

The non-degeneracy condition matters. On $f(w) = w^{4}$ the curvature at the minimum is 0 ( $m = 0$ ), and Newton is only linear, with factor 2/3 (Drill 10).

w_{k+1} = w_k - \frac{f'(w_k)}{f''(w_k)} = w_k - \frac{4w_k^3}{12w_k^2} = \frac23\,w_k

$f'$: the slope of $f(w) = w^4$
$f''$: the curvature of $f(w) = w^4$

Logistic regression. With the gradient and Hessian from Card 3, factor the Newton step so that it reads as a weighted least-squares solve: weights $p_{i}(1 - p_{i})$ , and a "working response" $z$ that adds a scaled residual to the current score.

\mathbf w^{+} = \mathbf w - (X^\top SX)^{-1}X^\top(\mathbf p - \mathbf y) = (X^\top SX)^{-1}X^\top S\Big[X\mathbf w + S^{-1}(\mathbf y - \mathbf p)\Big] = (X^\top SX)^{-1}X^\top S\,\mathbf z

$\mathbf w^{+}$: the weights after one Newton step
$S^{-1}$: inverse of $S$ : divides each residual by $p_i(1 - p_i)$

The weights change with $w$ , so the solve is repeated: iteratively reweighted least squares. On the late-order model, IRLS reaches a step size below $10^{-8}$ in 10 iterations (relative suboptimality below $10^{-6}$ after 7); statsmodels' Newton takes 10 and its GLM IRLS 9. Gradient descent at $\eta = 1/L$ needs 553 iterations on standardized features and about 50,000 on raw km and items, where the Hessian's $\kappa$ is about 2,581.

Gauss–Newton for a least-squares loss $\tfrac12\lVert r(w)\rVert ^{2}$ . The Hessian has a part built from first derivatives ( $J^\top J$ ) and a part weighted by the residuals; drop the second, which is small near a good fit and zero for a linear model.

\nabla L = J^\top\mathbf r, \qquad \nabla^2 L = J^\top J + \sum_i r_i\,\nabla^2 r_i \approx J^\top J \;\Rightarrow\; \mathbf w^{+} = \mathbf w - (J^\top J)^{-1}J^\top\mathbf r

$J$: the Jacobian: how each residual changes with each weight
$J^\top J$: Gauss–Newton's curvature, built from first derivatives only
$\mathbf r$: the residual vector, one entry per order
$\sum_i$: add up over every order $i$
$r_i$: order $i$ 's residual
$\nabla^2 r_i$: the curvature of residual $i$ : the part Gauss–Newton drops

For a linear model $J = -X$ and this is the normal equation, reached in one step. For the power-law ETA model $a + c\cdot\text{km}^q + d\cdot\text{items}$ on the 10k orders, pure Gauss–Newton from (0, 1, 0.5, 0) diverges; with step halving it converges in 11 iterations to $\hat q = 0.991$ (true $q = 1$ ).

The cost. A $10^{6}$ -parameter Hessian in float32 takes $4 \times 10^{12}$ bytes (4 TB), and a dense solve costs on the order of $p^{3} = 10^{18}$ operations.

Key move. T (second order) for steps 1–6 and 10.

Common slip. Writing $w - H\nabla L$ , or dropping the inverse. Claiming Newton always converges quadratically: it needs a non-degenerate minimum and a start close enough, and on a non-convex loss it heads for any stationary point, saddles included, because it solves $\nabla L = 0$ (Card 17, step 7).

How it's asked. "Do one Newton step on the six-order quadratic from (0, 0). Why not use Newton for a 100M-parameter model?" (Q21; Q22, Drills 10–11.) Strong answer: step 3 by hand, then the three toos (too big, too noisy, too saddle-happy) and what is used instead: damping or trust regions, L-BFGS for small full-batch convex problems, Hessian-vector products when only curvature along a direction is needed.

Card 15 · The Lagrangian and KKT on the toy ★★

Statement. Ops caps the per-item time: $w_{\text{items}} \le 1.5$ . The constrained optimum is $w = (3.25, 1.5)$ , and the multiplier $\mu = 1.25$ is the price of the cap: raising it by one minute would lower the best loss by about 1.25.

\nabla L(\mathbf w) + \mu\,\mathbf e_2 = \mathbf 0, \quad w_2 \le 1.5, \quad \mu \ge 0, \quad \mu\,(w_2 - 1.5) = 0 \;\;\Rightarrow\;\; \mathbf w = (3.25,\; 1.5), \quad \mu = 1.25

$\mu$: the multiplier: the cap's price, in loss per minute of cap
$\mathbf e_2$: the unit vector along the items weight
$w_2$: the items weight, minutes per item (capped at 1.5)

Derivation.

Turn the constraint into a price: a penalty $\mu$ per unit of $w_{2}$ above the cap, with $\mu \ge 0$ so that violating it can only cost.

\mathcal L(\mathbf w, \mu) = L(\mathbf w) + \mu\,(w_2 - 1.5), \qquad \mu \ge 0

$\mathcal L(\mathbf w, \mu)$: the Lagrangian: the loss plus the cap's violation priced at $\mu$

Why the four KKT conditions (Some People Dislike Constraints). At a constrained optimum on the wall $w_{2} = 1.5$ , the downhill direction $-\nabla L$ must point out through the wall, along $+e_{2}$ ; otherwise you could slide along the wall and do better. That is Stationarity with Dual feasibility ( $\mu \ge 0$ ). Primal feasibility is the constraint itself. Complementary slackness says that if the optimum is strictly inside, the wall exerts no push ( $\mu = 0$ ).
The toy's gradient in matrix form.

\nabla L(\mathbf w) = H(\mathbf w - \mathbf w^\star) = \frac13\begin{pmatrix}10 & 5\\ 5 & 10\end{pmatrix}\begin{pmatrix} w_1 - 3\\ w_2 - 2\end{pmatrix}

$w_1$: the km weight, minutes per km

Try the inactive case first: $\mu = 0$ gives the unconstrained optimum (3, 2), which breaks the cap (2 > 1.5). So the constraint is active: $w_{2} = 1.5$ .
The first row of stationarity has no $\mu$ in it; solve for $w_{1}$ .

\tfrac13\big[10(w_1 - 3) + 5(1.5 - 2)\big] = 0 \;\Rightarrow\; w_1 = 3 + \frac{2.5}{10} = 3.25

The second row gives $\mu$ . It is positive, so dual feasibility holds and the solution is confirmed.

\mu = -\tfrac13\big[5(3.25 - 3) + 10(1.5 - 2)\big] = -\tfrac13\,(1.25 - 5) = 1.25 \;\ge 0

The multiplier is a price. Write the cap as $c$ and differentiate the optimal value. At the optimum $\partial\mathcal{L}/\partial w = 0$ and the constraint is active, so only the explicit dependence on $c$ survives (the envelope theorem).

\frac{dL^\star}{dc} = \frac{\partial\mathcal L}{\partial\mathbf w}\cdot\frac{d\mathbf w}{dc} + (w_2 - c)\frac{d\mu}{dc} + \frac{\partial}{\partial c}\big[\mu(w_2 - c)\big] = 0 + 0 - \mu = -1.25

$\frac{dL^\star}{dc}$: how fast the best loss changes as you raise the cap $c$ : a slope, not a fraction
$c$: the cap on $w_2$ (1.5 here)
$\frac{\partial\mathcal L}{\partial\mathbf w}$: the Lagrangian's slope in the weights: zero at the optimum
$\frac{d\mathbf w}{dc}$: how the optimal weights move as the cap changes
$\frac{d\mu}{dc}$: how the multiplier moves as the cap changes
$\frac{\partial}{\partial c}$: the slope with respect to $c$ alone, holding the rest fixed

The constrained loss is 1.979 against 1.667 unconstrained.

Projected gradient descent reaches the same point: take a gradient step, then snap back into the allowed set. With $\eta = 0.3$ from 0 it is exact after two steps.

\mathbf w_1 = \Pi\big[(4.0,\; 3.5)\big] = (4.0,\; 1.5), \quad \nabla L(\mathbf w_1) = \tfrac13\begin{pmatrix} 10(1) + 5(-0.5)\\ 5(1) + 10(-0.5)\end{pmatrix} = \begin{pmatrix} 2.5\\ 0\end{pmatrix}, \quad \mathbf w_2 = \Pi\big[(3.25,\; 1.5)\big] = (3.25,\; 1.5)

$\Pi$: projection: snap back into the allowed set ( $w_2 \le 1.5$ )
$\mathbf w_1$: the weights after one projected-GD step from 0
$\mathbf w_2$: the weights after the second projected step

A budget instead of a cap (Drill 15): $w_{1} + w_{2} \le 4$ . Stationarity says $H(w - w^*) = -\mu(1, 1)$ , and (1, 1) is the steep eigenvector with $\lambda = 5$ , so the move from $w^*$ is along it. The active constraint fixes $\mu$ .

\mathbf w - \mathbf w^\star = -\frac{\mu}{5}\begin{pmatrix}1\\1\end{pmatrix}, \qquad (3 + 2) - \frac{2\mu}{5} = 4 \;\Rightarrow\; \mu = 2.5,\quad \mathbf w = (2.5,\; 1.5)

Key move. +L (write the Lagrangian), then case-check complementary slackness.

Common slip. Assuming the constrained answer is the unconstrained one clipped: clipping (3, 2) gives (3, 1.5), but the right answer is (3.25, 1.5), because distance and items are correlated and $w_{\text{km}}$ absorbs part of what $w_{\text{items}}$ can no longer explain. Also: a negative $\mu$ (a sign error in how the constraint was written), or skipping the inactive case. And treating KKT as sufficient in general: for a convex problem with a strictly feasible point (Slater's condition) KKT is necessary and sufficient, as here; without convexity it is only necessary, and only under a constraint qualification.

How it's asked. "Ops requires $w_{\text{items}} \le 1.5$ minutes. Solve the constrained toy problem and tell me what the multiplier means." (Q26, Drill 15.) Strong answer: solve by cases, interpret $\mu$ as the marginal value of the cap, then show projected GD ("step, then snap") and mention that L-BFGS-B handles box bounds this way; duality returns with SVMs (Ch 11).

Card 16 · Soft-thresholding is the proximal operator of L1 ★★

Statement. Minimizing a squared distance plus $t\lvert w\rvert$ shrinks $z$ toward 0 by $t$ and sets it exactly to 0 when $\lvert z\rvert \le t$ . ISTA, proximal gradient descent for lasso, is a gradient step on the smooth loss followed by this shrink, and it lands on exact zeros.

\text{prox}_{t|\cdot|}(z) = \arg\min_w\;\tfrac12(w - z)^2 + t|w| = \text{sign}(z)\max(|z| - t,\, 0), \qquad \mathbf w^{+} = \text{prox}_{\eta\lambda\lVert\cdot\rVert_1}\big(\mathbf w - \eta\nabla f(\mathbf w)\big)

$\text{prox}_{t|\cdot|}(z)$: the proximal operator: the point nearest $z$ after charging $t|w|$
$z$: the input value being shrunk
$w$: the candidate output value
$t$: the threshold: the penalty per unit of $|w|$
$\arg\min_w$: the $w$ that makes what follows smallest
$\text{prox}_{\eta\lambda\lVert\cdot\rVert_1}$: soft-thresholding by $\eta\lambda$ on every weight (‖·‖₁ = sum of absolute values)
$\lambda$: the lasso (L1) penalty strength
$f$: the smooth part of the loss (the MSE)
$\mathbf w^{+}$: the weights after one ISTA step

Derivation.

$\lvert w\rvert$ has a kink at 0, so use the subgradient: the set of slopes of lines that touch $\lvert w\rvert$ from below. The objective is convex, and $w$ minimizes it exactly when 0 is in its subgradient.

0 \in (w - z) + t\,\partial|w|, \qquad \partial|w| = \begin{cases}\{+1\} & w > 0\\ [-1,\, 1] & w = 0\\ \{-1\} & w < 0\end{cases}

$\partial|w|$: the subgradient of $|w|$ : the set of slopes touching it from below

Solve each case and keep the ones that are self-consistent.

w > 0:\; w = z - t \;\;(\text{needs } z > t); \qquad w < 0:\; w = z + t \;\;(\text{needs } z < -t); \qquad w = 0:\; z \in [-t,\, t]

The three cases tile the real line, which gives the formula. Check with $t = 1$ (Drill 14): $z = 3 \to 2$ , $z = 0.5 \to 0$ , $z = -2 \to -1$ ; numerical minimization gives the same three values.
ISTA as "minimize an upper bound". Replace the smooth part $f$ by its quadratic upper bound with curvature $1/\eta$ (Card 2, valid for $\eta \le 1/L$ ), keep the L1 term exact, and complete the square. The problem splits by coordinate, and each piece is the prox with $t = \eta\lambda$ .

\mathbf w^{+} = \arg\min_{\mathbf v}\;\nabla f(\mathbf w)^\top(\mathbf v - \mathbf w) + \frac{1}{2\eta}\lVert\mathbf v - \mathbf w\rVert^2 + \lambda\lVert\mathbf v\rVert_1 = \arg\min_{\mathbf v}\;\frac{1}{2\eta}\big\lVert\mathbf v - \big(\mathbf w - \eta\nabla f(\mathbf w)\big)\big\rVert^2 + \lambda\lVert\mathbf v\rVert_1

$\arg\min_{\mathbf v}$: the $\mathbf v$ that makes what follows smallest
$\mathbf v$: a candidate next weight vector
$\lVert\mathbf v\rVert_1$: the L1 norm: the sum of the absolute weights

Toy, lasso convention $(1/n)\lVert y - Xw\rVert ^{2} + \lambda\lVert w\rVert _{1}$ , with $\eta = 0.1$ and $\lambda = 4$ from $w = 0$ : the gradient step gives (1.333, 1.167), and the shrink subtracts $\eta\lambda = 0.4$ from each. The simulated ISTA step gives the same (0.933, 0.767) (Drill 14).

(0,\; 0) \xrightarrow{\;-\eta\nabla f\;} (1.333,\; 1.167) \xrightarrow{\;\text{shrink by } 0.4\;} (0.933,\; 0.767)

$\xrightarrow{\;-\eta\nabla f\;}$: take a gradient step on the smooth part
$\xrightarrow{\;\text{shrink by } 0.4\;}$: soft-threshold each weight toward 0 by $\eta\lambda = 0.4$

Where ISTA ends at $\lambda = 4$ : both weights stay positive, so stationarity uses $\operatorname{sign}(w) = (1, 1)$ and is a linear solve.

\tfrac13\begin{pmatrix} 10w_1 + 5w_2 - 40\\ 5w_1 + 10w_2 - 35\end{pmatrix} + \begin{pmatrix} 4\\ 4\end{pmatrix} = \mathbf 0 \;\Rightarrow\; \mathbf w = (2.2,\; 1.2)

The ends of the lasso path. Zero is optimal exactly when every gradient coordinate at 0 fits inside $[-\lambda, \lambda]$ , so $\lambda_{\max} = \lVert \nabla f(0)\rVert _\infty = 40/3 = 13.33$ . Items leaves the model first: with $w_{\text{items}} = 0$ , $w_{\text{km}} = (40 - 3\lambda)/10$ , and items' gradient stays inside the band once $\lambda \ge 10$ , where $w_{\text{km}} = 1$ .

\Big|\tfrac13\big(5w_1 - 35\big)\Big| = \Big|\tfrac13\Big(\tfrac{5(40 - 3\lambda)}{10} - 35\Big)\Big| = 5 + \frac\lambda2 \le \lambda \iff \lambda \ge 10

Why plain subgradient descent never lands on 0: its step $-\eta\lambda\cdot \operatorname{sign}(w)$ has a fixed size, so it jumps back and forth across zero. At $\lambda = 11$ and $\eta = 0.01$ , the last 1,000 iterates of $w_{\text{items}}$ contain no exact zeros, while ISTA returns exactly (0.7, 0).
Other proximal operators reuse the same move. For the squared L2 penalty the prox is a multiplicative shrink, which is weight decay. For the indicator of a set $C$ (0 inside, $\infty$ outside) the prox is projection onto $C$ , so projected GD (Card 15) is proximal GD.

\text{prox}_{\frac t2\lVert\cdot\rVert^2}(\mathbf z) = \arg\min_{\mathbf v}\;\tfrac12\lVert\mathbf v - \mathbf z\rVert^2 + \tfrac t2\lVert\mathbf v\rVert^2 = \frac{\mathbf z}{1 + t}, \qquad \text{prox}_{\iota_C}(\mathbf z) = \arg\min_{\mathbf v\in C}\tfrac12\lVert\mathbf v - \mathbf z\rVert^2 = \Pi_C(\mathbf z)

$\text{prox}_{\frac t2\lVert\cdot\rVert^2}(\mathbf z)$: the prox of a squared L2 penalty: weight decay's shrink
$\mathbf z$: the input vector being shrunk or projected
$\text{prox}_{\iota_C}(\mathbf z)$: the prox of $\iota_C$ , the indicator of set $C$ (0 inside, ∞ outside)
$\arg\min_{\mathbf v\in C}$: the $\mathbf v$ inside the set $C$ that minimizes what follows
$\Pi_C(\mathbf z)$: projection: the point of $C$ nearest to $\mathbf z$
$\tfrac t2$: half the L2 penalty strength $t$

Key move. +L (optimality with a subgradient) and T (the quadratic upper bound in step 4).

Common slip. Thresholding at $\lambda$ instead of $\eta\lambda$ in ISTA. Getting the threshold's constant wrong across conventions: Ch 1, Q44 has $\lambda/2$ because its loss had no $\tfrac12$ in front of the squared error. Writing sign(w) where it should be sign(z).

How it's asked. "Your teammate's lasso trained by gradient descent never gives exact zeros; coefficients hover at ±0.001. Why, and what's the fix?" (Q25, Drill 14.) Strong answer: the case analysis, ISTA as "step, then shrink", then FISTA (momentum for the proximal step) and coordinate descent, which is what scikit-learn's Lasso uses, with the same soft-threshold applied one coordinate at a time.

Card 17 · Classifying stationary points and escaping saddles ★★

Statement. At a point where the gradient is zero, the signs of the Hessian's eigenvalues decide its type: all positive is a minimum, all negative a maximum, mixed a saddle. Along a negative-curvature direction gradient descent grows the error by $(1 + \eta\lvert \lambda\rvert )$ per step, so escaping takes a number of steps logarithmic in how close to the saddle it started.

\nabla L(\mathbf w_0) = \mathbf 0:\;\; L(\mathbf w_0 + \mathbf d) \approx L(\mathbf w_0) + \tfrac12\sum_i\lambda_i z_i^2, \qquad z_k = (1 + \eta|\lambda|)^k z_0 \;\Rightarrow\; k_{\text{escape}} = \frac{\ln(z_{\text{target}}/z_0)}{\ln(1 + \eta|\lambda|)}

$\mathbf w_0$: a stationary point: where the gradient is zero
$\mathbf d$: a small move away from it
$\sum_i$: add up over the Hessian's eigen-axes $i$
$\lambda_i$: the curvature along axis $i$ : positive bends up, negative bends down
$z_i$: the move's component along axis $i$
$z$: the distance from the saddle along a downhill-bending axis; subscript = step
$\lambda$: a negative eigenvalue: the curvature along the escape axis
$k_{\text{escape}}$: the number of steps needed to escape
$z_{\text{target}}$: the distance that counts as escaped

Derivation.

Second-order Taylor at a stationary point: the gradient term vanishes, so the Hessian alone describes the neighborhood. Rotate to its eigenbasis.

L(\mathbf w_0 + \mathbf d) = L(\mathbf w_0) + \underbrace{\nabla L(\mathbf w_0)^\top\mathbf d}_{0} + \tfrac12\mathbf d^\top H\mathbf d + \dots = L(\mathbf w_0) + \tfrac12\sum_i\lambda_i z_i^2 + \dots

Read off the signs. If every $\lambda_{i} > 0$ , every small move goes up: a minimum. If every $\lambda_{i} < 0$ , a maximum. If some are positive and some negative, some directions go up and some down: a saddle. If some $\lambda_{i} = 0$ , the test is inconclusive and higher-order terms decide ( $w^{4}$ has a minimum at 0, $w^{3}$ does not).
Check on the double well $f(w) = w^{4} - 3w^{2} + w$ , whose second derivative is $12w^{2} - 6$ . The curvature is 14.3 at $w = -1.30$ (the global minimum, $f = -3.51$ ), 9.35 at $w = 1.13$ (a local minimum, $f = -1.07$ ) and −5.65 at $w = 0.170$ (a maximum, which is also the boundary between the two basins). Gradient descent from −2, −0.5 and 0.1 ends in the global minimum; from 0.3 and 2, in the local one.
Near a saddle, linearize gradient descent mode by mode as in Card 5. For a negative eigenvalue the factor $1 - \eta\lambda$ exceeds 1, so the error grows geometrically; for a positive one it shrinks as usual.

z_{k+1} = (1 - \eta\lambda)\,z_k = (1 + \eta|\lambda|)\,z_k \;\Rightarrow\; z_k = (1 + \eta|\lambda|)^k z_0

Drill 12: $L = \tfrac12(a^{2} - b^{2})$ , $\eta = 0.1$ , start $b_{0} = 10^{-6}$ , escape when $\lvert b\rvert$ reaches 1. The simulation takes 145 steps.

k = \frac{\ln(1/10^{-6})}{\ln(1.1)} = \frac{13.82}{0.0953} = 145

Noise shortens the wait. Adding noise of size $\sigma = 0.01$ per step means $b$ no longer starts at $10^{-6}$ but at about the noise level, so the count is roughly $\ln(1/0.01)/\ln 1.1 \approx 48$ . The simulation's mean over 2,000 seeds is 47.2. On the quartic saddle $\tfrac12a^{2} - \tfrac12b^{2} + \tfrac14b^{4}$ , whose escape slows as $b$ nears the minima at ±1, plain GD takes 139 steps to reach $\lvert b\rvert = 0.5$ .
Newton is attracted to the saddle instead. It solves $\nabla L = 0$ , so on $L = \tfrac12(a^{2} - b^{2})$ one step from any point lands exactly on the saddle at the origin.

H = \begin{pmatrix} 1 & 0\\ 0 & -1\end{pmatrix},\quad \nabla L = \begin{pmatrix} a\\ -b\end{pmatrix} \;\Rightarrow\; \mathbf w - H^{-1}\nabla L = \begin{pmatrix} a - a\\ b - b\end{pmatrix} = \begin{pmatrix} 0\\ 0\end{pmatrix}

$a$: the first coordinate of the saddle $L = \tfrac12(a^2 - b^2)$ : curving up
$b$: the second coordinate: curving down
$H$: the saddle's Hessian: curvature +1 along $a$ , −1 along $b$

Key move. T (second order at a stationary point), then R.

Common slip. "Zero gradient means a minimum." "A zero eigenvalue with the rest positive means a minimum" (inconclusive). "GD gets stuck at saddles forever": it slows down near them and leaves unless it starts exactly on the directions that flow into the saddle, a set of measure zero; noise makes even that irrelevant.

How it's asked. "A research lead blames slow training on local minima, but the Hessian at the end has many negative eigenvalues. What is going on?" (Q35; Q12, Drill 12.) Strong answer: negative eigenvalues mean a saddle, not a minimum; in high dimensions, stationary points with mixed signs vastly outnumber minima; escape time is logarithmic and noise shortens it; and Newton is the method that does get stuck there (the third "too").

Card 18 · GD from zero finds the minimum-norm solution ★★★

Statement. For least squares with more weights than rows ( $X$ of size $n \times p$ with $n < p$ and full row rank), infinitely many weight vectors fit the data exactly. Gradient descent started at $w = 0$ converges to the one with the smallest norm, $X^{+}y = X^\top(XX^\top)^{-1}y$ .

\mathbf w_0 = \mathbf 0 \;\Rightarrow\; \mathbf w_k \to X^{+}\mathbf y = X^\top(XX^\top)^{-1}\mathbf y = \arg\min\big\{\lVert\mathbf w\rVert : X\mathbf w = \mathbf y\big\}

$\mathbf w_0$: the starting weights, here zero
$X$: the $n \times p$ feature matrix, with more columns than rows
$X^{+}$: the pseudo-inverse of $X$ : returns the shortest exact fit
$\mathbf y$: the vector of delivery times
$(XX^\top)^{-1}$: inverse of the rows' inner-product matrix
$\arg\min$: the $\mathbf w$ that minimizes what follows
$\lVert\mathbf w\rVert$: the length of $\mathbf w$
$\mathbf w$: the weight vector (in this card: 10 weights, only 6 orders)

Derivation.

Every gradient is a combination of the rows of $X$ , so every update lies in the row space. Starting from 0, induction keeps every iterate there.

\mathbf w_{k+1} = \mathbf w_k + \frac{2\eta}{n}X^\top(\mathbf y - X\mathbf w_k), \qquad \mathbf w_k = X^\top\boldsymbol\alpha_k \;\Rightarrow\; \mathbf w_{k+1} = X^\top\Big(\boldsymbol\alpha_k + \frac{2\eta}{n}(\mathbf y - X\mathbf w_k)\Big)

$\boldsymbol\alpha$: coefficients writing $\mathbf w_k$ as a combination of $X$ 's rows; subscript = step

Rotate to the eigenbasis of $H = (2/n)X^\top X$ . Row-space directions have positive eigenvalues, so with $\eta < 2/\lambda_{\max}$ they converge (Card 5). Null-space directions ( $Xu = 0$ ) have eigenvalue 0 and factor exactly 1: GD never moves along them.
The limit fits the data (the loss is convex with minimum 0 and every row-space mode converges) and lies in the row space. Those two facts determine it.

\mathbf w_\infty = X^\top\boldsymbol\alpha,\quad X\mathbf w_\infty = \mathbf y \;\Rightarrow\; XX^\top\boldsymbol\alpha = \mathbf y \;\Rightarrow\; \mathbf w_\infty = X^\top(XX^\top)^{-1}\mathbf y = X^{+}\mathbf y

$\mathbf w_\infty$: where GD ends up after infinitely many steps

It has the smallest norm. Any exact fit is $X^{+}y$ plus a null-space vector $u$ . The cross term vanishes because $u^\top X^\top = (Xu)^\top = 0$ , so the norms add like Pythagoras.

\lVert X^{+}\mathbf y + \mathbf u\rVert^2 = \lVert X^{+}\mathbf y\rVert^2 + 2\,\mathbf u^\top X^\top(XX^\top)^{-1}\mathbf y + \lVert\mathbf u\rVert^2 = \lVert X^{+}\mathbf y\rVert^2 + \lVert\mathbf u\rVert^2

$\mathbf u$: any null-space vector: $X\mathbf u = \mathbf 0$

From any other start, the null-space part of $w_{0}$ is frozen (step 2), so GD lands on the minimum-norm fit plus that part.

\mathbf w_\infty = X^{+}\mathbf y + P_{\text{null}}\,\mathbf w_0

$P_{\text{null}}$: projection onto the null space of $X$

Check on the underdetermined toy (the six orders plus eight random menu flags: 10 weights, 6 rows, rank 6). GD from 0 lands within $1.2 \times 10^{-14}$ of $X^{+}y$ , whose norm is 5.44. From a random start it lands 2.06 away from $X^{+}y$ (norm 5.82), matching $X^{+}y$ plus the start's null-space part to $1.1 \times 10^{-14}$ .
Drill 16: minimize $(w_{1} + w_{2} - 2)^{2}$ . Here $X = (1, 1)$ and $y = 2$ , so the null space is the direction (1, −1).

X^{+}y = \frac{(1,\; 1)^\top}{2}\cdot 2 = (1,\; 1), \qquad P_{\text{null}}(3,\; 0) = \frac{(3, 0)\cdot(1, -1)}{2}\,(1,\; -1) = (1.5,\; -1.5) \;\Rightarrow\; \mathbf w_\infty = (2.5,\; -0.5)

$y$: the single target, 2

The preconditioner changes the answer. With a fixed positive-definite $P$ , the update $-\eta P\nabla L$ keeps iterates from 0 in the span of $PX^\top$ , and the Lagrangian of "minimize $w^\top P^{-1}w$ subject to $Xw = y$ " puts its solution there too. So a fixed $P$ picks the solution smallest in $w^\top P^{-1}w$ , not in $\lVert w\rVert$ . Adam's $P$ changes during training, so its implicit bias has no equally simple form.

\min_{\mathbf w}\;\tfrac12\mathbf w^\top P^{-1}\mathbf w \;\;\text{s.t.}\;\; X\mathbf w = \mathbf y \;\Rightarrow\; P^{-1}\mathbf w = X^\top\boldsymbol\nu \;\Rightarrow\; \mathbf w = PX^\top\boldsymbol\nu

$\min_{\mathbf w}$: the smallest value over all weight vectors
$P$: a fixed positive-definite preconditioner
$P^{-1}$: the inverse of $P$
$\boldsymbol\nu$: the Lagrange multipliers, one per row

Key move. R (null-space modes have factor 1), then U.

Common slip. "GD finds the minimum-norm solution from any start": only from 0 (or any start in the row space). Thinking ridge regression with $\lambda \to 0$ gives a different answer: it converges to the same $X^{+}y$ .

How it's asked. "Least squares with more features than rows has infinitely many perfect fits. Which one does gradient descent return, and why?" (Q37, Drill 16; Ch 1, Q67 follow-up.) Strong answer: row-space argument plus Pythagoras, the frozen null-space part, and the link to implicit regularization and benign overfitting (Ch 4), with the caveat that the answer depends on the optimizer's geometry.

Card 19 · The linear scaling rule and the gradient noise scale ★★★

Statement. Because SGD's noise enters through $\eta/B$ (Card 9), scaling the batch by $k$ and the step by $k$ leaves the dynamics nearly unchanged, as long as $k\eta$ stays well inside the stability limit. The critical batch size $B_{\text{noise}} = \operatorname{tr} \Sigma/\lVert \nabla L\rVert ^{2}$ marks where a bigger batch stops buying proportionally fewer steps.

(B, \eta) \to (kB, k\eta) \text{ preserves the dynamics while } k\eta\,\lambda_{\max} \ll 2, \qquad B_{\text{noise}} = \frac{\operatorname{tr}\Sigma}{\lVert\mathbf G\rVert^2}, \qquad \frac{\text{progress per step}}{\text{full-batch progress}} = \frac{B}{B + B_{\text{noise}}}

$k$: the factor batch size and step are both scaled by
$B_{\text{noise}}$: the critical batch size: beyond it, bigger batches buy few extra steps
$\lVert\mathbf G\rVert^2$: the squared length of the full gradient

Derivation.

From Card 9, the floor in each mode is $\eta\sigma^{2}/(2B(2 - \eta\lambda))$ , which depends on $\eta$ and $B$ only through $\eta/B$ when $\eta\lambda$ is small.
Compare $k$ small steps with batch $B$ to one big step with batch $kB$ and step $k\eta$ , assuming the full gradient $G$ barely changes over the $k$ small steps. The means agree, and so do the noise covariances.

\underbrace{\mathbf w - \eta\sum_{j=1}^{k}\mathbf g_{B,j}}_{k \text{ steps of batch } B} \approx \mathbf w - k\eta\,\mathbf G - \eta\sum_{j=1}^{k}\boldsymbol\xi_j, \qquad \text{Cov} = k\,\eta^2\,\frac{\Sigma}{B}

$\sum_{j=1}^{k}$: add up over the $k$ small steps
$\mathbf g_{B,j}$: the batch- $B$ gradient at small step $j$
$\boldsymbol\xi_j$: the noise in small step $j$ 's gradient
$\mathbf w$: the current weight vector

\underbrace{\mathbf w - k\eta\,\mathbf g_{kB}}_{1 \text{ step of batch } kB}: \qquad \text{mean } \mathbf w - k\eta\,\mathbf G, \qquad \text{Cov} = (k\eta)^2\,\frac{\Sigma}{kB} = k\,\eta^2\,\frac{\Sigma}{B}

$\mathbf g_{kB}$: the gradient from one batch of $kB$ orders

Where it breaks. The big step must be stable, $k\eta < 2/\lambda_{\max}$ (Card 5), and the factor $1/(2 - \eta\lambda)$ in the floor grows as $k\eta$ rises. WP2 holds $\eta/B$ fixed at 0.03: the floor is 0.0305 at $(\eta, B) = (0.03, 1)$ , 0.0319 at (0.12, 4) and 0.0395 at (0.48, 16). On the 10k orders with a fixed budget of 2 epochs, going from $B = 32$ ( $\eta = 0.02$ , excess loss 0.0087) to $B = 256$ with 8× the step gives 0.0207, while keeping the old step gives 0.899. At $B = 2{,}048$ , the 64× step ( $\eta = 1.28$ ) is past the cliff at 0.733 and diverges; 32× ( $\eta = 0.64$ ) gives 0.332 with only 9 steps.
The critical batch. Expand the expected loss after one step with batch $B$ (T), using $E[g_B] = G$ and $\text{Cov} = \Sigma/B$ (E).

\mathbb E\big[L(\mathbf w - \eta\mathbf g_B)\big] \approx L(\mathbf w) - \eta\lVert\mathbf G\rVert^2 + \frac{\eta^2}{2}\Big(\mathbf G^\top H\mathbf G + \frac{\operatorname{tr}(H\Sigma)}{B}\Big)

$\mathbf G^\top H\mathbf G$: the curvature along the full gradient, times its squared length
$\operatorname{tr}(H\Sigma)$: the noise weighted by curvature: how much noise raises the loss
$H$: the Hessian of the loss at the current weights

Choose the best $\eta$ for that batch (set the derivative to zero). The best achievable drop is the full-batch drop divided by $1 + B_{\text{noise}}/B$ .

\eta_{\text{opt}}(B) = \frac{\lVert\mathbf G\rVert^2}{\mathbf G^\top H\mathbf G + \operatorname{tr}(H\Sigma)/B}, \qquad \Delta L_{\text{opt}}(B) = \frac{\Delta L_{\max}}{1 + B_{\text{noise}}/B}, \qquad \Delta L_{\max} = \frac{\lVert\mathbf G\rVert^4}{2\,\mathbf G^\top H\mathbf G}, \quad B_{\text{noise}} = \frac{\operatorname{tr}(H\Sigma)}{\mathbf G^\top H\mathbf G}

$\eta_{\text{opt}}(B)$: the best step size for batch size $B$
$\Delta L_{\text{opt}}(B)$: the best expected one-step drop with batch size $B$
$\Delta L_{\max}$: the best one-step drop with the full batch

If $H$ is roughly a multiple of the identity, $H$ cancels and $B_{\text{noise}}$ reduces to the simple noise scale $\operatorname{tr} \Sigma/\lVert G\rVert ^{2}$ . Steps needed scale as $1 + B_{\text{noise}}/B$ and examples needed as $B + B_{\text{noise}}$ : below $B_{\text{noise}}$ , doubling $B$ nearly halves the steps; above it, it mostly wastes examples.
Drill 18: $\operatorname{tr} \Sigma = 100$ and $\lVert G\rVert ^{2} = 0.5$ give $B_{\text{noise}} = 200$ . The progress per step, as a fraction of the full-batch progress, is $B/(B + 200)$ : 0.2, 0.333, 0.5, 0.667, 0.8 and 0.889 for $B = 50$ , 100, 200, 400, 800 and 1,600; the simulation matches to three digits.
On the 10k orders at $w = 0$ the noise scale is 8,330/2,222 = 3.75: tiny, because the gradient is huge far from the optimum. As training approaches $w^*$ , $\lVert G\rVert ^{2} \to 0$ while $\operatorname{tr} \Sigma$ stays near 109, so $B_{\text{noise}}$ grows: larger batches pay off later in training, which is why large runs ramp the batch size up.

Key move. E and T (steps 4–5), plus Card 9's floor (step 1).

Common slip. "Linear scaling works for any $k$ ": it fails once $k\eta$ nears $2/\lambda_{\max}$ , which is why large-batch training needs warmup. " $B_{\text{noise}}$ is a property of the dataset": it changes during training. Writing $\operatorname{tr} \Sigma/\lVert G\rVert$ without the square.

How it's asked. "Moving from 1 GPU ( $B = 256$ ) to 8 GPUs ( $B = 2{,}048$ ) made epochs 7× faster but final error worse. What happened and what would you change?" (Q28, Drill 18.) Strong answer: the $\eta/B$ argument, scale $\eta$ by 8 with warmup, check that $8\eta$ stays below the stability limit, and compare $B$ with the noise scale; for adaptive optimizers a square-root scaling of $\eta$ is often recommended instead of linear.

Card 20 · Stability selects flat minima ★★★

Statement. Gradient descent with step $\eta$ can only settle at a minimum whose sharpest curvature is below $2/\eta$ . So larger steps (and more gradient noise) rule out sharp minima; "edge of stability" is training pushing sharpness up to that bound.

\text{GD can settle at } \mathbf w^\star \iff \lambda_{\max}\big(H(\mathbf w^\star)\big) < \frac{2}{\eta}

$\mathbf w^\star$: a minimum that GD might settle in
$H(\mathbf w^\star)$: the Hessian at that minimum

Derivation.

Near a minimum, Taylor turns the loss into a quadratic with Hessian $H(w^*)$ , and Card 5 applies to the error: the minimum is stable for GD only if every mode's factor has size below 1. A minimum sharper than $2/\eta$ can't hold the iterates: any small perturbation in its sharpest direction grows.

\mathbf e_{k+1} \approx \big(I - \eta H(\mathbf w^\star)\big)\,\mathbf e_k, \qquad |1 - \eta\lambda_{\max}| < 1 \iff \lambda_{\max} < \frac{2}{\eta}

The flat-vs-sharp toy is two Gaussian dips. A dip of depth $A$ and width $s$ has curvature $A/s^{2}$ at its bottom.

f(w) = -A\,e^{-(w - c)^2/(2s^2)} \;\Rightarrow\; f''(w) = \frac{A}{s^2}\Big(1 - \frac{(w - c)^2}{s^2}\Big)e^{-(w - c)^2/(2s^2)}, \qquad f''(c) = \frac{A}{s^2}: \quad \frac{1}{0.15^2} = 44.4\;(\text{sharp}), \quad \frac{0.9}{1.0^2} = 0.9\;(\text{flat})

$f(w)$: one Gaussian dip in the 1-D loss
$w$: the single weight
$A$: the dip's depth
$e$: Euler's number, 2.718…
$c$: the dip's center (its bottom)
$s$: the dip's width
$f''$: the dip's curvature
$f''(c)$: the curvature at the bottom: $A/s^2$

Read off. At $\eta = 0.1$ , $2/\eta = 20 < 44.4$ : the sharp mode's factor is $1 - 0.1 \times 44.4 = -3.44$ , so GD can't settle there, while the flat mode's factor is 0.91. At $\eta = 0.01$ , $2/\eta = 200$ : both are stable (factors 0.556 and 0.991). The threshold is $\eta = 2/44.4 = 0.045$ .
Check against the simulation (1,000 starts uniform on [−4, 4], 2,000 steps, small noise). At $\eta = 0.01$ , 64.1% of runs end in the flat minimum and 19% settle in the sharp one. At $\eta = 0.1$ , 67.3% end in the flat one and 0% settle in the sharp one, but the same 19% stay trapped bouncing inside the sharp well with spread 0.16: its walls flatten away from the bottom, so the bounce never throws them out. "Can't settle" is not "always leaves".
Noise adds a softer version of the same pressure. Card 9's floor in a mode is $\eta\sigma_{i}^{2}/(2B(2 - \eta\lambda_{i}))$ ; it rises with curvature and blows up as $\eta\lambda_{i} \to 2$ . If the gradient noise also grows with curvature (for a well-specified likelihood loss, the gradient covariance at the optimum is close to the Hessian, $\sigma_{i}^{2} \approx c\lambda_{i}$ ), sharp modes cost the most excess loss, so larger $\eta$ or smaller $B$ push toward flatter regions. This is an argument, not a theorem.

\mathbb E[L_i] - L_i^\star = \frac{\eta\,\sigma_i^2}{2B(2 - \eta\lambda_i)} \;\overset{\sigma_i^2 \approx c\lambda_i}{=}\; \frac{\eta\,c\,\lambda_i}{2B(2 - \eta\lambda_i)}

$\mathbb E[L_i] - L_i^\star$: the excess loss SGD keeps in mode $i$
$c$: a constant linking noise to curvature

Even without noise, GD prefers flatter paths. Look for a continuous flow whose state after time $\eta$ matches one GD step to second order. Taylor-expand the flow, using $\ddot w = -H\dot w = H\nabla L + O(\eta)$ .

\dot{\mathbf w} = -\nabla L + \eta\,\mathbf f_1 \;\Rightarrow\; \mathbf w(\eta) = \mathbf w + \eta\dot{\mathbf w} + \tfrac{\eta^2}{2}\ddot{\mathbf w} + O(\eta^3) = \mathbf w - \eta\nabla L + \eta^2\Big(\mathbf f_1 + \tfrac12 H\nabla L\Big) + O(\eta^3)

$\dot{\mathbf w}$: the flow's velocity: how fast the weights move in continuous time (dot = time derivative)
$\mathbf f_1$: the correction term the flow needs to match GD
$\mathbf w(\eta)$: the flow's position after time $\eta$
$\ddot{\mathbf w}$: the flow's acceleration (two dots = second time derivative)
$O(\eta^3)$: terms that shrink like $\eta^3$ or faster

Matching the GD step $w - \eta\nabla L$ requires $f_{1} = -\tfrac12H\nabla L$ . Since the gradient of $\tfrac12\lVert \nabla L\rVert ^{2}$ is $H\nabla L$ , the flow is plain gradient flow on a modified loss with a gradient-norm penalty: GD is pulled toward regions where the gradient stays small nearby, which are the flat ones.

\dot{\mathbf w} = -\nabla L - \frac\eta2 H\nabla L = -\nabla\Big(L + \frac\eta4\lVert\nabla L\rVert^2\Big)

$\frac\eta2$: half the step size
$\frac\eta4$: a quarter of the step size: the strength of the implicit gradient penalty

In neural networks, sharpness tends to rise during training until $\lambda_{\max}$ hovers near $2/\eta$ and the loss keeps falling non-monotonically: the "edge of stability" (Cohen et al., 2021). The bound in step 1 is the ceiling it hits. The caveat interviewers want: sharpness depends on the parameterization. Rescaling one layer up and the next down leaves the network's function unchanged but can make a flat minimum arbitrarily sharp (Dinh et al., 2017), so sharpness alone can't be the explanation for generalization.

Key move. R (local eigenvalues) and T (local quadratic in step 1; flow expansion in steps 6–7).

Common slip. Stating "SGD finds flat minima, and flat minima generalize" as a theorem. Reading "can't settle" as "always escapes" (step 4). Forgetting that sharpness is not invariant to reparameterization.

How it's asked. " $B = 8{,}192$ matches $B = 256$ on training loss but is worse on test. Someone says 'sharp minima'. Evaluate the claim." (Q36, Drill 13.) Strong answer: the $2/\eta$ stability argument and the $\eta/B$ noise argument, the implicit gradient penalty, edge of stability as evidence, the reparameterization critique, and SAM (sharpness-aware minimization) as the method that targets flatness directly.

Practice protocol

Read only the Statement. Cover the rest of the card.
Derive on a blank page against a timer: 5 minutes for ★, 10 for ★★, 15 for ★★★. Talk out loud as if an interviewer were listening; the narration is half the grade.
Land the toy number. Every card has a check ( $\eta^* = 0.3$ , $w = (3.25, 1.5)$ , 3.16×, 145 steps…). If your derivation doesn't reproduce it, the error is in your algebra, not the toy.
Compare step by step. Mark the first step you missed or got wrong, and name the toolkit move it needed (T, R, U, E or +L). Read the Common slip and check whether you made it.
Answer "How it's asked" cold, including the strong-answer extension. This is where senior and research rounds go.
Re-derive after 48 hours, then after a week, without looking. A card is mastered when you can do it twice in a row within time and hit the check.
Run the chains. Several cards are one argument continued; practice them in one sitting:

The eigenbasis chain: Card 5 → 6 → 7 → 11 (cliff → best step → step count → momentum).
The noise chain: Card 8 → 9 → 19 (variance → floor → batch scaling).
The curvature chain: Card 2 → 3 → 14 (smoothness → Hessians → Newton and IRLS).
The constraint chain: Card 15 → 16 (KKT → prox, "step, then snap" → "step, then shrink").
The landscape chain: Card 17 → 20 → 18 (saddles → stability selection → implicit bias).

Suggested order: Cards 1–8 after the chapter's second read, then Interview Bank Levels 1–2, then Cards 9–20, then Levels 3–4.

Mastery checklist

[ ] Card 1 · Steepest descent via Cauchy–Schwarz; slope −17.7 along (0.753, 0.658) on the toy; preconditioned direction $-P^{-1}\nabla L$ .
[ ] Card 2 · Descent lemma from the integral remainder; $\eta = 1/L$ maximizes the guaranteed drop (31.39 vs actual 31.48 on the toy); Armijo accepts $\eta = 0.25$ .
[ ] Card 3 · Three convexity tests proved equivalent; MSE and logistic Hessians derived; $\sigma^{2}$ has negative curvature when $\sigma > 2/3$ .
[ ] Card 4 · Local = global by the chord argument; minimizer set convex; strict ⇒ unique; existence is not guaranteed.
[ ] Card 5 · Rotate and unroll GD on a quadratic; the four regimes; $w_{1} = (4.0, 3.5)$ at $\eta = 0.3$ by hand; loss shrinks by the factor squared.
[ ] Card 6 · Balance the extreme modes: $\eta^* = 2/(\lambda_{\max} + \lambda_{\min})$ , $\rho = (\kappa - 1)/(\kappa + 1)$ ; toy 0.3 and 0.5; $\eta^*$ hugs the cliff by $\kappa/(\kappa + 1)$ .
[ ] Card 7 · $k \le (\kappa/2)\ln(1/\varepsilon)$ (991 by distance, 496 by loss on the raw 10k model); PL ⇒ $(1 - 1/\kappa)^{k}$ ; telescoping ⇒ $1/k$ ; $w^{4}$ gives $1/k^{2}$ ; non-convex ⇒ $\min\lVert \nabla L\rVert ^{2} \le 2L(L(w_{0}) - L^*)/k$ (16.0 vs $1.2 \times 10^{-10}$ on the double well).
[ ] Card 8 · Minibatch gradient unbiased, variance $\Sigma/B$ ; finite-population factor from Var(full sum) = 0; importance sampling 9.0 → 3.24.
[ ] Card 9 · Noise floor $\eta\sigma^{2}/(2B(2 - \eta\lambda))$ via the second-moment recursion (0.105 at $\eta = 0.1$ , $B = 1$ ); Robbins–Monro; $c/t$ rate needs $2c\lambda > 1$ .
[ ] Card 10 · Momentum buffer as a geometric sum; step $\eta/(1 - \beta)$ , window $1/(1 - \beta)$ ; zigzag damped by $1 + \beta$ ; classical form equivalence.
[ ] Card 11 · Heavy-ball characteristic roots of size $\sqrt{\beta}$ ; $\eta^*$ and $\beta^*$ from the band edges; toy $\beta^* = 0.0718$ , 10k $\beta^* = 0.715$ ; why 7.0× not 12×.
[ ] Card 12 · $E[m_{t}] = (1 - \beta_{1}^{t})E[g]$ by a finite geometric series; first step 3.16× without correction; 10.0 / 3.24 / 1.26 inflation; units: $c^{2} \to c$ .
[ ] Card 13 · L2 = weight decay under SGD only; $\lambda$ cancels under Adam (0.258 vs 0.905 after 1,000 steps); Adam + L2 → ridge, AdamW → ridge with $\lambda\sqrt{\hat v_{j}}$ .
[ ] Card 14 · Newton from the quadratic model; (3, 2) in one step; error squares ( $\sqrt{2}$ digits 1, 2, 5, 11); $w^{4}$ gives 2/3; IRLS derivation; Gauss–Newton.
[ ] Card 15 · KKT by cases on the cap: $w = (3.25, 1.5)$ , $\mu = 1.25$ , $dL^*/dc = -\mu$ ; projected GD in two steps; budget gives (2.5, 1.5), $\mu = 2.5$ .
[ ] Card 16 · Soft-threshold from the subgradient case analysis; ISTA as majorize-minimize; (0.933, 0.767); $\lambda_{\max} = 13.33$ , items leaves at $\lambda = 10$ .
[ ] Card 17 · Classify by Hessian signs (double well: 14.3, 9.35, −5.65); escape time $\ln(10^{6})/\ln 1.1 = 145$ ; noise ≈ 48; Newton jumps to the saddle.
[ ] Card 18 · Row-space induction, null-space modes frozen; $X^{+}y$ by Pythagoras; (1, 1) from 0 and (2.5, −0.5) from (3, 0); preconditioned version.
[ ] Card 19 · Linear scaling by matching mean and covariance of $k$ steps vs one; where it breaks; $B_{\text{noise}} = \operatorname{tr} \Sigma/\lVert G\rVert ^{2}$ from the optimal-step drop; Drill 18 gives 200.
[ ] Card 20 · Stability needs $\lambda_{\max} < 2/\eta$ (44.4 vs 20 at $\eta = 0.1$ ); "can't settle" ≠ "leaves" (19% bouncing); implicit penalty $(\eta/4)\lVert \nabla L\rVert ^{2}$ ; reparameterization caveat.