= Solution
The <Euclidean projection onto a convex set> is nonexpansive, and $x^*=P_C(x^*)$ because the optimum is feasible. Therefore the <projected subgradient method> satisfies
$$
\begin{aligned}
\lVert x_{i+1}-x^*\rVert_2^2
&\leq\lVert x_i-tg_i-x^*\rVert_2^2\\
&=\lVert x_i-x^*\rVert_2^2
-2t\langle g_i,x_i-x^*\rangle+t^2\lVert g_i\rVert_2^2.
\end{aligned}
$$
The <subgradient inequality> gives $\langle g_i,x_i-x^*\rangle\geq f(x_i)-f^*$, while <Lipschitz continuity> of the finite <convex function> gives $\lVert g_i\rVert_2\leq G$. Hence
$$
2t\bigl(f(x_i)-f^*\bigr)
\leq \lVert x_i-x^*\rVert_2^2-
\lVert x_{i+1}-x^*\rVert_2^2+t^2G^2.
$$
Summing this telescoping inequality for $0\leq i<k$, and then bounding the smallest term by the average, yields
$$
\min_{0\leq i<k}f(x_i)-f^*
\leq\frac{\lVert x_0-x^*\rVert_2^2}{2tk}
+\frac{tG^2}{2}.
$$
Writing $D=\lVert x_0-x^*\rVert_2$, the right-hand side is minimized by the constant <step size>
$$
t=\frac{D}{G\sqrt{k}}.
$$
Substitution gives
$$
\boxed{\min_{0\leq i<k}f(x_i)-f^*\leq\frac{GD}{\sqrt{k}}}.
$$
If $D=0$, the initial point is already optimal and the result is immediate.
Back to article page
