# Convergence rate and complexity for convex minimization problem

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?

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$.

• First, it seems to me: $r_{k+1} \leq c^{2^{k+1}-1}r_0^{2^{k+1}}$. So if we let $r_{k+1} \leq c^{2^{k+1}-1}r_0^{2^{k+1}} \leq \epsilon$, then we have $k \geq \ln(\frac{\ln (c\epsilon)}{\ln(cr_0)})/\ln2 -1$ given $cr_0 < 1$. What is the next step? Thanks! – John Smith Sep 1 '18 at 16:24