The Optimization Domain: Convexity, Rates, and Which of Your Training Claims Are Theorems

Start with the one sentence everything else hangs on, stated with the three words that are usually dropped. An optimization problem is a function and a set; a method is a sequence of queries to an oracle about that function; a guarantee is a statement about the worst function in a class after a fixed number of queries. Nothing else is primitive. "Converges", "rate", "optimal", "condition number", "step size" and "stationary" are all defined in terms of those three objects, and every time one of them produces a paradox it is because the class or the oracle was left implicit and two readers filled it in differently. Say that gradient descent on a smooth convex function "converges at rate $1/T$" and a reader who has the class $\{$convex, $L$-smooth$\}$ in mind is right; a reader who has strongly convex functions in mind is also right, and gets a geometric rate instead; and a reader who is thinking of a quadratic with a single bad direction and a particular start is right to observe that the first reader's bound is off by a factor of a thousand on it. §3 shows all three with numbers. Every result in this piece is a consequence of taking that sentence seriously, including the cases where a method that provably converges on every function in a class is the wrong method on the one function you have, and where a method with no guarantee at all is the one that trains your model.

Here is the claim, at the width the mathematics supports, because the tidy version is wrong in both directions. We are not claiming that training a neural network is convex optimization wearing a hat, and we are not claiming that a practitioner needs Nesterov's lower bound to pick a learning rate — nobody does, and we say exactly where the convex theory stops applying. The claim is this:

Optimization theory supplies the class in which each training claim is a theorem, and the rate at which it is one. "Gradient descent with step $1/L$ reaches an $\varepsilon$-stationary point of a smooth function in $O(1/\varepsilon^2)$ steps" is an exact theorem, convex or not, and nothing better is possible for a first-order method. "Momentum accelerates" is a theorem on the class of smooth strongly convex functions, with the exponent $\sqrt\kappa$ in place of $\kappa$, and a heuristic everywhere else. "Adam converges" is false as stated — there is a convex problem on which it does not — and true for the variant that monotonises its second moment. "A learning-rate cooldown drops the loss" is a one-line computation on a noisy quadratic. "SGD finds flat minima that generalise" is a hypothesis with a counter-example attached to the word "flat". "Deep networks have no bad local minima" is false as stated and true for matrix factorisation. The value of the lens is not that everything is secretly convex. It is that it tells you which of your claims are theorems, which are theorems on a class your loss is not in, and which are hypotheses.

Every connection in this piece carries one of four labels — the same four as our Information Domain and Probability Domain pieces, so the three can be read as chapters of one book. If you are here for the learning-rate questions, skip to §5 and come back to this table the first time a label stops you:

Where a connection has two parts we grade both: the theorem, and the claim that the training problem satisfies its hypotheses. Nesterov's acceleration is L1; "a transformer's loss is smooth and strongly convex near the end of training, so momentum is accelerating it" is L3; the two grades sit side by side in §3 and §4 rather than being averaged into one. In this piece the second grade bites harder than it did in the earlier two, because almost every theorem below is stated for a class — convex, smooth, PL, strict-saddle — and the first question about any training loss is which class, if any, it is in.

Four running examples carry the same numbers through the whole piece, so that when two sections seem to disagree you can see which one is wrong.

• E1 — the quadratic with condition number $\kappa$: $f(x) = \tfrac12 x^\top A x$ with eigenvalues log-spaced in $[1, \kappa]$. The step-size boundary at $2/L$ (§0), the rates of gradient descent, heavy ball and Nesterov against their theorems (§3), the block-heterogeneous version on which one learning rate fails and a diagonal preconditioner is exact (§4), the noise floor $\alpha\sigma^2/(2-\alpha)$ under additive gradient noise (§5), and the noisy quadratic model on which every learning-rate schedule can be computed exactly (§5).
• E2 — logistic regression, in two forms: a 30-dimensional problem on which the batch-size curve and the gradient noise scale are measured (§5), and our Probability Domain's two-class Gaussian mixture in $d = 20$ with Bayes risk $\Phi(-1) = 0.1587$, on which the three errors of the excess risk — approximation, estimation, optimization — are separated (§5.7).
• E3 — rank-$r$ matrix sensing, $f(U) = \tfrac{1}{4m}\sum_i(\langle A_i, UU^\top\rangle - y_i)^2$: a non-convex problem that gradient descent solves from every random start (§0), the strict saddle at $U = 0$ that it never leaves when started there (§0), the theorem that explains both (§7), and what over-parameterising the factor costs (§7).
• E4 — the two-dimensional Rastrigin function, $f(x) = 20 + \sum_i (x_i^2 - 10\cos 2\pi x_i)$ on $[-5.12, 5.12]^2$: the problem on which branch-and-bound certifies the global minimum and on which the number of boxes it needs grows exponentially with dimension (§8), on which local search succeeds one time in a hundred, annealed Langevin one time in nine and Bayesian optimization finds a better point than random search with the same budget (§8).

Prerequisites. Calculus, including the gradient and the Hessian; linear algebra at the level of eigenvalues and the singular value decomposition; the words "mean" and "variance"; having trained something with SGD or Adam. No convex analysis is assumed, and some is taught: §1 to §3 build the objects the rest of the piece is written in — the convex function, the subgradient, the conjugate, the oracle and the condition number — from those prerequisites, and build only those. Two kinds of section follow. §1 to §5 and §6.2–§6.4 are built from the stated prerequisites: each theorem they use is stated with its hypotheses and either proved, sketched, or reduced to a named result the text has already given. §4.6, §6.1, §7, §8.2 and §9 state theorems with their assumptions and a reference and do not pretend to prove them; those sections are read for what a theorem licenses and what it does not. If you know convex optimization, §1 to §3 are a fast re-read with the machine-learning consumers attached; the new material for you starts at §4.

Three reading paths, and the sections none of them may skip. The piece is six modules — Convex core §1–§3; Geometry §4; Stochastic §5; Non-convex §6–§7; Global §8; Minimax and the rest §9–§11 — and the paths are routes through them.

The fast path, for the practitioner who wants the learning-rate answers and will come back for the objects, has fourteen stops, each marked by a banner under its heading: §0, §1.4, §3.2, §3.3, §4.4, §4.5, §5.1, §5.2, §5.4, §5.6, §6.2, §7.3, §10 and §11, in that order. Its destination is §5.4, the schedule section, which is stop 9. If you only have two hours, start here and stop at §11. The fast path is a route through fourteen selected results, not a substitute for the objects behind their proofs: a claim quoted at a stop is proved in a section the path skips, and the hypotheses the stop's number rests on are stated there.

The full practitioner path is §0 → §1 → §3 → §4 → §5 → §6 → §7 → §10 → §11, doing the checkpoint exercises that lie on it. The theorist path is §0 → §1 → §2 → §3 → §4 → §5 → §6 → §7 → §8 → §9 → §10 → §11. §1, §3 and §5 are on both full paths: §1 is the object, §3 is what a rate is and why momentum is a theorem, and §5 is the regime every training loop actually runs in. §2 (duality) is the bridge to our Information Domain piece and the section a reader who liked that one should take. §8 (global optimization) is the section the board asked for by name and the one most likely to be new to a deep-learning reader; it is on the theorist path and recommended on the other, because the practitioner's intuition that "global" is the goal is corrected there. §9 (minimax) is the on-ramp to our game-theory pieces and can be read on its own. The history is Appendix A, the audit of where this machinery is load-bearing outside machine learning is Appendix B, two toy cases of ours are Appendix C, and the graded ledger of how this piece bears on our earlier posts is Appendix D. This piece stands alone: where an earlier post of ours is relevant it is linked as a citation, the way a paper would be, and nothing below requires having read it.

Six common misreadings, up front. The material below is misapplied in a few recurring ways; §10 gives the action that replaces each, and the section named proves the correction. (1) Reading a rate without its class: Nesterov's $1/T^2$ is a theorem on smooth convex functions and says nothing about a transformer's loss (§3.4, §6.2). (2) Reading "flat" as a property of the function: sharpness changes under reparametrisation, so every flatness claim needs a normalisation before it is well-defined (§7.5). (3) Reading "Adam converged" as a statement about the problem: at a constant step it is a statement about the noise floor, and without a schedule it is not a convergence claim at all (§5.1, §5.4, §6.2). (4) Reading a theorem on the simplex as a theorem in the logits: the KL-penalised objective is concave in the probabilities and not in the parameters, already for two actions (§1.5, §2.4, §9.2). (5) Reading the constants as transferable: $\beta = 0.9$ accelerates nothing in the $\sqrt\kappa$ sense, $\eta = 2/L$ is the boundary and not a safe step, and Adam's $\eta$ bounds a coordinate's step only up to a factor — $3.16$ for one gradient after a quiet stretch, $7.27$ over all gradient histories (§3.3, §0, §4.4). (6) Reading a certificate into a method that has none: restarts, annealing and Bayesian optimization report a success rate, branch-and-bound reports a proof, and only the latter is "global" (§8.1, §8.3).

Companion code. Every number in a code block below is copied from the printed output of worked_numbers.py, a single NumPy script with 53 numbered sections, float64, CPU-only, that ships with this piece; a section number in the form §N beside a block names the section that printed it, the numbers are verbatim, and where a line's label has been shortened for the page the full label is in the script's output file. The script's generator is seeded once, default_rng(20261105), and the sections draw from it in order, so that a reader running the script reproduces every line, line for line, in the pinned environment (requirements.txt: Python 3.14.5, NumPy 2.5.3). On another Python or NumPy build the closed-form lines are identical and the seeded Monte Carlo lines agree within their printed standard errors but not necessarily to the digit — a different build can round, and therefore iterate, differently — so the check elsewhere is agreement within tolerance, not identical digits (an independent re-run on Linux, Python 3.13 / NumPy 2.3, reproduced forty of forty-nine sections exactly and moved nine within their tolerances, with every section's reading surviving); every Monte Carlo value that is compared to a theory value is printed with its standard error, computed from the draws the section already makes. The script takes about eleven minutes on a laptop; the bulk of that is the batch-size sweep of §17 and the branch-and-bound of §32, both of which are the point. A test_worked_numbers.py beside the script re-derives the closed-form values the blocks are compared against. The two companion notebooks — 00_convex_machinery.ipynb (the puzzles, convexity, duality, rates, mirror descent and natural gradient, Adam's counter-example, the orthogonalised update, the stochastic regime and schedules, the three errors, and the critic-round counter-examples: the heavy-ball prefactor, KL in the logits, Adam's step after a quiet stretch and over all histories, and AdamW against the exact prox) and 01_nonconvex_and_global.ipynb (stationarity, saddles, PL, autodiff at a kink, benign landscapes, lazy versus feature learning, the edge of stability, implicit bias, mode connectivity, branch-and-bound, Langevin, Bayesian optimization, verification, quantisation, minimax, compressed sensing, double descent, the stable-ReLU interval counter-example, the GRPO baseline, the Goemans–Williamson triangle, the Euler–Langevin variance and the two saddle-method spectral radii) — ship beside it, built from those sections cell by cell; each cell restores the script's generator state at its section, so a notebook prints this piece's numbers whether it is run top to bottom or one cell at a time. A reader on the fast path who runs only the cells its stops quote — §1, §2, §3, §7, §12, §13, §14, §15, §16, §17, §19, §20, §21, §22, §28, §42, §46 and §48, eighteen cells — sees every number the fast path quotes, for the same reason: each of those cells was run on its own in a fresh interpreter after the setup cell, and none reads a variable that an earlier cell defines (the setup cell holds every helper, and the state each cell needs beyond the generator is computed inside it).

Units and conventions, once. $f$ is the function to be minimised; $f^\star$ its infimum; $x^\star$ a minimiser when one exists. $L$ is the Lipschitz constant of the gradient ("$f$ is $L$-smooth"), $\mu$ the strong-convexity constant, $\kappa = L/\mu$ the condition number. $\eta$ and $\alpha$ are both step sizes — $\eta$ when the step is a design choice, $\alpha$ when it is the subject of a theorem — because the two literatures use different letters and we quote both. $T$ is the number of steps, $t$ the current one. $\|\cdot\|$ with no subscript is Euclidean; $\|\cdot\|_2$ on a matrix is the spectral norm, $\|\cdot\|_F$ the Frobenius norm, $\|\cdot\|_\ast$ the nuclear norm. Logarithms are natural. "a.s." means almost surely. A rate is an upper bound on $f(x_T) - f^\star$ or on $\min_{t\le T}\|\nabla f(x_t)\|^2$ as a function of $T$, over a class; a lower bound is a statement that no method in a class of methods can do better on the worst function in a class of functions.

0. Three puzzles that are one puzzle

Fast path · stop 1 of 14. Next stop: §1.4. This section's numbers run in 00_convex_machinery.ipynb.

Optimization is counter-intuitive in a specific way. The puzzles that trip people up are almost never about the arithmetic of a step; they are about which class the function is in and which oracle the method is talking to. Three of them, each resolved by naming the object the question left out, and each the seed of a section below.

Puzzle 1 — one step size, two verdicts. Take E1 at $\kappa = 100$: twenty eigenvalues log-spaced from $1$ to $100$, so $L = 100$. Run gradient descent with the step written as a multiple of $1/L$, for 200 steps from the all-ones vector:

§1 Puzzle 1: one step size, two verdicts — GD on a quadratic at eta = 0.5/L, 1.9/L, 2.1/L
  eta = 0.50/L  f(x_200) =   1.7290e-01   contraction factor max|1-eta*lambda| = 0.9950
  eta = 1.00/L  f(x_200) =   1.4182e-02   contraction factor max|1-eta*lambda| = 0.9900
  eta = 1.90/L  f(x_200) =   2.7082e-04   contraction factor max|1-eta*lambda| = 0.9810
  eta = 1.99/L  f(x_200) =   8.9771e-01   contraction factor max|1-eta*lambda| = 0.9900
  eta = 2.01/L  f(x_200) =   2.6762e+03   contraction factor max|1-eta*lambda| = 1.0100
  eta = 2.10/L  f(x_200) =   1.8032e+18   contraction factor max|1-eta*lambda| = 1.1000
  L = 100.0, mu = 1.0, kappa = 100; the boundary is eta = 2/L = 0.0200

Every step below $2/L$ converges, and the best of the six is $1.9/L$ — fifty times better than the "safe" $1/L$ after the same 200 steps — not because a larger step is always better but because the quantity that decides, $\max_i |1 - \eta\lambda_i|$, is smallest when the two ends of the spectrum contract equally: at $1.9/L$ the stiffest direction contracts at $0.90$ per step and the softest at $0.981$; at $1.99/L$ the stiffest direction oscillates at $0.99$ and the run is worse than at $1/L$, though still convergent. (The optimum is $2/(L + \mu)$, where the two factors coincide.) Every step above $2/L$ diverges, and the divergence is not gradual: at $2.01/L$ the loss after 200 steps is $2{,}700$, at $2.1/L$ it is $10^{18}$. The contraction factor of the worst eigen-direction is a function of the step and the largest curvature only. Now the puzzle. The step that trains a transformer under Adam is $3\times10^{-4}$ or so, and a practitioner who has never seen a loss diverge at that step takes it to a convex logistic regression and watches it oscillate. The resolution is the oracle, not the function: Adam's update is not the gradient, it is the gradient divided coordinate-wise by a running root-mean-square of itself, so its step has the units of the parameter and not of the parameter divided by curvature, and the $2/L$ rule does not apply to it in the form above (it applies in another form: §4.4). The same number is a step size for one method and a trust-region radius for the other. §1.4 names $L$ and $\kappa$, §3 turns the contraction factor into a rate, and §7.3 shows a network whose top curvature is driven to exactly $2/\eta$ by the training dynamics and held there.

Puzzle 2 — the same loss, zero training error twice, two different models. Take a least-squares problem with $d = 200$ parameters and $n = 40$ examples, generated by a sparse truth (ten nonzero coefficients). Any method that reaches zero training loss has solved the problem as posed. Run two from the origin — plain gradient descent, and sign descent, which is Adam with both moving averages switched off — and compare them with the minimum-norm interpolant that the pseudo-inverse computes:

§2 Puzzle 2: same loss, zero training error twice, two different models (d > n least squares)
  GD from 0            train MSE =  9.15e-32  test MSE =  54.7481  ||w||_2 =   3.336  ||w||_1 =    36.74  ||w||_inf = 0.933
  sign descent from 0  train MSE =  8.58e-05  test MSE =  68.2429  ||w||_2 =   3.867  ||w||_1 =    50.48  ||w||_inf = 0.348
  min-norm (pinv)      train MSE =  4.27e-28  test MSE =  54.7481  ||w||_2 =   3.336  ||w||_1 =    36.74  ||w||_inf = 0.933
  ||w_GD - w_minnorm||_2 = 9.95e-15   (GD from zero converges to the min-norm interpolant)

Both optimizers minimised the same function to (essentially) the same value. They returned different vectors, with different test errors, and gradient descent's vector is the minimum-Euclidean-norm interpolant to fourteen digits while sign descent's is a different interpolant with a smaller $\ell_\infty$ norm and a larger $\ell_2$ norm. The loss did not choose the model; the method did, by a bias the loss never mentions. This is a theorem for gradient descent on least squares (the iterates never leave the row space of $X$, so the limit is the min-norm solution — a four-line argument, §7.4) and a theorem of a different kind for sign descent (§7.4 states it with its grade). The practical content: when a problem has many global minima — every over-parameterised problem does — "which optimizer" is a question about which minimum, not about speed, and the two optimizers that reach zero loss fastest need not reach the same place. §4 and §7.4 carry this through to the implicit bias of Adam versus SGD on real networks, with the grade the evidence supports.

Puzzle 3 — a non-convex problem that gradient descent solves from any random start. E3 at rank one: $u \in \mathbb R^{10}$, $m = 200$ Gaussian sensing matrices, and $f(x) = \tfrac{1}{4m}\sum_i(\langle A_i, xx^\top\rangle - y_i)^2$, which is a quartic in $x$ and not convex (it has two global minima, $\pm u$, and a convex function has a convex set of minimisers). Run gradient descent from a hundred random starts, and once from the origin:

§3 Puzzle 3: a non-convex problem that gradient descent solves from any random start (rank-1 matrix sensing)
  100 random starts (scale 0.1), step 0.1: reached a global minimiser (x = +/-u to 1e-4) in 100/100 runs; steps to f < 1e-12: median 84, max 108
  Hessian at the saddle x = 0: lambda_min = -2.5073, lambda_max = 0.5781  (lambda_min < 0: x = 0 is a strict saddle, not a minimum)
  started exactly at x = 0: f after 20000 steps = 6.1520e-01  (gradient descent never leaves a stationary point)

A hundred of a hundred, in about ninety steps, on a function that no convexity theorem covers; and a run that never moves, from a point where the gradient is exactly zero and the Hessian has a negative eigenvalue of $-2.5$ — a strict saddle, from which the slightest push would have escaped in a few dozen steps (§6.3 measures how many). The resolution is the class: this function is not convex, but every one of its local minima is global and every one of its saddles is strict (§7.1 states the theorem with the sample-size condition that makes it true), and on that class gradient descent from a random start converges to a global minimum with probability one (§6.3). "Non-convex" is not one class; it is everything that is not convex, and the first job of §6–§8 is to separate the non-convex problems that have a theorem from the ones that have only hardness results — and to say, honestly, which of those a neural network is.

All three puzzles are the same puzzle: a method was described by what it does on one class of problems, and used on another. The rest of this piece is the catalogue of classes.

1. What convexity buys, and the one pathology it leaves

1.1 The definition is a statement about chords

A set $C \subseteq \mathbb R^d$ is convex if the segment between any two of its points lies in it: $x, y \in C \Rightarrow \theta x + (1-\theta)y \in C$ for every $\theta \in [0,1]$. A function $f: C \to \mathbb R$ on a convex set is convex if it lies below its chords,

strictly convex if the inequality is strict for $x \ne y$ and $\theta \in (0,1)$, and concave if $-f$ is convex. That is the whole definition; everything else in this section is a consequence of it, and the first thing to notice is what it does not mention: derivatives. Convexity is a property of the graph, and a function can be convex without being differentiable anywhere a step wants to go ($|x|$, the hinge loss, the $\ell_1$ penalty). The definition is also checkable, which Jensen's inequality (our Probability Domain's §3.5) turns into a test: draw chords at random and count the violations.

§4 Convexity is checked on chords: Jensen on three functions, 10,000 random chords each
  x^2                fraction of chords with f(theta a+(1-theta) b) > theta f(a)+(1-theta) f(b): 0.0000
  exp(x)             fraction of chords with f(theta a+(1-theta) b) > theta f(a)+(1-theta) f(b): 0.0000
  log-sum-exp(x, 0)  fraction of chords with f(theta a+(1-theta) b) > theta f(a)+(1-theta) f(b): 0.0000
  sin(x)             fraction of chords with f(theta a+(1-theta) b) > theta f(a)+(1-theta) f(b): 0.5034
  sqrt|x|            fraction of chords with f(theta a+(1-theta) b) > theta f(a)+(1-theta) f(b): 0.5586

The third row is the one to keep: $\log(1 + e^x)$ is the logistic loss of a single example as a function of its logit, and it is convex — which is why logistic regression, a linear logit followed by that loss, is a convex problem in its weights. (A convex function of an affine function is convex; a sum of convex functions is convex; a non-negative multiple is convex. Those three closure rules, plus "pointwise maximum of convex functions is convex", are the calculus with which one certifies a loss. Boyd & Vandenberghe's chapter 3 is the reference and is free.) The last two rows are the shape of the trouble ahead: $\sin$ is convex on half its domain and concave on the other, and $\sqrt{|x|}$ is a cusp that is concave on each side — the shape of an $\ell_p$ penalty with $p < 1$, which is exactly the sparsity penalty whose minimisation is NP-hard (§8.5).

1.2 First-order conditions, and the subgradient

For differentiable $f$ on an open convex set, convexity is equivalent to the first-order condition

the tangent plane at $x$ lies below the graph everywhere; and for twice-differentiable $f$ to $\nabla^2 f(x) \succeq 0$ everywhere. The first-order condition is the one that does work, because it is a global statement obtained from a local computation: one gradient at $x$ bounds $f$ from below on the whole domain. That is the mechanism under every convergence proof in §3.

When $f$ is convex but not differentiable at $x$, the tangent plane is replaced by the set of all planes that lie below the graph and touch it at $x$: the subdifferential

a closed convex set, non-empty at every interior point of the domain for a convex $f$ (Rockafellar's Theorem 23.4), equal to $\{\nabla f(x)\}$ where $f$ is differentiable. For $f(x) = |x|$ it is $\{\operatorname{sign} x\}$ away from zero and the whole interval $[-1, 1]$ at zero. For the hinge loss $\max(0, 1 - y\langle w, x\rangle)$ it is a segment at the kink. A method that uses "a subgradient" at a kink has a choice to make there, and the §3.5 rates for the subgradient method are rates for any choice.

1.3 Local is global: the proof, in four lines

Theorem. If $f$ is convex and $x^\star$ is a local minimiser, it is a global minimiser; the set of global minimisers is convex; if $f$ is strictly convex it has at most one.

Proof. Suppose $f(y) < f(x^\star)$ for some $y$. For $\theta \in (0,1)$, $f(\theta y + (1-\theta)x^\star) \le \theta f(y) + (1-\theta) f(x^\star) < f(x^\star)$. As $\theta \to 0$ the point $\theta y + (1-\theta)x^\star$ enters every neighbourhood of $x^\star$ with a smaller value, contradicting local minimality. Convexity of the minimiser set is the chord inequality applied to two minimisers; uniqueness under strict convexity is the same chord with a strict inequality. $\square$

The corollary that matters for a method: for a convex differentiable $f$, $\nabla f(x) = 0$ if and only if $x$ is a global minimiser (one direction is the first-order condition with $\nabla f(x) = 0$; the other is calculus), and for a nondifferentiable one, $0 \in \partial f(x)$ if and only if $x$ is a global minimiser. A stationary point is the answer. Every "stationary point" guarantee of §6 is this corollary with the convexity hypothesis removed, and §6.2 is about what is left of it when it is.

1.4 Smoothness, strong convexity, and the one number to know

Fast path · stop 2 of 14. Next stop: §3.2.

Two quantitative strengthenings of convexity give the two numbers that every rate in this piece is written in.

$f$ is $L$-smooth if its gradient is $L$-Lipschitz, $\|\nabla f(x) - \nabla f(y)\| \le L\|x - y\|$; for twice-differentiable $f$ this is $-LI \preceq \nabla^2 f \preceq LI$ — both sides, since the gradient of $-10x^2$ has Lipschitz constant $20$ although its Hessian, $-20$, is below $1$. The one-sided $\nabla^2 f \preceq LI$ is the weaker upper-curvature condition; it is all the descent lemma below uses, and it coincides with smoothness exactly when $f$ is convex, because convexity supplies the other side. The distinction matters from §6 on, where smoothness is used without convexity: there the two-sided condition is the hypothesis, and a function whose curvature is bounded above but not below has a descent lemma and no $L$. Its consequence is the descent lemma, an upper quadratic:

(Proof: $f(y) - f(x) = \int_0^1 \langle \nabla f(x + s(y-x)), y - x\rangle\, ds$, subtract $\langle \nabla f(x), y - x\rangle$, bound the integrand by $sL\|y - x\|^2$ with the Lipschitz property, integrate.) Put $y = x - \eta\nabla f(x)$ and the lemma says $f(y) \le f(x) - \eta(1 - \tfrac{L\eta}{2})\|\nabla f(x)\|^2$: a gradient step of size $\eta < 2/L$ decreases $f$ by a definite amount, with the largest guaranteed decrease at $\eta = 1/L$. The descent lemma needs no convexity and only the upper side of the Hessian bound, which is why it survives into §6 — and it is why Puzzle 1's boundary was $2/L$: on a quadratic the lemma is exact, the contraction factor of each eigen-direction is $|1 - \eta\lambda_i|$, and the direction with $\lambda_i = L$ crosses from contraction to expansion at exactly $\eta = 2/L$.

$f$ is $\mu$-strongly convex if $f - \tfrac\mu2\|\cdot\|^2$ is convex, equivalently $f(y) \ge f(x) + \langle \nabla f(x), y - x\rangle + \tfrac\mu2\|y - x\|^2$ — a lower quadratic — equivalently $\nabla^2 f \succeq \mu I$. Its consequences: a unique minimiser; $f(x) - f^\star \le \tfrac{1}{2\mu}\|\nabla f(x)\|^2$ (minimise the lower quadratic over $y$), so that a small gradient certifies a small suboptimality — the inequality that §6.4 generalises beyond convexity as Polyak–Łojasiewicz; and $\|x - x^\star\| \le \tfrac1\mu\|\nabla f(x)\|$.

The condition number $\kappa = L/\mu \ge 1$ is the ratio of the two, and it is the one number a practitioner should be able to estimate for their problem, because it governs every rate in §3: gradient descent needs $O(\kappa\log(1/\varepsilon))$ steps, momentum $O(\sqrt\kappa\log(1/\varepsilon))$, and nothing first-order does better. On a quadratic it is the ratio of extreme Hessian eigenvalues; on a least-squares problem it is the squared ratio of extreme singular values of the design matrix; on a logistic regression it is bounded by the same ratio times a factor from the curvature of the loss. On a deep network it is undefined in the strongly convex sense ($\mu = 0$ at best, negative curvature in general) and the useful analogues are the ones §7 introduces: the top Hessian eigenvalue, which plays $L$ (§7.3), and the smallest eigenvalue of the tangent kernel on the data, which plays $\mu$ (§7.2).

The practitioner's reading. A learning rate is a fraction of $1/L$ and you do not know $L$; everything in a training loop that touches the learning rate is a way of estimating or evading it. A warmup estimates it by starting small (§5.5). Adam evades it by normalising per coordinate (§4.4). Gradient clipping bounds the step where $L$ is locally large (§5.2). Line search measures it directly and is not used in deep learning because each measurement costs a forward pass on a stochastic objective. And the edge-of-stability phenomenon of §7.3 is the one behaviour none of the convex theory anticipates: on a network under gradient descent the top curvature rises along the trajectory until it meets $2/\eta$ and is held there by a feedback in the dynamics — not an intention — so that $L$ ends up set by the step rather than the step by $L$.

1.5 Where this touches a loss function already

• Least squares, ridge, logistic regression, softmax regression, SVM, lasso: convex in their weights. For each, a stationary point is the global optimum, the duality of §2 applies, and the rates of §3 are theorems about the training loop. The KL-penalised policy objective of RLHF (§2.4) is concave in the policy's probabilities on the simplex, and not in its logits — already for two actions, with no network in sight. Take zero reward, a uniform reference and $p = \sigma(z)$: the objective is $J(z) = -\mathrm{KL}(\mathrm{Ber}(\sigma(z))\,\|\,\mathrm{Ber}(\tfrac12))$, and its second derivative changes sign once the policy is confident:

§43 The KL-penalised objective is concave in the policy's probabilities and NOT in its logits: a two-action counter-example
      z     J(z) = -KL(Ber(sigmoid z) || Ber(1/2))     J''(z) closed form     J''(z) by central differences (h = 1e-4)
    0.0        -0.000000                                  -0.25000               -0.25000
    1.0        -0.110944                                  -0.10575               -0.10575
    1.5        -0.218096                                  -0.00705               -0.00705
    2.0        -0.327813                                  +0.05493               +0.05493
    3.0        -0.502282                                  +0.07750               +0.07750

$J''(2) = +0.055$: the sigmoid's own curvature overwhelms the KL's, the function is not concave in $z$, and a theorem proved over the simplex (§2.4's closed form) says nothing about the landscape a gradient method sees in the logits — let alone in the weights of a network that produces them. This is the first instance of the rule the whole piece runs on: the class is a property of the parametrisation, not of the problem. When one of these is the problem — a linear probe, a calibration head, a reward model's last layer — the question "did it converge" has a yes/no answer, and the §3 rates say how many steps a yes costs.

• Any network with a hidden layer: not convex, and not for a subtle reason. Permuting the hidden units of a trained network gives another network with the same function and the same loss; the midpoint of the two parameter vectors is, in general, a different function with a higher loss (§7.6 measures the barrier: zero between two runs from one initialisation, a midpoint loss five times the endpoints' between runs from two). A convex function's minimisers form a convex set; these do not. Beyond symmetry, Blum & Rivest (1992) show that deciding whether a three-node network can fit a dataset is NP-complete, so no polynomial algorithm minimises the training loss of every network on every dataset unless P = NP. Both facts are L1, and neither says anything about the typical instance, which is §7's subject.
• The parametrisation can be chosen for convexity. A one-hidden-layer network is non-convex in its weights but convex in the measure over hidden units (Bengio et al. 2006; Bach 2017) — which is the mean-field view of §7.2 and the reason global convergence theorems exist in the infinite-width limit. Phase retrieval is non-convex in $x$ and convex (a semidefinite program) in $xx^\top$; matrix completion is non-convex in the factors and convex in the matrix with a nuclear-norm penalty. In each case the convex formulation is the one with a theorem and the non-convex one is the one that runs, and §7.1 is about when the non-convex one inherits the theorem.
• A loss can be convex and still have $\kappa = \infty$ in practice. Logistic regression on linearly separable data has no minimiser — the loss tends to zero as $\|w\| \to \infty$ along any separating direction — and gradient descent runs forever, which is not a failure but the setting of §7.4, where which direction it runs along is a theorem.

Checkpoint exercise 1. The cross-entropy loss $-\log \operatorname{softmax}(z)_y$ is convex in the logits $z$. Show it (hint: it equals $\log\sum_j e^{z_j} - z_y$, and log-sum-exp is convex by the Hessian test or the §4 chord test). Then show that it stays convex in the weights $W$ of the layer that produces $z = W\phi(x)$ when the features $\phi(x)$ are fixed — the logits are affine in $W$, and a convex function of an affine map is convex — which is why a linear probe on frozen features is a convex problem with a unique minimum value. Finally explain why that convexity is lost once the layers that produce $\phi$ are trained jointly with $W$, using the permutation argument: permuting the hidden units gives a second minimiser, and the midpoint of the two is not one. The two facts together are the difference between fitting a probe and fine-tuning end to end. Exercise 2. For E1 with $\kappa = 100$, compute $\max_i|1 - \eta\lambda_i|$ at $\eta = 1/L$ and at $\eta = 1.99/L$ and check that both equal $0.99$ — the first from the softest direction ($\lambda = 1$), the second from the stiffest ($\lambda = 100$). Then explain why the $1.99/L$ row of §1 is nevertheless sixty-three times worse than the $1/L$ row after 200 steps, although the surviving amplitude decays at the same rate in both: $f = \tfrac12\sum_i\lambda_i x_i^2$ weights that amplitude by its curvature, and the two surviving directions differ in curvature by $\kappa$ (§47 prints the two shares, $\tfrac12\cdot 100\cdot 0.99^{400} = 0.898$ against $\tfrac12\cdot 1\cdot 0.99^{400} = 0.009$). The moral is the one §0 drew: a step just below the stability boundary is not a fast step, because the direction it leaves oscillating is the one the loss weights most.

2. Duality, KKT, and the conjugate

This section is on the theorist path and is the bridge to our Information Domain piece. A practitioner may read §2.3 for the support vectors and §2.4 for the one closed form that RLHF and DPO are built on, and skip the rest on a first pass.

2.1 The Lagrangian and weak duality

The constrained problem is $p^\star = \min_x f(x)$ subject to $g_i(x) \le 0$, $i = 1..m$, and $h_j(x) = 0$, $j = 1..p$, over a domain $\mathcal D$. Its Lagrangian attaches a price to each constraint:

and the dual function $q(\lambda, \nu) = \inf_{x \in \mathcal D} \mathcal L(x, \lambda, \nu)$ is concave in $(\lambda, \nu)$ whatever $f$ and $g$ are — it is an infimum of affine functions of the multipliers. Weak duality: $q(\lambda, \nu) \le p^\star$ for every $\lambda \ge 0$ and $\nu$, because for any feasible $x$, $\mathcal L(x, \lambda, \nu) \le f(x)$ (the penalty terms are $\le 0$). So the dual problem $d^\star = \max_{\lambda \ge 0, \nu} q(\lambda, \nu)$ is a convex problem whose value is a lower bound on the primal, for any primal, convex or not. The gap $p^\star - d^\star \ge 0$ is the duality gap.

Weak duality is what a lower bound is, operationally: §8.1's branch-and-bound certifies a global minimum by producing a lower bound that meets the best value found, and a Lagrangian relaxation is one of the standard ways to produce one. The gap can be enormous. For $\min\{-x^2 : -1 \le x \le 1\}$ the primal value is $-1$, but $\mathcal L(x, \lambda_1, \lambda_2) = -x^2 + \lambda_1(x - 1) + \lambda_2(-x - 1)$ is unbounded below in $x$ for every multiplier, so $q \equiv -\infty$ and $d^\star = -\infty$: the dual certifies nothing. Concave objectives over a box are the elementary hard case of global optimization (§8.1), and their dual gap is the elementary reason.

2.2 Strong duality, Slater, and when the gap closes

Strong duality is $p^\star = d^\star$. It holds for convex problems under a constraint qualification; the standard one is Slater's condition: $f, g_i$ convex, $h_j$ affine, and some strictly feasible point exists ($g_i(x) < 0$ for the non-affine $g_i$). Under it the dual optimum is attained; and when a primal optimiser $x^\star$ exists as well — Slater gives $p^\star = d^\star$ and dual attainment, not primal attainment, for which one adds a compact feasible set or a coercive $f$ — the primal–dual pair $(x^\star, \lambda^\star, \nu^\star)$ is a saddle point of the Lagrangian: $x^\star$ minimises $\mathcal L(\cdot, \lambda^\star, \nu^\star)$ and $(\lambda^\star, \nu^\star)$ maximises $\mathcal L(x^\star, \cdot, \cdot)$ — the minimax structure of §9 in its convex–concave, always-solvable form. Strong duality also holds for every linear program with a finite value, with no Slater (LP duality, 1947 — Appendix A); it can fail for convex problems without Slater (the standard example is $\min e^{-x}$ s.t. $x^2/y \le 0$, $y > 0$: $p^\star = 1$, $d^\star = 0$).

Here it is on a problem a practitioner has run. The bias-free soft-margin SVM $\min_w \tfrac12\|w\|^2 + C\sum_i \max(0, 1 - y_i\langle w, x_i\rangle)$ has the dual $\max_{0 \le \alpha \le C}\ \mathbf 1^\top\alpha - \tfrac12\alpha^\top Q\alpha$ with $Q_{ij} = y_i y_j\langle x_i, x_j\rangle$, and $w(\alpha) = \sum_i \alpha_i y_i x_i$. Run projected gradient ascent on the dual and evaluate both objectives along the way:

§5 Weak and strong duality on a bias-free soft-margin SVM: primal and dual objectives meet; KKT names the support vectors
  iter      1: dual = 0.628651   primal(w(a)) = 30.334389   gap = 2.97e+01
  iter     10: dual = 2.875073   primal(w(a)) = 19.140024   gap = 1.63e+01
  iter    100: dual = 12.766033   primal(w(a)) = 13.587708   gap = 8.22e-01
  iter   1000: dual = 13.408400   primal(w(a)) = 13.420371   gap = 1.20e-02
  iter  20000: dual = 13.412993   primal(w(a)) = 13.412993   gap = 3.55e-15
  support vectors (alpha > 1e-6): 17/60;  alpha = C (inside margin or misclassified): 15;  0 < alpha < C (exactly on the margin, y w.x = 1): 2
  max |y w.x - 1| over the on-margin set = 3.89e-15;  min y w.x over alpha = 0 points = 1.0389 (>= 1: complementary slackness)

At every iteration the dual value is below the primal value (weak duality), the two meet at the optimum to machine precision (strong duality: the problem is a convex quadratic with affine constraints), and — the useful part — the gap is a stopping criterion you can compute: at iteration 1000 the solution is certified to within $0.012$ of optimal without knowing the optimum. Every interior-point solver (§3.6) reports exactly this number.

2.3 KKT, and complementary slackness names the support vectors

At a primal–dual optimum of a convex problem with strong duality and differentiable functions, the Karush–Kuhn–Tucker conditions hold:

1. primal feasibility $g_i(x^\star) \le 0$, $h_j(x^\star) = 0$;
2. dual feasibility $\lambda^\star \ge 0$;
3. stationarity $\nabla f(x^\star) + \sum_i \lambda^\star_i \nabla g_i(x^\star) + \sum_j \nu^\star_j \nabla h_j(x^\star) = 0$;
4. complementary slackness $\lambda^\star_i\, g_i(x^\star) = 0$ for every $i$.

For a convex problem these are also sufficient. Condition 4 is the one with content: a constraint either binds ($g_i = 0$) or its price is zero ($\lambda_i = 0$). On the SVM the constraints are the margins, and the block above reads them off: 43 of the 60 points have $\alpha_i = 0$ and sit strictly outside the margin (their smallest margin is $1.039 > 1$); 15 have $\alpha_i = C$ and are inside it or misclassified; and exactly two have $0 < \alpha_i < C$ and sit exactly on the margin, $y_i\langle w, x_i\rangle = 1$ to fifteen digits. The decision boundary is determined by seventeen points — the support vectors — and the other 43 could be deleted without changing it. That is not a heuristic about SVMs; it is KKT condition 4 read as a statement about the data.

For a non-convex problem the KKT conditions are necessary at a local optimum under a constraint qualification (the Lagrange multiplier theorem) and not sufficient; a KKT point can be a saddle or a local maximum. §6 is the unconstrained version of that sentence.

2.4 The Fenchel conjugate: log-partition ↔ negative entropy, and the one closed form under RLHF

The Fenchel conjugate of $f$ is $f^*(y) = \sup_x\ \langle y, x\rangle - f(x)$: the largest gap between a linear function with slope $y$ and $f$. It is convex always (a sup of affine functions), and for convex closed $f$, $f^{**} = f$ (Fenchel–Moreau). The conjugate is the engine under Lagrangian duality — the dual function of a linearly constrained problem is a conjugate in disguise — and under the two identities that tie this piece to our Information Domain one.

Identity 1 (log-sum-exp ↔ negative entropy). On the simplex $\Delta$, the conjugate of the negative entropy $-H(p) = \sum_i p_i\log p_i$ is the log-partition function: $(-H)^*(\theta) = \log\sum_i e^{\theta_i} =: A(\theta)$, with the sup attained at $p = \operatorname{softmax}(\theta)$. Equivalently $A(\theta) = \max_{p \in \Delta}\ \langle\theta, p\rangle + H(p)$. That is the variational characterisation of the softmax our Information Domain's §9.8 stated; here it is a conjugate pair, which means it comes with a method: maximise $\langle\theta, p\rangle + H(p)$ over the simplex by mirror descent (§4.2) and watch it find the softmax.

§6 Fenchel conjugate of log-sum-exp is negative entropy; the KL-penalised objective has a Gibbs closed form (W41 bridge)
  A(theta) = log sum exp(theta) = 2.440190;  max_p <theta,p> + H(p) by exponentiated gradient = 2.440190;  argmax p = [0.2369 0.0871 0.0321 0.6439];  softmax(theta) = [0.2369 0.0871 0.0321 0.6439]
  KL-penalised argmax by EG = [0.866  0.0762 0.006  0.0519]; closed form pi exp(r/beta)/Z = [0.866  0.0762 0.006  0.0519]; optimal value 1.459336 vs beta log Z = 1.459336

Identity 2 (the KL-penalised maximisation has a Gibbs solution). For a reference distribution $\pi$, reward $r$ and temperature $\beta > 0$,

which is Identity 1 with the entropy replaced by a relative entropy, i.e. the conjugate of $\mathrm{KL}(\cdot\|\pi)$. The second line of §6 checks both the maximiser and the value. This is the closed form on which the RLHF objective of our Information Domain §10.3 rests, and the step on which DPO (Rafailov et al. 2023) is built: substituting $r = \beta\log(p^\star/\pi) + \beta\log Z$ into the Bradley–Terry preference likelihood eliminates the reward model. Grade: the identity is L1 and holds per prompt in the tabular case, over the simplex; "a policy network trained by gradient ascent on the penalised objective reaches $p^\star$" is a statement about a non-convex problem — non-convex already in the logits of a two-action tabular policy, §1.5's §43, before any network — and is L3; and the identity says nothing about the estimation of $r$, which is where the practical difficulty sits. The conjugate structure also gives the mirror-descent view of the KL-penalised updates (PPO's penalty form, the objective GRPO carries): a KL-penalised step is a proximal step in the Bregman geometry of §4.2, which is why its closed form is multiplicative. PPO's clipped form is a different object, §9.2.

Identity 3 (Fisher is the Hessian of KL). $\nabla^2_\theta\,\mathrm{KL}(p_{\theta_0}\|p_\theta)\big|_{\theta = \theta_0} = F(\theta_0)$, the Fisher information. This is the identity under natural gradient, and §4.3 checks it numerically in two parametrisations and uses it.

Checkpoint exercise 3. Derive the SVM dual of §2.2 from the Lagrangian: introduce slacks $\xi_i \ge 1 - y_i\langle w, x_i\rangle$, $\xi_i \ge 0$, write $\mathcal L$, minimise over $w$ and $\xi$ in closed form, and show the box constraint $0 \le \alpha_i \le C$ is what is left. Exercise 4. Show that $\max_p \langle r, p\rangle - \beta\mathrm{KL}(p\|\pi)$ at $\beta \to 0$ puts all mass on $\arg\max r$ and at $\beta \to \infty$ returns $\pi$, and compute the KL between $p^\star$ and $\pi$ as a function of $\beta$ on the four-state example of §6.

3. Rates and lower bounds: what a guarantee is

3.1 The oracle model, and what "optimal" means for a method

Nemirovski & Yudin (1983) made the question precise. A first-order oracle returns $f(x)$ and $\nabla f(x)$ (or a subgradient) at a query point; a method is any rule that chooses the next query from the answers so far; the complexity of a class $\mathcal F$ of functions is the smallest number of queries that guarantees $f(x_T) - f^\star \le \varepsilon$ for every $f \in \mathcal F$. A rate is an upper bound on that number achieved by a particular method; a lower bound is a proof that no method does better on the worst function in the class. A method is optimal for a class when its rate matches the class's lower bound up to constants.

Three things follow from the definition that are routinely forgotten. A rate is a worst-case statement: the function you have may be far from the worst in its class, and gradient descent on it may beat its bound by a large factor (§7 below shows a factor of $1.5$ for a reason that is a one-line computation). A lower bound is a statement about a function in the class, constructed to defeat every method; it says nothing about yours. And a class is a choice: the same method has a different rate on $\{$convex, $L$-smooth$\}$, on $\{\mu$-strongly convex, $L$-smooth$\}$, and on $\{L$-smooth$\}$ with no convexity, and the three are $O(1/T)$, $O((1-1/\kappa)^T)$ and "$O(1/T)$ for $\min_t\|\nabla f\|^2$", which are not comparable because they bound different quantities.

3.2 Gradient descent: the two convex rates, and the condition number as the exponent

Fast path · stop 3 of 14. Next stop: §3.3.

Theorem (smooth convex). If $f$ is convex and $L$-smooth, gradient descent with $\eta = 1/L$ satisfies $f(x_T) - f^\star \le \dfrac{L\|x_0 - x^\star\|^2}{2T}$.

Sketch. The descent lemma gives $f(x_{t+1}) \le f(x_t) - \tfrac{1}{2L}\|\nabla f(x_t)\|^2$; the first-order condition at $x_t$ against $x^\star$ gives $f(x_t) - f^\star \le \langle\nabla f(x_t), x_t - x^\star\rangle$; combining the two with the identity $\|x_{t+1} - x^\star\|^2 = \|x_t - x^\star\|^2 - \tfrac2L\langle\nabla f(x_t), x_t - x^\star\rangle + \tfrac1{L^2}\|\nabla f(x_t)\|^2$ shows that $\|x_t - x^\star\|$ is non-increasing and that $\sum_t (f(x_t) - f^\star) \le \tfrac L2\|x_0 - x^\star\|^2$; since $f(x_t)$ is non-increasing, the last term is at most the average. (Bubeck 2015, Thm 3.3; Nesterov 2018, Thm 2.1.14.)

Theorem (smooth strongly convex). If in addition $f$ is $\mu$-strongly convex, gradient descent with $\eta = 1/L$ satisfies $\|x_T - x^\star\|^2 \le (1 - 1/\kappa)^T\|x_0 - x^\star\|^2$ and $f(x_T) - f^\star \le (1 - 1/\kappa)^T\,\tfrac L2\|x_0 - x^\star\|^2$; with $\eta = 2/(L + \mu)$ the factor improves to $\big(\tfrac{\kappa - 1}{\kappa + 1}\big)^{2T}$ on the distance.

Sketch. Strong convexity and smoothness together give $\langle \nabla f(x) - \nabla f(y), x - y\rangle \ge \tfrac{\mu L}{\mu + L}\|x - y\|^2 + \tfrac1{\mu + L}\|\nabla f(x) - \nabla f(y)\|^2$ (Nesterov's Thm 2.1.12); expand $\|x_{t+1} - x^\star\|^2$ and apply it. On a quadratic every direction contracts by $|1 - \eta\lambda_i|$ per step, and $\max_i|1 - \lambda_i/L| = 1 - \mu/L$: the bound is the worst direction's contraction, and $f$, being quadratic in the distance, contracts by its square.

So the number of steps to reach accuracy $\varepsilon$ is $O(\kappa\log(1/\varepsilon))$: the condition number is the exponent's denominator, and doubling $\kappa$ doubles the steps. Here are the two theorems on E1, with heavy ball and Nesterov's method beside them for §3.3:

§7 Rates on a quadratic: GD, heavy ball and Nesterov at kappa = 10, 100, 1000, 10,000 — iterations to f - f* < 1e-8, against the theorems' upper bounds
  kappa     GD iters   GD bound (1-1/kappa)^2t    HB iters   Nesterov iters   NAG bound (1-1/sqrt kappa)^t
      10         69              91                     18             25                  52
     100        703            1036                     71             88                 204
    1000       6976           11370                    263            291                 730
   10000      69417          123943                    953            935                2536
  (a bound is an upper bound: the worst direction holds only 1/d of the initial energy here, so GD beats its bound by a factor ~1.5)

Read the first three columns against the theorem. Gradient descent's iterations grow by a factor of ten per decade of $\kappa$ — linear in $\kappa$, as the exponent says — and the bound is above the measurement at every row by a factor between $1.3$ and $1.8$. The factor is not slack in the theorem; it is the start. The bound assumes all of $\|x_0 - x^\star\|^2$ can sit in the slowest direction, and E1's start spreads it evenly over fifty directions, so the slowest one begins with a fiftieth of the energy and needs $\log(50)/(2\cdot 1/\kappa) \approx 2\kappa$ fewer steps. A reader who estimates $\kappa$ for their problem and finds the bound pessimistic by a constant has found the constant; a reader who finds it pessimistic by a power of $\kappa$ has the wrong class.

3.3 Momentum is a theorem: heavy ball and Nesterov, $\sqrt\kappa$ for $\kappa$

Fast path · stop 4 of 14. Next stop: §4.4.

Two methods add a memory of the previous step:

• Heavy ball (Polyak 1964): $x_{t+1} = x_t - \alpha\nabla f(x_t) + \beta(x_t - x_{t-1})$.
• Nesterov's accelerated gradient (1983): $y_t = x_t + \beta(x_t - x_{t-1})$, $x_{t+1} = y_t - \alpha\nabla f(y_t)$ — the gradient is evaluated at the extrapolated point.

Theorem (heavy ball on a quadratic). With $\alpha = 4/(\sqrt L + \sqrt\mu)^2$ and $\beta = q^2$, $q = \tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}$, heavy ball on a strongly convex quadratic, started with zero momentum, satisfies $\|x_T - x^\star\| \le \big(1 + (1 + q)T\big)\,q^T\,\|x_0 - x^\star\|$; equivalently, for every $\delta > 0$ there is a $C_\delta$ with $\|x_T - x^\star\| \le C_\delta\,(q + \delta)^T\|x_0 - x^\star\|$. The condition number enters as its square root. (Polyak 1964; the proof is the spectral radius of the $2\times2$ companion matrix of each eigen-direction, which is $q$ at those constants.) The prefactor is not a constant, and the form the theorem is usually quoted in — a $T$-independent $C$ in front of $q^T$ — is false: at the two extreme eigenvalues the companion matrix has a double root, so the iterate along those directions is $(1 + ct)\,q^t x_0$, with the factor in front of $q^t$ growing linearly:

§42 Heavy ball's rate has a prefactor that grows with T: at the extreme eigenvalues the companion matrix has a double root, so x_T = (1 + c T) q^T x_0, not C q^T x_0
  kappa = 100: alpha = 0.03306, beta = q^2 = 0.66942, q = 0.81818; double root +q at lam = mu, -q at lam = L; x_{-1} = x_0
      T    |x_T|/|x_0| at lam = mu    (1 + (1-q) T) q^T    at lam = L     (1 + (1+q) T) q^T    max over 2001 lam in [mu, L]     q^T alone
     10       3.7885e-01           3.7885e-01       2.5786e+00      2.5786e+00          2.5786e+00           1.3443e-01
    100       3.6972e-08           3.6972e-08       3.5237e-07      3.5237e-07          3.5237e-07           1.9274e-09
   1000       1.2937e-85           1.2937e-85       1.2874e-84      1.2874e-84          1.2874e-84           7.0766e-88

At $T = 100$ the stiff direction's iterate is $183$ times $q^{100}$, the soft direction's $19$ times, and at $T = 10$ the stiff direction is at $2.6$ times its start — momentum at these constants overshoots before it contracts. None of this touches the complexity: $(1 + 2T)q^T \le \varepsilon$ still holds at $T = O(\sqrt\kappa\log(1/\varepsilon))$, because the logarithm of a polynomial is absorbed by the logarithm of $1/\varepsilon$; it touches the statement, and a statement is what a theorem is. On non-quadratic strongly convex functions heavy ball with these constants can fail to converge — Lessard, Recht & Packard (2016) give a one-dimensional counter-example — so its $\sqrt\kappa$ rate is an L1 statement about quadratics and an L3 one about everything else.

Theorem (Nesterov, smooth convex). With $\alpha = 1/L$ and the momentum sequence $\beta_t = (\lambda_{t} - 1)/\lambda_{t+1}$, $\lambda_{t+1} = (1 + \sqrt{1 + 4\lambda_t^2})/2$, $f(x_T) - f^\star \le \dfrac{2L\|x_0 - x^\star\|^2}{(T+1)^2}$ (Nesterov 2018 Thm 2.2.2 gives $4L\|x_0 - x^\star\|^2/(T+2)^2$; the constant depends on the variant). (Nesterov, strongly convex.) With $\alpha = 1/L$ and constant $\beta = \tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}$, $f(x_T) - f^\star \le \big(1 - \tfrac1{\sqrt\kappa}\big)^T\big(f(x_0) - f^\star + \tfrac\mu2\|x_0 - x^\star\|^2\big)$. Both hold for every smooth (strongly) convex function, not only quadratics — that is the difference from heavy ball, and the reason the extrapolated gradient is not a cosmetic change. The proofs go through an estimate sequence (Nesterov 2018 §2.2.1) or, more transparently, a potential function $\phi_t = t^2(f(x_t) - f^\star) \cdot c + \|z_t - x^\star\|^2$ that is shown non-increasing (Bansal & Gupta 2019 give the four-line version).

The last three columns of §7 are the theorem on E1. Heavy ball and Nesterov's method grow by a factor of about $\sqrt{10} \approx 3.2$ per decade of $\kappa$, against gradient descent's $10$; at $\kappa = 10{,}000$ they need $953$ and $935$ steps against $69{,}417$. The Nesterov bound is again above the measurement by a constant ($2.1$ to $2.7$), for the same reason as before plus the $f(x_0) - f^\star + \tfrac\mu2\|x_0 - x^\star\|^2$ factor.

The practitioner's reading of "momentum". Momentum in a training loop is heavy ball ($\beta = 0.9$, $\alpha$ a learning rate), applied to a stochastic, non-convex objective. The theorem above says: on a strongly convex quadratic, with the right $\alpha$ and $\beta$ tied to $\kappa$, it is $\sqrt\kappa$ faster. It does not say that $\beta = 0.9$ accelerates anything — the acceleration constants are $\beta = ((\sqrt\kappa-1)/(\sqrt\kappa+1))^2$, which is $0.9$ at $\kappa \approx 1{,}500$ — and in the stochastic regime of §5 the role of $\beta$ is different: with gradient noise, momentum at a fixed effective step mainly averages the noise over $\sim 1/(1-\beta)$ steps and does not change the noise floor (§5.1; Kidambi et al. 2018 show heavy ball cannot beat plain SGD's rate in the stochastic least-squares setting). So the grade of "momentum helps my transformer": L1 on the quadratic model of its local curvature, L3 as a statement about the run. What is L1 without qualification is that the heavy-ball update's effective learning rate at a constant gradient is $\alpha/(1 - \beta)$ — ten times $\alpha$ at $\beta = 0.9$ — which is the first thing to remember when comparing learning rates across optimizers.

3.4 Nesterov's lower bound: no first-order method beats $1/T^2$

The acceleration is not a trick that could be improved on by a cleverer method; it is optimal, and the proof is a single function.

Theorem (Nesterov 2018, Thm 2.1.7). For every $t$ with $1 \le t \le (d-1)/2$ there is an $L$-smooth convex function $f$ on $\mathbb R^d$ such that any first-order method whose iterates lie in $x_0 + \operatorname{span}\{\nabla f(x_0), \dots, \nabla f(x_{t-1})\}$ satisfies

The function is the chain $f_{2t+1}(x) = \tfrac L4\big(\tfrac12(x_1^2 + \sum_{i<2t+1}(x_i - x_{i+1})^2 + x_{2t+1}^2) - x_1\big)$, a tridiagonal quadratic whose gradient at a vector supported on the first $k$ coordinates is supported on the first $k+1$: starting from $0$, after $t$ gradient queries the method has only seen $t$ coordinates of a $(2t+1)$-dimensional problem whose solution $x^\star_i = 1 - i/(2t+2)$ lives on all of them, and the suboptimality of the best point on the first $t$ coordinates is the bound. The dimension grows with $t$ — the theorem is about a family of functions, one for each horizon — and that is the right way to run it:

§8 Nesterov's worst-case function f_{2t+1}: no first-order method beats 3 L ||x0 - x*||^2 / (32 (t+1)^2) at step t, and Nesterov's method is within a constant of it
     t    d=2t+1   GD gap f(x_t)-f*   NAG gap     lower bound 3LR^2/(32(t+1)^2)   GD/bound   NAG/bound   NAG upper bound 4LR^2/(t+2)^2
     1       3         0.046875     0.046875            0.020508               2.29        2.29          0.388889
     2       5         0.040690     0.057292            0.015914               2.56        3.60          0.381944
     5      11         0.031630     0.031762            0.009151               3.46        3.47          0.286848
    10      21         0.024915     0.017577            0.005300               4.70        3.32          0.190025
    20      41         0.018985     0.009321            0.002871               6.61        3.25          0.111603
    50     101         0.012792     0.003915            0.001208              10.59        3.24          0.049559
   100     201         0.009324     0.002003            0.000614              15.18        3.26          0.025696
  (the function depends on t: at step t the method has only touched coordinates 1..t of a 2t+1-dimensional chain, whatever it did)

Both methods are above the lower bound at every $t$, as they must be. Nesterov's method sits at a constant $3.3\times$ the bound from $t = 5$ onward — it is optimal up to that constant — while gradient descent's ratio grows like $t$, which is exactly $O(1/t)$ against $O(1/t^2)$. The right-hand column is the method's own upper bound, which it satisfies with room. Three things the table says that the theorem's statement does not: the lower bound is attained up to a constant, so there is no better first-order method to look for on this class; the gap between gradient descent and the optimum is a factor of $t$, which at the $10^5$ steps of a training run would be enormous if the class applied; and the class does not apply to training a network — the lower bound is for the worst smooth convex function, and §6.2 gives the non-convex analogue, where the optimal rate is a different quantity altogether.

3.5 Nonsmooth: subgradient $1/\sqrt T$, proximal $1/T$, FISTA $1/T^2$

Remove smoothness and keep convexity. The subgradient method $x_{t+1} = x_t - \eta_t g_t$, $g_t \in \partial f(x_t)$, with the horizon-aware constant step $\eta = D/(G\sqrt T)$ ($D$ a bound on $\|x_0 - x^\star\|$, $G$ on the subgradients) satisfies $\min_{s \le T} f(x_s) - f^\star \le DG/\sqrt T$ (Bubeck 2015, Thm 3.2). With the decreasing step $\eta_t = D/(G\sqrt t)$, which needs no horizon, the same bound holds for the best iterate up to a $\log T$ factor — $\sum_t\eta_t^2$ is $D^2\log T/G^2$ — and the log is removed by reporting the average of the last half of the iterates or a $\sqrt t$-weighted average: the rate is a property of the pair (schedule, iterate reported), not of the method alone, a distinction §5.4 returns to for SGD. The $1/\sqrt T$ rate is optimal for the class of $G$-Lipschitz convex functions — Nemirovski & Yudin's second lower bound. It is also not a descent method: a subgradient step can increase $f$, which is why the guarantee is on the best iterate. Each halving of the error costs four times the steps.

But most nonsmooth losses in machine learning are structured: $F(x) = f(x) + h(x)$ with $f$ smooth and $h$ simple — $\ell_1$ for the lasso, an indicator for a constraint set, the nuclear norm for low rank. The proximal gradient method $x_{t+1} = \operatorname{prox}_{\eta h}(x_t - \eta\nabla f(x_t))$, with $\operatorname{prox}_{\eta h}(v) = \arg\min_u h(u) + \tfrac1{2\eta}\|u - v\|^2$, handles $h$ exactly at each step (for $\ell_1$ the prox is soft-thresholding; for an indicator it is projection; for the nuclear norm it is singular-value soft-thresholding) and recovers the smooth rates: $O(1/T)$ at $\eta = 1/L$, and $O(1/T^2)$ with Nesterov's extrapolation, which is FISTA (Beck & Teboulle 2009). Here are the three on a lasso with $n = 100$, $d = 50$, a five-sparse truth:

§9 Nonsmooth: subgradient O(1/sqrt t) vs proximal gradient O(1/t) vs FISTA O(1/t^2) on a lasso problem
  t =    10: subgradient (best)  1.031e-01   proximal  1.364e-02   FISTA  1.410e-03
  t =   100: subgradient (best)  9.048e-03   proximal  0.000e+00   FISTA  0.000e+00
  t =  1000: subgradient (best)  2.548e-03   proximal  0.000e+00   FISTA  0.000e+00
  t =  2000: subgradient (best)  1.825e-03   proximal  0.000e+00   FISTA  0.000e+00
  support of the lasso solution: 5 nonzeros of 50 (truth 5); L = 2.923

The subgradient method is still at $1.8\times10^{-3}$ after $2{,}000$ steps, with the $1/\sqrt t$ shape ($\times 0.28$ per decade, against the $0.32$ of the exponent); the two proximal methods have the exact optimum, to the last digit, by step 100. The second fact is a theorem of its own and the reason to prefer the prox, with two hypotheses that the §11 map carries. Under a non-degeneracy condition — $-\nabla f(x^\star)$ lies in the relative interior of $\partial h(x^\star)$, which for the lasso says the inactive columns' correlations with the residual are strictly below the threshold $\tau$ — the proximal method identifies the support of the solution after finitely many steps, the five nonzero coordinates here; and under restricted strong convexity on that support (the active columns have full column rank) the problem there is a smooth strongly convex quadratic on which it converges linearly (Hare & Lewis 2004 on identifiable surfaces; Liang, Fadili & Peyré 2014 for FISTA). Without the non-degeneracy, finite identification is no longer guaranteed; without the restricted curvature, the rate after identification is sublinear. The subgradient method never identifies anything; it oscillates across the kink forever at a rate set by its step.

Where the practitioner meets this. Weight decay is, to first order, the prox of $\tfrac\lambda2\|\cdot\|^2$: the exact proximal step is $w/(1 + \eta\lambda)$, AdamW's decoupled decay multiplies by $1 - \eta\lambda$ instead, and the two agree to $O((\eta\lambda)^2)$ — $0.900$ against $0.909$ at $\eta\lambda = 0.1$ — so AdamW is a first-order approximation to a proximal step and not the step itself (Zhuang, Liu, Cutkosky & Orabona 2022 is the paper on the exact-prox variant; §5.6's equilibrium argument needs only the first order):

§50 AdamW's decoupled decay w <- (1 - eta lambda) w is the FIRST-ORDER approximation of the exact proximal step w / (1 + eta lambda) for (lambda/2)||w||^2: they differ at order (eta lambda)^2
      eta*lambda     AdamW factor 1 - x     exact prox factor 1/(1+x)     difference     x^2 (leading term)
       0.001            0.99900                0.99900              0.00000         0.00000
       0.010            0.99000                0.99010              0.00010         0.00010
       0.100            0.90000                0.90909              0.00909         0.01000
       0.500            0.50000                0.66667              0.16667         0.25000

The rest of the sentence holds as stated. A projection onto a norm ball after each step is a prox. Magnitude pruning is not a prox of anything convex (it is the prox of the $\ell_0$ penalty, which is non-convex), and the §8.5 argument about why sparse training lacks guarantees starts there. And the soft-thresholding operator is the mechanism by which the $\ell_1$ relaxation of §8.5 produces exact zeros, which an $\ell_2$ penalty never does.

3.6 Newton, quasi-Newton, and why LP, QP and SDP are "solved"

Everything so far queried a first-order oracle. Newton's method $x_{t+1} = x_t - \nabla^2 f(x_t)^{-1}\nabla f(x_t)$ queries a second-order one and is affine-invariant: reparametrise $x \mapsto Ax$ and the iterates transform the same way, so the condition number disappears from its rate. Locally it converges quadratically — the error squares each step — under a Lipschitz Hessian; globally it needs damping or a trust region (Nocedal & Wright ch. 3–4); and its cost is $O(d^3)$ per step for the solve, which at $d = 10^9$ is the end of the discussion. Quasi-Newton methods (BFGS, L-BFGS) build a secant approximation to the inverse Hessian from gradient differences, converge superlinearly on smooth problems, and are the default for deterministic medium-scale optimization; in the stochastic regime of §5 their secant equations are corrupted by noise and they are rarely used. The deep-learning descendants of Newton are the preconditioners of §4 — diagonal (Adam), Kronecker-factored (K-FAC, Shampoo), spectral (Muon) — each a structured approximation to $\nabla^2 f^{-1}$ or to the Fisher that costs $O(d)$ to $O(d^{3/2})$ per step instead of $O(d^3)$.

Interior-point methods are Newton's method applied to a barrier: replace the constraint $g_i(x) \le 0$ by the penalty $-\tfrac1t\log(-g_i(x))$, solve the unconstrained problem by Newton for increasing $t$, and the central path it traces converges to the constrained optimum with a duality gap of exactly $m/t$ (Boyd & Vandenberghe ch. 11). Nesterov & Nemirovski (1994) showed that for self-concordant barriers the number of Newton steps to reduce the gap by a factor $\varepsilon$ is $O(\sqrt{\nu}\log(1/\varepsilon))$ with $\nu$ the barrier parameter — polynomial in the problem size and independent of the condition number. That theorem, with Karmarkar's 1984 algorithm before it, is why linear, quadratic, second-order-cone and semidefinite programs are "solved" problems: a solver returns a primal–dual pair whose duality gap is its certificate (§2.2), in a number of iterations that is tens, not thousands — a numerical certificate: the solver stops at a residual tolerance, $10^{-8}$ say, and turning that into a mathematically validated one takes a further step, such as rounding the dual to an exactly feasible point or running the residual computation in interval arithmetic, which is what the SDP certificates of §8.2 go through before they count as proofs. It is also why "relax to an SDP" is the strategy of §8.2 — Lasserre's hierarchy turns a polynomial optimization problem into a sequence of SDPs, each of which interior point solves to a duality-gap tolerance, and the hierarchy's cost is in the size of the SDP, not in its conditioning.

Checkpoint exercise 5. For E1 at $\kappa = 100$, compute the heavy-ball constants $\alpha, \beta$ of §3.3 and show that the effective step $\alpha/(1-\beta)$ is $\approx 0.5 \cdot (2/L) \cdot \ldots$ — more precisely, show $\alpha/(1-\beta) = 1/\sqrt{\mu L}$, the geometric mean of $1/L$ and $1/\mu$, and explain why that is the natural step for a method that cannot see the eigenvalues. Exercise 6. Run gradient descent on the chain function $f_{2t+1}$ from $x_0 = 0$ by hand for $t = 1, 2$ and verify that $x_t$ is supported on the first $t$ coordinates. Exercise 7. Show that soft-thresholding $\operatorname{sign}(v)\max(|v| - \tau, 0)$ is the prox of $\tau\|\cdot\|_1$ by solving the one-dimensional problem $\min_u \tau|u| + \tfrac12(u - v)^2$ in the three cases $v > \tau$, $|v| \le \tau$, $v < -\tau$.

4. Beyond Euclid: the geometry of the step

Every method in §3 took a step in the direction $-\nabla f$. That direction is special only because the Euclidean norm is: the gradient is the steepest-descent direction for the $\ell_2$ norm, and a different norm gives a different direction, a different method, and — in the right geometry — a different rate. This section is one idea repeated five times, and by the end of it Adam, Shampoo and Muon are the same idea with three norms.

4.1 Steepest descent under a norm

The steepest-descent direction for a norm $\|\cdot\|$ at $x$ is the solution of $\min_{\|d\| \le 1}\langle \nabla f(x), d\rangle$: the unit vector (in that norm) along which the linearisation of $f$ falls fastest. For $\ell_2$ it is $-\nabla f/\|\nabla f\|_2$. For $\ell_\infty$ it is $-\operatorname{sign}(\nabla f)$: every coordinate moves by the same amount — sign descent, which is Adam with its averages switched off (§4.4). For $\ell_1$ it is a single coordinate — coordinate descent. And for a matrix gradient $G$ under the spectral norm $\|\cdot\|_2$ (largest singular value), it is $-UV^\top$ where $G = U\Sigma V^\top$: the orthogonal polar factor of the gradient, with every singular value set to one. Here are the three on one $6\times4$ gradient with singular values spread over four orders of magnitude: