Year: 2019

Abstract:
How many training data are needed to learn a supervised task? It is often observed that the generalization error decreases as n−β where n is the number of training examples and β an exponent that depends on both data and algorithm. In this work we measure β when applying kernel methods to real datasets. For MNIST we find β ≈ 0.4 and for CIFAR10 β ≈ 0.1. Remarkably, β 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 β for translation invariant kernels, using previous results from the kriging literature. Provided that the Student is not too sensitive to high frequencies, β 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.

heading: 1 INTRODUCTION
text: In supervised learning machines learn from a finite collection of n training data, and their generalization 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 a power law n−β , with an exponent β that depends on both the data and the algorithm. In (Hestness et al., 2017) β is reported for state-of-the-art (SOTA) deep neural networks for various tasks: in for neural-machine translation β ≈ 0.3–0.36 (for fixed model size) or β ≈ 0.13 (for best-fit models at any n); language modeling shows β ≈ 0.06–0.09; in speech recognition β ≈ 0.3; SOTA models for image classification (on ImageNet) have exponents β ≈ 0.3–0.5. Currently there is no available theory of deep learning to rationalize these observations. Recently it was shown that for a 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 to 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 Lipschitz, then the best guarantee is β = 1/d (Luxburg and Bousquet, 2004; Bach, 2017) where d is the data dimension. Thus for large d, β is very small: learning is completely inefficient, a phenomenon referred to as the curse of dimensionality. As a 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 β does not depend on d (for instance in (Rudi and Rosasco, 2017) β = 1/2 is guaranteed). 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.
In this work we compute β empirically for kernel methods applied on MNIST and CIFAR10 datasets. We find βMNIST ≈ 0.4 and βCIFAR10 ≈ 0.1 respectively. Quite remarkably, we observe essentially the same exponents for regression and classification tasks, using either a Gaussian or a Laplace kernel. Thus the exponents are not as small as 1/d (d = 784 for MNIST, d = 3072 for CIFAR10), but neither are they 1/2 as 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 is assumed to be a Gaussian random field of zero mean with translation-invariant isotropic covariance KT (x). The data can equivalently be thought as being synthesized by a “Teacher” kernelKT (x). Learning is performed with a “Student” kernel KS(x) that minimizes the mean-square error. In general KT (x) 6= KS(x). 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 on a hypersphere of varying dimension d, focusing on a 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.
To derive β(d) we consider the simplified situation where the Gaussian random field is sampled at training points lying on a regular lattice. Building on the kriging literature (Stein, 1999b), we show that β is controlled by the high-frequency scaling of both the Teacher and Student kernels: assuming that the Fourier transforms of the kernels decay as K̃T (w) = cT ||w||−αT + o (||w||−αT ) and K̃S(w) = cS ||w||−αS + o (||w||−αS ), we obtain
β = 1
d min(αT − d, 2αS). (1)
Importantly (i) Eq. (1) leads to a prediction for β(d) 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 δ(n) between adjacent data points. δ(n) is asymptotically similar for random data or data sitting on a lattice. (ii) If the kernel KS is not too sensitive to high-frequencies, then learning is optimal as far as scaling is concerned and β = (αT − d)/d. We will argue that the smoothness index s ≡ [(αT − 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 β in large dimensions. Point (ii) leads to an apparent paradox: β is significant for MNIST and CIFAR10, for which d is a priori very large, leading to a 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-dimensional manifolds. As far as kernel learning is concerned, our findings support that the correct definition of dimension should be based on how the nearest-neighbors distance δ(n) scales with n: δ(n) ∼ n−1/deff . Direct measurements of δ(n) support that MNIST and CIFAR10 live on manifolds of lower dimensions deffMNIST ≈ 15 and deffCIFAR10 ≈ 35. Considering the effective dimensions that we find, the observed values for β would be obtained for Gaussian fields of smoothness sMNIST ≈ 3 and sCIFAR10 ≈ 1, values that appear intuitively more reasonable. More generally this analogy with Gaussian fields allows one to associate a smoothness index s to any dataset once β and deff are measured, which may turn out to be a useful characterization of data complexity in the future.

heading: 2 RELATED WORKS
text: Our set-up of Teacher-Student 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 on a high-dimensional regular lattice. Similar results have been previously derived in the kriging literature (Stein, 1999b) when sampling occurs on 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 at the origin,
we compute the average error for a test point that lie at an arbitrary point, sampled uniformly at random and not necessarily on the lattice.
In what follows we show, via extensive numerical simulations, that such predictions are accurate even when the training points do not lie on a regular lattice, but are taken at random on a hypersphere. An exact proof of our result in such a 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 not necessarily evenly spaced.
In this work the effective dimension of the data plays an import role, as it controls how the distance between nearest neighbors scales with the dataset size. Of course, there exists a 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.

heading: 3 LEARNING CURVE FOR KERNEL METHODS APPLIED TO REAL DATA
text: In what follows we apply kernel methods to the MNIST and CIFAR10 datasets, each consisting of a set of images (xµ) n µ=1. We simplify the problem by considering only two classes whose label Z(xµ) = ±1 correspond to odd and even numbers for MNIST, and to two groups of 5 classes in CIFAR10. The goal is to infer the value of the label ẐS(x) of an image x that does not belong to the dataset. The S subscript reminds us that inference is performed using a positive definite kernel KS . We perform inference in both a regression and a classification setting. The following algorithms and associated results can be found in (Scholkopf and Smola, 2001).
Regression. Learning corresponds to minimizing a mean-square error:
min n∑ µ=1 [ ẐS(xµ)− Z(xµ) ]2 . (2)
For algorithms seeking solutions of the form ẐS(x) = ∑ µ aµKS(xµ, x) ≡ a · kS(x) by minimizing the man-square loss over the vector a, one obtains:
ẐS(x) = kS(x) ·K−1S Z, (3)
where the vector Z contains all the labels in the training set, Z ≡ (Z(xµ))nµ=1, and KS,µν ≡ KS(xµ, xν) is the Gram matrix. The Gram matrix is always invertible if the kernel KS is positive definite. The generalization error is then evaluated as the expected mean-square error on unseen data, estimated by averaging over a test set composed of ntest unseen data points:
MSE = 1
ntest ntest∑ µ=1 [ ẐS(xµ)− Z(xµ) ]2 . (4)
Classification. We perform kernel classification via the algorithm soft-margin SVM. The details can be found in Appendix A. After learning from the training data with a 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 ntest elements.
In Fig. 1 we present the learning curves for (binary) MNIST and CIFAR10, for regression and classification. Learning is performed both with a Gaussian kernel K(x) ∝ exp(−||x||2/(2σ2)) and a Laplace one K(x) ∝ exp(−||x||/σ). 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 a very similar behavior, compatible with the same exponent: about −0.4 for MNIST and −0.1 for CIFAR10. The presented data are for σ = 1000; in Appendix B we show that the same behaviour is observed for different values.

heading: 4 GENERALIZATION SCALING IN KERNEL TEACHER-STUDENT PROBLEMS
text: We study β in a simplified setting where the data is assumed to follow a Gaussian distribution with known covariance. It falls into the class of teacher-Student problems, which are characterized by a machine (the Teacher) that generates the data, and another machine (the Student) that tries to learn from them. The Teacher-Student 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; Aubin et al., 2018; Franz et al., 2018). He we restrict our attention to kernel methods: we assume that a target function is distributed according to a Gaussian random field Z ∼ N (0,KT ) — the Teacher — characterized by a translation-invariant isotropic covariance function KT (x, x′) = KT (||x−x′||), and that the training dataset consists the finite set of n observations Z = (Z(xµ)) n µ=1. This is equivalent to saying that the vector of training points follows a centered Gaussian distribution with a covariance matrix that depends on KT and on the location of the points (xµ) n µ=1:
Z ∼ N (0,KT ) , where KT = (KT (xµ, xν))nµ,ν=1. (5)
Once the Teacher has generated the dataset, the rest follows as in the kernel regression described in the previous section. We use another translation-invariant isotropic kernel KS(x, x′) — the Student — to infer the value of the field at another point, ẐS(x), 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 to be a Laplace kernel, and the Teacher is either a Laplace kernel or a Gaussian kernel. The
points (xµ) n µ=1 are taken uniformly at random on the unit d-dimensional hypersphere for several dimensions d and for several dataset sizes n. We take σS = σT = d as we observed that with this choice smaller datasets were enough to approach a limiting curve — in Appendix C we show the plots for the case σS = σT = 10, which appears to converge to the same limit curve with increasing n, but at a smaller pace. The figure shows that when n is large enough, the mean-square error behaves as a power law (dashed lines) with an exponent that depends on the spatial dimension of the data, as well as on the kernels. The fitted exponents are plotted in Fig. 2 (c-d) as a 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 a thick black line. The figure shows that as the dataset gets bigger, the asymptotic exponent tends to our prediction. In Appendix D we present the learning curves of Gaussian Students with both a Laplace and a 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).

heading: 5 ANALYTIC ASYMPTOTICS FOR THE KERNEL TEACHER-STUDENT PROBLEM
text: ON A 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. In order to derive the result we assume that both the Teacher Gaussian random field lives on a bounded hypercube, x ∈ V ≡ [0, L]d, where L is a constant and d is the spatial dimension. The fields and the kernels can then be thought of
as L-periodic along each dimension. Furthermore, to make the problem tractable we assume that the points (xµ) n µ=1 live on a regular lattice, covering all the hypercube V . Therefore, the linear spacing between neighboring points is δ = Ln−1/d. 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-square error EMSE = E [ Z(x)− ẐS(x) ]2 , (6)
where the expectation is taken over both the Teacher process and the point x 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 K̃T (w) = cT ||w||−αT + o (||w||−αT ) and K̃S(w) = cS ||w||−αS + o (||w||−αS ) as ||w|| → ∞, where K̃T (w) and K̃S(w) are the Fourier transforms of the kernels KT (x), KS(x) respectively, assumed to be positive definite. We assume K̃T (w) and K̃S(w) has a finite limit as ||w|| → 0 and that K(0) <∞. Then,
EMSE = n−β + o ( n−β ) with β = 1
d min(αT − d, 2αS). (7)
Moreover, in the case of a Gaussian kernel the result holds valid if we take the corresponding exponent to be α =∞.
Apart from the specific value of the exponent in Eq. (7), Theorem 1 implies that if the Student kernel decays fast enough in the frequency domain, then β depends only on the data through the behaviour of the Teacher kernel at high frequencies. One then recovers β = (αT − d)/d, also found for the Bayes-optimal setting where the Student is identical to the Teacher.
Consider the predictions of Theorem 1 in the cases presented in Fig. 2 (a-b) of Gaussian and Laplace kernels. If both kernels are Laplace kernels then αT = αS = d + 1 and EMSE ∼ n−1/d, which scales very slowly with the dataset size in large dimensions. If the Teacher is a Gaussian kernel (αT =∞) and the Student is a Laplace kernel then β = 2(1 + 1/d), leading to β → 2 as d→∞. In Fig. 2 (c-d) we compare these predictions with the exponents extracted from Fig. 2 (a-b). We plot logEMSE/ log n ≡ −β, against the dimension d 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 not assume the same distribution for the sampling points (xµ) n µ=1, 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 a much harder problem. Intuitively, for kernel learning performs an 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 a lattice, one has δmin ∼ n−1/d when n is large enough, thus both situations lead to the same β.
Theorem 1 underlines that kernel methods are subjected to the curse of dimensionality. Indeed for appropriate students, one obtains β = (αT − d)/d. Let us define the smoothness index s ≡ [(αT − d)/2] = βd/2, which must be O(d) to avoid β → 0 for large d. The two Lemmas below, derived in Appendix, indicate that the target function is s time differentiable (in a mean-square sense). Thus learning with kernels in very large dimension can only occur if the target function is O(d) times differentiable, a condition that appears very restrictive in large d.
Lemma 1. LetK(x, x′) be a translation-invariant isotropic kernel such that K̃(w) = c||w||−α+ o (||w||−α) as ||w|| → ∞ and ||w||dK̃(w)→ 0 as ||w|| → 0. If α > d+n for some n ∈ Z+, then K(x) ∈ Cn, that is, it is at least n-times differentiable. (Proof in Appendix G).
Lemma 2. Let Z ∼ N (0,K) be a d-dimensional Gaussian random field, with K ∈ C2n being a 2n-times differentiable kernel. Then Z is n-times mean-square differentiable in the sense that
• derivatives of Z(x) are a Gaussian random fields;
• E∂n1x1 · · · ∂ nd xd Z(x) = 0;
• E∂n1x1 · · · ∂ nd xd Z(x) · ∂n
′ 1 x1 · · · ∂ n′d xdZ(x ′) = ∂ n1+n ′ 1 x1 · · · ∂ nd+n ′ d
xd K(x − x′) < ∞ if the derivatives of K exist.
In particular, E∂mxiZ(x) · ∂ m xiZ(x ′) = ∂2mxi K(x− x ′) <∞ ∀m ≤ n. (Proof in Appendix G).
6 EFFECTIVE DIMENSION OF DATA SETS
If we approximate the high-dimensional MNIST and CIFAR10 datasets with Gaussian random fields, to obtain the curves shown in Fig. 1 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 in the fact that the data live in a much smaller manifold than the number of pixels of these pictures would suggest. As argued above, a key determinant of kernel performance is the typical distance δmin between a point in the training set and its nearest neighbor. We define the effective dimension deff accordingly from the asymptotic relationship between δmin and n:
δmin ∼ n− 1/deff . (8)
For random points on a d-dimensional hypersphere δmin displays fluctuations and the scaling is valid only on average and only asymptotically, that is for n larger than some characteristic scale n?(d) that depends on the spatial dimension. In Fig. 3 (a) we show how the typical δmin scales with the dataset size n for random points on hyperspheres of dimension d = 15 and d = 35. Notice that while for d = 15 the asymptotic regime is reached when n ' 104, for d = 35 a larger dataset is needed, with n > 105 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 can 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 it a subset of n pictures. For each
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. 3 (b) we present how δmin scales with n for the MNIST and CIFAR10 datasets. Both display a power-law decay, but the exponent is not compatible with 1/d with d the spatial dimension, namely d = 784 for MNIST and d = 3072 for CIFAR10. MNIST actually seems to scale pretty much like random data on a hypersphere with d = 15, and CIFAR10 scales approximately as random data on a hypersphere with d = 35. For this reason, the effective dimensions of these datasets are consistent with:
d effMNIST ≈ 15 d effCIFAR10 ≈ 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 we neglect such subtle effects. Interestingly, our effective dimensions leads to reasonable values for the effective smoothness:
seff = βdeff/2.
In particular we find s ≈ 3 for MNIST and s ≈ 1 for CIFAR10.

heading: 7 CONCLUSION
text: In this work we have shown for CIFAR10 and MNIST respectively that kernel regression and classification display a power-law decay in the learning curves, quite remarkably with essentially the same exponent β, found to be larger for MNIST. These exponents are much larger than β = 1/d expected for Lipschitz target functions and smaller than β = 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 β are obtained.
It is important to note the high degree of smoothness underlying the RKHS hypothesis. Consider realizations Z(x) of a Teacher Gaussian process with covariance KT and assume that they lie in the RKHS of the Student kernel KS , namely
E||Z||2KS = E ∫ dxd yZ(x)K−1S (x− y)Z(y) = ∫ dw K̃T (w)K̃ −1 S (w) <∞. (9)
If the Teacher and Student kernels decay in the frequency domain with exponents αT and αS respectively, convergence requires αT > αS + d, and KS(0) ∝ ∫ dw K̃S(w) <∞ (true for many commonly used kernels) implies αS > d. Then using Lemma 1 and Lemma 2 we can conclude that the realizations Z(x) must be at least bd/2c-times mean-square 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 as a first step on which to build on, to later include other effects such as noise in the data and deviations from Gaussianity.

heading: ACKNOWLEDGMENTS
text: Anonymized for double-blind review.

heading: A SOFT-MARGIN SUPPORT VECTOR MACHINES
text: The kernel classification task is performed via the algorithm known as soft-margin Support Vector Machine.
We want to find a function ẐS(x) 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 x→ φ(x):
ẐS(x) = w · φS(xµ) + b, (10)
where w, b are parameters to be learned from the training data. The kernel is related to the feature space via KS(x, x′) = φS(x) · φS(x
′). We require that Z(xµ)ẐS(xµ) > 1 − ξµ for all training points. Ideally we want to have some large margins 1 − ξµ = 1, but we allow some of them to be smaller by introducing the slack variables ξµ and penalizing large values. To achieve this the following constrained minimization is performed:
min w,b,ξ
1 2 ||w||2 + C ∑ µ ξµ subjected to ∀µ Z(xµ) [ w · φ S (xµ) + b ] ≥ 1− ξµ, ξµ ≥ 0. (11)
This problem can be expressed in a dual formulation as
min a
1 2 a ·QSa− n∑ µ=1 aµ subjected to Z · a = 0, 0 ≤ aµ ≤ C, (12)
where QS,µ,ν = Z(xµ)Z(xν)KS(xµ, xν) and Z is the vector of the labels of the training points. Here C (= 104 in our simulations) controls the trade-off between minimizing the training error and maximizing the margins 1− ξµ. For the details we refer to (Scholkopf and Smola, 2001). If a? is the solution to the minimization problem, than
w? = ∑ µ a?µφS(xµ), (13)
b? = Z(xµ)− ∑ ν aνyνKS(xµ, xν) for any µ such that aµ < C. (14)
The predicted label for unseen data points is then sign(ẐS(x)) = sign( ∑ µ Z(xµ)aµKS(xµ, x) + 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 a probability is again estimated as an average over a test set with ntest elements:
Error = 1
ntest ntest∑ µ=1 θ [ −sign ( ẐS(xµ) ) Z(xµ) ] . (16)

heading: B DIFFERENT KERNEL VARIANCES
text: In Fig. 4 we show the learning curves for kernel regression on the MNIST (parity) dataset — the same setting as in Fig. 1 (a). Several Laplace kernels of varying variance σ are used. The variance ranges several orders of magnitude and the learning curves all decay with the same exponent, although for σ = 10 the algorithm achieves suboptimal performance and the test errors are increased by some factor.

heading: C DIFFERENT CHOICE OF KERNEL VARIANCES
text: In Fig. 5 we show the learning curves for the Teacher-Student kernel regression problem, with a 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 = σS = d and in the other σT = σS = 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).
10 10
10 8
10 6
10 4
10 2
100
M SE
Gaussian-Laplace = d d = 4 d = 8 d = 16 d = 32
Gaussian-Laplace = 10 d = 4 d = 8 d = 16 d = 32
10 1
10 2
10 3
10 4
n
10 2
10 1
M SE
Laplace-Laplace = d d = 4 d = 8 d = 16 d = 32
10 1
10 2
10 3
10 4
n
Laplace-Laplace = 10 d = 4 d = 8 d = 16 d = 32
4.0
3.5
3.0
2.5
2.0
1.5
lo g
M SE
/lo gn
Gaussian-Laplace = d MSE n 2(1 + 1/(d 1))
n=64 n=256 n=1024 n=4096 n=8192
Gaussian-Laplace = 10 MSE n 2(1 + 1/(d 1))
n=64 n=256 n=1024 n=4096 n=8192
5 10 15 20 25 30 d
1.0
0.8
0.6
0.4
0.2
0.0
lo g
M SE
/lo gn
Laplace-Laplace = d MSE n 1/(d 1)
n=16 n=128 n=1024 n=4096 n=8192
5 10 15 20 25 30 d
Laplace-Laplace = 10 MSE n 1/(d 1)
n=64 n=256 n=1024 n=4096 n=8192
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 mean-square 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 the results for σT = σS = d and σT = σS = 10.
Figure 6: Left: The test error of a Laplace Teacher (αT = d+ 1) with a Gaussian Student (αS =∞) decays as a power law with the predicted exponent β = 1d min(1,∞) = 1 6 in d = 6 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 is increased. This plot confirm this by showing that the logarithm of the test error decays linearly as a function of n 1 3 . Right: Comparison between the learning curves for the cases where both kernels are 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 β =∞ found within our framework. In all these plots we have taken the variances of both the Teacher and Student kernels to be equal to the dimension d = 6.

heading: D GAUSSIAN STUDENTS
text: In this appendix we present the learning curves of Gaussian Students: the Fourier transform of these kernels decays faster than any power law and one can effectively consider αS = ∞. If the Teacher is Laplace (αT = d + 1) then the predicted exponent is finite and takes the values β = 1d min(αT − d, 2αS) = 1 d min(1,∞) = 1 d . Such a case is displayed in Fig. 6 (left) in dimension d = 6. However, if we consider the Teacher to be Gaussian as well, then the predicted exponent would be β = 1d min(∞,∞) =∞. This case corresponds to Fig. 6 (center): the test errors decays faster than a power law. In Fig. 6 (right) we compare the case where both kernels are Gaussian to the case where both kernels are Laplace: while the latter decays as a power law, the former decays much faster.

heading: E MATÉRN TEACHERS
text: To further test the applicability of our theory, we show here some numerical simulations for a Teacher kernel that is a Matérn covariance function and a Laplace kernel as student. We ran the simulations in 1d: the data points are sampled uniformly on a 1-dimensional circle embedded in R2. Matérn kernels are parametrized by a parameter ν > 0:
KT (x) = 21−ν
Γ(ν) zνKν(z), (17)
where z = √
2ν ||x||σ (σ being the kernel variance), Γ is the gamma function and Kν is the Bessel function of the second kind with parameter ν. Interestingly we recover the Laplace kernel for ν = 1/2 and the Gaussian kernel for ν =∞. As one can find in e.g. (Williams and Rasmussen, 2006), the exponent αT that governs the decay at high frequency of this kernels is αT = d+ 2ν. Varying ν we can change the smoothness of the target function.
For d = 1 our prediction for the learning curve exponent β is
β = 1
d min(αT − d, 2αS) = min(2ν, 4). (18)
In Fig. 7 we verify that our prediction matches the numerical results.

heading: F PROOF OF THEOREM
text: We prove here Theorem 1:
Theorem 1 Let K̃T (w) = cT ||w||−αT + o (||w||−αT ) and K̃S(w) = cS ||w||−αS + o (||w||−αS ) as ||w|| → ∞, where K̃T (w) and K̃S(w) are the Fourier transforms of the kernels KT (x), KS(x) respectively, assumed to be positive definite. We assume K̃T (w) and K̃S(w) has a finite limit as ||w|| → 0 and that K(0) <∞. Then,
EMSE = n−β + o ( n−β ) with β = 1
d min(αT − d, 2αS). (19)
Moreover, in the case of a Gaussian kernel the result holds valid if we take the corresponding exponent to be α =∞.
Proof. Our strategy is to compute how the mean-square test error scales with distance δ between two nearest neighbors on the d-dimensional regular lattice. At the end, we will use the fact that δ ∝ n−1/d, where n is the number of sampled points on the lattice.
We denote by F̃ (w) the Fourier transform of a function F : V → R:
F̃ (w) = L− d/2 ∫ V dx e−iw·xF (x), where w ∈ L ≡ 2π L Zd, (20)
F (x) = L− d/2 ∑ w∈L eiw·xF̃ (w). (21)
If Z ∼ N (0,K) is a Gaussian field with translation-invariant covariance K then by definition
EZ(x)Z(x′) = K(x− x′). (22)
Properties of the Fourier transform of a Gaussian field:
K̃(w) = K̃(−w) ∈ R, (23) EZ̃(w) = 0, (24)
EZ̃(w)Z̃(w′) = Ld/2δww′K̃(w). (25)
Eq. (23) comes from the fact that K(x) is an even, real-valued function. The real and imaginary parts of Z̃(w) are Gaussian random variables. They are all independent except that Z̃(−w) = Z̃(w). Eq. (25) follows from the fact that Z(x) and K(x) are L-periodic functions, and therefore eiw·xK̃(w) is the Fourier transform of K(·+ x) if w ∈ 2πL Z d. #
The solution Eq. (3) for kernel regression has two interpretations. In Section 4 we introduced it as the quantity that minimizes a quadratic error, but it can also be seen as the maximum-a-posteriori (MAP) estimation of another formulation of the problem (Williams and Rasmussen, 2006). The field Z(x) is assumed to be drawn from a Gaussian distribution with covariance function KS(x): KS therefore plays a role in the prior distribution of the data Z = (Z(xµ) n µ=1). Inference about the value of the
field ẐS(x) at another location is then performed by maximizing its posterior distribution,
ẐS(x) ≡ arg max P (Z(x)|Z) . (26)
Such a posterior distribution is Gaussian, and its mean — and therefore also the value that maximizes the probability — is exactly Eq. (3):
ẐS(x) = kS(x) ·K−1S Z, (27)
where where Z = ( Z(xµ) )n µ=1 are the training data, kS(x) = ( KS(xµ, x) )n µ=1
and KS =( KS(xµ, xν) )n µ,ν=1
is the Gram matrix, that is invertible since the kernel KS is assumed to be positive definite. By Fourier transforming this relation we find
Z̃S(w) = Z̃ ?(w)
K̃S(w) K̃?S(w) , (28)
where we have defined F ?(w) ≡ ∑ n∈Zd F ( w + 2πnδ ) for a generic function F .
Another way to reach Eq. (28) is to consider that we are observing the quantities
Z̃?(w) ≡ δdL−d/2 ∑
x∈lattice e−iw·xZ(x) ≡ ∑ n∈Zd Z̃ ( w + 2πn δ ) . (29)
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 Z̃?(w), and it is straightforward to see that we recover Eq. (28).
The mean-square error can then we written using the Parseval-Plancherel identity,
EMSE = L−dE ∫ V dx [Z(x)− ẐS(x)]2 = L−dE ∑ w∈L ∣∣∣∣∣Z̃(w)− Z̃?(w)K̃S(w)K̃?S(w) ∣∣∣∣∣ 2 . (30)
By taking the expectation value with respect to the Teacher and using Eq. (23)-Eq. (25) we can write the mean-square error as
EMSE = L−dE ∑ w∈L
[ Z̃(w)Z̃(w)− 2Z̃(w)Z̃?(w)K̃S(w)
K̃?S(w) + Z̃?(w)Z̃?(w)
K̃2S(w)
K̃?S 2 (w)
] =
= L−dE ∑ w∈L Z̃(w)Z̃(w)− 2K̃S(w) K̃?S(w) ∑ n∈Zd Z̃(w)Z̃ ( w + 2πn δ ) +
+ K̃2S(w)
K̃?S 2 (w) ∑ n,n′∈Zd Z̃ ( w + 2πn δ ) Z̃ ( w + 2πn′ δ ) =
= L− d/2 ∑ w∈L K̃T (w)− 2 K̃S(w) K̃?S(w) K̃T (w) + K̃2S(w) K̃?S 2 (w) ∑ n∈Zd K̃T ( w + 2πn δ ) =
= L− d/2 ∑ w∈L∩B K̃?T (w)− 2 [K̃T K̃S ] ?(w) K̃?S(w) + K̃?T (w)[K̃ 2 S ] ?(w) K̃?S(w) 2 , (31)
where B = [ −πδ , π δ ]d is the Brillouin zone.
At high frequencies, K̃T (w) = cT ||w||−αT + o (||w||−αT ) and K̃S(w) = cS ||w||−αS + o (||w||−αS ). Therefore:
K̃?T (w) = K̃T (w) + δ αT cT ∑ n∈Zd\{0} ||wδ + 2πn||−αT + o ( ||w||−αT ) ≡
≡ K̃T (w) + δαT cT ψT (wδ) + o ( ||w||−αT ) . (32)
This equation defines the function ψT , and a similar equation holds for the Student as well. The hypothesis KT (0) ∝ ∫ dw K̃T (w) <∞ implies αT > d and therefore ∑ n∈Zd ||n||−αT <∞ (and likewise for the Student). Then, ψαT (0), ψαS (0) are finite; furthermore, the w’s in the sum Eq. (31) are at most of order O ( δ−1 ) , therefore the terms ψα(wδ) are O(δ0) and do not influence how Eq. (31) scales with δ. Applying Eq. (32), expanding for δ 1 and keeping only the leading orders, we find
EMSE =
= L− d/2  ∑ w∈L∩B 2cTψαT (wδ)δ αT + c2Sψ2αS (wδ) K̃T (w) K̃2S(w) δ2αS + o ( ||w||−αT ) + o ( ||w||−2αS ) = = L− d/2
 ∑ w∈L∩B 2cTψαT (wδ)δ αT + c2Sψ2αS (wδ) K̃T (w) K̃2S(w) δ2αS +o (||w||−αT−d)+o (||w||−2αS−d) . (33)
We have neglected terms proportional to, for instance, δαT+αS , since they are subleading with respect to δαT , but we must keep both δαT and δαS since we do not know a priori which one is dominant. The additional term δ−d in the subleading terms comes from the fact that |L ∩ B| = O ( δ−d ) .
The first term in Eq. (33) is the simplest to deal with: since ||wδ|| is smaller than some constant for all w ∈ L ∩ B and the function ψαT (wδ) has a finite limit, we have
δαT ∑
w∈L∩B 2cTψαT (wδ) = O (δαT |L ∩ B|) = O
( δαT−d ) . (34)
We then split the second term in Eq. (33) in two contributions:
Small ||w|| We consider “small” all the terms w ∈ L∩B such that ||w|| < Γ, where Γ 1 is O(δ0) but large. As δ → 0, ψ2αS (wδ)→ ψ2αS (0) which is finite because K(0) <∞. Therefore
δ2αS ∑
w∈L∩B ||w||<Γ
c2Sψ2αS (wδ) K̃T (w)
K̃2S(w) → δ2αSc2Sψ2αS (0) ∑ w∈L∩B ||w||<Γ K̃T (w) K̃2S(w) . (35)
The summand is real and strictly positive because the positive definiteness of the kernels implies that their Fourier transforms are strictly positive. Moreover, as δ → 0, L∩B∩{||w|| < Γ} → L∩{||w|| < Γ}, which contains a finite number of elements, independent of δ. Therefore
δ2αS ∑
w∈L∩B ||w||<Γ
c2Sψ2αS (wδ) K̃T (w)
K̃2S(w) = O
( δ2αS ) . (36)
Large ||w|| “Large” w are those with ||w|| > Γ: we recall that Γ 1 is O(δ0) but large. This allows us to approximate K̃T , K̃S in the sum with their asymptotic behavior:
δ2αS ∑
w∈L∩B ||w||>Γ
c2Sψ2αS (wδ) K̃T (w)
K̃2S(w) ∝ δ2αS ∑ w∈L∩B ||w||>Γ ||w||−αT+2αS + o ( ||w||−αT+2αS ) ≈
≈ δ2αS ∫ 1/δ
Γ
dwwd−1−αT+2αS + o ( ||w||−αT+2αS ) = O ( δmin(αT−d,2αS) ) . (37)
Finally, putting Eq. (34), Eq. (36) and Eq. (37) together, EMSE = O ( δmin(αT−d,2αS) ) . (38) The proof is concluded by considering that δ = O ( n−1/d ) .
In the case of a Gaussian kernel K(x) ∝ exp(−||x||2/(2σ2)) — and therefore K̃(w) ∝ exp(−σ2||w||2/2) — one has to redo the calculations starting from Eq. (31), but the final result can be easily recovered by taking the limit α→ +∞ (Gaussian kernels decay faster than any power law).

heading: G PROOFS OF LEMMAS
text: Lemma 1 Let K(x, x′) be a translation-invariant isotropic kernel such that K̃(w) = c||w||−α + o (||w||−α) as ||w|| → ∞ and ||w||dK̃(w) → 0 as ||w|| → 0. If α > d + n for some n ∈ Z+, then K(x) ∈ Cn, that is, it is at least n-times differentiable.
Proof. The kernel is rotational invariant in real space (K(x) = K(||x||)) and therefore also in the frequency domain. Then, calling ̂1 = (1, 0, . . . ) the unitary vector along the first dimension x1,
K(x) ∝ ∫ dw eiw·̂1xK̃(||w||). (39)
It follows that |∂mK(x)| ∝ ∣∣∣∣∫ dw (w · ̂1)meiw·̂1xK̃(||w||)∣∣∣∣ < ∫ dw |w · ̂1|m|K̃(||w||)| ∝ ∝ ∫ ∞
0
dwwd−1+m|K̃(w)| ∫ π
0
dφ1| cos(φ1)|m ∝ ∫ ∞
0
dwwd−1+m|K̃(w)|. (40)
We want to claim that this quantity is finite if m ≤ n. Convergence at infinity requires m < α− d, that is always smaller than or equal to n because of the hypothesis of the lemma. Convergence in zero requires that wd+m|K̃(w)| → 0, and we want this to hold for all 0 ≤ m < α − d, the most constraining one being the condition with m = 0.
Lemma 2 Let Z ∼ N (0,K) be a d-dimensional Gaussian random field, with K ∈ C2n being a 2n-times differentiable kernel. Then Z is n-times differentiable in the sense that
• derivatives of Z(x) are a Gaussian random fields; • E∂n1x1 · · · ∂ nd xd Z(x) = 0;
• E∂n1x1 · · · ∂ nd xd Z(x) · ∂n
′ 1 x1 · · · ∂ n′d xdZ(x ′) = ∂ n1+n ′ 1 x1 · · · ∂ nd+n ′ d
xd K(x− x′) < ∞ if the derivatives of K exist.
In particular, E∂mxiZ(x) · ∂ m xiZ(x ′) = ∂2mxi K(x− x ′) <∞ ∀m ≤ n.
Proof. Derivatives of Z(x) are defined as limits of sums and differences of the field Z evaluated at different points, therefore they are Gaussian random fields too, and furthermore it is straightforward to see that their expected value is always 0 if the field itself is zero centered.
The correlation can be computed via induction. Assume that E∂n1x1 · · · ∂ nd xd Z(x) ·∂n
′ 1 x1 · · · ∂ n′d xdZ(x ′) =
∂ n1+n
′ 1
x1 · · · ∂ nd+n
′ d
xd K(x− x′) holds true. Then, if we increment n1:
E∂n1+1x1 · · · ∂ nd xd Z(x) · ∂n
′ 1 x1 · · · ∂ n′d xdZ(x ′) =
= lim h→0
h−1E [ ∂n1x1 · · · ∂ nd xd Z(x+ ĥ1)− ∂n1x1 · · · ∂ nd xd Z(x) ] · ∂n ′ 1 x1 · · · ∂ n′d xdZ(x ′) =
= lim h→0
h−1 [ ∂ n1+n ′ 1 x1 · · · ∂ nd+n ′ d xd K(x− x′ + ĥ1)− ∂ n1+n ′ 1 x1 · · · ∂ nd+n ′ d xd K(x− x′) ] =
= ∂ n1+1+n
′ 1
x1 · · · ∂ nd+n
′ d
xd K(x− x′). (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 EZ(x)Z(x′) = K(x− x′).

Review summaries:
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.

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.