Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm

By Stefano Spigler, Mario Geiger, Matthieu Wyart. 2020

97 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 −β where n is the number of training examples and β is 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, for both 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 study 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 smoothness and dimension of the training data. We confirm numerically that these predictions hold when the training points are sampled at random on a hypersphere. Overall, the test error is found to be controlled by the magnitude of the projection of the true function on the kernel eigenvectors whose rank is larger than n. Using this idea we predict the exponent β from real data by performing kernel PCA, leading to β ≈ 0.36 for MNIST and β ≈ 0.07 for CIFAR10, in good agreement with observations. We argue that these rather large exponents are possible due to the small effective dimension of the data.

Subfields: Artificial Intelligence

How researchers see this paper

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

In Artificial Intelligence

Citations in the corpus

Learning curves for continual learning in neural networks: Self-knowledge transfer and forgetting (2021, background): “It sometimes provides us with novel insight into what the worst-case evaluation has not captured (Abbaras et al., 2020; Spigler et al., 2020).”
Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks (2020, background): “Indeed, a recent study suggested that structure in data allows kernel methods to out-perform pessimistic generalization expectations based on the high ambient dimension 65 .”