Lasso Oracle Inequalities and Convergence Rates

Lasso picks a sparse set of predictors out of possibly thousands of candidates, but why should you trust the resulting estimate rather than dismiss it as noise-fitting? An oracle inequality is a theorem that answers this directly: it bounds how far Lasso's prediction error can be from the error of an oracle estimator — a hypothetical procedure that already knows exactly which handful of variables truly matter and simply runs ordinary regression on just those. If Lasso's error is provably close to the oracle's, you have a mathematical guarantee it isn't badly fooled by the noise variables sitting alongside the real signal.

The typical guarantee, under a condition on how correlated the candidate predictors are (roughly: no small group of irrelevant variables can mimic a true predictor too closely), is that Lasso's prediction error shrinks at rate proportional to $\frac{s \log p}{n}$, where $s$ is the number of truly relevant variables, $p$ is the total number of candidates, and $n$ is the sample size. In plain English: error falls with more data ($n$) exactly as you'd hope, and the price of searching among $p$ candidates instead of knowing the $s$ relevant ones in advance is only a logarithmic penalty — searching among a million candidates instead of a thousand costs a factor of about 2, not 1,000.

That $\log p$ term is the celebrated result: it's why Lasso can work even when there are vastly more candidate predictors than observations, so long as the true model is sparse and the predictors aren't too collinear.