Gradient Descent on a Quadratic Bowl

Minimize a simple quadratic to build intuition for step size, convergence rate, and why conditioning matters.

The setup

Minimize f(x) = (1/2) x^T A x - b^T x with A symmetric positive definite. The gradient is A x - b, zero at the solution x* = A^-1 b. Gradient descent steps downhill: x_new = x - eta (A x - b).

Step size

Convergence hinges on the learning rate eta relative to the eigenvalues of A. It is stable when eta < 2/lambda_max. Too small and it crawls; too large and it oscillates and diverges. The optimal fixed rate is 2/(lambda_min + lambda_max).

import numpy as np
A=np.array([[3.0,0.0],[0.0,1.0]]); b=np.array([3.0,1.0])
x=np.zeros(2); eta=0.3
for i in range(60):
    g=A@x-b
    x=x-eta*g
print(np.round(x,5))   # -> [1,1], the minimizer

Conditioning

The convergence factor per step is (kappa-1)/(kappa+1), where kappa = lambda_max/lambda_min is the condition number. A well-conditioned bowl (kappa near 1) converges in a few steps; an ill-conditioned, elongated valley (large kappa) zig-zags slowly across the narrow direction. This single fact motivates preconditioning, momentum, and conjugate gradients.

Beyond the quadratic

Every smooth function looks quadratic near a minimum (its Hessian is the local A), so this analysis governs the last phase of any smooth optimization - including neural-network training near convergence. Momentum and adaptive methods are largely tricks to beat the (kappa-1)/(kappa+1) rate.