Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm
Authors: Stefano Spigler
Mario Geiger
Matthieu Wyart
Venue:  (2020)

Abstract: How many training data are needed to learn a supervised task? It is often observed that the generalization error decreases  as $n^{-\beta}$ where $n$ is the number of training examples and $\beta$  an exponent that  depends on both data and algorithm. In this work we measure  $\beta$  when applying kernel methods to real datasets. For MNIST we find $\beta\approx 0.4$ and for CIFAR10 $\beta\approx 0.1$. Remarkably, $\beta$ is the same for  regression and classification tasks, and for Gaussian or Laplace kernels. To rationalize the existence of non-trivial exponents that can be independent of the specific kernel used, we introduce the Teacher-Student framework for kernels. In this scheme, a Teacher generates data according to a Gaussian random field, and a Student learns  them via kernel regression. With a simplifying assumption --- namely that the data are sampled from a regular lattice --- we derive analytically $\beta$  for translation invariant kernels, using previous results from the kriging literature.  Provided that the Student is not too sensitive to high frequencies, $\beta$ depends only on the training data and their dimension. We confirm numerically that these predictions hold when the training points are  sampled  at random on a hypersphere. Overall, our results quantify how smooth Gaussian data should be to avoid the curse of dimensionality, and indicate that for kernel learning the relevant dimension of the data  should be defined in terms of how the distance between  nearest data points depends on $n$. With this definition one obtains reasonable effective smoothness estimates for MNIST and CIFAR10.

Under review as a conference paper at ICLR 2020
ASYMPTOTIC LEARNING CURVES OF KERNEL METH- ODS: EMPIRICAL DATA V.S. TEACHER-STUDENT PARADIGM
Anonymous authors Paper under double-blind review
ABSTRACT
How many training data are needed to learn a supervised task? is often observed that the generalization error decreases as n n where is the number of training examples and 3 an exponent that depends on both data and algorithm. In this work measure 3 when applying kernel methods to real datasets. For MNIST we find 33 = 0.4 and for CIFARIO 3 Rs 0.1. Remarkably, / is the same for regression and classification tasks, and for Gaussian Laplace kernels. To rationalize the existence non-trivial exponents that can be independent of the specific kernel used, we introduce the Teacher-Student framework for kernels. In this scheme, a Teacher generates data according to a Gaussian random field, and a Student learns them via kernel regression. With a simplifying assumption namely that the data are sampled from a regular lattice we derive unalytically 3 for translation invariant kernels, using previous results from the kriging literature. Provided that the Student is not too sensitive to high frequencies, B depends only on the training data and their dimension. We confirm numerically that these predictions hold when the training points are sampled random on hypersphere. Overall, our results quantify how smooth Gaussian data should be to avoid the curse of dimensionality, and indicate that for kernel learning the relevant dimension of the data should be defined in terms of how the distance between nearest data points depends on With this definition one obtains reasonable effective smoothness estimates for MNIST and CIFARIO.
INTRODUCTION
In supervised learning machines learn from a finite collection of training data, and their generaliza- tion error is then evaluated on unseen data drawn from the same distribution. How many data are needed to learn a task is characterized by the learning curve relating generalization error to n. In various cases, the generalization error decays as power law n -9 with exponent 3 that depends on both the data and the algorithm. In (Hestness et al., 2017) 3 is reported for state-of-the-arr (SOTA) deep neural networks for various tasks: in for neural-machine translation 3 ze 0.3-0.36 (for fixed model size) or B R0 0.13 (for best-fit models at any n); language modeling shows / z 0.06-0.09; in speech recognition B = 0.3; SOTA models for image classification (on ImageNet) have exponents 3 2 0.3-0.5. Currently there is no available theory of deep learning to rationalize these observations. Recently it was shown that for proper initialization of the weights, deep learning in the infinite- width limit (Jacot et al., 2018) converges to kernel learning. Moreover, it is nowadays part of the lore that there exist kernels whose performance is nearly comparable deep networks (Bruna and Mallat, 2013; Arora et al., 2019), at least for some tasks. It is thus of great interest to understand the learning curves of kernels. For regression, if the target function being learned is simply assumed to be Lips- chitz, then the best guarantee is 9 3/a (Luxburg and Bousquet, 2004; Bach, 2017) where d is the data dimension. Thus for large d, 3 is very small: learning is completely inefficient, a phenomenon referred to as the curse of dimensionality. As result, various works on kernel regression make the much stronger assumption that the training points are sampled from a target function that belongs to the reproducing kernel Hilbert space (RKHS) of the kernel (see for example (Smola et al., 1998)). With this assumption 3 does not depend on d (for instance in (Rudi and Rosasco, 2017) 3 1/2 is guaranteed). Yet, RKHS is very strong assumption which requires the smoothness of the target

---

Under review as a conference paper at ICLR 2020
function to increase with d (Bach, 2017) (see more this point below), which may not be realistic in large dimensions.
In this work compute 33 empirically for kernel methods applied on MNIST and CIFARIO datasets. We find ÍMIIST R 0.4 and BCIFARIO R 0.1 respectively. Quite remarkably, we observe essentially the same exponents for regression and classification tasks, using either Gaussian a Laplace kernll. Thus the exponents are not as small as 1/a (d = 784 for MNIST, d = 3072 for CIFARIO), but neither are they 1/2 one would expect under the RKHS assumption. These facts call for frameworks in which assumptions on the smoothness of the data can be intermediary between Lipschitz and RKHS. Here we propose such a framework for regression, in which the target function assumed to be a Gaussian random field of zero mean with translation-invariie can equivalently be thought as being synthesized by "Teacher" kernel (z). Learning performed with a "Student" kernel K (2) that minimizes the mean-square error. In general (r * (z))). In this set-up learning is very similar to a technique referred to as kriging, or Gaussian process regression, originally developed in the geostatistics community (Matheron, 1963; Stein, 1999b). To quantify learning, we first perform numerical experiments for data points distributed uniformly at random hypersphere of varying dimension d, focusing Laplace kernel for the Student, and considering a Laplace or Gaussian kernel for the Teacher. We observe that in both cases ((d) is a decreasing function.
isotropic covariance (x) The data
To derive ((d) we consider the simplified situation where the Gaussian random field is sampled at training points lying on regular lattice. Building on the kriging literature (Stein, 1999b), show that 3 is controlled by the high-frequency scaling of both the Teacher and Student kernels: assuming that the Fourier transforms of the kernels decay as Kr(w) = cr lrl -ar + +o( (1| -ar)
and (s(w) = cs es|w|-a as + o (|wl as), we obtain
B min(ar - 2as).
Importantly (i) Eq. (1) leads to a prediction for (dd) that accurately matches our numerical study for random training data points, leading to the conjecture that Eq. (1) holds in that case as well. We offer the following interpretation: ultimately, kernel methods are performing a local interpolation whose quality depends on the distance 8(n) between adjacent data points. d(2) is asymptotically similar for lattice. (ii) If the kernel K is not too sensitive to figh-frequencies. then learning is optimal as far as scaling is concerned and / = (aT - dd/d. We will argue that the (aT d)/2] characterizes the number of derivatives of the target function that are continuous. We thus recover the curse of dimensionality: s needs to be of order d to have non-vanishing 3 in large dimensions. Point (ii) leads to an apparent paradox: ,3 is significant for MNIST and CIFAR1O, 10, for which d is priori very large, leading to smoothness value s in the hundreds in both cases, which appears unrealistic. The paradox is resolved by considering that real datasets actually live on lower- dineer-dmmnsionall manifolds. As far as kernel learning is concerned, our findings support that the correct definition of dimension should based on how the nearest-neighhors distance 5(n) scales with n:: 6(n) n 1/áatr, Direct measurements of d(n) support that MNIST and CIFAR 10 live on manifolds of lower dimensions deff MNIST ~ 15 and geff dIIFARIO = 35. Considering the effective dimensions that we find, the observed values for / would be obtained for Gaussian fields of smoothness SNNIST RV 3 and ScIfAR R 1, values that appear intuitively more reasonable. More generally this analogy with Gaussian fields allows one to associate a smoothness index & to any dataset once 3 and deff are measured, which may turn out to be useful characterization of data complexity in the future.
random data or data sitting
smoothness index
2 RELATED WORKS
Our set-up of Teacher-Studen learning with kernels is also referred to as kriging, or Gaussian process regression, and it was originally developed in the geostatistics community (Matheron, 1963). In Section 5 we present a theorem that allows one to know the rate at which the test error decreases as we increase the number of training points, assumed to lie high-dimensional regular lattice. Similar results have been previously derived in the kriging literature (Stein, 1999b) when sampling occurs the regular lattice with the exception of the origin, where the inference is made. Here we propose an alternative derivation that some readers might find simpler. We also study a slightly different problem: instead of computing the test error when the inference is carried on the origin,
2

---

Under review as a conference paper at ICLR 2020
compute the average error for test point that lie at arbitrary point, sampled uniformly at random and not necessarily on the lattice.
In what follows we show, via extensive numerical simulations, that such predictions accurate even when the training points do not lic on a regular lattice, but are taken at random on a hypersphere. An exact proof of our result in such general setting is difficult and cannot be found even in the kriging literature. To our knowledge the results that get closer to the point are those discussed in (Stein, 1999a), where the author studies one-dimensional processes where the training data are necessarily evenly spaced.
In this work the effective dimension of the data plays import role, as it controls how the distance between nearest neighbors scales with the dataset size. Of course, there exists vast literature (Grassberger and Procaccia, 1983; Costa and Hero, 2004; Hein and Audibert, 2005; Levina and Bickel, 2005; Rozza et al., 2012; Facco et al., 2017; Allegra et al., 2019) devoted to the study of effective dimensions, where other definitions are analyzed. The effective dimensions that we find are compatible with those obtained with more refined methods.
3 LEARNING CURVE FOR KERNEL METHODS APPLIED TO REAL DATA
In what follows apply kernel methods to the MNIST and CIFAR10 datasets, each consisting of a set of images (x,,) j- We simplify the problem by considering only two classes whose label (zz,) = +1 correspond to odd and even numbers for MNIST, and to two groups of 5 classes in CIFARIO. The goal infer the value of the label 2 of image z that does not belong the dataset. The S subscript reminds us that inference is performed using a positive definite kernel Kg. We perform inference in both regression and a classification setting. The following algorithms and associated results can be found in (Scholkopf and Smola, 2001).
Regression. Learning corresponds minimizing a mean-square error:
T2
E5( (2())) Z(Zz))
For algorithms seeking solutions of the form -s(z)= En anKs kz(()) by minimizing the man-square loss the vector a, obtains:
(x(x) (2(x) Kg5 Z.
where the vector Z contains all the labels the training set, = (Z (z,,))) and Ks = ( ) is the Gram matrix. The Gram matrix is always invertible if the kernel K3 is positive definite. The generalization error is then evaluated the expected nquar- error unseen data, estimated by averaging over a test set composed of Doest unseen data points:
( -Z(,,)
MSE-
Tarrst
Classification. We perform kernel classification via the algorithm soft-margin SVM. The details can be found Appendix A. After learning from the training data with student kernel Ks, performance is evaluated via the generalization error. It is estimated as the fraction of correctly predicted labels for data points belonging to a test set with Nestt elements.
In Fig. we present the learning curves for (binary) MNIST and CIFAR10, for regression and classification. Learning is performed both with a Gaussian kernel K K(x) x exp(-Izl' exp(-lxl'/(2o")) /(o2)) and Laplace one K (z) x exp(-lzl/o)) Remarkably, the power laws in the two tasks are essentially identical (although the estimated exponent appears to be slightly larger, in absolute value, for classification). Moreover, the two kernels display very similar behavior, compatible with the same exponent: about -0.4 for MNIST and -0.1 for CIFAR1O. The presented data are for o = 1000; in Appendix B show that the same behaviour is observed for different values.
3

---

Under review as a conference paper at ICLR 2020
Regression MNIST
Regression CIFAR10
10
Gaussian
Gaussian
Laplace
Laplace
0.37
9.9
10P
MSE
-
88
(a)
(b)
10-1
x
Classification MNIST
Classification CIFAR10
Gaussian Laplace
Gaussian
Laplace
n
0.4
0.10
-4x10
Error
10-1
3
(c)
(d)
10a
10a 10
102
103
104
Figure 1: Learning curves for regression on MNIST and CIFARIO (a-b); and for classification on MNIST and CIFARIO (c-d). Curves are averaged over 400 runs. A power law plotted to estimate the asymptotic behavior at large the exponent is fitted the last decade on the average of the two curves, since it does not seem to depend significantly on the specific kernel or on the task. In each setting use both Gaussian kernel K K(x) x exp(-lll?/(2o²)) and a Laplace one K(x)) x exp( (Izl/)) with a = 1000.
GENERALIZATION SCALING IN KERNEL SEACHER-STUDRRE PROBLEMS
We study 3 in a simplified setting where data assumed to follow a Gaussian distribution with known covariance. It falls into the class of Seacher-Student problems, which are characterized by machine (the Teacher) that generates the data, and another machine (the Student) that tries to learn from them. The Sttcher-Sttdent paradigm has been broadly used to study supervised learning (Saad and Solla, 1995; Monasson and Zecchina, 1995; Opper and Saad, 2001; Engel and Van den Broeck, 2001; Zdeborová and Krzakala, 2016; Barbier et al., 2019; Gabrié et al., 2018; 8; Aubin al., 2018; Franz et al., 2018). He we restrict our attention to kernel methods: we assume that target function is distributed according
Gaussian random field Z (0 KT) the Teacher characterized by a translation -anaaaiio-invariantt isotropic covariance function K2 (z. x²) Kr([æ z' l), and that the training dataset consists the finite set of n observations the vector of training points follows centered Gaussian distribution with covariance matrix that depends on Ky and on the location of the points (xr,) )²=1
(Z (x ))= This equivalent to saying that
N (0, Ky), where Ky- Ex), 2x))).m
(S)
Once the Teacher has generated the dataset, the rest follows in the kernel regression described in previous section. We use another consslationinvarian isotropic kernel Ks(r, x') the Student to infer the value of the field at another point, (I),,, with a regression task, i.e. minimizing the mean-square error in Eq. (2). The solution is therefore given again by Eq. (3).
Fig. 2 (a-b) shows the mean- square error obtained numerically. In the examples the Student is always taken be Laplace kernel, and the Teacher is either Laplace kernel or Gaussian kernel. The
4

---

Under review as a conference paper at ICLR 2020
points (En)ū=ı taken uniformly random the unit d-dimensional hypersphere for several dimensions d and for several dataset sizes n. We take dg = or = as we observed that with this choice smaller datasets were enough to approach limiting curve in Appendix C we show the plots for the case Øs = or = 10, which appears to converge to the same limit curve with increasing n, but smaller pace. The figure shows that when is large enough, the mean-square emror behaves power law (dashed lines) with an exponent that depends on the spatial dimension of the data, as well on the kernels. The fitted exponents are plotted in Fig. 2 (c-d) as function of the spatial dimension d for different dataset sizes n. In the next section we will discuss the theoretical prediction, that in the figure is plotted thick black line. The figure shows that as the dataset gets bigger, the asymptotic exponent tends to prediction. In Appendix D we present the learning curves of Gaussian Students with both Laplace and Gaussian kernel. When both kernels are Gaussian the test error decays exponentially fast, a result that matches our theoretical prediction. In Appendix E we also provide further numerical results for the case where the Teacher kernel is a Matérn kernel (as defined therein).
ANALYTIC ASYMPTOTICS FOR THE KERNEL MACHER-STUDENT PROBLEM ON LATTICE
In this section we compute analytically the exponent that describe the asymptotic decay of the generalization error when the number n of training data increases. order to derive the result we assume that both the Teacher Gaussian random field lives a bounded hypercube, z E V = [0, Lj where L is a constant and is the spatial dimension. The fields and the kernels can then be thought of
10
Gaussian-Laplace
Laplace-Laplass
d 4
d m 4
10
8
d 8
d= 16
d == 16
MSE
10-4
d= 32
d = 32
10
10-6
10-8
(a)
(b)
10
10
10
10
10'
10
10
10
0.0
-2.0
(c)
(d)
- 0.2
E MSE/log
-2.5
Gaussian-Laplace
Laplace-Laplace
-3.0
MSE - +
E MSE n -1Nd-11
n=64
n=16
n=258
n=128
-3.5
n=1024
n=1024
-088
n=4096
n=4096
n=8192
n=8192
-4.0
25
30
5 10
15
20
25
Figure 2: Results for the Teacher-Studen kernel regression problem, where the Student is always Laplace kernel. Data points are sampled uniformly at random on d-dimensional hypersphere. (a-b) Mean-squarg еитог versus the size of the training dataset, for Gaussian and Laplace Teachers and for multiple spatial dimensions. Dotted lines are the fitted power laws we fit starting from n = 700. (c-d) Fitted exponent 3 log E MSE/ log against the spatial dimension, for several dataset sizes. We fit from n = 0 to a varying (written in the legends). The thick black lines are the theoretical predictions.
5

---

Under review as a conference paper at ICLR 2020
L-periodic along each dimension. Furthermore, to make the problem tractable we assumee that the points (z live on a regular lattice, covering all the hypercube V. Therefore, the linear spacing between neighboring points is 8 Ln- This is of course a different setting than the one used in the numerical simulations presented in the previous section, yet our results below support that these differences do not matter.
Generalization error is then evaluated via the typical mean- error
E MSE E ((z) (s(
(6)
where the expectation is taken over both the Teacher process and the point at which we estimate the field, assumed to be uniformly distributed in the hypercube V. In Appendix F we prove the following:
Theorem 1. Let Kr crl w/ -o o (1wll -rr) and ks(w) es cslw-los ([wu) -as)
as |u oo, where Kr(w) and Ks(w) are the Fourier transforms of the kernels Kr(z), Ks(æ) respectively, assumed to be positive definite. We assume Kr(w) and Ks(w) has a finite limit as |wc] - 0 and that K (0) < oc. Then,
EMSE = n -B + o (n with 3=
3 1i.min(ary - d, 20r))
(7)
Moreover, in the case of Gaussian kernel the result holds valid if we take the corresponding exponent be
Apart from the specific value of the exponent in Eq. (7), Theorem implics that if the Student kemel decays fast enough in the frequency domain, then 3 depends only on the data through the behaviour of the Teacher kernel high frequencies. One then recovers B (aT d)/d, also found for the Bayes-optimal setting where the Student is identical to the Teacher.
Consider the predictions of Theorem in the cases presented in Fig. (a-b) of Gaussian and Laplace kernels. If both kernels are Laplace kernels then ar as d + and EMSE n n-/4/ which scales very slowly with the dataset size in large dimensions. If the Teacher is Gaussian kernel (OT 00) and the Student is Laplace kernel then 2(1 1 1/d), leading to 3 2 as d co. In Fig. 2 (c-d) we compare these predictions with the exponents extracted from Fig. (a-b). We plot log EE MSE/MSE//oe log -3, against the dimension of the data, varying the dataset size n. The exponents extracted numerically tend to our analytical predictions when n is large enough.
Notice that, although the theory and the experiments do assume the same distribution for the sampling points (Gw)"=> this does not seem to yield any difference in the asymptotic behavior of the generalization error, leading to the conjecture that our predictions are exact even when the training set is random, and does not correspond to a lattice. The conjecture can be proven in one dimension following results of the kriging literature (Stein, 1999a), but generalization to higher d is much harder problem. Intuitively, for kernel learning performs expansion, whose quality is governed by the target function smoothness and the typical distance òmin between a point and its nearest neighbors in the training set. Both for random points or on lattice, one has òmin enough, thus both situations lead to the same 3.
1/2 when n is large
Theorem underlines that kernel methods are subjected to the curse of dimensionality. Indeed for appropriate students, one obtains 3 (arr d)/ d. Let us define the smoothness index = [(T d)/2] = 3d/2, which must be ((d) to avoid - for large d. The two Lemmas below, derived in Appendix, indicate that the target function is time differentiable (in mean-square sense). Thus learning with kernels in very large dimension can only occur the target function is (dd) times differentiable, a condition that appears very restrictive in large d.
Lemma 1. Ler K K(x, x') be a coasslation-inaaiian isotropic kernel such that K(w) = cl|w|| + [[wil-a as w| + 0c and | " (w) - 0 as [|l] + 0. If > d + for some n. E z then K( E C", that is, is at least n-times differentiable. (Proof in Appendix G).

---

Under review as a conference paper at ICLR 2020
Lemma Lei Z (O K) d-dlmmnnsionl Gaussian random field, with K C being 2n-times differentiable kernel. Then Z is n-times mean Sean-square differentiable in the sense that
derivatives of (z) are a Gaussian random fields;
Ed 0 (x) = 0;
B0 ... ad ((z) 0z1 ...00 ((z') = 0. Saat K(I - x²) < 0o if the derivatives of K exist.
In particular, E0T, (x)) 0 Z(z)
Smm K(r - x') < 00 Vm S (Proof in Appendix G).
EFFECTIVE DIMENSION OF DATA SETS
(a)
(b)
mmin > (nommaizzed)
10
Random d=15
14.43
6x
d
MNIST
d:35
Random d=15
du
CIFAR10
4x
dn 35.00
Random d=35
10'
10"
10
10" 10
10'
10
10"
10" 10"
Figure 3: Average distance from one point to its nearest neighbor function of the dataset size (a) For random points on d-dimensional hypersphere, (6min) n Colored solid curves found numerically, dashed lines are the theoretical asymptotic prediction and the gray lines are numerical fit (we fitted only starting from match the data at n 10). The larger d, the stronger the preasymptotic effects (a larger is needed observe the predicted scaling). (b) Comparison between random data on 15- and 35-dimensional hyperspheres and the MNIST, CIFAR 10 datasets. According to this definition of effective dimension, MNIST live on 15-dimensional manifold and CIFAR10 on 35-dimensional one. Data have been rescaled along the y-axis for ease of comparison.
6000 reduce finite size effects, and the fit have been rescaled to
If we approximate the nigh-dimensional MNIST and CIFAR10 datasets with Gaussian random fields, to obtain the curves shown in Fig. and to find the values the we report for these fields would have to be hundreds of times differentiable, which seems unrealistic. A possible resolution of this paradox lies the fact that the data live in a much smaller manifold than the number of pixels of these pictures would suggest. As argued above, key determinant of kernel performance is the typical distance 8min between point in the training set and its nearest neighbor. We define the effective dimension des accordingly from the asymptotic relationship between 8min and n:
8min n 1/eex
For random points on d-dimensional hypersphere 6min displays fluctuations and the scaling is valid only on average and only asymptotically, that for larger than some characteristic scale n' (d) that depends on the spatial dimension. In Fig. 3 (a) we show how the typical dmin scales with the dataset size n for random points on hyperspheres dimension = 15 and
35. Notice that while for d = 15 the asympiotic regime is reached when 10 for d = 35 larger dataset is needed, with n > 108 points (that is about the maximum size of the dataset that we can use to apply kernel methods in our simulations, due to memory constraints). One naturally wonder whether real data are also subjected to a scaling relation like in Eq. (8), from which an effective dimension can be defined. Consider for instance the MNIST dataset, and sample from subset of n pictures. For each

---

Under review as a conference paper at ICLR 2020
point we could compute the distance from its nearest neighbor and average such quantities. As the number of data points increases, we expect that this measure characterizes the geometry of the local manifold where the data live in, since nearest neighbors are going to be closer and closer. In Fig. (b) we present how min scales with n for the MNIST and CIFARIO I0 datasets. Both display power-law decay, but the exponent is not compatible with 3/a with d the spatial dimension, namely d = 784 for MNIST and d = 3072 for CIFAR 10. MNIST actually seems to scale pretty much like random data on a hypersphere with 15, and CIFARIO scales approximately as random data on hypersphere with d = 35. For this reason, the effective dimensions of these datasets are consistent with:
d MNNIT 15
CIFARIO R 35.
Obviously, the intrinsic dimension of the data could vary in data space, as has been reported for MNIST (Costa and Hero, 2004; Hein and Audibert, 2005; Rozza et al., 2012; Facco et al., 2017). In this qualitative discussion neglect such subtle effects. Interestingly, effective dimensions leads to reasonable values for the effective smoothness:
Scff = 3ddtt/ /
In particular we find 8 R 3 for MNIST and 8 R 1 for CIFAR10.
7 CONCLUSION
In this work we have shown for CIFARIO and MNIST respectively that kemell regression and classification display power-law decay in the learning curves, quite remarkably with essentially the same exponent (3, found to be larger for MNIST. These exponents are much larger than 3 1/d expected for Lipschitz target functions and smaller than 3 1/2 expected for RKHS target functions. This observation led us to introduce a framework in which data are modeled as Gaussian random fields of varying smoothness, in which intermediary values of 3 are obtained.
is important to note the high degree of smoothness underlying the RKHS hypothesis. Consider realizations (z) of Teacher Gaussian process with covariance Kr and assume that they lie in the RKHS of the Student kernel Ks, namely
E Z = EE (g)dy(())s5 v) = f Kr (r)) (w) < oo.
If the Teacher and Student kernels decay in the frequency domain with exponents aT and as respectively, convergence requires at as and (s( x dw Ks(w) (w) co (true for many commonly used kernels) implies o,s > d. Then using Lemma and Lemma 2 we can conclude that the realizations (αx) must be least 14/2j-time mean- equars differentiable to be RKHS.
From this perspective, the RKHS assumption appears to be very strong, and thus may not provide an accurate description of various empirical learning curves. Our assumption that data are generated by Gaussian random processes is milder, and may thus have broader applications. Yet, we view this approximation first step on which to build on, later include other effects such as noise in the data and deviations from Gaussianity.
ACKNOWLEDGMENTS
Anonynized for double-bline review.
REFERENCES
M. Allegra, Facco, Laio, and Mira. Clustering by the local intrinsic dimension: the hidden structure of real-world data. arXiv preprint 1902. 10459, 2019.
S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv:1904; 19555, 2019.
B. Aubin, A. Maillard, F. Krzakala, N. Macris, L. Zdeborová, al. The committee machine: Computational to statistical gaps in learning a two-layers neural network. In Advances in Neural Information Processing Systems, pages 3223-3234 2018.
8

---

Under review as a conference paper at ICLR 2020
F. Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, (8(1))629-688) 2017.
J. Barbier, F, Krzakala, N. Macris, L. Miolane, and L. Zdeborova. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116:201 802705, 03 2019. doi: 10.1073/pnas. 1..1773/paa.18827751111 1802705116.
Bruna and Mallat, Invariant scattering convolution networks. IEEE transactions on puttern analysis and machine intelligence, 1878):1872-1886 2013.
A. Costa and A. O. Hero. Learning intrinsic dimension and intrinsic entropy of high-dimensional datasets. In 2004 12th European Signal Processing Conference, pages 369-372. IEEE, 2004.
A. Engel and C. Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
E. Facco, M. d'Errico, A. Rodriguez, and A. Laio. Estimating the intrinsic dimension of datasets by minimal neighborhood information. Scientific reports, 7(1):12140, 2017.
S. Franz, Hwang, and Urbani. Jamming multilayer supervised learning models. arXiv preprint arXiv: 2018.
M. Gabrié, A. Manoel, C. Luneau, N. Macris, F. Krzakala, L. Zdeborová, al. Entropy and mutual information in models of deep neural networks. In Advances in Neural Information Processing Systems, pages 1821-1831, 2018.
P. Grassberger and I. Procaccia. Measuring the strangeness of strange attractors. Physica D: Nonlinear Phenomena, 911-2)1889220 1983.
M. Hein and J.-Y. Audibert. Intrinsic dimensionality estimation of submanifolds in r d. In Proceedings of the 22nd international conference on Machine learning, pages 289-296. ACM, 2005.
J. Hestness, S. Narang, N. Ardalani, G. and Zhou. Deep learning scaling is predictable, empirically. CoRR, abs/ 2017.
Diamos, Jun, H. Kianinejad, M. M. A. Patwary, Y. Yang,
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in Neural Information Processing Systems 31, pages 8580 8089-589..18 2018
E. Levina and Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems, pages 777-784, 2005.
U. v. Luxburg and O. Bousquet. Distance-based based classification with lipschitz functions. Journal of Machine Learning Research, 5(un))669-695, 2004.
G. Matheron. Principles of geostatistics. Economic geology, 58(8):1246-1266) 1963.
R. Monasson and R. Zecchina. Weight space structure and internal representations: direct approach to learning and generalization multilayer neural networks. Physical review letters, 7532))2243, 1995.
M. Opper and Saad. Advanced mean field methods: Theory and practice. MIT press, 2001.
A. Rozza, G. Lombardi, C. Ceruti, E. Casiraghi, and P. Campadelli. Novel high intrinsic dimensional- ity estimators. Machine learning. 891--))337-65, 2012.
A. Rudi and I.. Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, pages 3215-3225, 2017.
D. Saad and S. A. Solla. On-line learning in soft committee machines. Physical Review E, 52(4): 4225, 1995.
B. Scholkopf and A. J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.

---

Under review as a conference paper at ICLR 2020
A. J. Smola, B. Schölkopf, and K.-R. Müller. The connection between regularization operators and support vector kemels.. Neural networks, 11(4):637-66) 649, 1998.
M. L. Stein. Predicting random fields with increasing dense observations. The Annals of Applied Probability, 91):242-223, 1999a.
M. Stein. Interpolation of spatial data: some theory for kriging. Springer Science Business Media, 1999b.
C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume 2. MIT Press Cambridge, MA, 2006.
L. Zdeborová and F. Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 6555)453-555, 2016.
10

---

Under review as a conference paper at ICLR 2020
A SOFT-MARGIN SUPPORT VECTOR MACHINES
The kernel classification task is performed via the algorithm known as soft-margin Support Vector Machine.
We want to find function (z(z) such that its sign correctly predicts the label of the data. In this context we model such a function as a linear prediction after projecting the data on a feature space via 2 > (zz):
Zs(r) = w 2g (
+
(10)
where uz are parameters be learned from the training data. The kernel related the feature space via (2(222') z') points. Ideally we want have some large margins E, 1, but we allow some of them to be smaller by introducing the slack variables çn and penalizing large values. To achieve this the
(z) Lz(z) &g (z'). We require that (zs (z,) 1 E, for training
following constrained minimization performed:
min b.g
W 2 + C
ΣE Ep
subjected to Vp Z(zx)
w 25((E) +b] 2 1- Eur Ey 2 0. (11)
This problem can be expressed in a dual formulation as
n
min 2 2a Qse
au
subjected
a- 05 SC,
(12)
where QS. = (r,
and Z is the vector of the labels of the training points. Here C= 10 in our simulations) controls the trade-off between minimizing the training error and
maximizing the margins εn. For the details we refer to (Scholkopf and Smola, 2001). If a* the solution to the minimization problem, than
Ean0s(En)
(13)
(Ix,)= - Σ Ks for any μ such that au < C.
(14)
The predicted label for unseen data points is then
sign [s(z)) = sign( Σ Zlg Kss b*)
(15)
The generalization error is now defined as the probability that an unseen image has a predicted label different from the true one, and such probability is again estimated as an average over with Rest elements:
1
Neast
sign (2S(E,)) Z(En))
Error
0
(16)
Tleest
B DIFFERENT KERNEL VARIANCES
In Fig. 4 we show the learning curves for kernel regression the MNIST (parity) dataset - the same setting as Fig. (a). Several Laplace kernels of varying variance o are used. The variance ranges several orders of magnitude and the learning curves all decay with the same exponent, although for o = 10 the algorithm achieves suboptimal performance and the test errors are increased by some factor.
11

---

Under review as a conference paper at ICLR 2020
10
==10
d=
10000
10a
10
Figure 4: Learning curves for kernel regression on the MNIST dataset. Regression is performed with several Laplace kernels of varying variance a ranging from 10 to 10000.
C DIFFERENT CHOICE OF KERNEL VARIANCES
In Fig. 5 we show the learning curves for the Teacher-Student kernel regression problem, with Student kernel that is always Laplace and a Teacher that can be either Gaussian or Laplace. We show how the test error decays with the size of the training dataset and how the asymptotic exponent depends on the spatial dimension. Every experiment is run with two different choices of the kernel variances: in one case σT = as d and in the other or dg 10. We observed that scaling the variances with the spatial dimension leads faster to the results that we predicted in this paper, but overall the choice has little effect on the exponents (both tend towards the prediction as the dataset size is increased).
10a
Gaussian
-1.5
d-4
d=8
2.0
d6
log MSEilog
10-4
MMSE
Gaussian Laplace 0 101---
Gaussian-L Gausssen-Lapploo g
-3.0
Aae-10
7154
n=64
10-4
n7255
n7256
d-8
-3.5
n=1024
de
18
n-61192
(1+8152
0.0
-0.2
10
log MMgtogg
0.4
Laplace
Laplace-4 aplace
-0.6
MBE - --300-111
MSE ny-
Loplace-Loplaced
Laplace-Laplace dm
d=8
d-4
d=4
d=B
16
-0.8
n7128
n=1024
n7256
n=1024
(-40006
-1.0
10'
Figure 5: In these plots we show the results for the Teacher-Student kernel regression. The Student is always a Laplace kernel, the Teacher is either Gaussian or Laplace. The four plots on the left depict the equare error against the size of the dataset for different spatial dimensions of the data, those on the right show the fitted asymptotic exponent against the spatial dimension for different dataset sizes. For every case we show both the results for oT = og = and oT = os = 10.
12

---

Under review as a conference paper at ICLR 2020
d=6 o:
d=6 d:
d=6 a
6x
6m66
10F
0
10-1
1077
10
N5R
MSE.
10"1
3x
10"4
10-1
Laplace Laplace
10-1
Guassian Gaussian
10"1
10
10
10
10
8/n
The test error of Laplace Teacher (ar = d+ 1) with a Gaussian Student (ag = oo) decays as a power law with the predicted exponent / a min(1, 00) = in d dimensions. Center: When both the Teacher and the Student are Gaussian the test error decays faster than any power law as the number n of data increased. This plot confirm this by showing that the logarithm of the test error decays linearly as a function of ns. Right: Comparison between the learning curves for the cases where both kernels either Laplace (top blue line) or Gaussian (bottom orange line). While the former decays algebraically with the predicted exponent, the latter decays exponentially, in agreement with the prediction 3 found within framework. In all these plots we have taken the variances both the Teacher and Student kernels to be equal to the dimension d = 6.
Figure 6: Left:
D GAUSSIAN STUDENTS
In this appendix we present the learning curves of Gaussian Students: the Fourier transform of these kernels decays faster than any power law and
effectively consider og oc. If the Teacher is Laplace (AT d + 1) then the predicted exponent is finite and takes the values 1 min(ar- d, 2as) 1/ min(1, o0) 5. Such case is displayed in Fig. (left) in dimension d = 6. However, if we consider the Teacher to be Gaussian as well, then the predicted exponent minn(o,, 00) = oo. This case corresponds to Fig. 6 (center): the test errors decays
would be 3 faster than power law. In Fig. (right) we compare the case where both kernels are Gaussian the case where both kernels are Laplace: while the latter decays as a power law, the former decays much faster.
E MATÉRN TEACHERS
To further test the applicability of theory, show here some numerical simulations for a Teacher kernel that a Matérn covariance function and a Laplace kernel as student. We ran the simulations in Id: the data points sampled uniformly I-dimensional circle embedded in IR, Matérn kernels are parametrized by parameter v > 0:
21-v
Kr(x) T(v) z (x),,
(17)
where 2 1 (a being the kernel variance), I' is the gamma function and Kr, is the Bessel function of the second kind with parameter v. Interestingly we recover the Laplace kernel for 1/2 and the Gaussian kernel for xo. As one can find in e.g. (Williams and Rasmussen, 2006), the exponent aT that governs the decay at high frequency this kernels is ar = d + 2v. Varying v we can change the smoothness of the target function.
For our prediction for the learning curve exponent 3 is
β =
min - d, 20g) = min 4).
(18)
In Fig. we verify that our prediction matches the numerical results.
13

---

Under review as a conference paper at ICLR 2020
Teacher Matérn, Student Laplace, d 1, 8 min(2v, 4)
10
10-4
MSE
10
0=0.5, #=10
v= p=2
10-9
2- 8
4- B
8= #=4
10
10a
10a
Figure 7: Mean-squared error for Matérn Teacher kernels and Laplace students, The variance of the kernels equal for all the curves.
F PROOF OF THEOREM
We prove here Theorem
Theorem Let (r(w) = orlwl-or + o(wl]] and Ks(w) cslwl-oo -as + (wwl -as) as we + oo, where Kr(w) and Ks(w) are the Fourier transforms of the kernels Kr(x), Ks(x) respectively, assumed to be positive definite. We assume Kr(w) and Ks(w) has a finite limit as w 0 and that K (()) co. Then,
MSE = - + (n with == 3= min(ar - d, 20g)-
(19)
d
Moreover, in the case of Gaussian kernel the result holds valid if we take the corresponding exponent to be 20.
Proof. Our strategy is to compute how the mean-square test error scales with distance 5 between two nearest neighbors on the d-dimensional regular lattice. At the end, we will use the fact that x 1/2 where is the number of sampled points the lattice.
We denote by F(w) the Fourier transform of function F R:
F(w) = L-42/2 /
2T
dze-i=iF(s)
where w EL=
zd
(20)
L
F L -
iu f F(w).
(21)
EEL
~ ((0, K) a Gaussian field with translation-invariant covariance K then by definition
[7(z))(z))) = -')--
(22)
14

---

Under review as a conference paper at ICLR 2020
Properties of the Fourier transform of Gaussian field:
((w) = ((--)) w E R.
(23)
E2 (w) 0, (w)) L 8ww K(w).
(24)
(25)
Eq. (23) comes from the fact that (xx) is an even, real-valued function. The real and imaginary
parts of (w) are Gaussian random variables. They are all independent except that 2(-w) (w)) Eq. (25) follows from the fact that (z) and (xx) are L-periodic functions, and therefore f K (w) the Fourier transform of K( + _ if u E 2224.
#
The solution Eq. (3) for kernel regression has two interpretations. In Section we introduced as quantity that minimizes a quadratic error, but it can also be seen the maximum-atpositrricn (MAP) estimation of another formulation of the problem (Williams and Rasmussen, 2006). The field (zx is assumed to be drawn from Gaussian distribution with covariance function K (z)z): Ks therefore plays a role the prior distribution of the data Z = (Zm)) Inference about the value of the field g (2x another location is then performed by maximizing its posterior distribution,
Zs(z) arg max (Z(z)
(26)
Such a posterior distribution is Gaussian, and its mean - and therefore also the value that maximizes the probability iss is exactly Eq. (3):
(z(z) ks(z) Kg' Z.
(27)
where where Z (Z(z,)) ) (Ks(En (x)) l_v= the Gram matrix, that is invertible since the kernel Ks is assumed to be positive definite. By Fourier transforming this relation we find
μ=1 are the training data, (5(x) (K
x)) x)) and Ks
Zs(w) = [w) Ks
(28)
(
where we have defined F*(w) Eneza (w+
for generic function F.
Another way to reach Eq. (28) is to consider that we are observing the quantities
2mn
(*(w) = 8d L-
Z(z)
W +
(29)
5
zElattice
7E24
Given that we know the prior distribution of the Fourier components on the right-hand side in Eq. (29),
we can infer their posterior distribution once their sums are constrained by the value of 2 (w), and straightforward see that we recover Eq. (28).
The mean-square error can then we written using the Parseval-Planchene identity,
E MSE L --48 / dx (Z(z) 2 = - Σ
K (sw)
((w) ('
(30)
K (w)
ELL
15

---

Under review as a conference paper at ICLR 2020
By taking the expectation value with respect to the Teacher and using Eq. (23)-Eq. (25) we can write the mean-square error as
E MSE
E
Σ
2
w (w))
w
Z W
Kg (w)
+
-
20
W
S
w
WEL
K w
K
w
(w)) ((w) -2 Ks(w)
2nn
L E
Z w 7
w +
+
K m
WEL
nE24
(w)
Σ
7
w
2T
Z
w +
2TT''
K3 W
L 4/2
Kr(wi (w)
2
Kg w
Kr(w) (0)
Kz(w)) (w)
Σ
Kr
W +
2T
K w
K 2 (w)
WEL
nEZ"
(w) - Kr KK Ks] (w)
(w) (2
(w)
L --
(31)
Kz(w)
Rz(w)²
where B = [- 8: 5] is the Brillouin zone.
At high frequencies, Kr(w) cr w Therefore:
+ o (1 and Ks(w)
cs |u| as +
@[]w] ass).
(7(w)= = (K(() 8 CT
ww + 27n ar + o
nEZa) (0)
(w))) + 8 or (1rd)) + ar). (32)
This equation defines the function vh,, and a similar equation holds for the Student as well. The hypothesis (r)(0) x J dw Kr(w) < oc implies or > d and therefore Σnez" |n]|-ar < oo (and likewise for the Student). Then, Yar (0), Las (0) are finite; furthermore, the w's in the sum Eq. (31) are at most of order O (8-1), therefore the terms do (wo' are O and do not influence how Eq. (31) scales with 8. Applying Eq. (32), expanding for 8 1 and keeping only the leading orders. we find
E ESSE=
2005 Kr(w) 5aas + o (lw1-00) + o (1
4/a
Σ weLng
20r 2cr Var (wō) + esrbrag (w))
K3 (w)
Kr (w) K3 (w)
T-/
20T (wō)8aT es (w))
(w))
8aa0
to [w]] or -r
+0 |w 2ag
WELnB
(33)
We have neglected terms proportional to, for instance, tor since they are subleading with respect to gar, but must keep both 80r and gas since we do not know priori which one is dominant.
The additional term 8-d in the subleading terms comes from the fact that [LO B = O (8-d).
The first term Eq. (33) the simplest to deal with: since |wō] is smaller than some constant for all E IL n B and the function vor (wo) has a finite limit, we have
20t (wo) = O (8 ( (LDB) = O (gar-d).
(34)
WELNB
We then split the second term in Eq. (33) in contributions:
16

---

Under review as a conference paper at ICLR 2020
Small |
We consider "small" all the terms Ln B such that
|w| < r, where I > i O
but large. As + O, 2/2a5 (wo) + 2/20s (0) which finite because K (0) < co. Therefore
Kr (w:
Kr(w)
82as Σ
cs (w))
2aas
ce Cgg a
(35)
K3
K (w)
WELnn <T
weLng
12 |<r
The summand is and strictly positive because the positive definiteness of the kernels implies that their Fourier transforms are strictly positive. Moreover, as 8 - 0, LLBn ([|wl 1,, which contains finite number elements, independent of d. Therefore
< LO
[lwl <
KT(w) O (D2as). K2(w)
82as Σ
cs cisi (wo)
(36)
wELnB RR <T
Large |ell "Large" w are those with |// > r: we recall that P > is O(09) but large. This
allows us to approximate Kr, Kg in the sum with their asymptotic behavior:
Kr w
8208
Σ
cs (w))
220s
Σ
w
+20 + o + ar +20s) 2
K3
wELnB 10 sr
WELnB 1
1/
828
dw
w d-1--ar--- +2as + (lwll-arrtas
arr aar2222s))))))
(quul(ar-d2as))
(37)
Finally, putting Eq. (34), Eq. (36) and Eq. (37) together,
EMSE = o gmin(ar-d200
(38)
The proof is concluded by considering that = (/a)
In the case of a Gaussian kernel ((x) x exp(-1=11 (=)o=) and therefore K(w) oc exp(-o²|[u 22/ - one has to redo the calculations starting from Eq. (31), but the final result
can be easily recovered by taking the limit - +o0 (Gaussian kernels decay faster than any power law).
G PROOFS OF LEMMAS
Lemma Let K
K(x, x') be a tronslation-imvariant isotropic kernel such that K (w) = c/wll (1wl -x) as |wll + do and [ [[((())) (w) + as |wi| - 0. a > d + n nofor some n E Z+, then
K 2 C", that is, it is at least n-times differentiable.
Proof. The kernel is rotational invariant in real space (K(x)= K ((I+=:) and therefore also in the frequency domain. Then, calling Ol,O,...) the unitary vector along the first dimension IT,
K(x) /
Idw dw o dw ((w)))
(39)
It follows that
1 K(x) x I dw - (w- ee K [(ww]) /
f dew w - E. " ([w])) x
/ dw w-ttm- l' déi cos(())) x 1.² dw wwwwd-ltm R(w).. (40)
We want to claim that this quantity is finite if m S Convergence at infinity requires that is always smaller than or equal to n because of the hypothesis of the lemma. Convergence in zero requires that # [(())))))))))))))) - 0, and we want this to hold for all < m < a d, the most constraining being the condition with 0.
d.
17

---

Under review as a conference paper at ICLR 2020
Lemma 2 Let Z ())
K) be d-dimensional Gaussian random field, with K C being 2n-times differentiable kernel. Then Z is n-times differentiable in the sense that
derivatives of (x) are Gaussian random fields;
0n Z gz) 0: (z)
0% 0 Z(z') -01tti Shatnia K(x - < oo if the deriva-
24
tives of K exist.
In particular, B0 [(x) TTh Z(x') = p2mh K( x') 00 vm n.
Proof. Derivatives of (æ) are defined as limits of sums and differences of the field Z evaluated at different points, therefore they Gaussian random fields too, and furthermore it is straightforward to see that their expected value is always if the field itself is zero centered.
The correlation be computed via induction. Assume that E0 ... ((x) 0 ... ...0. 2²z'
K
[
z') holds true. Then, if we increment nt:
10 ... 0th (Iz)
lim
E 10m
0 ((x + hē1)
0t ... 8t (z))
0 2h Z(z))
h-10
lim h-1 1
10 +n/
n K(r I' + hē₂) - On t
nat K x z2)
h-:0
0% + I+
0md
+ K ( z'). (41)
Of course by symmetry the same can be said about the increase of any other exponent. To conclude the induction proof we simply recall that by definition (ZZ(())Z(z)) K(x
=²).
18


Reviews:
[{"review_id": "Sye_AQX0FH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper experimentally investigates how fast the generalization error decreases when some specific kernel functions are used in real datasets. This paper conducted numerical experiments on several datasets to investigate the decreasing rate of the generalization error, and the rate is determined for such datasets. This decreasing rate is theoretically analyzed by using the approximation theory of RKHS in the teacher-student setting. It is shown that the rate is determined with the smoothness and effective dimensionality of input. Then, the smoothness of the teacher function is also derived through this analysis.\n\nOverall, the paper is well written. I could easily follow the line. The pros and cons of the paper are summarized as follows.\n\nPros:\nThe numerical experimetns conducted in this paper are thorough, and they show interesting observations on the real datasets. This paper gives a practical information on the theoretical analysis as an empirical study.\n\nCons:\n- The approximation theory shown in this paper (Theorem 1) is closely related to well-known results on kernel interpolation. However, this paper misses several related work in the literature. The result should be properly put in the literature. See, for example, [R1].\n\n[R1] H. Wendland. Scattered Data Approximation. Cambridge University Press, Cambridge, UK, 2005.\n\n- It is mentioned that this paper investigates the \"generalization error.\" However, what is acutally done is more like \"approximation error\" analysis (about linear interpolation in RKHS). In reality, there are observation noises and thus we typically consider the generalization error. But, the teacher-student setting does not assume the existence of noise. Under existence of noise, generalization error analysis seems more appropriate as performed in [R2].\n\n[R2] I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008.\n\nMinor comment:\n- In the introduction, it is mentioned that the assumption that the target function is included in RKHS is strong. However, the teacher-student setting considered in Theorem 1 assumes this assumption. The introduction requires some modification to make the message consistent.\n\n---Update---\nThank you for your reply.\nI understand the RKHS for teacher and that for student are different. But, in the introduction, you stated as \"Yet, RKHS is a very strong assumption which requires the smoothness of the target function to increase with d (Bach, 2017) (see more on this point below), which may not be realistic in large dimensions.\", which sounds like that an assumption that the target function is included in \"some\" RKHS corresponding to a smooth kernel is a strong assumption. At least, this sentence is not saying anything about difference between teacher and student, but is just saying assuming smoothness on the target is unrealistic. For me, this sounds inconsistent to your analysis. (This is just a minor concern. I wanted to clarify my understanding of your problem setting.) \n\nI think the setting where the teacher is not included in the student RKHS is also analyzed, for example, in the following papers (there are also several related papers):\nF.J. Narcowich, J.D. Ward, and H. Wendland. Sobolev Error Estimates and a Bernstein\nInequality for Scattered Data Interpolation via Radial Basis Functions. Constr. Approx.,\n24:175–186, 2006.\nSCHEUERER, M., SCHABACK, R., & SCHLATHER, M. (2013). Interpolation of spatial data – A stochastic or a deterministic problem? European Journal of Applied Mathematics, 24(4), 601-629. \n\nTherefore, I still feel that the paper requires more expositions about the relation to the literature.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylkirUAYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies, empirically and theoretically, the learning rates of (shift-invariant) kernel learners in a misspecified setting. In the well-specified setting, the rate of kernel learners is at least $n^{-1/2}$, and in a misspecified setting assuming only Lipschitz targets, the rate is $n^{-1/d}$. Neither seems to match the experimental rate on MNIST and CIFAR-10; this paper proposes a theoretical model that can more-or-less match the experimental rate with essentially-reasonable assumptions.\n\nMy main complaint is on the basic setting of the work: in your motivation, you say \"it is nowadays part of the lore that there exist kernels whose performance is nearly comparable to deep networks.\" The main such kernel, though, is the (convolutional) neural tangent kernel of Arora et al. (2019), which unlike the kernels you study here is not shift-invariant, and your theorems do not at all apply to this kernel. This is fine, but should probably be clearer in the description.\n\nA related comment on your main theorem: your target function evaluated at every conceivable point (not just on a grid) is a sample from a Gaussian process. Samples from GPs with mean zero and covariance kernel $K_T$ almost surely are not in the RKHS $\\mathcal H_T$, but they *are* almost surely in the RKHS of any kernel $K_R$ which nuclearly dominates $K_T$ (see Lukic and Beder, \"Stochastic Processes with Sample Paths in Reproducing Kernel Hilbert Spaces\", Trans. AMS 2001). If such a kernel exists, using it as the \"student\" kernel should give us a rate of at least $n^{-1/2}$ with standard results (with some slight details still to be worked out, but should be true). Thus, it seems that your theorem implies that for $\\alpha_T < \\frac32 d$, no such translation-invariant kernel $R$ exists. This might be already easy to see from a Fourier definition of nuclear dominance, I'm not sure, but if not it is something that seems of somewhat independent interest.\n\nIt is also notable that both your practical results and your theorem are for algorithms essentially without any regularization other than the choice of kernel: the regression setting is exact interpolation, and your soft-margin uses $C = 10^4$ so is \"almost\" a hard-margin SVM. This is also fine – interpolation methods have seen a lot of interest of late, and certainly can perform well. But it's not the typical setting, and it would be interesting to see if the curves of Figure 1 look different when using e.g. a cross-validated setting for the amount of regularization.\n\nAnother complaint: you argue that applying Theorem 1 with this particular notion of effective dimension seems to give good results, but at least as it's stated, Theorem 1 doesn't actually apply with effective dimension, only ambient dimension. Is it possible to prove Theorem 1 with an appropriate version of effective dimension? I didn't carefully check the proof, but from your outlined sketch it seems like it might be only a small change.\n\nEmpirically, your investigations are nice, but it would be good to consider some other shift-invariant kernels as well: inverse multiquadric, Matérn, or spline RBF kernels would be prominent options.\n\nOverall: I think this is a worthwhile study with interesting results. The theoretical setting, though, is somewhat limited by its fundamental approach, and the experiments aren't as thorough as they could be. Also, honestly, I'm not sure ICLR is the best venue for it (if I had written this paper around this time, I probably would have submitted it to AISTATS; it's certainly not *off* topic for ICLR, but fairly distant from most work at it).\n\nSome typos:\n- Under (2): \"man-square error.\"\n- Under (25): \"where where.\"", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HklSLYXrcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In order to rationalize the existence of non-trivial exponents that can be independent of the specific kernel\nused, this paper introduces the Teacher-Student framework for kernels. In this scheme, a Teacher generates data according to a Gaussian random field, and a Student learns them via kernel regression. Theresults quantify how smooth Gaussian data should be to avoid the curse of dimensionality, and indicate that for kernel learning the relevant dimension of the data should be defined in terms of how the distance between nearest data points depends on sample numbers.\nThe paper is well written, tghe major issue of this paper is the lack of comparison with other previous methods. Therefore, the efficacy of the proposed model can not be well demontrated.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies, theoretically and empirically, the problem when generalization error decreases as $n^{-\beta}$ where $\beta$ is not $\frac{1}{2}$. It analyses a Teacher-Student problem where the Teacher generates data from a Gaussian random field. The paper provides a theorem that derives $\beta$ for Gaussian and Laplace kernels, and show empirical evidence supporting the theory using MNIST and CIFAR.

The reviews contained two low scores, both of which were not confident. A more confident reviewer provided a weak accept score, and interacted multiple times with the authors during the discussion period (which is one of the nice things about the ICLR review process). However, this reviewer also noted that ICLR may not be the best venue for this work.

Overall, while this paper shows promise, the negative review scores show that the topic may not be the best fit to the ICLR audience.
Decision: Reject