Persistent Overfitting: The Statistical Price of Interpolation

What is the statistical price of fitting $n$ noiseless training examples exactly? In noiseless linear regression with sufficient dimension, requiring interpolation raises the minimax expected population risk from $\Theta (1/n)$ to $\Theta (\log n/n)$, with the same data and linear predictor class. Gradient descent and fixed-dataset SGD incur this statistical price at convergence, matching the minimax rate among interpolating estimators. Yet, on a single instance, their $T$-point prefix averages achieve expected population risk $\Theta (\log n/n^{3/2})$ at $T=n$, followed by a persistent $\Theta (\sqrt{n})$ deterioration to $\Theta (\log n/n)$, even though the iterates never move farther from the target in Euclidean distance. We explain this behavior through shared constraints and missing coordinate penalties. For general realizable quadratics, we sharply characterize how the interpolation price depends on dimension, population trace, and sample rank. Finally, we study how accurately the risk of the converged predictor can be certified from observed data. With $m$ fresh validation examples, the optimal certification scale is $$\begin{gathered} \Theta (\min \\ \log n/n,1/m \\ ) \end{gathered}$$, even when the true risk is zero.