Chapter 2 — Interview Bank

Every answer here follows the same four beats. Say the first two within 20 seconds; the last two are what turn a correct answer into a strong one.

Questions are stacked by difficulty. Each level assumes everything above it.

How questions are written here. Real interviewers rarely ask "define X". They describe a situation — a training run, a loss curve, a colleague's claim about a learning rate — and watch whether you spot the concept underneath. So every question below opens with a scenario, then names the concept being tested, then gives the four beats. Every number comes from the chapter's running example: the six-order ETA toy (centered distance and items, best weights (3, 2), Hessian eigenvalues 5 and 5/3) or the 10,000-order simulation. Practice by reading only the scenario and answering out loud before you look.

Level 1 — Screen

Q1 · "What does training actually do?"

You've joined the ETA team at a food-delivery app. The PM watches the nightly job print "epoch 12/40" for forty minutes and asks: "What is the computer actually doing all that time, and how does it know when it's done?"

• Concept tested: learning as empirical risk minimization; the optimizer as a search.
• Intuition: the weights are a position on a landscape whose altitude is the average error on past orders; training walks downhill until the ground is flat.
• Answer: it searches for the weights that make the average loss on past orders as small as possible. Each epoch is one pass over the orders that nudges the weights downhill:

\hat{\mathbf w}

the trained ETA weights (hat = estimated from data; bold = a vector of all of them)

\arg\min_{\mathbf w}

the weights \mathbf w that make what follows as small as possible

n

the number of past orders

\sum_{i=1}^{n}

add up over every past order, i = 1 to n

\ell

the per-order loss: what one prediction's miss costs (e.g. squared minutes)

y_i

order i's actual delivery time in minutes

f(\mathbf x_i; \mathbf w)

the model's predicted ETA for order i, from its features \mathbf x_i (distance, items)

"Done" means the slope (the gradient) is near zero or the validation error has stopped improving, not that the model is perfect.

• Why: every model is F-L-O (Family, Loss, Optimizer), and the training job is running the O. There's also no point polishing past the data's own noise: on the 10k orders the distance weight's standard error is 0.0144 min/km, so optimizing it to 10^{-10} buys nothing (Section 1).
• Next they'll ask: "Does it find the best possible weights?" → For a convex loss like linear + MSE, yes (Q6). In general it finds a point where the slope is zero, which is not always the global best.

Q2 · "But regression has a formula"

An engineer says: "The old ETA model was fit with one call to a least-squares solver. The new one is a small neural network and needs an optimizer, a learning rate and a tolerance. Why can't we just solve for the weights like before?"

• Concept tested: closed-form vs iterative solutions.
• Intuition: a formula exists only when "slope = 0" turns into linear equations; put the weights inside a nonlinearity and the equations knot together.
• Answer: for least squares the gradient is linear in w, so setting it to zero gives a linear system with an exact solution (Ch 1, Section 3). For a network, \nabla L(w) = 0 is a system of nonlinear equations with no formula, so we walk toward a solution step by step.

\nabla L

the gradient of the loss: the vector of slopes, one per weight; points uphill

X

the data matrix: one row per order, one column per feature

X^\top

X transposed: rows become columns

\mathbf y

the vector of actual ETAs, one per order

\mathbf w

the weights (bold = a vector of all of them)

• Why: quadratic loss → linear gradient → linear equations. Logistic regression (Ch 3) already loses the closed form. Even for linear regression, iteration wins when p is huge (the solve costs about p^{3}) or the data stream in.
• Next they'll ask: "So should we always iterate?" → No. On small convex problems an exact solve or Newton's method is faster and more precise (Q22, Q33).

Q3 · Which way is downhill?

*A new hire reading the training code sees w -= lr * grad and asks: "Why do we subtract the gradient instead of adding it? And is one step guaranteed to make the loss go down?"*

• Concept tested: the gradient as steepest ascent; the first-order Taylor picture and its limit.
• Intuition: the gradient is an arrow pointing straight uphill; a small step the other way must lose altitude, but a long one can overshoot the valley and climb the far side.
• Answer: -\nabla L is the direction of steepest descent, and a small enough step is guaranteed to help. The Taylor expansion shows both the gain and its limit:

L(\mathbf w - \eta\nabla L)

the loss after one step against the gradient

L(\mathbf w)

the loss (mean squared ETA error) at the current weights

\eta

the learning rate: how far the step goes

\lVert\nabla L\rVert^2

the gradient's squared length: how steep the loss is here

\nabla L^\top H\,\nabla L

the curvature along the gradient times its squared length (^\top = transpose)

H

the Hessian: the matrix of second derivatives, the bowl's curvature in every direction

The first term always helps and grows like \eta; the curvature term charges for long steps and grows like \eta^{2}. If the curvature never exceeds L, any \eta < 2/L lowers the loss.

• Why: Cauchy–Schwarz makes -\nabla L the steepest direction (Card 1); bounding the curvature turns the expansion into the descent lemma (Card 2). On the six orders at \eta = 0.1, the linear term alone predicts the loss falls from 33.3 to 1.94; it actually falls to 9.77, because the curvature charges \tfrac12 \cdot 0.01 \cdot 1{,}565.
• Next they'll ask: "How small is small enough?" → Below 2/\lambda_{\max}, the cliff (Q4).

Q4 · "Just set the learning rate to 0.4"

A learning-rate sweep on the six-order ETA bowl gives: \eta = 0.3 converges in 10 steps, \eta = 0.39 needs 135, and \eta = 0.41 blows up. A colleague reasons: "0.3 works and 0.41 fails, so 0.4 must be fastest. Let's ship 0.4." What do you tell them?

• Concept tested: the 2/\lambda_{\max} stability cliff and the oscillating regime below it.
• Intuition: along the steepest direction of the bowl each step overshoots the valley floor; at 0.4 the overshoot is exactly as big as the miss, so you bounce forever.
• Answer: 0.4 is the cliff itself, not the sweet spot. The toy's steepest curvature is \lambda_{\max} = 5, and each step multiplies the error along that direction by 1 - 5\eta. At \eta = 0.4 that factor is exactly −1: the iterate flips between two points and never converges. The fastest fixed step is 0.3 = 2/(\lambda_{\max} + \lambda_{\min}), and the step count climbs steeply toward the cliff (135 at 0.39).

c_{\text{steep},k}

the error along the bowl's steepest direction after k steps

c_{\text{steep},0}

that error at the start

k

the step number

\lambda_{\max}

the steepest curvature (largest Hessian eigenvalue): 5 on the toy

• Why: gradient descent on a quadratic splits into one 1-D problem per Hessian eigenvector (Card 5). Hook: "1/\lambda smooth, 2/\lambda the cliff." Below 1/\lambda_{\max} = 0.2 every mode shrinks monotonically; between 0.2 and 0.4 the steep mode zigzags but shrinks; above 0.4 it grows.
• Next they'll ask: "In a real model you don't know \lambda_{\max}. How do you pick \eta?" → An LR range test, a backtracking line search, or power iteration with Hessian-vector products (WP1).

Q5 · Distance in meters

The dispatch system logs distance in meters, and a teammate trains on (meters, items), centered but not rescaled. Gradient descent blows up at \eta = 0.1. At \eta = 5 \times 10^{-7} it's stable, but after 1,000 steps the loss is 6.65 against a best of 1.67, and the items weight has barely left zero. What's wrong, and what's the fix?

• Concept tested: feature scaling and the condition number \kappa.
• Intuition: one learning rate has to serve a cliff face and a plain at once; small enough for the cliff, it freezes on the plain.
• Answer: in meters the curvature along the distance weight is about 3.33 million, while the items direction has curvature 2.5. So \kappa \approx 1.33 \times 10^{6} and the cliff is \eta_{\max} \approx 6.0 \times 10^{-7}. Any \eta safe for distance moves the items weight almost nothing: after 1,000 steps it has covered 0.125% of its way to 2, and the distance weight has absorbed items' share (4.0 min/km instead of 3). Convert to km (keeping the centering): \kappa = 3, \eta_{\max} = 0.4, ten steps at \eta = 0.3.

\kappa

the condition number: steepest over flattest curvature, how elongated the bowl is

\lambda_{\min}

the flattest curvature (smallest Hessian eigenvalue)

\varepsilon

the target: shrink the distance to the optimum to this fraction (e.g. 10^{-6})

• Why: \eta is capped by the steepest direction and progress is set by the flattest, so steps grow in proportion to \kappa (Cards 5–7).
• Next they'll ask: "Does standardizing make \kappa = 1?" → No. Two standardized features with correlation r still give \kappa = (1 + r)/(1 - r), which is 3 on the toy. Hook: "Center, then scale, then worry about correlation." "Does Adam fix it?" → Partly (Q10).

Q6 · "Is our loss convex?"

The team is comparing three ETA candidates: (a) linear model + MSE, (b) linear model + MAE, (c) two-layer network + MSE. A teammate asks which of them can get "stuck" at a bad answer, and whether any need special handling even if they can't get stuck.

• Concept tested: convexity and its guarantee; convex vs smooth.
• Intuition: a convex loss is a bowl with no false bottoms; water poured anywhere runs to the same place.
• Answer: (a) is convex and smooth: gradient descent reaches the global minimum. (b) is convex, so it can't get stuck, but it has kinks where a residual is zero; the gradient doesn't exist there, so it needs subgradients, a proximal method or a smooth stand-in like Huber, and the minimum may not be unique. (c) is non-convex: it has many stationary points and the starting point matters.

\mathbf v

any direction in weight space

\mathbf v^\top H\mathbf v

the loss's curvature along \mathbf v (^\top = transpose)

\lVert X\mathbf v\rVert^2

squared length of X\mathbf v: how much predictions move along \mathbf v; never negative

• Why: "Chord above, tangent below, curvature up" (Card 3), and for a convex function every local minimum is global (Card 4). By SAM, a convex loss of an affine map of w is convex, which covers (a) and (b); a network puts the weights inside nonlinearities.
• Next they'll ask: "Convex in what?" → In the weights. \hat y = w_{1}x + w_{2}x^{2} is curved in x, yet its MSE is convex in (w_{1}, w_{2}).

Q7 · Batch size 32 or 4,096?

The infra lead wants every training job to use the largest batch that fits on the GPU, 4,096, "for efficiency". The DS lead prefers 32. On a fixed budget of training examples, who's right, and what decides it?

• Concept tested: minibatch noise \propto 1/B, cost \propto B, and the critical batch size.
• Intuition: asking 4,096 people for directions gives a sharper answer than asking 32, but if 32 already point the same way, the other 4,064 cost time and add little.
• Answer: the minibatch gradient's variance falls like 1/B while its cost rises like B, so per example processed, small batches make more progress. On the 10k orders with a budget of 50,000 examples and \eta tuned per batch size, B = 1 and B = 32 reach excess losses of 1.67 \times 10^{-4} and 1.32 \times 10^{-4}, while B = 1{,}024, which gets only about 50 steps, stops at 2.59 \times 10^{-3}. Large batches win on wall-clock time only while the hardware processes them nearly as fast as small ones, and only up to the critical batch size.

\mathbb E

the average over every possible random minibatch

\mathbf g_B

the minibatch gradient: the average slope over B random orders

\mathbf G

the full gradient over all orders

\operatorname{tr}\Sigma

the total variance of per-order gradients (trace of their covariance \Sigma)

B

the batch size: orders per step

B_{\text{noise}}

the gradient noise scale: the batch size past which doubling B stops paying (critical batch)

\lVert\mathbf G\rVert^2

the full gradient's squared length: the signal

• Why: Card 8 gives the 1/B variance (measured on the 10k orders: 8,584 at B = 1, 275 at B = 32, 7.07 at B = 1{,}024, log-log slope −1.02). Card 19 gives the noise scale B_{\text{noise}}, past which doubling B stops halving the steps needed.
• Next they'll ask: "If we do move to 4,096, what else must change?" → Scale \eta with B (the linear scaling rule) with warmup, until the cliff or the critical batch (Q28).

Q8 · The table was sorted

A pipeline change made the nightly ETA trainer read orders straight from the warehouse table, which is stored sorted by distance, instead of from a shuffled export. Nobody touched the model code, but offline error jumped. What broke?

• Concept tested: SGD's assumption that minibatches are random samples (i.i.d., shuffled).
• Intuition: if batches arrive short trips first and long trips last, each step pulls toward whatever kind of order it just saw, and the last pull wins.
• Answer: SGD's guarantees need each minibatch gradient to be unbiased, E[g_B] = \nabla L, which holds only if the batch is a random sample. Sorted data make consecutive batches systematically different, so the gradient is biased and constant-step SGD ends wherever the final batches drag it. On the 10k orders (B = 32, \eta = 0.05), one epoch in stored order ends 18.8 from w^* in weight space against 0.22 shuffled; the excess loss is 350.5 against 0.035, and the intercept sits near 40 minutes instead of 21.6. Fix: reshuffle every epoch.
• Why: unbiasedness is a property of how the batch is drawn, not of the gradient formula (Card 8). This is the U in SCUBA, and the first of the four S's: Shuffle, Stratify, Sample by importance, Scale.
• Next they'll ask: "How would you have caught it from the dashboard?" → A sawtooth with the epoch period (14.7 ↔ 201 over five epochs in stored order) and a shuffle on/off A/B (Q23).

Q9 · Momentum made it faster, then it oscillated

Adding momentum \beta = 0.9 to SGD sped up ETA training noticeably. Encouraged, a teammate raised it to 0.99 without touching the learning rate, and the loss began swinging up and down. Explain both effects.

• Concept tested: momentum as an exponential moving average; the effective step \eta/(1 - \beta).
• Intuition: a heavy ball rolls through the side-to-side bumps but keeps going downhill; a much heavier one overshoots before it can turn around.
• Answer: momentum steps along a running average of past gradients. Zigzags across a ravine cancel; the steady push along it adds up, which is the speedup. But on a steady slope the step grows to \eta/(1 - \beta): 10\eta at \beta = 0.9 and 100\eta at \beta = 0.99. Raising \beta to 0.99 without lowering \eta made the effective step 10 times bigger and the memory 100 steps long, so the iterate overshoots and swings.

\mathbf v_k

the momentum velocity at step k: a running sum of past gradients

\nabla L

the gradient; the subscript is the step it was taken at

\beta

the momentum coefficient: the fraction of the old velocity kept each step (0.9 or 0.99)

\mathbf g

a gradient that stays the same every step

\frac{\mathbf g}{1 - \beta}

where the velocity settles: 1/(1 - \beta) copies of the gradient (10 at \beta = 0.9)

• Why: unroll the velocity: a geometric series (Card 10). Hook: "\beta is memory: window 1/(1 - \beta), step \eta/(1 - \beta)."
• Next they'll ask: "Then how do you pick \beta?" → On a quadratic the optimum is \beta^* = ((\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1))^{2} (Q27). In practice, raise \beta and lower \eta together.

Q10 · "Why does everyone use Adam?"

A product manager notices that almost every model the team trains uses Adam and asks: "What does Adam do that plain gradient descent doesn't? Is it ever the wrong choice?"

• Concept tested: per-parameter adaptive steps, and their limits.
• Intuition: Adam gives every weight its own step size by dividing by how big that weight's gradients usually are, so steep and shallow directions move at similar speeds.
• Answer: Adam is momentum, plus a per-weight division by the root of a running average of squared gradients, plus a bias correction for starting the averages at zero. Each weight then moves about \eta per step whatever its gradient's scale, so it tolerates badly scaled features and needs less tuning. On the six orders with distance in meters, GD at any single \eta diverges or freezes; Adam with \eta = 0.05 reaches loss 1.676 (best 1.667) in 300 steps. It can be the wrong choice: it ignores correlation between features, stores two extra numbers per weight, sometimes generalizes worse than tuned SGD + momentum on vision models, and is slower than L-BFGS or Newton on small convex problems.
• Why: Adam is a diagonal preconditioner (the four D's, Card 12). Under a unit change x \to c\cdot x, GD needs step sizes c^{2} apart; Adam needs them only c apart. For meters that's 10^{3} instead of 10^{6}: much better, not invariant.
• Next they'll ask: "Adam or AdamW?" → AdamW, whose weight decay isn't distorted by the adaptive denominator (Q20).

Q11 · Why does the learning rate go down?

A training dashboard shows the learning rate rising linearly for the first 1,000 steps, then falling along a cosine curve toward zero. The PM asks why you don't simply keep it at the value that works best.

• Concept tested: warmup and decay; the SGD noise floor.
• Intuition: with noisy steps you rattle around the bottom of the valley; to settle, the steps have to shrink. And at the start, big steps from a bad position are the riskiest.
• Answer: with a constant \eta, minibatch noise keeps SGD bouncing at a floor proportional to \eta/B; decaying \eta removes it. On the 10k orders (20 epochs, B = 32, peak \eta = 0.1) the final excess loss is 0.0373 with a constant rate, against 1.00 \times 10^{-4} for step decay, 1.58 \times 10^{-4} for cosine and 1.65 \times 10^{-4} for warmup + cosine. Warmup protects the first steps, when gradients are large and Adam's running averages are still unreliable.
• Why: the noise floor is \approx \eta\sigma^{2}/(4B) per direction; it vanishes only if \eta_{t} \to 0 with \sum\eta_{t} = \infty and \sum\eta_{t}^{2} < \infty (Robbins–Monro, Card 9). Hook: "Warm up, hold, cool down."
• Next they'll ask: "Can you beat the floor without decaying?" → Average the iterates: with constant \eta the average over the second half of training reaches 5.76 \times 10^{-6} (Q18).

Q12 · "Stuck in a local minimum"

Two training runs of the neural ETA model, identical except for the random seed, finish with validation losses about 0.6% apart. The PM asks whether the worse one is "stuck in a local minimum", and suggests running 50 seeds and shipping the best.

• Concept tested: non-convex landscapes; why most minima found by SGD are comparable.
• Intuition: a large network's landscape is less a mountain range with one deep lake than a broad valley floor with many nearly equal low spots, mostly connected.
• Answer: probably nothing is wrong. Different seeds land in different minima, but in wide networks the minima SGD finds tend to have similar loss and are often joined by low-loss paths (mode connectivity). Compare the gap with the seed-to-seed spread before acting. Truly bad local minima are rare in high dimensions; saddles and plateaus are the usual slowdowns. And shipping the best of 50 seeds on validation overfits the validation set.
• Why: on a non-convex loss the start does decide the end (on the double well w^{4} - 3w^{2} + w, starts at −2, −0.5 and 0.1 reach the global minimum, starts at 0.3 and 2 the local one), but high-loss stationary points in many dimensions almost always have some downhill direction, i.e. they're saddles (Card 17).
• Next they'll ask: "Then what do seeds change?" → Initialization and data order. Report the mean and spread across seeds, or average the runs as an ensemble.

Level 2 — Onsite core

Q13 · Six orders on the whiteboard

The interviewer writes six centered orders: distance d_{1} = (-2, -1, 0, 0, 1, 2), items d_{2} = (-1, -2, 2, 0, 1, 0), ETA \tilde y = (-6, -9, 3, 0, 5, 7). "The loss is mean squared error. Compute the gradient at w = 0 by hand, take one step with \eta = 0.1, and tell me whether the loss went down."

• Concept tested: computing \nabla L = -(2/n)X^\top(y - Xw) by hand.
• Intuition: the gradient is each feature column, weighted by how badly each order is missed.
• Answer: at w = 0 every residual is \tilde y itself, so the gradient needs only \sum d_{1}\tilde y = 40 and \sum d_{2}\tilde y = 35:

\nabla L(\mathbf 0)

the gradient at w = (0, 0): one slope per weight (distance, items); points uphill

\mathbf 0

the starting weights: both zero

\mathbf w_1

the weights after one step with \eta = 0.1

The loss falls from 200/6 = 33.33 to 9.77.

• Why: the chain rule on (1/n)\sum(y_{i} - w^\top x_{i})^{2} gives -(2/n)\sum x_{i}\cdot r_{i} (Card 1). Both components are negative, so both weights should rise.
• Next they'll ask: "Where's the exact answer?" → Solve 10w_{1} + 5w_{2} = 40, 5w_{1} + 10w_{2} = 35: w = (3, 2). Or take one Newton step (Q21).

Q14 · Derive the cliff

At an ML research onsite, the interviewer points at your learning-rate sweep, which shows a sharp cliff. "Take L(w) = \tfrac12(w - w^*)^\top H(w - w^*), with H symmetric positive definite. Prove that gradient descent with a fixed step \eta converges from every start if and only if 0 < \eta < 2/\lambda_{\max}. What happens at exactly 2/\lambda_{\max}?"

• Concept tested: GD on a quadratic in the eigenbasis (Card 5).
• Intuition: rotate to the bowl's own axes and one hard problem becomes several 1-D ones, each shrinking by its own factor per step.
• Answer: write e = w - w^*; since \nabla L = He, one step is a linear map:

\mathbf e

the error: current weights minus the optimum \mathbf w^* (bold = a vector)

k

the step number

\eta

the fixed learning rate (step size)

H

the Hessian: the symmetric positive definite curvature matrix of the quadratic loss

I

the identity matrix

With H = Q\Lambda Q^\top and c_{i} = q_{i}^\top e, each coordinate evolves alone:

c_{i,k}

the error's coordinate along eigenvector i after k steps (c_i = q_i^\top e)

c_{i,0}

that coordinate at the start

\lambda_i

the curvature (eigenvalue) along eigenvector i

All modes must shrink, and the binding one is the largest \lambda, so the condition is 0 < \eta < 2/\lambda_{\max}. At exactly 2/\lambda_{\max} the steep mode's factor is −1: it neither grows nor shrinks, flipping sign forever, so GD fails to converge from any start with a component along that eigenvector.

• Why: the Hessian's eigenvectors are orthogonal, so the modes don't interact; the sign of 1 - \eta\lambda only decides whether a mode zigzags.
• Next they'll ask: "And for a loss that isn't quadratic?" → If \nabla L is L-Lipschitz, the descent lemma guarantees a decrease for any \eta < 2/L (Card 2); locally the Hessian at the current point sets the cliff, which deep nets sit on (edge of stability, Q36).

Q15 · How many steps to 10^{-6}?

A ranking model's loss is close to quadratic near its optimum. A Hessian probe gives eigenvalues 50 and 0.5. "What's the best fixed learning rate, what convergence rate does it give, and how many steps to shrink the distance to the optimum by a factor of 10^{6}?"

• Concept tested: the optimal fixed step, the (\kappa - 1)/(\kappa + 1) rate and the iteration count (Cards 6–7).
• Intuition: the best single step makes the steepest and flattest directions shrink equally fast, one overshooting and one undershooting.
• Answer: \kappa = 100.

\eta^*

the best fixed learning rate (star = the optimum)

\lambda_{\max}

the largest Hessian eigenvalue: the steepest curvature

\lambda_{\min}

the smallest Hessian eigenvalue: the flattest curvature

\rho

the per-step shrink factor of the distance to the optimum

\kappa

the condition number \lambda_{\max}/\lambda_{\min}: how elongated the bowl is

A simulation needs exactly 691 steps. The loss gap shrinks by \rho^{2} per step, so it reaches 10^{-6} in about half as many.

• Why: minimizing \max_{i}\lvert 1 - \eta\lambda_{i}\rvert sets the two extreme factors equal and opposite; \ln(1/\rho) \approx 2/\kappa makes the count \approx (\kappa/2)\cdot \ln(1/\varepsilon), proportional to \kappa.
• Next they'll ask: "What would momentum buy?" → Rate (\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1) = 9/11 \approx 0.818, about 69 steps by the formula and 93 in simulation (Drill 4). "Is that the best any gradient method can do?" → Only on problems with more dimensions than steps. This one is 2-D, and conjugate gradient solves any d-dimensional quadratic in d steps: 2 here (Section 9).

Q16 · Prove the loss is convex

A question type widely reported from ML-engineer and research onsites; reconstructed, wording may differ. "Show that the MSE of a linear model and the logistic loss are both convex in the weights. Then tell me whether squared error on a sigmoid output, (\sigma(w^\top x) - y)^{2}, is convex, and why practitioners care."

• Concept tested: convexity via a PSD Hessian (Card 3); why cross-entropy replaces MSE for classifiers.
• Intuition: a loss is convex if it curves up, or stays flat, in every direction everywhere; a loss that flattens out on both sides can't be a bowl.
• Answer: both Hessians are "X^\top(\text{non-negative diagonal})X", hence PSD:

H_{\text{MSE}}

the Hessian (curvature matrix) of the linear model's MSE

H_{\text{logistic}}

the Hessian of the logistic loss

n

the number of orders

X

the data matrix: one row per order, one column per feature

X^\top

X transposed: rows become columns

S

a diagonal matrix holding each order's weight p_i(1 - p_i)

\operatorname{diag}

a diagonal matrix with these entries, zeros elsewhere

p_i

the model's predicted probability for order i

\mathbf v^\top H\mathbf v

the curvature along direction \mathbf v, for either Hessian

\mathbf v

any direction in weight space

c

2 for MSE, 1 for logistic

\sum_i

add up over every order i

s_i

order i's non-negative weight: 1 for MSE, p_i(1 - p_i) for logistic

\mathbf x_i^\top\mathbf v

how much order i's score changes when the weights move along \mathbf v

MSE on a sigmoid is not convex. Along any line, with one example x = 1 and y = 1, \ell(w) = (\sigma(w) - 1)^{2} is bounded and non-constant, rising toward 1 as w \to -\infty and flattening toward 0 as w \to +\infty; a convex function on the whole real line that is bounded above must be constant. It has flat regions where a confidently wrong prediction gets almost no gradient.

• Why: composition with an affine map preserves convexity (SAM), and the logistic loss's second derivative in the score is p(1 - p) \ge 0. The sigmoid inside a square breaks it.
• Next they'll ask: "Is the logistic minimum unique?" → Not if the data are separable: the loss keeps falling as \lVert w\rVert \to \infty and there's no finite minimizer (Q37, Ch 3).

Q17 · Unbiased but noisy

A teammate says "SGD just uses a worse gradient." The interviewer asks you to make that precise: "Show that a minibatch gradient of B examples drawn uniformly at random is unbiased, derive its variance, and say what changes when batches are drawn without replacement, as in a shuffled epoch."

• Concept tested: the minibatch gradient as an estimator (Card 8); the finite-population correction.
• Intuition: a random focus group is right on average; its wobble shrinks as it grows, and if it's the whole population it doesn't wobble at all.
• Answer: with G = (1/N)\sum\nabla\ell_{i} and \Sigma the covariance of per-example gradients:

\mathbb E

the average over every random draw of the batch

\mathbf g_B

the minibatch gradient: the average over B randomly drawn orders

\mathbf G

the full gradient: the average over all N orders

\operatorname{tr}\Sigma

the total variance of per-order gradients (trace of their covariance \Sigma)

B

the batch size

N

the number of orders in the training set

\frac{N - B}{N - 1}

the finite-population correction for drawing without replacement

Unbiased because each sampled index is uniform; the variance is that of an average of B draws. Without replacement, draws are slightly negatively correlated (each one excludes itself from the rest), giving the factor (N - B)/(N - 1). For B = 1{,}000 of N = 10{,}000 it's 0.900 (simulation: 0.902); at B = N it's 0.

• Why: linearity of expectation for the mean; Var of a mean of B independent draws is \sigma^{2}/B; the covariance between two draws without replacement is -\sigma^{2}/(N - 1). On the 10k orders the measured variance follows \operatorname{tr} \Sigma/B with a log-log slope of −1.02.
• Next they'll ask: "Is uniform sampling the lowest-variance choice?" → No: sampling \propto \lVert \nabla\ell_{i}\rVert and reweighting by 1/(Np_{i}) stays unbiased with lower variance (Q34, Drill 19).

Q18 · The plateau that isn't a plateau

SGD on the 10k ETA orders (standardized features, \eta = 0.1, B = 8) flattens at a training MSE of about 9.41, roughly 4.5% above the full-batch optimum of 9.01. Doubling the number of epochs doesn't move it. "Has it converged? Explain what you're seeing and give two ways to get lower."

• Concept tested: the constant-step noise floor \propto \eta/B (Card 9).
• Intuition: each step pulls the weights toward the bottom by a fraction \eta\lambda and kicks them randomly by \eta\cdot \text{noise}; the floor is where pull and kicks balance.
• Answer: it has reached a stationary distribution around w^*, not w^* itself. For one direction with curvature \lambda and per-example gradient noise variance \sigma^{2}:

e_k

the error along one direction after k steps (weight minus its optimum)

e_{k+1}

the same error one step later

\lambda

the curvature along that direction

\xi_k

the gradient noise at step k: random, mean 0, variance \sigma^2/B

\mathbb E[L - L^*]

the average excess loss once SGD settles: the noise floor

\sigma^2

the variance of one order's gradient along this direction

Summed over directions, \approx (\eta/4B)\cdot \operatorname{tr} \Sigma with \operatorname{tr} \Sigma = 109 at w^*: 0.341 here, 0.383 from the exact per-mode formula, 0.407 simulated. Raise B to 32 and it falls to 0.0994. Ways down: decay \eta (a step schedule ends at 1.00 \times 10^{-4} on this data), average the iterates (Polyak), or grow the batch late in training.

• Why: the floor depends only on \eta/B, so halving \eta or doubling B halves it; only \eta_{t} \to 0 with \sum\eta_{t} = \infty and \sum\eta_{t}^{2} < \infty removes it.
• Next they'll ask: "Does the formula hold at any \eta?" → Only for small \eta. At \eta = 0.1, B = 1 the simulation gives 8.24 against 3.06, because per-example noise grows as w wanders from w^* (multiplicative noise).

Q19 · Code Adam from memory

A question type widely reported from ML-engineer onsites; reconstructed, wording may differ. "No libraries. Write Adam's update for a parameter vector in NumPy, explain every line, and justify the bias correction mathematically."

• Concept tested: the four D's of Adam; why bias correction makes the moment estimates unbiased (Card 12).
• Intuition: keep a running average of the gradient (where to go) and of its square (how big it usually is), fix both for having started at zero, then step by their ratio.
• Answer:

import numpy as np

def adam_step(w, g, m, v, t, lr=1e-3, b1=0.9, b2=0.999, eps=1e-8):
    m = b1 * m + (1 - b1) * g              # Direction: EMA of gradients (momentum)
    v = b2 * v + (1 - b2) * g * g          # Denominator: EMA of squared gradients
    m_hat = m / (1 - b1 ** t)              # Debias: both EMAs started at 0 (t counts from 1)
    v_hat = v / (1 - b2 ** t)
    w = w - lr * m_hat / (np.sqrt(v_hat) + eps)   # per-weight step, about lr in size
    return w, m, v

For a stationary gradient, unrolling the average shows it's shrunk toward its zero start by exactly 1 - \beta_{1}^{t}:

\mathbf m_t

Adam's moving average of gradients after t steps, started at 0

t

the step number, counting from 1

\beta_1

how much of the old average to keep each step (0.9)

\sum_{j=0}^{t-1}

add up over the past t gradients, j steps back

j

how many steps back a gradient is; \beta_1^{\,j} is its weight

\mathbb E[\mathbf g]

the true average gradient, which the moving average should estimate

\frac{\mathbf m_t}{1-\beta_1^t}

the bias-corrected average \hat{\mathbf m}_t

After 10 steps m carries only 1 - 0.9^{10} = 0.651 of the true mean (Monte Carlo: 0.650). Without either correction, the first step is 0.1/\sqrt{0.001} = 3.16 times too big.

• Why: the EMA weights (1 - \beta)\beta^{j} sum to 1 - \beta^{t}, not 1, after t steps. The same argument applies to v with \beta_{2}, where the correction matters more because \beta_{2} is so close to 1.
• Next they'll ask: "Add weight decay." → Apply it outside the adaptive step, w -= \text{lr}\cdot \lambda\cdot w (AdamW, Q20). "What if you correct m but not v?" → Steps inflated by \sqrt{1/(1 - \beta_{2}^{t})}: 10.0× at t = 10, 3.24× at t = 100 (Drill 8).

Q20 · Adam with weight_decay = 0.01

*A colleague trained the ETA network with torch.optim.Adam(params, weight_decay=0.01). Switching to AdamW with the same number changed the results noticeably. They ask: "Isn't weight decay just weight decay? Why would the optimizer class matter?"*

• Concept tested: L2 penalty vs decoupled weight decay (Card 13).
• Intuition: inside Adam everything that enters the gradient gets divided by that weight's typical gradient size, including the penalty, so the "shrink" stops being a shrink.
• Answer: Adam(weight_decay=λ) adds \lambda w to the gradient (L2). Under plain SGD that's identical to shrinking w by (1 - \eta\lambda) each step, but in Adam the \lambda w term passes through m and v and gets divided by \sqrt{\hat v}. AdamW applies (1 - \eta\lambda) outside the adaptive step. They are different models:

\mathbf w

the ETA network's weights (bold = all of them)

\nabla L

the gradient of the data loss: one slope per weight; points uphill

\lambda

the weight-decay strength (0.01 in the question)

(1-\eta\lambda)

the factor every weight shrinks by each step

\hat{\mathbf m}

Adam's bias-corrected average gradient (the direction)

\hat{\mathbf v}

Adam's bias-corrected average squared gradient (the scale)

\epsilon

a tiny constant (10^{-8}) that keeps the division safe

Two facts from the simulations. A weight with no data gradient (w_{0} = 1, \eta = 10^{-3}, \lambda = 0.1): AdamW leaves it at 0.905 after 1,000 steps; Adam + L2 leaves it at 0.258, and the result is the same for \lambda = 10^{-3} or 1, because Adam divides out the penalty's scale. On the raw 10k model with \lambda = 0.1, Adam + L2 lands on the ordinary ridge solution (6.21, 2.97, 1.96), while AdamW behaves like ridge with a per-weight strength \lambda\sqrt{\hat v_{j}} (0.45 for distance, 0.38 for items) and lands on (6.69, 2.89, 1.89).

• Why: a fixed point of Adam + L2 is wherever the penalized gradient is zero, whatever the preconditioner, so it's ridge; AdamW's fixed point is \nabla L + \lambda\sqrt{\hat v_{j}}\cdot w_{j} = 0.
• Next they'll ask: "Which parameters should be decayed?" → Weight matrices, not biases or normalization gains; use parameter groups.

Q21 · One-step Newton

"On the six-order quadratic, with Hessian H = [[3.333, 1.667], [1.667, 3.333]] and gradient (−13.33, −11.67) at w = 0, do one Newton step by hand. Then tell me why nobody trains the 100-million-parameter ranking model this way."

• Concept tested: Newton's step and its cost (Card 14); the three toos.
• Intuition: Newton fits the local bowl exactly and jumps to its bottom; on a true bowl, that's the answer.
• Answer:

H^{-1}

the inverse of the toy Hessian: undoes its curvature

\mathbf w_1

the weights after one Newton step

One step, from any start, gradient exactly zero: for least squares a Newton step is the normal equation. For the big model: too big (even a 1-million-parameter Hessian has 10^{12} entries, 4 TB in float32, and a solve costs on the order of 10^{18} operations), too noisy (minibatch curvature estimates are poor, and inverting them amplifies the noise), too saddle-happy (Newton heads for any stationary point of the local quadratic, saddles included).

• Why: Newton's step minimizes the second-order Taylor model; H^{-1} rescales every eigen-direction by 1/\lambda_{i}, so \kappa becomes 1.
• Next they'll ask: "What do people use instead?" → Diagonal or structured curvature (Adam, K-FAC, Shampoo), L-BFGS for mid-sized full-batch problems, and Hessian-vector products when only \lambda_{\max} is needed (WP1).

Q22 · Ten iterations vs five hundred

For next quarter's P(late) model (logistic, 10,000 orders, standardized distance and items), statsmodels converges in 10 iterations. Your hand-written gradient descent at \eta = 1/L needs 553 iterations, and on the raw, unscaled features about 50,000. A reviewer asks you to explain both gaps.

• Concept tested: IRLS = Newton for logistic regression; quadratic vs linear convergence; affine invariance (Card 14).
• Intuition: Newton measures the bowl's curvature and corrects for it every step; gradient descent uses one step size and pays for every bit of elongation.
• Answer: statsmodels' Logit runs Newton's method (its GLM routine, IRLS, takes 9): each iteration solves a weighted least-squares problem with weights p_{i}(1 - p_{i}). Near the optimum it converges quadratically; our IRLS is below 10^{-6} relative suboptimality by iteration 7 and at \lVert \Delta w\rVert < 10^{-8} by 10. GD converges linearly at a rate set by \kappa: the logistic Hessian at the optimum has \kappa = 27.5 (553 steps at \eta = 1/L, 70 at the best fixed \eta of 14), and on raw km and items \kappa \approx 2{,}581, so 49,989 steps.

(X^\top S_k X)^{-1}

the inverse of the logistic Hessian (up to 1/n) at iteration k

S_k

a diagonal matrix of each order's weight p_{ik}(1 - p_{ik}) at iteration k

\mathbf p_k

every order's predicted P(late) at iteration k

\mathbf y

the 0/1 labels: 1 if the order was late

p_{ik}

order i's predicted P(late) at iteration k

The second gap is the interesting one: Newton took 10 iterations on the raw features too, because a Newton step is unchanged by any linear reparameterization of the features. GD isn't.

• Why: "Sublinear crawls, linear adds digits, quadratic doubles them." All methods reach the same coefficients (−5.05, 4.11, 1.78).
• Next they'll ask: "Then why not Newton for everything?" → p \times p Hessians (Q21); for many features, L-BFGS (Q33).

Q23 · Read this loss curve

The interviewer sketches a training-loss curve for a minibatch job: it falls, then settles into a repeating sawtooth whose period is exactly one epoch, and much later shows two isolated tall spikes that partly recover. "Diagnose each feature, and tell me what you'd check first."

• Concept tested: reading loss curves with the four N's; a debugging order.
• Intuition: the shape of the curve is a fingerprint of what broke: periodic means the data order, isolated means individual batches or steps.
• Answer: both are Notches. A sawtooth locked to the epoch means the data arrive in the same non-random order every epoch: the gradient is biased toward whatever comes next (stored-order SGD on the 10k orders swings between 14.7 and 201; shuffled, it stays within 9.008–9.237 of an optimum of 9.007). Isolated spikes are rare huge gradients: a bad or heavy-tailed batch, a step size near the stability edge, or Adam dividing by a tiny \sqrt{\hat v}. Check the data loader first (is shuffle on?), then log gradient norms around the spikes, then clip.

• Why: SCUBA's U (unbiased gradients) and B (bounded noise) are the assumptions these shapes violate. Debugging order: data → loss → gradient → step size → optimizer.
• Next they'll ask: "How would you fix the spikes in a large run?" → Clip, skip the batch, lower peak \eta or \beta_{2}, rewind to a checkpoint (Q30).

Q24 · The gradient check fails

You wrote the gradient for a custom ETA loss by hand. A finite-difference check reports a relative error of 0.5. A teammate runs the same check in float32 on a correct gradient and gets 3 \times 10^{-3}, and wonders whether that one is buggy too. Diagnose both.

• Concept tested: gradient checking: central differences, step size h, precision, relative error.
• Intuition: a correct gradient should agree with "nudge each weight both ways and measure the change"; a factor that's off shows up as a clean, round disagreement.
• Answer: a relative error of exactly 0.5 is the signature of a factor of 2: if the analytic gradient is half the true one, the error is \lVert g - g/2\rVert /\lVert g\rVert = 0.5. The usual culprit is dropping the 2 from the derivative of a square. The float32 result is a false alarm: rounding error divided by a tiny h swamps the difference. On the toy, a correct gradient scores 9.0 \times 10^{-12} in float64, 3.1 \times 10^{-3} in float32 at h = 10^{-5}, and 7.4 \times 10^{-5} in float32 at h = 10^{-3}.

g_j^{\text{num}}

the numerical estimate of the slope along weight j

L

the custom ETA loss being checked

h

the nudge size (e.g. 10^{-5})

\mathbf e_j

the unit vector for weight j: 1 in slot j, 0 elsewhere

\mathbf g^{\text{ana}}

the hand-derived (analytic) gradient

\mathbf g^{\text{num}}

the vector of numerical slopes

• Why: central differences have truncation error of order h^{2}, forward differences of order h; rounding error grows like (machine precision)/h. Gradient-check in float64, at a random point (not w = 0, where some bugs vanish).
• Next they'll ask: "Do you need this with autodiff?" → For custom backward passes or custom losses, yes; a check is a few lines.

Q25 · Lasso by gradient descent

A teammate fits the lasso version of the ETA model with plain gradient descent, using sign(w) as the gradient of \lvert w\rvert. The coefficients that "should" be zero hover around ±0.001 and never land on zero, so the feature-selection report lists every feature. What's wrong?

• Concept tested: subgradients vs proximal steps; soft-thresholding (Card 16).
• Intuition: subgradient descent steps a fixed amount past zero each time, so it jitters across the kink; a proximal step asks "is the pull of the data stronger than the penalty?" and, if not, sets the weight to exactly zero.
• Answer: \lvert w\rvert has a kink at zero; any subgradient step overshoots it. On the toy at \lambda = 11, where the exact answer has w_{\text{items}} = 0, subgradient descent (\eta = 0.01) keeps w_{\text{items}} jittering between about −0.001 and 0.21 and is never exactly zero in its last 1,000 steps. Use proximal gradient descent (ISTA): a gradient step on the smooth MSE, then soft-threshold with t = \eta\lambda. It lands on (0.7, 0), an exact zero.

\operatorname{prox}_{t|\cdot|}(z)

the proximal operator of t|w|: best trade between staying near z and paying the penalty

z

the weight right after the plain gradient step

\arg\min_w

the w that makes what follows smallest

w

a candidate value for one weight

t

the shrink threshold: \eta\lambda in ISTA

\operatorname{sign}

the sign: +1 for positive, −1 for negative, 0 at 0

• Why: the prox has a flat region: every z with \lvert z\rvert \le t maps to exactly 0. Hook: "Projected: step, then snap. Proximal: step, then shrink."
• Next they'll ask: "What does sklearn's Lasso use?" → Coordinate descent, an exact 1-D soft-threshold per weight; FISTA adds momentum to ISTA for a 1/k^{2} rate.

Q26 · Ops caps the per-item time

Ops runs an SLA model that assumes each extra item adds at most 1.5 minutes, so they require w_{\text{items}} \le 1.5 in the ETA model. On the six-order toy (unconstrained best (3, 2)), "solve the constrained problem by hand, interpret the multiplier for the ops lead, and show how projected gradient descent finds it."

• Concept tested: the Lagrangian, KKT conditions and complementary slackness (Card 15); projected GD.
• Intuition: the cap is a wall; at the answer the downhill pull into the wall is exactly balanced by the wall pushing back, and the push's size is the price of the wall.
• Answer: the cap binds (unconstrained w_{\text{items}} = 2), so set w_{\text{items}} = 1.5 and solve the rest. Stationarity in w_{\text{km}} gives w_{\text{km}} = 3.25; the leftover slope in w_{\text{items}} is the multiplier:

\frac{\partial L}{\partial w_{\text{km}}}

how fast the toy loss changes as you nudge the distance weight, items fixed: a slope, not a fraction to divide

w_{\text{km}}

minutes per km of distance

\mu

the KKT multiplier: the cap's push back, the loss saved per unit of slack

\frac{\partial L}{\partial w_{\text{items}}}

how fast the loss changes as you nudge the items weight, distance fixed

Check all four KKT conditions: stationarity, primal feasibility (1.5 ≤ 1.5), dual feasibility (\mu = 1.25 \ge 0), complementary slackness (the constraint is tight, so \mu may be positive). The distance weight rose to absorb what items can't explain, and the loss rose from 1.667 to 1.979. For ops: \mu is a shadow price, dL^*/d(\text{cap}) = -1.25, so loosening the cap by one minute per item lowers the best loss by about 1.25 per unit. Projected GD (\eta = 0.3): step to (4.0, 3.5), snap to (4.0, 1.5); step and snap again to (3.25, 1.5), done in 2 iterations.

• Why: hook KKT = "Some People Dislike Constraints": Stationarity, Primal, Dual, Complementary slackness.
• Next they'll ask: "A budget w_{\text{km}} + w_{\text{items}} \le 4 instead?" → w = (2.5, 1.5), \mu = 2.5 (Drill 15). In code: scipy's L-BFGS-B with bounds.

Q27 · Choosing \beta

The raw 10k ETA model (intercept, km, items, unscaled) has Hessian eigenvalues 49.9 and 0.348 at the extremes, \kappa \approx 143. Plain GD at its best fixed step needs 991 steps to shrink the distance to the optimum by 10^{6}. "What momentum \beta and step would you pick, what rate does that buy, and what speedup should you promise?"

• Concept tested: heavy-ball momentum on a quadratic: the optimal \beta and the \sqrt{\kappa} rate (Card 11).
• Intuition: the right amount of inertia lets the ball carry speed along the ravine's floor without bouncing off its walls.
• Answer:

\beta^*

the best momentum coefficient (star = the optimum)

\sqrt\kappa

the square root of the condition number \kappa (about 12 here)

Against GD's 0.986, the per-step log-rate improves by a factor of 12.0 = \sqrt{\kappa}. But don't promise 12×: the simulation goes from 991 to 112 steps by distance (8.8×) and from 496 to 71 by loss (7.0×). At the optimal (\eta, \beta) each mode's 2 × 2 update matrix has a repeated eigenvalue, so the error behaves like k\cdot \rho^{k}, and the factor k costs extra steps before the asymptotic rate shows.

• Why: per mode, momentum is a 2 × 2 linear recursion; tuning makes every mode's eigenvalues have modulus \sqrt{\beta}, which equalizes the slowest and fastest modes.
• Next they'll ask: "Nesterov instead?" → With standard settings it needs 76 by loss and 188 by distance here; its advantage is a guarantee on every smooth convex function, not speed on a tuned quadratic. "And if you standardize first?" → \kappa = 2.15 and plain GD needs 13 steps; fix conditioning before reaching for momentum (WP1).

Level 3 — Senior

Q28 · From 1 GPU to 8

ETA training moved from one GPU (batch 256) to eight with data parallelism (effective batch 2,048), keeping the learning rate and epoch count. Epochs are 7× faster, but final error is clearly worse. A second attempt with the learning rate multiplied by 8 diverges in the first few hundred steps. What's going on, and what would you do?

• Concept tested: the linear scaling rule, warmup, the stability cap and the critical batch size (Card 19).
• Intuition: a bigger batch gives a cleaner direction but 8× fewer steps per epoch; you must take bigger steps to cover the same ground, but there's a cliff that no batch size moves.
• Answer: with the same \eta and epochs, the run takes 8× fewer updates with the same step size, so it simply doesn't get as far. The noise floor depends on \eta/B, so the linear scaling rule says multiply \eta by 8 to keep the dynamics; but 8\eta may cross 2/\lambda_{\max} early in training, when curvature is highest, hence the divergence. The 10k simulation (2 epochs) shows all three effects. Starting from B = 32, \eta = 0.02 (excess 0.0087): B = 256 at 8\eta reaches 0.0207, while B = 256 at the old \eta stalls at 0.899. B = 2{,}048 at 64\eta = 1.28 is above the full-batch cliff of 0.733 and diverges; at 32\eta = 0.64 it survives but, with only 9 steps, ends at 0.332. Fix: scale \eta linearly with a warmup, cap it below the cliff, and expect diminishing returns once B passes the gradient noise scale B_{\text{noise}} = \operatorname{tr} \Sigma/\lVert G\rVert ^{2}, where more epochs are needed instead.
• Why: the floor \propto \eta/B (Card 9) gives the rule; the cliff (Card 5) and the critical batch (Card 19) bound it (Goyal et al., 2017, made it work on ImageNet with warmup).
• Next they'll ask: "Why does B_{\text{noise}} grow during training?" → \lVert G\rVert \to 0 near the optimum while the noise doesn't, so large batches pay off more later (3.75 at w = 0 on the 10k orders). "LARS/LAMB?" → Per-layer step scaling for very large batches.

Q29 · Adam trains faster, SGD tests better

The vision team reports that Adam reaches a lower training loss than SGD + momentum on their image model, but SGD + momentum gets lower test error. A director asks whether the team should drop Adam everywhere.

• Concept tested: generalization of adaptive methods; tuning parity; implicit bias.
• Intuition: different optimizers don't just reach the bottom at different speeds; they reach different bottoms, and the training loss can't tell you which generalizes.
• Answer: don't generalize from one benchmark. Well-tuned SGD + momentum has generalized better than Adam on some vision benchmarks (Wilson et al., 2017), but much of the gap closes with decoupled weight decay (AdamW) and equal tuning budgets, and Adam variants dominate in transformers and LLMs. Check, in order: was weight decay coupled (Adam(weight_decay=…), Q20)? Were both tuned with the same budget and schedule? Is the gap larger than seed-to-seed spread? Then decide per domain.
• Why: with non-convex losses and more parameters than data, the optimizer picks among many zero-training-loss solutions (implicit regularization, Card 18), and its noise and step geometry affect how sharp they are (Card 20). The sharpness story is a heuristic, not a law (Q36).
• Next they'll ask: "Can you get both?" → Common practice: AdamW with a tuned decay and a cosine schedule; or switch to SGD late in training (SWATS-style), which is rarely worth the complexity.

Q30 · The spike at step 40,000

A 1-billion-parameter pretraining run's loss has been falling smoothly to 2.1 when, at step 40,000, it jumps to 7 and only partly recovers over the next few thousand steps. The run uses Adam with \beta_{2} = 0.999, peak learning rate held for a long time, and fp16. You're on call. What are the likely causes, and what do you do now and next time?

• Concept tested: loss spikes: causes and fixes.
• Intuition: a spike is one step that was far too big for where the model stood: either the step size, a huge gradient, or a tiny denominator.
• Answer: suspects, all from this chapter: (1) a peak \eta at the edge of stability (sharpness has risen to 2/\eta); (2) Adam's \hat v became tiny for some weights after a long quiet stretch, with a 1,000-step memory (\beta_{2} = 0.999), so a sudden large gradient produced a huge step; (3) a bad or unusual batch; (4) fp16 overflow. Now: rewind to a checkpoint before the spike and skip the batches around it (PaLM did exactly this, Chowdhery et al., 2022), possibly with a lower \eta. Next time: the LLM recipe, "Always Warm up, Cool down, Clip, in bf16, with AdamW": \beta_{2} = 0.95, clipping at global norm 1.0, warmup, a decaying schedule, bf16, and logged gradient norms per layer.
• Why: with Adam each step is \approx \eta\cdot \hat m/\sqrt{\hat v}, so it's large when \hat v is stale and small relative to a new gradient; \beta_{2} = 0.95 (memory ≈ 20 steps) lets \hat v catch up quickly (Card 12). Clipping bounds the step (Section 10).
• Next they'll ask: "Does clipping fix accuracy?" → No; it's insurance. On the storm orders, clipping at the 95th percentile halves the largest step (0.633 → 0.292) but barely moves the average weight error (0.311 → 0.294).

Q31 · Fine-tuning diverges in the first 100 steps

Fine-tuning a pretrained text model on delivery-review data with Adam at \eta = 10^{-4} and no warmup blows up within the first 100 steps. The same run with 500 linear warmup steps is fine. The new hire asks: "The model is already trained — why would it need warming up?"

• Concept tested: why warmup matters for Adam; early moment estimates (Card 12).
• Intuition: in its first steps Adam has seen too few gradients to know their size, so it moves every weight by about the full learning rate at once, whether or not that weight should move.
• Answer: on step 1, Adam's bias-corrected step is \eta\cdot \operatorname{sign}(g) for every weight: \hat m_{1}/\sqrt{\hat v_{1}} = g/\lvert g\rvert. A pretrained model has many weights with tiny but nonzero gradients, and all of them move by the full \eta simultaneously, a large coordinated jolt to a model sitting in a good minimum. Over the next steps \hat v is an average of very few squared gradients, so its noise makes some steps far too large. Warmup keeps \eta small until \hat v is reliable. Two related bugs make it worse: skipping v's bias correction inflates early steps by 10.0× at t = 10, and forgetting all correction gives a first step 3.16× too big.
• Why: the estimator \hat v is unbiased but high-variance for small t; RAdam (2020) rectifies that variance explicitly, which works like an automatic warmup.
• Next they'll ask: "Other fixes?" → A lower peak \eta for fine-tuning, freezing early layers at first, and decay excluded from biases and norm weights.

Q32 · NaNs under mixed precision

To speed up training, a teammate switched the ETA network to fp16 automatic mixed precision. After a few hundred steps the loss becomes NaN. With bf16 on the same hardware it trains fine. Explain, and say how you'd make fp16 work.

• Concept tested: floating-point range; loss scaling; the order of operations with clipping.
• Intuition: fp16 is a short ruler: big numbers fall off one end (overflow → inf → NaN) and tiny gradients fall off the other (underflow → 0). bf16 has fewer digits but fp32's full length.
• Answer: fp16 has a narrow exponent range, so large activations or gradients overflow and small gradients underflow to zero. bf16 keeps fp32's exponent range with less precision, which is why it needs no extra machinery. To use fp16: keep fp32 master weights; use dynamic loss scaling (GradScaler), which multiplies the loss so small gradients survive, and skips the step and lowers the scale whenever it sees inf or NaN; compute softmax, log and reductions in fp32. The order matters: scaler.scale(loss).backward() → scaler.unscale_(opt) → clip → scaler.step(opt) → scaler.update(). Clipping before unscaling compares scaled gradients against the threshold, which is meaningless.
• Why: NaN after many steps (rather than at once) points to an overflow or a bad batch, not a learning rate above the cliff (Q23); in the NaN run on raw km, float32 hit a non-finite loss at step 10 against step 90 in float64.
• Next they'll ask: "Does Adam's \varepsilon interact with precision?" → Yes: in low precision raise \varepsilon (e.g. 10^{-6}) so weights with tiny \hat v don't take huge steps.

Q33 · L-BFGS or SGD?

You own two models. One is a 300-feature logistic credit model refit nightly on 5 million rows, which regulators want reproducible. The other is a 100-million-parameter ranking network trained continuously on streaming data. Which optimizer for each, and why?

• Concept tested: second-order vs first-order trade-offs; full-batch smooth convex vs stochastic non-convex.
• Intuition: for a smooth bowl you can afford to measure, use its curvature; for a huge, noisy, bumpy landscape, take cheap steps and lots of them.
• Answer: credit model: deterministic full-batch L-BFGS or Newton/IRLS. The problem is convex and smooth, p = 300 makes a 300 × 300 Hessian trivial, convergence takes tens of iterations, and the answer is exact and reproducible to the tolerance (our logistic preview: IRLS in 10, against hundreds of GD steps). Ranking net: minibatch SGD + momentum or AdamW with a schedule: the Hessian is impossibly large (a 1-million-parameter one is already 4 TB in float32), streaming data make full-batch passes impossible, minibatch curvature is too noisy for quasi-Newton, and the loss is non-convex.
• Why: the three toos (Card 14) apply to the ranking model, not to the credit model. L-BFGS stores only m \approx 5–20 pairs of gradient differences, O(mp) memory.
• Next they'll ask: "What would break L-BFGS on the credit data?" → Perfect separation (no finite optimum, Q37), unscaled features (more iterations, not failure), and too loose a tolerance; also sklearn's default max_iter = 100 can stop it early with only a warning.

Q34 · 1% late in a batch of 32

For a rare "very late" class (about 1% of orders), the classifier's predicted probability stays near zero for many epochs. Most minibatches of 32 contain no very-late orders at all, and the pipeline happens to write those orders in one block at the end of each daily file. What's going wrong, and how do you fix it without biasing the model?

• Concept tested: imbalanced and class-sorted batches; stratification; importance sampling with reweighting.
• Intuition: the model only learns about the rare class when it shows up, and if it shows up all at once the model swings to it and back.
• Answer: two problems. The block at the end makes batches class-sorted, which biases the gradient: in the 10k preview, feeding all late orders first and then all on-time ones leaves the intercept 1.08 too low and the average predicted probability at 0.057 against a true rate of 0.159, while stratified batches leave it off by only 0.105 with average prediction 0.156. And with 1% positives, a batch of B contains none with probability (1 - 0.01)^{B}, so the rare-class gradient arrives in rare, noisy bursts. Fixes: shuffle; stratify batches so each carries the class mix; or oversample the rare class and reweight each example by 1/(Np_{i}) so the gradient stays unbiased (or correct the intercept afterward, Ch 3).

\mathbf g

the reweighted gradient from one sampled order i

N

the number of training orders

p_i

the probability of drawing order i (higher for the rare very-late orders)

\nabla\ell_i

order i's own gradient: the slopes of its loss, one per weight

\mathbb E

the average over random draws

\sum_i

add up over all N orders

\nabla L

the full-data gradient (average over all orders); points uphill

• Why: reweighting keeps E[g] = \nabla L for any sampling distribution p_{i} (Card 8); sampling ∝ gradient norm minimizes variance (on the 10k orders, 8,330 → 3,558, 2.34× lower).
• Next they'll ask: "Oversample without reweighting?" → Then you've changed the loss: probabilities come out too high, a known intercept shift for logistic models (Ch 3).

Q35 · "We're stuck in local minima"

A research lead blames slow training of a deep model on "bad local minima". You compute the Hessian's spectrum at the current weights with Lanczos and find several clearly negative eigenvalues alongside many positive ones. What does that tell you, and what would you change?

• Concept tested: classifying stationary points by Hessian signs; saddles vs minima; escape (Card 17).
• Intuition: a mountain pass, not a valley floor: downhill exists, but in a direction the gradient barely points along.
• Answer: negative eigenvalues mean the current point is not a local minimum. If the gradient is near zero it's a saddle region: downhill exists along those eigenvectors. GD escapes a saddle only as fast as the tiny component along the negative direction grows, by (1 + \eta\lvert \lambda\rvert ) per step; noise kicks that component up and escapes much faster. On the saddle toy from b_{0} = 10^{-6} with \eta = 0.1, GD needs 139 steps to reach \lvert b\rvert = 0.5, while adding noise of 0.01 per step escapes the pure quadratic saddle in 47 steps on average instead of 145. Change: keep SGD noise (don't push to huge batches), use momentum, check initialization and normalization for plateaus; don't switch to Newton, which is attracted to saddles.

b_k

the offset from the saddle along the downhill direction after k steps

b_0

the starting offset (10^{-6} on the saddle toy)

b_{\text{target}}

the offset that counts as escaped (0.5)

k

the number of steps

\eta

the learning rate (0.1)

\lambda

the negative eigenvalue (curvature) along that direction; |\lambda| is its size

• Why: hook "Signs of the Hessian: all up = minimum, all down = maximum, mixed = saddle." In high dimensions high-loss stationary points almost always have mixed signs (Dauphin et al., 2014, an empirical and random-matrix argument).
• Next they'll ask: "Hessian of a 100M-parameter model?" → Never formed: Lanczos or power iteration on Hessian-vector products gives the extreme eigenvalues. "What does GD actually guarantee here?" → Without convexity, only a small gradient: \min_{j}\lVert \nabla L(w_{j})\rVert ^{2} \le 2L(L(w_{0}) - L^*)/k, so about 1/\varepsilon^{2} steps to \lVert \nabla L\rVert \le \varepsilon (Card 7). From a random start it almost surely avoids strict saddles (Lee et al., 2016), and adding small random kicks (perturbed GD, Jin et al., 2017) reaches an approximate local minimum efficiently.

Q36 · Big batch, worse test error

Training with batch 8,192 matches batch 256 on training loss but is about 1 point worse on test accuracy. A colleague says "large batches find sharp minima, which generalize worse" and proposes SAM. How much of that do you accept?

• Concept tested: stability selection of flat minima; sharpness and its critique; SAM (Card 20).
• Intuition: a step size too big for a narrow hole can't come to rest in it, and noise shakes it out; large batches remove the noise, so narrow holes become habitable.
• Answer: the mechanism is real: GD with step \eta can only settle in a minimum with \lambda_{\max} < 2/\eta, and SGD noise (\propto \eta/B) acts the same way. In the flat-vs-sharp toy (curvatures 44.4 and 0.9, cliff at \eta = 0.045), \eta = 0.01 settles in the sharp hole from 19% of starts; \eta = 0.1 settles there from 0%, but those same 19% stay trapped bouncing inside the sharp well: can't settle, not "always leaves". The generalization link is weaker: Keskar et al. (2017) found large batches reach sharper minima, but sharpness isn't invariant to reparameterization (Dinh et al., 2017), so "flat generalizes" is a heuristic. First fix the confounds: scale \eta with B, add warmup, compare at equal tuning. SAM (Foret et al., 2021) is a reasonable experiment.
• Why: Card 5 applied locally around each minimum; hook "Big steps can't sit in sharp holes." In real nets sharpness rises until it hovers near 2/\eta (edge of stability, Cohen et al., 2021).
• Next they'll ask: "What does SAM do?" → Takes the gradient at the worst point within a small radius \rho of w, then steps: it minimizes the neighborhood's maximum loss, at about twice the cost per step.

Q37 · The weights keep growing

Two odd behaviors on your desk. (1) A logistic model on data that turn out to be perfectly separable: training loss heads to zero and \lVert w\rVert grows without bound. (2) An unregularized least-squares model with more features than rows: GD from zero converges to a perfect fit with a particular, stable set of weights. A teammate asks which weights you'd get in each case and why the optimizer, not the loss, decides.

• Concept tested: implicit bias of gradient descent: minimum norm for least squares (Card 18), max-margin direction for separable logistic.
• Intuition: when infinitely many answers fit perfectly, the path decides: GD from zero only ever moves in directions the data can see, and on separable data it keeps pushing in the direction that separates the classes most comfortably.
• Answer: (2) GD from w = 0 converges to the minimum-norm interpolating solution X^{+}y: every gradient -(2/n)X^\top r lies in the row space of X, iterates never leave it, and the only exact fit there is X^{+}y. On the toy with 8 extra binary flags (10 weights, 6 rows), GD matches X^{+}y to 1.2 \times 10^{-14} (norm 5.44); from a random start it lands on a different perfect fit 2.06 away, X^{+}y plus the start's null-space part. (1) There's no finite minimizer; \lVert w\rVert grows like \log t, and the direction w/\lVert w\rVert converges to the hard-margin SVM direction (Soudry et al., 2018).

\mathbf w

the least-squares weights (more weights than rows)

\mathbf 0

the all-zero start

k

the step number

n

the number of rows (orders)

X

the data matrix: rows = orders, columns = features (wider than tall)

X^\top

X transposed: rows become columns

\mathbf r_k

the residuals at step k: actual ETAs minus predictions

\operatorname{row}(X)

the row space of X: all combinations of the orders' feature rows

\mathbf w_\infty

where GD ends after infinitely many steps

X^+

the pseudo-inverse of X: gives the minimum-norm exact fit

\mathbf y

the ETAs, one per order

\arg\min

the weights that make what follows smallest

\lVert\mathbf w\rVert

the length of the weight vector

• Why: implicit regularization: the optimizer picks among the loss's ties. It's one leading explanation of why overparameterized networks generalize (Ch 4).
• Next they'll ask: "What do you do about (1) in production?" → Add L2 (finite, unique optimum), or early-stop; check for a leaking feature that separates the classes perfectly (Ch 3).

Q38 · Online learning with drift

The ETA model is updated every minute by SGD on the latest orders. To make it "converge", someone added a 1/t learning-rate decay. Within a week it no longer adapts when rush hour starts and travel times jump. Explain, and design a better update.

• Concept tested: tracking vs convergence; constant step as exponential forgetting; when Robbins–Monro's assumptions fail.
• Intuition: a decaying step is a voter who trusts the past more every day; if the world changes, they never notice. A constant step forgets the past at a fixed rate.
• Answer: Robbins–Monro conditions guarantee convergence to a fixed optimum. Under drift the optimum moves, and with \eta_{t} = c/t the step shrinks until new data barely move the weights. A constant \eta makes the weights an exponentially weighted average of recent information, with memory of roughly 1/(\eta\lambda) steps along a direction of curvature \lambda. That memory has a price: the noise floor \approx \eta\sigma^{2}/(4B). So choose \eta to trade tracking error (too slow when \eta is small) against noise (too jumpy when \eta is large), validated on a rolling, time-ordered backtest. Alternatives: a decay with a floor, periodic restarts, sliding-window refits, or time-of-day features so the shift isn't drift at all.
• Why: per mode, e_{k+1} = (1 - \eta\lambda)e_{k} - \eta\xi_{k}: the factor (1 - \eta\lambda) is exactly an exponential forgetting factor (Card 9, WP2).
• Next they'll ask: "How would you detect when to adapt faster?" → Monitor residuals over time and feature drift (Ch 5, Ch 28); a rising residual mean is the signal.

Q39 · Asynchronous workers

An older parameter-server setup lets 64 workers each compute gradients on slightly stale weights and push them without waiting. With the learning rate tuned for one worker, training oscillates and occasionally diverges; it's stable only when \eta is cut sharply. Explain why, and what you'd change.

• Concept tested: gradient staleness as implicit momentum; synchronous vs asynchronous data parallelism.
• Intuition: each update is based on where the model was a few updates ago; acting on old information is like driving with a delayed steering wheel, which overshoots the same way too much momentum does.
• Answer: with M workers, a typical gradient is computed on weights about M updates old. Applying stale gradients behaves like adding momentum (Mitliagkas et al., 2016, "Asynchrony begets momentum", show an implicit momentum of about 1 - 1/M), so the effective step grows toward \eta/(1 - \beta) and crosses the stability cliff unless \eta falls, exactly like Q9's \beta = 0.99. Fixes: synchronous all-reduce (the standard for modern GPU training), which turns workers into a bigger batch (use the linear scaling rule, Q28); gradient accumulation; if async must stay, reduce explicit momentum to compensate, bound staleness, or scale \eta down with the delay.
• Why: momentum's effective step is \eta/(1 - \beta) (Card 10); staleness supplies \beta you didn't ask for.
• Next they'll ask: "Why did async exist at all?" → Slow or failing workers (stragglers) stall synchronous steps; async kept CPUs busy in early large-scale systems.

Level 4 — Research and quant

These questions give you an update rule and a curvature (a Hessian's eigenvalues, a 1-D quadratic, a noise variance) and ask for the exact step size, rate, iteration count or noise floor. There's one method, and every problem below uses it.

The recipe: Rotate, Recurse, Read off.

1. Reduce to a quadratic. Near a minimum, L(w) \approx L^* + \tfrac12(w - w^*)^\top H(w - w^*). Write the update as a recursion in the error e = w - w^* (plus a noise term for SGD).
2. Rotate to H's eigenbasis. The recursion splits into independent 1-D problems, one per eigenvalue \lambda_{i}.
3. Recurse each mode. The deterministic factor is (1 - \eta\lambda_{i}), or a 2 × 2 matrix with momentum. With noise, take expectations and solve for the stationary variance with a geometric series.
4. Read off the worst mode. Stability means every |factor| < 1; the rate is the largest |factor|; the noise floor is the sum over modes.
5. Sanity-check on the toy (\lambda = 5 and 5/3), then say what changes off the quadratic: the Hessian varies along the path, and real gradient noise depends on w.

\mathbf e

the error: weights minus the optimum \mathbf w^* (bold = a vector)

k

the step number

I

the identity matrix

\eta

the learning rate

H

the Hessian: the curvature matrix of the (near-)quadratic loss

\xrightarrow{\;H = Q\Lambda Q^\top\;}

rotate to H's eigenbasis: Q holds its eigenvectors, \Lambda its eigenvalues

\tilde e_{k,i}

the error's coordinate along eigenvector i after k steps (tilde = rotated)

\tilde e_{0,i}

that coordinate at the start

\lambda_i

the curvature (eigenvalue) along eigenvector i

\tilde{\mathbf e}

the whole error in eigen-coordinates

Q^\top

Q transposed: rotates a vector onto the bowl's own axes

Worked problem 1 — The run that diverged at η = 0.05

A question type widely reported from quant-research and ML-research interviews ("here are the Hessian's eigenvalues: what step size, and how many iterations?"), reconstructed around this chapter's data; the real wording varies.

Setup: the nightly ETA model is fit on 10,000 orders with raw features: an intercept column, distance in km and item count, uncentered and unscaled. Full-batch GD with \eta = 0.05 diverges; \eta = 0.01 is still visibly off the OLS answer after 500 steps. The Hessian H = (2/n)X^\top X has eigenvalues \lambda_{\max} \approx 49.9, 4.58 and \lambda_{\min} \approx 0.348. (1) Why did 0.05 diverge? (2) What is the best fixed \eta, and what rate does it give? (3) How many steps to shrink the error by 10^{6}? (4) What does momentum buy? (5) What does standardizing do to each answer? (6) In a model where you can't form H, how would you find \lambda_{\max}?

Intuition first: the bowl is 143 times steeper across than along. The step that is safe across the bowl is tiny along it, so one step size can't be both safe and fast.

Solution.

(1) The cliff. Each eigen-direction multiplies its error by (1 - \eta\lambda_{i}) per step (Card 5). The steep one at \eta = 0.05:

\eta_{\max}

the cliff: the largest fixed step that still converges

\lambda_{\max}

the steepest curvature (largest Hessian eigenvalue): 49.93 on the raw 10k model

The steep mode's error grows 1.5× per step, so the loss (which is quadratic in the error) grows about 2.2× per step. After 20 steps it is 5.3 \times 10^{9}.

(2) The best fixed step balances the steepest and the flattest modes so that both contract equally (Card 6):

\eta^\star

the best fixed learning rate (star = the optimum)

\lambda_{\min}

the flattest curvature (smallest eigenvalue): 0.348

\rho

the per-step shrink factor of the distance to the optimum

\kappa

the condition number \lambda_{\max}/\lambda_{\min}: how elongated the bowl is (143)

(3) The step count. \rho^{k} = 10^{-6} in distance; the loss falls by \rho^{2} per step, so the loss criterion needs half as many steps (Card 7):

k_{\text{dist}}

steps to shrink the distance to the optimum by 10^6

k_{\text{loss}}

steps to shrink the loss gap by 10^6

Simulation from w = 0 confirms both: 991 steps to shrink \lVert w - w^*\rVert by 10^{6}, and 496 to reach relative loss suboptimality 10^{-6}. The \eta = 0.01 run is slow for the mirror-image reason. Its flat-mode factor is 1 - 0.01 \times 0.348 = 0.9965, so after 500 steps 17.5% of the flat-mode error is still there. The weights sit at (5.14, 3.05, 2.19) against the OLS answer (6.05, 2.99, 1.99): the intercept lags, because with uncentered features "raise the intercept, lower the slopes" is nearly a free trade.

(4) Momentum. Heavy ball turns each mode into a 2 × 2 recursion; tuned optimally, every mode contracts at \sqrt{\beta} (Card 11):

\beta^\star

the best momentum coefficient

\sqrt\kappa

the square root of the condition number (about 12 here)

\eta_{\text{HB}}

the best learning rate for heavy-ball momentum

\rho_{\text{HB}}

heavy ball's per-step shrink factor

The rate formula predicts 82.5 steps by distance, \sqrt{\kappa} \approx 12 times fewer than GD's 991. The simulation needs 112 by distance and 71 by loss: speedups of 8.8× and 7.0×, not 12×. The reason is that at the optimal (\eta, \beta) each mode's 2 × 2 matrix has a repeated eigenvalue, so the error behaves like k\cdot \rho^{k}, not \rho^{k}. The extra factor k costs steps before the asymptotic rate takes over.

(5) Standardize. Centering alone takes \kappa from 143 to 3.02; full standardization gives \kappa = 2.15, with \eta^* = 0.5 and \rho = 0.364:

The simulation needs 13 steps by distance and 6 by loss, and the cliff moves out to 2/\lambda_{\max} = 0.733. Every answer gets better at once: a safe \eta 18 times larger, a rate of 0.364 instead of 0.986, and 6 steps instead of 496.

(6) \lambda_{\max} without H. Power iteration needs only Hessian-vector products. Hv is the directional derivative of the gradient, so autodiff computes it for about the cost of two gradients (Pearlmutter's trick), and H is never formed:

\mathbf v

the current guess of the steepest direction, a unit vector

t

the power-iteration count

H\mathbf v

a Hessian-vector product: how the gradient changes along \mathbf v, without forming H

\frac{d}{dr}

how fast what follows changes as you nudge r: a slope, not a fraction to divide

\nabla L(\mathbf w + r\mathbf v)

the gradient at a point moved a distance r along \mathbf v; points uphill

\mathbf w

the current weights

r

a small distance along \mathbf v, sent to 0

\hat\lambda_{\max}

the estimate of the largest eigenvalue (hat = estimated)

\mathbf v_t^\top H\,\mathbf v_t

the curvature along \mathbf v_t (^\top = transpose)

On this model, 30 iterations give 49.93, matching the exact eigenvalue. The direction converges geometrically at \lambda_{2}/\lambda_{1} = 0.092 per iteration, so it converges fast here; it would be slow if the top two eigenvalues were close.

What to say out loud: "The cliff is 2 over \lambda_{\max}, which is 0.040, so 0.05 diverges in the steep direction. The best fixed step is 2 over (\lambda_{\max} + \lambda_{\min}), and the rate is (\kappa - 1)/(\kappa + 1) = 0.986, about a thousand steps by distance or 500 by loss. Optimally tuned momentum gives a \sqrt{\kappa} rate, about 12× on paper and 7–9× in practice. But the real fix is to standardize, which takes \kappa to 2 and the count to single digits."

Follow-ups that separate senior from research-level answers:

• "Is \eta^* the fastest step for this run?" Not necessarily. \eta^* minimizes the worst-case contraction over all starting points. On the figure's grid, \eta = 0.034 reaches the loss tolerance in 382 steps, fewer than 496 at \eta^*. From w = 0 most of the initial loss sits in the steep mode, and a smaller \eta kills that mode quickly, so the flat mode's slightly slower factor matters less. A hair above \eta^* the steep mode becomes the bottleneck: the grid point \eta = 0.0398 needs 555. Name the criterion and the start before quoting a count.
• "The loss isn't quadratic." Use smoothness instead: if \nabla L is L-Lipschitz, any \eta < 2/L decreases the loss (descent lemma, Card 2). The local Hessian sets the local cliff, and it changes along the path; for logistic loss H \preceq (1/4n)X^\top X gives a global bound.
• "Would Adam fix this without standardizing?" It fixes axis-aligned scale, not correlation. Adam is a diagonal preconditioner: in meters the step disparity GD needs falls from c^{2} = 10^{6} to c = 10^{3}, not to 1 (Section 8). The leftover \kappa from correlation, (1 + r)/(1 - r), needs a full preconditioner such as whitening or Newton.
• "What about Nesterov?" With the textbook strongly convex setting (\eta = 1/L = 0.0200, \beta = 0.846), it contracts at about 1 - 1/\sqrt{\kappa} = 0.916 per step and needs 76 steps by loss and 188 by distance. On a quadratic its advantage is robustness to mis-tuning, not a better constant.
• "In a deep net, does the loss just blow up past 2/\lambda_{\max}?" Not always. In full-batch training the sharpness \lambda_{\max} rises until it hovers near 2/\eta, and the loss keeps falling on average while it oscillates: the edge of stability (Cohen et al., 2021). The quadratic analysis explains the threshold but not that self-stabilization.
• "How would you choose \eta automatically?" Backtracking (Armijo) line search for full-batch problems; an LR range test, or the power-iteration estimate of \lambda_{\max} with a margin, for stochastic training.

How to identify it in real data: the loss explodes within the first few steps, geometrically (a straight line on a log scale, slope \ln 1.5^{2} per step). An LR range test shows a sharp cliff. Per-feature gradient magnitudes differ by orders of magnitude, and feature means are far from zero. A power-iteration estimate of \lambda_{\max} puts 2/\lambda_{\max} below the \eta you used.

How to mitigate it:

1. Center, then scale (\kappa 143 → 3.02 → 2.15). "Center, then scale, then worry about correlation."
2. Normalization layers in deep nets (BatchNorm, LayerNorm) do the same job inside the model.
3. Warmup, so \eta grows only after the early high-curvature phase has passed.
4. Precondition: diagonally (Adam, AdaGrad) for axis-aligned scale, fully (Newton, L-BFGS) for correlation.
5. Momentum for the \sqrt{\kappa} rate once the scale is fixed.
6. Line search, or an \eta set from \lambda_{\max} with a margin, such as \eta = 1/\lambda_{\max}.

Worked problem 2 — The SGD noise floor and the linear scaling rule

A type reported in research-scientist and quant interviews: "SGD with a constant step size: where does it end up, and how does that depend on the batch size?" Reconstructed; the wording varies.

Setup: the streaming ETA retrain runs SGD with a constant \eta and batch size B. Its training loss stops improving at a level above the full-batch optimum and stays there. Model the slowest direction as L(w) = (\lambda/2)(w - w^*)^{2}, with per-example gradient noise variance \sigma^{2}, so a batch gradient is \lambda(w - w^*) + \xi with \operatorname{Var}(\xi) = \sigma^{2}/B. Take \lambda = 1, \sigma^{2} = 4. (1) What is the stationary E[L - L^*]? (2) How does it depend on \eta and B, and what does that say about scaling them together? (3) When does that rule break? (4) How do you get below the floor? (5) Does it hold on the 10,000 orders, in three dimensions?

Intuition first: each step pulls the weight a fraction \eta\lambda of the way toward the bottom and kicks it randomly by \eta\xi. The floor is where the average pull balances the average kick.

Solution.

(1) The recursion. Write the error e = w - w^*:

e_k

the error along the slowest direction after k steps: w - w^*

e_{k+1}

the same error one step later

\lambda

the curvature of that direction (\lambda = 1 here)

\xi_k

the batch gradient's noise at step k

\mathbb E

the average over the random noise

\sigma^2

the per-example gradient-noise variance (4 here)

B

the batch size

\xi_{k} is independent of e_{k}, so variances add. At stationarity V = \operatorname{Var}(e_{k+1}) = \operatorname{Var}(e_{k}):

V

the stationary variance of the error: how widely the weight rattles around w^*

\mathbb E[L - L^\star]

the average excess loss at the floor (star = the optimum)

With \lambda = 1, \sigma^{2} = 4: \eta = 0.1, B = 1 gives 0.105; \eta = 0.1, B = 4 gives 0.0263; \eta = 0.01, B = 16 gives 0.000628. A simulation over the grid \eta \in \{0.01, 0.03, 0.1, 0.3\} \times B \in \{1, 4, 16\} (4,000 chains each) matches the exact formula within 1.2% in all 12 cells (verified by simulation).

(2) It depends on \eta/B to first order. Doubling the batch halves the floor, and so does halving \eta. So multiplying B by k and \eta by k leaves the floor unchanged: the linear scaling rule (Card 19). Notice that \lambda dropped out of the approximation. Each direction contributes \eta\sigma_{i}^{2}/(4B) whatever its curvature, so the multi-dimensional floor is a sum over noise, not over curvature:

\sum_i

add up over the eigen-directions i

\sigma_i^2

the gradient-noise variance along direction i

\Sigma

the covariance of per-example gradients; its trace (tr) is the total noise

(3) Where the rule breaks. First, through the (2 - \eta\lambda) term. Holding \eta/B = 0.03 fixed, the exact floor is 0.0305 at (\eta, B) = (0.03, 1), 0.0319 at (0.12, 4) and 0.0395 at (0.48, 16). It is not constant, and at \eta\lambda \ge 2 the run diverges: the cliff from WP1 doesn't move with B. On the 10k orders, B = 2{,}048 with 64\eta = 1.28 is above the full-batch cliff 0.733 and diverges (Q28). Second, once B passes the gradient noise scale B_{\text{noise}} = \operatorname{tr} \Sigma/\lVert G\rVert ^{2}, noise is no longer what limits progress, and a bigger batch stops cutting the number of steps (Drill 18).

(4) Getting below the floor. The floor is proportional to \eta, so \eta must go to zero, but slowly enough to keep moving: the Robbins–Monro conditions.

\sum_t

add up over every step t

\eta_t

the learning rate at step t

\eta_{t} = 1/t satisfies both. With \lambda = 1 it makes the iterate a running mean of the noise, so the excess falls as \sigma^{2}/(2t):

t

the SGD step number

e_{t+1}

the error after step t

\sum_{s=1}^{t}

add up over steps s = 1 to t

\xi_s

the gradient noise at step s

At t = 10^{5} that's 2.0 \times 10^{-5} (simulation: 1.98 \times 10^{-5}), straight through every constant-\eta floor in the figure. The other way out is Polyak averaging: keep \eta constant and average the iterates. On the 10k orders, the last iterate's excess is 0.0373 and the average over the second half is 5.8 \times 10^{-6}.

(5) The 10k check. At \eta = 0.03, B = 8 on standardized features, starting at w^*, the simulated floor is 0.106 against (\eta/4B)\cdot \operatorname{tr} \Sigma = 0.102 with \operatorname{tr} \Sigma = 109 at w^* (verified by simulation). The formula is a small-\eta result, though. At \eta = 0.1, B = 1 the simulation gives 8.24 against 3.06 from the exact additive-noise formula, because real per-example noise grows as w wanders away from w^* (multiplicative noise), which the model above leaves out.

What to say out loud: "Constant-step SGD doesn't converge; it reaches a stationary distribution around the minimum. The excess loss is \eta\sigma^{2}/(2B(2 - \eta\lambda)), about \eta\sigma^{2}/4B, so it depends on \eta over B. That's the linear scaling rule, and it breaks near the stability cliff and beyond the critical batch. To go lower you decay \eta with \sum\eta_{t} = \infty and \sum\eta_{t}^{2} < \infty, or average the iterates."

Follow-ups that separate senior from research-level answers:

• "Is this a temperature?" Yes, loosely. In the small-\eta limit SGD behaves like a Langevin-type SDE whose noise level scales with \eta/B. If the gradient noise is isotropic (covariance \propto I), the stationary distribution near a minimum is approximately Gibbs, \propto \exp(-L/T) with T \propto \eta/B. Near the optimum of a well-specified model the noise covariance is closer to \propto H; then the stationary spread is the same in every direction (not Gibbs), and the sharp directions carry the most excess loss (Card 20).
• "Is the noise only a cost?" No. GD with a finite step implicitly follows a modified loss L + (\eta/4)\lVert \nabla L\rVert ^{2} (Barrett and Dherin, 2021), and SGD adds a penalty on the variance of the minibatch gradients (Smith et al., 2021). Both favor flatter regions (Section 11, Card 20).
• "Why do LLM schedules end with a decay?" The floor \propto \eta. A long stable phase at high \eta makes progress; the final decay (cosine to about 10% of peak, or the "D" of warmup-stable-decay) collapses the floor, which is why the loss drops sharply at the end. On the 10k orders with the same budget, constant \eta ends at excess 0.0373 and cosine at 1.6 \times 10^{-4}.
• "Momentum removes the floor?" No. It averages noise, but the effective step grows to \eta/(1 - \beta) and so does the floor. At a matched effective step it sits about where plain SGD's does.
• "Why do c/t schedules sometimes crawl?" The 1/t rate needs 2c\mu > 1 for the flattest curvature \mu. With c too small, E[e^{2}] decays only like t^{-2c\mu} (Drill 17).
• "What about online learning under drift?" Then the floor is the price of tracking. A constant \eta is exponential forgetting with a memory of about 1/(\eta\lambda) steps, and decaying it to zero stops the model adapting (Q38).

How to identify it in real data: the training loss flattens above the full-batch optimum and doesn't improve with more epochs. The plateau height moves with \eta/B: halve \eta or double B and the gap roughly halves. The gradient norm stays well away from zero. When a step schedule cuts \eta, the loss drops at once (the "staircase").

How to mitigate it:

1. Decay the learning rate (step, cosine, 1/t, or the final phase of WSD). "Warm up, hold, cool down."
2. Average the iterates (Polyak, or an EMA of the weights).
3. Grow the batch late in training, which lowers the floor at the same \eta and pays off more as \lVert G\rVert shrinks.
4. Variance reduction (SVRG, SAGA) for finite-sum convex problems, which removes the floor at constant \eta. On the 10k orders (B = 1, \eta = 0.005), SVRG reaches excess 6.2 \times 10^{-7} after five snapshot rounds, while SGD with the same \eta and gradient budget hovers near 0.155 (Section 6).
5. Stop at the statistical floor. Optimizing much past the parameter standard errors (0.014 for w_{\text{km}} on the 10k orders) buys nothing (Section 1).

Remember: Rotate, Recurse, Read off. Deterministic: factor 1 - \eta\lambda, cliff 2/\lambda_{\max}, rate (\kappa - 1)/(\kappa + 1). Stochastic: stationary variance from a geometric series, floor \eta\sigma^{2}/(2B(2 - \eta\lambda)) \propto \eta/B. Always name the convergence criterion before quoting a step count.

Level 4 drills

Twenty drills. Drills 1–4 cover step size and rates; 5–9 momentum, minibatch variance and Adam; 10–11 Newton; 12–13 non-convex landscapes; 14–16 constraints and implicit bias; 17–19 stochastic theory; 20 regularization as conditioning. Cover the answer, run the recipe on paper, then check. Every answer was checked in sims/bank.py (Drill 20 in sims/review.py): by Monte Carlo where the problem has noise, and by running the exact update rule otherwise. "Verified by simulation" below marks a Monte Carlo check.

Step size and rates — Drills 1–4

Drill 1 · The cliff in one dimension

A pricing team tunes one weight whose loss is well approximated by a 1-D quadratic with the same curvature as the toy's steep direction. Their sweep shows smooth descent at some step sizes, a loss that flips sign each step but still shrinks at others, and blow-ups beyond a point. The interviewer writes L(w) = (a/2)w^{2} with a = 5 and asks: "For which \eta does GD converge monotonically, converge while oscillating, or diverge? What happens exactly at the boundaries?"

Concept tested: the four learning-rate regimes (Card 5).

• Answer: monotone for \eta < 0.2; oscillating but converging for 0.2 < \eta < 0.4; diverging for \eta > 0.4. At \eta = 0.2 it lands on w = 0 in one step; at \eta = 0.4 it bounces between \pm w_{0} forever.
• Intuition: each step multiplies w by 1 - 5\eta. Below 1/a that factor is positive; between 1/a and 2/a it's negative but smaller than 1 in size; past 2/a it's bigger than 1 in size.
• Why: running the update for 50 steps confirms it: \eta = 0.1 and 0.19 monotone, 0.21 and 0.39 oscillating to zero, 0.41 diverging. "1/\lambda smooth, 2/\lambda the cliff."

w_k

the single weight after k steps (its optimum is 0)

w_{k+1}

the weight one step later

a

the curvature of the 1-D loss (a/2)w^2: 5, like the toy's steep direction

Drill 2 · Two eigenvalues, one step

A ranking model's loss near its optimum has a Hessian with eigenvalues 50 and 0.5 (\kappa = 100). The team runs full-batch GD at a fixed step and wants to know how long to budget. "What is the best fixed \eta, what rate does it give, and how many steps until the distance to the optimum shrinks by a factor of 10^{6}?"

Concept tested: the optimal fixed step and the (\kappa - 1)/(\kappa + 1) rate (Cards 6–7).

• Answer: \eta^* = 2/50.5 \approx 0.0396, \rho = 99/101 \approx 0.980, k \approx 691 steps. Running the iteration from e_{0} = (1, 1) takes exactly 691.
• Intuition: the best single step makes the steep mode overshoot by exactly as much as the flat mode undershoots, so both shrink at the same rate.
• Why: minimize \max_{i} \lvert 1 - \eta\lambda_{i}\rvert. The two factors are equal and opposite at \eta^*.

• Next they'll ask: "And by loss?" → About half as many, because the loss is quadratic in the error and falls by \rho^{2} per step (WP1: 991 by distance, 496 by loss). "With \eta = 1/L instead?" → \rho = 1 - 1/\kappa, so about \kappa \ln(1/\varepsilon) steps: roughly twice the count at \eta^*, which is why the textbook bound with \eta = 1/L is looser.

Drill 3 · Which direction survives

On the six-order bowl (best weights (3, 2), Hessian eigenvalues 5 along (1, 1)/\sqrt{2} and 5/3 along (1, -1)/\sqrt{2}), a new hire runs GD from (0, 0) with \eta = 0.2 and notices that after the first step the iterates move along a straight line. "From which direction does w approach (3, 2) after step 1, and by what factor does the error shrink per step?"

Concept tested: GD in the eigenbasis; \eta = 1/\lambda_{\max} zeroes the steep mode.

• Answer: along (1, -1)/\sqrt{2}. The error after one step is (−1/3, +1/3), pure flat mode, and it shrinks by 2/3 per step: (2.667, 2.333), (2.778, 2.222), …
• Intuition: \eta = 0.2 is exactly 1/\lambda_{\max}, so the steep mode's factor is 1 - 0.2 \times 5 = 0, and one step removes it completely. What's left is "trade distance for items", the direction the data barely pins down.
• Why: running the iteration confirms the direction (−0.707, 0.707) and the shrink ratio 0.667.

Drill 4 · Heavy ball for \kappa = 100

The same ranking model (eigenvalues 100 and 1 after rescaling) is switched to heavy-ball momentum. The engineer wants to know whether it's worth tuning. "What are the optimal \beta and \eta, what rate do they give, and how many steps to 10^{6} compared with plain GD? Would a simulation agree with your formula?"

Concept tested: the optimal heavy-ball rate \sqrt{\kappa} and the k\cdot \rho^{k} transient (Card 11).

• Answer: \beta = (9/11)^{2} \approx 0.669, \eta = 4/121 \approx 0.0331, \rho = 9/11 \approx 0.818. The rate formula gives about 69 steps against 691 for GD (10×). Running the iteration needs 93: still 7.4× fewer than GD's 691.
• Intuition: momentum lets the flat mode build up speed while the steep mode's oscillations cancel. At the optimum, the extreme modes sit exactly on the boundary between real and complex eigenvalues.
• Why: per mode, the error follows a 2 × 2 linear recursion. Its eigenvalues have modulus \sqrt{\beta} when they're complex. At the optimal tuning the extreme modes have a repeated eigenvalue, so the error is \propto k\cdot \rho^{k}, and solving k \ln(1/\rho) - \ln k \approx \ln 10^{6} gives about 90.

e_k

one mode's error after k steps

e_{k-1}

that error one step earlier

\beta

the momentum coefficient

\lambda

that mode's curvature (Hessian eigenvalue)

Momentum, minibatches and Adam — Drills 5–9

Drill 5 · Momentum's real step size

A colleague adds momentum \beta = 0.9 to an SGD run "without changing the learning rate", keeps \eta = 0.01, and is surprised the loss now overshoots. They insist the step is still 0.01 × gradient. The interviewer: "Using v \leftarrow \beta v + g and w \leftarrow w - \eta v, on a long stretch where the gradient is a constant g, what step does the weight eventually take?"

Concept tested: momentum as an EMA; the effective step (Card 10).

• Answer: 0.1\cdot g, which is \eta/(1 - \beta) = 10\eta. Running the update for 200 steps gives exactly 0.1g.
• Intuition: the velocity keeps adding the same gradient, discounted by 0.9 each step, so it piles up to ten copies.
• Why: a geometric series. "\beta is memory: window 1/(1 - \beta), step \eta/(1 - \beta)." To keep the same effective step when you add \beta = 0.9, divide \eta by 10.

v_t

the velocity after t steps: a running sum of past gradients

\sum_{j=0}^{t-1}

add up over the past t steps, j steps back

j

how many steps back; \beta^j is that gradient's weight

g

the constant gradient on a steady slope

\Delta w

the change in the weight per step

\frac{\eta}{1 - \beta}

momentum's effective step size: 10\eta at \beta = 0.9

Drill 6 · Sampling without replacement

The ETA trainer draws batches of 1,000 from the 10,000 orders without replacement within a batch, and a reviewer asks whether the variance formula \sigma^{2}/B in the design doc is right. "Relative to sampling with replacement, what is the variance of the minibatch mean gradient? What happens when B = N?"

Concept tested: the finite-population correction (Card 8).

• Answer: the factor is (N - B)/(N - 1) = 9{,}000/9{,}999 \approx 0.900, so the variance is 10% smaller. At B = N it is zero: the "minibatch" is the full gradient. Verified by simulation: 80,000 batches each way on the 10k gradients give a ratio of 0.902.
• Intuition: without replacement no order is counted twice, and once you've seen most of the population there's little left to be random about.
• Why: the covariance between two distinct draws without replacement is -\sigma^{2}/(N - 1), which subtracts from the variance of the mean.

\bar g_B

the minibatch mean gradient (bar = average over the batch)

\sigma^2

the variance of a single order's gradient

N

the number of orders (10,000)

\frac{N - B}{N - 1}

the finite-population correction for drawing without replacement

Drill 7 · Adam's first step

A research engineer implementing Adam from a paper forgets both bias corrections. The first update on a fresh model is visibly larger than intended. "With \beta_{1} = 0.9, \beta_{2} = 0.999, m_{0} = v_{0} = 0 and a first gradient g, how large is the uncorrected first step compared with the corrected one?"

Concept tested: bias correction of the moment estimates (Card 12).

• Answer: 0.1/\sqrt{0.001} \approx 3.16 times larger. The corrected first step is \eta\cdot \operatorname{sign}(g), exactly \eta in size whatever the gradient's scale.
• Intuition: both averages start at zero, but the square root makes v's shortfall hurt more: m is 10× too small, \sqrt{v} is 31.6× too small.
• Why: m_{1} = (1 - \beta_{1})g and v_{1} = (1 - \beta_{2})g^{2}. The ratio is exact; computing the two steps directly gives 3.16228.

m_1

Adam's gradient average after step 1, uncorrected

v_1

Adam's squared-gradient average after step 1, uncorrected

\beta_1

the decay rate of the gradient average (0.9)

\beta_2

the decay rate of the squared-gradient average (0.999)

g

the first gradient

\hat m_1

m_1 after bias correction (hat = corrected estimate)

\hat v_1

v_1 after bias correction

Drill 8 · Correcting m but not v

A buggy fork of an optimizer library corrects \hat m = m/(1 - \beta_{1}^{t}) but uses v without correction. Training seems fine after a while, but the first few hundred steps are erratic. "With \beta_{2} = 0.999, by what factor is the step inflated at t = 10, 100 and 1,000?"

Concept tested: how long v's bias lasts (Card 12).

• Answer: \sqrt{1/(1 - 0.999^{t})}: 10.0×, 3.24× and 1.26×. Running both versions of Adam on noisy gradients gives the same three factors.
• Intuition: v's memory is about 1/(1 - \beta_{2}) = 1{,}000 steps, so its startup bias takes about that long to wear off. That's one reason Adam needs warmup (Q31).
• Why: E[v_{t}] = (1 - \beta_{2}^{t})E[g^{2}] for stationary gradients, so the uncorrected denominator is too small by \sqrt{1 - \beta_{2}^{t}}.

Drill 9 · The weight nobody uses

An embedding row for a menu item that no longer exists receives zero data gradient. The team expects weight decay to shrink it. "Start w_{0} = 1 with \eta = 10^{-3} and \lambda = 0.1. What is w after 1,000 steps under AdamW, and under Adam with an L2 penalty (\lambda w added to the gradient)? Does the answer depend on \lambda?"

Concept tested: coupled L2 vs decoupled weight decay (Card 13).

• Answer: AdamW: (1 - \eta\lambda)^{1000} = (1 - 10^{-4})^{1000} \approx 0.905. Adam + L2: 0.258 after 1,000 steps, 0.021 after 2,000, and it never crosses 0. For the first 100 steps it moves about \eta per step (w = 0.902 at step 100), then slows. The result is the same for \lambda = 10^{-3} and \lambda = 1 (0.258 both times): under Adam, the penalty's strength stops mattering.
• Intuition: AdamW shrinks the weight by a fixed fraction, outside the adaptive step. Adam + L2 feeds \lambda w through the normalizer, which divides out \lambda and turns "decay" into "move about \eta per step", until \hat v remembers larger past gradients than the current one.
• Why: running both updates confirms all the numbers above. The gradient is \lambda w, so \hat m and \sqrt{\hat v} both carry a factor \lambda, and it cancels whenever \lambda\lvert w\rvert \gg \varepsilon (in the formula, the bars are the bias-corrected \beta_{1}- and \beta_{2}-weighted averages of past w and w^{2}). Since \hat v averages over about 1,000 steps of a shrinking w, \sqrt{\hat v} exceeds the current \lvert g\rvert and the steps shrink.

w_t

the unused weight after t steps

w_0

its starting value (1)

\lambda

the weight-decay or L2 strength (0.1)

\hat m_t

Adam's bias-corrected gradient average at step t

\hat v_t

Adam's bias-corrected squared-gradient average at step t

\epsilon

a tiny constant (10^{-8}) that keeps the division safe

\overline{w}_{\beta_1}

the \beta_1-weighted average of past w (bar = average)

\overline{w^2}_{\beta_2}

the \beta_2-weighted average of past w^2

• Next they'll ask: "Where does Adam + L2 converge on a real model?" → To the plain ridge solution: its fixed point is where the penalized gradient is zero, whatever the preconditioner. AdamW instead acts like ridge with a per-weight strength \lambda\sqrt{\hat v_{j}} (Section 8).

Newton — Drills 10–11

Drill 10 · Newton on a flat bottom

A teammate claims Newton's method "always converges quadratically" and proposes it for a loss whose minimum is very flat. The interviewer simplifies to f(w) = w^{4} from w_{0} = 1. "Write the Newton step. What is the convergence rate, and why isn't it quadratic?"

Concept tested: quadratic convergence needs a non-degenerate minimum (Card 14).

• Answer: w_{k+1} = (2/3)w_{k}: linear, with factor 2/3. Running five steps gives 1, 0.667, 0.444, 0.296, 0.198, 0.132, a ratio of exactly 2/3 each time.
• Intuition: Newton fits a parabola and jumps to its bottom. On w^{4} the local parabola always has its bottom only a third of the way to 0, because the curvature vanishes at the minimum.
• Why: quadratic convergence needs f''(w^*) > 0; here f''(0) = 0. For f = w^{2p} the factor is 1 - 1/(2p - 1). If you know the multiplicity, scaling the step by 3 fixes it.

f'(w_k)

the slope of f = w^4 at the current point

f''(w_k)

the curvature of f (second derivative) at the current point

Drill 11 · Square root by Newton

A staple of quant phone screens: "No calculator. Compute \sqrt{2} with Newton's method on f(x) = x^{2} - 2 from x_{0} = 1. Give the first three iterates and tell me how many correct digits you gain per step."

Concept tested: quadratic convergence (Card 14).

• Answer: 1.5, 1.416667, 1.414216. Errors are 0.0858, 0.00245 and 2.1 \times 10^{-6}: the number of correct digits roughly doubles each step (1, 2, 5, then 11 at the fourth step).
• Intuition: near a non-degenerate root the error after a step is proportional to the square of the error before it. "Quadratic doubles them."
• Why: running the iteration gives the values above. Expanding f around the root gives the error recursion below.

x_k

the k-th Newton guess for \sqrt{2}

x_{k+1}

the next guess

e_k

that guess's error, x_k - \sqrt{2}

e_{k+1}

the next guess's error

Non-convex landscapes — Drills 12–13

Drill 12 · The mountain pass

A neural ETA model's training stalls for a long stretch at the same loss, and the Hessian there has one small negative eigenvalue. The interviewer simplifies to a saddle L = \tfrac12(a^{2} - b^{2}), with the run starting at b_{0} = 10^{-6} (almost exactly on the ridge) and \eta = 0.1. "How many GD steps until \lvert b\rvert reaches 1? What if each step adds Gaussian noise of standard deviation 0.01 to b?"

Concept tested: saddle escape time; noise as an escape mechanism (Card 17).

• Answer: without noise, \ln(10^{6})/\ln(1.1) \approx 145 steps (running the update: 145). With noise \sigma = 0.01 the mean drops to 47.2 steps (verified by simulation, 2,000 seeds; median 45). Roughly, \ln(1/0.01)/\ln 1.1 \approx 48, because the noise replaces the tiny start.
• Intuition: along the downhill direction GD multiplies b by 1.1 each step, so the time to escape depends only on how many factors of 1.1 it takes to get from the start to 1. Noise hands you a start of about 0.01 for free.
• Why: along a negative-curvature direction the factor is 1 + \eta\lvert \lambda\rvert > 1, so b grows geometrically from wherever it is.

b_k

the offset from the saddle's ridge along the downhill direction after k steps

b_{k+1}

the offset one step later

b_0

the starting offset (10^{-6})

• Next they'll ask: "So is a saddle a trap?" → Only for exact GD started on the ridge. Any noise (SGD, random init) escapes in time proportional to log(1/noise), which is why saddles slow training but rarely stop it.

Drill 13 · Big steps can't sit in sharp holes

Two candidate minima of a 1-D loss: a sharp one at w = -2 with curvature 44.4, and a flat one at w = +2 with curvature 0.9. A researcher runs GD from 1,000 random starts in [−4, 4] (2,000 steps, tiny noise \sigma = 0.01 per step) at \eta = 0.01 and at \eta = 0.1. "Which minima can GD settle in at each step size? Predict, roughly, what happens to the starts that fall into the sharp basin at \eta = 0.1."

Concept tested: stability selects flat minima (Card 20).

• Answer: settling at a minimum needs curvature below 2/\eta. At \eta = 0.1, 2/\eta = 20 < 44.4, so GD can't settle in the sharp minimum: its mode factor is 1 - 0.1 \times 44.4 = -3.44. At \eta = 0.01, 2/\eta = 200, so both minima are stable (sharp factor 0.556, flat 0.991). Verified by simulation: at \eta = 0.01, 64.1% of starts settle in the flat minimum and 19% in the sharp one. At \eta = 0.1, 67.3% reach the flat one and 0% settle in the sharp one, but the same 19% stay trapped bouncing inside the sharp well (spread about 0.16) instead of being ejected. Started next to the sharp minimum, GD is still 0.080 away after 3,000 steps at \eta = 0.1, and within 3 \times 10^{-5} at \eta = 0.01.
• Intuition: a big step overshoots a narrow hole and gets thrown back up its walls. But this hole's walls flatten out higher up, where the curvature is small again, so the ball rattles around inside rather than escaping.
• Why: linearize at each minimum: the error factor is 1 - \eta\lambda. The quadratic analysis says the minimum is unstable; it doesn't say the iterate leaves the basin. "Big steps can't sit in sharp holes" means can't settle, not "always leaves".

\lambda

a minimum's curvature: 44.4 for the sharp one, 0.9 for the flat one

• Next they'll ask: "Does flat mean better generalization?" → Often observed, not a theorem. Sharpness changes under reparameterization (Dinh et al., 2017), so state it as a heuristic (Q36).

Constraints and implicit bias — Drills 14–16

Drill 14 · Soft-thresholding by hand

A teammate's lasso ETA model, fit by plain gradient descent, never produces exact zeros (Q25). You propose ISTA. The interviewer checks you can do it by hand: "Compute the prox of t\lvert w\rvert with t = 1 at z = 3, 0.5 and −2. Then take one ISTA step on the six-order toy from w = 0 with \eta = 0.1 and \lambda = 4, under the loss (1/n)\lVert y - Xw\rVert ^{2} + \lambda\lVert w\rVert _{1}."

Concept tested: the proximal operator of L1 and ISTA (Card 16).

• Answer: prox values 2, 0, −1. The ISTA step goes gradient step first, (0, 0) - 0.1 \times (-13.33, -11.67) = (1.333, 1.167), then shrinks each coordinate by \eta\lambda = 0.4 to give (0.933, 0.767). Minimizing the prox objective numerically and running the step in code both reproduce these values exactly.
• Intuition: soft-thresholding subtracts a fixed amount from each weight's size and stops at zero. Anything within t of zero lands exactly on zero.
• Why: minimize \tfrac12(w - z)^{2} + t\lvert w\rvert one coordinate at a time. Where w \ne 0 the minimizer is w = z - t\cdot\operatorname{sign}(w); if \lvert z\rvert \le t, the subgradient condition at 0 holds. "Proximal: step, then shrink."

t

the shrink threshold (1 in the drill; \eta\lambda in ISTA)

z

the input to the prox: the weight after the gradient step

\arg\min_w

the w that makes what follows smallest

w

a candidate value for one weight

\lambda

the L1 penalty strength (4 in the drill)

\lVert\cdot\rVert_1

the L1 norm: the sum of the weights' absolute values

\nabla L

the gradient of the smooth MSE part; points uphill

Drill 15 · A budget on the weights

Ops sets a combined budget: the per-km time plus the per-item time can't exceed 4 minutes (w_{\text{km}} + w_{\text{items}} \le 4), against the toy's unconstrained optimum (3, 2). "Solve the constrained problem with KKT. What is the multiplier, and what does it tell ops?"

Concept tested: KKT and the multiplier as a price (Card 15).

• Answer: w = (2.5, 1.5), \mu = 2.5. Projected GD (step, then project onto the half-plane) converges to the same point, and the gradient there gives \mu = 2.5.
• Intuition: the optimum (3, 2) has sum 5, so the constraint is tight. You slide back along the steep direction (1, 1) until the sum is 4, and since that direction is an eigenvector of H, both weights drop by the same 0.5.
• Why: stationarity says H(w - w^*) + \mu(1, 1) = 0. Since H(1, 1) = 5(1, 1), w = w^* - (\mu/5)(1, 1). The tight constraint gives 5 - 2\mu/5 = 4, so \mu = 2.5 > 0 (dual feasible, complementary slackness holds). "Some People Dislike Constraints." The price: relaxing the budget by one minute lowers the best loss by about 2.5 per unit, to first order.

\mu

the KKT multiplier for the budget: loss saved per extra minute of budget

\mathbf w^\star

the unconstrained optimum (3, 2) (star = the optimum)

Drill 16 · Which solution does GD pick?

An over-parameterized ETA model has two weights that only ever appear as a sum, so the loss is (w_{1} + w_{2} - 2)^{2} and infinitely many weight pairs are perfect. "Run GD from (0, 0). Where does it end? Now start from (3, 0). Where does it end, and which of the two is the minimum-norm solution?"

Concept tested: implicit bias of GD toward the minimum-norm solution (Card 18).

• Answer: from (0, 0) it ends at (1, 1), the minimum-norm solution. From (3, 0) it ends at (2.5, −0.5). Running GD for 500 steps from each start gives these values.
• Intuition: the gradient only ever points along (1, 1), so GD can't change the part of w along (1, −1). Whatever you start with in that direction, you keep.
• Why: \nabla L = 2(w_{1} + w_{2} - 2)(1, 1) lies in the row space of X. Starting from 0, the iterates stay in the row space, and the only perfect fit there is the minimum-norm one. From (3, 0) the null-space part (1.5, −1.5) survives, and (1, 1) + (1.5, −1.5) = (2.5, −0.5).

w_1

the first of the two weights that only appear as a sum

w_2

the second weight

\mathbf w_\infty

where GD ends after many steps

X^+ y

the minimum-norm perfect fit (pseudo-inverse of X times the targets): (1, 1)

w_{0,1}

the first weight's starting value

w_{0,2}

the second weight's starting value

Stochastic theory — Drills 17–19

Drill 17 · The decaying step c/t

To get below the noise floor (WP2), a team switches to \eta_{t} = c/t and finds that with c = 0.25 the loss decays much more slowly than with c = 1. The interviewer simplifies: SGD on L = \tfrac12w^{2} with unit-variance gradient noise, so w_{t+1} = w_{t} - \eta_{t}(w_{t} + \xi_{t}). "How does E[w^{2}] decay in t for c = 1 and for c = 0.25? What's the general rule?"

Concept tested: Robbins–Monro rates and the 2c\mu > 1 condition (Card 9).

• Answer: c = 1: E[w^{2}] \propto 1/t. c = 0.25: E[w^{2}] \propto t^{-0.5}. The general rule is t^{-\min(1, 2c\mu)}, here with \mu = 1. Verified by simulation (20,000 chains, slopes fitted on log-log over t = 1{,}000 to 10,000): −1.00 and −0.498.
• Intuition: with c too small, the step decays faster than the pull toward the minimum can remove the starting error. The deterministic part then shrinks only like t^{-2c}, which is slower than the 1/t of the averaged noise.
• Why: take expectations in the variance recursion. Try v = A/t: matching the 1/t^{2} terms gives A = c^{2}/(2c - 1), which is valid only for 2c > 1. For 2c < 1, the deterministic product \prod(1 - c/s)^{2} \propto t^{-2c} dominates.

v_t

E[w_t^2]: the expected squared error at step t

v_{t+1}

the same one step later

c

the schedule constant in \eta_t = c/t (1 or 0.25)

Drill 18 · The critical batch size

The infra team wants to keep doubling the batch size for throughput. At the current point in training, the per-example gradient covariance has \operatorname{tr} \Sigma = 100 and the full-batch gradient has \lVert G\rVert ^{2} = 0.5 (curvature normalized to H = I). "Beyond what batch size does doubling B stop paying off? How much per-step progress do you get at B = 200, 400 and 1,600, relative to a noiseless gradient?"

Concept tested: the gradient noise scale B_{\text{noise}} = \operatorname{tr} \Sigma/\lVert G\rVert ^{2} (Card 19).

• Answer: B_{\text{noise}} = 100/0.5 = 200. With the best \eta for each batch, per-step progress is B/(B + B_{\text{noise}}) of the noiseless maximum: 0.50 at B = 200, 0.67 at 400, 0.89 at 1,600. Verified by simulation (Monte Carlo estimate of E\lVert g_B\rVert ^{2}, then optimal \eta): 0.499, 0.667, 0.889. Well below 200, doubling B buys a lot (50 → 100 raises progress from 0.20 to 0.33); well above it, doubling B mostly doubles compute (800 → 1,600 raises it only from 0.80 to 0.89).
• Intuition: batching averages away noise. Once the noise is smaller than the signal, there's little left to average away.
• Why: expand the expected loss after one step to second order and optimize \eta. Steps needed scale like 1 + B_{\text{noise}}/B, and examples processed like B + B_{\text{noise}} (McCandlish et al., 2018).

\mathbb E[L(\mathbf w - \eta\mathbf g_B)]

the average loss after one minibatch step

L

the loss at the current weights

\lVert G\rVert^2

the full-batch gradient's squared length: the signal (0.5 here)

\Delta L_{\max}

the largest one-step drop in loss, with the best \eta

B_{\text{noise}}

the gradient noise scale \operatorname{tr}\Sigma/\lVert G\rVert^2: the critical batch size (200 here)

• Next they'll ask: "Is B_{\text{noise}} fixed?" → No. \lVert G\rVert shrinks as training proceeds while the noise doesn't, so B_{\text{noise}} grows: on the 10k orders it is 3.75 at w = 0. Larger batches pay off more late in training.

Drill 19 · Importance sampling

In the ETA data, 90% of orders produce a gradient of norm 1 and 10% (long, multi-item orders) produce norm 9. Uniform minibatches are dominated by whether a long order happened to be drawn. "Compare the second moment of the single-sample gradient estimate under uniform sampling and under optimal importance sampling (p_{i} \propto \lVert g_{i}\rVert, reweighted by 1/(Np_{i})). Is the importance-sampled estimate still unbiased?"

Concept tested: importance sampling for SGD: variance reduction while staying unbiased (Section 10, the four S's).

• Answer: uniform: 0.9 × 1 + 0.1 × 81 = 9.0. Optimal IS: (E\lVert g\rVert )^{2} = (0.9 + 0.9)^{2} = 3.24, a 2.78× reduction. Still unbiased. Verified by simulation (10^{6} draws, random gradient signs): 8.97 and 3.24, and the importance-sampled mean is −0.0037 against a true mean of −0.0040. Because the mean gradient is near zero here, the second moment is essentially the variance.
• Intuition: sample the big-gradient orders more often but count each one for less, so every draw contributes about the same amount.
• Why: the reweighting makes the expectation exact. With p_{i} \propto \lVert g_{i}\rVert, Cauchy–Schwarz shows this choice minimizes the second moment.

\mathbf g_i

order i's gradient (norm 1 for most orders, 9 for long ones)

p_i

the probability of sampling order i

\frac{\mathbf g_i}{Np_i}

the reweighted single-sample gradient estimate

\sum_i

add up over all N orders

\lVert\mathbf g_i\rVert

the length of order i's gradient

• Next they'll ask: "Why not do this always?" → You need the per-example gradient norms, which cost about as much as the gradients themselves. Practical versions use a cheap proxy (the loss, or the last-layer gradient) and are stale. Forget the 1/(Np_{i}) reweighting and the gradient is biased toward the oversampled orders.

Regularization and conditioning — Drill 20

Drill 20 · Ridge as a speed fix

The raw 10k ETA model (intercept, km and items, unscaled; Hessian eigenvalues 49.93, 4.58 and 0.348) needs 991 GD steps at its best fixed step to shrink the distance to the optimum by 10^{6}. A teammate finds that adding (\lambda/2)\lVert w\rVert ^{2} on all three weights with \lambda = 1 makes training "four times faster" and proposes it as the fix. "What does the penalty do to \kappa and to the step count, and what's the catch?"

Concept tested: an L2 penalty shifts every Hessian eigenvalue by \lambda: better conditioning, different answer.

• Answer: the Hessian becomes H + I, with eigenvalues 50.93, 5.58 and 1.348, so \kappa falls from 143 to 37.8, \rho from 0.986 to 0.948, and the step count from 991 to 261 (running GD at the new best step also takes 261). The catch: the minimizer moves from the OLS answer (6.05, 2.99, 1.99) to (2.17, 3.19, 2.72). With uncentered features the penalized intercept collapses and the slopes absorb it. At \lambda = 0.1 the gain nearly vanishes (\kappa = 112, 772 steps). Standardizing gets \kappa = 2.15 with no bias at all.
• Intuition: ridge lifts the floor of the flattest direction, so the ravine gets shallower; but it also pulls the answer toward zero, most of all along that same flat direction, where the data were weakest.
• Why: the penalty's Hessian is \lambda I, which shares every eigenvector with H and adds \lambda to each eigenvalue. \kappa drops a lot only when \lambda is comparable with \lambda_{\min}.

\kappa_\lambda

the condition number after adding the ridge penalty

\lambda

the ridge penalty strength (1 here); it adds \lambda to every eigenvalue

• Next they'll ask: "So is ridge ever the right speed fix?" → Only when you wanted the penalty anyway (it also makes logistic loss strongly convex, \mu \ge \lambda, with a unique minimum). For speed alone, precondition: center and scale, or use a method that adapts to curvature.

Optimization-failure cheat sheet

Counting traps (the formula is right, the number quoted is wrong): distance vs loss criteria differ by a factor of 2 (991 vs 496, WP1); the asymptotic \sqrt{\kappa} speedup is not the realized one (12× on paper vs 7–9× in WP1's run; 10× vs 7.4× in Drill 4); \eta^* is optimal for the worst case, not for every start (WP1); the noise-floor formula is for small \eta and additive noise (WP2); "can't settle" is not "leaves the basin" (Drill 13).

Rapid fire — the day before

One line each. Cover the right column and answer out loud; anything you hesitate on, go back to its full question above.

Review schedule: go through this table the day after you study, then 3 days later, a week later, and 3 weeks later. Any row you miss goes back to the start.