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 to 1e-6 in five steps

Why Does This Exist?

"Gradient descent converges" promises nothing about Friday. Sublinear $O(1/k)$ needs 1,000,000 steps for $10^{-6}$ ; linear $0.5^k$ needs 20; quadratic needs 5. The rate is the budget, and picking Newton versus gradient 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 assume the smooth setup in calculus optimization 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: $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 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. Quadratic from $0.1$ with $C = 1$ : $0.1 \\to 0.01 \\to 10^{-4} \\to 10^{-8}$ , 3 steps past the start. 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

1import math2
3print(math.ceil(1 / 1e-6))  # -> 1000000 sublinear4print(math.ceil(math.log(1e-6, 0.5)))  # -> 20 linear5e = 0.16for i in range(4):7    e = e**2  # quadratic8print(f"{e:.0e}")  # -> 1e-08 after 3 squarings

Three tiny computations budget three regimes. Quote them before choosing the optimizer.

Watch Out For

Expecting linear rates without strong convexity

Plain convex (logistic without regularization, Lasso) gives sublinear theory, yet teams budget linear and declare 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 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. If Newton jumps wildly, you are outside, not broken.

The Quick Version

Sublinear $O(1/k)$ : smooth convex default; 1M 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 past 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.