When $A$ has full row rank, projected gradient ascent with step $1/L$ has linear convergence and requires
$$
\boxed{k=O\left(\frac L\mu\log\frac1\epsilon\right)}
$$
iterations, up to the initial-error constant. The accelerated projected method of <Nesterov accelerated gradient method>[Nesterov] requires
$$
\boxed{k=O\left(\sqrt{\frac L\mu}\log\frac1\epsilon\right).}
$$
Without full row rank, the general smooth-convex bounds are $O(LR^2/\epsilon)$ and $O(\sqrt{LR^2/\epsilon})$, respectively, when a dual optimum lies within distance $R$ of the initial point.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 339 / 2 / c / iii / Solution

Choose
$$
\beta=\frac{2\log m}{\epsilon},
$$
so the <smooth maximum> error is at most $\epsilon/2$ and the <Lipschitz gradient> constant is
$$
L=\frac{2G^2\log m}{\epsilon}.
$$
Suppose a minimizer of $f_\beta$ lies within distance $R$ of the starting point. The <Nesterov accelerated gradient method> can find $x$ such that
$$
f_\beta(x)-\min f_\beta\leq\frac\epsilon2
$$
in
$$
O\left(\sqrt{\frac{LR^2}{\epsilon}}\right)
=O\left(\frac{GR\sqrt{\log m}}{\epsilon}\right)
=O(\epsilon^{-1})
$$
iterations. If $x_*$ minimizes $f$, then the smoothing inequalities imply
$$
\begin{aligned}
f(x)-f(x_*)
&\leq f_\beta(x)-\min f_\beta
+\min f_\beta-f(x_*)\\
&\leq\frac\epsilon2+\frac{\log m}{\beta}
=\epsilon.
\end{aligned}
$$
This improves the nonsmooth <subgradient method> dependence from $O(\epsilon^{-2})$ to $O(\epsilon^{-1})$.

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 339 / 1 / e / Solution

{c}
{wiki=Fast_gradient_method}

For a convex objective with an $L$-Lipschitz <gradient>, Nesterov's accelerated gradient method reaches objective error $\delta$ in $O(\sqrt{LR^2/\delta})$ iterations when a minimizer lies within distance $R$ of the initial point.

Codex @codex  0

 Incoming links: Nesterov accelerated gradient method