= Solution
{c}
Fix $x$, and write $p=x-\alpha G_\alpha(x)$ and $g=G_\alpha(x)$. The supplied <subgradient> relation gives $v=v_\alpha\in\lambda\partial\psi(p)$ with $g=\nabla f(x)+v$. The evaluation point in $\nabla f$ is $x$, whereas $v$ is a <subgradient> at the new point $p$.
Apply the <subgradient inequality> at $p$, with comparison point $x$:
$$
\lambda\psi(p)-\lambda\psi(x)\leq v^T(p-x)=-\alpha v^Tg.
$$
The <descent lemma> for the $L$-<Lipschitz gradient> of $f$ gives
$$
f(p)-f(x)\leq-\alpha\nabla f(x)^Tg+\frac{L\alpha^2}{2}\|g\|^2.
$$
Adding these estimates proves the stronger, explicit inequality
$$
\boxed{\phi(p)-\phi(x)\leq-\alpha\left(1-\frac{L\alpha}{2}\right)\|G_\alpha(x)\|^2.}
$$
In particular, the <objective function> decreases for $0<\alpha<2/L$ whenever the <proximal gradient mapping> is nonzero.
To justify the requested <big O notation>, we must check that $g$, which depends on $\alpha$, stays bounded. Suppose $\partial(\lambda\psi)(x)$ is nonempty, and choose a fixed $w$ in this <subdifferential>. This holds for a finite-valued <convex function> on $\mathbb R^n$, including both <norms> in parts (a) and (b). By <monotonicity of a convex subdifferential>,
$$
(v-w)^T(p-x)\geq0.
$$
Substituting $p-x=-\alpha g$ and $v=g-\nabla f(x)$, and then using the <Cauchy-Schwarz inequality>, yields
$$
\|g\|^2\leq(\nabla f(x)+w)^Tg\leq\|\nabla f(x)+w\|\,\|g\|.
$$
Thus $\|g\|\leq C_x:=\|\nabla f(x)+w\|$, uniformly in $\alpha>0$. This <local boundedness of the proximal gradient mapping> makes the remainder at most $LC_x^2\alpha^2/2$, so
$$
\boxed{\phi(x-\alpha G_\alpha(x))-\phi(x)\leq-\alpha\|\nabla f(x)+v_\alpha\|^2+O(\alpha^2).}
$$
\b[No differentiability of $\psi$ is needed.] If an <proper extended-real function> is allowed as the <regularization> term, the <subdifferential> condition at $x$ is a qualification for this uniform remainder; the preceding explicit descent inequality remains the useful statement whenever its quantities are finite.
Back to article page
