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}$. This implies the subgradient $\partial f(x)\neq\emptyset, \forall x\in\mathbb{R}^{n}$.

(iii) $f$ is $L$-smooth 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.

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.

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}$. This implies the subgradient $\partial f(x)\neq\emptyset, \forall x\in\mathbb{R}^{n}$.

(iii) $f$ is $L$-smooth 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},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.

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}$. This implies the subgradient $\partial f(x)\neq\emptyset, \forall x\in\mathbb{R}^{n}$.

(iii) $f$ is $L$-smooth 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.