Proximal gradient objective error bound ($\varphi (x^k)-\varphi (x^{\ast })\le L\Vert x^0-x^{\ast }{\Vert }^2/(2k)$)

For $\varphi =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^{\ast }$ exists. The one-step subgradient inequality and descent lemma giveThe objective function values are nonincreasing. A telescoping sum over $j=0,\dots ,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.