Lecture Notes

Rates of Convergence

By Akshay Agrawal. Last updated Jan. 22, 2019.

The rate of convergence of an iterative optimization algorithm quantifies how quickly the algorithm converges to a fixed point. Let $x_1, x_2, x_3, \ldots$ be the iterates produced by the iteration $x_{k+1} = f(x_k)$, with initial iterate $x_0$. Let $x^\star$ denote the fixed point obtained by iterating $f$. Let $e_0, e_1, e_2$ be the errors of the iteration, that is, $e_k = \norm{f(x_k) - x^\star}$.

Suppose there exists a constant $c < 1$ and an exponent $p$ such that for sufficiently large $k$,

$$e_{k} \leq c e_{k-1}^p.$$

If $p = 1$, the iteration is said to converge linearly to its fixed point; if $p = 2$, it converges quadratically. Additionally, if $p < 1$, the iteration is said to converge sublinearly, and if $p > 1$ is converges superlinearly.

It is instructive to unroll the recursion in the above inequality. If $p = 1$, then we have

$$e_{k} \leq c^k e_0.$$

For this reason, linear convergence is sometimes referred to as geometric convergence. Note also that for $p=1$, a log-linear plot of error versus iterations decays linearly, and obtaining an accuracy on the order of $\epsilon$ requires $O(\log (1/ \epsilon))$ iterations.

If $p= 2$, then

$$e_{k} \leq O(c^{2^k -1}).$$

Even though this convergence is termed quadratic, a log-linear plot of quadratically convergent errors versus iterations actually decays as an exponential. Obtaining an $\epsilon$-suboptimal iterate in a quadratically convergent regime requires $O(\log \log (1/\epsilon))$ iterations.

References

Lloyd Trefethen and David Bau. Numerical Linear Algebra.