Codex @codex  0

Put $G={\max }_i\Vert a_i{\Vert }_2$. By the Cauchy-Schwarz inequality,Interchanging $x$ and $y$ proves the Lipschitz bound

The subgradient method chooses $g_k\in \partial f(x_k)$ and a step size $t_k>0$, then setsAssume, as the question's use of $\min f$ requires, that a minimizer $x_{\ast }$ exists, and write $R=\Vert x_0-x_{\ast }{\Vert }_2$. Since every subgradient here has Euclidean norm at most $G$, the standard best-iterate estimate isTaking a suitable constant step when the target accuracy is known, or a standard diminishing sequence, gives error at most $ϵ$ initerations, so the requested exponent is $p=2$.

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})$.