An optimization certificate says that a computed vector nearly minimizes a stated objective. A statistical guarantee asks a different question: if the observed responses contain noise, how close are the fitted values to the unknown signal? The answer depends on the scale of the penalty and on how the design acts on the errors that the optimization problem permits.
A fixed-design model
Let be positive integers, let be fixed, let , and choose . We penalize every coordinate and define any exact minimizer
A minimizer exists because this continuous objective is coercive; it need not be unique. If an intercept is left unpenalized, the argument below must first be adapted, for example by consistently centering both response and columns. Our prediction error is : it measures discrepancy at these same design points, not error on future inputs.
Suppose is supported on , with . Coordinates outside vanish; some coordinates inside may also vanish. For a vector , write for the vector retaining only coordinates in . The relevant cone is
Definition 1.6.1
(Restricted eigenvalue on a cone)
The design has restricted eigenvalue constant for if, for every ,
This condition concerns a restricted set of directions, and can hold when and is singular. It depends on the chosen support and the cone constant.
Concept lensGeometric
A restricted eigenvalue exists exactly when the kernel misses the cone
Some works for if and only if . If for a nonzero in the cone, then , because forces ; the inequality fails for every positive . Conversely, the set of cone vectors with is closed and bounded, since on it, so it is compact. If the kernel misses the cone, the continuous function is positive there and attains a positive minimum, which is an admissible ; scaling extends the inequality to the whole cone. The analytic inequality is therefore a geometric statement: no direction that the LASSO error can take is invisible to the design.
The main result is deterministic: it assumes a bound on the noise correlations, not a distribution.
Theorem 1.6.2
(Fixed-design prediction bound)
Assume the restricted eigenvalue condition above and the noise event
Then every exact minimizer obeys
No probability assumption is needed for this deterministic statement.
Proof
(Basic inequality, cone membership and the two bounds)
Put and . Comparing the objective at the minimizer with its value at , expanding the square, and canceling gives
The noise event bounds the first term by . On , the reverse triangle inequality gives ; outside the penalty difference is exactly . Thus
In particular . Applying Cauchy–Schwarz and the restricted eigenvalue condition gives . If , divide by ; if , the same bound is immediate. This proves the prediction inequality. The restricted eigenvalue also gives , including when . The cone condition yields , as claimed.
Proof X-ray
Why the error enters a cone
The proof uses each hypothesis exactly once. Optimality of supplies the basic inequality; nothing about how the minimizer was found is used, which is why the bound covers every minimizer. The noise event converts the random cross term into .
The key move is the split of the penalty difference over and . On the triangle inequality can only lose , but off , where vanishes, the penalty gains the full . Half of that gain is spent on the noise, and what remains places in the cone: on against off gives the ratio .
Only then does the design enter. The restricted eigenvalue is needed on the cone and nowhere else, which is why it may hold when is singular. The argument closes by a self-bounding step: is bounded by a multiple of , so dividing gives the rate.
The constant is not a universal feature of LASSO: it comes from the choice of one half in the noise event. The inequality gives sufficient conditions, not a claim that every useful design must satisfy this particular condition. The noise event itself cannot be dropped, however.
Counterexample mode
A penalty below the noise level breaks the bound
Claim: once the restricted eigenvalue condition holds, the prediction bound holds for every . Take , , , and , so and . With , the minimizer is the soft-threshold of at level , namely . Its prediction error is , whereas the claimed bound is .
The noise event fails here: exceeds . Repair: take , so that the event holds. With the minimizer is , and the error satisfies the bound .
Turning the event into a probability
The noise event is random once the errors are. A Gaussian tail bound shows how large must be for the event to be likely.
Corollary 1.6.3
(Gaussian calibration of the penalty)
Assume that the entries of are independent with , that each column satisfies , and that the restricted eigenvalue condition holds. For , set
Then the two bounds of the fixed-design theorem hold simultaneously with probability at least , for fixed , , and .
Proof
(Gaussian tails and a union bound)
Each is centered Gaussian with variance . The Gaussian tail bound for variance , applied with , and a union bound over the columns give
On the complementary event, of probability at least , the deterministic theorem applies.
Zero noise may instead be handled directly by the deterministic theorem with any positive . Choosing a smaller penalty may improve empirical fit, but the displayed probability guarantee no longer follows from this calculation. The expression depends on , which in practice may be unknown.
Worked example 1.6.4
(An orthogonal design)
Let , , , and suppose . With , the noise event holds at equality and . Since , minimizing separates into scalar soft-thresholding problems. The unpenalized coefficient vector is , so .
The actual prediction error is , whereas the theorem gives . The coefficient is shrunk even though its coordinate is correctly retained. A bound can be valid and still be conservative; it is not an exact prediction of the realized error.
Worked example 1.6.5
(Reading the calibrated rate)
Take , , , , and . Then and
Substituting into the theorem gives the prediction bound and the bound , both with probability at least . Quadrupling divides the prediction bound by four, to about . Multiplying by one hundred raises only to , so the bound grows to about : the dimension enters only logarithmically.
Why the design condition matters
Worked example 1.6.6
(Identical columns: one fit, many attributions)
Take , , , zero noise, and . The objective depends on the sum through and satisfies . Its optimal sum is , attained by every nonnegative split of between the two coordinates. All these solutions give the same fitted value, yet disagree about which feature matters. For , belongs to the cone and although , so no positive exists. Identical columns can preserve prediction while making attribution impossible.
Common mistake
(Prediction is not exact support recovery)
The theorem bounds prediction and total coefficient error; it does not say that the estimated support equals . Small nonzero coefficients may be removed by the penalty, while correlated noise can introduce other coordinates. Exact support recovery requires further assumptions and a separate argument. Nor does the bound certify the error at a new design point or the error of an approximate numerical solution.
Common mistake
(Using the calibrated penalty with unnormalized columns)
The penalty formula assumes . If the columns instead satisfy , each correlation has variance , and the same only gives the failure bound . For and this is about , which says nothing. Either rescale the columns or multiply by the largest value of .
Exercises with solutions
Quick check
(A deterministic check. Let , , and . Assuming the noise event, find the theorem’s prediction and bounds.)
Solution · Answer
The respective bounds are and . They need not be sharp.
Quick check
(Failure of the event. In the scalar case , , , , and , compute the minimizer. Does the theorem apply?)
Solution · Answer
Soft-thresholding at gives . The noise correlation is , so the theorem’s noise hypothesis fails. With the bound would read , and the error happens to satisfy it: failure of the hypothesis does not by itself make the answer poor. It means only that this proof supplies no certificate; the counterexample above shows that a smaller can make the bound false.
Quick check
(Orthogonal case. If , show that is valid for every support, and derive a sharper prediction bound directly from soft-thresholding on the noise event.)
Solution · Guided solution
For every , . Soft-thresholding with sets all coordinates outside to zero. On , the thresholding operation changes its input by at most , so . The prediction error is therefore at most , a sharper bound for this special design.
Quick check
(Zero signal. Suppose and the same noise event holds. Show that every minimizer is zero, without using a restricted eigenvalue condition.)
Solution · Answer
The basic inequality with gives . Both terms are nonnegative and , so .
The earlier LASSO optimization note explains how to compute and certify an optimizer. This section concerns the additional assumptions needed to relate an exact optimizer to a fixed underlying signal.