Motivation
Soft thresholding solves lasso in an orthonormal design because each coefficient then controls an independent quadratic term. Real predictors often overlap. Changing one coefficient changes the residual seen by several others, so thresholding an ordinary least-squares vector once is generally wrong. A useful sparse-learning method must repeatedly account for those interactions.
Two algorithms expose the same principle at different scales. Coordinate descent solves one exact scalar problem with the other coefficients fixed. Proximal gradient replaces the coupled smooth loss by a quadratic upper bound and solves its separable nonsmooth part. Both retain the sharp corner of the absolute-value penalty, which allows exact zero coefficients without pretending that the objective is differentiable there.
Optimization is only half the problem in a small sample. Choosing the penalty after inspecting validation scores uses information. Reporting the same winning score as independent evidence then creates selection optimism. We will connect a precise solver certificate to a precise evaluation protocol, while keeping coefficient selection, prediction and recovery of a true scientific mechanism separate.
Definitions
Definition 8.1.1
(A scaled lasso objective)
For a design , response and , minimize
Write for column of . The smooth gradient is , with Lipschitz constant . Soft thresholding is , with , applied coordinatewise to vectors.
The loss divisor matters: changing it without changing the penalty changes the fitted problem. We state algorithms for a design without an intercept. An unpenalized intercept can be eliminated by centering training predictors and response, then restored when predicting. Within validation, those means and scales must be estimated on the training portion of that fold. A column constant on that portion becomes a zero centered column and needs explicit removal or a zero-coefficient convention.
Standardizing columns is also a modeling choice, not merely numerical housekeeping. If a predictor is divided by its scale, its coefficient must be multiplied by that scale to keep predictions unchanged. An unweighted absolute-value penalty on the transformed coefficients therefore becomes a weighted penalty on the original coefficients. Equal numerical penalties across differently measured variables have different scientific meanings. State which scale receives equal penalization, preserve training-derived transformation parameters, and translate coefficients back carefully when interpreting a fitted model.
Definition 8.1.2
(A global optimality certificate)
For residual , lasso optimality is equivalent to
These are subgradient conditions, including the interval for the absolute value at zero. A proximal-gradient residual is for a fixed ; it is zero exactly at an optimum.
Unlike NMF, this whole coefficient problem is convex. A valid global certificate is therefore available even for a rank-deficient design. Convexity does not imply unique coefficients, and the word “global” refers to this training objective, not future prediction risk or correct variable identification.
Concept lensGeometric
Lasso as a fit constrained to an L1 ball
For a minimizer put . Then also minimizes over , because a competitor in that set with smaller loss would also have a smaller objective. This ball is a cross-polytope with corners on the coordinate axes, which is why a loss level set can touch it at a point with exact zero coefficients.
Theorem/Proposition
Theorem 8.1.3
(An exact coordinate step and a safe full-vector step)
Let , and . If , the exact coordinate minimizer is
For , set , which uniquely minimizes its penalty. If and , the proximal-gradient update
satisfies , and hence decreases by at least . If , the solution is simply zero.
Theorem 8.1.4
(Different lasso coefficients have the same fitted response)
For fixed and , a minimizer exists. Any two minimizers satisfy . Their coefficients and selected supports can nevertheless differ when the design is rank deficient. If has full column rank, the minimizer itself is unique.
Theorem 8.1.5
(Selection lowers the apparent winning error)
Let be integrable error estimates for a finite list of candidates. Then
No independence assumption is needed for this inequality. Even if every individual estimate is unbiased for its candidate's risk, the minimum is generally an optimistic score for judging a selection procedure. Independent evaluation must assess the full selection-and-fitting rule.
Proof sketch or proof idea
Proof
(Keep the absolute-value corner while controlling the quadratic)
With other coefficients fixed, the varying objective is plus a constant. For its derivative vanishes at ; this is positive exactly when . For the solution is when . In the remaining case the scalar objective has subdifferential at , and this interval contains zero. These cases give the coordinate formula, including both threshold equalities.
For the vector step, minimize . Completing the square makes this the proximal problem for , and its scalar minimizers are soft thresholds with threshold . Put . Optimality provides with . Convexity of gives
The exact smooth quadratic expansion and give . Adding proves the descent bound. The fixed-point condition is precisely , which is sufficient for a global minimum by convexity. The same inclusion gives the residual-correlation certificate coordinate by coordinate.
Proof X-ray
Why coupling and nonsmoothness require different treatment
The loss couples predictors through the Gram matrix. Coordinate updates repeatedly recompute partial residuals; proximal gradient bounds the entire coupling by a known curvature constant. The penalty remains exact in both methods. Replacing it with an arbitrary derivative at zero, or thresholding an unconstrained fit once, removes the logic that establishes the optimum.
Proof
(Existence, unique predictions and optimistic selection)
Because , sublevel sets are bounded. They are closed by continuity, so a minimizing sequence has a convergent subsequence attaining the minimum. Suppose two minimizers give different fitted responses. Their midpoint has strictly smaller squared residual loss than the average of their losses, because squared distance is strictly convex in the fitted response. Its penalty is no larger than the average by convexity. This contradicts minimality. If is injective, equal fitted responses imply equal coefficients; without injectivity they need not.
For selection optimism, pointwise for every fixed . Taking expectations and minimizing over proves the inequality. Strictness is possible whenever different candidates win because of estimation noise. The inequality is about the reported minimum, not a formula for the true risk of the candidate that happened to win; obtaining that risk requires additional evaluation.
A complete coordinate solver cycles over all design columns with , updating a maintained residual after each exact scalar step. It stops when the full residual-correlation certificate is within a declared tolerance, including the zero coefficients. A complete proximal solver computes the gradient, uses a valid curvature upper bound, thresholds, and stops from a declared proximal residual. Warm starts across nearby penalties can save computation, but do not turn a path of training solutions into an evaluation result. The modern proximal viewpoint is developed in Parikh and Boyd's primary authored monograph; the specialized derivations needed here are given above.
For small-sample evaluation, reserve outer folds for assessing the procedure. Within each outer training set, use inner folds to choose the penalty. For every inner split, fit centering, scaling and any variable filtering using only its inner training data, apply those transformations to the inner validation data, and compare the declared prediction loss. After choosing a penalty, refit transformations and coefficients on the entire outer training set and score once on the untouched outer fold. Pool those outer predictions under a stated aggregation rule. For a final model, choose and refit using the available development data; an independent test set remains untouched until the whole procedure is locked.
This nested arrangement estimates a fitting-and-selection procedure trained on smaller samples than the final refit. It is not an exact guarantee for the final fitted coefficient vector. Fold errors can be dependent because training sets overlap, and very small validation sets yield noisy choices. Report the split rule, candidate grid, scoring function and variation across outer folds. Do not interpret one minimum as a precise uncertainty interval or treat a stable selected variable as a proved causal mechanism.
Worked examples
Worked example 8.1.6
(A correlated two-predictor coordinate sweep)
Let , , and , without an intercept. Starting at zero, the first coordinate has , so it becomes . The second sees partial residual , giving and coefficient . One sweep therefore gives , not the final answer. Repeated updates lead to . Its residual has both normalized correlations , satisfying KKT. Its objective is ; after the first sweep it was .
Worked example 8.1.7
(Identical predictors allow infinitely many sparse explanations)
Take two identical columns with and response , where . The fit depends only on . The triangle inequality gives , with equality for nonnegative splits. The scalar optimum is . Every summing to this value is a minimizer. One solution selects the first predictor only, another selects the second only, and others select both. Their fitted values are identical. Variable selection can therefore be ambiguous even when the convex optimization is solved exactly.
Worked example 8.1.8
(A winning validation score need not be an independent estimate)
Suppose two candidates have the same true risk two. Each error estimate is independently one or three, with equal probabilities, and hence is unbiased. Their minimum is three only when both estimates are three, an event of probability ; otherwise it is one. Its expected value is , below the common risk two. The candidate chosen using these scores still has true risk two in this construction. Independent outer evaluation targets the selection procedure rather than repeating its optimistic minimum.
Common mistakes
Counterexample mode
Thresholding an ordinary fit once is wrong under coupling
In the two-predictor example the exact unpenalized fit is . Thresholding both entries by gives . The residual is , whose second normalized correlation is , larger than the required for a positive coefficient. Thus the proposed answer fails the global certificate. The correct correlated-design solution is .
Common mistake
(Prediction, support and causality are different targets)
A small optimization residual certifies a solution to a declared convex training problem. Accurate validation predictions assess a declared prediction procedure. Recovering a unique support requires stronger assumptions about design, signal and noise, and causal interpretation requires an appropriate causal design. Correlated predictors can exchange roles without changing predictions. Penalty tuning cannot by itself settle these scientific questions.
Summary
General-design lasso requires repeated residual-aware updates. Coordinate descent solves exact scalar problems; proximal gradient uses a curvature-controlled upper bound and exact thresholding. Convexity provides a global training certificate and unique fitted values, while coefficients can remain nonunique. Honest small-sample evaluation includes every transformation and penalty choice inside the procedure being evaluated.
Exercises
Quick check
(In the correlated example, update the first coordinate after the first sweep, holding the second at . Then update the second again and calculate the objective.)
Recompute each partial residual; the updates are sequential.
Solution · Guided solution
With second coefficient , the first partial residual is . Its normalized correlation is and curvature , so the first coefficient becomes one. The second then sees residual , giving normalized correlation one and coefficient . Reconstruction is , residual . Loss is , penalty , total . This is below the first sweep's and above the optimal .
Quick check
(Show that the zero vector minimizes lasso exactly when the largest absolute scaled predictor–response inner product is at most .)
Use the zero-coordinate part of the certificate.
Solution · Answer
At zero, residual is and every coordinate is inactive. The necessary and sufficient subgradient condition is for all , equivalently . Equality is allowed. Thus penalties at or above this threshold give the zero solution. If zero is optimal, the fitted-value theorem implies that every minimizer has , hence the same loss. Equal objectives then force . Since , zero is the unique coefficient minimizer even without full column rank.
Quick check
(For two identical normalized predictors with response and , give three different minimizers and verify their common objective.)
Split the scalar fitted coefficient two into nonnegative parts.
Solution · Answer
Take , and . Each produces , residual and smooth loss . Every penalty is two, so the common objective is . The triangle-inequality reduction to the scalar lasso proves all are global minima, despite their different supports.
Quick check
(A validation fold is used to choose a penalty, remove variables, and decide whether to transform the response. Explain what an outer evaluation must include and why reusing the winning score is problematic.)
The object being evaluated includes all three decisions.
Solution · Answer
For each outer training set, repeat the inner choices of penalty, variable filtering and response transformation using only that training set and its internal splits. Refit all chosen transformations and coefficients on the outer training set, then apply the locked prediction rule to the outer observations under the declared scoring scale. Outer labels must not influence any choice. Reusing the minimum inner score reports a number selected partly for favorable noise, as the finite-candidate inequality and worked example demonstrate.