Assessing tradeoffs: complexity vs precision - Mines Nancy

It is useful to express convergence results as complexity bounds, i.e., given a precision $\varepsilon$ , provide a bound on the number of iterations $K$ needed to reach that bound, in the worst case scenario.

Example 1

Consider gradient descent in the smooth convex case. We have from the theorem;

f(x^{(K)}) - f(x^\star) \leq \frac{L}{2K}\Vert x^{(0)} - x^\star\Vert_2^2

(1)

Let $\varepsilon > 0$ be the desired precision after $K$ iterations. Then, if one wants $f(x^{(K)}) - f(x^\star) \leq \varepsilon$ , this can be satisfied if that

\frac{L}{2K}\Vert x^{(0)} - x^\star\Vert_2^2\leq \varepsilon

(2)

and thus whenever

K \geq\frac{L}{2\varepsilon}\Vert x^{(0)} - x^\star\Vert_2^2

(3)

Hence, the number of iterations is a linear function of the inverse precision $\frac{1}{\varepsilon}$ .

We conclude this chapter with a few important takeaways.

6.4 Assessing tradeoffs: complexity vs precision