Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm

By Stefano Spigler, Mario Geiger, Matthieu Wyart. 2019

43 citations recorded by the source corpus.

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.

Subfields: Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Scaling & Learning Theory

Citations in the corpus

A Neural Scaling Law from the Dimension of the Data Manifold (2020, background): “ing can be understood as a consequence of interpolation between points on the data manifold, and so should have a similar relationship to the data manifold dimension. Recent works have made this case [SGW19]. Compute scaling exponents [KMH+20] are also not far from model-size exponents, but combine ”
Locality defeats the curse of dimensionality in convolutional teacher–student scenarios (2021, background): “Although the general modal decomposition cannot be proven rigorously in the ridgeless limit [19, 21], additional results are available when the target functions are Gaussian random fields with covariance specified by a teacher kernel: • Equation (8) can be proven rigorously [4] if teacher and studen”
Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, methodology): “In Appendix B we show how to recover the results of [37] and [53] for the power law scaling of the generalisation error in kernel ridge regression.”
Modelling the influence of data structure on learning in neural networks (2019, background): “Its dimension can nevertheless be estimated to be around D ≈ 14 based on the neighbourhoods of inputs in the data set (Grassberger & Procaccia, 1983; Costa & Hero, 2004; Levina & Bickel, 2004; Spigler et al., 2019).”
Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks (2020, methodology): “Such power law decays have been observed empirically on standard datasets (Hestness et al., 2017; Spigler et al., 2019).”