Why a Norm-Penalized Comparison Is Useful
Penalized least squares is often introduced through a particular penalty, such as the Euclidean norm or the maximum norm. A useful comparison, however, does not require a special formula for the penalty or a closed-form estimator. It follows directly from the defining minimization problem and the way noise interacts with the penalty’s norm.
The resulting bound separates three ingredients: the comparator’s approximation error, the size of its penalty, and the noise measured in the dual norm. This makes the result applicable even when the fitted vector is difficult to calculate explicitly. The bound concerns prediction at the observed design points; it is not, by itself, a bound on prediction at new points.
Setup and Definitions
Let \(Y,f,\varepsilon\in\mathbb{R}^n\) satisfy \(Y=f+\varepsilon\). Here \(Y\) is the observed response vector, \(f\) is its mean vector, and \(\varepsilon\) is the noise vector. For a vector \(u\in\mathbb{R}^n\), define its empirical squared distance from \(f\) by \(n^{-1}\|u-f\|_2^2\). Let \(\mathcal C\subseteq\mathbb{R}^n\) be a nonempty candidate set, and let \(\Omega\) be any norm on \(\mathbb{R}^n\). For a fixed penalty level \(\lambda\geq 0\), consider a minimizer \[ \hat f\in\arg\min_{u\in\mathcal C}\left\{\frac{1}{n}\|Y-u\|_2^2+\lambda\Omega(u)\right\}. \] We assume that such a minimizer exists. No convexity of \(\mathcal C\) is needed for the comparisons below.
The dual norm appears because the stochastic term in the least-squares comparison is an inner product with \(\varepsilon\). For example, the dual of the Euclidean norm is the Euclidean norm, while the dual of the maximum norm is the \(\ell_1\) norm. Thus the noise scale depends on the chosen penalty, not only on the size of the noise in an unspecified sense.
The Basic Comparison Inequality
The first result holds for every comparator \(g\in\mathcal C\), without requiring the noise to be small. It displays the noise and penalty contributions before imposing a condition that absorbs one of them.
Proof. By the definition of \(\hat f\), its penalized criterion is no larger than the criterion at \(g\): \[ \frac{1}{n}\|Y-\hat f\|_2^2+\lambda\Omega(\hat f) \leq \frac{1}{n}\|Y-g\|_2^2+\lambda\Omega(g). \] Substitute \(Y=f+\varepsilon\) and expand both squares. After cancelling \(\|\varepsilon\|_2^2/n\) and rearranging, this gives \[ \frac{1}{n}\|\hat f-f\|_2^2 \leq \frac{1}{n}\|g-f\|_2^2 +\frac{2}{n}\varepsilon^\mathsf{T}(\hat f-g) +\lambda\{\Omega(g)-\Omega(\hat f)\}. \] By the definition of the dual norm and the triangle inequality for \(\Omega\), \[ \frac{2}{n}\varepsilon^\mathsf{T}(\hat f-g) \leq \frac{2}{n}\Omega^*(\varepsilon)\Omega(\hat f-g) \leq \delta\{\Omega(\hat f)+\Omega(g)\}. \] Combining these inequalities yields the first assertion. If \(\delta\leq\lambda\), then \((\delta-\lambda)\Omega(\hat f)\leq 0\), while \((\delta+\lambda)\Omega(g)\leq2\lambda\Omega(g)\). This proves the second assertion. \(\square\)
The noise condition has a direct interpretation: the penalty level must be at least the realized dual-norm noise level \(\delta\). If the data are random and \(\lambda\) is fixed, the result holds on the event \(\{2\Omega^*(\varepsilon)/n\leq\lambda\}\). For example, if that event has probability at least \(1-\alpha\), then the comparator bound holds with probability at least \(1-\alpha\). The theorem does not assert an expected-risk bound merely from a high-probability event.
Worked Comparisons
Worked Example: Euclidean Penalty and a Computable Fit
Take \(n=2\), \(\mathcal C=\mathbb{R}^2\), \(f=(1,0)\), and \(\varepsilon=(0.2,-0.1)\), so \(Y=(1.2,-0.1)\). Use \(\Omega(u)=\|u\|_2\) and \(\lambda=0.25\). The dual norm is again Euclidean, so \[ \delta=\frac{2}{2}\|\varepsilon\|_2 =\sqrt{0.2^2+(-0.1)^2} =\sqrt{0.05}\approx0.2236<0.25. \] The theorem therefore applies.
In this example the minimizer can also be calculated. Multiplying the objective by \(n/2=1\) does not change its minimizer, and its form is \[ \frac{1}{2}\|Y-u\|_2^2+\frac{n\lambda}{2}\|u\|_2 = \frac{1}{2}\|Y-u\|_2^2+0.25\|u\|_2. \] For a Euclidean norm penalty this minimizer is zero if \(\|Y\|_2\leq0.25\); otherwise it is \((1-0.25/\|Y\|_2)Y\). Here \(\|Y\|_2=\sqrt{1.45}\approx1.2042\), giving \[ \hat f\approx(0.7924)(1.2,-0.1)=(0.9509,-0.0792). \] Its empirical squared prediction error is \[ \frac{1}{2}\|\hat f-f\|_2^2 \approx\frac{(-0.0491)^2+(-0.0792)^2}{2} \approx0.00435. \] Using \(g=f\) in the theorem gives the upper bound \(0+2(0.25)\|f\|_2=0.5\). It is valid but loose: a comparison bound is a guarantee, not generally the exact risk.
Worked Example: Maximum-Norm Penalty and Its Dual Noise
Let \(n=3\), \(\Omega(u)=\|u\|_\infty\), \(f=(1,0,0)\), and \(\varepsilon=(0.1,-0.2,0.05)\). The dual norm is \(\|z\|_1\): indeed, \(z^\mathsf{T}u\leq\sum_i|z_i||u_i|\leq\|z\|_1\|u\|_\infty\), and equality is attained by choosing coordinates of \(u\) to have the signs of \(z\). Consequently, \[ \delta=\frac{2}{3}\|\varepsilon\|_1 =\frac{2}{3}(0.1+0.2+0.05) =\frac{7}{30}\approx0.2333. \] Choose \(\lambda=0.24\), which exceeds this noise level, and compare with \(g=(0.8,0,0)\in\mathcal C\), assuming \(g\) is in the candidate set. The approximation error and penalty are \[ \frac{1}{3}\|g-f\|_2^2=\frac{(-0.2)^2}{3}=\frac{0.04}{3}, \qquad \Omega(g)=0.8. \] Thus, irrespective of the particular minimizer, \[ \frac{1}{3}\|\hat f-f\|_2^2 \leq \frac{0.04}{3}+2(0.24)(0.8) =0.013\overline{3}+0.384 =0.397\overline{3}. \] The maximum norm in the penalty makes the \(\ell_1\) size of the noise the relevant quantity. Substituting the Euclidean noise norm instead would not justify this comparison.
Worked Example: Choosing a Comparator Balances Fit and Penalty
Let \(n=2\), \(f=(1,1)\), and consider the candidate family \(\mathcal C=\{(t,0):t\in\mathbb{R}\}\) with the Euclidean penalty and \(\lambda=0.1\). For each comparator \(g_t=(t,0)\), the right-hand side of the theorem’s noise-controlled bound is \[ B(t)=\frac{1}{2}\|g_t-f\|_2^2+2\lambda\|g_t\|_2 =\frac{(t-1)^2+1}{2}+0.2|t|. \] For \(t\geq0\), the derivative is \(B'(t)=t-1+0.2=t-0.8\), so the minimum on that range occurs at \(t=0.8\). For \(t<0\), \(B'(t)=t-1-0.2=t-1.2<0\), so \(B\) decreases as \(t\) increases toward zero; this range cannot contain a smaller minimum than the positive-range minimizer.
At \(t=0.8\), the approximation term is \(\{(-0.2)^2+(-1)^2\}/2=0.52\), and the penalty contribution is \(0.2(0.8)=0.16\). Hence \(B(0.8)=0.68\). At \(t=1\), the approximation term is \(0.5\), but the penalty contribution is \(0.2\), giving \(B(1)=0.7\). The slightly less accurate comparator \(g_{0.8}\) produces the smaller overall bound because it has a smaller penalty. The best comparator for the bound need not be the one with the smallest approximation error alone.
What the Bound Does—and Does Not—Say
The theorem gives a comparison against every candidate at once on the noise event. Taking the infimum of its right-hand side over \(g\in\mathcal C\) shows that the fitted vector is controlled by the best available balance between approximation and penalty: \[ \frac{1}{n}\|\hat f-f\|_2^2 \leq \inf_{g\in\mathcal C} \left\{\frac{1}{n}\|g-f\|_2^2+2\lambda\Omega(g)\right\}. \] The first term records how well the candidate set can approximate the mean vector. The second charges for the comparator’s norm, with a price set by \(\lambda\). A larger penalty level can make the noise condition easier to satisfy, but it also increases the price paid for nonzero comparators. Choosing \(\lambda\) is therefore a balance, not a direction to make the penalty as large as possible.
The result is deliberately basic. It does not use curvature, a special structure of the candidate set, or a sharper relationship between prediction error and parameter error. It also does not convert empirical prediction error into error for future observations without further assumptions. Those distinctions matter when interpreting a valid inequality: the target and the conditions in the result must match the claim being made.
Common Mistake
- Using the wrong dual norm or penalty scaling. The noise term is \((2/n)\varepsilon^\mathsf{T}(\hat f-g)\), so its control is \((2/n)\Omega^*(\varepsilon)\Omega(\hat f-g)\). Omitting the factor \(2/n\), or using \(\Omega\) in place of \(\Omega^*\), can give an incorrect penalty threshold. Write out the inner-product bound before setting \(\lambda\).
- Assuming the theorem automatically gives a small risk. The comparator error and penalty contribution can both be large. The inequality guarantees a comparison, but a useful numerical bound requires a suitable comparator and a noise level that the penalty can absorb.
- Treating \(\lambda\Omega(u)\) as a squared-norm penalty. The theorem concerns a norm penalty. Replacing it by \(\lambda\Omega(u)^2\) changes the objective and the resulting comparison; the displayed bound does not transfer unchanged.
Check Your Understanding
Use the definitions and comparison above to answer these questions.
- For the penalty \(\Omega(u)=\|u\|_1\), which norm measures the noise in \(\delta\)?
- In the theorem’s first inequality, why can the term involving \(\Omega(\hat f)\) be discarded when \(\delta\leq\lambda\)?
- If \(\Omega(u)=\|u\|_\infty\), write the noise level \(\delta\) using the coordinates of \(\varepsilon\).
- Explain why the comparator minimizing approximation error need not minimize the theorem’s full right-hand side.
- Does the bound by itself control prediction error at new design points? State why or why not.