Convergence rate and complexity for convex minimization problem

Question

In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization problem:

$$\min f(x),\quad x \in \mathbb R^n$$

The error at iteration $k$ is denoted by $r_k=||x_k-x^*||$ where $x_k$ is the approximate solution at iteration $k$ and $x^*$ is the true solution. Quadratic rate: $r_{k+1} \leq c r_k^2$.

The corresponding complexity estimate depends on a double logorithm of the desired accuracy: $\ln\ln\frac{1}{\epsilon}$. Why is this the case?

Answer 1

Unlike the first two cases on page 36, case 3, "Quadratic rate", has a bound on $r_{k+1}$ that depends on $r_{k}$ rather than $k$.

We have

$r_{k+1} \le cr_{k}^{2}$

$r_{k+1} \le c(cr_{k-1}^{2})^{2}$

$r_{k+1} \le c(c(cr_{k-2}^{2})^{2})^{2}$

$\vdots$

$r_{k+1} \le c^{2^{k}-1} r_{0}^{2^{k+1}}$

Unfolding this, you can see that $O(\log \log 1/\epsilon)$ iterations are needed to get $r$ down to less than $\epsilon$.