Beyond Least Squares: Uniform Approximation and the Hidden Cost of Misspecification

Thank you for the helpful comments. Your observations are valid, and we will revise the paper accordingly: we will add a brief introduction to ridge regression and clarify the definition of its estimator, as well as improve the presentation of Eqs.(4) and (5).

On the remaining questions:

Can you complete answering Q1 by combining Theorem 9 and Proposition 10? Yes, Theorem 9 and Proposition 10 together provide a complete answer to Q1. We will make this explicit in the final version.

.. more examples besides the polynomial basis .. better denepndence on $d$? Yes, for the Fourier basis, the same algorithm reduces the Lebesgue constant from $O(\log(d))$ to $O(1)$. In the multidimensional case (domain is $N$ dimensional), this grows to $O(\sqrt{d})$ for the so-called spherical summation domain where one controls the multi-dimensional frequencies $k$ involved by their $2$-norm. We will be happy to add these. Interestingly, we are not aware of any characterization of the Lebesgue constant of, say, RBF networks, but we expect bad news (as the well-known ill-conditioned property of RBFs is closely related to exploding approximation errors). While large Lebesgue constants are not frequently calculated, we expect that they may appear commonly even if their values are not known.

Dependence on $\mu$ Note that all the results of the paper, except for Proposition 15 are valid of all choices of $\mu$. It is true that the bounds of the Lebesgue constant in Table 1 only focus on the uniform distribution. The reasons are mostly historical, as the result come from the Fourier analysis or approximation theory literature. We would also note that Proposition 6 allows to generalize all the results for the uniform distribution to any other distribution such that the density ratio is bounded. When the density is unbounded (the distribution has partial support), the uniform approximation error will be uncontrolled.

We thank the reviewer for their comments and the time dedicated to our paper.

On the mentioned weaknesses

W1a To judge significance, given motivation, more empirical work is needed.. Our ultimate motivation is indeed to make an impact on the design of RL algorithms. We reject the notion that the significance of this work can only be judged through empirical results. Significance can also be judged based on whether a work makes meaningful contribution to the theory of relevant methods. We insist that our work falls into this category, which, according to the call-for-papers is well within the scope of NeurIPS. As such, we ask the reviewer to reconsider their position and look at the merits of the paper on its own terms. For this, we would like to note the following (copied from our response to W3 of reviewer bUTv): "We also would like to emphasize that we think that even with the limited experiments the paper could be of great interest to the RL theory community, which, since the seminal paper of Du et al. (ICLR 2020) was struck by the price one may need to pay for misspecification. Our paper not only significantly refines the "dark picture" painted by the paper of Du et al. (namely, that polynomial sample complexity is only possible when the misspecification error is blown up by a factor of $\sqrt{d}$), in that we connect the blow-up factor to the Lebesgue constant associated with the learning setting, which, as we illustrate with examples can be much smaller than $O(\sqrt{d})$, but we also suggest a way of avoiding the blow-up with a novel technique."

W1b no discussion about the experiment in Figure 1 or its methodological choices The covariates are uniformly distributed, the standard polynomial basis is used as described in the caption. The target function (as is visible on Figure 1) is a near-periodic piecewise constant function. We aimed for a moderately challenging target function which is piecsewise smooth, as is common in optimal control/RL (think of Mountain-Car, optimal value function) and we set the sample size high enough relative to the frequency of the "slow" changes in the function so that the estimators have a chance to get a good estimate. Significant Gaussian was added to increase difficulty and illustrate robustness of the methods to noise. We will add this description with precise detailed to the appendix. Our excuse for omitting this description was that we thought that all these choices are perhaps self-evident from the figure, but we realize it is better to include these details. Thanks for raising this issue, which we hope with this we have satisfactorily addressed.

W2 Narrative, presentation, grammar could be improved. Thanks for the constructive feedback which we will take into account in the revision of our paper.

W3 uniform error is rarely encountered in machine‑learning tasks, relevance to RL The papers of Du et al. (ICLR 2020) and Lattimore et al. (2020) established that controlling the uniform error is necessary in RL. The heart of this argument is as follows: in these tasks, ultimately one needs to choose an action with a high value and one is evaluated by the difference between the value of the best action and that of the action chosen. Ultimately, the algorithms thus need to produce value estimates. Even if the optimal action's value is perfectly known, if some suboptimal action's value is overestimated by a large quantity, the resulting value loss can be high. Clearly, it is not sufficient here to have small errors over the action-values on average as this is not sufficient to control the value loss. We have not included this discussion in the paper since it has been presented (formally and in detail) in multiple prior works, but if the reviewer thinks that it would be useful to present this argument, we will try to find a way to add it. See also our response to Reviewer KqBU Q1 for how our bounds specifically help in the RL context.

Q: Could you share any useful insights from your theory that add to existing perspectives on how the way we design models and feature representations to achieve better generalization? The key takeaway for machine learning applications is summarized in three buller points:

1. Uniform error, not average error, is the real bottleneck in data-driven optimization, and it is highly sensitive to the choice of features and the sampling distribution.
2. When it comes to approximating smooth (incuding piecewise smooth) functions, local and/or periodic features (e.g., wavelets, Fourier) are vastly better than for example the standard polynomial basis.
3. The amplification factor can grow with model size: In this case running least-squares methods may not control uniform errors at all. Changing features can help with this.
4. Nontrivial regularization methods such as our BWR methods can "tame" even bad feature maps. The design of these methods should be governed by the need to control the uniform approximation error.

We thank the reviewer for their comments and the time dedicated to our paper.

Q1 Applications to RL. In a large number of RL papers [e.g., 1-6], the algorithms estimate action-value functions based on least squares. These papers all rely on using least-squares approaches based on rollouts to estimate value functions and controlling uniform approximation errors (as noted in our paper, this is known to be unvoidable by the results proven in [1]). In any of these papers an error term of size $C \epsilon$ appears in the final suboptimality bounds, where $\epsilon$ is the uniform approximation error, $C$ is an "error amplification constant". The constant $C$ is either uncontrolled, or is of order $\sqrt{d}$. By our results, $C$ in these results can be replaced by an appropriate Lebesgue constant without changing anything else. If OLS is replaced by BWR, the constant $C$ can be further reduced (at the price of a modest increase of the estimation error term, which will also result in a modest increase of the corresponding term in the final error bounds). We are happy to include a discussion of this (in addition to the existing discussion) if the reviewer feels this would help. However, we also have to be conscious of that including full details would require introducing the settings of the works, which will not only take up a nontrivial amount of space, but may also distract the reader from the main message of the paper.

Q2 Role of Lebesgue constant/lower bound for OLS. As $n\to\infty$, the OLS estimator will return $\Pi_{d,\mu} f$. As such, Theorem 3 provides an asymptotic lower bound in terms of the Lebesgue constant. Combining the ideas in Theorem 3 (i.e., choice of worst-case target function) with finite-sample instance specific lower bound techniques should give rise to a finite-time lower bound. A back-of-the-envelope asymptotic calculation based on the central limit theorem can be used to give a bound that takes the expected form (essentially matching our upper bound). Deriving any of these results will require considerable work, which we leave for future work. We feel, however, that even without providing this lower bound, the reader will agree that it is very likely that even for the finite-sample case the Lebesgue constant should control the error. (We find it intriguing that no known lower bounds for OLS that would be strong enough to build on appear to be available in the literature. The closest/strongest results seem to appear in a surprisingly recent paper [7].)

Q3 Cardinality of data domain and higher order dimension terms. The reviewer’s intuition is essentially correct, and in the most common settings we can rely on a tool even simpler than metric entropy. The bound extends to infinite index sets through a standard covering argument: as noted on line 105, it grows only logarithmically with the Lipschitz constant of the feature map. Moreover, note that in many optimization problems, which are the motivation for the paper, the optimizer is allowed to work only on a finite and relatively small subset of $\mathcal X$, so that we need a good estimation only in those points.

The higher-order polynomial dependence on the dimension appears in a low-order, or "fast" term, and as such, we made no effort to optimize this term. It may be interesting technical work to try to reduce the magnitude of this term. We also note in passing that the same term does not appear for the fixed-design case. We suspect, some cost needs to be paid for working with a random-design.

[1] Lattimore et al. Learning with good feature representations in bandits and in RL with a generative model. ICML, 2020.

[2] Antos et al. Fitted Q-iteration in continuous action-space MDPs. In Advances in neural information processing systems, 2008.

[3] Weisz et al. Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs. NeurIPS, 2022.

[4] Hao et al. Confident Least Square Value Iteration with Local Access to a Simulator. AISTATS, 2022.

[5] Yin et al. Efficient local planning with linear function approximation. ALT, 2022.

[6] Lazic et al. Improved Regret Bound and Experience Replay in Regularized Policy Iteration. ICML, 2021.

[7] Mourtada: Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. Annals of Statistics, 2022.

Thanks for the supportive and insightful review and interesting questions. We will address all the questions and fix all the typos listed in the final version of the manuscript provided the paper gets accepted.

Q1 Is it possible to give general rules of thumb for how many features should be added or which features should be added? We think that using $D\approx d$, i.e., doubling the number of features should work well in many cases. Indeed, we can confirm that this works when the features come from the Fourier and polynomial basis functions (e.g., Theorem 14). More generally, we expect this to work as long as approximation errors (of continuous functions) decay at a polynomial rate. This fact is stated, even if somehow hidden, in the works that we cite about De La Valleè Poussin methods, and directly translates to our approach (which is stronger since it is automatically able to "guess" the oracle weights).

Q2 How does the BWR method compare to kernel (ridge) regression (with a kernel function that can be expressed a weighted sum of basis functions)? Could a version of the BWR method be used to learn a kernel function (e.g. by representing the kernel function as a weighted sum of basis functions, and then fitting these weights)? Indeed, all our metods work with the projection operator, which is indeed the convolution with a kernel. Our approach in deriving the estimator BWR may be seen as a way to find the optimal regularization of the kernel from empirical data, in order to compete with the performance of an oracle, as the reviewer suggests. The exact details of this remain challenging as one needs to address a number of statistical and computational issues that arise. We are nevertheless optimistic that the method can be extended to this case.

Q3 Since the error bound for BWR depends on $D$ instead of $d$, should one expect BWR to perform worse than OLS when the sample size is small relative to $D$ (and the misspecification is sufficiently small)? If so, do the error bounds in the paper give an indication of how large and/or the misspecification level has to be before BWR should outperform OLS?

If we allow ourselves to compare upper bounds, we can conclude the following: The terms in play are the estimation error (EE), and the amplified misspecification error (AME). BWR increases EE by a factor of

$\phi_{2,D}/\phi_{2,d}$ (dropping overline due to limited markup), while it decreases the AME. In particular, the misspecification error is not increased, while the amplification factor may be drastically reduced. To get a simple answer, ignoring constants, higher order terms and log factors, assuming $\phi_{2,d}$ $= \sqrt{d}$, we find that EE for OLS is $\sqrt{d/n}$, and it is $\sqrt{D/n}$ for BWR.

We also find that AME for OLS is $(1+\Lambda_{d}) \epsilon_d$, where $\Lambda_d$ is the Lebesgue constant, $\epsilon_d$ is the approximation error when using $d$ basis functions. We also find that AME for BWR is $\epsilon_d$ (simplified best case; see eg Theorem 14). Solving $\sqrt{D/n}+ \epsilon_d \le \sqrt{d/n}+(1+\Lambda_d) \epsilon_d$, we find that BWR "wins" when

$n \ge d (\sqrt{D/d}-1)^2/(\Lambda_d \epsilon_d)^2.$

Now, if we choose $D=2d$ (cf. Section 5), the condition, ignoring constants, becomes $n\ge d/(\Lambda_d \epsilon_d)^2$. Here, what is important to realize is that as $d\to\infty$, $\Lambda_d \epsilon_d$ may not converge to zero, as is the case for the polynomial basis functions for target functions for which $\epsilon_d = \Omega(1/d)$. For cases like this, the condition essentially becomes $n = \Omega(d)$. The worst-case for our method is when $\Lambda_d =1$. In this case, the threshold for $n$ is $d/\epsilon_d^2$.

However, perhaps a more charitable view of the method, which we hope will be appealing to many, is that with $D=2d$, it never loses only minimally compared to OLS (by a factor of $\sqrt{2}$ on the EE), while in cases of poor basis functions, it may gain much. In this view, BWR acts as an insurance strategy where potentially very large errors are drastically reduced while errors are never increased by much compared to OLS.

We thank the reviewer for their comments and the time dedicated to our paper.

W1: We acknowledge that the linear case is limiting and that it remains to be seen whether our findings have any relevance to the more general, non-linear case. We still think that this setting is worthy of being studied thoroughly, despite the acknowledged limitations for the following reasons: (i) The linear setting is the simplest case where generalization (function approximation) happens. As such, it makes sense to investigate the linear case first. Accordingly, much attention have been spent to this setting in the theoretical RL/bandits literature. If one does not understand the linear case, there is little hope one will understand the nonlinear case. Some of the insights gained may in fact generalize to the nonlinear setting. This has been the case for a number of related problems (ie exploration can be addressed by optimism and without optimism of the right form, exploration algorithms remain statistically intractable). In our case, we think that some take-home message of this paper may also apply in the general case: In the limit of infinite data, learning can be seen as a map from data-distributions to regression functions. A fundamental insight of this paper is that extrapolation errors are essentially controlled by the discrepancy between this map and the $L^\infty$ projector. Another insight of this paper is that there can be better ways of using extra learning capacity than the naive approach. Combined with tools such as the NTK approach, one may hope to derive effective methods that also help in the nonlinear case, though. We will be happy to add a discussion of this to the paper, though the details will need to be left for future work.

W2: We agree that missing proofs would be a serious flaw. All proofs, 47 pages in total, are included in the Supplementary Material zip file, which was uploaded with the submission. Another reviewer's review confirms that the zip file is accessible to them.

W3: The goal of this work is primarily theoretical: we identify an intrinsic limitation of all squared-loss based empirical‑risk‑minimisation estimators in the uniform norm and propose a provably optimal remedy. The synthetic experiment in at page 8 already illustrates the phenomenon visually and confirms the theory. A full‑scale RL or bandit benchmark is certainly interesting, linear features (e.g., polynomial or Fourier bases) are standard in those settings, but such an evaluation would require introducing many additional domain‑specific concepts and would distract from the paper’s core contribution. Nevertheless, we plan to conduct this evaluation and follow-up our paper with an empirical counterpart in the future. We also would like to emphasize that we think that even with the limited experiments the paper could be of great interest to the RL theory community, which, since the seminal paper of Du et al. (ICLR 2020) was struck by the price one may need to pay for misspecification. Our paper not only significantly refines the "dark picture" painted by the paper of Du et al. (namely, that polynomial sample complexity is only possible when the misspecification error is blown up by a factor of $\sqrt{d}$), in that we connect the blow-up factor to the Lebesgue constant associated with the learning setting, which, as we illustrate with examples can be much smaller than $O(\sqrt{d})$, but we also suggest a way of avoiding the blow-up with a novel technique.

Q1 For many basis function sequences, such as the Fourier or standard polynomial basis, choosing $D=d$ (ie doubling the number of dimensions) is provably sufficient, as we demonstrate it in our paper. The worst-case cost of the subgradient method used to solve the optimization problem in BWR (cf. Theorem 12) can still be relatively high ($O(d^2)$ for Fourier and $O(d^3)$ for polynomials; due to the different value of $\widehat \phi_{D,2}$)). However, we only need a low-accuracy solution to the optimization problem (ie in Theorem 12 we can take $\varepsilon=O(1)$), and as such, we observed that running the subgradient method was not the bottleneck. A more general idea is to use model-selection to tune $D$, following, e.g. [1], where the compute cost was also taken into account. However, more work is needed to see whether ideas like in this paper apply to our setting.

Q2 Yes, the reviewer is right, we will correct as soon as possible. Thanks for spotting it!

[1] Agarwal, Alekh, et al. "Oracle inequalities for computationally budgeted model selection." Proceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 2011.