Beyond Least Squares: Uniform Approximation and the Hidden Cost of Misspecification
Authors: Davide Maran
Csaba Szepesvari
Venue: NeurIPS 2025 poster ()
Keywords: Uniform error
Regression
Lebesgue constant
Primary area: theory

Abstract: 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 (RL).
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, including regularized least-squares, can improve it substantially.
We argue  this explains the empirical observation that some feature-maps (e.g., those derived from the Fourier bases) ``work better in RL'' than others (e.g., polynomials): 
given some covariate distribution, the Lebesgue constant is known to be highly sensitive to choice of the feature-map.
As a second contribution, we propose a method that augments the original feature set with auxiliary features designed to reduce the error amplification. 
We then prove that the method successfully competes with an "oracle'' that knows the best way of using
the auxiliary features to reduce this amplification.
For example, when the domain is a real interval and the features are monomials, 
our method reduces the amplification factor to $O(1)$ as $d\to\infty$, while 
without our method, least-squares with the monomials (and in fact polynomials) will suffer a worst-case error amplification of order $\Omega(d)$. It follows that there are functions and feature maps for which our method is consistent, while least-squares is inconsistent.

Beyond Least Squares: Uniform Approximation and the Hidden Cost of Misspecification
Davide Maran Politecnico di Milano davide www.napooaaaaaa..ommmm.oo imi
Csaba Szepesvári Google DeepMind and University of Alberta szepiegoogle, com
Abstract
We study the problem of controlling worst-case errors in misspecified linear regres- sion under the random design setting, where the regression function is estimated via (penalized) least-squares. This setting arises naturally in value function ap- proximation for bandit algorithms and reinforcement learning (RL). Our first main contribution is the observation that the amplification of the misspecification er- ror when using least-squares is governed by the 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 the misspecification error is tight for least-squares regression: general, no method minimizing the empirical squared loss, including regularized least-squares. improve it substantially. We argue this explains the empirical observation that some feature- maps (e.g., those derived from the Fourier bases) "work better in RL" than others (e.g.. polynomials): given some covariate distribution, the Lebesgue constant is known to be highly sensitive to choice of the feature-map. As second contribution, we propose a method that augments the original feature set with auxiliary features designed reduce the error amplification. We then prove that the method successfully competes with an "oracle" that knows the best way of using the auxiliary features to reduce this amplification. For example, when the domain is real interval and the features are monomials, our method reduces the amplification factor to (1) as d + oc, while without our method, least-squares with the monomials (and in fact polynomials) will suffer a worst-case error amplifi- cation of order (dd). follows that there are functions and feature maps for which our method is consistent, while ceast-squares is inconsistent.
Introduction
Value function approximation plays central role in modern reinforcement learning (RL) and contextual bandit algorithms [Sutton and Barto, 2018, Lattimore and Szepesvári, 2020]. In many such settings, policies evaluated selected based value estimates obtained by regressing observed returns. To this end, (penalized) linear regression based on empirical squared loss serves core subroutine due to its simplicity and favorable computational properties [Ernst et al., 2005, Antos et al., 2008). A fundamental challenge arises, however, when the true value function or reward model lies outside the span of the chosen features situation referred Recent work by Du et al. [2020] highlighted that in this setting for any d, there are feature maps so that the worst-case prediction error incurred by least-squares regression can be vd larger than the misspecification error, even if the learner can control the covariate distribution." This amplification is concerning because it implies that adding more features may not improve the learner's 's performance
model misspecification.
'Du et al. [2020] prove the stronger result that any learner that has access to polynomially sized sample matter the method they
ought to suffer "large" worst-case prediction
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the misspecification error decreases at rate of ((1//Vd, As such, in the RL and bandits communities much ink was spilled on the implications and the control of error amplification [Lattimore et al., 2020, Dong and Yang, 2023, Amortila et al., 2023, Maran et al., 2024, Amortila et al., 2024].
In this paper, we further investigate this error amplification and suggest method designed dras- tically reduce it. We study this problem in the context of misspecified linear regression under the random design setting, where inputs are drawn from an unknown distribution. Our first contribution is to identify how the amplification of the misspecification error depends directly on the interaction be- tween the sampling distribution and the feature subspace. Specifically, we show that this amplification is governed by the Lebesgue constant- a classical quantity in approximation theory that captures how well the 2-norm projection underlying least-squares regression projects arbitrary functions onto the span of the features. This result provides a significant refinement of previous results in this direction. While prior work established worst-case, feature-agnostic amplification factor of vd (which is known to be tight for some feature maps), our approach identifies the governing principle for this amplification, explaining why the true factor can range from as low as 1 for favorable features. This distinction is critical, as allows for significantly tighter finite-sample guarantees than those derived from the universal v scaling. Moreover, we prove that this dependence on the Lehesgue constant tight: no estimator based on least-squares can substantially improve upon this bound. This sensitivity of least-qquares regression to misspecification is in fact a modern re-emergence of a phenomenon that is well known in classical approximation theory. When polynomial bases are used on equispaced grids, the Runge phenomenon causes the uniform error to explode near the boundary despite good L behaviour, precisely because the associated Lebesgue constants grow in an uncontrolled way. Likewise, in Fourier approximation, the well-known Gibbs phenomenon, although far milder than the Runge blow-up, causes localized oscillatory overshoots near discontinuities [Gottlieb and Shu, 1997].
The disparity in error severity is not accidental. corresponds directly to their differing Lebesgue constant growth rates: logarithmic for Fourier bases, exponential (in the case of equispaced grids) for polynomials. Yet, despite its central role in approximation theory since the early works of Gregory et al. [1848], De La Vallée Poussin et al. [1919] and Szegō [1939], the link between the Lebesgue constant and misspecification error has, to the best of our knowledge, been overlooked in the modern statistical and reinforcement learning literature. In fact, while the superiority of Fourier bases over polynomials for value function approximation has been empirically observed (see Konidaris et al. [2011]) this phenomenon has lacked precise theoretical explanation.
Motivated by this connection to the Lebesgue constant, our second contribution is a method for reducing misspecification error amplification. The approach works by augmenting the original feature set with auxiliary features and then using a weighted ridge regression approach to explicitly regularize the corresponding projection operator to give small error amplification. To illustrate, we show that when the domain is an interval and the base and auxiliary features are monomials, our method reduces the amplification factor to (1) as d + cc. In contrast, standard least squares suffers from arbitrarily large worst-case errors in the same setting.
2 Problem Formulation
We consider the problem of estimating a function with uniform accuracy using a misspecified linear model. We first detail the statistical setting, introduce the standing assumptions and define the performance criterion that will be used in the rest of the paper.
Let IR denote the set of reals, X' be measurable input space, and let f X + R denote an unknown measurable targel (or regression) function that we wish to estimate from a sample D,- = ((11, y1),.., (In, yn)) of independent, identically distributed pairs that belong to X' x IR and which satisfy that almost surely for all i. E [n] == (1,....
f(x,) = [[y][x=]-
We denote the marginal distribution of the inputs x, by μ, while the distribution underlying (#i, (e) is denoted by P.
Assumption 1 (Sub-Gur Gaoo-ia Noise). For some > 0, yı f(x1) is o-subgaussian conditionally on Tt. That is, almost surely.
A E R
-f())))) exp(2
2

---

We are interested in the problem of linear function approximation. That is. the goal is to approximate linear combination of basis functions, PI.....PPP X R. When these clear from the context, for 0 E IR. we let Jo X + IR. be defined via
fo(z) Σ 01p,(z), IEX.
We shall also collect them into feature-map 1p : X Rd and write fo(æ) = where <p(-) (f9 (-).... pp(()) Motivated by the applications mentioned earlier, we depart from the bulk literature in this setting and evaluate performance via the uniform (or maximum) norm. For function g X - R. this is defined l|g]lc supxex [(()]] We let (X') denote the set of functions with finite maximum norm. In what follows, we assume that both f and our basis functions s belong to this set. For f E L (2) and 0 IRd we let
S0 (0, = So ~
())
inf & (), BER
Thus, (6.
(0. f) is the maximum error suffered when approximating with fo. The quantity & (f) represents the best possible uniform approximation error achievable by our basis functions, and its value is unknown to the learner. When (f) > refer to & (J" as the misspecification error. In the next section, we investigate the behavior of the error eo (0,; f) when 0, is the ordinary least-squares (OLS) parameter estimate?
we refer this the misspecifted setting, and
0,. arg min dE
Σ (ye
As we will see, while the OLS estimator is simple, rigorous analysis of its uniform error under misspecification is involved.
3 Characterizing the behavior of OLS
Let == {ffe 8 Rd) denote the subspace of L (X) spanned by the basis functions un- derlying the feature-map sp From now on we assume that the population Gram matrix V f (x)) p(dz) non-singular. As - cc. the Strong Law of Large Numbers ensures that fa. converges almost surely to
nazd == arg min ||g S
gEF
where || [| denotes the I (22 (norm, defined for any measurable X - R by ||l| Sx g" (z))(dx)). Since is probability measure, have 1191 < |lg|13. The map II de- fined in Eq. (1) is the orthogonal projection onto J with respect the L²(x)) inner product and is well-defined thanks to our assumption on the Gram matrix Vz. The map II is linear, idempotent and satisfies TT = for all f E F. Moreover, it is non-expansive in the T.2 npo)
By continuity, the almost sure convergence of the OLS estimate implies that, almost surely, The first question must address is how large ||[l, ooo can be relative to the best possible error, E (.). In other words, by how much is the misspecification error (f) amplified when we use the (2() projection of f onto F? The following classical result provides an answer:
lim,-+oo (Bn, f) f
Lemma (Lebesgue's lemma, e.g., Proposition 4.1 from Chapter 2 of De and Lorentz [1993] )
Let (S. |I]I) l) be a normed vector space, F. subspace of S and II S - S be a linear map such that I(S) C F and II is identity on F. Then, for any S,
Il IIfll < (1+ [[]]] inf ||
gll
gEF
where ||||| == sup I || is the operator norm of
In principle, this minimizer may not be unique; however, it unique under the assumptions required for the results are about show.
A map Il with this property is called projection. Note that orthogonal projections are projections, but there projections of course which are not orthogonal with respect any inner product.

---

When II maps between two normed spaces, (X, xIx) and (Y. -lyy,, we denote its operator norm
by ||]]x_ Applying this result our setting with (S, II) (L (x), ll we obtain
(L
lf I (1 20) inf | gl gEF
where ||TT|| denotes the operator norm ||||| [x))-~>>>>0><<00<>>>> (x) In honor of its discoverer, this quantity formally named as follows:
Definition (Lebesgue constant), For linear operator I1 (X) + L (X),, its induced norm is called the Lebesgue constant associated with II, and is denoted by
A(II= == |||||
sup (
|
Since the Lebesgue constant of our projection operators will be frequently needed, to minimize clutter we introduce the shorthand
Ad,u A(Ilau)
Notably, it is the subspace F-no not the specific feature map used to define that is the fundamental object: JF alone determines the intrinsic misspecification error (f), while its interplay with governs the projection Ia and the amplification factor Ad, With the notation just introduced, Lemma 1 yields the upper bound
Ta,ffll S (1 oz
(2)
easy see that Ad., 2 (consider any nonzero E F). Unfortunately, there no general upper limit on how large this constant can be. Moreoever, the bound in Lemma 1 is essentially tight: Theorem 1. For any e > 0 and any subspace there exist f L (X²) such that
|| - floo 2
- - E
We relegate all proofs to the Appendix. The proof of this specific result can be found in Appendix C.I. Given the tightness of the lower bound established above, we expect any guarantee on the uniform error (0n, f) to inherently involve &o (f). Our main result of this section confirms this.
/)
To state the result, we need one additional quantity characterizing the feature space. Let ( igiis be an orthonormal basis of with respect (m) (obtained, for instance, via the Cram-Schmidi procedure the original basis functions). We let yp X + Rd denote the orthogonalized featuremap defined via (xx = (4
We further define 0d,2 = supzex [/)
While the orthonormal basis (sig is not unique, the quantity da is uniquely defined. In particular (see Proposition 16), it is the (²) + L (X)) operator norm of the projection Id
Da.2 = | (Z())))-)))))
Being j probability measure, Ad,-- I
S [a (ou 00,2
Theorem Let X finite and Assumption I hold. Let be finite and Assumption hold. For any E (0, 1/3] and any n 2 2002,2 log(d/8), the OLS estimate 0n satisfies, with probability at least 1 - 38,
log(1>'1/8)
Eso (0. (1 A ( 3(a + Eo
poly(d, 04,, Eo
The first term in the bound matches the deterministic amplification derived in Eq. (2), accounting for the irreducible approximation gap between IT2,,// and ʃ. The remaining terms bound the additional finite-sample stochastic error. While stated for finite X' for simplicity, the result extends continuous domains standard covering arguments For example, if X [-1, 1] and the basis functions are L. Lipschitt, uniform bound over X' can be obtained by considering e L.p cover of X. This

---

extension incurs only a mild logarithmic factor proportional to log(Lp/ Alternatively, sometimes tighter bound can be achieved by covering the feature set {5(x)) X C. E directly.
Beyond Ad,u. the bound also depends the constant d,,,, which scales with the dimension d. In particular, we show that v2 2 v holds regardless of the chosen feature map (see Proposition 18 in the appendix). The scaling of the terms in Theorem 2 aligns with standard expectations. The first term represents the unavoidable approximation error (bias) discussed previously. The remaining terms quantify the estimation error (variance) due to finite sampling. Specifically, the term that involves a captures the effect of additive noise, while the remaining term accounts for the additional variance induced by the random design, which itself is amplified by the Lebesgue constant and the intrinsic misspecification level. Below we show that when an a priori upper bound e on & (f) is available (as can be the case in certain numerical applications when the target function belongs to some known class of functions, such as a smoothness class), we can obtain a semi-eme gemi-empirical bound. This bound, which relies on data-dependent quantities, has the potential to significantly improve upon the wosst-case bound given in Theorem 2.
A uniform, semi-empirical bound Our purpose here is to bound the uniform error of the OLS estimate using empirical quantities. Let μt, = Σi= Ss, denote the empirical measure associated with the inputs (z1,..., In.). A key advantage of this analysis is that it relies on the empirical Lebesgue constant Ad,p, associated with pa allowing us to drop all assumptions regarding how the inputs are generated (i.e., it applies to fixed design). The empirical operator Il takes the form f(ww))
where and & E Raxd is the design matrix with rows sp (xt). Analogous to the population case, assuming that Vn, is non-singular, we let (fi) be an orthonormal basis of F in L (2(u)), define the
f() == (-(()))))))))))
f, ==
feature map @p X + Rd via (xx) (z), ..... Pa(x)) and let ((m) suprex |1
Theorem 3. Let X' be finite, Assumption I hold, 0n be the OLS estimate. Then, for any fixed 5 > 0, with probability at least 5-
o0ln) d,2 / 2log(2
(θ.) S (1+ Ad,p. (x)
vn
Compared to Theorem 2, this bound offers several improvements: eliminates the lower-order O(1/n) term entirely and it removes the dependence the misspecification error (f) from the leading stochastic term (the 1/vīi term). Furthermore, the population Lebesgue constant Ad, is replaced by its empirical counterpart Ad,pa. which may be smaller than Ad,a- When X is finite, Ad, which is a matrix maximum norm, can be calculated in Onn(x) time.
If the input points (I), (Ii,..., ;,,) can be chosen, one may attempt to optimize this bound directly. Both Ad, and ((o)) depend on f'n- In experimental optimal design, a G-optimal design minimizes ( by carefully selecting pn fundamental result by Kiefer and Wolfowitz [1960] establishes that for n = (dd), there exists a design ph, such that gfn) d.2 = (VV)), which is the best possible scaling.
Assuming that unn G-optimal design, we can compare our result with Proposition 5.1 from Lattimore et al. [2020] (see their equation (2) and the corresponding bound in high probability). Rephrased in our notation, their bound (adapted to high probability with a = 1) states that if μa an optimal design, then
Esc (0n, (Va
dd |log(((x1/8)
+
n
This result is recoverable as special case of our Theorem 2. Indeed, for G-optimal design, (fm)
((m) always holds. In the large sample 4.2 = vd, and it is straightforward to show that Ad,,, S limit (n + 20), the term VdE (f)) dominates their bound. Therefore, our finer bound involving the Lebesgue constant yields strictly better guarantee whenever Ad,ra is smaller than Vd. For example, consider a parlition-bused feature map where each yo; is an indicator function of distinct region X; in partition of X. In this case, Ad, = 1 regardless of μ. offering massive improvement over the worst-case Va-factor. While Proposition 5.1 can be refined to replace Vd by ( in the variance term, this improvement still falls short of recovering the Ad, factor in the bias term.
5

---

Basis functions
μ
Ad,u
Source
Note
Polynomial
uniform on
22(24)
[Quarteroni et al., 2010]
regular d-grid
Polynomials
uniform
(dd)
Verore and Lorentz [1993]
2a 2 d
Fourier
uniform
(log(d))
[Katznelson, 2004, p.59, Ex. Huang [2003]
Continuous B-splines
uniform
((1)
Wavelets
uniform
0(1)
Chen and Christensen [2013]
Table
Examples Lebesgue constants. Domain is X = [-
3.1 The Lebesgue constant: properties and particular cases
While we established with Eq. (3) that Ad, S aa always hold, 0d,2 itself is lower-bounded by vd (see Proposition 18). To find cases where Ad, significantly smaller than vd, we must look at specific feature maps. Table summarizes known results for several classical bases on [-1, 1].
As shown in the table, the Lebesgue constant varies dramatically depending on the basis and measure. Polynomials on regular d-grid exhibit the worst behavior, with exponential growth 22(2 Even with uniform measure, polynomials still suffer from linear growth (d). stark contrast, Fourier series enjoy much slower logarithmic growth Ollg d). It follows that if target function's 1,2 approximation error decreases as (1/d") with some & > O, the additional uniform error incurred by eeast-squares is minimal for d large. Interestingly, reinforcement learning has identified Fourier bases as strong general-
noted earlier, empirical work in choice [Konidaris al., 201 IJ. Our analysis provides theoretical justification for this: their slowly growing Lebesgue constant ensures reasonable error control even under misspecification.
Finally, localized basis functions like wavelets and B-splines achieve the ideal constant scaling (1), independent of d. This makes them excellent candidates when uniform accuracy paramount. We speculate that tile coding, popular localized representation in RL, likely shares these favorable extrapolation properties.
practical limitation of relying on tabulated Lebesgue constants is their dependence on the specific sampling distribution μ.. Calculating these constants is non-trivial, and standard results typically only exist for simple, idcalized distributions (e.g., uniform). The following proposition provides a way to transfer these known bounds other distributions, provided they are not too dissimilar:
Proposition 4. Let μ. be two discrete probability measures supported on countable set X such that for all x E X, 0 < e
p(x) (())
E < C. Then, Nd. C Ad,v-
4 Regularized estimators
Crefthn:lowerbounddne establishes a fundamental limitation of the OLS estimator: its worst-case error is inescapably amplified by the Lebesgue constant. Importantly, this bound holds even in the infinite data limit, meaning the issue is not standard overfitting to finite-sample noise. Rather, the problem stems from the geometry of the L (p) (p)-projection itself: due the rigidity of the feature subspace. minimizing the average eтror can force the projection IL, to exhibit large oscillations entirely absent from the target f. particularly in low-density regions.
natural strategy to dampen such oscillations is regularizing the loss. In the next theorem, however, show that the standard Ridge Regression approach is ineffective for this purpose, even when the ideal orthonormal basis & is known and used.
Theorem 5.
Lei 02 RIDGE be the X A-ridge regression estimate. For any feature map pP())) X + Rd. there exists a target function f L (X) such that, in the infinite data limit,
Eoo (000 RiuGe) = mmxx {(SEn- 2A)Es (f), ( (011)
This result highlights a "damned you do, damned you don't" dilemma for ridge regression. If we choose large penalty À me Ad,u/ to counteract the amplification, the second term in the lower bound

---

approaches 1, preventing convergence even as the misspecification error (f) - 0. Conversely, if small, we essentially recover the poor (A worst-case bound of OLS. Crucially, this phenomenon persists even in the infinite data regime, indicating that it is not merely sample size issue, but geometric defect of the projection operator itself. Consequently, standard techniques designed to achieve small test mean-squared error such as cross-validation or early stopping [Ghojogh and Crowley, 2019]-000 -annoot overcome this fundamental geometric limitation, as they will asymptotically converge to the OLS solution, which is what minimizes the test mean-squared error.
Let us examine why ridge regression fails. The proof of Theorem relies on the explicit form of the corresponding ridge operator TT the infinite data limit:
d.p
p.(z)) / (z)) dp(z))
d.y f(x) = a Σ
Ridge
where a
(4)
1+1 A
Importantly, this is not a projection operator because it does not preserve functions in F. For example, applying this operator to the basis function f = 1 yields an eπrоr of 71 -1 p = A p To obtain an enror bound that scales with the misspecification (f) (i.e., bound that is zero when I E F), every function in F must be a fixedpoint of the operator. Eq. (4), this requires a = 1, which forces X = 0, bringing us back to OLS and its associated amplification problems.
Stabilization via Feature Augmentation Instead of ridge regression, we propose a different approach: we augment the feature map and use the additional degrees of freedom purely "stabilize" the operator, rather than to improve approximation: After all, our bounds depend on both { (f) and Ad Selecting sufficiently many features (x) may be under control; hence, the idea is to use additional features to control Ad Let us denote our original feature map by Pa and its corresponding subspace by Fa. We now augment this map with D d additional features, yielding the extended map Pp. While these extra features could be arbitrary, many standard bases (Fourier, polynomials, splines) have natural nested structure that provides a canonical sequence of extensions.
Let PD denote the orthonormal basis for this extended space obtained via Gram-Schmidt on p with respect I.2 (u)). We now define weighted ridge regression operator on this extended basis. For any sequence of weights À = Ap) E [0, ) let
ITRidge f(x) (o) / (+())((s)) dp(z)
where
0g
(5)
1+ X
Crucially, we want this new operator to serve as a superior replacement for Id while maintaining the approximation power of our original space Fa. We do not aim to target the potentially better (but likely much less stable) approximation of the full space FD. This requirement forces to use zero regularization on the first d components (A; = 0 =
1 for i < d), ensuring that every function in Fa is fixed by the operator. This leads to the set of valid attenuation parameters:
AP = fa E [0, Vi < d. a 13.
(6)
For any a E AP, the operator Ridge fixes every function Fs, thereby avoiding the pitfall of standard ridge regression.
Remark 1 (Connection to Averaging Projections). This formulation generalizes the classical technique of averaging projections to increase stability. For instance, the averuged operator IT exactly equivalent to Eq. (5) with a specific choice of linearly decaying weights a E AD. The intuition is that while individual high-degree projections 11s. may oscillate wildly, these oscillations often cancel out when averaged, leaving a stable estimate. Our framework allows for optimizing these weights directly.
1 D-d+1 El=a
4.1 Weighted ridge estimator and the Oracle Operator
Every operator Ridss with a E AD maintains the elements of the original subspace Fa as its fixed points. Hence, the operators satisfy the conditions of Lebesgue's Lemma (Lemma 1) with F = Fa. Denoting by Aa, the Lebesgue constant of Ridee we immediately obtain the following result:
7

---

Proposition 6. Let a E Al (see (6)) and I be defined as in (5). Then, for any f E (2),,
|| Iidee fo S Aa,
Established in Proposition 6 that the error amplification is governed by Aa. our goal is to select the parameter a E A that minimizes this constant. We refer to this ideal choice as the ORACLE choice:
Oracle
arg min Aa,a
Orucle
min Aa... CEAA
aEAB
Unfortunately, Oraele is unknown to the learner, depends on the unknown distribution j.. The remainder of this section addresses two key questions:
Q1 Can we design a finite sample estimator whose error, for fixed a E A asymptotically scales with Aa...
Q2 Can we design finite sample estimator whose enror asymptotically scales with the optimal A Oraele?
Q1 To answer these questions, we first generalize Theorem 3 incorporate regularization with a chosen parameter a. Although z unknown, we can define an empirical counterpart of operator in Eq. (5) using the empirical measure Pn- Recalling that Φp is the feature map obtained by orthogonalizing yp w.r.t Un, we have
IT Ridge f(-) = Σ ()) 1 Σ (()))(()))
This empirical operator has two key properties: (1) it depends on the evaluations f(zz), and (2) its output is a linear combination of the basis functions P,. Property (1) allows us to estimate Ia ((-) from noisy data by simply replacing the unknown values f(x;) with the observed targets y/- Property (2) ensures that the resulting estimate can be parameterized as (-) 0 for some coefficient vector 0. Specifically, let Rs be the upper triangular matrix from the Gram-Schmidt procedure, such that < = (-) Rg. Letting la = diag(ar) be the the regularization weights matrix, we define estimator follows
On.a = :a:== 11 Σ (z))))
(8)
Theorem 7. Let Assumption hold. Then, for any 8 > with probability
(Gn.a)))) S (1 Aa, (f) o D 2og 21/5)
Vn
This result confirms that amplification error our estimator scales with Aa.a.. To fully answer question Q1, we must show that for large this empirical constant is good proxy for the population constant A Ac... The following proposition establishes this convergence:
Proposition 8. Fix 0. With probability 8, the following bounds holds simultaneously for every a E AD: [0 ( = Ō(0 /og((//)/(//)) and
Vdd0, D.2 voog(1))
(og(1/5)
Vdo% D.2 log(1/0)
A Aa,pl = 5
n
Q2 For this more challenging goal, we must optimize converge the oracle value, despite not knowing true distribution μ.. Our strategy to rely on computable quantities: the empirical operator Ridde (Eq. (7)) and its associated empirical Lebesgue constant Aa,,.. A key observation enables this approach: the Lebesgue constant convex with respect to
Proposition 9. The function J AA (0, +oo) defined by J(a) Aa.a, is convex in

---

Data True function
Dase
Trus furction
0LS cstinota
0LS estmmtar
extmaror
BKR astimator
0-
1.00
-0.50
-225
0.00
Figure 1: Comparison between the OLS estimator and the BWR estimator using polynomial features on [-1, 1], with 10 features (left) and = 15 features (right). The inputs are chosen uniformly at random from [-1, 1]. Even if the true function is bounded, OLS suffers from large oscillations near the boundaries due to the high Lebesgue constant. In contrast, BWR achieves a much more uniform approximation error across the domain by effectively controlling the amplification effect.
This convexity allows us to provably find an approximate minimizer in a finite number of iterations. We employ standard subgradient method [Boyd et al., 2003]: starting from arbitrary E A we iteratively update it until convergence. The details are provided in Algorithm (Appendix D.4).
Theorem 10. Fixe > O. After I = 22 ( 2 (D - d)) iterations, Algorithu I outputs a A
such that ((a inf an J(x) cc.
By definition of J, this result guarantees that a is approximate minimizer of the empirical Lebesgue constant Aa,,, To finally answer Q2, we define the BWR (Best Weighted Regularizer) estimator by plugging (1) into Eq. (8):
1 Epp(E))
BR, R
(9)
n 1=1
Theorem 11. Let Assumption I hold and fix 8 O. Then, with probability 1 5,
Eso & (1 + A Onaele E (f) /DD2//Dogg(HT d 2 log()
This oracle inequality affirmatively answers Q2: estimator is asymptotically able to compete with the Oracle Lebesgue constant.
Case study: polynomial basis
The method introduced in Section 4 aims reduce amplification by explicitly controlling the Lebesgue constant. While broadly applicable, its impact is best illustrated settings where standard estimators suffer from poor uniform behavior. A canonical example is polynomial regression compact interval, where the feature map P. consists of the first d monomials, {1, x,
Consider the standard setting where X [-1, 1] and the data data-generating distribution is uniform on this interval. Even in this favorable scenario, the Lebesgue constant for the polynomial basis grows linearly with the degree, Ad, d. Consequently, the worst-case uniform error for OLS scales as Od Exx (f)). meaning small misspecification enrors can be amplified into large prediction errors.
In contrast, the BWR estimator augments the feature space-for instance, by doubling the degree to D 2d and optimizes the attenuation vector a to minimize the empirical Lebesgue constant. This yields projection operator that preserves the original degree-d polynomials exactly while using the

---

extra degrees of freedom to stabilize the approximation. Theoretically, this reduces the amplification factor from (dd) (1). as the following theorem shows:
Theorem 12. Let y be the uniform distribution on [-1, 11. There exists a constant C > 0 independent of d such that, if we choose D = 2d and 4 (z) = [1, ...... _22611 as the augmented map for the larget space spanned by (a(x)) [1...., x
we have A Oracee
p - C.
This theoretical improvement translates directly to empirical performance, as shown in Fig. While OLS exhibits characteristic large oscillations near the boundaries (a manifestation of the classical Runge phenomenon). B WWR remains stable across the entire domain. By effectively controlling the Lebesgue constant, B WR achieves significantly smaller uniform error despite using the same base features for the final representation.
The above simulations visually demonstrate how the amplification factor is exacerbated by increasing d. We complement them with an asymptotic result showing just how severe this factor can be, even for target functions where the approximation error (x) (f) + 0 as d + cc. In fact, there exist a bounded function that can be uniformly approximated by polynomials, yet for which the OLS estimator diverges with a uniform error roughly of order ((d):
O. Let On be the OLS estimator, and On, be our estimator defined in equation (9). There exists a function f [-1,1] - lK such that, {x(( - 0 as - oc, and under
Proposition 13. Fix
Assumption I with μ = [1[[-1,1] 1]], the following hold with probability one:
lim lim - ()a()))(a(()) 0n BwRlloo =0
while
lim [I - (f(-)-)a(())) Onllo 2 d'= 1-000
d 10000 200
6 Related works
The problem we address, while motivated by the goal of designing principled algorithms for bandits and reinforcement learning. has roots in several fields, including mathematical analysis, econometrics, and approximation theory. We provide a brief overview here, with an extended discussion in Appendix A.
In mathematical analysis the problem of projecting onto linear subspace of (x)) in way that minimizes the uniform error have long been a central topic. Classical results on orthogonal polynomials Szegö [1939] and Fourier series Katznelson [2004] share this goal. More recently, Kobos and Lewicki [2024] proposed an approach for general feature maps. In econometrics, related line of research studies pointwise estimators based on least-squares from noisy samples [Newey, 1997, Belloni et al., 2015, Li and Liao, 2020], which can be naturally adapted to yield uniform convergence guarantees. Most recently, this problem has resurfaced in bandits and reinforcement learning under the name misspecified linear function approximation [Du et al., 2020, Lattimore et al., 2020, Maran et al., 2024, Dong and Yang, 2023, Amortila et al., 2024].
The specific regularization technique we propose in Section is inspired by classical methods for regularizing Fourier series [de la Vallée Poussin, 1918, De La Vallée Poussin al., 1919]. Variants of this technique remain an active topic of study in numerical mathematics today [Németh, 2016, 6, Themistoclakis and Van Barel, 2017, Occorsio and Themistoclakis, 2025].
7 Conclusion
We investigated the problem of uniform error control in misspecified linear regression under the random design setting. Our key insight is that the amplification of & (f) by least-squares methods is governed by the Lebesgue constant, a fundamental concept from approximation theory. We showed that this amplification is tight and intrinsic to the geometry of L'-projection, thereby exposing fundamental limitation of ordinary and ridge least-squares methods, even in the infinite data regime.
To overcome this limitation, we introduced novel regularization framework based on weighted ridge regression over extended feature sets, which preserves the approximation power of the base features while using the auxiliary features to stabilize the projection operator. We proved that this approach allows us to, asymptotically for n + co, compete with the best possible (oracle) projection in terms of uniform error, and we proposed an efficient algorithm for learning such weights from data. In the canonical case of polynomial features, we demonstrated dramatic improvement: from ((d) amplification with OLS to the optimal (1) with our method.
10

---

References
Luigi Ambrosio, Nicola Fusco, and Diego Pallara. Functions of bounded variation and free disconti- nuity problems. Oxford university press, 2000.
Philip Amortila, Nan Jiang, and Csaba Szepesvári. The optimal approximation factors in misspecified off-policy value function estimation. In ICML,, pages 768-790, 2023.
Philip Amortila, Tongyi Cao, and Akshay Krishnamurthy. Mitigating covariate shift in misspecified regression with applications reinforcement learning. In The Thirty Seventh Anmual Conference on Learning Theory, pages 130-160. PMLR, 2024.
Andras Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration in continuous action-space MDPs. In Advances in neural information processing systems, pages 9-16, 2008
Alexandre Belloni, Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Some new asymptotic theory for least squares series: Pointwise and uniform results. Jourmal of Econometrics, 186(2): 345-366, 2015.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208-240. Springer, 2003.
Stephen Boyd, Lin Xiao, and Almir Mutapcic. Subgradient methods. lecture notes of EE392o.
Stanford University, Autumn Quarter, 2004(01), 2003.
Xiaohong Chen and Timothy Christensen. Optimal uniform convergence rates for sieve nonparametric instrumental variables regression. urXiv preprint 13X1v:1311.0412 2013.
E.W. Cheney. Introduction to approximation theory. McGraw-Hin Hill,, 1966.
Ch de la Vallée Poussin. Sur la meilleure approximation des fonctions d' d'une variable réelle par des expressions d' d'orrre donné. CR Acad. Sci. Paris, 166:799-802, 1918.
Ch J De La Vallée Poussin et al. Leçons sur l'approximation des fonctions d'une variable réelle. Paris, 1919.
Ronald A DeVore and George G Lorentz. Constructive Approximation, volume 303 of Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, Berlin, Heidelberg, January 1993.
Jialin Dong and Lin Yang. Does sparsity help in learning misspecified linear bandits? In International Conference on Machine Learning, pages 8317-8333. PMLR, 2023.
Zlatko Drmaž, Matjaž Omladič, and Krešimir Veselić. On the perturbation of the cholesky factoriza- tion. SIAM Journal on Matrix Analysis and Applications, 15(4):1319-132, 1994.
Simon S Du. Sham M Kakade, Ruosong Wang. and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
Benyamin Ghojogh and Mark Crowley. The theory behind overfitting, validation, regularization, bagging, and boosting: tutorial. arXiv preprint UrXiv:1905.12787 2019.
D Gottlieb and Chi- Whin Shu. On the gibbs phenomenon and its resolution. SIAM Rev. Soc. Ind. Appl. Math., 39(4):6444668, December 1997.
Duncan Farquharson Gregory, Robert Leslic Ellis, William Thomson Baron Kelvin, and Nor- man Macleod Ferrers. The Cambridge and Dublin Mathematical Journal, volume 7. E. John- son:fetc., etc.]: Macmillan, Barclay and Macmillan, 1848.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. Foundations of Computational Mathematics, 14:569 600, 2014.

---

Jianhua Z Huang. Local asymptotics for polynomial spline regression. The Annals of Statistics, 31 (5):1600-1635, 2003.
Yitzhak Katznelson. An introduction to harmonic analysis. Cambridge University Press, 2004.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366. 3366,,6,,110 1960.
Tomasz Kobos and Grzegorz Lewicki. On the dimension of the set of minimal projections. Journal of Mathematical Analysis and Applications, 12755), 2024.
Andrei Kolmogoroff. Über die beste annäherung von funktionen einer gegebenen funktionenklasse. Annals of Mathematics, 37(1):107-110, 1936.
George Konidaris, Sarah Osentoski, and Philip Thomas. Value function approximation in rein- forcement learning using the Fourier basis. In Proceedings of the AAAI conference artificial intelligence, volume 25, pages 380-385, 2011.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. Learning with good feature representations in bandits and in RL with generative model. In International conference machine learning. pages 5662-5670. PMLR, 2020.
Jia Li and Zhipeng Liao. Uniform nonparametric inference for time series. Journal of Econometrics, 219(1):38-51 51, 2020.
G.G. Lorentz. Approximation of functions. Athena. New York, Holt, Rinehart and Winston, 1966.
Davide Maran, Alberto Maria Metelli, Matteo Papini, and Marcello Restelli. Local linearity: the key for no-regret reinforcement learning in continuous MDPs. arXiv preprint arXiv:2410.2400 2024.
7solt Németh. De la Vallée Poussin Type Approximation Methods. PhD thesis, Fötvös Loránd University, Hungary, 2016.
Whitney K Newey. Convergence rates and asymptotic normality for series estimators. Journal of econometries, 79(1):147-168, 1997.
Donatella Occorsio and Woula Themistoclakis. De Vallée Poussin filtered polynomial approxima- tion on the half-line. Applied Numerical Mathematics, 207:569-584, 2025.
Allan Pinkus. N-widths in Approxination Theory, volume 7. Springer Science & Business Media, 2012.
Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri. Numerical mathematics, volume 37. Springer Science & Business Media, 2010.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
Gábor Szegö. Orthogonal polynomials, volume 23. American Mathematical Society, 1939.
Woula Themistoclakis and Mare Van Barel. Generalized de la Valléc Poussin approximations [-1, 1]. Numerical Algorithms, 75:1-31, 2017.
Joel Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230 2015.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limits of the paper and the future research directions order address them.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
All the statements are provided with proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We include the code in the supplementary material (very simple, just one very short Jupyter notebook)
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: We include the code in the supplementary material (very simple, just one very short Jupyter notebook)
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nan) cc/
public/ /wwie//guee//eeeeee Code Suiomi ss ssssnoooicyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips, http:/pplllccggill
CoceeoodSSuil Submi ssi iesiooPolli oolycy for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We include the code in the supplementary material (very simple, just one very short Jupyter notebook)
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The simulation is straightforward and its computational time is negligible.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htt /tt///eursppp.pp// cc http:cccccccccccccccccccccccoaaa ines?
Answer: [Yes]
Justification:
The paper is coherent with NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers aw! thcode com da set. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: : / ///nurrips. cc/Conferences / 2025/ LLM) for what should or should not be described.
19

---

A Related Works
Classical approximation theory The idea of approximating a class of functions with a family of vector spaces in uniform sense has always been an important topic in mathematical analysis. On the more general level, this theory takes the name of Kolmogorov's n-width (Kolmogoroff [1936]; see Lorentz [1966] and Pinkus [2012] for more modern formalization). The idea, central to this paper, of finding a linear operator that well approximates the non-linear L projection operator has also been the main topic of multiple line of research. In particular, many result about orthogonal polynomials Szegö [1939] or Fourier Series Katznelson [2004] approximation have this goal. More recently, Kobos and Lewicki [2024] studied the problem for general feature map, investigating the class of linear operators that achieve the lower bound.
Asymptotic pointwise and uniform convergence of LS series in the econometric literature In the econometric literature, the series least squares (LS) estimators have been analyzed primarily through an asymptotic lens: with the sample size n +oo and the basis dimension d + +o0, one studies asymptotic Gaussianity of the estimator of the function in each single point. Newey [1997] provided seminal results for this literature, which were then improved by Belloni et al. [2015], the first to use the Lebesgue constant in this field, and by Li and Liao [2020], who generalize the result to time series data. All these contributions, however, remain asymptotic: they provide limiting distributions or rates without explicit high high-probability bounds, and-crucially- they do not propose algorithmic modifications capable of reducing the amplification factor induced by the Lebesgue constant.
Uniform bounds for linear regression in the context of Online Learning As anticipated in the introduction, the problem of getting - bounds for regression over domain naturally arises in the context of Online Learning with linear function approximation; bandits and RL in particular. Du et al. [2020] established the first dd amplification lower bound in some specific cases, which was then refined by Lattimore et al. [2020], who also derives the corresponding an upper bound of vd. using an optimal design argument. In fact, it can be proved that the factor vd is precisely the maximal Lebesgue constant of any feature map for μ that is the optimal design. These lower bound hold for a worst-case feature map, but allowing the learner to choose the data distribution. Following these works, many papers tried to understand how this amplification factor could be reduced. Maran et al. [2024] shows how to remove it in case of a locally linear feature map; Dong and Yang [2023] improves the v amplification in case of sparsity. Perhaps, the most similar paper to our one is Amortila et al. [2024], which proposes a method mitigate the effect of misspecification w.r.t. the beast-squares fitting. Still, the latter focuses on different objective, i.e. the error under covariate shift (measuring the MSE under distribution v * p). and scales with the density ratio v/-)/u(-). Generalizing to the uniform error would mean to take (-)) as Dirac's delta, which would make this bound vacuous.
De la Valleè Poussin approach The to reduce the Lebesgue constant by adding auxiliary features is rooted in concept that dates back in the history of mathematics to Baron de la Vallée Poussin [de la Vallée Poussin, 1918, De La Vallée Poussin et al., 1919]. The technique he invented is still studied today in numerical mathematics [Németh, 2016, Themistoclakis and Van Barel, 2017, Occorsio and Themistoclakis, 2025).
Finite-sample bounds for ridge regression Hsu et al. [2014] gives finite-sample bounds for ridge regression under random design. The results, when translated into our setting, bound the error between fo. and f where f ;= g o ip and the bound is expressed in terms of f -Iy.af- Here for u E Rd g(u) = f (() where u(dx|u) u)) is the disintegration of μ with respect to the fush-forward of j under yp In particular, for S C X, u E Rdd, p(Slu) = T(x e S, S, = u)p(dr). In the special case when & is injective, f f. Just like in the result that can be extracted from the work of Lattimore et al. [2020], the bounds in this work depend on 04,2 (or )( and scale similarly.
In fact, papers like Lattimore et al. [2020] adopt the following way to bound the uniform error of least squares. Let Vn = E (0xx))p(zz be the Gramian matrix and O, be the vector realizing the 0 projection, that xpxxTe 0, fz). Then each y takes the form ((xx) 0. + =(2,) + mc.
20

---

meaning
(0xx) (0. - 8n) =x(x)²
0. - Vn- Σ ((x))((p(12)) To, +<(())) stoc, part
= <xx)
-v Σ ((()))(())) + stoc. part
1=1 pl()) (onu))"VVVlllaaa ((x))s((x)) + stoc. part. [-=,,((>)
While the stochastic part is bounded as in our Theorems 2 and 3, the one containing the misspecifica- tion is treated as follows
(p(at) 00--0al1
Σ (fx)) V (
(x(x) V/- [=(x))))((
1p(x) Vn (
(1 | 11
-1(((=)llv=
<11p(=)llv_
1|x(x)]lv, (F)
I1(()))((r///))))00))0 Es)
By definition, (Vx/n)-1/22p(1 (xx). Therefore, when making the supremum end up with d.2 E0 (f). As we pointed out in the main paper and also noted by Lattimore et al. [m]
X'
[2020], whatever the choice of (xt); and the feature map, d,2 2 Vd. Therefore, this strategy is doomed to achieve sub-optimal guarantees, whenever Ad,a. < ((d)).
B General-interest results
We start from the usual Bernstein's 's inequality Boucheron et al. [2003], here written for variables that are bounded in [-B, B] and in the "high probability" form.
Theorem 14. Let (xt) be sequence of zero-mean random variable bounded in [-B, B). Let o² >m Var(X,). Then, with probability at least 8
2B
Σ X S 20 log(2/0) +
log(2/8).
3
Lemma 2. Let &a be an orthonormal feature map w.r.l. p.
Expp (x) = Tai
where La is the d- d-dimensional identity matrix.
21

---

Proof. In this proof, let us denote with for i = 1....d. d, the standard basis of R By definition of outer product between two vectors we get what follows.
Eup (Pa()))(a(1)) Reup
(t)
Σ
Exxu [e)( [1ee
1=1 y=1
ΣΣ =1j==
la-
This completes the proof.
Lemma 3. Let {ve]t=1 be sequence of independent d dimenssional random vectors such that
Eluzu, Lla
1 < B.
Let V = Ei ueu. Then,
1. W.p. at least 8
5B log (d/o) ko
Amin (V) 1
ko 2
if (11-) 5B log(d/6) kad
(1-v
$ 1/2.
2. W.p. at least 8
2B log (d/o)
Amax (V) S
1+
ko?
ko2
is 1 [1+1
2B log(d/6) ko
<1. 1.
Proof. Note that, as Amax(Urt) = 111e B, we can then apply Theorem 5.1.1 from Tropp et al. [2015] taking
Amin Mmax ko²
L B,
which ensures that
koR/B
-=
Ve E (0, 1), PP (Amin (V) S (1 E)ko² <d
(11-5)1-6
while
ko? ka²/B
VE > O, IP (Amax 2 (1+ E)Ko?) <d
(1+
The thesis is going to follow by just simplifying the previous expressions. We recall from elementary Taylor expansions that
g²
<<0. 0.5 = -E -5-452/5 log(1 =) < -
2
22

---

and
E²
2²
<<l = E
log 10(11+2 + = 5
2
Therefore, we have, for E < 0.5
e
(1 - =)--c =xp( - (1 z) log(1 -E))
Sexp (-e (1 - c)(-c e - 48a /e))
e / 0(s²)) me 15
On the other side, for S 1,
e
(1+ 11+ exp(e (1 +) log(1 + +
c - (1 E) =222)
=xpp(="//2+((<)) -
This tells us that
Ve E 10,1,2), (Amin (V) S (1- - =))ko² S de -ko=="
and
VE E (0, 1), P (Amax (1) 2 (1 (1+e)ko?) - /
We can reformulate the previous results in the high-probability notation. Indeed, taking de de-ko =o" (/BB),, we get
5B
ko²
which entails that
5B log((d//) ko²
(Amin(() S
5B log d/o)
11/ = P
1-
S 8. ho?
ko²
Doing the same for the other result, we get
2B log d/5)
2B log(d/5)
<1
Xmmax (V)
1
S 6, ko²
kg?
ko?
which completes the proof.
Proposition 15. The Lebesgue constant satisfies Ad, = supzex fx ΣL (x)2) du(z).
Proof. See Cheney [1966], chapter 4.
23

---

C Proofs from Section
C.1 Lower bound for LS
Let x arg min geF |J - gl with ties broken arbitrarily. Theorem 1.1 of Chapter 3 in the book of Vore and Lorentz [1993] guarantees that at least one minimizer exists, (As discussed there, uniqueness may or may not hold.)
Lemma 4. We have
| S1lo 2 Ad, 1.
sup
(x(
feJ
Proof. By definition of Lebesgue constant, for every E there function g such that ||L,, 2 (Ad, - E)]l9]loo.
Take f = -oo g. We will use twice that for any h E F, || = -10- 2 infuer (lu- =
[ h oo Now.
Ia - flloo
Id [1o - 9) 1I + gl
Ilo 1 1l + gloo0
11 + gl1x
Id x - ||g||
(Ad, 1 - =-]1gg10o
(Ad. 1 1- gl100
(Ad, - -
(Ad.u =)]lle Ollxo-
The result follows by letting E - O.
Theorem 1. For any E > 0 and any subspace there exist I (2) such that
|/ - floo 2 (Ad, - Eoo
Proof. The result is immediate from Lemma 4.
For the next result we abbreviate Proposition 16.
|| [ by || 12
0u2 sup [0x)]l2= 1l
xEt
Proof. The following equalities hold:
[T 122
sup fl
||
p.(Kf. pi)
sup
[=
sup sup =
(f)
Σ (f) sp)
sup sup
zEX [
sup
sup
(x)
.eX vER ||
sup | |1| 042-
#ex
24

---

In particular, the first is by definition of induced 2 - oc-norm, the second one by definition of projection operator, and the third by definition of infinity norm. The fourth passage follows exchanging the two supremum, while the fifth from Parseval's 's theorem and the sixth one by duality of the two-norm (i.e. for any uz w suppe]|2= (v, un)
C.2 Towards the proof of Theorem 2
Lemma 5. Fix d O, and 200 log(d/6). Let
VR Σ ((x))
Then, Amin((n) 2 n/2.
Proof. The matrices we are summing correspond to ( each one being semi-positive definite with the biggest eigenvalue bounded by 02 almost surely (indeed, u (()()))((()) is maximized for parallel to (x:)) and produces p (xx))) Moreover, as we have seen in Lemma 2,
E
Σ
(()))((
E (())) nda-
These two ingredients allow us to apply Lemma 3 part one, which ensures that with probability at least 1
502 d,2 log(d/0)
Amin ( (Vn)) 2 1 1-V
n,
50 a log(d/5)
1
S 1/2. Therefore, taking n 2 200 d,2 (og(d/)), we get (Vr) 2 n122.
which completes the proof.
Lemma 6. Let ((+) f(-) I.) With probability least 6,
2Ad 2o Vlog(1/8),
( V ((x))(()))) I
Vn
plus a lower-order term depending on n- which takes the form of δ 6n 12/22 (f)) 33/2 d.2 A
Proof. We start rearranging the equation follows
p(z) Σ (prx) = x02)) T
-V/
Σ
((x))((
t=1
( T (Ta + An) Σ ((x))(()))
< ((2)
F (1x))
x(z) T A (ax)))(((t)
1
+
n
For A, == (V./n)-' Ia- To bound both parts, we start by giving result for 1 Σ v ((x))(()))) that holds for one fixed v Rd Indeed,
25

---

1. Every random variable v ((z)) is bounded by 14 (f) a.s.
2. The variance of the same random variable is
Bx~pl(r (()))())))())))))))))(
Emmpl<(x) p(x) ((x)))]
(oo (f))² (p))))((1) ( (<))]
&o (f))²u² T
Co (f))
the main step following from Lemma 2.
So by Bernstein's 's inequality (Theorem 14),
((x))((1)))) Ee (log(1/5) + 2 log(1/6). (10)
vn
3n
We can use the previous equation to bound both parts. For the first, we just take v = pf(=), respects ||u||2 I 0a,,, in Eq. (10) and get
which
(f)02 Vlog(1/0) +
20 20 log(1/6).
(o=)) Σ ((a))( v
Vn
3n
Let us now focus on the second part. Indeed,
(xx))(()))
S Aa2llAnnl2
Σ ((t))(
Now, using Lemma as done in the proof of Lemma have
5 blog(d/0)
| 12 S 0a.1
n
while for the last part we can write
n Σ (()))((a)))
n
(()))()))
sup 1ella
n
((x))(())) + (o
sup |ell 1/m n
where B//" is 1/n covering of the set of vectors such that ||0||2 1. It is well-known that can choose B1/"" so that [B2/m Rs -d so that, making union bound together with Eq. (10), we get
2o0 / /dlog(188) + Vn
E (og(1/5)
Eo
Σ (()))(()))
<
3n
As consequence,
T A, Σ ((x))((()))
t=1
(lo((d/))
(2A /dlog(1/8). +
20 20 (f)
Ad. (f)
< d,2 V
log(1/0) +
VT
3n
= o
- 122 Ezo + -
3/2 do3
This completes the proof.
26

---

C.3 Proof of Theorem 2
Theorem Let X be finite and Assumption I hold. Let X be finite and Assumption hold. For any 8 E (0, 1/3) and any n 2002, log(d/6), the OLS estimate On satisfies, with probability at least
1-36, 36.
E Eo f) (1+ Ae + 3(0 + Ex) log(1>21/8) poly(d, 02.2, Ea
+
Proof. In this proof, let (+) = -() - ( and 7) Yt - ((x)) Moreover, we will call
on the OLS estimator parametrized w.r.t. ip, rather than ip We will also call (-) (p) 0, the corresponding estimated function (which does not change with the parameterization the basis, as only depends on F).
We start making the following decomposition:
( On - f(x)] - 1 (z) 0, 11. u (x)) + |Ild flloo
4 xz) 0n 11 (x) + (1 (o,)
To bound the first part, we let be such that (.) To.. By Assumption 1, the samples take the form 3/ (2x)) To, 0, + (xr) + nhe where (mp) is family of independent subgaussian random variables. By definition, letting Vn Ei= (f the LS solution takes the form (x(x)) T where
On = Vn -1
t=1
Vn
Σ
(Fp))(((())) To. + + Sa,((r)))
1=1
0. Vn
x (xx) + (a,u(z)))
Therefore, we have
(Pa(x) On [T)n(())]
(0(x)) T,," -1 Σ
(p(x)) me
)(x)) Vn
Σ (p)
(11)
We going bound the two terms separately. First, let F. = (Amin (Vn) n/2). From Lemma 5, under the assumptions of this theorem, we have P(E) 2 1 6.
(I) Since 7) independent and subbauussiann conditionally to (x,)²_ (Assumption 1), Lemma 5.4 and Theorem 5.3 from Lattimore and Szepesvári [2020] ensure that, with probability at least 25
4 (x))
Vn
4
(()))
20
(p))) V ((x))) log(1/6)
20 20 [pp x:) 12 log log(1/0)
/ 2lo( (log(1/5)o) (llg(1/))o|((((())1k)) (()))l,,
Moreover, if event E holds.
211x(x))l2 20aa
Vn <
Vn
that the full term is bounded by / 1/2
27

---

This term is bounded by Lemma which, with probability at least 8 gives
2 vn
(0(2) V
Vlog(1/6),
plus lower-order terms of the form pay/d.0a2.aa
Note that, thanks to Lemma 5, event E holds with probability 1 ò under the assumptions of this theorem. Moreover, imposing that both events in (1) and (11) verify, we get, with probability at least 1 35,
P xx) (())TAn - f $ (1 A p(z) 8, [x))
3(0 ( Vlog(1/0)
S &
vn
plus lower-order terms of the form pa (M) This completes the proof.
C.4 Bound scaling with the empirical Lebesgue constant
Theorem 3. Let X be finite, Assumption hold, 0n be the OLS estimate. Then, for any fixed > 0, with probability at least 1 5.
(0) S (1 +1+ EE 00(m) (n) V
Vn
Proof. In this proof, let (() f(-) Id f() and 17t = 3/ f(x)). Moreover, will call é, the
OLS estimator parametrized w.r.t. &o. rather than sp. We will also (.) = (-)) T 0, the corresponding estimated function (which does not change with the parameterization of the basis, as it only depends on F).
The following decomposition holds:
II(() - fa S 11(() 10) + [()) Fa (1 Eo (f) a. Folee
Now, focus the second term. As done in the previous proof of Theorem 2, we let O, be such that p.. f()) = ( To, and <(.) = f(-) - T 0,, In this way, our samples take the form
= ((x)) TO, 0. + ((x,) + Vr.
For any fixed x E X we have
=(()))(())T)
((x))
n
= -(x) T
((xx) + ((x)) +m)
1=1
n
n
= -((x) T0, + (xx)
Σ n
((x))(())) + +())) = Σ p(x)). n
(n)
(11)
Here, the last passage is due to the fact that, being ((-) orthogonal w.r.t. pn((), it follows Σn ((x)) La. Now, we analyze the two terms (I) and (II) separately.
28

---

(1) ((x) Σ ((x))(())))
= =(x) / (())(()) d = (0x)) =
In fact, by definition of orthogonal projection, ((-) orthogonal in I,2 (,2())) to the span of ((-), so to each of its components in particular.
Let look the second term. Since 7/2 independent and -usbbauusian conditionally on (==))=1 Lemma 5.4 and Theorem 5.3 from Lattimore and Szepesvári [2020] ensure that, with probability at least 1 26
(x)) n
(( x
20 (T())) log(1/0)
22 (1) log(11/))
2llog(1/ (2x)l22
Where the second passage comes once again from the fact that 1 Σー ((x)) = la. This proves that (TT) is bounded by (0llooo1))mn-aa Making union bound E X, this entails w.p. 5,
(pr)) ((r)) S \21)og((81/8) 12.
sup 2E
We have proved that
(O) = l1((-) - -.
$ (1 Ao (ʃ) + |[L f(- - -a
< (1+ + E (f) + /2log((21/0)on) 1/2 G2.
C.5 Proofs from Section 3.1
Proposition 17, The Lebesgue constant is bounded by Nd,a S 04.2
Proof. Let f E (X) with If = 1. We have, for any x X.
[a))(())] =
Σ (s. (1.
i=1
Σ (. Σ (.(1)²
< || ||/|=>1// (x) S Ja,2,
the last passage coming from the fact that as p a probability measure, |1/ S [/ follows taking the supremum f.r.
The thesis
D
29

---

Proposition 18. Let Pa : X- - Bd be any feature map, and probability measure. Then,
2 2 Vd.
Proof. The key for this result is to note that, being probability measure, 02.2 2 Ex~D [IF (the supremum of a function upper bounds integral on any probability measure). Then,
0,2 2 V Eump p (x)
EENp (P, [p,()))
BeeD (1
(F TT(La)) Vd.
Where the passage (*) comes from Lemma 2.
Proposition 19. Let X [k] and (p(l)) Xıj. with all the Xiz being independent bounded zero-mean unit variance random variables. Then, if = O(V)), the feature map 4u satisfies
Ad, 00 (llo(())))))
with probability at least 1 Moreover E[Aa,a] 2 ((vd).
Proof. By convenience, we call E kxd the matrix having, as columns, the features of Pa- Precisely, the i-th column of & corresponds to yi. It well-known that, in a finite dimensional space the orthogonal projection operator writes as
a 2 1)
call Pm the m-thh th row of which, by assumption, is random vector of independent entries bounded in B, B] and with variance one. We have
Σ
T T
E T T TT.1
o²Id,
Aa( $ T dB²
At this point, we can apply Lemma 3, that ensures with probability 1 - 28, for k sufficiently large,
5dB² log(d/)) kg²
2dB² (d/o) kg
ko² S Amin ( TT) S Amax (Φ (T)) S 1+
ko²
Now, we can fix in the assumption and rewrite the projection operator the following form
1a == k - (1: ---
T- T
k-1
where A has all the eigenvalues of magnitude less than
5dB3 GdB2 log(d/8)
by the previous result.
kat
We now bound the infinity norm of the two terms separately. First,
30

---

||:
11:00
max 1 m=l1...
|1(
d
max m.......
k n=l
701
1=1
where holds since the infinity norm matrix corresponds the maximum -orm between its rows. Now, note that, as the rows are independent, each variable Σ mm & ns. for m * n is a sum of i.i.d. random variables such that
T ma nas bounded [-B², B²) almost surely.
The variance
E o P )²]==
E T
E E mi E 1.
Therefore, Bernstein's inequality (14) ensures that, w.p. 1
2
mi 2 ni
/2dlog(2/8) +
1og(2/5).
Making a union bound over the x.a ls pairs m + n, we get, still with probability least 1 8,
4B
Vn + m
p Dns S v (og((2200)) +
3 log(2k/8).
(11)
At this point, we simply have, with probability 1 5,
| 1 11 = max
m=l....k
k
n=l
dB²
max
T mn $ nä
m=1 m=l....k
1,
(1I) dB²
4B²
(Adllg((2/0))
1og(2k/8)
max
k
K
I,nfm
4B²
dB²
V lodlog22//0
+
(2g(2k/8) +
3
k
For the second term, we have
1k $4Φ 11 S Sk-
{ m- (A$ Tmm))
max
m= m=1...
k-1 max
| ( ).n
m=1... k
n=1
d.B2
k-
max m=
VT:
dB²
Vk
31

---

where comes from the bound on the eigenvalues of A, Putting everything together, we have proved that
4B² | I (4lk0g22k0) + log(2k/0)
dBa
dB²
(udlog((k/0)+
vk
To show that we cannot go much lower than this quantity, note that, even ignoring the contribution of we have
d
1 s0 110000000 T 11:0
max
$ Φ
met
ni
n=1
i=1
Therefore,
B| ll [o0] se
EE
max
mi
ni
m=
m=l....
k
d
max
E
Lzd
m= I...k
n=1
Σ
Q(vd) = 12(vd).
max
1=1
The last passage comes from the fact that, for & m. have the expected value of the modulus sum of d independent random variables, which grows vd.
Proposition 20. Let μ, be two discrete probability measures supported countable set X such that for all x E X. 0 S
v(w) (())
C. Then, Ad, C Ad
Proof. The following identity holds for the Lebesgue constant
Nda = sup
(0x) (p()) du(2)
2E x
sup / ((())R()))
R(n)) (R()) R( du(2))
=Ex x
sup / 14(x:) -(x)) xx() dp(z),
=EX x
where G(μ)- = fx <x())p(=)]))))))))))))))))>))))) du(z) and R(p) is its Cholesky factor, such that R(u) R(p) =
G(z)); here, the second passage comes from the fact that the Cholesky factor of matrix corresponds the R factor in the QR factorization, which the one giving Graham-Schmide orthogonalization Quarteroni et al. [2010]. In fact, letting ((x) be the basis orthonomalized w.r.t. we have
p(x) (p=)) p (G)) (x))
Note that, by absolute continuity, we have, for any X
32

---

1
du(2)) 0 =
(o())))( (p(x) du(z)
sc / (c()) (foee)o0))) ault)) sp(z) du(z)
/
p(()T (Asoettveee) dote))) sp(=) du(z)
sC
C
с pdx) ( ((e))oee sp(z) de(z)
/
C
с /
(p(xx) G(v))+((())) dv(z).
Passing the supremum, we get the thesis.
D Proofs from Section 4
D.1 Lower bound for standard ridge regression
Lemma 7. Let I1 be the operator defined in this way:
=-) 0x
0x = arg min lIf(-) - (0-)
T01l22 + =110113
(12)
Then, we have
u2a II.
1+1
Proof. We start from the definition of 0x:
0x
arg min [I((-) kp.) T011, + 2l11k
arg min f.) + (.) (p()) Te + A|101|
arg min
[K 122 [|La, (-) (-)) TOll. 211012
where the last passage comes from Parseval's theorem, as Çd. is orthogonal in I,2 the span of 4. while f T T belongs to this vector space. We then write the operator I explicitly:
0^ arg min [
T01 211lN
d
arg min
Σ
(f. (f. -p.)T
+ +1101
i=1
1.2
arg min Σ (( -0) 20.
The last passage holds from Parseval's 's theorem since ;, are orthonormal in L Note that, as the 0 the last minimization problem are disentangled, we can find as explicit solution
(f.7))12 1+1
Ila,f
0^,1
1 1+X X
This completes the proof.
33

---

Lemma 8. Let I1's be defined according to Eq. (12). For every feature map we have
| - 11
Adda - -1
sup feL=(2)
| olloo
1+1
Proof. By definition of Lebesgue constant, for every there function g such that
| = (Ad, -E)lsgloo-
Take f g - g. We have, by Lemma 7,
1 1 1 X
[m f10x
11(1 -)=-__11, (P - 9) 1lbog gl100
= |[(1 + A) -)-11 (1
Ild,a - pd + gloo
| + A) "11 1 ++t x
p + 9
At this point, note that
|1009|000 2111g|ooo
as follows from Using this property, we have
S b1g ll + |1ll1
11g 0l1oo l1g|lo
2|1g|lo0
X
[ | 8l1s0 2
((1 + 1
"Tapp
1+ X Too +
+ 2X 1 + x 119100.
- A)
At this point, using the definition of
1 11g1l00 2
Ad.
1 2A 1+
- -1 11
E
|[Ix - glloo
1 A
1+X
Ad..
1 2A
||/
1+ X
1+ X
Ad. - -
1 21
||TToo] - -f flooo
1+X
1+
The thesis follows letting 0.
Theorem Let dn RIDCE be the > A-ridge regression estimate. For any feature map spa()) : X - Rd there exists target function f (X) such that, in the infinite data limit,
Ese (00.0.oR RIDGE) = [aax {
(Aa. - 22)E (A)) ( (), (0x11)
Proof. Let Fr, be the output of A A-ridge regression, that is the function ((.) 0m, where
O, = arg min DERA
(vp(x))) To 2²) + Ano
St sid μ.
34

---

By the uniform law of large numbers, in the limit, the minimizer fm converges to II I f. the regularized projection operator is defined as follows
IT (+) :-))) 8x
x = arg min IIf() Tf()) T(.)T + 1l101k
We start showing the X+1 have, by Lemma 7,
lower bound. Taking any function in the span of cp(+) with || = 1 we
A
|f - fl = -1f- X+I
To show the other part, use Lemma to define fuucciinn such that
[Ad - 2 2A
[1 -flox
||Ixe - fllmo.
1+
Replacing |I| flloe (f) completes the proof.
D.2 Proofs from Section 4.1
Theorem 7. Let Assumption I hold. Then, for any 8 >> O, with probability 8,
(x, & (1 Aa. Ex + (22.0/22o22))1//00
Vn
Proof. In this proof, let ((-) = -() Ridge [() and f)- yt f(x)) and On be the estimator
corresponding to Ridge in the parameterization of pp (-), so that
pa(-)
11 Ridge f = f-). a.
The following decomposition holds:
II((.) f20))xx < (1(()) TTRidae f()) + [ (() -10)-fan f
S (1 + Aa,, E (f) + | f(.) (-)looo
where we have applied Proposition 6 for Ax- Let us focus on the second term. As in the proof of the previous theorems, we call 0, the vector corresponding to the orthogonal projection over (- so that we have, for every E X
T
Σ
(x:)
= -x) la
(x)) To, + ((x)) + (
= =x)
la
(
n
+ pp(() la-
Toa
((z))
m
+ 1a
m (4x).
By orthogonality, the first term corresponds to
35

---

pD(x) T
1
Σ
p (Tr
(n(m)) 0. Gb(x) T Ia0, BBidge fxx
n1
The second term
( la / <(=)@n(=) dun(z) = 0,
P (2)
la
(x))
m
0 vector
by definition of orthogonal projection. The third term is
1 6b(Z) la -
n ((1),
which can be bounded as the corresponding terms Theorems and 3: as t are independent and --subgaussian subgaussian conditionally (x, -= Lemma 5.4 and Theorem 5.3 from Lattimore and Szepesvári [2020] ensure that, with probability at least
25
pa(x) lan
Σ (almm <
20
log(1/0)
20 2222n-111020 102n-111@,000 ( log(1/6)
Where the only difference w.r.t. the other proofs is the presence of Ta which is erased after the first step since, being a AD. its norm is S This proves that last term bounded by /2 log()10)onn11/2
1/2 2.DD Making a union bound over X' gives, w.p. 1 1-
Medee ((x) [a(x)) < / wollool1///00 1/2 22.
sup
=EX
Putting everything together, we have proved that
Ess ( s &o s (1 (a) D22.D2 log(2X Vn
Proposition 21. Fix 0. With probability 8, the following bounds holds simultaneously for every ::: 10 ( = Ö(0r, /lo///oog///////// and
M Aa,pl= = δ Valb D.2
(1g))
Vd03.
D.2 log(1/5)
Vn
n
We prove this theorem for generic d E N. The result follows for D.
define Vn, := 1. Σn (a:)) Let (a(-)) the basis obtained from &a by Gram-Schmidt orthogonalization w.r.t. Mns the empirical distribution of the {ar)e. As in the main paper, we let R, = Chol(V,, and, since the Cholesky factor corresponds to the matrix given by Graham Schmidt orthogonalization (proposition 3.4 in Quarteroni al. [2010]).
(a(x)) RT, (x(x))
pa(#s) T TTp((x))
(13)
36

---

so that, under this convenient normalization, we can pass from (a((z) to Pa(zz) trough matrix that is exactly the Cholesky factor of V,, In this setting. Theorem 2.1. in Drmač al. [1994]. which provides a stability result for the Cholesky decomposition which, combined with our theorem gives
1 1-0( S Amin (Rx) S Amax (Ra) S 1+ 1
( (0d2//oo(1/00/// log(d)) (14)
We can now proceed with the proof.
Proof. Bounding norm difference
We have measure
sup (1aa(z)) - pu(())l2. #ex
As said, the relation between the two is Pa(x) Pa(x) which also wite as R (((=))
(x))), so that
sup
(1)x()) (2(2))12 sup
II R, ()((22ll
aeX
#EX
At this point, equation (14) ensures that I[ R,,T/22 12-22 = =0 -0 so we
(1/a(x)) - < s s0 Vogg//oo log())) zEX
sup
(15)
A simple yet useful consequence of this result
1a.2 ((m) sup [1)(
sup (=)
(16)
zEd
,Ei
sup
[1)(a())]12 (z)
(17)
zed
< sup
(1pa(z) =a(x))l2
(18)
zed
O 02
(19)
Lebesgue constants difference
Let us bound the distance between the estimated and the true Lebesgue constant, for any Ab.
37

---

11
Napp Aaa
sup
(.)
- sup =Ex x
Σ a.p (x)p()))) du(z))
ZE TI
I sup =ex
(.)
(x) (z) du(z)
sup xEt
(1)
(1)
sup
(1)
019, du(=))
zēX
sup xxX
1
Σ
(x)
Σ
d
0.7 (1)
1=1
Σ
sup xExt
(x)
000 (x) du(=)
1=1
In the following, we call
d
First term :=
sup aEAf .EE
Σ
Σ
(1)
Σ
and
4 -1 -
Second term :=
sup xEA. ,EEX
1 Σ
Σ a a (I))
- (1) du(z))
1=1 1=
1=1
Bound the first term
Fix E AD,
d
First part
(1)
Σ (177
n
(z),
7
T lap)( px(x))
Where, la diag(a)). At this point, we can replace the result of Eq. (13): getting
38

---

First part I
IaP((m))) (
(Pa(z)) - - Rn Ra pp(()))
(1a (x) T
(2)(2))122144 La - R. (m)
This formulation allows us to apply Eq. (14): As La is diagonal matrix with elements in [0, 1]. we have
Hl Rn RnlaR
This gives the following
1 n
First part O
(a(x))|2|11H R, (all Iall@a(()))l2)
1 0a.2/log(11) log(d)
[ [
(220(n) d,2 V log(1/0) log(d) Σm= (x:))l22
Vn.
(220(l)) V log(11/) log(d) n Di 10 (1))
Vn
0220lm d.2
log(110) log(d) n
Vnd
=
Vn
Vdll.20(a) d.2 V log 1/5) log(d)
Vn
Here, the first equality is due the fact that, being &a orthonormal w.r.t. pan we have En (2.))1 nd. This holds uniformly for every a, we have only used the fact that [L
< 1.
Bounding the second term The second term corresponds to
f
& Σ
Second term sup zEX
Σ a (,)
a. (,,,(,))
du(z)
First, we fix X and E AP and use the scalar product to write as
pa(x) la lo - / (p()))))
(20)
39

---

Note that by definition
E Pa(z) [xFa(x=)]]= / Pa(x)) T [aFalz))
Moreover,
Var(IFa(a))
La (
< (L(( La [aFa((z))1]]
= E _ Ta))(())]
=<(x la (p)( (a
-a
= ( I 02.20
where the last step comes from the fact that 1 3 Ia- For the same reason, we also have (p) ( (aF)( I 02 almost surely. These three results allow apply Bernstein's 's in- equality (14) for
X, = (Pa()) Ia (l) Ia
0² Ei= Var (1) (aFa( s n09..
82.2
This gives, with probability at least 6,
20 d.2
X2
$ V
2n 2,2
log(2/6) log(2/6).
+ 3
So, we can bound Eq. (20), which corresponds 1 Σ Xtl, as follows.
Σ (pa(x))apaa(as))) / (a(l))TaPaall du(z) <V
20 log(2/8)
209
log( (2/8).
n
3n
The former holds for any fixed a E Ab. To have uniform bound, let
A' Cover of Ap
E (n)0,,2)
so that log |A'| < d Making a union bound gives, Vo A'
Pa(x) (aF)(xz)) - / ( laFa(2)) du(z)
2d02 2 log log(2n0a./00)
2di2 a.2
log 22m0
3n
To pass to the general case, note that for every a + EEEiaaa L. laFa(=<) - [xx ( (x)(2))dp(()) changes no more than 28.,2 between the two, by definition of cover. Therefore, we have, with probability least over all AB at the same time
Ao there is a' A' such that
40

---

Pa(x) T
[a (P((t) (a (p(())))dp(()
2d0 d,2 log 1og(2n0d,2/0)
2d02 d.2
log log(2n0a.2/0) + 20
71
3n
This means,
do log(1/6)
d log(1/0)
Second term zŌ
+
n
n
Putting the two results together. By the two bounds that we got for the two terms, follows with probability at least 1
ViDla20 (lg(( d,2
d03 log(1/6)
d +
sup Aa,, aEA4
Aapls SÓ δ
+
log(1/6)
Vn
n
n
To end the proof, note that, using Eq. (19), the difference between da.2 and (lv) is of order
O2 Vd.2/log(1//)) so that
Vdlaz0 20000222lloo
[og(1/8)
VdVa,(0a.2 + 82,2 v llo((1/8)/m) log((1/))
d2
Vn
Vn
vd0a 2 (1g(1/5)
Vd03 d,2 log(1 (1/8)
n
Finally, note that, as vd < 0a,, the term before.
Vd0 a log(1/8)
dominates over
do
log(1/6) that we had
D.3 Proofs about gradient method
Proposition 22. The function J A + (0, +00) defined by J(xx) = Da,, is convex a..
Proof. By definition,
J(a) ||M(())
where M(a) = 1 (1)) Therefore, particular
J(x)
sup =EX.
(.))
This function is convex, being the supremum of family of linear functions EL (z)( in a..
Theorem 10. Fixe > 0. After = Ö(c 20(f)) D.2 (D (D-d) d)) iterations, Algorithm I outputs a (1) A
such that (() infae.g J(a) t
Proof. The first step of this proof consists in finding an upper bound for any sub-gradient of a. As said,
41

---

J(x)
sup sEx LE (-1,1
(.)
sup 1E
(n(() T 1.
where la diag(a:) is D x D diagonal matrix and is the n x d matrix having, as rows, @ (xx)) for each = I,...n. At this point note that, by duality
J(a)
sup 1 (x) (-13)
1 1
sup Σ [(D(()) L
n
where Og denotes the 1-th component of (a)
Ta which is 1 vector. Now, assuming" that the supremum is obtained by just one value Is E X, we can compute the gradient as
Vi((a) v 1 Σ
(.,
1a
sign (t) 1,
71
1
n
sign (x. TT (1)))=)))))))))))))))))) T (0)..
7
In the last line, have used the Hadamard product that is defined, for two vectors of length D like @ (1.)) and { the component product, generating another vector of length D. Now, we are going to bound the two-norm of this gradient:
V =
sign (.0 o
sign Sign((@n(a.) (1 [.07))))p(0) o (
[ 2 (6))}
(((x.)2 (a()))
Σ (xxx)² Σ ((())) = PD.2
where the last passage holds since the features (-(-) are orthonormal w.r.t (n).). Under these assumption, namely
J is convex
2. Each sub-gradient has norm bounded by G == ((x))
3. The diameter of the optimization space H.D is R = /D - -d
'if there ties, the argument applied each of them still holds bounding the norm of the sub-gra sub-gradient
42

---

equation (3) on Boyd et al. [2003] guarantees that running the subgradient method for iterations with step size
R
GVe+1
(corresponding to line 7), achieves suboptimality es bounded by
E1 R² + + EZ R + (3og +1) (R/G)VT
2RG (oglog(1)
D2 llg
2 2
VT
vT
Therefore, number of iterations 1 4e 2200! 2 e, In this way, have
(D d) log (40 (n) 2
(D dd) allows ensure
D.2
Ra
inf No - I(a!!)) inf REAR
J(a) Se Se
aEAd
which completes the proof.
Theorem 11. Let Assumption I hold and fix 8 > O. Then, with probability 1
Eoo (0n, S (1 + A Oracle (x) + (DD.2//oog((2)))) ( dD log(
Proof. By Theorem and the definition of 0 B,,WRR
(0n.BWRR) (1 Aoch an Eoo T / log 2x
(21)
Vn
By Theorem 10, for fixed e, we have Aath S miA Aay, +e. Moreover, note that
Oraele
A afinee 1
0D log( (l)))))) @D.v D Dlog( (
A Aafnec Mi
0
Vn
n
1D. Do.2yDloggh Dlog
1n.2 log(1
2 min Azzjun aEAD
Vn
n
1D22 D
loog(
@D log(1< +
AatD) -c-
Vn
n
Replacing this relation Eq. (21) we get the result.
D.4
Gradient method
The algorithm for estimator is called Subgradient Method in the literature, and is presented Algorithm 1.
E Proofs of Section
Theorem 12. Let μ be the uniform distribution on [- 1]. There exists a constant C independent of d such that, if we choose D 2d and (z) 2d 11 as the augmented feature map for the target space spanned by (p((x) [l....,................. have A Oracle C.
43

---

Algorithm Subgradient Method
Require: Feature map PD. d, Number / of iterations Ensure: Sequence a' E AA.
1: Compute PD from Pp via Gram- Cram-Schmiit orthogonalization
2: Define the following loss:
{(a = [I
3: Initialize (0
(e)os)) d)]
4: for to I do
5: Compute step size V
-D-d
62.eVE+1
6: Compute subgradient 9t (J((et))))
7: Update: (C) (f-1)) Tegt
8: if (+) AP then
9: Project: ha (
10: end if
end for
12:
return a = (1)
Proof. See Theorem 3.1 by Themistoclakis and Van Barel [2017]
Proposition 23. Fix y > O. Let On be the OLS estimator, and dg. be our estimator defined in equation (9). There exists a function f: [[-1,1] - R. such that, {x)( + as cc, and under
Assumption I with μ = 11-11, ([1,,11] I]), the following hold with probability one:
lim lim lIf(-) T Bwwlll d-+00 700000
while
lim II(()) - -pa(-) 0n 2 d d 7
Most of the proof of this proposition is about in building the function, that we are calling f()).
The construction of the function in this proof is going to be quite involved. The function is going to be sum of terms of the form (-). The following notation will be used
1. Let d, dimension of the basis function used at step n
2. Let 0,, = =,,7, for a parameter y >> to be defined
3. Let h, width of the mollifier
4. Let M..(.) (./hn,),, where M()) is the standard mollifier, that is, nonnegative function M(-) E - ((-1,1)) with integral one and compact support.
5. (.()) = sg, ()) To, (In)),, where v., such that
Paa. (.) TT, (zn))le 2 sup
IPPd. Fd. - 1.
=E(-1.1)
6. Fn = fn M,
We are able to prove the following lemmas: Lemma 9, For every n,
llf fullra llfn fn Mall S hynd
Proof. In order to perform this proof, we need one result from mathematical analysis. In fact, call bounded variation function X' (-1,1) - such that the following norm bounded
sup Σ (f(()4)) f(x)))-
txah.C CX
well-known characterization this space Ambrosio et [2000] ensures that the former norm equivalent to
44

---

Bl & I + MMM
M
sup (2).
g(x) (())))()))
Now, we can proceed to the proof. First, note that by definition fn the (V((-1,,) 1)) class with Il BV Od,,). Indeed, (-) takes only values in {-1, +11 }. and can only jump between the two values when Pa, (-) Pd, (In) O, which happens at most d, times, the previous is polynomial of degree dn, At this point, by the properties of convolution,
(n(w) - fa * M,.1)) = In * (Mn(y) - 8(y))
= - * ( Mn 8(1) di
Where we have moved the derivative in the first term. At this point, the properties of convolution allow us to say that for any pair of functions 91.92, 11 * 92lle2 I ll9 Therefore, we have
(-)x()) fn Mn(')l2> S 11200MM 1" M.(() 8(1) de
fx(-))BB | Mt)() 5(t) dt
S
12
Sda
At this point, note that by definition (I) 0, its integral is and its support is contained in (-hin hn). Therefore,
0 y 2 hn
5r" (t)()) 5(t) s
2 hn < y hn
0 y S hm
so that its L norm bounded by Ayb This completes the proof.
Lemma 10. For every m S n, and > 0
1im oe S O(tpi
Proof. First, let us examine the smoothness of Fm. Indeed, we have, for any s >
[fmalle- = Il * Mmlle-
[mmaleee (
Therefore, by Jackson's theorem, we have for any
1 Te s -f O(d,,
Theorem 24. For any 7 < 1/4 there is f such that
Lima ||f" 11 1o
45

---

limsupa -5- d
10
> 0.
Proof. Let
5 = Σ (.)
n=1
First part
Fix E > O. As an goes to zero faster than exponentially and () I 1, we can find ng such that
an Fnf()) r Σ ==1
Now, Ene (-) is a finite sum of C (1-1, functions, so it is uniformly continuous, in particular. Therefore, by Stiersseisss theorem, for sufficiently large d,
an Fa
Σ an Fn(
Id
n=l
Putting the two results together, we have proved that, for sufficiently large d,
|1 11,,00
((() 11
Σ
an
fn()))
n=
no
<e/2+
Σ
(n).))
ITd
au f+()
E.
Second part Let us fix and consider
[
1lc
Σ an))())
n=1
Σ In(+) + (el() Idee E anTal))
n=(+1
an Fn())))
anJr(()
n=1
10
n=t++
13
We are going to analyze the three terms separately.
(A) We start bounding the first term from below,
A at I (e)
00 2 04 (ed..ufe--)l... - at
- fe(t)
a.ddr. 01922,1 ||ca, (f((-) - fe(-))llz
anAdi asF2, (Ife(.) fel-))lz>
2 arAdin 4a0 de he.
46

---

Here, the second inequality comes from Parseval's theorem and the last comes from Lemma 9. Note that, for the polynomial basis, P2, R Ade. R de, so we get
the sequent equality from
A 2 a (aede(1- devhe)
This term is BB)
Σ anna(t)
B
nml
Fa()) 10
an
f-1
Σ an Iaee (a()) R=1
Iede Th + tan (1)
The last passage holds as IT Tude oal = (a()) Now, we can apply Lemma 10, E, which ensures
I (d(e((a()) [a + an (1e
B
an
(a(n - Ta) + ann oete
an nml
anAe [n(() -Ile Fa(t) / +an (n))
n=l
an 1o + an |ale
C The last term can be simply bounded due to the fact that 1| 1:
C de
Σ
On
n=t+1
Now, fix any 7 1/4 and take
= 2;
d, = cxp(1///?" hn = 1x==sp(-1((2/xt]] a, =exp(-1/7"
We get
A 2 2 (1 devhhe)
2 B2 (cxp((1 - >)/ -xpp////00000p000-----/--------- -1/(4r
20 exp((1 - 7)/> - exp(11/" 1/(4))))
2 12 (exp((1 - ))// = 22(2
47

---

For term B, we have
BSO
Σ
h an oo
s+ "nn""
0
Σ Og 1
nnm"" On
1-
0
On 1ooopp(ss+t11/))pppppp(p1 + an
0
On (xp(((=++11)))))))))) (1(=)===))///)xp(s///// 100 + an
0
exp(( ()p((ss/21)) 13/7//)))//)) tan
Last term:
CSO
de Σ an 00
(exp(1>>)
Σ exp( n=t+1
exp(-1/9-1)) =0
Σ expl exp(-1//"))
n=
m==
Again, this term satisfies 011), as the term exp(-1/17)) in the last sum decays faster than 2 2-m
where the last passage holds as 2. Therefore we get B < 0 a,)) = 0(1), since a, decays faster than 2- which already generates convergent seqeuence.
All together, these passages prove
I of 2 ((dh--))
I|'" -r- 0.
Therefore, taking this d, sequence entails limsupa
Proof. (of Proposition 13). Let f f defined before, for the specific value of y > 0. Thanks to part of Theorem 24 assumption Esc (f) 4 0 satisfied:
Ex) = |1 o 1o $ 0.
Then, we prove the two theses point by point. Point one: for fixed d, Theorem 1l gives
1D22 D Dlog( (log((x210)) (x105)
@D log(1x(1/))
(1 0n mw..ww.lee..... loc S (1+A A ) (
Oracle
vn
As X' is [1 and the feature map is Lipschitz continuous, we can get rid of the | by covering argument. As + oo, the former gives
lim llf(-) T Bw.wll I (1 + A Oracle (f)..
formally, the result holds for y > 1/4 but, for what we are trying prove, the validity of the statement for y implies its validity for every 7 7, therefore proceed w.l.o.g.
48

---

For -[[11, Theorem 12 ensured that A < C, universal constant independent on d. Therefore,
lim lim |1(0 - (pa(-) On, ,wR loo S lim C) (f)
Let us pass the second thesis:
lim [lf(-) - (a(+)) "Tt.aa()T,oooss/)/ 2 d'
This follows from the fact that, for n - oo, pa(t) ,nS + l.) and that Theorem 24 ensures
lim supa I n llx O.
49


Reviews:
[{"review_id": "LeY4ZLCkL6", "reviewer": "Reviewer_bUTv", "summary": "This paper investigates the problem of uniform error control of ordinary least-squares (OLS) regression in the context of mis-specified linear model — where the true function lies outside the span of the chosen feature set. The task is motivated by applications in value function approximation for bandit algorithms and reinforcement learning (RL), where OLS regression is a standard tool but can suffer from significant error amplification under model mis-specification. The authors provide a sharp characterization of how the amplification of the mis-specification error depends on the interaction between the sampling distribution and the feature subspace, which is governed by the “Lebesgue constant” —  a classical quantity in approximation theory. Moreover, they prove that the dependence on the Lebesgue constant is shown to be tight — no estimators based on empirical squared-loss minimization can substantially improve upon this bound in general. Motivated by these insights, the authors propose a method for reducing the mis-specification error amplification by augmenting the original feature set with auxiliary features and applying a “weighted ridge regression”, optimizing the weights to minimize the empirical Lebesgue constant. The authors offer theoretical guarantees for this novel regularization framework.", "questions": "Q1. For augmentation of auxiliary features to the original feature set (here, the original feature set consists of $d$ basis), we choose some integer $D > d$ and then add $D - d$ features to construct the full feature map $\\varphi_{D} : \\mathcal{X} \\to \\mathbb{R}^D$. In this framework, selection of an overly large integer $D$ will lead to a demanding computational cost since we need to solve a convex optimization problem in high-dimensional settings (the search space has dimension $D - d$). How can we control the trade-off between $D$ and the choice of $D - d$ suitable auxiliary features for the efficacy of the proposed regularization framework?\n\nQ2. In the equation (2), I would like to confirm that the constant in the right-hand side of the inequality should be $1 + \\Gamma_{d, \\mu}$ instead of $\\Gamma_{d, \\mu}$.", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "(a) Strengths:\n\nS1. The paper provides tight upper and lower bounds, showing that the dependent on the Lebesgue constant is intrinsic and cannot be substantially improved by any empirical squared-loss minimization method — the connection between classical approximation theory notions and value function approximation in RL and bandit problems is interesting.\n\nS2. The paper elucidates limitation of standard estimators — the authors show that standard regularization techniques including ridge regression, cross-validation, and early-stopping cannot resolve the geometric amplification of error in LS regression, even with infinitely many data.\n\nS3. The proposed framework based on weighted ridge regression with feature augmentation is novel — it can provably reduce the amplification factor to the oracle level. \n\n\n(b) Weaknesses:\n\nW1. The results are specific to linear function approximation; the paper does not address non-linear models or neural networks, which are increasingly prevalent in modern applications.\n\nW2. The paper does not contain any detailed proofs of their theoretical results in the appendix, even though they seem concrete.\n\nW3. The paper lacks experimental validations to support their theoretical results. Broader empirical validations on real-world datasets would strengthen the practical effectiveness.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and the time dedicated to our paper.\n\n**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. \n\n**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. \n\n**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.\n\n**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. \n\n**Q2** Yes, the reviewer is right, we will correct as soon as possible. Thanks for spotting it!\n\n[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."}, {"review_id": "4E1ajL3gdt", "reviewer": "Reviewer_UvJD", "summary": "The paper studies the problem of controlling the worst-case error in misspecified linear regression. It is shown that for least squares methods, the constant in front of the misspecification error is determined by the Lebesgue constant, which itself depends on both the feature map and the distribution from which the covariates are drawn. Bounds on the Lebesgue constant for polynomial, Fourier and wavelet bases (as well as some others) are presented. Based on the insights that: 1) amplification of the misspecification error is determined by the Lebesgue constant; 2) the Lebesgue constant can be reduced by adding features, the paper proposes a new regularised estimator called Best Weighted Regulariser (BWR), which utilises an extended feature map. It is shown that, for a given extended feature map, the maximum error of the BWR estimator asymptotically matches that of the (a priori unknown) oracle regularised estimator. Finally, there is a case study of misspecified linear regression with monomial features, in which BWR achieves significantly lower maximum error than Ordinary Least Squares.", "questions": "Is it possible to give general rules of thumb for how many features should be added or which features should be added?\n\nHow 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)?\n\nSince 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 $n$ and/or the misspecification level has to be before BWR should outperform OLS?\n\nThe following is a list of typos:\n- In the definition of the Lebesgue constant, there seem to be some extra brackets around $\\|P\\|_{\\infty}$\n- I presume that the factor on the RHS of Equation (2) should be $1 + \\Lambda$ rather than $\\Lambda$\n- Line 95: should $\\hat{\\theta}_n$ be $\\hat{\\theta}_{n,OLS}$?\n- Line 99: “n positive integer” to “positive integer n”\n- Line 150: “to under we have to resort of” to “to understand them we have to resort to”\n- Line 151: “we enumerate few” to “we enumerate a few”\n- Line 191: “this does to corresponds to” to “this does not correspond to”\n- Line 233: Gram-Schmidt typo\n- Eqn (7): lower case $d$ should be upper case $D$\n- Statement of Thm. 5: $\\mathcal{X}$ should be $|\\mathcal{X}|$\n- Statement of Thm. 9 $\\mathcal{X}$ should be $|\\mathcal{X}|$", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\nThe paper is very well-written and the results of the paper are presented very well.\n\nThe problem of misspecified linear regression is interesting and the paper offers several nice insights about this problem and the consequences for methods (such as value function approximation) that use linear regression as a core component. For instance, the fact that the Lebesgue constants of the Fourier basis and localised basis functions are relatively small offers one explanation for the observation that these bases are observed to work well in reinforcement learning problems.\n\nThe proposed BWR method appears to be an effective solution to the problems raised in earlier sections of the paper. In particular, it achieves the goal of asymptotically matching the error bound of the oracle regularised estimator and outperforms OLS in terms of maximum error in the case study.\n\n**Weaknesses:**\nI don’t think the paper has any major weaknesses (though I did not check the proofs carefully).\n\nIt isn’t clear to me that the theoretical results of the paper lead easily to general rules of thumb for how many features one should add or which features should be added for best results.", "was_revised": true, "final_justification": "The paper studies an interesting problem, it provides an effective solution to the problem and is both insightful and well-written. I feel strongly that this paper should be accepted.", "rebuttal": "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.\n\n**Q1** *Is it possible to give general rules of thumb for how many features should be added or which features should be added?* \nWe 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).\n\n**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)?*\nIndeed, 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.\n\n**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?*\n\nIf 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). \nBWR increases EE by a factor of \n\n$\\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}$\n$ = \\sqrt{d}$, \nwe find that EE for OLS is \n$\\sqrt{d/n}$, \nand it is $\\sqrt{D/n}$ for BWR. \n\nWe 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\n$$n \\ge  d (\\sqrt{D/d}-1)^2/(\\Lambda_d \\epsilon_d)^2.$$\n\nNow, 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$. \n\nHowever, 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."}, {"review_id": "pZm7oB6P4z", "reviewer": "Reviewer_KqBU", "summary": "Motivated by the error ampification in RL with linear function approximation, the paper studies $L^\\infty$ oracle inequalities for least-square linear regression problems. The paper identifies ``Lebesgue constant'' -- the $L^\\infty$-operator norm of the $L^2$ orthonormal projection operator -- as a key quantity governing performance of estimators.\n\nThe paper shows the following result\n1. For the OLS estimator, the paper proves an upper bound with an approximation error term depending on the Lebesgue constant and the $L^\\infty$ oracle error, as well as a statistical error term that depends also on the log-cardinality of the data domain.\n2. The paper analyzes the Lebesgue constant by showing upper and lower bounds on some specific choices of basis functions.\n3. Moving beyond OLS, the paper studies regularized and weighted versions of the least-square estimators, with approximation/statistical error guarantees. In particular, the approximation factor now depends on the $L^\\infty$-operator of a weighted version of the orthonormal projection operator. The paper further studies optimization procedures that choose the weight to minimize the approximation factor.", "questions": "I think the paper could be significantly strengthened from the following aspects:\n1. Concrete applications to RL. As the paper motivates the study of $L^\\infty$ oracle inequalities from value learning with function approximation, it would be beneficial to show concrete results to these problems. For example, does the weighted estimator lead to an RL algorithm with better theoretical guarantees?\n2. The role of Lebesgue constant. It is helpful to establish lower bounds showing the necessity of Lebesgue constant, at least for OLS estimator. The current Theorem 3 is just an operator norm characterization.\n3. The statistical error term depends on the cardinality of data domain, which may be infinite in practice. In principle, it should depend on the metric entropy in the infinite case. Also, the bound may not be tight, as it involves a high-order polynomial dependence on dimension.", "limitations": "The paper has some limitations in terms of the scope and the optimality of the results. There are no potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength: The paper presents interesting results that are relavant to a well-known limitation in RL with function approximations. Though the oracle error amplification is already observed in literature, it is nice to see a comprehensive study on this. Moreover, the minimization procedure for the approximation factor is novel and interesting. The paper also illustrates a concrete improvement using polynomial basis.\n\nWeakness: The results are relatively limited to specific setups, and some bounds seem weak. I will explain more in questions section below.", "was_revised": true, "final_justification": "Though there are certain limitations (e.g. consequences to RL, lower bounds, etc), the paper already made considerable contribution given the length limit of a conference paper. The author's response also clarify certain technical details. I think the paper should be accepted and therefore I decide to raise my score.", "rebuttal": "We thank the reviewer for their comments and the time dedicated to our paper.\n\n**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.\n\n\n**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.\n(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].)\n\n\n**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. \n\nThe 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.\n\n[1] Lattimore et al. Learning with good feature representations\nin bandits and in RL with a generative model. ICML, 2020.\n\n[2] Antos et al. Fitted Q-iteration in continuous action-space\nMDPs. In Advances in neural information processing systems, 2008.\n\n[3] Weisz et al. Confident Approximate Policy Iteration for Efficient Local Planning in $q^\\pi$-realizable MDPs. NeurIPS, 2022.\n\n[4] Hao et al. Confident Least Square Value Iteration with Local Access to a Simulator. AISTATS, 2022.\n\n[5] Yin et al. Efficient local planning with linear function approximation. ALT, 2022.\n\n[6] Lazic et al. Improved Regret Bound and Experience Replay in Regularized Policy Iteration. ICML, 2021.\n \n[7] Mourtada: Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. Annals of Statistics, 2022."}, {"review_id": "11NW1nNen7", "reviewer": "Reviewer_c8kL", "summary": "The paper investigates uniform‐norm generalization error in misspecified linear regression under random design. Its first contribution is to identify the Lebesgue constant of the $L^2(\\mu)$-projection onto the feature span as the exact amplification factor by which ordinary least‑squares (OLS) magnifies the misspecification bias.  The authors prove matching upper and lower bounds by showing that no estimator that minimizes empirical squared error can beat this factor in the worst case. The second contribution is a feature‑augmentation and weighted ridge setting. By adding auxiliary basis functions and assigning individual ridge penalties, the learner can change the projection operator itself.  The paper shows an oracle inequality comparing the proposed estimator to the best attenuation vector that minimizes the Lebesgue constant, and a convex sub‑gradient algorithm that provably converges to this optimum using only data. They also demonstrate this in the special case of monomial features on $[-1,1]$, where the method turns the $\\Omega(d)$ error amplification by OLS into $O(1)$.", "questions": "- 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? I realize this is somewhat open‑ended, but I would appreciate hearing the authors’ thoughts on it. \n\nThis is a minor point but I guess you meant to write $E [exp(\\lambda \\eta_t)]$ in line 61, not just $\\eta_1$, and f is missing in $\\varepsilon_{\\infty}(\\hat{\\theta}_{n, \\text{OLS}})$ in Theorem 5 statement. I don’t have additional questions aside from the above, please refer to the weaknesses I stated in the previous part.", "limitations": "The submission does not contain a limitations/impact section; they should have discussed at minimum the computational cost overhead originating from the Gram-Schmidt orthonormalization.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper presents rigorous theory and proves tightly matched upper/lower bounds.\n\n- The amount of the novelty is sufficient, as the paper brings a new perspective on reframing misspecification amplification as a geometric property that can be learned and controlled.\n- The paper brings a thorough, well‑motivated discussion of the Lebesgue constant, which helps the reader grasp the intuition behind the results.\n\n**Weaknesses:**\n\n- Only one synthetic experiment; no real data or RL experiment to validate practicality, despite that being the stated motivation, which makes it hard to judge the significance of the paper. Also, there's no discussion about the experiment in Figure 1 or its methodological choices.\n\n- Narrative is a bit hard to follow due to excessive expositions, and there is some overlapping content, such as Theorems 4 and 5, or ridgeless and ridge least squares sections, which could have been written more briefly. I also believe work can be done to improve the grammar (e.g., in the abstract) and presentation in several places.\n\n- The uniform error is rarely encountered in machine‑learning tasks, and the paper needs a stronger conceptual argument for why the theoretical guarantees matter in realistic settings. Although briefly mentioned in the intro, the paper would benefit from further clarifying where uniform error influences/determines performance and how theoretical insights translate to practical scenarios like RL.", "was_revised": true, "final_justification": "I still believe that the paper can benefit from more experiments, especially using real data. This is not fully addressed by the authors, and the paper does not well motivate and connect to problems in the RL literature.", "rebuttal": "We thank the reviewer for their comments and the time dedicated to our paper.\n\n### On the mentioned weaknesses\n**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.\"\n\n**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.\nWe 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.\n\n**W2** *Narrative, presentation, grammar could be improved.* Thanks for the constructive feedback which we will take into account in the revision of our paper. \n\n**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.\n\n**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?* \nThe key takeaway for machine learning applications is summarized in three buller points:  \n1) 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.\n2) 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. \n3) 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. \n4) 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."}, {"review_id": "vhmI7UTqDu", "reviewer": "Reviewer_ZEuE", "summary": "This paper addresses the problem of uniform error in linear regression under model misspecification. The authors focus on the random design setting and aim to control the worst-case (uniform norm) error, rather than the $L_2$ error. The authors show that the amplification of misspecification error in least-squares regression is governed by the Lebesgue constant, a classical notion from approximation theory that quantifies how poorly least-squares can behave in the worst case. They prove that this amplification is intrinsic and cannot be avoided by standard techniques such as ridge regression. To address this, the authors propose a novel estimator—Best Weighted Regularization (BWR)—which augments the feature space with auxiliary functions and optimizes a weighted projection to minimize the uniform error. The proposed method achieves an oracle-type performance guarantee and reduces the worst-case error, particularly in settings with polynomial bases. The theoretical results are complemented by synthetic experiments that clearly illustrate the improvement over standard least-squares methods.", "questions": "Generally, I think the paper answers most of my questions when I am reading. Here are some minor questions and comments:\n\nIt is better if the paper can give a short introduction  to $\\lambda$-ridge regression in the main paper, and the exact definition of $\\hat{\\theta}_{n,\\textup{RIDGE}}$.\n\nThe display of Eq.(4) and Eq.(5) is a bit controversial, especially on $\\alpha_i$.\n\nCan you complete answering \\textbf{Q1} by combining Theorem 9 and Proposition 10?\n\nCan you provide more examples besides the polynomial basis to show that the oracle Lebesgue constant has a better denepndence (or even independence) on the dimension $d$?\n\n So far the paper discuss the dependence on the dimension $d$. What is the dependence on $\\mu$? The paper mainly focus on the uniform distribution. Is this a standard assumption or we can investigate more distributions?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall, this is a strong paper, with solid theoretical contribution as well as the story flow and readability. A small problem is that the main body excess the 9-page limit in the appendix version.\n\nLebesgue Constant as Amplification Factor: The authors demonstrate that the amplification of the misspecification error under least-squares regression is governed by the Lebesgue constant, a classical concept from approximation theory. They prove this characterization is tight, revealing an intrinsic limitation of ordinary least-squares (OLS), even with infinite data.\n\nNegative Result for Ridge Regression: The paper shows that standard ridge regression fails to mitigate this issue and can still suffer from large uniform errors, despite its regularization effect in other settings.\n    \nTheoretical Guarantees: The paper proposes a new method called \\emph{Best Weighted Regularization (BWR)} that augments the feature space and optimally attenuates auxiliary components. The estimator provably achieves the optimal Lebesgue constant and thus uniform error..\n    \nCase Study -- In the polynomial feature case, the proposed method illustrates reducing the amplification factor from $\\Omega(d)$ to $O(1)$, supported by explicit error bounds. The example gives readers a clearer sense of the contribution of the BWR estimator.", "was_revised": true, "final_justification": "Thank the authors for addressing my questions. I will maintain my score and I believe this is a solid and informative paper to accept", "rebuttal": "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).\n\nOn the remaining questions:\n\n*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. \n\n*.. 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.\n\n*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."}]

Author rebuttal:

Meta-review: This paper proves that, under random design and misspecification, the worst-case (uniform-norm) error of least-squares estimators is intrinsically amplified by the Lebesgue constant determined by the feature subspace and covariate distribution, with tight upper and lower bounds showing that no empirical squared-loss minimizer can substantially improve this dependence in general. Main commendations include sharp, conceptually clarifying theory: Lebesgue constant governs amplification; bounds are tight (all reviewers), novel method (BWR) that effectively reduces amplification and competes with an oracle (bUTv, UvJD, c8kL, and ZEuE), illuminating negative result for standard regularization (bUTv and ZEuE), quality of exposition and insight for practice (choice of bases) (UvJD, c8kL, and ZEuE), concrete case study demonstrating improvement (monomials) (UvJD, ZEuE, and c8kL). Main concerns include limited empirical validation; lack of real-data or RL experiments despite RL motivation (bUTv, c8kL, KqBU, and ZEuE), guidance on auxiliary features and model size; practicality of choosing how many/which features (UvJD, bUTv, and ZEuE). Given the paper's focus on theoretical investigation, I believe that these concerns about empirical studies are not substantial enough to diminish the paper's excellent contribution. Therefore, I recommend acceptance.
Decision: Accept (poster)