Return to 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.

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.

Are there examples of simple and strongly convex functions for which the convergence bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s 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 ratio.

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.