How many samples are needed to leverage smoothness?
Authors: Vivien Cabannes
Stefano Vigogna
Venue: NeurIPS 2023 poster (2023)
Keywords: Statistical learning
breaking the curse of dimensionality
smoothness priors
kernel methods
TL;DR: Investigating transitory regimes in methods that break the curse of dimensionality thanks to smoothness priors

Abstract: A core principle in statistical learning is that smoothness of target functions allows to break the curse of dimensionality. However, learning a smooth function seems to require enough samples close to one another to get meaningful estimate of high-order derivatives, which would be hard in machine learning problems where the ratio between number of data and input dimension is relatively small. By deriving new lower bounds on the generalization error, this paper formalizes such an intuition, before investigating the role of constants and transitory regimes which are usually not depicted beyond classical learning theory statements while they play a dominant role in practice.

How many samples are needed to leverage smoothness?
Vivien Cabannes Meta AI
Stefano Vigogna University of Rome Tor Vergata
Abstract
A core principle in statistical learning that smoothness of target functions allows to break the curse of dimensionality. However, learning smooth function seems to require enough samples close to one another to get meaningful estimate of high-order derivatives, which would be hard in machine learning problems where the ratio between number of data and input dimension relatively small. By deriving new lower bounds on the generalization error, this paper formalizes such an intuition, before investigating the role constants and transitory regimes which are usually not depicted beyond classical learning theory statements while they play a dominant role in practice.
Introduction
The current practice of machine learning consists in feeding machine with many samples for it to infer a useful rule. supervised learning, the samples are input/output (I/O) pairs, and the rule is a relationship to predict outputs from inputs. Once learned, the I/O mapping can be deployed in the wild infer useful information from new inputs. Because it was not engineered by hand, one can question the existence of unwanted behaviors. Classical guarantees regarding the mapping's correctness are offered by statistics: assuming that the training samples are independent and identically distributed according to the future use cases, it is possible to derive theorems akin to the central limit theorem.
While many statistical learning principles offer practical insights, theoretical results often appear somewhat obscure, and forming intuition about them is often challenging, which limits their impact. In this paper, we focus on one simple principle: "smoothness allows us to break the curse of dimensionality". The curse of dimensionality is generic term referring to a set of high-dimensional phenomena with significant practical consequences. In supervised learning, it manifests as follows: without a good prior on the I/O mapping to be learned, one can only get good estimates of the mapping close to the observed examples; as a consequence, to obtain a good global estimate, one needs to collect enough data points to finely cover the input space, which implies that the number of data points should scale exponentially with the dimension of the input space. Yet, when provided with the information that the mapping has some structure, to learn from. This is notably the case when the mapping is assumed to smooth. The goal of this paper is to better understand how and when we can expect to get much better convergence guarantees when the target function known to be smooth.
might need significantly less examples
Related work. Nonparametric local estimators were introduced soon as the field of learning began to form in the 50's [T]. and their consistency was studied extensively in the second half the twentieth century (see Stone [29] Devroye al. [8] and references therein). Introduced for scatter plots 71, local polynomials were the first estimators to leverage smoothness to improve regression
12] They were later replaced by kernel methods, which are powerful way adapt smoothness without much fine-tuning, and were widely regarded as state-of-the-ar before the deep learning era
Convergence results for kernel methods can be understood through the size of their associated functional spaces [13 32 how those sizes relate to generalization guarantees [31], and how those
25
spaces adhere to L 22 26 For least-squares regression, relations between the size of those spaces
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Lambda: 3.01c-06
109
300
Siigmose
10
0.1
Bundeeier
10
Number of samples
Figure 1: Log-log-log-los plots of excess risk (in color) with respect the number of samples (s-axis), the regularizer (æ-axiss) and bandwidth (y-axis) when f (xx sign((r, (1)) and px is uniform on [-1,1]2 Asymptotically, there exists some (An, o.) to ensure that the excess risk decreases in Onn") for ay predicted by theory. However, for finite values of n, the excess risk can present different power law decays. The dark blue line on each plot indicates the transition between low- and high-sample regime: corresponds
graph {(o, A, nt) n (1 ))} (see (10) for the definition AG). The figure illustrates a double descent phenomenon where excess risk peaks are reached when n A before a second descent takes place. Those peaks can he avoided in practice by computing the effective dimension
N and tuning hyperparameters ensure to be smaller than
and generalization guarantees are usually derived through operator concentration 27 6 More recently, transitory regime behaviors were described in Mei et al. [16), Mei and Montanari 15]. and nigh-ddmensional phenomena that lift the need have more data than dimensions were studied in with Bach 3 relating the latter analyses with the former ones.
23 14.
Contributions. This work focuses the role of smoothness in breaking the curse of dimensionality for typical supervised learning problems. At high-level, our main contribution is to showcase the importance of transitory regimes where does not have enough samples to leverage high-order smoothness. In such transitory regimes, the behavior of the excess risk can be quite different than its asymptotic "stationary" behavior. Usually not well described by theory, they might be the dominating regimes in applied machine learning, where the number of samples is often relatively small compared the input dimension (see Figure [ for an illustration). This arguably explains the poor performance of kernel methods without strong kernel engineering in the deep learning era: they try to leverage smoothness, but usually do not access enough samples to meaningfully estimate high-order derivatives. More precisely, our contributions are twofold:
We provide two generic "minimax" lower bounds that illustrate how the curse of dimension- ality can not be fully beaten under smoothness assumptions alone.
We delve more specifically into guarantees offered by algorithms that built leverage smoothness assumptions, and get a fine-gra ane-grained picture some of the transitory regimes where learning takes place in practice.
All results are illustrated by numerical experiments, some of them be found in Appendix
2
The Significance of Constants
This section reviews classical results in learning theory, before providing generic lower bounds when relying solely smoothness assumptions.
2.1 Established Upper Bounds
Supervised learning is concerned with learning function from an input space A' to output space y from dataset D,, = (X;, Yi) of n E N examples For simplicity, we will assume y IR and X Rd X' = T being the torus. A learning rule, learning algorithm, is mapping based on the dataset D.,, with the goal capturing
A D,, + fn that builds a function fa X
We use [n] = (l...., n. denote the set of integer from

---

the underlying I/O relation. To discuss generalization to unseen examples, it is standard to model both the already collected and the future examples as independent realizations of random pair (X, Y).
Assumption 1. There exists distribution P E Axxy that has generated independent training samples D, = (X,, Y)eEjm) ~ pe",, and will generate future test samples inlependently.
Under Assumption | the quality of mapping f X - y is measured through the excess risk
ε()) - R()) - = ||ʃ 1 Lx(xx))
(I)
where px is the marginal distribution of p on X and, assuming that (Y X x) has second order moment for every x E X.
(x)
YY X x]], which minimizes
R() - y1
The risk Rff) represents the average enror of guessing f(X) in place of Y when the error is measured through the least- -qusres loss. From a statistical viewpoint, it is useful to model fa = A(,,)) as random function (inheriting its randomness from the samples), upper tail of the excess risk (.n) Provided that f is measurable, it is possible to find methods such that {(f)) ) converges zero in probability. Without additional assumptions on f", it is not possible to give any guarantee on the speed of this convergence [12] Theorem 3.1]. However, when f* is assumed be smooth, the picture improves consequently.
study the expectation or the
Theorem 1 (Breaking the curse of dimensionality 41) Under Assumption ! when f is a-sooth for a > 0 in the sense that it admits a derivatives that are regular, more precisely if f e C (i.e.
is HöHöle regular), fr f E H Wo.? (i.e. f is a-Sobolev regular), there exists learning rule fn = A(D,, that guarantees
ED, [E(f))] S -22//2a2d
(3)
where e is constant independent of n. Moreover, the bound (3) is minimax optimal, in the sense that for any rule Jn = A(Dm) there exists a distribution such that f E CC,, or f H and the upper bound 3 holds lower bound with different constant c.
Why do constants matter? At first glance, when two algorithms A₁ and A2 guarantee two different upper bounds O(n 7T) and (nn"2)) the expected excess risk, A₁ will be deemed superior to A 21 2 72. since after certain number of samples, we will have that Ep,, [Ai (Dx)) s ED, [A₂(D.)), However, the constants hidden in the front of the big Os might lead to a different picture when given a small number of samples: Ai might actually be a so-called "galactic algorithm", similarly to Strassen's algorithm for matrix multiplication, that might not be worth using without indecently large number of samples.
2.2 Minimax Lower Bounds
The following lower bounds show how classical algorithms that reach the minimax optimal conver- gence rates based on smoothness assumptions (3) necessarily present constants that are growing fast with respect to the input dimension. Our analysis holds in noisy settings
Assumption 2 (Homoscedasticity). The noise in the label (Y IX x) is assumed to be independent of I E X with var | = x) = =².
Theorem 2. Under Assumptions 2 for any algorithm A, there exists a target f" such that f=(a+1) = 0, and
Ep. [E(A(D)))) 2 (
d /d+ d
Theorem 3. Under Assumption 2 for any algorithm A, there exists a target function 8 such that
its Fourier transform is compactly supported on the - disk of radius i.e., f (w'') = 0 for all | olo w, and
(2w
Ep, (((A(,)))
(5)
n
TThis contrasts with interpolation regimes where other phenomena might appear, requiring different analysis tools.
3

---

Number of dimenssio
Number of dimeension
Elffective dimension
10
10"
10
10a
10
10a
Number samples
Number samples
Smoothness
Figure 2: (Left)) Convergence as function of the input dimension d and the number of samples when target function is (z) = zi and k(z,y) (1 x y) We observe that convergence rates depend heavily on the dimension, which is mainly due to "changing constants". (Middle) Theoretical lower bound. As the number of samples increases and we enter the high-sample regime, the lower bound resembles the real convergence rates. (Right) Illustration
+> (Vaa) (d+a) for d 100, which corresponds to the dimension of the space of polynomials with d variables of degree at most a. Given number of samples, Taylor expansion can only be estimated meaningfully up to the order such that ((a)) In particular, it shows that in dimension one-hundred, one millions samples (n = 10%) only allow to leverage more than oouthhooddrr smoothness (a 4). See Appendix C.2 for details.
Proof Sketch (detailed in Appendix). The proofs of those two theorems consist in retaking the standard lower bound g² D/n when performing linear regression with orthogonal features. In Theorem
D corresponds the number of polynomials of degree less than with d variables; in Theorem the number of integer vector m E z whose norm is smaller than w.
Theorems and iillustrate how the usage of strong smoothness assumptions on f* can not guarantee an excess risk lower than E² without accessing indecently large number of samples with respect to the input dimension (e.g.. n 2 (d+a) (1 + (1+a/d) a/d) or n 2 2d respectively). Empirical validations are offered by Figure 2] In their inner-workings, those theorems capture how the rates derived through Theorem are deceptive when one does not have enough samples compared to the size of the hypothesis space that f assumed to belong to; and that the size of smooth functions spaces grows quite fast with respect to the dimension of the input space. Similar lower bound theorems can be proven with rates in n 22)(22+dd under more detailed assumptions, as illustrated with Theorem 7 in Appendix. Efficient learning beyond the limits imposed by those theorems can only take place when leveraging other priors: for example, sparsity priors would reduce the minimax rates from c D/n to e²s log( D)/n where is the sparsity index of
Crisp Picture in RKHS Settings
To provide a fine-grained analysis of the phenomena stake, this section presents stylized settings where constants and transitory regimes can be studied precisely, allowing to get a better picture of convergence rates in practical machine learning setups.
3.1 Backbone Analysis
In the following, we shall consider a feature map : X' - H. with H. Hilbert space and xp (px) The map yp linearly parameterizes the space of functions
F= (fe x (p(x).))) 1 H3 (Px))).
(6)
For example, H could be R& yp seen as defining l features sp(x) on inputs & E X. This model can be used to estimate f through the empirical risk minimizer
Jn arg min FEF
E1S03 -
#E|n]
In order to ensure that F can learn any function f", the features can be enriched by concatenating an infinite countable number features together. this setting, more convenient to describe
the geometry induced by FF through the (reproducing) kernel k X x X + E defined k(x, x²)

---

ppx)), When F can fit too many functions, the estimate 7 needs to be refined to avoid overfitting. This paper will focus on Tikhonov (also known as ridge) regularization
fn arg fer
Σ (f())) ke(n
Yi +n
(8)
where the norm is defined from 6 as ||fl inf {11@1 f= fot. but also be expressed with the sole usage of k through the integral operator K : 1,2 (pxx) + (px):
Kf(x)= = Jxx k(z, (((e) = (x) X))(
(9)
as ||/ /l (ex)) with the convention K 1ke K) {+oo).
The statistical quality of fn (8) depends on two central quantities, defined as
(a(K) Tr
and
S(K) [|(K +1)-
(10)
where a = 2. The first term, known as the effective dimension, quantifies the size of the space F in which f is searched for. It relates the variance of the estimator as function of the dataset D,, will capture the estimation error, the error due to the finite number of accessed samples, related to the risk of overfitting. The second term quantifies the adherence of f to F. It can be understood as the proximal distance between f on F since (K + 1) 1j I - K(K + 1)- is proximal projector. It will capture the approximation error, the error due to the fact that our model does not exactly fit the target function, related to the risk of underfitting.
Theorem 4 (High-sample regime learning behavior). Under Assumptions 1 Mand 2
as well as two Hand when f the closure of F in I, (pxx)). there exists a constant
mild technical Assumptions 3
such that the estimate (8) verifies
(K) S(K) s (NN((K) (an. (2N a (/22(K))
ED. [E(f))]
(LI)
n
n
where an -K)(K)/m and N+ ess esssup xxux Tr(K + 1)- with K the rank-one operator on (2x that maps to the constant function equal to [[fKk(,, 2).. The different notions of seurch space size are always related by N2 S Ni S &N+ Moreuver under the interpolation property (P(L)(px)) + (xx()))) (px), Lee. ||PP I (f it holds that (A = O(x 2P); while under the source condition f (KTLL(ppx) it holds that S(X-1 K) = 0(2²))
While the excess risk upper bound deriving from Theorem is somewhat standard, the lower bound is new. This theorem states that the generalization error Ep,, [f(f)) behaves A(n, K) ==
e2N2 //nn/nnnnnnn/ S S(K) up to higher order terms specified in the right-hand side. Theorem 4 also holds for ridge-less regression 7 with Ni (K, 0) N2 (K,
dim J. WN+ 0) | - -
and S(K, = 1 - / 12 where πy is the (p² -orthogoaaa projection onto J. In this setting, ED. [ (f [))] ] A(n, K, () + On ")). More in general, we conjecture the right-hand 4 to be improvable with the removal of A (K) in front of the rates (which is due to our usage of concentration inequalities on operators rather than on scalar values), the change of the second MG into N2. and the substitution of on by an- This would show that ED,, (E(S)) behaves as A A(n, (1 + (an)). In the following, we will call very high-sample regimes situations where a, < 1, and high-sample regimes situations where N₂(K) < n.
side of Theorem
3.2 Approach Generality
Despite their apparent simplicity, reproducing kernels i describe rich spaces of functions F. known as reproducing kernel Hilbert space (RKHS), namely any Hilbert space of functions with continuous pointwise evaluations [2]. Classical examples are provided by subspaces of analytical functions C
II practice, it is usual to add a regularization parameter À in front of [|]]] in (8) This parameter À can be incorporated as specific hyperparameter of the kernel by replacing by k.. This is useful unify the study the different hyperparameters that might define kernel.
When px does not present heavy tails behaviors, those three quantities actually behaves similarly.
5

---

On 3/2)
Excess risk
10
On-11/2)
Stationary behavior
10
Thcoretical bounds
Real profile
10-2
Phase transition
10
103
Samples n
Figure 3: Illustration of transitory regimes. In essence, Theorem 4 states that En PD,, [E(fm)]
(n,, (1 hn,, K)) for h = O(N+()(++)))) (K)/ We illustrate our upper-lower bound when A(n, K) 1/2 and nh(n, K) is known to he in [- 100 10"). The upper-lower bound forces En hehave in -1/2 when goes to infinity, yet when small, can showcase quite different "transitory" behaviors.
through the Gaussian kernels k(r, x²) /0²², and by the Sobolev space (dd+1)/2 through the exponential kernel ='", exp(- | /o). Reproducing kernels encompass several approaches and algorithms that have been suggested to leverage smoothness of the target function f
The first approach consists in estimating local Taylor expansion through local polynomials, defined through
((x) - 1 (1zEA0) 11-1/(1Leea ( 1.BB.APP
(12)
for P partition on X, B E N a degree, > 0 a regularization parameter. Intuitively in high- dimension problems, where d = dim( is big, leveraging local properties may not be very reason- able, since the covering of X' with local neighborhoods grows exponentially with the dimension d (when has unit volume, and neighborhoods have a fixed radius), meaning that if one wants to have enough samples per neighborhood, should scale exponentially with d.
Rather than local properties, the second approach consists in leveraging global smoothness properties, through the estimation of Fourier coefficients. Such estimators can be built implicitly from translation- invariant kernels, defined as
xxxxx')= = x((=)==(
(13)
for q : Rd - R basic function, bandwidth parameter, and À regularization parameter. However, the number of frequencies smaller than a cut-off frequency, i.e., the number of trigonometric monomials + eim T with m E 2d such that ||m]]] < grows exponentially with the dimension, and this approach will not escape from the curse of dimensionality.
Other approaches, such as windowed Fourier estimation, or wavelets expansion estimation (aiming to reconstruct both fine local details together with coarse large-scale behaviors), could be thought of and described through the lens of RKHS. Yet, whatsoever the definition of smoothness considered (i.e., Hölder, Sobolev, Besov), all those methods will hit an inherent limit: the number of "smooth" functions increases really fast as the dimension increases. Indeed, since their proofs simply consist in finding D) linearly independent function, lower bound theorems akin to Theorems and could be derived without difficulties for other notions of smoothness.
All the previously described methods usually endowed with a few hyperparameters that modify the integral operator K and the norm ||-1l,- defining the estimator (8) Geometrically, a change of the front regularization parameter À leads to isotropic rescaling of the ball |1-115 {1} inside L (px), while change of other hyperparameters. could favor certain directions, or even remove some functions in F. In practice, fitting hyperparameters through cross-validation can be understood as implicitly searching to balance and minimize (KK) and S(K). This fitting allows all those methods 2a/ -2a/ (2(+)))))))))))))) as explain in Appendix.
to reach the performance of Theorem in O( 12ann22////

---

Kernel
F FC C
Ma X)
S(o, Ha 2n log(A A ) (220-d)a Xa/D (o 104)2a/(d+1)
Gaussian
log(A X -1 o d(20-d)/22 /20 -120
Matérn
H H(d+1)/2
Exponential
(a))-d/(d+))
Table 1: Example of connslation-nvariian kernels, their associated function classes, upper bounds (up to multiplicative constants) their sizes function of the bandwidth and regularization parameter A. well as on bias when approximating function in the Sobolev space H Here C stands for of analytical functions. Proofs and details are to be found in Appendix
3.3 Exploration of Transitory Regimes
Given samples, Theorem suggests Suggests to tune K to minimize (KN(K)n++((K) Interestingly, while theory tends to focus deriving convergence rates in ((==22/(aa+d)) that maximize the coefficient ex P Theorem 4 can also be leveraged to characterize tightly the expected decay of the generalization error when accessing small number of samples. To ground the discussion, we will focus on a stylized setting where N and S can be studied in detail as a function of hyperparameters.
Proposition 1 (Capacity and bias bounds). When px uniform on the torus T R /zá and is iinislation-nvvarion kernel k(z, v) x>'1q(( - =)//),, ). the capacity of the space defined through with regularization and bandwidth a verifies, for a E (1,2),
N) = [ ((ow)) Ao-
( (low)
# #(ww,,
(14)
where # is the counting measure on Zdd C Rd,, and q is the (discrete) Fourier transform of Similarly, the biases quantifying the adherence of f in F verify
S(a, 1) [ (o"q(ow) A)2
(w)222
# #(dw).
(15)
Moreover on x IRd,, if px has a density bounded above by Poo < +00, then 14p and (15) become upper bounds for p. the Lebesgue measure and f the continuous Fourier transform, at the cost of extra constants in front of their right-hand sides (respectively Pso. and max(p 1) for No and S).
Proof Sketch. This relatively standard fact follows from the assumption on px which implies that K diagonal the Fourier domain.
Proposition I unlocks precise sense of the effective dimension for the Gaussian kernel, defined with the exponential kernel, with g(æ) = exp(- ||x[]),, and the Sobolev kernel, with
((x) expl - ||
(w)) = (1 + ||س|| 1 as well as the bias term S when approximating a function f E H7t with those kernels. This is reported in Table I and proved in Appendix B
High-sample regimes in harmonics settings. Proposition T is useful to describe formally different convergence rates profiles that one may expect in practice. In particular, the linearity of the bias characterization (15) is theoretically useful to decorrelate the estimation of different power laws appearing in the Fourier transform of f. More precisely, if
F (w)) Pw)
J. c1 + [p()))
with c, being the inverse of the constant in front of the characterization of S X; H)) in Table and μi some measure with profile that ensures the good definition of f H we have, taking for example ls as the Gaussian kernel,
S(a,A:f" ~ / 1ogg)
Forr example, when JF im k1/2 H and 1 HH, it typically holds that A4 (A- O()-2p) with p- = d/43, and S(X -1 -t)) = 0(x2r) with a/28, which be used to prove Theorem by tuning
A -28/2a+d))
7

---

100
10-2
10-1-
fixed (a, best param
10-3
10-2
3
10-4
10
103
10a
103
Figure 4: Composite convergence rates profile. The r-axis corresponds the number of samples, while the y-axis corresponds to excess risk. From the analysis in Section 3.3 one can build different convergence rates profiles. For example, regular functions with relatively high-frequencies are going to be hard to learn with few samples but really easy after a certain number of samples, roughly equals to the number of harmonics with (reeefrrquunccies:: while regular low-frequency functions with singularity are going to show convergence rates where the coarse details of the functions are learned with few samples. but the reconstructions of fine-grained details will required much more samples. The former profile is illustrated with the left figure, and the latter on the right figure. For any sample sizes, excess risk is reported for the best hyperparameters, found with cross- validatio... More details are provided in Appendix C.3
In partieular, with o² log(A~ n=r, we get the following convergence rate profile, with ev the constant in front of the characterization of N N(o A) in Table
Fp.(E(()) inf FER
(ecymn-trdd + n ((dd)) (1 ((a)))
(16)
This characterization enables us to easily create target functions exhibiting different convergence profiles, as long as we stay in the high-sample regimes where our bounds are meaningful (i.e. when the factor in 1 + (an) is relatively constant).
Fast then slow profile. The first type of profile is built from j that charges most of its mass on fast decays, but also puts some small mass on slow decays. It corresponds to target functions that are roughly well approximated by highly smooth functions, but whose exact reconstruction needs to incorporate less regular functions. The smooth part of the function will be learned quickly, yet the non-smooth part will be learned slowly. Typical examples of such profile are provided by non- non-smooth functions that can be turned into infinitely differentiable ones after introducing infinitesimal perturbations, such as f (z)
exp(- min [lx]* M)), which is only C but where one can expect to learn fast before stalling to estimate the C'-singularity. Another example is given by a function made of a sum of one low- www-freuuency cosine with large amplitude easy to learn together with one freg-frryuency cosine with small amplitude much harder to learn. We illustrate these profiles on Figure 4
Slow fast profile. The second type of profile that can be created is for functions that are supported on few eigenfunctions of K associated with small eigenvalues. typical example of this profile in one dimension would be (xx) cos(wxx) for high frequency For this target function, no meaningful learning can be done when the search space is too small, because small search spaces do contain high-frequency functions. On the other hand, when the search space is big enough, the bias quickly goes to zero, allowing for fast learning long as one controls the estimation error. When provided with few samples, one would prefer a small search space to avoid blowing up of the estimation error, and learning will stall until enough samples are collected to explore bigger search spaces, where f could be learned quickly. We illustrate this profile on Figure 4
Those examples illustrate how, given a target function and range the number of available samples, convergence behaviors might fall in regimes that do not correspond to the steady convergence rate in On 2a/2a+dd predicted by Theorem | The intuition beyond those examples is not specific to translation invaarint kernels in harmonics settings, but holds more generically for abstract RKHS.
Empirical study low-sample regimes. this work, we have focused on Lunder-parameterizerr situations where the parameters were set to have more samples than the effective dimension of the

---

Figure 5: Level lines of the weights x + (2u) (17) for given 2p E X, when is the torus R² /2² and the kernel is taken as the Gaussian kernel with the Riemannian metric on the torus (think of an unrolled donut). Parameters From this picture, one can build examples of non-smooth functions where the kernel inductive bias will have adversarial effects.
R²/2²
taken
1 together with X = 10 (left), À 10 (middle) À = 1 (right).
resulting functional space Fz(x). In a deep learning world, where many phenomena are understood as taking place in the "over-paramettrizee" regime, it is of interest to compare perspective with the double descent phenomenon. Figure shows the excess risk as a function of two of the three parameters (n, a, A), well as the graph defined by {nn, A) WV σ) n. It illustrates double descent phenomena with "phase" transition governed by the passage from the low-sample to
the high-sample regime. To delve into this, we investigate into regression weight learned by kernel ridge regression. When given access to the knowledge of the full distribution p. the estimator in (8) can be rewritten
L E(Ya)) a (K A ((X,
(17)
As such, kernel ridge regression be seen learning in unsupervised fashion the weights a : X' - (p), which then indicate how to fold the input space to use information provided by the labels. At high level, finite differences and leverage the result to build an estimate of the target function from Taylor expansions, whatsoever would be the label observations. Sigure how, when is not too big, the reconstruction (Io) (rp being the same point at the bluest center on the different pictures on this Figure) depends on observations made far away from zp according to some periodic pattern, implicitly assuming that the target function should be regular when looked at in the Fourier domain. Similarly, one can look at the weights â satisfying ED.. [x)] E,x,y) [ (z)Y), and whose closed form is given in Appendix C.4 Those weights are shown on Figures 6 They present weird behaviors when the number of data n closed
think of scheme, given some input points, perform
search space size No K ). Note that this double descent phenomenon actually takes place in the regularized setup, and not in the interpolation regime,
contrarily to prior works on the matter [e.g. 28 21
4 Conclusion
In this paper, we have shown how subtle is the saying that smoothness allows to break the curse of dimensionality. In essence, without implicit bias and in presence of noise, one needs to be in the high-sample regime where the size of the search space avoid overfitting, As the input dimension grows, many more smooth functions constrains the diversity of functions within F, which will typically be devoid fine-grained details (linked with high-order, eventually trigonometric, polynomials), hence unable to harness high-order smoothness without accessing a large number samples n.
smaller than the number samples to
be defined. This
Future work. Since we have shown that smoothness alone is not a strong enough prior to build efficient learning algorithms in nigh-diimnsions, other priors could be investigated. As such, sparsity assumptions, multi-index models, feature learning or multi-scale behaviors might offer more realistic models to break the curse of dimensionality. How deep learning models exploit such priors has been an active line of research, although linking theoretical results with "interpretable" observations in neural networks remains challenging, and theory has not yet provided that many meaningful insights for practitioners.

---

High-sample ratio: 0.60
High-sample ratio: 1.00
Highssumple radio: 2.00
-0.5
0.0
0.5
-0.5
0.0
0.5
00.5
0.0
0.5
High-sample ratio: 4.00
High-sample ratio: 8.00
High-sample ratio: 16.00
Figure 6: Weights x + 0g (2t) such that ED, (x)) = (xx,)(xx(=))), for To -1/2 (bluc), Tp O (orange) and Zo 1/2 (green), when X' = |-1, 1] and is uniform. The weight a₂ a= (Ia) quantifies how much the prediction at inferred from the output observed at the point The weights computed with the Gaussian kernel with bandwidth dimension (K) 45, and n {27, 45, 90, 180, 360, 7203. which explains the high-sample ratio n/N2(K) seen on the title of the different plots. When this ratio is close to one, the weights present weird behaviors, which could explain the bad performance when transitioning from low-sample to high-sample regimes.
and 10-5, which yields effective
Furthermore, going beyond the sole selection of a few hyperparameters, it would be interesting to understand more aggressive model selection. In particular, given some observations (X, Y.) and some hypothesis classes (Fe)t, seems natural to trade a term that fits the data as per ( together with regularization term min; [l F, that seleets Fj so that fn has a small Fr norm. We understand this as a lex parsimoniae, where each Fr encodes different notions of simplicity (c.g. different priors) while fn only needs to satisfy one them.
Finally, while this work heavily relies on the least-square loss, practitioners tend to favor other losses such as the cross-entropy. How losses deform and modify the size of the search space and its adherence properties to some target functions f* is an open-question -not to mention its adherence properties when the final predictor built as decoding y(x) = arg max,, f'y (x) in order to learn discrete y from score (yy .)) that relates ((x,Y)>p(Y x X x).
Experiments reproduction. All the code figures is available at httts://gittub.com Facebookresearch//rttte
Acknowledgements. VC would like thank Alberto Bietti, Jaouad Mourtada and Francis Bach for useful discussions. SV was partially supported by the MUR Excellence Department Project MatMod@ TOV awarded to the Department of Mathematics, University of Rome Tor Vergata.
References
[1] Robert Adams and John Fournier Sobolev Spaces. Academic Press, 1975.
[2] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathemati- cal Society, 1950.
[3] Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. arXiv preprint arXhv:2303.01377 2023.
10

---

[4] Francis Bach. Learning Theory from First Principles. MIT press (announced), 2023.
[5] Vivien Cabannes, Alessandro Rudi, and Francis Bach, Fast rates in structured prediction. In Conference on Learning Theory, 2021.
[6] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 2006.
[7] William Cleveland. Robust locally weighted regression and smoothing scatterplots. Journal of the American Statistical Association, 1979.
[8] Luc Devroye, Låslzó Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition. Springer, 2013.
[9] David L. Donoho and lain M. Johnstone. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3):879 921, 1998.
[10] Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 2020.
[11] Evelyn Fix and Joseph Hodges. Diseriminatory analysis. Nonparametric discrimination: Con- sistency properties. Technical report, School of Aviation Medicine, Randolph Field, Texas, 1951.
[12] Lászłó Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. Distributtin--Fre Theory of Nonparametric Regression. Springer, 2002.
[13] Andrey Kolmogorov and Vladimir Tikhomirov. e-entropy and e-capacity of sets in functional spaces. Uspekhi Matematicheskikh Nauk, 1979.
[14] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 2020.
[15] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2022.
[16] Song Mei. Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59, 2022.
[17] Jaouad Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. The Annals of Statistics, 50(4), aug 2022.
[18] Jaouad Mourtada and Lorenzo Rosasco. An elementary analysis of ridge regression with random design. Comptes Rendus. Mathématique, 2022.
[19] Jaouad Mourtada, Tomas Vaškevičius, and Nikita Zhivotovskiy. Distribution-free robust linear regression. Mathematical Statistics and Learning, 2022.
[20] Jaouad Mourtada, Tomas Vaškevičius, and Nikita Zhivotovskiy. Local risk bounds in statistical aggregation. Preprint, 2023.
[21] Nicolò Pagliana, Alessandro Rudi, Ernesto De Vito, and Lorenzo Rosasco. Interpolation and learning with scale dependent kernels. In ArXiv, 2020.
[22] Jaak Peetre. New thoughts on Besov spaces. Duke University Mathematics Series, 1976.
[23] Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels is high-dimensional phenomenon. In Conference on Learning Theory, 2019.
[24] Carl Rasmussen and Christopher Williams. Gaussian Processes for Machine Learning. The MIT Press, 2005.
[25] Bernhard Scholkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.
[26] Steve Smale and Ding-Xuan Xuan Zhou. Estimating the approximation error in learning theory. Analysis and Applications, 2003.
[27] Steve Smale and Ding- Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive Approximation, 2007.

---

[28]
Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. jamming transition from under- to wer-parraettiizaioonn affects loss landscape and generalization. Journal of Physics A: Mathematical and Theoretical, 2019.
[29] Charles Stone. Consistent nonparametric regression. The Annals of Statistics, 1977.
[30] Hans Triebel. Interpolation Theory, Function Spaces, Differential Operators. North-Holland Publishing Co., 1978.
[31] Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.
[32] Ding-Xuan Zhou. The covering number in learning theory. Journal of Complexity, 2002.
12

---

Sigma: 0.46
With 30 samples
10
Lambdas
100
Lambdas
10a
10"4
10
10-7
10
10
30
300
0.1
Number samples
Sigmas
Figure 7: Two other cuts of Figure)
A Generic Proofs and Discussions
A.1 What do we mean by Transitory Regimes?
In essence, by transitory regimes we mean any finite-time behavior that does not match an expected long-time horizon "stationary" behavior. More precisely. T = {nn En, (E(f))) the graph of the expected excess risk. Theorem 4 provides a lower-upper bound of the form C (n, en (1 + ah(n))) n E a [-1, 1]} with c, two constants and h function that goes to zero when its argument goes infinity. This shows that, as en c However, this stationary behavior in en my might take time to kick in, and when only accessing a small number of samples n, our bound does not lead strong constraints on ED, (E())
N be
grows large, Ep, (E(m)) will behave
which might arguably exhibit very different profile. We illustrate this idea on Figure
A.2 Generic Lower Bounds
Let us recall a relatively standard lower bound for linear regression.
Theorem 5 (Linear regression minimax rates, [7).. Let po E Axxy with X Rd and y = R be defined with its marginal over being Px, and its conditionals being (X) = X+e² ~ ~N(0.1) 1) with N the Gaussian distribution. Let D,, ~ Pg on be datasel of a samples (X;, Yi), and A be an algorithm that map D., to guess for Under the assumption that n d and that Σ X,X, is almost always invertible, we have
edd
sup
D [10 100-A(22)
A(DA)(
2
12 d+1
Replacing X by (XX,, we get the following corollary.
Corollary 6. For any learning algorithum A targeting a function f*( p(X) with o + R and E R,, there exists a and a distribution px on such that under Assumption 2
Epacp [1oe A(D.)II) e² dim Span (xx)
n
The proof of Theorem 2 (resp. Theorem 3 follows by considering &p to be the concatenation of all the (d+a) polynomials of degree at most a with variables (resp. all the trigonometric polynomials トー exp( im T 2) with ||m]l.o < w). To be totally rigorous, one should incorporate the assumptions of Theorem yet we remove extra assumption, one can actually show that the worse excess risk could be infinite [17 Proposition 1], so this does not cast shadow on our results, but would only make them stronger. We choose present weaker results that are easier to understand and parse for the reader.
13

---

Those theorems could be proven from scratch by considering well-thought Bayesian prior on & that has generated the dataset n,,, before lower bounding
inf sup Ep, [IA(D))) - 011² z inf Dn
[ILA(D,) 012
inf Dm) [I,(D,,) - 016)
A
||E D..] 016
(..D..)
and computing the last term explicitly. We conjecture that it should be equally possible to compute with this technique a precise "exponentially bad" lower bound on the optimal minimax constants appearing in front of (2/(2a)))) in Theorem
is equally possible to retake the proof techniques of Theorems and to prove lower bound that are targeted to match the upper bound in O(n -2a/(2a+4))
Theorem 7. For any RKHS F and distribution px such that the spectrum of the integral operator verifies spec K = (n-2ar 22//d n E NJ].for for any algorithm A and value D > 0, there exists function satisfying | S D such that under Assumption]
2
ED, (E(A(D.))) 1 ela/(2a)))) (2d/
(2a/(2ad))
Proof. The proof consists in finding a subproblem that reduces to linear regression. Under the and the additional assumption that |00 D, it is possible to show the assumptions of Theorem 5 minimax lower bound
{ Ed2d n
Eg D. P 8
|10- A(Dw))
N min
for some Bayesian prior on 0 [see Chapter on "lower bound", section on Bayesian analysis].
Let us now consider the case where ||0|| S D, and is supported on the top-k eigenvectors of K, DA 11/2 where A is the k-th eigenvalue T' Hence, considering RKHS F, under Assumption for any algorithm A. there exists function such that || S D, and
got |[ |/20|]
{e >x
Ep, [E(A(D.)) max min
REB
Considering A = k 2a/d and (nD2 (nD2//2)2am/22ar (22)2a/((2axd) leads to the result.
terms of implications Theorem 7 harmonics settings, is possible to build integral operator such that the eigenfunctions of K known to be regular smooth functions, e.g., the trigonometric polynomials fm I + exp(-ing z) for m 2d ordered according to ||ma]| = w. As such, for m E 2d with m|] = w, f. expected be ordered around the wd eigenfunctions of K, typically if corresponds to H Using that when f the ke-th eigenfunctions of K, have || = >i Theorem 3 would become that for any algorithm A, under Assumption 2 there exists function f such that || S [l.fmll II with ||m]| and,
associated with the eigenvalue Ayd As (w²) -2//d
(2a 2dd.
Ep, [E(A(D.)))
n22a
When scales linearly with d (so to beat the curse of dimensionality), this lower bound presents constant that is exponential with d.
A.3 Precise Excess Risk Bound
This subsection is devoted the proof of the bound in Theorem
For ease of notation, we will use the fimite-dimensional notation w to denote the inner product (u, v) in iifinite-dimensionn Hilbert spaces. Moreover, we will simply write ||-I| for both ||-Il
14

---

and the operator norm on H. (depending on context), L for (pxx,, and I-112 for both Il-l and the operator norm on L
For the sake of clarity, we have expressed all our statements in terms of operators on L², For the proofs, it is more convenient to work in H. Let us introduce the embedding
S L2,
0 (x + 0 ((x)).
From S, one can take its adjoint S and check that K = SS K isometric to the (non-centered) covariance operator
== = (X) @ (X)).
Note that
|| = (x) 0) < ( I |101
= 1| |10|
which implies that K is a continuous operator as soon as E L The kernel ridge regression estimator (8) is characterized as
fa = + +) 1
where
Sn H -+ RD, 0 (0T
40 ((Xi)))e(n)
En, = S
Y (V:) R..
Endowing R" with the scalar product (a,
12 ;1ie(n) arbs, we have
S
Σ (X,( iE[m]
En (X,) @ (XX))
is useful define E, as the difference between Y, and (X,) E|y, I X,), which can be seen as the labeling noise and average zero. For simplicity, we will first assume that our model is well-specified, i.e. f S0. for some 0", We have, with E (e:)se(m) R",
Y = fx + = =xxx, To. t
Y = S,0, + E.
As consequence,
S(E,, + E,, + 5(E,, + 1
Let X = (Xi)ie(n) we have
Ep, [8(f)) X
Ep, 115n f- x
= =1|s(En + +1) -I - S0. 1|2
+ Ep. ||s(En, + +1) 1) El/ X
[S(E,, +1) - -SO.) S(E,, + +1) x
+ 2E D.
=||s(E, + 1) 1 10.113
+ +D,, [||(Enn + 10 X
+ (S, + +1 -IE,, + +1) Ep, E X
1) 10.113 + +ED ||1(E2n +1) -; 2 X
where in the third equality we used / - (2n, + 1) (2,, + +1 and in the last one that
Ep, EE [X] = O. Assuming for simplicity that the noise is homoscedastic so that EE = e21 for
E > O, we obtain
ED. |(E. +1)-
x
Tr (S, +1 - + - EE X
2 = Tr (Σ(E, + 1) -
n
where the 1/n factor arises from the fact that E = F /n the geometry we have considered on R". Finally we have retrieved the following standard bias-variane variance decomposition result.
15

---

Lemma 2 (Bias- Variance decomposition). When our model is well-specified so that f S0 with 0, H,, and when the noise in the label is homoscedastic with variance 5 the estimator verifies
ED, [8()) = |E 1) 0.11 n Tr (E(E,, + +1)-
(18)
We would like to get the limit when n goes to infinity in equation concentrate towards | + 1)- and the second term to Tr 2 + 1)
We expect the first term to
||
A.3.1 Bounding the bias term
Let us begin by working out the term B, ||S + 1 We first introduce some notation to make derivations shorter. Let En En E, E1 = E + a F. ET 1/2 -E,1/2 ET 1/2 |F < 1, we have
As long as
B, = 0_ (Ep, + 1) + 10
(E) + E,)- + En) -0
= 00_ MΙ 1/2 1/2(1 F,) - ET Fr)) F 1/20.
= =E 1/2
" 1/28.
IJEN
Let us assume for moment that
(XX F.E S
(19)
If equation 19 holds, then
BB, 0, 1 _00
Σ
0. 1/2 Fr 5
" 1/20.
<
Σ
0. 0.1 1/2
1/20.
1+100
= Σ
EΣ 1/2 (Σ- 13
/2 1/20.)
< Σ
1- [Σ] Σ) 128 /
1 2 1/2
++170
= 0. -.EE200
Σ
(( 1/2 F, [Σ 1/1/38t1
1 1/2 F, (ΣΣ 1/2 itj
< -0'2--00
Σ
11/2
(ΣΣ))) 11/2 Fr (ΣE) 11/2 i+1
-. 1 -0,
2)
iEN
+ 2) |F 11 = -.. 250, / ([x) + 2) [[ dr
< 20 Σ
iEN
1- 2 2og FF
< 0 5 2
2x Fr 1 dx = 0.'05 x 250
log"( ((
This inequality is useful as long as [F is small enough, which is not always true. When F is large, we can instead proceed with the simpler bound
BB, - 0, 0,,2 2; 200. < B, + 0, 0,22 200. - 20. E0. 2 12
16

---

Therefore, rewriting the limit as
0_ 1E+1)
(SO.) (K + +1) 550
(K ( -[( 1 S(K),
we split the bias error as
s 2 |1.1>1/2+ + S(K) - 2 log((1 15//2
1B, - 0, 200
log²(1 Fx
3S(K)
s 2 |1.111/2 log(1 Fl
1 1//111/1/2-
Taking the expectation and using the convexity of the absolute value, we obtain
/
1/2 3P (1 x)
Ep, [B,]
2 2,
P(IENN)) 1/2) S(K))
dr.
log(z)
We now proceed with an exponential concentration inequality on Cabannes et al. [5], Eq. (25). As long as 1 < []]] we have
| We will use the one of
nt2
F S 28 28 exp
(N+(K)(+
This incquality shows the restrictive notion of effective dimension, which is useful to ensure the good conditioning of the linear system implicitly encoded in (8) and, in essence, bound all moments of (X().. As long as N (K) 3n/2, we can compute the integral
1/2 IP ( Fn > x)
dr S (K) S.
1/2 exp( 3nx (K))
dr
log(x)
log(æ)
1/2
exp(-u²² u²)
= (K)
log(u) log 3n/2N2 (K)) du
1.
NG (K)N (1 (K)
1/2
(xp(-=²)
(K)
- -8
du S
1.52/2
log(u)
n²//2
We recall that the bounds above were derived under condition 19] which is rather strong. However, the attentive reader would remark that much laxer assumption is sufficient, which we introduce thereafter.
Assumption 3. There exists constant such that, for all i,j EN,
E "F(E)
$ 1/2] S d
|| it F $ 1/2]
(20)
Assumption 3 notably holds when F finite dimensional with e² |ー Kg + As such
all lowed-bound results can be cast with finite-dimensional approximation of dufiite-dimensionn RKHS. Under Assumption 3 we get
|| 1/2] E B, 0_ 2,001
<
Σ
23 122 1|
-
|/ s 1/2
+t$0
Sc
Σ
10.1111 [[ || < 1/2
which allows us to proceed with the precedent derivations without assuming that 19 holds.
While the previous results were achieved for f* F. they can be extended by density to any f in the closure of F in L ). i.e. f (ker K) leading the following result.
Proposition 3. When f E (ker K)' and 1 < EE|, under the technical Assumption the bias term
can be bounded from above and below by
56 1f exp (- n
8S(K) (K) (K))
E.,, [B.] - S(K) $ &N)G(K)
(T6N_(K)
(21)
n 1/2
17

---

A.3.2
Discussion on the bias bound
More direct upper bound. series of implications, with < B meaning that x' Ax S x: Br for every x:
The precedent derivations can be made more direct with the following
Fall S 1/2
-1/21 F, = 1/21
1/21=1- F, 3/21
4/91 (1- 3 41
4/9 1 " (I - = 345(K).
Let us assume that
E (I - F,)
ΣΣΙ (I F.) F,) | S 1/2
(22)
3 c Σ 1/2 (T -,))) |Rall S $1/2]
This leads the simple upper bound
B₁ =
- 1/3g
200 12
1 1/20 + P(1EE11 > 1/2)
exp +11 exp
n (K)
Improvement directions. In essence, expect the bias upper-lower bound to behave F2)-² - (x)
S(K) -
F(.)
Getting this linear dependency in Fa explicitly would allow to improve the bound since ED, Moreover, going back to the definition of Fn.
S 1/2] ||
(K)m
(= Σ 0, ΣΣΙ 3/2 ((X.)) - Exx 0-_ 02222 3/2 xxx)]]
"D,,,,2, 10, F,EE 0. = LED,
n i=1
( 0, ΣΣ x(X.) - Exx 1 3/2 +1xx)/22(x0)) )
EE,
which suggests possible improvements of the bound S(K)n
A.3.3 Bounding the variance term
Let us now work on the term V. = Tr (>n, + + It works similarly to the bias term, concentrating towards (K). With En, 2n, 1, have
Tr (ΣΣ, Σ, Using that, for any A positive semi-definite and any B, Tr(BB) < |B||| Tr(A), it follows that |
Tr E, - 3
E - (Σ E, 1) ΣΣ (ΣnE,,) ))
Da- - N2(K))
/|| + +M((K) مバ - اΣ
S [1)
( (( -
- >
Let us focus on the first term. Using a --:--------- a)b-1 we get
Σ - = (-
< |
/, 1/2
<
(||7I) + ||> 71])
|>ا F. x 1/2
Σ
ا F.E 1/2
450
18

---

For the second term,
2n, - 221
1 | - - -
- En Nn > + (2 Σ
1 2 (En, -E
= 2 ////2 Fn Fn 1
Similarly for (19, if we assume that
Σ/ F E 1/2
scllFull.
(23)
then have, as long as | 1/2c,
- N2(K) -
Σ
11/2 2 Fn, - 1/2
+ | F F. 1/2
1>-0
Full
+ 2c
Fvll
< 4c Ex
Fxll
For the case when ||,]| is large, we can again proceed with simple bound:
V2 (2() Tr (E,, (x
s 2 Tr()).
Splitting the full expectation as we did for the bias we thus obtain
DD, [v]] - [V - ED, IlV, -N2(K)]]
2 T+())(( > 1/2c) + 4cB [||//]| |1A./| S 1/ S 1/2c).
We are left with the computation of two integrals. As long as 1 < |E with the coefficient appearing in the exponential
P( s 1/2c) |I| 1 < 1/2c] < 28))(K)) L. x 1exp(_33nx /2N+ (K)) da
1/22/22
exxp(=x²) do (K)
=K)N -
be relaxed with the following assumption. Assumption 4. There exists constant such that, for all i EEN. N,
Once again, the condition
23
2 12
F.
Fall = 1/20
S T
|| Full S 112cc]
(24)
As for Assumption 3 Assumption holds when F is Liite-dimensional with c² = | [1| + 1). It holds in general with c² = |Σ]|| + 1. although this would deteriorate the bound by a factor of X when considering Σ be E.
[
We are finally ready to collect the different pieces.
Proposition 4. When I* (ker K)¹ and 1 S ||E||, under the technical Assumption 4 the variance term can be bounded from above and below by
Ep, [x) -P,1-NGKK) s (NF(K) 28 (r()
) exp (- (4 (c
on
40cN+(K)
n²
(25)
A.3.4 Discussion to the variance bound
Once again, the bound presented here is somewhat unsatisfying, as it will not necessarily decrease faster than ((K)/n. If one considers target functions that are far away from F and requires large search space (i.e.
decreases slowly with X, and given fixed number of samples the
19

---

optimal X is found for (A,,, quite large compared to n), so that not go zero. Several directions can be taken improve the bound. For example. when Y is bounded by M, the noise gº can be replaced by M and it is possible to get upper bound of the form
does
8M2
Ep, (E
(i(K + inf (15- + +1111) FEF
T
for truncated version fü f(thress)) of the estimator regression and extended to ridge regression in Mourtada et al. (20] Moreover, retaking the analysis of Mourtada and Rosasco [8]. one can get lower bound of the form
proved by Mourtada 19 for ridge-less
Ep, Vn 2 n+1 ED..I En In+1 E-
u 1-1(11)// L
Ep, Tr (2n2),.)) ED,, Tr In 2 1
which might lead to some lower bound with
EDa41 Tr En 1 ((at)//))))))))) n n + ED. Tr (Mn Ex 1 (X) 2 ((X))
ED..x Tr (InEz,) (En,1 + ((X) 8 ((
n
We also note that it should not be too hard replace Fn by E4/25 E,, - which would lead
to E (2)(K)nn instead of e in the right-hand side
A.3.5 Full theorem
Collecting the precedent results leads the following theorem.
Theorem 8. Under the technical Assumptions and as long as [||, when f belongs to the closure of F in (px),, the estimator (8) verifies
(2N((K) S(K)
n + a 22/2((K))
ED. [E(f)]
S 4K) an
n
(26)
?TrEE)²
+ (K)
+ 11 exp(-coo)
n
where = (KK) and some constant c.
As long as its right-hand side decreases faster then Ep, [E(f)) Theorem states that ED, (f())) behaves like
Ep, [E(f)) 22) + S(K).
When optimizing for when K is actually - K, assuming that Mi N2. the right-hand side of -1 1/2 goes to zero with n. This
Theorem 8 decreases faster than ED, [f,)]] if and only if AG (K)a,,
implies N (K)3 n, which much stronger condition than the high-sample regime condition ((K) < n.
A.4
Interpolation spaces, capacity and source conditions
This section discusses the values of ((K) and S(K), and prove the last statements of Theorem
A.4.1 Variances
We begin with simple facts about the variance term. Proposition 5 (Relation between variances). For any kernel k we have the relation
N₂(K) S (K) < N4
(27)
20

---

10P
T0F
10
UP
107
107
102
10A
10
30
10
1006
10
Saaubria
10
Figure 8: Effective dimensions M3 (left) and N2 (right) as a function of (A, 0) in one dimension (top) and two dimension (bottom) when px is uniform on 1] and is Gaussian kernel.
Proof. Once again, the precise study of the variance is easier in H with the operator Σ rather than in T.2. First of all, notice that K = SS has the same spectrum as Σ = S*S, so that, for a E [1,2].
Na(K)= = + =
= Σ
(1 + 11"
#Espec(E)
This shows the first part of the inequality 27
0
x x +
a
N2(K) S (K).
x
(r + 1)
For the second part of the inequality, we need to reformulate N₁ (K), which is the object of the next Lemma. In view of Lemma the last incquality in (27) follows from
N2(K)= Ex [Tr(E= + 1) (X) @ p(X) < ess
ess sup Tr + 1) ((() @ (())) (K)...
x
The ends the proof of the proposition.
Lemma 6. (K) can be expressed in H as
N4(K) = eus
( 1) 13++1)11/((11)) p/)p
xupx
Proof. Observe that, for E X,
[ 12++))1//2(22) || = =x() = Ir ( & @()))
Let us introduce the operator
S H [2(())) 0 (x' + TO)
From
(S.0.)) (l)(X))(()) To 10, (0.
21

---

we get 6ig = (lg(XX) Similarly, one can check that
(x') (5
((xx)xx((xx) Blg)k(r,
and that
m 5,0= [x( 0)p(x) (f((x) (())))
from which we deduce that there exists E { 11, such that
& [|((K [|| +) K2| Tr (K = Tr(x + ())))))))))))))))))))))>)) & (())) = ||
+ 1)))1/2((())
Necessarily & since the right term is positíve. Taking the essential supremum ends the proof. 0
The following a reinterpretation of Proposition 29 of Cabannes al. 1 Proposition 7 (Capacity condition under interpolation inequalities). When (P(L)(px)) is continu- ously embedded in L (px) with p S 1/2, there exists a constant e such that
N+ S c2-
(28)
When the function - k(x, x) is bounded, the RKHS associated with ls verifies
Proof.
The continuous embedding means that there exists constant such that, for any À 2 0,
|K s <clffll.
Stated in H. we get
|S0|| S P =c|x2//2-00)
for every 0 E H. In other terms,
ess ess |p(x) 01 S 2
Let us denote by (A;, 0:) the eigenvalue decomposition of Σ. Then
ess ssssupp(p(r T0) 0)2 s c² |//2--1 c² (0T 0). iEN
When considering 0r this leads to
A xTx]) S c2.
Therefore,
22 sup
( + 1)-1/12 ((x))
sup sup 0 TT x(x) ((x)
x
0:100g11
TT00T p(x) ((x))
a;> 1/2-p
= sup sup
Sc sup (A+ 112
(X + 1/2
0 1 EEN
az af iEN
1/2-p
1/2-B
1/2-1p
csup
iEN () + 1/2 = c
(K) (1 +x+1)1/2
sup
< csup 120
(A + 1)
c((2p) (11p) - 2p) 1/2 1ル2ーPーー0
where the last equality follows from basic calculus.
The second inequality follows from the fact that K (I2) - L soon as o is bounded since, for any T E F SH = (L?),
lf(z) (xxx) < || 00 |||||
|| [Ifll = |1 K (
The previous characterization of N₁ leads to the claim.
22

---

A.4.2 Bias
We now focus our attention on the bias term. Proposition (Source condition). When f E (L*(L((px)) with S 1, there exists constant e such that, any À 2 0.
S( S c2
(29)
Moreover,
S(^-k) 2 (=(0.1),EEK<((3)
inf
x || "xx"ffll f + f 191
(30)
Proof. The proof is straight-forward. If f = K'g with g E L then
x - [|(K fr [ + A) 1||
$ || 1)y 112 || (K + . 11911 I 2 |
Squaring this term and multiplying it by x leads to the result. The second equation is due the decomposition
X S-2S(A-1 K) ( 1) f" 2 + f11 2 [ +1) " f
s 2 2 + カ + 22-> -
The previous derivations explain the final result.
A.5 Application of T'eoree 4 to Taylor expansions
natural idea to estimate a target function f E Ca, with C the space a-Hölder functions, is to estimate its Taylor expansion. This is done with local polynomials which consists in concatenating into ((x)) a finite number of features of the form x + 12 for [3] for some 3 E and A in partition of X:: together with the ridgeless estimator of (7). In this setting No (K,,, 0) is equal the number of polynomials of degree at most 3 with d variables times the size of the partition considered.
The number of such polynomials is hea1)), where h[ss is the complete homogeneous symmetric polynomial of degree 3 in d variables and La is the vector of all ones. Thus,
N₂(K 0) h
(
d + $ (d 3d+
E (1+ 2 d
(1+2)
[1,
3
d!,!
where the last inequalities is due to the fact that (*) E [[n/k)*, (ne/k)²].
When X' = [0, with uniform distribution, and f = f is assumed to be (a, La) Hööder, i.e.
((la)) (x) - ((())(y) s Taa |a - y) -
by fitting Taylor expansions on intervals [(i 1)/m, i/m) for [m] and m E Z4 with polynomials
(
2i 28-11
p(z)=
1 10 1-1 .
2m
one can ensure that [see 12 Lemma 11.1]
L
my 1 101 S
2a a m
where II denotes the orthogonal projection from L onto F. The same type of result also holds for X [0, 1]d when using md multivariate polynomials of degree less then [a]. Balancing the bias and the variance term, we get an excess risk that behaves as (up to higher order term)
e² (me)d (1 + 3/d)a
T
1fn --1p] s
inf mE2=;8E[a]
inf can 23/(d+28) SE[a]
n
22 m2
23

---

for some constant that depends on B, d and grows with Lg, a², the infimum being found for m (13n)//(+220) This argument of the minimizer illustrates how the size of the window should depend on how smooth f" is expected to be among the functions in C Interestingly, it equally shows that the partition size does not deteriorate with the dimension of the input space. Nor will deteriorate the percentage of the total volume contained in each region of the partition. However, the radius of those regions will scale as r = e²/d for u the volume of those regions, meaning that when this volume will shrink zero, the radius will shrink slower as the dimension grows, which will lead to slower minimization of the approximation error. Ultimately as n grows, the last upper bound will end up behaving according to the "stationary behavior" in Co -2a/(2a+d),
A.6 Application of Theorem 4 to Fourier expansions
Rather than local properties, one could leverage global smoothness properties, such as fast decays of Fourier coefficients, e.g. f* E Ha with Hº the Sobolev space of functions that are a-times differentiable with derivatives in (px).
Fourier coefficient estimators can be built implicitly built from translation-invariant kernels, i.e. x() = A (1(((11-- - (v)(a==))//r x')/a) for q IRd - R. bandwidth parameter and À > 0 regularization
parameter. Examples are provided by the Matérn kernels, defined from ((w) = (1 + ||ا]|]] - the exponential kernel, which corresponds to a Matérn kernel of low smoothness / (d 1)/2, and the Gaussian kernel, which can be seen as the limit of a Matérn kernel to infinite smoothness, defined as q(x) exp(- ||=|| l The corresponding estimators can be proven to guarantee the convergence rates as Theorem namely
E
[1
I inf can (2/((++)) g<a
where co notably relates to the norm of fr in H
Proof. For the Matérn kernels, the generalization error reads, with 7 = 2B d, up to constants and higher order terms, according Table
E 1lfm - r-]] x (0" X) 4/20
+ (07A)/133
This is optimized for leading to minimax convergence rates in O(n 2a For the Gaussian kernel, we get
28 28/ 2 (2a+d)
0nnnnnn(2nn-))) (2)
d log(A-1o0)d122
E
[1.f 113 <
+ 2 log(> (og))-lo0)-9
n
which is optimized for leading to the same minimax convergence rate. In particular, when a is fixed, this leads to A Ar =0 ad (xp(-o2n2/(Rotd))
log(> ( - = n (2a++d))
Based on Theorem 4 this is true as long as N()))N 122 some constraints on when assuming f E H However, considering generalization of Mourtada et al. 200 from linear regression to RKHS, the upper bound is actually true without this constraint, which allows to prove the convergence rates in (a/2a/2a+d) for any a.
(A)/n1/2 /
goes to zero with n, which imposes
&
A.7 Application of Theorem 4 to Sobolev spaces
We now turn ourselves to an informal more generic reformulation of the previous facts on Fourier expansions estimation based well-known facts in approximation theory [30
24

---

Proposition 9 (Informal source condition). When F = H and f E H it holds
f E (
Proof. In essence, explained in Appendix B K takes function in (pxx and multiply its Fourier transform by ((w)-1 (1 ||=l with q defining the Matérn kernel, making it 2,3- smooth in the Sobolev sense. In harmonic settings where the Fourier functions diagonalize K and ((w) parameterizes the spectrum of K. the fractional operator K be as multiplying the Fourier transform of f by ((w) making it 2p8-shooth. This fact can be extended beyond those harmonic settings, notably with interpolation inequalities. On the opposite direction, any a-smooth function can be multiplied by ((w)a/20 in Fourier while staying in I.2 (pxx), that, if f is a-smooth, belongs to Ka/25_
Proposition 10 (Informal interpolation inequality). When FF = H is the space of a-Sobolev functions.
K (L)
( L
Proof. Note that F SH (T?) We have informally in the proof of the previous lemma how (P(L²) C 1p2p3 Now, let recall the Sobolev embedding theorems [. Under mild assumptions on Px. for k. r, 1
as long as 1
k 1
(px) 4 W 1. (px),
d'
We want to use with = 2p3, 2, = 0 and & +oc, which leads to p = 43/d.
These results could be used to explain the scaling with respect to À in Table 1 which we will derive formally in Appendix B They can also be used to show convergence rates in On ((n=2a/(2a+d)) for any target functions f E Hº when utilizing a kernel such that F = H (in terms sets equally, F being eventually endowed with an other norm than Sobolev norms).
B Translation-invariann kernels and Fourier analysis
This section recalls basic facts about kernel methods and Fourier analysis, before proving Table |
B.1 Stylized analysis on the torus
When k is translation- cunslationinvvariant kernel, i.c. k(x,2²) g(x - x'), the integral operator is convolution against q. Let us expand on the friendly case provided by the torus X' T R2/Z" = [0, 1] / ~ where ~ is the relation identifying opposite faces of the hypercube, and Px the uniform distribution. On the torus, translation invariant kernel is defined through q being one-periodic function on Rd, Let dæ denote the Lebesgue measure on Rd The integral operator K (2, dx) (22 dx) is the convolution
[ J0.111 k(,, (x,z'))(z')d da' =
Kf(x)=
11o.1j (od'=))(('))) f()))
For m E 2d, define the Fourier function fm x + exip (m, x)). One can check that the fm 's form an orthonormal family that diagonalizes K with
fm = Im.
where
Tm
q(x) exp(2in (x, m)) da.
1o.11
Hence, using Pythagoras theorem, we can define the norm on FF through its action on Fourier coefficients as
11f = (f:K- L)
Σ I
1l 2
(dw),
megd
where Fm fm) LP(px)) and # is the counting measure on zd Rdd
IIndeed, the Fourier transform of a function f E L'(TT) can be defined as the mapping from N to (ff., MEN where (f:) is basis that diagonalizes all convolution operators (note that this definition is possible because px is uniform on the torus).
25

---

B.1.1 First part of the proof of Proposition |
Since K is diagonalized in Fourier, we compute the size of F for a E {1,
with
Na(K) = Tr (K + 1)-9) = Σ
P'
Om + 1)aa
mEZ4
For kernels whose scales are explicitly defined through qo = g(x/o), we have To (w) = o'g(ow). which leads (4...
Similarly, the bound on the bias term follows from Fourier analysis by
2
S(K) |[( 1)) 11=
Σ mEZ
im
Im
+
which provides
15)
B.1.2 Second part of the proof of Proposition 1
When p is distribution that absolutely continuous with respect to the Lebesgue measure and whose density is bounded from above, we get
dpx
K 1 Poo Kdz
with
Poo =
dx
L (px)
where Kd is the integral operator associated to the kernel &s on I (dzd)... Using the fact the effective dimension an increasing function of the eigenvalues (since + x (x + 1) increasing), and that eigenvalues are increasing with the Loewner order, this leads to
Káx) = Poo {
?(w) gz 1 1 @(w)
N(K) S Poo Tr ((Kde 1111'K"Kaa
dw.
Note that those derivations are written informally (since and Kaz do not act on the same space), but could be made formal with the isomorphic covariance operators H. plus some technicalities to make sure Edz is well defined (assuming (xX) has a fourth-order moment against Lebesgue, or approaching Kaz within its action on compact subspaces of X' where it bounded, before taking the limit of Naw (K)).
For the bias term, using the fact that (px) is continuously embedded in (dzz) and the isometry between the spatial and the Fourier domain, we get
1/2 || M = P33 1 (l
Finally, it should be noted that the norm associated with F does not depend on the density of X, hence the formula can be written independently of px. Indeed, under definition assumption, i.c. if E (dxx, this formula can even be written with a measure of infinite mass. For example, when X IRd one can consider the Fourier transform associated with L (dx). and get
| / ((w) (f(m) dw,
((w) J ((x) expe)xpppp200 2im (I, (r,w)) dx, (31)
where
although some care is needed deal with the continuous version of the spectral theorem (the set of eigenvalues being non-countable). From there the same derivations as for Proposition [ lead to the desired result.
B.2 Sobolev spaces
Recall the action of differentiation on the Fourier transform: for m E Nd. |m| = ||m]]as and (dr))
0lml
(W) = (2imr) [m] II
w f(w).
Hlield gmixz
i [d]
26

---

This characterizes the noeudo-norm
alml f())(()) [le amiry
dr = (2 2/ml
w |(w] dw.
This pseudo-norm is associated with the translation-invariint kernel such that 7(w) = [hee[4 4 2m, as per (3T). Note that q well defined when 7 belongs to L ('(rr) (by Bochner's theorem), that is |ml > d. Those observations are usual to deduce that the Matérn kernels, which are defined from (ww) x (1 [| correspond the Sobolev spaces H (dx) endowed with the norm
I| =
E ma mg
follows from Bochner's theorem that H is a reproducing kernel Hilbert space if and only 2,3 > d. Remarkably, the exponential kernel corresponds to the Matérn kernel with 3 = (d+ 1)/2
24 For the Gaussian kernel, ((w) -4/2 exp(-xt ||w]l"), and the associated function class F is analytic (by the Paley-Wienc theorem).
B.2.1 Functional sizes
Let us now express the capacity and bias bound within Sobolev spaces. Proposition 11 (Sobolev capacity). When ((w) = x >- (1 + ||س|| ) for B d, Ao -d-d d. is bounded and p has bounded density, have
Ni 28p 7 dd/23 ((28-4)128. T((d - (((2-1)/2)
Moreover, when X' = TT and Px is uniform, we get
(1+1)/2
Na 1, max
21+1 1 X 1-1228 teld]
Proof. In this setting, Proposition leads to 1
[ 1 (oo(w)-1 dw [
+ do dq(ow)-1 dw =
3dd 1 do 1o- + 0² [||l 110 dw
pd- dr
=suf((S4+1)
1+ 1o + 02r2)S
(u- 1 0 1/13d//2-20000 du
2n vS)
1/22-1 dx Ad/23 gd gd-d2 82/20
+ +ww)
2x vol(S
4/28 d a(d-29)/222
RR 1 (I X188 dd/8)
$ 2nB vol(S 4/28
4/22 d(t
28)
where we used the fact that
4/2 dr 1+ x 1/3 d/3/3
4/2-11 dr max 11 max(x3, \o-
x d/2-1 dx + 1o
/ dx
x d/2 (d/2 B) = B,
which is true as long as 3 > d/2 to ensure proper convergence of the last integral.
For the part on the torus, in order to get sharp learning limit, we need to be slightly more precise. In partieular, we want to relate the discrete Fourier transform integral of Proposition [ with the continuous one through series-integral comparison, and get lower bound on the last integral. We
27

---

will fix o = for simplicity. A simple cut of R into unit cubes, together with the fact that our integrand decreasing, leads
Σ
10gm
(m + X)2 $
Pm
i(w)2
dw S
Σ
(
m,
Im (m + 2)2
(g(w) + 2)2
mEZ"
mE
We simplify it as
N2 2 /
i(w)
(Q(w) + A)2 de,
We now compute the integral with the same techniques before:
/
((w)2 (T(W) + X)2
/ IW) dw
dw
(1+ (1 + )o)) dw
(1+
xd-1
= -2
(1+ +1+ 2)) dx
x xd-1 + (AI/3 + 02) dr
v
xd-1
2
4max 48hh max X2 x41) dr
2 a vol vo1(8*)1~111 4/28 (fo xdd I dx +
+4- 4- S
rdd
x dæ
2 x vol(5 4/20
(d + 4 4- (4, -d))
2- vol 1
It should be noted that this last bound is somewhat too lax, as it tends to zero when the dimension increases. Since Emeza a(I] for a >> 0 is strictly increasing with d, we deduce that this lower bound holds for any k S d.
IT
Proposition 12 (Gaussian capacity). When ((w) x- 1-1exp(-N [|wl)3) and p has bounded density, we have
O) s (d- T²d -100)
20
where L is defined by Eq. (32). In particular, L(x) S x when x < 1, and L(x) & log(z)d/2 when gets large. Moreover when X = T and px is uniform, we get
π (d-1)// 1)/2
N2(A,
2dtigd L(A-10 )m))
Proof. With the Gaussian kernel, Proposition leads to
Jee 1 + to exp [1m133) dw = vol(S")
1
2x
dx
1 -a- exp(o222)
R
1//2-1
vol(S")
du
R+ 1 to <cxp(u)
((d(5)) Lid/2 (-od/N)
gd
where Tig/2 is the polylogarithm function, hence the definition of I. as
(-1)++1a
L(x) Lin/2(-z) Σ
(32)
kd/2
We recognize an alternating sequence, whose term amplitudes are decreasing as a function of k E N when x S 1, which explains that T.(x) is smaller than the first term this case. The expansion the polylogarithm function at infinity leads to the upper bound when goes to infinity.
28

---

When it comes to lower bound, we can proceed as the precedent lemma with
N2(a, A) 2 2- /
dw
/ dw
(1+ iQW)-- 2 2
XQ(W)-
which corresponds to the integral computed for the upper bound. Once again, this also holds when d replaced by any / E [d].
B.2.2 Adherence
Let us now turn our attention to the bias, i.e. the adherence functions in those spaces. For proof readability, will assume that px has compact support. In this setting, Wa.2 is continuously embedded in Ca+d/22 Wa+d/2,00 which can be defined as
{ f: Rd R Illlaa = ess sup WERd
[(w)) +1+ [Wll)att/// < +
Co cd/22/2
Proposition 13 (Adherence of Ha in H When ((w) x- ||01)2)-8, hence F H if > 28, any I E (px), and X small enough, we have
B(a, S A² > fll (((x))
a and px has a bounded density, then for any function f E Ca+d/2
(3 Poo 11 3
B(o, X) S Pox - a3)-aa)[((d-11) X0/8 (28
(33)
Proof. The first part results from previous considerations on the source condition since have the inclusion J E Ha C H29 = KLI (px)). The second part follows from an I,1 L Hölder inequality:
F(W)
Bla, A) S Poo /
dw S Pmo |1 /
(1+ ||0|3) 3 (d/2+aa du
((W))
+ 1)2
(A-1o 2² || ) -B 1)2
2(1 + (d/24a))
2n voll(S Poo 1/
(1-1od(1 + x2x2) + 1)2 dx
Rt
1oe (u + ao²) - (u- (lu--))/70 d/211 (u + 1)2
2n vol(S P0 1 02020
du
4,x vol(S
Poo 11
<
1013 (28 4j0/8
8-
where was set to X 1/80 d/B and the last integral can be bounded by
uu - a + ao (d/2+a) (u d/2-1 du S
4/2
du
P + 1)2
11 a( - 1))d/2+a u0y2
u d/2488-1
8/2
+00
n 4/2
00 (u+ ( 1))d/2+00 u du
4/22+ du
du
4/22+0 ui
1
B
a + B+a a)
Recalling the volume of the sphere completes the proof.
Proposition 14 (Adherence of H in the Gaussian RKHS), When associated with the Gaussian kernel and px has bounded density, for any f" E C/-dd/2 we have
B(o, < (d+1)/2 P:0 1f11 - T((d-1)/2
2 logg(2) (log(2)(44/+22)) (4/22+2)) 0 log(A (og()--oa)-a
gdd+4a 4a
d + 2a
29

---

Proof. We follow the same path as for the adherence of H in H
(1+ 1[]ll))))- (d/2+a)
Bla, A) S Poc 1lf
(A-Lo + 1)2 dw
(1+ 1 ) (d/2++)
Pro llfll
(X-10" 0² ( + 1) dw
(1 + x2) (d (1/2+a) x xd-1
2T voll(S
|1511a
dx
(1-1o"exp) 0² 02102) + 1)2
2n vol 115112 2aa L
400
log( log(z)d/2-1 d/2-1
de
(02 + log(s))
( (d (a x))
log(2) -a @2d+da
2 vol(S")) sx Ilf 2aa log(A~ 100)
where the integral can be bounded by
(gg(2)4/2-1 dx / log(z) log(z) 22) (a+0) x)
+.00
dx +
(log(x))d/2++2)) 2x+ dx
2d
log(2) log(2)-(d/2+2n (d//2+2a)
σ 22d44a
d/2 + 2a
The same type of derivations can be made for the bias in the lower bound.
Note that the proof's also work when the L - -x Hölder inequality is replaced with L L', showcasing the norm of f in Hdt instead of in Ca+d/2, We refer Bach 4 for details.
Remark 15 (Blessing of dimensionalityy. constant pxp vol(S") which will be present in front of the excess risk. As d increases, this constant goes to zero faster than any exponential profile. To see that, note how the volume of the d-sphere is always smaller than twice the one of its inseribed hypercube, whose volume is d d/d/2 We do not have clear intuition to understand this behavior at the time of writing.
should be noted that all our integral calculations show
The previous derivations could be used derive lower bound under highly specific priors on the structure of f However, this proposition is somewhat deceptive compared to Theorems 2 and 3 that are more generic, easier to parse, and show more clearly the curse of dimensionality.
Proposition 16 (Lower-bound application example). For the Matérn kernel corresponding to F= H on the torus T TR / with uniform measure px, when f + cos(2 x:) is function with single frequency m E zd,
N22 -K) K) + S(A-1K)
1m1-1//22
LT (111)/222
)) + [|m]]²) 21/2
inf A>0
2 max IEM
2 21-1((11 1)/2mm
where 7 4/3/(48 + 1) goes to one as goes to infinity.
Proof.
Using the bias and variance lower bounds decomposition and Proposition 11 we get, when f = fm is single frequency function f(w) (m) with m 2d.
2N- KK) + +S(A
dx (d-11/2
X2
N
2d+2T - 1)/2)n X dd28
((1 +
||m
( 2 - A)2
(d-1)/2 x d/28 min() + ||mm]|])2,,, 11)
2 20+1 (1d-1)/2))
From the fact that
+ 2 (12(2=))) + t aa/(ta))) g > (0/12+a) 2/(2+a)
inf ax
30

---

Number dimension
Number of dimension
109
9
10
10-6
10
10
10a
10a
10
10a
10a
Number of samples
Number of samples
Figure 9: (Right) Noise-free convergence rates for fx) = z with k(z, v) or (1 + x. y) We observed similar deterioration of convergence rates function of the dimension The fact that the error added our algorithm to avoid running into computational issues when inverting a matrix online. (Left) Convergence rates for I" (a) cos(Arr)) on the torus X' = T with the (periodic) exponential kernel k(z, v) g 100 || yl /d). We observe similar behavior as Figure 2 the picture being worse because the kernel weights all frequencies in the Fourier domain, and not only the first ("==0) ones.
Figure 2 and 2 is due small regularization
exactly zero when
we have that, whatsoever is (if it fixed for all n independently of the realization D,.).
(d-1)/
A
d/22 + + + 2)
Id+II((d - 1)/2)m
(d-1)) 1)/2
43/(48+d)
[1+1ml]] 23d/(194d)
(nd-11((d-1)))
Once again, this lower bound is also true when is replaced by any / E [d].
C Experimental details
C.1 Online solving of problems increasing size
In order to solve big number of least-squares problems with increasing numbers of samples, one can use recursive matrix inversion. When A E Raxx x E IR" and b E R, one can check that
A
A + cyy' cy
cy )
b
where
and
y = A-1a. l.
xTy
This allows efficient computation of matrix inversion online the number of samples increases.
C.2 Example of convergence rates for "atomic" functions
Polynomial estimation. Consider the target function f*(z) 63x 70x 15x learned with the polynomial kemeel k<xx.)) y) (1
")" with p = 5 X' [0, 1] and px uniform, in the interpolation regime À = 0. In this setting, F is exactly the space of polynomials of degree no larger than 5, which follows from the fact that & can be rewritten through a vector &p that enumerates monomials:
(1+x 4)
(,) G=t (1)
Σ
1 = - T ((v).
As consequence, f* belongs to F. and we expect the bias term to be zero. Yet, we expect the variance, hence the generalization error, to behave as s" dim F/n, where & corresponds to some notion of variability between labels. The dimension of the class of polynomials in dimension d of degree larger than is (p-d). In particular, in dimension d = 100, polynomial of degree at
31

---

most 5 can have up to one hundred million coefficients, so that one needs about one hundred million observations to enter the high-sample regime and expect an excess risk {(f,) of order =² as per Theorem 4 While one could fit polynomial of lower maximum degree, e.g. 4 instead of 5, since the f considered here is actually orthogonal to all polynomials of lower degree, there is no hope to obtain better rates. On Figure the target function is (*) = zy. and the polynomial kernel is normalized as
k(0 v) = 1 +
y
to avoid computational issues. The noise level E is set to 10-2, and the lower bound in s² dim F/n is plotted on Figure 2 In practice, this lower bound describes well the learning dynamic when the number of samples is high compared to the effective dimension the space functions considered.
To transpose the previous example in the Fourier domain, one can consider ('xx) = cos(wpx11 ) together with some translation-invarian kernel. We illustrate this case on Figure The deterioration of the rates with respect to dimension can be understood precisely. In harmonic settings, such as on the torus with uniform measure, one can consider f as an eigenfunction of the integral operator K associated with the eigenvalue Awa The lower bound on the bias is given
Same examples in Fourier.
by
X
S(^-IK) (A + Awo When & is translation-invarianl k(x, v) g(3r y). get that
Tr(K) =
= (lp(X) T -= ([, X)] = =()).
WEZ4
When (0) does not depend on d, this quantity is constant. On the other hand, we expect A to decrease with ||'|| But since the number of frequencies below ||wi|| grows exponentially with the dimension, in order to keep this sum constant Awo has to decrease exponentially fast with the dimension, hence the bias will increase exponentially fast with the dimension.
Example of "wrongfflll"" arbitrarily fast convergence rates. To further emphasize the impor- tance of constants and transitory regimes, let discuss an even simpler example. Assume that one wants to learn a polynomial of a unknown degree E N in a noiseless setting: or equivalently, learn an analytical function such that ((+1)) = 0 for an unknown s E N. This polynomial can be learned exactly when provided with as many points as the unknown coefficients in the polynomial, meaning that the generalization eтrоr will almost surely goes to zero when provided enough points. As consequence,
vh: N
E(f.) S O(h(n)).
where fn is defined in (7) with the space of polynomials of any degree. In other terms, we are able to prove arbitrurily fast convergence rates. Yet, such convergence rates hide constants that are the real quantities governing convergence behaviors of any learning procedure. Figure 9 shows how the number of coefficients in Taylor expansion of order is once again the right quantity to look at.
C.3 Different convergence rates profiles
Figure was computed with the Gaussian kernel on either the -ie-dimensional torus or R. One hundred runs were launched and averaged to get meaningful estimate of the expected excess risk. Convergence rates were computed for different hyperparameters, and the best of hyperparameters (changing with respect to the number of samples but constant over run) was taken to show the best achievable convergence rate.
Fast then slow profile. Let us focus on the example provided by f" : x exp( max M)) exp(-M) (note that we substract exp(-M) -M) so that the function goes zero infinity, which remove the burden of learning a constant offset with the Gaussian kernel.. Note that, for go = exp(-2² 2op(222/ol /o). the convolution 4r * f for large a will not modify / much, while making it analytical. This follows from Fourier analysis: if i' integrable, its Fourier transform is bounded; since a convolution corresponds to a product in Fourier, and since the Fourier transform go decays exponentially fast, so does f go, which implies its analytical property. As a consequence, all functions are close to
32

---

Sigma: 0.34
10
10
10
1 m-aggiinng
Lambdas
10
-10
10
10-7
10-3
10
Bandeiith
Regulatioon
10-3
0.5
Number samples
Figure 10: Excess risk when the target the top taken f*) exp(- max(2", MM) (Xp(M) with M 1/4, and with unit Gaussian distribution. Note that the learning of the smooth part is more efficient when the regularizer is big, which forces the reconstruction to be smooth.
0.2
0.50
Ground truth
10 samples
0.25
0.0
10a samples
0.00
-1.50 -1.25
11.00 -0.75
Figure 11: Example of smooth target function with singuullary whose estimation expected to showcase convergence rates that decrease first fast and then slowly. The z-axis represents the input space X' = [- 2). the y-axis represent the output space f*(x) and fn.A for n = 102 and n = 10 The first fast decrease of excess risk corresponds to the easy estimation of the coarse details of the function, while the slow decrease thereafter corresponds the precise estimation of the C' -singullarit The target function ı m> exp(- max(x², 2 1)) exp(-1) is represented blue, the estimation with 10" samples is represented in orange, and the one with 102 samples is represented in dashed green. The left picture zooms in on the estimation of the singularity. We see that the increase from 10t to 10* does not lead to much better estimate.
analytical functions, whose approximation should exhibit convergence rates in Onn In partieular, for f" defined as before for a some M large enough, without enough observations one will not be able to distinguish between f and 9, f*, and as the number of sample first increases, one will learn quite fast smooth version f* After a certain number samples, the learning will stall until enough points are provided distinguish between and its smoothing, and learn the C'-singularity of the former. Figures 10 and TT illustrate this observation. Note that similar reasoning could be made for any RKHS that is dense Tpx().).
Slow then fast profile. The slow then fast profile was computed with S1 Px being uniform and f - cos(2 with w = 20. One hundred runs were launched and averaged to get an estimate of the excess risk of the estimator in (8) for different values of and X. Again, the best results for different sample sizes were reported get estimate of convergence rates Figure A log-log-log-log plot of the results is provided on Figure [2
C.4 Exploring the low-sample regime
Looking at the empirical weights. While the previous paragraph discusses the weights ax (x) when given access the full distribution, similar derivations can be made when accessing a finite number of samples. Indeed, kernel ridge regression reads as
(xn(x) Σ YYā(())) (E(m)
a(x) (K nd) R, R"
where
K = (K)X). RR*
K, (N(x), R..
33

---

Lambda:
4.28e-04
300 samples
10"1
0.00
Sigmas
10
Lambcler
10
3M
10
10
Numnbor sumples
Sagans
Figure 12: Excess of risk when the target the top is taken as f (a: cos(2 with 20, and S 2/2 uniform on the circle. Observe how the risk first stalls, before learning function quite fast. The two graphs (a,,Na(A, (A, o) for a E {1,2] are plotted with the blue lines.
Hampesample ratio: 0.32
High-sample ratio: 0.53
High-sample ratio: 1.06
High-sample ratio: 2.11
High-sample ratio: 4.23
High-sample ratio: 8.45
0
-0.5
0.0
0.5
-0.5
0.0
-0.5
Figure 13: Same picture Figure 6 yet with .05, which leads effective dimension V 85.
Note that (x( = xxxxx(()) where x= = (Xi..... ,,,) is the input dataset. As consequence,
Σ Eo. (xxx,x)))x = n... Ep, [V xE/mi
In other terms, fn is bias estimator whose average is defined
[fa] (Yxx)
2x Ex [ax,æ X1 x].
(34)
These are the weights plotted on Figures 6 and 13 In order to compute those weights efficiently, one use the block matrix inversion. Using the sliced indices matrix notations, have
âx./P,, (x) [(K -A) Rx]n = [R + n x R₂
[[K nd) Immm-11 x [Kg].n-1 + [[ + "I,n [Krh
-(bb- x TA '1xx) -
([Kx] - x A x [Kglm-1).
where
R + ndT
A x =
RK
I- 1.n + nd
K Kmmn-1
x.
K mmin-1
[K + nd
Denoting
K= (K(Xi, -
-R K₂
E TR--1
get
ãxio, (x) = (k(X,X) - 2ξZx + +nd) (I(X,2)) ZKZz).
2. (K + nnd
34


Reviews:
[{"review_id": "Ca3XRCA7wP", "reviewer": "Reviewer_z9Dq", "summary": "Classical results in learning theory have shown that smoothness of the function class can be leveraged to \"break\" the curse of dimensionality in empirical risk minimization. However, this paper shows that in the specific case where a Taylor expansion or a Fourier expansion is used to leverage smoothness, the constant in the sample complexity can grow exponentially in $d$, which is the dimension of the function. ", "questions": "I also have trouble understanding the role of the meta-algorithm described on line 161. How is it related to the main results regarding Taylor and Fourier expansions?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "I think the theoretical results in this paper are interesting since it tackles a very fundamental question in learning theory: \"is smoothness of the target function enough to guarantee good generalization?\" Classical results in learning theory (e.g. Theorem 1) show that the excess risk for estimating $\\alpha$-smooth functions are upper bounded as $c n^{-2 \\alpha /(2 \\alpha+d)}$, where $n$ is the sample size, $d$ is the dimension of the input, and $c$ is a constant. Thus, for a fixed $d$, as the sample size $n$ grows, the excess risk decays rapidly to zero.\n\n In this paper, the authors show that in specific cases, such as when a Taylor expansion or Fourier expansion is used to estimate $f^\\star$, the constant $c$ can actually be exponential in $d$. Therefore, at least in these specific cases, smoothness alone is not enough to guarantee efficient learning algorithm in terms of the sample complexity. I think these negative results in terms of sample complexity are of interesting because it shows that smoothness might not be a strong enough prior to guarantee good generalization. ", "weaknesses": "I think the writing of this paper could be significantly improved. In its current state, it takes a long time to see what are the \"main results\" and main contributions of this paper. It is also hard to which parts of the paper are restating standard results or standard proofs, and which parts are technically new. On line 132 the authors state that \"the usual proof of Theorem 1 [which is a known result] relies on theorems such as Theorem 2 below\". This is very confusing to me. Is theorem 2 a standard result that the authors restate? Or is it a new result proved in this paper. How it is different from previous theorems used to prove Theorem 1? There also parts of the paper that are just difficult to understand because of the English. For instance, the sentence on line 172 makes no grammatical sense and is hard to understand. \n\nOverall I think both the organization and the writing of this paper needs to be significantly improved, otherwise it would be hard for readers to spot the main contributions of this paper. The organization and the writing is the main issue preventing me from giving this paper a higher score, as I think this paper could benefit greatly from a major revision. \n\n**Update** -- After the rebuttal I have decided to increase the score by 1, because the revised version outlined in the rebuttal pdf is much clearer than the current version. I hope the authors can implement all these changes, as promised. \n\n\n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your feedback. \nIt greatly helped us in improving the presentation of our work.\nAs detailed in our general rebuttal answer (point 2), our draft now begins with generic negative results right after the introduction, and subsequently delves into details in RKHS settings.\n\nIn terms of novelties, Theorem 2 was necessary to establish a lower bound on convergence rates, which was previously unknown. Previous results solely provide upper bounds.\n\nMoreover, as Taylor and Fourier expansions can be shown to be Bayesian optimal, the fact that they suffer from unfavorable constants implies that any other algorithm will necessarily suffer from such constants (see the attached pdf in our general rebuttal answer for crisper details).\n\nThe objective of the meta-algorithm is to explain that the discussed approaches can be viewed through a single meta-algorithm that seeks the optimal ${\\cal F}$ to balance and minimize ${\\cal N}$ and ${\\cal S}$. \nImplementation involves \"kernel cross-validation\" when defining $f_n$ (ridgeless) or $f_{n,\\lambda=1}$ (ridge).\nIn practice, local polynomials estimators change the kernel by adding or removing features in $\\phi$ (based on partition coarseness and polynomial degree), while Fourier-based estimators modify the hyperparameters $\\lambda$ and $\\sigma$ which can be seen as a change of kernel as explained in the paragraph on \"regularization is a change of kernel\".\n\nThank you again for your suggestions that have led us to meaningfully revise the presentation of our work.\nWe hope that it will help you to better appreciate this work.\nWe stay at your disposal for any further questions or suggestions."}, {"review_id": "9e3c1fGYvq", "reviewer": "Reviewer_yXo1", "summary": "This paper studies the problem of learning a smooth function from iid data under different formal definitions of smoothness (e.g. learning an $\\alpha$-Holder function, learning a function in Sobolev space). The paper makes a distinction between two different regimes of sample complexities: the \"very high sample complexity\" regime and the \"high sample complexity\" regime, noting that prior work on learning functions generally proves that the excess risk decays at some rate $O(n^{-\\gamma})$ where $\\gamma$ depends on your particular smoothness assumption.\n\nSuch results have to hold for arbitrarily large $n$, meaning that these rates really describe the decay of excess risk in the \"very high sample complexity\" regime, which they argue is often only descriptive for an unreasonably large sample complexity which isn't possible in practice (i.e. the constant in the big-Oh is huge). They further argue that realistic sample complexities lie in the merely \"high sample complexity\" regime, which exhibits decay at some other rate, say $O(n^{-\\gamma'})$ for some $\\gamma' \\neq \\gamma$.\n\n---\n\nIt's worth noting the proof technique at a high level. The theory of the paper is mainly split into two key flavors of results:\n1. A tight characterization of the excess risk $\\mathcal{E}$ of a function-learning algorithm, showing that the excess risk $\\mathcal{E} \\approx A(n,\\lambda)$, where $A(n,\\lambda)$ is the sum of a variance term depending on a technical notion of \"$\\lambda$-statistical dimension\" and bias term induced by regularization parameter $\\lambda$.\n1. A series of lower bounds roughly showing that for learning $\\alpha$-Holder functions, Sobolev functions, and wavelets, the function $A(n,\\lambda)$ grows exponentially in the dimension of the data.\n\nThese problems are already known to admit excess risk decay rates of $\\mathcal{E} \\leq O(n^{-\\gamma})$ in theory, where the big-Oh hides the dependence on dimension. The above summarized two results together imply that these big-Oh rates in the prior work hide constants that are exponentially large in the data dimension.\nMore broadly, this implies that the intuition that \"assuming a function is smooth lets us avoid a sample complexity that's exponential in the data dimension\" is an insufficient intuition to carry around in data science.\nIt's more accurate to note that the sample complexity is not $O(n^d)$, but nevertheless still likely exponential in the dimension $d$.\n\nSome experiments compliment this theory.", "questions": "Does Prop 1 [Line 194] really show an exponential dependence on dimension, or is the dependence polynomial in dimension and exponential in the degree $\\alpha$?\nSpecifically, I'm thinking of the approximation $(\\frac{n}{k})^k \\leq \\binom{n}{k} \\leq (\\frac{ne}{k})^k$, which implies that\n$$\\textstyle{(1+\\frac d\\alpha)^\\alpha = (\\frac{d+\\alpha}{\\alpha})^\\alpha \\leq \\binom{d+\\alpha}{\\alpha} \\leq (\\frac{e(d+\\alpha)}{\\alpha})^\\alpha = e^\\alpha (1+\\frac{d}{\\alpha})^\\alpha}$$\nand therefore overall that the term in proposition 1 grows polynomially in $d$ for fixed alpha, and grows exponentially in $\\alpha$.\nAm I missing something here?\n\n---\n\nHere's a list of typos / recommended edits. Feel free to use whatever edits you want to use, these are all recommendations.\n\n1. [Line 10] \"they\" instead of \"that\"\n1. [Line 17] \"mapping's\" instead of \"mapping\"\n1. [Line 17] \"can we\" instead of \"to\"\n1. [Line 20] end sentence with a question mark\n1. [Line 23] add \"us\" after \"allows\"\n1. [Line 35] \"was\" instead of \"were\"\n1. [Figure 1] Define $\\mathcal{N}_1(\\sigma,\\lambda)$ or don't use the symbol.\n1. [Line 64] Sometime before this line (i.e. before Section 2), define the notion of a transitory regime. Perhaps use the sentence from Figure 1, but outside of a figure caption.\n> Those transitory regimes, where the behavior of the excess risk can be quite different than its asymptotic “stationary” behavior, are usually not well described by theory, while they might be the dominating regimes in applied machine learning when the number of samples is relatively small compared to the input dimension\n1. [Line 50] Wrong figure reference\n1. [Line 51] \"era\" instead of \"area\"\n1. [Line 135] Remove \"$\\varepsilon^2/n$\"\n1. [Line 173-174] I think the grammar of this sentence is completely borked? Or maybe there's just a word or two that's throwing me way off? I dunno what you're trying to say.\n1. [Line 213] Digest the rate of Prop 2 for us. For example, lower bound the maximum by the choice of $\\ell=d$, and show the rate of the two terms, so that we can easily tell that the second term dominates the first term when $\\|\\|\\vec m\\|\\|_2$ is large enough. (If I did my math correctly, it's roughly when $\\|\\|\\vec m\\|\\| \\geq d$?). Take this as a moment to return to the broader story about the scale of the constants in the big-Oh notation and really pull everything back together.\n1. [Line 224] Remove \"a\"\n1. [Line 254] You mention inequalities, but it's not clear if they're $\\geq$ or $\\leq$\n1. [Figure 3] Include labels for the axes and titles on the plots.\n1. [Line 262] add \"being\" after \"$c_\\gamma$\"", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has an interesting narrative, trying to add nuance to the discussion of how assuming that a function is smooth should significantly reduce the sample complexity of learning that function in $\\mathbb{R}^d$ from a $O(n^{O(d)})$ sample complexity down to a $O(n^{\\gamma})$ sample complexity, where $\\gamma$ depends on the smoothness assumption.\nIt's a nice story, showing that the big-Oh really hides a different exponential dependence on data dimension.\n\nThe presentation is usually pretty good. There were points where I did have to read sentences or paragraphs a couple times to fully understand the idea, but the relevant information is all there, and nice intuitions for the expressions are given. This needing to re-read lines could _in some but not all parts_ also be chalked up to me being not super used to reading papers in this area.\n\nThe quality of the results is also pretty strong.\nThe first core result [Theorem 2, Line 139] is a very tight characterization of how the excess risk grows, being well approximated by this $A(n,\\lambda)$ function.\nIt's nicely interpreted and its lower bounds for specific problems are compelling shows of how the excess risk rate of $O(n^{-\\gamma})$ can really hide huge exponential terms.\nI really like this proof setup and style -- though it's not perfect and lacks some connective, which I'll elaborate on in the _weaknesses_ section.\nThis proof approach also strikes me a pretty novel, and I could imagine similar analysis for other statistical problems following a similar proof strategy as this paper, with the two pronged analysis I mentioned in my summary.\n\nOverall, I like this paper.\nUnfortunately, it has some clarity of writing errors and a lack of connective tissue in some parts, which makes me hesitant to recommend publishing the paper. But I do like it quite a bit!", "weaknesses": "The paper has some clarity issues and some obvious error that really harm legibility.\n\nThe most odd weakness is that many of the references to figures are incorrect. Like [Line 50] mentions Figure 4 when it should mention Figure 1. [Line 217] mentions Figure 5, when Figure 5 is clearly irrelevant to that discussion, but I'm not clear which figure is supposed to be mentioned here.\nI think Figure 8 on [Line 300] has the same issue, and I completely do not understand the message of that paragraph.\nIt's an odd (and presumably very easy to fix) error, but it really did hurt my comprehension at some vital points of the paper.\nBecause it hurt my comprehension, it acts as a very real mark against the paper.\n\n---\n\nThe paper also makes some leaps in logic that can be hard to follow.\nFor instance, Figure 2 [above Line 196] is supposed to visually convey that, when learning an $\\alpha$-Holder function, the excess risk has an exponential dependence on dimension.\nTo my understanding, if there was no such dependence on the dimension $d$ (as suggested by the convergence rate $O(n^{-\\frac{2\\alpha}{2\\alpha+d}})$) then the heatmaps in Figure 2 would not show any relationship between excess risk (the color of the heatmap) and the dimension.\nBut since the heatmaps do show such a relationship, we can empirically see that the big-Oh bound is hiding a painful dependence on $d$.\n\nThis story is not well conveyed by Figure 2's description.\nThere a basic description of what experiment generated the plots, but there's no connective tissue explaining how the plots relate back to the problem of this dimension dependence.\nI also have exactly no understanding of why the third plot in Figure 2 is present. No clue what message it's trying to evoke, nor why the x-axis of the plot is nonlinear in such an odd way.\nThis sort of lack-of-connective tissue appears in a few places, and really harms my understanding of how various puzzle pieces fit together in this paper.\n\nThis writing issue is especially painful in Section 4, where a theoretically tighter but harder to interpret bound on excess risk is presented in equation (14) [Line 265]. This harder-to-interpret rate is not really explained and instead the writing shifts to discussing a very intuitive explanation of two synthetic experiments where the excess rate decays fast-then-slow and slow-then-fast. The tie between the equation (14) and these experiments is thoroughly unclear.\n\nThese issues of clarity are really my big qualms with this paper.\nHaving not fully understood some of this technical material, or rather how this technical material relates to the experiments and intuitions, I really hesitate to accept the paper, hence the borderline judgement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for the depth of your review.\nYour observations helped us a lot to improve our paper.\nWe are also deeply grateful for the typos you spotted.\n\nIt is true that we have focused too much on derivations and have missed to present the connections between our different results. \nWe have modified our draft as explained in our general answer to remedy this limitation.\nWe have equally modified the caption of Figure 2 following your suggestions, and integrated your many other suggestions, it will greatly help us to better convey our message.\n\nWe are sorry for the figure misnumbering, especially since it has caused you some extra work.\nWe changed the figure labels while polishing the draft and missed some cross-references.\nLine 50 should refer to Figure 1, line 217 should refer to Figure 7 (left), line 300 should refer to Figures 12 and 13.\n\nWe are sorry for the lack of clarity of Section 4. \nOur motivation was to crisply capture how, as the number of samples increases, one is able to reconstruct finer and finer details, and to present a simple analysis of how this can be read mathematically.\nWe will clarify this, and we will expand on the math to show how Eq. (14) can be utilized to derive formally slow/fast and fast/slow profiles.\n\nYou are right for the polynomial dependency in $d$ (actually, since ${\\alpha+ d \\choose \\alpha} = {\\alpha + d \\choose d}$, the constants has the same type of dependency in $d$ and $\\alpha$, which is polynomial).\nHowever, to beat the curse of dimensionality, $\\alpha$ has to scale linearly in $d$, which implies the exponential dependency of the constant with respect to $d$.\nThank you for pointing out our lack of explanation there.\n\nThe right of Figure 2 illustrates the constant ${\\alpha + d \\choose \\alpha}$ as a function as $\\alpha$ in log-log scale (using the analytical continuation of the factorial to consider non-integer value of $\\alpha$), we will equally add a Figure to illustrate the constant that appear in Proposition 2 to better digest it as you suggested.\n\nThank you again for your detailed comments.\nWe hope that our revised revision will answer most of our concerns, and stay at your disposal for further questions and suggestions.\n"}, {"review_id": "eXujpLwxWH", "reviewer": "Reviewer_7mBD", "summary": " This paper aims to understand the transitory regimes where the data is not enough to enter the asymptotic regime. When the smoothness is leveraged through Taylor expansions, the number of samples needed to enter the aysmptotic regime is the number of polynomial in d-dimension.  When smoothness is leveraged through Fourier expansions, the picture will depend on how the Fourier coefficinet decays. ", "questions": "See above", "limitations": "I'm suspicious about the technical contribution made by the paper and how the theorem reveals the main information of the paper. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper investigated an important problem of how the constant looked like before the polynomial rate. This makes a contribution to understand what's the prior needed to break the curse of dimensionality. ", "weaknesses": "This paper is conceptually very interesting. However the reviewer is very suspicious about the exact theorem proved.  The reviewer is open to raise the score if the author can hlep me to understand the theorems and their technical contribution better.\n\nFrom my understanding theorem 2 is standard.\n\nIf we characterize the smoothness using taylor expansion. The main conclusion is the sample complexity depends on the number of polynomials. I'm wonder is this conclusion not surprising? and my second question is the sample complexity not depend on the volume in high dimension?\n\nFor the kernel characterization,  from prop3 till (14) looks standard to me. Am I missing anything? From my viewpoint it may have a better characterization of the fast than slow/slow that fast regime using the representing kernel Sobolev norms. Different spectrums have the same kernel norm will have different Sobolev norm. Using this it's easy to have this characterization. (takeoff between norm and convergence rate respect to the number of samples)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe are glad you find our paper conceptually very interesting.\nThank you for raising constructive concerns about our contributions; we will try to clarify them here.\n\nRegarding Theorem 2, while similar upper bounds can be found in the literature (see e.g., Mourtada and Rosasco 2022), the main contribution of Theorem 2 is that it provides a matching lower bound.\nWe are not aware of any such lower bound in the literature.\nIn the narrative of our paper, this lower bound is crucial, as it constrains the learning curve in its transitory and asymptotic regimes both from above and from below.\n\nRegarding Proposition 1 on Taylor expansions, it is not really surprising that the sample complexity depends on the dimension of the space of polynomials with bounded degree, which corresponds to the number of unknown in one Taylor expansion.\n\nRegarding volume in Taylor expansion, as we argue in Appendix A.4.1, paragraph \"Covering issues in high-dimension?\", it may indeed be surprising that an explicit dependence on the volume does not show up in Proposition 1.\nIn fact, one would expect needing exponentially more local neighborhoods to cover a $d$-dimensional domain as $d$ grows.\nHowever, by balancing bias and variance to the minimax rate $O(n^{-2\\alpha/(2\\alpha+d)})$, it appears explicitly that the number of local neighborhoods must be set to have cardinality $O(n^{d/(2\\alpha+d)})$, which does not deteriorate with the dimension.\n\nRegarding volume in Fourier expansions, it should be noted that the volume of the sphere decreases exponentially fast with the dimension (the base object with unit volume being the unit hypercube).\nAs a consequence, series-integral comparisons (i.e., replacing the counting measure by the Lebesgue measure in Proposition 3) are somewhat deceptive in high-dimension, which explains the intricate formulation of Proposition 2.\n\nYes, Proposition 3 is somewhat standard.\nIt is possible to get a characterization through Sobolev norms.\nIn essence, we have an upper bound on rates of the form $U(n) = \\min_{a < \\alpha} c_a n^{-2a / (2a + d)}$ where $c_a$ relates to the norm of $f$ in the Sobolev space $H^a$.\nOne might expect that to a given $n$ corresponds a certain $a$ which is the minimizer defining $U(n)$, and that the real error ${\\cal E}(n)$ might locally decrease in $cn^{-a}$. \nAs such, one could expect that $a$ would increase little by little as one is able to leverage more and more smoothness.\nHowever, 1. the real error does not have to behave as its upper bound, 2. the norms of $f^*$ in different Sobolev spaces are not independent, which makes it harder to create any type of given convergence rates profile (in contrast with our analysis that totally decorrelates the power laws), 3. it is not clear to us how this analysis allows to explain fast then slow profiles (such as the ones described by Song Mei et al. 2022).\nOn the other hand, 1. our analysis is not really different from Sobolev, which are basically integration of the Fourier transform of $f$ against some power law, 2. it describes the behavior of the real error, and not of an upper bound. 3. it can be used to derive fast then slow profiles or slow then fast ones.\nWe will clarify this.\n\nTo conclude, it seems that you have a really good intuition on the described phenomenon.\nOur work consisted in working out the details, which actually reveal subtleties (e.g., the exact variance and bias terms are not exactly the ones usually proven in upper bounds).\nWe hope that this is a good contribution in your eyes.\n"}, {"review_id": "sqkzartDa5", "reviewer": "Reviewer_n2Cg", "summary": "This paper studies transitory, non-asymptotic regimes in the generalization error of kernel methods.\nIt focuses on the use of smoothness to break the curse of dimensionality, and the sample complexity needed to achieve the fast asymptotic rates.\nIn several settings, the authors show that the classical analysis overlooks constants that can be exponential in the dimension.\n\nEDIT: I have read the author's rebuttal, which partially addressed my concerns (this depends on the changes made by the authors to the writing).", "questions": "What do the authors mean by \"so to be able to consider function spaces $\\mathcal F_t$ containing interesting-enough functions with still having more samples than the effective dimension of $\\mathcal F_t$\"? (lines 173-174)?\n\nWhat exactly is the relationship between the $\\mathcal N_a$ quantities? In the same paragraph (lines 150-160), the authors state that they all behave similarly, while making the distinction between the regimes when $\\mathcal N_\\infty(\\lambda) \\leq n$ and $\\mathcal N_2(\\lambda) \\leq n$.\n\nWhich kernel is being used in Proposition 1 to define the quantities $\\mathcal N_2$ and $\\mathcal B$?\n\nCould the authors summarize their results? I do not see the link from the propositions to the claims of the paper.", "limitations": "The authors acknowledge several limitations, among which being limited to the square loss.\n\nFrom my own (limited) understanding,the main limitation of the paper is that does not really answer the question in the title. The authors make various disconnected cases that quantities that are exponential in the dimension might appear for some learning algorithms in some settings.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper makes a very important point that is often overlooked.\nMy lack of expertise in the area, as well as the technicality of the writing, prevent me from judging of the novelty or significance of the analysis.", "weaknesses": "The paper is difficult to follow. Part of it is due to the fact that I am not an expert in this area at all, and this paper seems to be written for people with a significant deal of intuition about statistical learning analyses. I think it would be very useful for the authors to explain this intuition to the reader, rather than assuming they have it. Part of it is also due to the setting of the paper, which seems to constantly switch: in some cases the authors consider kernel ridge regression with a fixed kernel, in other cases an abstract family $\\mathcal F_t$, in yet other cases polynomials of fixed degree. In the end, I have no overview of the precise results of the paper, and it reads to me like a series of disconnected illustrations.\n\nMinor remark: I would suggest to change the notation $\\mathcal N_\\infty(\\lambda)$, as one would expect it to be equal to $\\Vert K (K + \\lambda)^{-1} \\Vert_\\infty$.\n\nTypos:\n- line 16: hands -> hand\n- line 53: four-folds -> four-fold\n- line 97: a -> an\n- line 113: space -> spaces\n- line : $2\\alpha d$ -> $2\\alpha + d$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your review, and for spotting numerous typos.\nYour perspective was highly valuable for us to enhance the readability of our paper, which we discussed in the general rebuttal answer.\nOur immersion in technical details has diverted us from a simple presentation of the overarching narrative.\n\nThere are three levels of abstraction:\n1. Abstract function classes ${\\cal F}$ that could encompass any sets of (measurable) functions from ${\\cal X}$ to ${\\cal Y}$.\n2. Reproducing Kernel Hilbert Spaces (RKHS), a specific type of function class with an inherent inner Hilbertian structure.\n3. Polynomials, a specialized type of RKHS, endowed with a Euclidean structure on polynomial coefficients.\n\nThroughout the paper, we transition between these different levels of generality to provide specific results while demonstrating their broader applicability.\nWe have revised our draft to ensure a smooth progression from one level to the next, as outlined in point 2 of the general rebuttal answer.\n\nIn reference to Lines 173-174, our intention was to convey a trade-off between the scope of the function class ${\\cal F}$ – which impacts the proximity of $f^*$ to ${\\cal F}$ (represented by ${\\cal S}$) – and the risk of overfitting, influenced by the size of the function class (represented by ${\\cal N}$). \nMore precisely, without implicit bias, one needs to be in the high-sample regime (${\\cal N} < n$) to avoid overfitting.\nThis constrains the diversity of functions within ${\\cal F}$, which will typically be devoid of fine-grained details (linked with high-order derivatives, polynomials, and Fourier coefficients), hence unable to harness high-order smoothness without accessing a large number of samples $n$.\nWe will remove this sentence and provide the intuition more sharply as detailed in point 4 of our generic rebuttal answer.\n\nIt is true that the ${\\cal N}$ notations are not ideal; we used some convention in the recent literature.\nWe will change the notations to make it clearer with $N_{\\infty}$ becoming $N_{+}$.\nWe have that $N_2 \\leq N_1 \\leq N_\\infty$ (Proposition 7 in submission's appendix).\nThose quantities behave similarly when there is no heavy-tail phenomenon in the input data (although to be rigorously general, one should distinguish the \"meso\"-sample regime where $N_2 \\leq n \\leq N_\\infty$).\n\nProposition 1 uses the kernel $k(x, x') = \\phi(x)^\\top \\phi(x')$ where $\\phi$ is defined by concatenating monomials. We will make it clearer.\n\nThe crux of this paper is to show that leveraging smoothness is not enough for truly overcoming the curse of dimensionality.\nWe explain that the curse of dimensionality should be read in the constants in front of convergence rates instead of read in exponents (where it does not show up).\nOur new lower bounds, established through Theorem 2, along with Propositions 1, 2, and Section 3.3, substantiate this claim.\nIn particular, Theorem 2 elucidates how the leading order in convergence rates aligns with the left-hand side of equation (10), while Propositions 1 and 2 show that this quantity grows exponentially with the dimension of the input space. \nIt highlights the insufficiency of smoothness as a robust prior for efficient high-dimensional learning. \nWe agree that there was some extra work needed from the reader to understand the full picture: notably we should have mentioned clearly that the discussed methods are optimal to leverage smoothness. \nWe have detailed this fact in our general rebuttal answer.\n\nLastly, because our RKHS analysis is accurate up to higher-order terms, that are insignificant in the \"underparameterized\" regime, but could change the picture in the \"overparameterized\" regime (when one has much fewer samples than dimensions), we turned to experiments to shed light on those regimes, where no magic happens (mainly the algorithm focuses on a coarse reconstruction of $f^*$, which could be, or not be, beneficial).\n\nWe hope that the rebuttal will help you to better appreciate our work.\nWe stay at your disposal for any additional questions."}, {"review_id": "YPkf9b7jhr", "reviewer": "Reviewer_jRbT", "summary": "This paper first states and proves Theorem 2, which bounds the generalisation error from above and below. The authors then use this result in Section 3 to find lower bounds on this generalisation error, quantifying the curse of dimensionality with Taylor expansion in the case of uniform measure on the unit cube and with Fourier expansion in the case of uniform measure on the torus. The final section of the paper investigates the transitory regime, theoretically in the high-sample regime and empirically in the low-sample regime. ", "questions": "L372, displayed equation: I don't recall theta_* being introduced? I assume it's the theta in H such that <phi(x),theta_*>=f*(x)? But then this assumes that f* is in F? In fact this assumption only gets introduced on L374, so is it correct to write the displayed equation after L372?", "limitations": "The authors adequately discussed the limitations in the conclusion section, as future work. These include the need to investigate other priors than smoothness, how neural networks exploit such priors, and other loss functions. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. This paper considers a problem which I find very important and interesting, i.e. the sample complexity required for smoothness of target functions to start overcoming the curse of dimensionality. \n\n2. The mathematics seem mostly solid, albeit some notational inconsistencies and presentational issues (see Weaknesses and Limitations), and the authors clearly put in a lot of effort to make the proofs solid (although I didn't have time to go through all of the proofs). \n\n3. For a theory paper, the authors valued and put in a lot of effort into experimental findings where theory could not extend to, e.g. in the low-sample transitory regime. This I find very valuable. ", "weaknesses": "1. There are a few places in the paper that leave seemingly important results as conjectures. For example, on L147, the authors state \"We expect the right-hand side to be improvable with the removal of N_1(lambda) in front of the rates (which is due to our usage of concentration inequalities on operators rather than on scalar values)\". If the improvement is needed for the subsequent statement within the paragraph and the authors have an idea of how to go about it, I wonder why they didn't do it? This comes up again on L418. \n\n2. The mathematical presentation could be more solid. For example, there are a few instances of notations being used without being introduced, and the same notation being used for different things - see Minor Comments below. Moreover, Theorem 2, which is the main result of the paper, is presented with some issues with regards to clarity - the assumptions under which the result holds can only be found scattered among the proofs in the Appendix. These assumptions do not seem as mild as the authors claim. For example, on L436, it is stated that for Assumption 2 to hold, F has to be finite-dimensional, which is very restricting, or the bound stated in the theorem has to be loosened. \n\n3. Despite the fact that the paper is in general written in a way to suggest very wide generality, the set-up is restricted in Section 2.1 to RKHSs, and the results do not seem to extend to other hypothesis spaces. Of course, RKHSs can be and indeed are large classes of functions, but do exclude e.g. neural networks and other interesting learning situations, and perhaps this restriction should be stated more clearly throughout the paper. \n\nMinor comments\n\nL16: by hands -> by hand\n\nL53: four-folds -> fourfold\n\nL70: Possibly worth defining the notation [n]={1,2,...,n}. \n\nL86: Possibly worth defining the notation for the floor function. \n\nL125-126, L159-160, L201: The notation q is used for different purposes. Perhaps worth changing one of them for consistency?\n\nL223: The same goes for the notation x used here, as opposed to the use of x in other parts of the paper. \n\nL238: In the denominator, 2alpha+d is missing the +. \n\nL368, displayed equation right below: to be consistent with (6), f_n should be f_{n,lambda}. Same is true for every f_n that comes afterwards. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your appreciation of our work, your highly valuable feedback, and for spotting typos.\nWe address here your main concerns.\n\n1. Thank you for your question. \n\na) The right-hand side in (10) is enough for subsequent paragraphs. \n\nb) While we expect the possibility of refining the bounds, we were unable to prove it. We will clarify that our expectation takes the form of a \"conjecture.\"\n\nTo provide more details:\n\nb) Concentration inequalities are primarily known for empirical averages, and convergence proofs for kernel methods often involve expressing differences between distinct empirical averages. \nCurrent \"state-of-the-art\" proofs notably involve rewriting a difference between empirical and real matrix inversions as a difference between matrix averages, which is bounded using recent concentration inequalities on operators (mainly due to the works of Stanislav Minsker and Joel Tropp). \nThese inequalities result in an additional factor of $N(\\lambda)$ in front of the rates (compared to scalar concentration).\n\na) The additional term means that to ensure that the right-hand side of (10) is of higher-order compared to the left-hand side, we need $a_n^{1/2} {\\cal N}(\\lambda)$ to go to zero as $n$ goes to infinity.\nThis implies that we cannot assume overly weak source conditions on $f^*$ (i.e., the largest $q$ such that $f^*$ belongs to $K^q L^2$ should not be too small), otherwise one would need to consider a big search space ${\\cal F}$ to approach $f^*$, which would lead to a too big value of ${\\cal N}(\\lambda)$ compared to $a_n$. \nThis is a typical caveat with weak source conditions (also known as \"hard learning problems\").\nNevertheless, throughout the rest of the paper, we only consider $f^*$ (e.g., Proposition 2) that indeed belongs to $K^q L^2$ for any $q$, ensuring there are no issues in that regard.\n\n2. We thank you for helping us strengthen our draft, particularly regarding notations. \nFor Assumption 2, one can use $c^2 \\simeq \\lambda^{-1}$ which primarily results in the condition that $\\lambda^{-1} {\\cal N}(\\lambda) a_n^{-1/2}$ must approach zero. \nThis restriction further narrows down the required source condition, similar to point 1. However, this adjustment does not impact the rest of the discussion. \nMoreover, we have added a generic lower bound that does not depend on any assumption as detailed in the generic rebuttal answer.\n\n3. We agree with your concern, we have addressed it with points 1 and 2 in the generic rebuttal answer.\n\nYou are right that the Assumption on line 374 and $\\theta_*$ should have been introduced on Line 372. Otherwise the equation afterwards is meaningless.\nIndeed, the proof assumes that $f^*$ belongs to the RKHS, before extending the results by density.\nWe will clarify it.\n\nThank you for your careful reading, and the many valuable suggestions to improve our paper."}]

Author rebuttal:
Dear Reviewers,

We are grateful for your careful assessment of our work.
We feel that our contributions have been well understood, and your feedback has helped us to improve the presentation of our results.
It seems that the reviewers all agree on the facts that:
- It is important to get a sense of the statistical guarantees that one can expect in practical machine learning setups where one has few samples compared to input dimension.
- It is important to understand if smoothness alone can alleviate the curse of dimensionality.

Two primary concerns were raised:

1. The assertion that "smoothness does not completely alleviate the curse of dimensionality" seems to be proven for specific counterexamples but not to hold universally.

2. Shortcomings of presentations necessitate readers to exert additional effort in weaving together the various components.

(3.) Additionally, questions have been raised regarding the novelty of Theorem 2.

(4.) Some sentences conveying intuitions on the trade-off between approximation and estimation errors were hard to parse (especially lines 172-174).

We agree with these observations. Our immersion in technical details has diverted us from a simple presentation of the overarching narrative.
We have taken the following actions to rectify these shortcomings:

1. The discussed Taylor and Fourier expansion can be proved to achieve "Bayesian optimality", thereby establishing unassailable constants.
Indeed, utilizing the fact that when the target function depends linearly on $D$ features, any algorithm has to incur an excess risk of $\epsilon^2 D / n$ for at least one of the "linear" target functions (which is easily proved based on the work of Pinsker on "Optimal Filtering of Square-Integrable Signals in Gaussian Noise" in 1980), we can establish the comprehensive applicability of our findings by demonstrating that:
- For any algorithm, there exists a function $f$ with $f^{(\alpha)} = 0$, where the excess risk for this specific target function exceeds $\epsilon^2 {\alpha + d \choose \alpha} / n$.
- For any algorithm, there exists a function $f$ with $\hat f(\omega') = 0$ for $|\omega'| \geq \omega$, leading to an excess risk greater than $\epsilon^2 \omega^d / n$.

2. To enhance the document's coherence, we will sequentially present generic negative outcomes (as elaborated in point 1 above), and subsequently transition to the RKHS framework.
Here, we will expose the trade-off between the size of the search space and the proximity of $f^*$ to this space, explicitly characterized by the quantities ${\cal N}$ and ${\cal S}$ in Theorem 2.
Our focus will later shift to harmonic settings (e.g., uniform distribution on the sphere), where. thanks to explicit computation of ${\cal N}$ and ${\cal S}$, one can crisply capture the fact that "as the number of sample increases, one is able to reconstruct finer and finer details".
Finally, we will add a discussion section where we will gather the intuition scattered here and there in the submission.
Without modifying the substance of our work, this revised structure will provide a cohesive thread uniting the distinct facets of our paper.
We have attached a pdf to detail this revised organization.

(3.) Concerning novelty, Theorem 2 implies two corollaries: an upper bound and a lower bound on the excess risk. While akin upper bounds have been established (and used to prove Theorem 1), the novelty lies in the introduced lower bound (whose proof approach, as pointed out by Reviewer yXo1, is novel). 
Its inclusion was indispensable for effectively bounding the constants that accompany the rates.

(4.) We will remove obscure sentences scatter here and there in the draft such as lines 172-174, and will make a specific discussion section where we discuss the generic "take-home" intuition. 

Thanks again to all the reviewers for deeply helping us to improve our paper's presentation. 
Your feedback will greatly facilitate the understanding of our work by future readers.
We are hopeful that these adjustments will improve your evaluation, and stay at your disposal for additional discussions.

Best regards,

The Authors


Meta-review: This paper studies the role of smoothness in breaking the curse of dimensionality in statistical learning problems. In particular, the paper presents an interesting negative result: it shows that in the specific case where a Taylor expansion or a Fourier expansion is used to leverage smoothness, the constant in the sample complexity to leverage smoothness can grow exponentially in the dimension.

Five reviewers have reviewed the paper, and their overall assessment of the paper was positive. I agree with the reviewers and believe that the paper sheds light on an interesting and, to some extent, overlooked phenomenon in the connection between the sample size, smoothness, and the problem dimension.
Decision: Accept (poster)