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

Chooseso the smooth maximum error is at most $ϵ/2$ and the Lipschitz gradient constant isSuppose a minimizer of $f_{\beta }$ lies within distance $R$ of the starting point. The Nesterov accelerated gradient method can find $x$ such thatiniterations. If $x_{\ast }$ minimizes $f$, then the smoothing inequalities implyThis improves the nonsmooth subgradient method dependence from $O({ϵ}^{-2})$ to $O({ϵ}^{-1})$.