Convergence Rates

Rates name how fast error shrinks: halving the leftovers, dividing by steps, or squaring the accuracy. The name predicts your compute budget.

On a log-error plot the sublinear curve crawls while linear descends steadily and quadratic plunges past 1e-6 in three squarings

Why Does This Exist?

"Gradient descent converges" promises nothing about Friday. Sublinear $O(1/k)$ needs a million steps for $10^{-6}$ ; linear $0.5^k$ needs 20; quadratic needs 3 squarings from $0.1$ . The rate is the budget, and picking Newton versus gradient descent without it is gambling.

Rates classify error recursions: sublinear $e_{k+1} \leq e_k - c\,e_k^2$ -ish, linear $e_{k+1} \leq \rho\,e_k$ , superlinear $\rho_k \to 0$ , quadratic $e_{k+1} \leq C\,e_k^2$ . They rest on smooth convex geometry and explain the variants in gradient descent variants.

The one idea you need first

Error $e_k = f(x_k) - f^\star$ (or $\|x_k - x^\star\|$ ) tracked per iteration. Strong convexity ( $\mu > 0$ ) plus smoothness ( $L$ ) gives linear gradient descent with $\rho = 1 - \mu/L$ ; bare convexity gives $O(1/k)$ ; Newton near a regular root gives quadratic.

Think of It Like This

Draining three tubs

Sublinear tub drains through a straw that narrows as it empties: fast at first, endless at the end. Linear tub drains a fixed fraction per minute: predictable halves. Quadratic tub doubles its drain width each minute: a few gulps and dry.

Condition number $\kappa = L/\mu$ is the tub shape: stretched tubs drain linearly but slowly. Where it stops: tubs are deterministic, while stochastic drains add noise floors that no rate outruns without variance fixes.

How It Actually Works

Gradient descent on $L$ -smooth convex objectives gives $f(x_k) - f^\star \leq \|x_0-x^\star\|^2/(2\alpha k)$ , sublinear. Add $\mu$ -strong convexity: linear with $1 - \mu/L$ per step ( $\kappa$ steps per digit). Accelerated gradient lifts smooth convex to $O(1/k^2)$ . Newton: quadratic once inside the basin ( $e_{k+1} \sim e_k^2$ ), e.g. $0.1 \to 0.01 \to 0.0001$ . Lower bounds certify tightness: no first-order method beats $O(1/k^2)$ on smooth convex objectives generally.

Worked example

Target $10^{-6}$ . Sublinear $1/k$ : $k = 10^6$ steps. Linear $0.5^k$ : $0.5^{20} \approx 9.5 \times 10^{-7}$ , so 20 steps (and $0.5^{19}$ is still above target, so 20 is exact). Quadratic from $0.1$ with $C = 1$ : $0.1 \to 0.01 \to 10^{-4} \to 10^{-8}$ , 3 squarings to pass the target. Gradient descent on $(x-3)^2$ ( $\mu = L = 2$ , $\kappa = 1$ ) with $\alpha = 1/L$ : exact in 1 step, the degenerate best case of linear with $\rho = 0$ .

Code

Standard library only: three tiny computations that budget three regimes. Quote them before choosing the optimizer.

1import math2
3print(math.ceil(1 / 1e-6))  # -> 1000000  sublinear steps to 1e-64print(math.ceil(math.log(1e-6, 0.5)))  # -> 20  linear steps at 0.5^k5e = 0.16for i in range(3):7    e = e**2  # quadratic squaring8print(f"{e:.0e}")  # -> 1e-08  after 3 squarings

Watch Out For

Expecting linear rates without strong convexity

Plain convex objectives (logistic regression without regularization, Lasso) give sublinear theory, yet teams budget linear and declare a stall at $10^{-3}$ . The algorithm is fine; the geometry never promised more.

Add strong convexity (regularize), accelerate ( $O(1/k^2)$ ), or budget sublinear. If error falls like $1/k$ , the theory already told you.

Quoting quadratic from outside the basin

Newton far from the root diverges or cycles; quadratic speed starts only inside a neighborhood that shrinks with nonlinearity. Damped phases precede it, and skipping them explodes.

Globalize (line search, trust region) then enjoy local quadratic speed. If Newton jumps wildly, you are outside, not broken.

The Quick Version

Sublinear $O(1/k)$ : smooth convex default; a million steps per $10^{-6}$ .
Linear $\rho^k$ : needs strong convexity; 20 steps at $\rho = 0.5$ .
Quadratic $e^2$ : Newton inside the basin; 3 squarings from 0.1 to pass the target.
Acceleration lifts smooth convex to $O(1/k^2)$ ; nothing first-order beats it generally.
Condition number sets linear speed; regularize or precondition stretched bowls.
Stochastic noise floors need variance reduction before rates apply.