Are there examples of functions with Nesterov's convergence bound between convex quadratic and strongly convex cases?

Question

Are there examples of strongly convex functions for which the complexity bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s complexity bound for strongly convex case $$\sqrt{1 - \frac{1}{\sqrt{k}}}$$ and worse than Nesterov’s quadratic bound $$1 - \frac{1}{\sqrt{k}}$$? Here $k = \frac{L}{m}$ is the condition number for $L$-smooth $m$-strongly convex functions.

EDIT: Nesterov's book has a strongly convex objective that is "bad" for any first order method. However, this "bad" function might not be the worst function for a particular method. In particular, it might not be the worst function for Nesterov's scheme.

For the Nesterov's scheme, we know that, as long as the objective is strongly convex, we are guaranteed to converge at a rate of at least $$\sqrt{1 - \frac{1}{\sqrt{k}}}.$$ We also know that, for strongly convex quadratic functions, we are guaranteed to converge at a rate of at least $$1-\frac{1}{\sqrt{k}}.$$ The question now is: can we find a "bad" strongly convex function for which Nesterov's scheme converges slower than $1-\frac{1}{\sqrt{k}}$ and faster than $\sqrt{1 - \frac{1}{\sqrt{k}}}$. This "bad" function should be parametrized by $k$, its condition number.

Answer 1

For your specific question, I do not really understand, what you are after, but be aware that this question is probably the wrong one to ask, because you did not specify over which class of problems you want your bound to hold.

Edit: I realized that my previous example was wrong - here is a one-dimensional example.

To illustrate that: here is an example class where the simple gradient method (with steepest descent) performs better than Nesterov's accelerated method: Simply take the one-dimensional function $$ F(x) = \begin{cases} \tfrac{L+\mu}2 x^2 & |x|<\tfrac1L\\ |x| - \tfrac1{2L} + \tfrac{\mu}2x^2 & |x|\geq \tfrac1L \end{cases}. $$ Then $F$ is strongly convex with condition number $k = L/\mu$, and steepest descent always finds the solution $x=0$ in one step. Nesterov's accelerated method one works with specific stepsizes and, the larger $L$, the smaller the stepsizes. It always needs "infinitely many steps", i.e. never terminates in finitely many steps and convergence get smaller when $L$ gets larger.

The crux is, that one method may perform well one some examples, while bad on others and the other way round for another method. Another example of this, that may be surprising: There is a convex function in two dimensions where gradient descent with steepest descent stepsizes, i.e. going along the neg-gradient until the function is smallest, does not even lead to a convergent sequence (but one with four accumulation points) while gradient descent with fixed stepsize does indeed converge (and also decreases the objective value faster in the long run).

Answer 2

Since the results you mentioned look not quite precise what they refer to, I regarded it as scheme (2.2.9) in [Nesterov]. The optimization problem has following settings.

(i) $f$ admits a minimizer $x^{*}$ on $\mathbb{R}^{n}$ such that $\|x^{*}\|\leq R$.

(ii) $f$ is convex on $\mathbb{R}^{n}$.

(iii) $f$ is $L$-smooth ($\nabla f$ exists) on the $\ell_{2}$-ball of radius $R$, that is for any $x\in\mathbb{R}^{n}$ such that $\|x\|\leq R$ and any $g\in\partial f(x)$, one has $\|g\|\leq L$.

Any algorithm in a gradient scheme follows an update $x_{t+1}=x_{t}-\eta\partial f(x_{t})$, for some step size $\eta>0$, its optimal rate is proven to be $O(\frac{1}{t^{2}})$.

The plain gradient algorithm has a rate of $O(\frac{1}{t})$.

Nesterov's accelerated gradient algorithm has a rate of $O(\frac{1}{t^{2}})$, i.e. it has an optimal convergence rate within the gradient scheme. To be more precise, if you consider “the worst function in the world” constructed on [Nesterov] p.59, then the following family of $n$ functions

$$f_{k}(\boldsymbol{x})=\frac{L}{4}\left\{ \frac{1}{2}\left[x_{1}^{2}+\sum_{i=1}^{k-1}\left(x_{i}-x_{i+1}\right)^{2}+x_{k}^{2}\right]-x_{1}\right\} ,\forall\boldsymbol{x}=\left(x_{1},x_{2},\cdots x_{n}\right)\in\mathbb{R}^{n},0\leq k\leq n$$

and the optimal quadractic bound is actually reached for this family as explained on pp.60-61.

The last comment I want to make on this method from a more mathematical perspective is that a 2013 paper of Su-Boyd-Candes [Su et.al] greatly expands the influence of Nesterov's method in stat community.

[Nesterov] Nesterov, Yurii. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2013. (This book is by no means "basic" in American sense...)

[Su et.al]Su, Weijie, Stephen Boyd, and Emmanuel Candes. "A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights." Advances in Neural Information Processing Systems. 2014.