Condition Number in Optimization
The condition number, the ratio of largest to smallest curvature, predicts how slowly gradient methods converge and why preconditioning helps.
Defining the condition number
For a smooth objective the condition number kappa at a minimum is the ratio of the largest to the smallest eigenvalue of the Hessian, kappa = lambda_max / lambda_min. It measures how different the curvature is across directions. A condition number near 1 means the landscape looks like a round bowl; a large condition number means a long narrow valley, steep across and shallow along.
Why it controls convergence
Gradient descent on a quadratic converges geometrically with a rate that worsens as kappa grows: the number of iterations to reach a given accuracy scales roughly with kappa. Intuitively, a step size safe for the steep direction is far too small for the shallow one, so the iterates bounce across the narrow valley while creeping along it. Ill-conditioned problems (large kappa) are the classic reason plain gradient descent is slow.
- kappa near 1: round bowl, gradient descent converges fast
- kappa large: narrow valley, gradient descent zig-zags and stalls
- Momentum reduces the dependence from kappa to roughly sqrt(kappa)
- Newton's method makes convergence independent of kappa locally
Remedies
Several techniques attack ill-conditioning. Momentum and accelerated gradient methods improve the iteration count from order kappa to order sqrt(kappa). Preconditioning multiplies the gradient by a matrix that approximates the inverse Hessian, reshaping the landscape toward a round bowl; a diagonal preconditioner is exactly what adaptive methods like Adagrad and RMSprop apply. Newton and quasi-Newton methods use curvature directly and are essentially insensitive to kappa near the solution.
Practical significance
Recognizing an ill-conditioned problem explains many training pathologies: slow progress, sensitivity to the learning rate, and zig-zagging. Simple fixes such as feature normalization reduce the condition number before optimization even begins, which is why standardizing inputs so dramatically speeds up training. In simulation-based engineering optimization, poor scaling among physical variables of very different magnitudes is a frequent, easily fixed cause of sluggish convergence.