Why a composite method is needed
Many optimization problems have the form "smooth data fit plus a simple nonsmooth penalty", for instance a least-squares term plus a multiple of the norm. Plain gradient descent does not apply because the penalty is not differentiable, and treating the penalty by a subgradient step gives only a slow rate. The proximal gradient method exploits the structure: it takes a gradient step on the smooth part and then solves the penalty exactly, in closed form whenever the proximal map is available. This unit builds on the proximal map of the absolute value (soft thresholding), the subgradient calculus of convex functions, and the descent inequality for functions with Lipschitz gradient used in the projected gradient unit.
Definitions and standing assumptions
Consider
Assume:
- is convex and differentiable, and is -Lipschitz for some . Then for all ,
- is convex (finite everywhere, hence continuous), not necessarily differentiable.
- attains its minimum value at some point .
Definition 9.2.1
(Proximal map)
For and the proximal map of is
The objective is continuous, strongly convex and tends to as , so the minimizer exists and is unique. For the map acts coordinatewise as soft thresholding with threshold ; for it is the identity.
Lemma 9.2.2
(Characterization of the proximal map)
if and only if .
Proof
(Optimality of a strongly convex subproblem)
The function is convex and finite, so minimizes it exactly when belongs to its subdifferential at . Because the quadratic is differentiable, the subdifferential of the sum is . Hence the condition reads .
Definition 9.2.3
(Proximal gradient method)
The proximal gradient method with step size and starting point generates
When it is gradient descent. When is the indicator function of a closed convex set (not finite, but the same formulas apply) the proximal map is the Euclidean projection and the method is projected gradient. When it is the iterative soft-thresholding algorithm (ISTA).
Concept lensAnalytic
Each step minimizes a quadratic upper model
Completing the square shows that
The method linearizes only , adds a proximity term and keeps exact. For the descent inequality makes this model an upper bound for that equals at , so : monotone decrease follows before any rate is proved.
Fixed points are minimizers
Proposition 9.2.4
(Fixed points are exactly the minimizers)
Let . A point minimizes if and only if .
Proof
(Two subgradient inequalities added together)
By the characterization lemma the fixed-point equation says . If this holds, then for every we have and, by convexity of , . Adding gives . Conversely, if minimizes , then by the sum rule, which is the same inclusion.
So the method stops exactly at minimizers, and the step size does not affect which points are fixed.
The one-step inequality
Theorem 9.2.5
(One-step inequality)
Let , let and . Then for every ,
Proof
(Three inequalities and a polarization identity)
Put , the gradient mapping. By the characterization lemma, with replaced by , we get . The subgradient inequality gives
By the smoothness inequality and ,
and by convexity . Adding the three inequalities, the terms and combine into , which cancels against the term coming from the first inequality. What remains is
Now and . Therefore , and the last term cancels the term .
Proof X-ray
Where each hypothesis is spent in the one-step inequality
Each of the three inequalities spends one hypothesis: the subgradient inequality at uses convexity of through the characterization lemma, the descent inequality uses the Lipschitz gradient, and the lower bound at uses convexity of . The step-size restriction enters only once, when is replaced by . The linear terms in cancel because the three inequalities are anchored at , and and together form a closed loop. The key move is the polarization identity: it rewrites the leftover inner product as a difference of squared distances to minus , and that negative term exactly absorbs the quadratic term from the descent inequality. If , a positive remainder survives on the right, and the telescoping argument for the rate no longer closes.
The convergence rate
Theorem 9.2.6
(An O(1/k) bound for the objective gap)
For and , the iterates satisfy and, for every ,
Proof
(Telescoping the one-step inequality)
Taking in the one-step inequality gives . Taking and summing over , the squared distances telescope:
Since the values are nonincreasing, each of the summands is at least . Dividing by gives the claim.
The bound is sublinear: halving the gap costs twice as many iterations. It is a statement about objective values. The proof also shows , since each term is nonnegative, but gives no rate for the distance.
Worked examples
Worked example 9.2.7
(A scalar problem solved in one step)
Let , , so . The minimizer of is , where , and .
With and any , , so : the method is exact after one step.
Worked example 9.2.8
(The same problem with half the step size)
Keep and , but take and . The gradient step is and the threshold is . Then , ; , ; , . In general , since whenever the argument exceeds the threshold, and then . The iterates converge geometrically here because is strongly convex, a stronger situation than the rate theorem assumes. Check at : , while the bound is .
Worked example 9.2.9
(A two-dimensional lasso whose sparse coordinate vanishes only in the limit)
Let , , , . Then , which is Lipschitz with . Take , so the threshold is , and .
The gradient step gives and . Hence the first coordinate equals after every step, and for the second coordinate as long as . Starting from the iterates are
so . The limit is . We confirm optimality by the fixed-point test: , so and soft thresholding at returns . The sparse coordinate becomes exactly zero only in the limit here, not in finitely many steps.
We check the rate theorem at . ; . , so the gap is . The bound is , which holds.
Common mistakes and subtle points
Common mistake
(Applying the proximal map before the gradient step)
The proximal map is applied to the gradient-step point , not to . Applying it to and then stepping gives a different and generally wrong method.
Common mistake
(Choosing the step size from the penalty)
Only must be Lipschitz. The penalty may be nondifferentiable, and its Lipschitz properties play no role in the step size.
Common mistake
(Reading the O(1/k) bound as a statement about iterates)
is a bound for the objective value at the last iterate. It does not claim the iterates converge faster, and it does not mean the support of equals that of after finitely many steps.
Two further points concern the hypotheses themselves.
- Convexity of is used twice: for the uniqueness of the proximal map and for the subgradient inequality in the one-step inequality. For nonconvex the proximal map can be multivalued and the rate theorem fails.
- The method is only as useful as the proximal map is cheap. Soft thresholding and projections onto boxes or balls are closed-form; a general may require an inner solver, and then the theorem does not apply to the inexact iteration.
Counterexample mode
Too long a step can make the method diverge
The bound is sufficient, not necessary, but some bound is needed. Take , so , and , with and . The iteration is , so the iterates are and , although . No bound of the form can hold. For this particular every converges (see the exercise on step sizes below), so the theorem's condition is conservative but cannot simply be dropped.
Exercises
Quick check
(Let , , , . Compute and verify that it minimizes .)
The threshold is times the penalty weight.
Solution
The gradient step is and the threshold is , so . For optimality, for , which vanishes at (and is consistent with the sign used). Since is convex, is the minimizer.
Quick check
(Let , , , . Compute and decide whether the method has converged.)
Apply the fixed-point test to the new point.
Solution
The gradient step gives , so . Since , the point is a minimizer, and it is a fixed point: . The method has converged after one step.
Quick check
(A problem has , and the method is run with from a point with . Give the guaranteed bound on .)
Substitute into the rate theorem.
Solution · Answer
By the rate theorem with , the gap is at most .
Quick check
(Show that if is the zero function, the rate theorem reduces to the gradient descent bound , and identify in this case.)
Minimize over .
Solution
If then is minimized at , so is the identity and the iteration is . Then and the rate theorem is exactly the stated gradient descent bound.
Quick check
(For and , find all step sizes for which the iterates converge to from every starting point.)
Write the iteration as multiplication by a constant.
Solution
Here the iteration is , so . This tends to for every exactly when , that is . With this includes the whole range guaranteed by the theorem, and shows the sufficient condition is conservative.