Penalized least-squares estimator ($\hat{\theta }\in \arg {\min }_{\theta }\{\Vert y-X\theta {\Vert }_2^2/n+\lambda J(\theta )\}$)

A penalized least-squares estimator balances squared error with a nonnegative penalty $J$. The Lasso uses the coefficient ${\ell }_1$ norm; graph total variation denoising uses the ${\ell }_1$ norm of endpoint differences. The choice of normalization of the squared loss changes the numerical tuning parameter.

For the identity design and $y={\theta }^{\ast }+z$, comparing the minimizing objective at $\hat{\theta }$ with its value at ${\theta }^{\ast }$ and expanding the squared Euclidean norm proves the displayed inequality, with $h=\hat{\theta }-{\theta }^{\ast }$. This deterministic inequality does not assume any probability distribution for the noise. A bound on the noise inner product turns it into a statistical error estimate.