Optimization: Quick recap

01 Loss surfaces and gradient descent

Gradient descent: $x_{k+1} = x_k - \eta\nabla f(x_k)$ , with learning rate (step size) $\eta > 0$ .
$-\nabla f(x)$ is the direction of steepest descent (Cauchy–Schwarz), and $\nabla f(x)$ is perpendicular to the level set through $x$ .
On $f = \tfrac{\lambda}{2}x^2$ : $x_k = (1 - \eta\lambda)^k x_0$ ; it converges if and only if $0 < \eta < 2/\lambda$ , and oscillates (but converges) for $1/\lambda < \eta < 2/\lambda$ .
With several curvatures, one step size must satisfy $\eta < 2/\lambda_{\max}$ ; the flat directions then shrink only by $1 - \eta\lambda_{\min}$ per step.
The best fixed step on $\tfrac12(\lambda_1 x_1^2 + \lambda_2 x_2^2)$ is $2/(\lambda_1 + \lambda_2)$ , with factor $(\lambda_2 - \lambda_1)/(\lambda_2 + \lambda_1)$ per step.
A large ratio of curvatures (condition number $\kappa$ ) causes zig-zag across the valley and a slow crawl along it.
If gradient descent converges, the limit is a stationary point; on a nonconvex loss the start decides which one.
Stop on a small gradient norm plus a step budget; a small change of $f$ alone can stop far from the minimum.

02 Convexity, smoothness, conditioning

$f$ is convex when chords lie on or above the graph; for differentiable $f$ , when $f(y) \ge f(x) + \nabla f(x)^\top(y - x)$ (tangents below); for twice-differentiable $f$ , when $\nabla^2 f \succeq 0$ everywhere.
For a convex function every local minimum is global, and a point with $\nabla f = 0$ is a global minimizer.
Least squares and logistic regression are convex; neural-network losses are not, because permuting hidden units gives separate minimizers whose midpoint is worse.
$L$ -smooth: $\nabla f$ is $L$ -Lipschitz ( $\nabla^2 f \preceq LI$ for convex $C^2$ functions). $\mu$ -strongly convex: $\nabla^2 f \succeq \mu I$ . Condition number $\kappa = L/\mu$ ; for a quadratic, the ratio of the extreme eigenvalues.
Descent lemma: $f(y) \le f(x) + \nabla f(x)^\top(y - x) + \tfrac L2\|y - x\|^2$ ; a step $1/L$ decreases $f$ by at least $\|\nabla f\|^2/(2L)$ .
PL inequality: $\|\nabla f(x)\|^2 \ge 2\mu(f(x) - f^\star)$ ; strong convexity implies it, but some nonconvex functions satisfy it too.
Feature scaling is a diagonal preconditioner: it changes $\kappa$ from about $s_{\max}^2/s_{\min}^2$ to about 1 for uncorrelated features, but cannot remove correlations ( $\kappa = (1 + |\rho|)/(1 - |\rho|)$ ).

03 GD rates and line search

On a quadratic with eigenvalues in $[\mu, L]$ , gradient descent multiplies the error component along each eigenvector $q_i$ by $1 - \eta\lambda_i$ ; the total factor is $\rho(\eta) = \max(|1 - \eta\mu|, |1 - \eta L|)$ .
Gradient descent on a quadratic converges from every start exactly when $0 < \eta < 2/\lambda_{\max}$ ; the steep direction sets this limit.
The best fixed step is $2/(\mu + L)$ with factor $(\kappa - 1)/(\kappa + 1)$ : about $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ steps for accuracy $\varepsilon$ . The step $1/L$ needs about twice as many.
For $L$ -smooth, $\mu$ -strongly convex $f$ , the step $1/L$ gives $f(x_k) - f^\star \le (1 - \mu/L)^k(f(x_0) - f^\star)$ (descent lemma + PL).
For $L$ -smooth convex $f$ , the step $1/L$ gives $f(x_k) - f^\star \le L\|x_0 - x^\star\|^2/(2k)$ : a sublinear rate, and $x_k$ may converge much more slowly.
Armijo: $\varphi(\alpha) \le \varphi(0) + c_1\alpha\varphi'(0)$ rejects steps that are too long. Backtracking ( $\alpha_0, \tau\alpha_0, \dots$ ) stops with $\alpha \ge \min(\alpha_0, 2\tau(1 - c_1)/L)$ , without knowing $L$ .
Wolfe = Armijo + curvature ( $\varphi'(\alpha) \ge c_2\varphi'(0)$ , or $|\varphi'(\alpha)| \le c_2|\varphi'(0)|$ for strong Wolfe), with $0 < c_1 < c_2 < 1$ ; usually $c_1 = 10^{-4}$ , $c_2 = 0.9$ .
The curvature condition guarantees $y^\top s > 0$ , which keeps the BFGS matrix positive definite.

04 Momentum and Nesterov

Heavy ball: $x_{k+1} = x_k - \eta\nabla f(x_k) + \beta(x_k - x_{k-1})$ . For a constant gradient the step approaches $\eta g/(1 - \beta)$ : ten times larger for $\beta = 0.9$ .
Momentum is a low-pass filter: gradient parts that keep their sign add up, parts that flip sign cancel.
On a quadratic each eigen-direction follows $c_{k+1} = (1 + \beta - \eta\lambda)c_k - \beta c_{k-1}$ , with roots of $z^2 - (1 + \beta - \eta\lambda)z + \beta$ ; complex roots have size exactly $\sqrt\beta$ .
Polyak's parameters $\eta = 4/(\sqrt L + \sqrt\mu)^2$ , $\beta = ((\sqrt\kappa - 1)/(\sqrt\kappa + 1))^2$ give the factor $(\sqrt\kappa - 1)/(\sqrt\kappa + 1)$ : about $\sqrt\kappa$ steps per digit instead of $\kappa$ .
Heavy ball on a quadratic is stable exactly when $0 \le \beta < 1$ and $\eta\lambda_{\max} < 2(1 + \beta)$ .
Heavy ball's acceleration is proven only for quadratics; on some smooth strongly convex functions it cycles (Lessard–Recht–Packard).
Nesterov's method takes the gradient at a look-ahead point. It gives $f(x_k) - f^\star \le 2L\|x_0 - x^\star\|^2/(k+1)^2$ for convex $f$ and about $(1 - 1/\sqrt\kappa)^k$ for strongly convex $f$ , and it is not monotone.
No method that moves only along past gradients can beat these rates by more than a constant factor (lower bounds); CG is optimal for one fixed quadratic.

05 SGD and batch size

A minibatch gradient is unbiased, $\mathbb E[g] = \nabla f(x)$ , with variance $\sigma^2/B$ .
Far from $x^\star$ all examples agree on the direction; near $x^\star$ (the region of confusion) they disagree, and the noise does not shrink.
With a constant step $\eta \le 1/L$ on a $\mu$ -strongly convex, $L$ -smooth $f$ : $\mathbb E\|e_k\|^2 \le (1 - \eta\mu)^k\|e_0\|^2 + \eta\sigma^2/(\mu B)$ . SGD converges linearly to a noise ball, not to $x^\star$ .
In 1D mean estimation the exact floor is $\eta\sigma^2/(2 - \eta)$ ; a step $1/(k+1)$ gives the running mean and the error $\sigma^2/k$ .
To reach $x^\star$ , the steps must satisfy the Robbins–Monro conditions $\sum\eta_k = \infty$ and $\sum\eta_k^2 < \infty$ ; $\eta_k = c/(k_0 + k)$ with $c\mu > 1$ gives $\mathbb E\|e_k\|^2 = O(1/k)$ .
Linear scaling rule: multiply the learning rate by $c$ when the batch grows by $c$ . It holds while $B \ll B_{\text{noise}}$ and the step stays below the curvature limit, with warmup.
The simple noise scale $B_{\text{simple}} = \operatorname{tr}\Sigma/\|G\|^2$ estimates the critical batch size; above it, extra examples per step are mostly wasted.
Per example gradient, SGD's cost to a fixed accuracy does not depend on $n$ ; GD's grows like $n$ . On large datasets SGD wins.

06 AdaGrad, RMSProp, Adam, AdamW

An EMA $m_t = \beta m_{t-1} + (1-\beta)g_t$ remembers about $1/(1-\beta)$ steps; with $m_0 = 0$ it is biased by the factor $1 - \beta^t$ .
AdaGrad divides by the root of the sum of squared gradients (steps decay like $1/\sqrt t$ ); RMSProp uses an EMA instead, without bias correction (first step $10\eta$ ).
Adam: $m_t$ and $v_t$ are EMAs of $g$ and $g^2$ ; $\hat m_t = m_t/(1-\beta_1^t)$ , $\hat v_t = v_t/(1-\beta_2^t)$ ; $\theta_t = \theta_{t-1} - \eta\,\hat m_t/(\sqrt{\hat v_t} + \varepsilon)$ . Defaults $10^{-3}$ , $(0.9, 0.999)$ , $10^{-8}$ .
Adam's first step is about $\eta\operatorname{sign}(g_1)$ in every coordinate; the step is invariant to the gradient scale and is typically at most about $\eta$ .
Adam is a diagonal preconditioner: it removes bad scaling along the coordinate axes, not along rotated directions.
A large $\varepsilon$ turns Adam into momentum SGD with step $\eta/\varepsilon$ ; $\beta_2 = 0.95$ gives a shorter memory than $0.999$ and reacts faster to changes in the gradient scale.
L2 regularization equals weight decay for plain SGD, but inside Adam it is divided by $\sqrt{\hat v}$ , so weights with large gradients are decayed less. AdamW decays every weight by $1 - \eta\lambda$ per step.

07 Schedules, warmup and clipping

A schedule gives $\eta(t)$ . Warmup + cosine: $\eta = \eta_{\max}t/W$ for $t < W$ , then $\eta_{\min} + \tfrac12(\eta_{\max} - \eta_{\min})(1 + \cos\pi p)$ with $p = (t - W)/(T - W)$ .
WSD = warmup, a stable phase at $\eta_{\max}$ , and a short cooldown (linear or 1−sqrt); a 10–20% cooldown matched cosine in language-model experiments.
SGD with a constant step stays in a noise ball whose expected loss is $\eta\sigma^2/(2(2 - \eta\lambda))$ per direction, proportional to $\eta$ ; decaying $\eta$ shrinks it, which is why the loss drops sharply in the cooldown.
A cosine planned for $T$ cannot be stopped early or extended; WSD can be branched from any checkpoint of its stable phase.
Warmup lets training reach regions of lower sharpness before $\eta$ is large, protects Adam's early second-moment estimate, and is needed with the linear scaling rule for large batches.
A learning-rate range test increases $\eta$ until the loss blows up; pick a value clearly below the blow-up, which is near $2/\lambda_{\max}$ on a quadratic.
Clipping by global norm, $\min(1, c/\|g\|)\,g$ , keeps the direction, changes only large gradients, and caps the step length at $\eta c$ ; it helps on $(L_0, L_1)$ -smooth losses, $\|\nabla^2 f\| \le L_0 + L_1\|\nabla f\|$ .

08 Lagrange multipliers, KKT, duality

At a constrained minimum of $f$ on $h(x) = 0$ , a level set of $f$ is tangent to the constraint, so $\nabla f(x^\star) + \nu\nabla h(x^\star) = 0$ (if $\nabla h(x^\star) \ne 0$ ). This also holds at constrained maxima.
The Lagrangian is $\mathcal L(x, \lambda, \nu) = f_0 + \sum_i \lambda_i f_i + \sum_j \nu_j h_j$ , with $\lambda_i \ge 0$ for constraints $f_i(x) \le 0$ and $\nu_j$ of any sign for $h_j(x) = 0$ .
A multiplier is a price: under strong duality, $\partial p^\star/\partial u_i = -\lambda_i^\star$ when constraint $i$ is relaxed to $f_i(x) \le u_i$ .
KKT conditions: primal feasibility, dual feasibility $\lambda \ge 0$ , complementary slackness $\lambda_i f_i(x) = 0$ , and stationarity $\nabla_x \mathcal L = 0$ .
For a convex problem, KKT points are global minimizers. Under Slater's condition (a strictly feasible point), KKT is also necessary.
The dual function $g(\lambda, \nu) = \inf_x \mathcal L$ is concave and $g \le p^\star$ (weak duality). For a feasible $x$ , $f_0(x) - g(\lambda, \nu)$ bounds $f_0(x) - p^\star$ .
The projection onto the probability simplex is $x_i = \max(y_i - \nu, 0)$ , with one threshold $\nu$ chosen so that the entries sum to 1.
The lasso dual is $\max_\theta \tfrac12\|b\|^2 - \tfrac12\|b - \theta\|^2$ s.t. $\|A^\top\theta\|_\infty \le \lambda$ ; at the optimum $\theta^\star = b - Ax^\star$ .

09 Proximal methods and ADMM

The proximal operator is $\operatorname{prox}_{\eta g}(v) = \arg\min_u g(u) + \frac{1}{2\eta}\|u - v\|^2$ : move toward small $g$ without going far from $v$ .
The prox of $\lambda|\cdot|$ with step $\eta$ is soft thresholding, $\operatorname{sign}(v)\max(|v| - \eta\lambda, 0)$ ; it maps a whole interval to exactly 0, which is why the lasso is sparse.
The prox of the indicator of a closed convex set is the Euclidean projection, so projected gradient is a special case of proximal gradient.
Proximal gradient: $x^+ = \operatorname{prox}_{\eta g}(x - \eta\nabla f(x))$ ; with $\eta \le 1/L$ it minimizes an upper bound of $F = f + g$ , so $F$ never goes up.
For convex $f$ and $g$ , $x^\star$ minimizes $f + g$ if and only if $x^\star = \operatorname{prox}_{\eta g}(x^\star - \eta\nabla f(x^\star))$ , for any $\eta > 0$ .
With step $1/L$ : ISTA has $F(x_k) - F^\star \le L\|x_0 - x^\star\|^2/(2k)$ ; FISTA has $2L\|x_0 - x^\star\|^2/(k + 1)^2$ at the same cost per step, but it is not monotone.
ADMM for $\min f(x) + g(z)$ s.t. $x = z$ alternates an $x$ -minimization, a prox step for $z$ , and a dual update $u \leftarrow u + x - z$ ; for the lasso the $z$ -step is the soft threshold.

10 Newton, BFGS and Gauss–Newton

The Newton step solves $\nabla^2 f(x)\,\Delta x = -\nabla f(x)$ : it jumps to the minimum of the local quadratic model. On a strictly convex quadratic it needs one step, for any condition number.
Near a minimizer with $\nabla^2 f(x^\star) \succ 0$ and a Lipschitz Hessian, Newton converges quadratically: $\|e_{k+1}\| \le (M/\mu)\|e_k\|^2$ , so the correct digits double. The result is local.
Damped Newton adds a line search; when the Hessian is not positive definite, the Newton step can go to a maximum or a saddle, so one modifies the Hessian or uses a trust region.
Newton's method is affine invariant: rescaling or rotating the variables does not change its iterates (in the new coordinates). Gradient descent is not affine invariant.
Quasi-Newton methods impose the secant condition $H_{k+1}y_k = s_k$ . The BFGS update $H^+ = (I - \rho sy^\top)H(I - \rho ys^\top) + \rho ss^\top$ stays positive definite exactly when $y^\top s > 0$ , which a Wolfe line search guarantees.
L-BFGS keeps the $m$ newest pairs $(s_i, y_i)$ and computes $-H_k g$ with the two-loop recursion in $O(md)$ time and $2md$ memory.
Gauss–Newton solves $J^\top J\,h = -J^\top r$ : Newton for $\tfrac12\|r\|^2$ without the term $\sum_i r_i\nabla^2 r_i$ . It is quadratic for zero residuals, linear for small ones, and can fail for large ones.
Levenberg–Marquardt solves $(J^\top J + \lambda I)h = -J^\top r$ ; small $\lambda$ gives Gauss–Newton, large $\lambda$ a short gradient step $-\nabla F/\lambda$ , and the gain ratio adapts $\lambda$ .

11 Saddles, sharpness and stability

At a stationary point the Hessian eigenvalues decide: all positive is a strict local minimum, all negative a strict maximum, mixed signs a saddle; a zero eigenvalue makes the test undecided ( $x^3$ , $x^4$ , monkey saddle).
GD with step $1/L$ on an $L$ -smooth function bounded below guarantees only $\min_{i<k}\|\nabla f(x_i)\|^2 \le 2L(f(x_0) - f_{\inf})/k$ : a small gradient, not a minimum.
Near a strict saddle, the component along a direction with $\lambda < 0$ grows by $1 + \eta|\lambda|$ per step; GD converges to a strict saddle only from a measure-zero set of starts, and escape takes about $\log(1/\delta)/\log(1 + \eta|\lambda_{\min}|)$ steps.
Newton's method jumps to any stationary point, including saddles; saddle-free Newton uses $|H|$ .
A Hessian-vector product $Hv = \tfrac{d}{dt}\nabla f(x + tv)|_{t=0}$ costs a small constant times one gradient; power iteration or Lanczos on HVPs gives the top eigenvalue without forming $H$ .
The sharpness $S = \lambda_{\max}(\nabla^2 L)$ sets the stability limit: GD can stay at a minimum only if $S \le 2/\eta$ . In practice $S$ rises (progressive sharpening) to about $2/\eta$ and hovers there (edge of stability) while the loss keeps decreasing.
Sharpness depends on the parametrization (Dinh et al.), so "flat minima generalize" is a heuristic; SAM minimizes $\max_{\|\varepsilon\| \le \rho} L(w + \varepsilon)$ using the gradient at $w + \rho\nabla L/\|\nabla L\|$ .

12 K-FAC, Shampoo and Muon

Optimizers differ by their preconditioner: the identity (gradient descent), a diagonal (Adam), the full curvature (Newton), or per-layer Kronecker factors (K-FAC, Shampoo) in between.
K-FAC approximates the Fisher block of a linear layer, $\mathbb{E}[(aa^\top)\otimes(\delta\delta^\top)]$ , by $A \otimes D$ with $A = \mathbb{E}[aa^\top]$ and $D = \mathbb{E}[\delta\delta^\top]$ ; it is exact for one example, and its step $D^{-1}\nabla_W A^{-1}$ needs only two small inverses.
Steepest descent under a norm: $\arg\min_\Delta[\langle g, \Delta\rangle + \tfrac{L}{2}\|\Delta\|^2] = -(\|g\|_*/L)\arg\max_{\|t\| = 1}\langle g, t\rangle$ . The $\ell_2$ norm gives gradient descent, $\ell_\infty$ gives sign descent.
Under the spectral norm the steepest direction is $-UV^\top$ for $G = U\Sigma V^\top$ (Theorem 2): keep the singular vectors and set all singular values to 1. The spectral and nuclear norms are dual.
Newton–Schulz iterations $X^+ = aX + b(XX^\top)X + c(XX^\top)^2X$ act on each singular value with the polynomial $p(\sigma) = a\sigma + b\sigma^3 + c\sigma^5$ and leave the singular vectors unchanged.
Muon = momentum, then five quintic Newton–Schulz steps, applied to the 2D hidden weights only; its singular values end in a band of about $[0.7, 1.2]$ , not exactly 1. The factor $0.2\sqrt{\max(m, n)}$ matches AdamW's update RMS.
Shampoo steps along $L^{-1/4}GR^{-1/4}$ ; without accumulation this equals $UV^\top$ . SOAP runs Adam in the eigenbasis of Shampoo's factors.
As of 2025–2026, matrix optimizers (Shampoo, Muon, SOAP) are the fastest well-tested methods, but with carefully tuned baselines their speedup over AdamW shrinks with model size (about $1.4\times$ at 0.1B to $1.1\times$ at 1.2B parameters).