Motivation
For orthonormal columns, the LASSO solution is obtained by thresholding correlations once. With correlated columns, changing one coefficient changes the residual seen by the others. We therefore need an iteration that accounts for the whole design and a way to tell whether its current answer is close to optimal. A decreasing objective alone is not a certificate of accuracy: the decrease can be small while the objective is still far from its minimum.
Fix , and . We consider the finite-dimensional objective
Every coefficient is penalized; there is no separate intercept. The loss gradient is . Put , the largest eigenvalue of . First suppose , so . The penalty makes coercive, hence a minimizer exists even if the columns are dependent. Dependence can prevent uniqueness.
From a quadratic model to an update
Definition 1.5.1
(Soft threshold and the proximal step)
For , define , with the convention . Given and , the next vector minimizes
It is uniquely given by .
To see this, complete the square. Apart from terms independent of , is the sum over coordinates of , where . On the positive and negative half-lines the stationary candidates are respectively and ; when , zero satisfies the subgradient condition. The quadratic makes the minimizer unique. Thus each iteration first moves in the loss-gradient direction and then applies the threshold appropriate to the step size, not simply .
Concept lensGeometric
Soft thresholding as identity minus a box projection
Coordinatewise, , where is the Euclidean projection onto the box , that is, clipping each coordinate to : if the clip returns and the threshold returns , and otherwise they return and . The proximal step therefore keeps the part of the gradient-step vector that a box of half-width cannot absorb. A box of half-width reappears as the dual constraint in the certificate below.
A convergence guarantee
Theorem 1.5.2
(Objective rate and convergence of the iterates)
Let , , and . Start from any and set
For every minimizer and every ,
The objectives are nonincreasing and the iterates converge to a minimizer. The limiting minimizer may depend on the starting point when minimizers are not unique.
Proof
(Three-point inequality, telescoping and convergence of the iterates)
The quadratic loss satisfies both the convex lower bound and the upper model
The second follows exactly from and . Optimality of in the proximal subproblem gives a satisfying . First combine the upper model at with the convex lower bound at and the subgradient inequality . Then replace by . Using the identity , we obtain for every
With , this shows descent. With , summing the inequality from to telescopes. Since the objective gaps are nonnegative and nonincreasing, their last value is at most their average, yielding the displayed rate.
The same inequality says that distance to each minimizer is nonincreasing. Hence the iterates are bounded. The objective bound tends to zero, so every cluster point is a minimizer by continuity. Choose one cluster point ; because is nonincreasing and a subsequence tends to zero, the full sequence converges to . This proves convergence without assuming full column rank. If , instead choose any : the problem is minimized uniquely at zero and repeated thresholding reaches zero in finitely many steps.
Proof X-ray
What the telescoping argument needs
The proof rests on one inequality valid for every comparison point , and each hypothesis enters it once. The step condition supplies the upper model at the new point ; convexity supplies the lower bound at ; the proximal optimality condition joins them, so that the linear terms cancel and only squared distances remain.
The freedom in does the work. Taking gives descent. Taking makes the right side telescope, and monotonicity of the gaps turns the sum into a bound on the last gap. The same inequality shows that cannot increase for any minimizer, which is stronger than the rate: it gives boundedness, and together with a cluster point it fixes the limit of the whole sequence. Neither uniqueness nor full column rank is used. The condition is used only in the upper model, which is exactly what the large-step counterexample below violates.
Fixed points and sparse decisions
Proposition 1.5.3
(Fixed points are exactly LASSO minimizers)
For any , a vector is a fixed point of if and only if it minimizes .
Proof
(Fixed points through the optimality condition)
The proximal subproblem has a unique minimizer, so is a fixed point exactly when minimizes . Its optimality condition at is , because the term vanishes there. This is precisely the necessary and sufficient convex optimality condition for .
The fixed-point equivalence holds for every positive step, including steps too large for the convergence theorem. The distinction is essential: identifying the correct fixed points does not prove that an iteration reaches one.
For a nonzero coefficient, the condition requires . At zero the allowed correlations fill the interval . The threshold can set a coefficient to zero in one iteration, but the residual changes at later iterations. Its correlation can then leave the interval and the coefficient can become nonzero again. A temporary zero is therefore not a permanent feature-selection guarantee.
Worked example 1.5.4
(A coupled design changes both coordinates)
Let
Here has eigenvalues and , so is allowed. From zero, the initial correlations are . The gradient step gives , and thresholding at yields . Its residual is , whose correlations are . Both coordinates remain positive after the next step, which gives : the first grows while the second shrinks. Both updates depend on the same residual. The exact optimum is ; its residual is , and both correlations equal , verifying optimality. Because has independent columns, it is the unique optimum.
Worked example 1.5.5
(A zero coefficient can return)
Keep the same matrix, step and , but take and . Initially , so the threshold gives : the first gradient-step coordinate is exactly at the threshold. Now , with correlations . The next gradient-step vector is . Thresholding gives . The first coefficient has returned because the residual correlation changed from to . Neither this return nor its initial zero alone determines the final support.
The theorem gives a sufficient fixed step based on the largest singular value. Computing that value exactly is not always necessary: any known upper bound permits the conservative choice . A smaller step can cost more iterations. Conversely, a practical adaptive rule must actually check an appropriate upper-model inequality; simply observing a decrease at one step does not establish the theorem for all later steps.
Backtracking when the curvature is unknown
A global bound can be expensive or overly conservative. Instead, fix a trial step and a shrink factor . At each iterate , start again with , compute , and accept it only if
If the test fails, replace by and recompute both the gradient step and its threshold. The test concerns , not the full objective: the penalty is already retained exactly in the proximal subproblem. For this quadratic loss it is equivalent to . Checking merely would be a different rule and does not provide the argument below.
Proposition 1.5.6
(Finite backtracking and its guarantee)
Suppose and . With the rule above, every search accepts after finitely many trials, and its accepted step is at least . The objective values decrease or stay constant; for any minimizer and ,
The iterates converge to a minimizer, even when it is not unique.
Proof
(Termination of the search and the weighted telescoping sum)
The quadratic expansion of shows that every trial with passes, regardless of the proposed direction. Thus repeated multiplication by must terminate. If the first trial passes, its size is . Otherwise, at the first passing trial the preceding, failing step was greater than ; the accepted step is therefore greater than . This proves the uniform lower bound. A larger step can also pass because the test depends on the actual direction; the test is sufficient without estimating the largest singular value.
The accepted upper model is exactly the ingredient used in the earlier three-point argument. At step , replace there by to get
Taking shows descent. Taking and summing gives a bound on the weighted sum of nonnegative objective gaps. Since those gaps do not increase, the last gap times is no larger than that weighted sum. The displayed estimate follows. The same inequality makes the distance to each minimizer nonincreasing; boundedness, vanishing objective gap, continuity and the cluster-point argument from the fixed-step proof then give convergence of the whole sequence. The positive lower bound matters: without a condition preventing steps from becoming summable, this proof does not establish the rate or convergence.
Proof X-ray
Why an accepted local model is enough
The test is checked only at the candidate actually produced, and that is all the three-point inequality uses: the upper model at , convexity at an arbitrary , and the proximal optimality condition, now with the accepted step . Since does not enter the inequality itself, a step longer than that passes the test serves as well as a short one.
The constant returns in one place only, the lower bound . Telescoping controls times the last gap, so the rate needs . Without the lower bound, accepted steps could be summable, and the weighted sum would no longer force the gap to zero.
Worked example 1.5.7
(Reject twice, then accept)
Let , , , , and . Here , and . The first candidate is : its loss exceeds the model value , so reject it. With , the candidate is ; its loss exceeds , so reject again. With , the candidate is ; its loss and model value both equal , so accept. Its residual is , and , verifying the candidate is already optimal. This immediate arrival is special to the scalar example, not a general one-step guarantee.
At an accepted candidate, the model and the fact that the proximal subproblem was minimized imply . The converse need not hold: objective decrease alone may accept a step that fails the model test. Also, a zero update passes the test for any positive step; by the fixed-point result it already identifies a minimizer, even if that trial step exceeds .
Worked example and a computable certificate
Worked example 1.5.8
(Two features with different scales)
Take , , , and . The gradient step is and thresholding at gives . The residual is , and .
The coordinates separate here: the minimizer is , with residual and objective . The second coordinate has already reached its final value; the first has not. The rate theorem remains valid for coupled columns, where this separable shortcut does not apply.
In practice and its distance from are unknown. A dual feasible vector satisfies . Its dual value is . For every and feasible ,
The identity follows by expanding the square. Feasibility and the norm inequality give . Applying the identity at a minimizer gives , hence is an observable upper bound on . It measures objective accuracy, not necessarily coefficient accuracy or correct feature selection.
For the example, . Scaling by yields feasible . Then and the gap is . More generally, use where when the denominator is nonzero; if it vanishes, take . At an optimum, the residual itself is dual feasible and gives zero gap by the LASSO subgradient conditions.
When the step is too large
Counterexample mode
A repeating sequence can increase the objective
In the scalar problem , , , , choose and . The threshold is : , followed by . The sequence alternates forever. Moreover and , so even descent fails. This does not say every step larger than fails; it shows why an arbitrary step needs a separate justification.
Common mistake
(A small update is not a universal certificate)
A fixed small step can make an update small even far from the optimum. Compare a feasible dual lower bound to the objective instead. A small objective gap still does not imply a small coefficient error without additional assumptions such as strong convexity. For example, if has full column rank, then , so an objective gap at most bounds the squared coefficient error by .
Common mistake
(Thresholding at instead of )
The gradient step is scaled by , so the threshold must be . With , , and , the wrong iteration has the fixed point , whereas the minimizer is . In general a fixed point of minimizes : the wrong threshold solves a LASSO problem with penalty instead of .
Exercises
Quick check
(For , , , , and , compute two iterates and the exact minimizer.)
Solution · Answer
and . The scalar optimum is . Both iterates are below it; convergence is not generally a one-step result.
Quick check
(Let , , and . Give two distinct minimizers and explain why objective convergence need not identify a unique coefficient vector.)
Solution · Answer
Both and have residual , and each obeys the residual-correlation conditions for . They are distinct global minimizers. In fact every nonnegative pair summing to is a minimizer. A statement that objective values converge therefore cannot by itself select a unique representation. The iterates still converge, but their limit may depend on .
Quick check
(In the scalar problem of the first exercise, calculate a feasible dual vector and a duality gap at .)
Solution · Answer
At the residual is ; choose , which obeys . The primal value is and the dual value is , so the gap is . Here it equals the true objective error because is the optimal residual ; an arbitrary feasible dual vector need not give a tight bound.
Quick check
(Take , , , . Try in the backtracking test, then halve it if rejected. Does objective descent alone decide the first trial?)
Solution · Answer
At , . Although , its loss is , while the upper model is . The trial is rejected despite descent. Halving gives and . Its loss is at most the upper model , so this trial is accepted.
Related notes
LASSO and matching pursuit develops the residual optimality conditions and distinguishes global LASSO from greedy pursuit. Gradient descent on quadratics explains how eigenvalues control smooth quadratic steps.