= Proximal gradient objective error bound
{title2=$\phi(x^k)-\phi(x^*)\leq L\|x^0-x^*\|^2/(2k)$}
For $\phi=f+h$, with $f$ a <convex function> having an $L$-<Lipschitz gradient> and $h$ a <proper convex function> with a well-defined <proximal operator>, the <proximal gradient method> with <step size> $1/L$ satisfies the displayed bound whenever a <global minimizer> $x^*$ exists. The one-step <subgradient inequality> and <descent lemma> give
$$
\phi(x^{j+1})-\phi(x^*)\leq\frac L2\big(\|x^j-x^*\|^2-\|x^{j+1}-x^*\|^2\big).
$$
The <objective function> values are nonincreasing. A <telescoping sum> over $j=0,\ldots,k-1$, followed by comparison of the last error with the <arithmetic mean> of the errors, proves the result. The bound controls the last <objective function> error without requiring a <strongly convex function> or a unique <minimizer>.
``
Target: convex-optimization.bigb, under Proximal gradient method.
``
Back to article page
