Beyond Least Squares: Uniform Approximation and the Hidden Cost of Misspecification
Davide Maran, Csaba Szepesvari
We study the problem of controlling worst-case errors in misspecified linear regression under the random design setting, where the regression function is estimated via (penalized) least-squares. This setting arises naturally in value function approximation for bandit algorithms and reinforcement learning.Our first main contribution is the observation that the amplification of the misspecification error when using least-squares is governed by the \emph{Lebesgue constant}, a classical quantity from approximation theory that depends on the choice of the feature subspace and the covariate distribution.We also show that this dependence on the misspecification error is tight for least-squares regression: in general, no method minimizing the empirical squared loss can improve it substantially. As a second contribution, we propose a method that augments the original feature set with auxiliary features designed to reduce the error amplification. For this method we prove an oracle inequality that shows that the method successfully competes with an ``oracle'' that knows the best way of using the auxiliary features to reduce error amplification.As an illustration, when the domain is a real interval and the features are monomials, we prove that in the limit as $d\to\infty$, our method reduces the amplification factor to $O(1)$. Note that without our method, least-squares with the monomials (and in fact polynomials) will suffers a worst-case error of order $\Omega(d)$ times the one of the best uniform linear approximator.