Polynomial Regression Degree Selection

Why Polynomial Degree Is a Model-Selection Problem

A polynomial regression fit can represent increasingly complicated patterns as its degree rises. A low degree may miss important curvature; a high degree estimates more coefficients from the same data. Degree selection is therefore a concrete instance of structural risk minimization (SRM): compare nested models by balancing fit against complexity.

The central calculation has two parts. The approximation term measures what is lost by restricting the regression function to polynomials of a given degree. The estimation term measures the cost of estimating the coefficients from a finite sample. Under squared-error loss and a fixed design, the expected prediction error separates exactly into these terms. An SRM penalty then favors degrees that balance them rather than selecting the model with the smallest training error.

Nested Polynomial Models and Their Risk

Suppose the observed responses satisfy \(Y_i=f_i+\varepsilon_i\), for fixed inputs \(x_1,\ldots,x_n\), where \(f_i=f(x_i)\). Assume the errors are independent, have mean zero, and have common variance \(\sigma^2\). For degree \(d\), let \(\mathcal P_d\) be the space of vectors obtained by evaluating polynomials of degree at most \(d\) at the observed inputs. Write \(k=d+1\) for its dimension, and restrict attention to degrees for which the polynomial design matrix has full column rank. In particular, \(k\le n\) is necessary when the inputs are distinct.

Let \(P_k\) be the orthogonal projection onto \(\mathcal P_{k-1}\), using the ordinary Euclidean inner product on the \(n\) observed responses. The least-squares fitted vector is \(P_kY\). Define empirical squared prediction error relative to the regression signal by \(n^{-1}\|P_kY-f\|^2\), where \(\|v\|^2=\sum_{i=1}^n v_i^2\).

The next identity is exact under the stated fixed-design assumptions; it is not an asymptotic approximation.

Proof. Since \(Y=f+\varepsilon\), \(P_kY-f=-(I-P_k)f+P_k\varepsilon\). The first vector is fixed, while \(E[P_k\varepsilon]=0\), so the expectation of their cross-product is zero. Also, \(P_k\) is a symmetric idempotent matrix of rank \(k\), and the error covariance matrix is \(\sigma^2 I\). Thus \(E[\|P_k\varepsilon\|^2]=\operatorname{tr}(P_k\sigma^2I)=\sigma^2\operatorname{tr}(P_k)=\sigma^2k\). Expanding the squared norm and dividing by \(n\) gives \(R_k=n^{-1}\|(I-P_k)f\|^2+\sigma^2k/n=A_k+\sigma^2k/n\). \(\square\)

This identity explains why dimension matters: each additional polynomial coefficient adds \(\sigma^2/n\) to expected prediction error in this setting. It also clarifies what is being selected. The best degree for expected prediction error minimizes \(A_k+\sigma^2k/n\), whereas an SRM procedure typically minimizes an empirical fit criterion plus a complexity penalty.

SRM Penalties for Degree Selection

In practice, the approximation errors \(A_k\) are unknown, so minimizing the exact expected risk is not directly available. One instead computes an empirical loss and adds a penalty that increases with model dimension. For squared-error regression, a basic dimension-scaled form is \( \widehat R_k+\lambda k/n\), where \(\widehat R_k=n^{-1}\|Y-P_kY\|^2\) is the training mean squared error and \(\lambda>0\) is a calibration constant. The selected dimension minimizes this penalized criterion over the eligible degrees. The penalty’s role is to keep the training fit from rewarding every additional coefficient automatically.

The exact risk identity above does not by itself prove that a particular empirical penalty yields an oracle guarantee. That requires a suitable calibration and control of empirical deviations, as in the earlier material on penalized selection. Here the focus is the degree-specific approximation-estimation balance and how its scale can guide a dimension penalty.

Balancing Approximation and Estimation

A common smoothness model for polynomial approximation is that, over the eligible degrees relevant to the comparison, the approximation error decreases at a power rate. Write \(s>0\) for the smoothness exponent and suppose \(A_k\) is bounded above and below by positive constant multiples of \(k^{-2s}\). The exponent expresses how quickly richer polynomial spaces approximate the regression signal. For the rate argument, it is important to specify both a positive noise level and a degree range that actually contains the balancing scale.

The upper approximation bound at a dimension near \(k_*\) gives a candidate risk of the order \(k_*^{-2s}+\sigma^2 k_*/n\). These terms have the same scale: from \(k_*^{2s+1}=n/\sigma^2\), \(k_*^{-2s}=(\sigma^2/n)^{2s/(2s+1)}\) and \(\sigma^2 k_*/n=(\sigma^2/n)^{2s/(2s+1)}\). The resulting rate is therefore \((\sigma^2/n)^{2s/(2s+1)}\), which is of order \(n^{-2s/(2s+1)}\) when the positive variance is fixed.

Proof. Choose an eligible dimension \(k_0\) within a fixed multiplicative factor of \(k_*\). Its approximation error is bounded above by a constant times \(k_*^{-2s}\), and its estimation term is bounded above by a constant times \(\sigma^2k_*/n\). The equal-scale identities above imply that its criterion is at most \(B r_*\), where \(B\) is fixed and \(r_*=(\sigma^2/n)^{2s/(2s+1)}\). Since \(\hat k\) minimizes the criterion, its criterion is also at most \(B r_*\).

For any eligible \(k\le k_*\), the lower approximation bound gives \(A_k\ge c k^{-2s}\). If \(k\le a k_*\), then \(A_k\ge c a^{-2s}k_*^{-2s}=c a^{-2s}r_*\). Choose \(a>0\) small enough that \(c a^{-2s}>B\). Such a \(k\) cannot minimize, because its criterion would exceed \(B r_*\). For any \(k\ge b k_*\), the estimation term alone is at least \(\sigma^2 b k_*/n=b r_*\). Choose \(b>B\); again, such a \(k\) cannot minimize. Consequently every minimizer lies between fixed positive multiples of \(k_*\). The upper bound \(B r_*\) and the lower bound from either the approximation term at smaller dimensions or the estimation term at larger dimensions establish the stated minimum-risk order. \(\square\)

Why the Positive-Variance Condition Matters

The rate conclusion depends on \(\sigma^2>0\), not merely on the algebraic appearance of a dimension term. If \(\sigma^2=0\), the expected risk criterion reduces to \(A_k\). Under the example sequence \(A_k=k^{-2s}\) and eligible dimensions \(1\le k\le n\), its minimum occurs at \(k=n\), not at order \(n^{1/(2s+1)}\). Its risk is \(n^{-2s}\), not \(n^{-2s/(2s+1)}\). Thus the positive-noise balancing argument cannot be applied at zero variance.

The eligible-degree condition matters as well. A balancing scale is only operational if the candidate collection contains dimensions near it, and the approximation bounds used in the comparison must hold over the relevant range. In fixed-design regression, one must also preserve full column rank; a degree with more coefficients than observations cannot be treated as an ordinary uniquely identified least-squares model.

Common Mistake

• Claiming the balancing degree without checking the noise level. The incorrect reasoning is that \(A_k\asymp k^{-2s}\) always balances with a dimension term and therefore the optimum must be \(n^{1/(2s+1)}\). That conclusion silently assumes a strictly positive variance multiplying \(k/n\). If \(\sigma^2=0\), there is no estimation term to balance against approximation error. Require fixed \(\sigma^2>0\), and verify that eligible degrees include the comparison scale.
• Calling the training-error minimizer the expected-risk minimizer. Training error is nonincreasing along nested least-squares models, while expected prediction risk includes an estimation cost. Penalization is introduced precisely to address that distinction.
• Reading the rate as an exact finite-sample degree. The scale \(k_*\) is an order statement. Constants in the approximation bounds, the noise variance, integer rounding, and the available degree range affect the actual minimizing degree.