Optimization

Condition Number and Convergence

The ratio of largest to smallest curvature controls how fast first-order methods converge and why ill-conditioned problems crawl.

What the condition number measures

For a smooth strongly convex objective, the condition number kappa = L / m is the ratio of the largest curvature (Lipschitz constant of the gradient, L) to the smallest curvature (strong convexity constant, m). Geometrically, level sets are ellipsoids whose axis-length ratio is sqrt(kappa). Large kappa means long, narrow valleys that are hard to descend.

Effect on gradient descent

Kronos motion — materials first

Gradient descent on a strongly convex quadratic converges linearly with rate (kappa - 1)/(kappa + 1) per step. When kappa is large this rate is close to 1, so progress per step is tiny and the iterates zig-zag across the narrow valley. The number of iterations to reach a target accuracy scales linearly with kappa.

How methods improve the dependence

Momentum and Nesterov acceleration reduce the iteration count to scale with sqrt(kappa), a large gain for ill-conditioned problems.
Newton's method rescales by the inverse Hessian, making convergence essentially independent of kappa near the optimum.
Preconditioning transforms the problem to reduce kappa before applying a first-order method.

Preconditioning

A preconditioner is a matrix that approximately whitens the curvature, replacing kappa with a much smaller effective condition number. Diagonal preconditioning (scaling each variable) is cheap and often helps; adaptive optimizers like Adam apply a data-driven diagonal preconditioner automatically. For linear systems, preconditioned conjugate gradient depends on the preconditioned condition number.

Practical implications

Ill-conditioning is the most common reason first-order optimization is slow. Feature normalization, batch normalization, and careful parameterization all reduce the condition number of the training objective. Recognizing that slow convergence often signals ill-conditioning, rather than a fundamentally hard problem, points to the right remedy.

python

import numpy as np
kappa = np.linalg.cond(H)     # ratio of largest to smallest eigenvalue
# GD linear rate ~ (kappa-1)/(kappa+1); accelerated ~ (sqrt(kappa)-1)/(sqrt(kappa)+1)

Diagnosing conditioning explains why an optimizer stalls and points to normalization or preconditioning as the fix, a routine concern in large model training.