The Proximal Gradient Method: Splitting Smooth and Nonsmooth

The precise statement

Let f: ℝⁿ → ℝ be convex and differentiable with an L-Lipschitz gradient, i.e. ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖ for all x, y. Let g: ℝⁿ → ℝ ∪ {+∞} be proper (not identically +∞), convex, and lower semicontinuous (l.s.c.). Assume F = f + g attains its minimum at some x* (guaranteed if F is coercive, or if the minimizer set is nonempty). The proximal gradient iteration with step γ ∈ (0, 1/L] is

xₖ₊₁ = prox_{γg}(xₖ − γ∇f(xₖ)).

Theorem. The iterates satisfy F(xₖ) − F(x*) ≤ ‖x₀ − x*‖² / (2γk). Hence for γ = 1/L the gap is at most L‖x₀ − x*‖²/(2k), an O(1/k) rate. If moreover f (or g) is μ-strongly convex, convergence becomes linear: ‖xₖ − x*‖² ≤ (1 − γμ)ᵏ ‖x₀ − x*‖². The prox operator is single-valued and well-defined here because g + (1/2γ)‖·−v‖² is strongly convex and l.s.c., so its argmin exists and is unique.

The picture: forward step, backward step

Read the iteration as forward–backward splitting. The forward half, v = xₖ − γ∇f(xₖ), is an explicit (forward) Euler step on the gradient flow ẋ = −∇f(x). The backward half, xₖ₊₁ = prox_{γg}(v), is an implicit (backward) Euler step on the subgradient flow of g: the optimality condition of the prox says xₖ₊₁ + γ∂g(xₖ₊₁) ∋ v, i.e. (I + γ∂g)⁻¹ v. So one iteration is (I + γ∂g)⁻¹ ∘ (I − γ∇f).

Why implicit on g? Because ∂g can be unbounded or set-valued (think of the corner of |x|), an explicit step would need a subgradient direction that oscillates; the proximal step instead resolves the nonsmooth part exactly by a small optimization you can solve in closed form. Geometrically prox_{γg}(v) pulls v toward the low-g region while penalizing overshoot — it is the resolvent of the maximal monotone operator ∂g, and it is firmly nonexpansive, which is what makes the whole scheme contract.

Key idea of the proof

Two engine parts. First, the descent lemma: L-Lipschitz ∇f gives f(y) ≤ f(x) + ⟨∇f(x), y − x⟩ + (L/2)‖y − x‖². Second, the prox step is a proximal minimization, so xₖ₊₁ minimizes the surrogate Q(x) = f(xₖ) + ⟨∇f(xₖ), x − xₖ⟩ + (1/2γ)‖x − xₖ‖² + g(x), a valid upper bound on F when γ ≤ 1/L. Optimality of xₖ₊₁ for the strongly convex Q yields, for any z, the key inequality

F(xₖ₊₁) ≤ F(z) + (1/2γ)(‖z − xₖ‖² − ‖z − xₖ₊₁‖²) − (1/2γ)‖z − xₖ₊₁... ‖² terms,

and setting z = x* telescopes: summing over k, the ‖z − xₖ‖² − ‖z − xₖ₊₁‖² collapses to ‖x₀ − x*‖², while monotone decrease of F(xₖ) lets us replace the running sum by k·(F(xₖ) − F*). Divide by k. Equivalently: T = prox_{γg}∘(I − γ∇f) is averaged (a composition of firmly nonexpansive and, for γ ≤ 2/L, nonexpansive maps), so Fejér monotonicity gives xₖ → x* even without strong convexity.

Worked example: LASSO and soft-thresholding (ISTA)

Take the LASSO: minimize F(x) = ½‖Ax − b‖² + λ‖x‖₁, with A ∈ ℝ^{m×n}. Split f(x) = ½‖Ax − b‖² (smooth, ∇f(x) = Aᵀ(Ax − b), L = ‖A‖² = σ_max(A)²) and g(x) = λ‖x‖₁ (convex, l.s.c., nondifferentiable at 0).

The prox of the ℓ¹ norm separates coordinatewise, and each 1-D problem min_t { λ|t| + (1/2γ)(t − v)² } has the explicit soft-thresholding solution S_{γλ}(v) = sign(v)·max(|v| − γλ, 0). So the iteration is

xₖ₊₁ = S_{γλ}( xₖ − γ Aᵀ(Axₖ − b) ),

with γ = 1/‖A‖². This is exactly ISTA (Iterative Shrinkage-Thresholding). Each step is a matrix–vector product plus a cheap threshold; no inner solver, no matrix inversion. The threshold zeroes out small coordinates — this is where sparsity comes from. FISTA adds a momentum term yₖ = xₖ + ((tₖ−1)/tₖ₊₁)(xₖ − xₖ₋₁) and evaluates the gradient at yₖ, upgrading the O(1/k) rate to O(1/k²).

Why the hypotheses matter

L-Lipschitz ∇f. The descent lemma needs it. If ∇f is not Lipschitz (e.g. f(x) = x⁴), a fixed step γ can overshoot and diverge; you must use a backtracking line search to estimate a local L, or the guarantee is void. γ ≤ 1/L. For γ > 2/L the map I − γ∇f fails to be nonexpansive and iterates can spiral out. g convex + l.s.c. ensures ∂g is maximal monotone, so the resolvent (I + γ∂g)⁻¹ = prox_{γg} is single-valued and firmly nonexpansive — the contraction backbone. Drop l.s.c. and the argmin may not be attained; drop convexity and prox becomes multivalued and the fixed-point argument collapses (though for some structured nonconvex g, e.g. the ℓ⁰ 'norm' with hard-thresholding prox, one still gets local/subsequential results). Properness rules out the vacuous g ≡ +∞. Existence of x* needs coercivity or compact sublevel sets; without a minimizer the O(1/k) statement is empty. These are the exact hypotheses under which forward–backward splitting is a genuine descent method.

Significance and connections

Proximal gradient is the workhorse behind sparse recovery and compressed sensing (LASSO, basis pursuit), low-rank matrix completion (nuclear-norm minimization via singular-value thresholding), total-variation image denoising, and ℓ¹-regularized logistic regression. It generalizes three classics as special cases: g ≡ 0 gives gradient descent; g = indicator of a convex set gives projected gradient descent; f ≡ 0 gives the proximal point algorithm. Its lineage traces to Lions–Mercier (1979) forward–backward and Passty splitting; the modern convex-analytic treatment is Combettes–Wajs (2005), and Beck–Teboulle's FISTA (2009) delivered the optimal O(1/k²) rate matching Nesterov's 1983 lower bound for first-order methods. It sits inside a family with ADMM and Douglas–Rachford splitting (which handle two nonsmooth terms), and the prox operator itself is the resolvent that makes the whole monotone-operator machinery — Moreau's envelope, Yosida regularization, operator splitting — computable.

Common g and their proximal operators (the backward step), with the resulting algorithm

Nonsmooth term g(x)	prox_{γg}(v) closed form	Resulting method
0 (no g)	v	Gradient descent
λ‖x‖₁	soft-threshold: sign(vᵢ)·max(|vᵢ|−γλ, 0)	ISTA / LASSO solver
ι_C(x) (indicator of convex C)	P_C(v), Euclidean projection onto C	Projected gradient descent
λ‖x‖₊ nuclear norm (matrices)	singular-value soft-thresholding of v	SVT / low-rank recovery
(λ/2)‖x‖²	v / (1 + γλ)	Shrinkage (ridge-type)
λ∑|xᵢ|₂ per group (group lasso)	block soft-threshold on each group	Group-sparse regression