= Solution
{c}
Set $g_j=G_{1/L}(x^j)$, $r_j=\|x^j-x^*\|^2$ and $\delta_j=\phi(x^j)-\phi(x^*)$. Here $g_j$ is the <proximal gradient mapping>, $r_j$ is a squared <Euclidean distance>, and $\delta_j\geq0$ because $x^*$ is a <global minimizer>. The update gives $x^{j+1}=x^j-g_j/L$.
First use the supplied inequality (1) with $z=x^j$:
$$
\phi(x^{j+1})\leq\phi(x^j)-\frac1{2L}\|g_j\|^2\leq\phi(x^j).
$$
Thus the <objective function> values, and hence the errors $\delta_j$, are nonincreasing. Next use (1) with $z=x^*$:
$$
\delta_{j+1}\leq g_j^T(x^j-x^*)-\frac1{2L}\|g_j\|^2.
$$
Expansion of the squared <Euclidean norm> gives
$$
r_{j+1}=r_j-\frac2L g_j^T(x^j-x^*)+\frac1{L^2}\|g_j\|^2,
$$
so the last bound is exactly $\delta_{j+1}\leq L(r_j-r_{j+1})/2$.
The <telescoping sum> over $j=0,\ldots,k-1$ therefore gives
$$
\sum_{j=0}^{k-1}\delta_{j+1}\leq\frac L2(r_0-r_k)\leq\frac L2r_0.
$$
Since each summand is at least $\delta_k$, we obtain the <proximal gradient objective error bound>
$$
\boxed{\phi(x^k)-\phi(x^*)\leq\frac L{2k}\|x^0-x^*\|^2,\qquad k\geq1.}
$$
\b[The bound holds for the last iterate.] The monotonicity of the <objective function> values is what converts an averaged estimate into this last-iterate estimate.
Back to article page
