Gradient Methods, Conditioning, and Preconditioning

For f(x)=½xᵀHx with positive definite H, each Hessian eigen-direction evolves on its own. The error along the eigenvector belonging to λᵢ is multiplied by 1−ηλᵢ at every step, so the method converges along that direction only while that factor stays inside the convergent range. That puts a ceiling on η, set by the largest eigenvalue, at the curvature 2/(step size).

The ceiling is not a safety margin that real training respects from below. Full-batch gradient descent on neural networks has been measured against it, by Cohen and four co-authors, at ICLR in 2021. The sharpness climbs until it reaches the threshold and then balances there: “In this regime, the maximum eigenvalue of the training loss Hessian hovers just above the numerical value 2 / (step size), and the training loss behaves non-monotonically over short timescales, yet consistently decreases over long timescales.”

A separate group restated the same regime independently at ICML in 2022 — “sharpness stabilizes around 2/LR and loss goes up and down across iterations, yet still with an overall downward trend” — and proved that two GD variants provably enter it.

The quadratic model is not being contradicted here. Training walks to the edge the quadratic model draws and then hovers just above it, where the quadratic model predicts divergence and the loss keeps falling anyway.

Gradient descent updates x ← x−η∇f(x). The gradient gives the steepest local Euclidean decrease, while η decides how far the method trusts that direction. On a curved landscape, the best step can differ sharply across directions. A single scalar learning rate must compromise between steep and shallow axes. Conditioning measures this imbalance. Poor conditioning creates zig-zag paths, slow progress, and sensitivity to step size even on a simple convex quadratic.

The price of that compromise has been measured, and it is not small. Take a large image classifier, leave the architecture and the objective alone, and change only the scale of the inputs each layer sees, by normalizing them. Ioffe and Szegedy did that in 2015, and their abstract reports the result: “Applied to a state-of-the-art image classification model, Batch Normalization achieves the same accuracy with 14 times fewer training steps, and beats the original model by a significant margin.” An ensemble of batch-normalized networks reached 4.9% top-5 validation error on ImageNet, and 4.8% test error, given as 4.82% in the ICML version.

The same abstract records the mechanical symptom. The method “allows us to use much higher learning rates” — which is what a step size looks like once it is no longer held hostage by the steepest direction in the problem.

Ioffe and Szegedy attributed the gain to reduced internal covariate shift. A paper at NeurIPS in 2018 showed that explanation does not hold, and that batch normalization instead makes the optimization landscape significantly smoother. The fourteenfold saving stands under either reading. What it buys is geometry, not capacity.

These methods may look similar in code but act through different mechanisms. The difference between the last two has now been settled on wall-clock time rather than argued from iteration counts.

MLCommons ran the inaugural AlgoPerf: Training Algorithms competition and announced the results on 1 August 2024: “The first iteration of the AlgoPerf: Training Algorithms competition attracted 18 submissions (with 15 being scorable) from 10 different teams. Scoring involved over 4000 individual training runs across the 14 workloads used in the benchmark.”

The external-tuning winner was Meta's Distributed Shampoo, which “provides an impressive 28% faster model training compared to the baseline” and took a $25,000 prize. The self-tuning winner, Schedule Free AdamW, delivered an “8% faster neural network training process”.

The competition results paper draws the conclusion: “The winning submission in the external tuning ruleset, using Distributed Shampoo, demonstrates the effectiveness of non-diagonal preconditioning over popular methods like Adam, even when compared on wall-clock runtime.” Preconditioning that models curvature across coordinates beat diagonal adaptive scaling on fixed hardware. It paid for its matrices every step and still finished first.

Let f(x,y)=½(100x²+y²). Shewchuk works the same manoeuvre on a small system in a 1994 Carnegie Mellon report. Its section on preconditioning opens: “Preconditioning is a technique for improving the condition number of a matrix.” Then it reports what the cheapest version of it actually buys.

Use targeted interventions instead of changing every hyperparameter at once. The probes below are real instruments with published readings, not metaphors.

The full Hessian spectrum of ImageNet-scale networks has been estimated with Hessian-vector products, by three authors at ICML in 2019. What they found is this lesson's anisotropy, counted: “the vast majority (> 99.99% of eigenvalues being close to 0)”, with a handful of large outliers separated from that bulk. They track the outliers with a scale-invariant ratio, ζ(t) := λ1(∇²L(θt))/λK(∇²L(θt)) — a condition number under another name — and state the consequence plainly: “For all directions where λi is small with respect to λ1, we expect convergence to be slow”.

The outliers are not a curiosity of the tail. The same authors also computed the spectrum of the gradient covariance, which shows how the energy of the mini-batch gradients is spread, for a Resnet-32 trained on CIFAR-10. Without batch normalization, “almost 99% of the energy is in the top few subspaces”, and those subspaces “mostly coincide” with the Hessian's outlier directions. Nearly all of the stochastic-gradient signal lives inside the few steep directions that already cap the step size.

Their summary carries the diagnosis and the intervention in one sentence: “in non-batch normalized networks, we observe the rapid appearance of large isolated eigenvalues in the spectrum, along with a surprising concentration of the gradient in the corresponding eigenspaces. In batch normalized networks, these two effects are almost absent.”

A least-squares model with two features can be computed exactly, which makes every step checkable. The five deliveries are invented: distance 1, 2, 3, 4 and 5 km, parcel weight 500, 1,500, 1,000, 2,500 and 2,000 g, and delivery time 12, 14, 15, 22 and 19 minutes. The model predicts centred time from centred distance and weight with loss f(w) = ½ · mean squared error. Every figure below was computed in double precision.

In a positive definite quadratic, the spectral condition number κ=λmax/λmin compares the steepest and shallowest curvature directions. A large κ forces conservative steps for stability along the steep directions, which leaves slow movement along the shallow ones. Condition number depends on parameterization. Rescaling variables can dramatically improve optimization without changing the represented problem.

The cost of ignoring that has been audited, with certified numbers attached. In 1967 Longley appraised least-squares programs from the point of view of the user, in the Journal of the American Statistical Association, building on a macroeconomic least-squares problem whose design matrix is so collinear that regression programs disagreed on the answer. Cleve Moler records what became of it: “The Longley data set of labor statistics was one of the first used to test the accuracy of least squares computations.” The R Core Team documents the same 16 observations, taken from 1947 to 1962 on 7 variables, as “A macroeconomic data set which provides a well-known example for a highly collinear regression.”

NIST's Statistical Reference Datasets archive now certifies it: 1 response variable, 6 predictors, 16 observations, classified at the “Higher Level of Difficulty”. B0 = −3482258.63459582. Residual standard deviation 304.854073561965. R² = 0.995479004577296. The figures are published so that software can be checked against them, and the archive's stated purpose is improving “the accuracy of statistical software by providing reference datasets with certified computational results”.

A badly conditioned matrix is not an abstraction about convergence rates. It is a problem on which two correct-looking programs return different numbers, and someone had to certify which ones were right.