Feature Representations And Interpolation Risk

Why the Feature Map Matters

An interpolating predictor fits every observed label, but this condition does not generally determine its predictions away from the training points. When there are more coefficients than observations, many coefficient vectors can fit the same sample. Gradient descent from zero selects the minimum-Euclidean-norm interpolating coefficient vector in the linear setting. That selection depends on how the predictor is represented: changing the feature map changes the geometry in which “minimum norm” is measured.

This tutorial compares fixed feature maps on the same sample. The sample labels and the requirement of exact fit stay fixed; the features used to represent the predictor change. The comparison separates two questions: which interpolating function is selected, and what prediction risk that function has under a specified test distribution.

Minimum-Norm Interpolation for a Fixed Feature Map

Let \(X_1,\ldots,X_n\) be training inputs and \(Y=(Y_1,\ldots,Y_n)^T\) their labels. A fixed feature map \(\phi\) takes each input to a vector in \(\mathbb{R}^p\). Write \(Z\) for the \(n\) by \(p\) design matrix whose \(i\)th row is \(\phi(X_i)^T\). A coefficient vector \(\beta\in\mathbb{R}^p\) defines the predictor \(x\mapsto\phi(x)^T\beta\).

Full row rank means that the \(n\) rows of \(Z\) are linearly independent. In particular, \(p\) must be at least \(n\). Under this condition, \(K=ZZ^T\) is invertible. The solution can be written in terms of \(K\), the training Gram matrix: its entry \(K_{ij}\) is the inner product \(\phi(X_i)^T\phi(X_j)\).

Proof. Define \(\beta_0=Z^T(ZZ^T)^{-1}Y\). Then \(Z\beta_0=ZZ^T(ZZ^T)^{-1}Y=Y\), so \(\beta_0\) interpolates. Every other interpolating vector has the form \(\beta_0+v\), where \(Zv=0\). Since \(\beta_0\) lies in the row space of \(Z\), it is orthogonal to every vector in the null space of \(Z\). Therefore \(\|\beta_0+v\|_2^2=\|\beta_0\|_2^2+\|v\|_2^2\), which is minimized uniquely at \(v=0\). Finally, \(\phi(x)^T\beta_0=\phi(x)^TZ^TK^{-1}Y=(Z\phi(x))^TK^{-1}Y\), as claimed. \(\square\)

This formula makes the role of geometry explicit. Even for the same labels \(Y\), another feature map generally changes both \(K\) and the test-point vector \(k(x)\), and hence can change \(\hat f(x)\). Interpolation alone only guarantees \(\hat f(X_i)=Y_i\) at the observed inputs.

Worked Comparisons on the Same Sample

A Risk Decomposition for a Representable Regression Function

A useful comparison separates the effect of fitting noisy labels from the effect of the test distribution. Suppose, for one fixed feature map, the regression function is represented as \(f^*(x)=\phi(x)^T\beta^*\). The observed labels are \(Y=Z\beta^*+\varepsilon\), where the noise vector \(\varepsilon\) has conditional mean zero and conditional covariance \(\sigma^2 I_n\) given the training inputs. Assume \(Z\) has full row rank and that the test feature vector has finite second moments. Define \(\Sigma=E[\phi(X)\phi(X)^T]\) for an independent test input \(X\), and define prediction risk against the regression function by \(R=E[(\hat f(X)-f^*(X))^2\mid X_1,\ldots,X_n,\varepsilon]\).

Proof. By the minimum-norm formula, \(\hat\beta=Z^T(ZZ^T)^{-1}(Z\beta^*+\varepsilon)=P\beta^*+Z^T(ZZ^T)^{-1}\varepsilon\). Consequently, \(\hat\beta-\beta^*=-(I-P)\beta^*+Z^T(ZZ^T)^{-1}\varepsilon\). For any fixed coefficient error \(u\), the test risk is \(E[(\phi(X)^Tu)^2]=u^T\Sigma u\), by the definition of \(\Sigma\). Averaging this quadratic form over \(\varepsilon\), the cross term vanishes because \(E[\varepsilon\mid X_1,\ldots,X_n]=0\). The squared bias term is the first term in the result. For the noise term, set \(A=Z^T(ZZ^T)^{-1}\); then \(E[\varepsilon^TA^T\Sigma A\varepsilon]=\sigma^2\operatorname{tr}(A^T\Sigma A)\), using \(E[\varepsilon\varepsilon^T\mid X_1,\ldots,X_n]=\sigma^2I_n\). Substituting \(A\) gives \(\sigma^2\operatorname{tr}(\Sigma Z^T(ZZ^T)^{-2}Z)\). This proves the decomposition. \(\square\)

The projection \(P\) is the Euclidean orthogonal projection onto the row space of \(Z\). Its appearance shows why interpolation does not imply recovery of \(\beta^*\): the minimum-norm fit retains only the component visible in that row space. The matrix \(\Sigma\) then weights coefficient errors according to how much they affect predictions under the test distribution. For two feature maps, both the projection and the test-feature covariance can differ, as can the noise term involving the inverse Gram matrix.

When a Change of Coordinates Does—and Does Not—Matter

Not every change in feature coordinates changes the interpolating predictor. If a feature map is transformed by a common orthogonal matrix \(Q\), so that \(\tilde\phi(x)=Q\phi(x)\) and \(Q^TQ=I\), then all feature inner products are unchanged: \(\tilde\phi(x)^T\tilde\phi(x')=\phi(x)^T\phi(x')\). Thus the training Gram matrix and every test-point vector \(k(x)\) are unchanged, and the minimum-norm predictions are identical. The coefficient norm is also preserved.

A general invertible transformation need not preserve Euclidean lengths or feature inner products. It can change which interpolating coefficient vector has minimum norm and, consequently, the prediction away from the sample. A scalar rescaling of every feature by the same nonzero constant is a special case where the fitted predictor remains unchanged: the coefficient rescales inversely, and the training and test feature factors cancel in \(k(x)^TK^{-1}Y\). Unequal rescaling of feature directions generally does not have this invariance.

Common Mistake: Treating Exact Fit as a Risk Guarantee

A tempting but incorrect argument is: “Both models interpolate the data, so they must have the same predictions and risk.” Interpolation says only that their predictions coincide with the observed labels at the training inputs. It places no such requirement on an unobserved input. The worked examples show that different feature maps can produce different test-point predictions—and different risks—while fitting exactly the same sample.

A second pitfall is to compare coefficient norms across feature maps as though they were directly comparable measures of predictive complexity. The norm is defined in the coordinates of each representation. To understand the resulting predictions, inspect the induced feature inner products, or equivalently the Gram matrix and test-point feature vectors. A small coefficient norm in one representation does not by itself establish lower prediction risk.