= 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})$.
Back to article page
