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


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

  • $\begingroup$ 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! $\endgroup$ – John Smith Sep 1 '18 at 16:24

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.