Lasso oracle inequalities and tuning

Use the objective in the display, with squared loss divided by twice the sample size and penalty parameter $\lambda>0$. Changing this normalization changes every numerical penalty and threshold, so a tuning formula must identify its convention. Let the true support be $S$ of size at most $s$, and let the coefficient error be the fitted vector minus the truth. Comparing the objective at the minimizer and at the truth gives a basic inequality with a noise inner product and a difference of absolute-value penalties.

Define the noise score as $X^\top\varepsilon/n$. On the event that its maximum absolute coordinate is at most half the penalty, Hölder’s inequality controls the noise inner product by half the penalty times the absolute error norm. The support decomposition bounds the possible penalty decrease by the inside mass minus the outside mass. Combining the two gives $\|X\Delta\|_2^2/n+\lambda\|\Delta_{S^c}\|_1\leq3\lambda\|\Delta_S\|_1$. In particular, the error lies in the previously defined cone, without assuming that the estimator selects the correct support.

Assume the full-error restricted-eigenvalue inequality with constant $\kappa$ on the cone for the true support. Cauchy–Schwarz bounds inside absolute mass by the square root of support size times the full Euclidean error. Combining this with the basic inequality yields the displayed coefficient and prediction bounds. For the absolute error norm, the cone gives at most four times the inside mass, producing the third bound. These constants follow the specified convention and are not universal across differently normalized definitions.

The word oracle reflects comparison with the lower-dimensional problem that would remain if the true support were supplied in advance. The unknown support introduces a logarithmic price in common tuning regimes. The displayed theorem assumes exact sparsity and gives error bounds, not exact variable selection or confidence intervals. If the truth is only approximately sparse, an additional tail or approximation term enters the argument. A small training prediction error also does not imply coefficient accuracy unless the stated restricted curvature holds.

For fixed design columns of Euclidean norm at most $\sqrt n$ and independent Gaussian observation noise with covariance $\sigma^2I_n$, every noise score has variance at most $\sigma^2/n$. A union bound therefore makes the score event hold with probability at least $1-\delta$ when $\lambda=2\sigma\sqrt{2\log(2p/\delta)/n}$, for $0<\delta<1$. Dependence between different column scores is allowed. The noise scale must be known or estimated with an additional justified procedure; the theorem does not make it observable automatically.

Cross-validation targets predictive performance and need not select a penalty satisfying this particular simultaneous-noise guarantee. Conversely, a conservative theoretical penalty can give a numerically loose bound while remaining valid. Optimization error is another distinct quantity: solving the convex objective very accurately does not remove shrinkage bias or poor design geometry. An approximate numerical solution needs its own optimization residual accounted for in the basic inequality. Statistical error, tuning uncertainty, and algorithmic convergence should not be conflated simply because all affect a final fitted vector.