Predicting kernel regression learning curves from only raw data statistics
This work provides a theoretical framework for predicting model performance from dataset structure, which is incremental as it builds on prior kernel eigenstructure results but extends to real-world image data.
The authors tackled the problem of predicting kernel regression learning curves from raw data statistics by introducing the Hermite eigenstructure ansatz (HEA), which approximates kernel eigenvalues and eigenfunctions using empirical data covariance and target function decomposition, achieving accurate predictions on datasets like CIFAR-5m, SVHN, and ImageNet.
We study kernel regression with common rotation-invariant kernels on real datasets including CIFAR-5m, SVHN, and ImageNet. We give a theoretical framework that predicts learning curves (test risk vs. sample size) from only two measurements: the empirical data covariance matrix and an empirical polynomial decomposition of the target function $f_*$. The key new idea is an analytical approximation of a kernel's eigenvalues and eigenfunctions with respect to an anisotropic data distribution. The eigenfunctions resemble Hermite polynomials of the data, so we call this approximation the Hermite eigenstructure ansatz (HEA). We prove the HEA for Gaussian data, but we find that real image data is often "Gaussian enough" for the HEA to hold well in practice, enabling us to predict learning curves by applying prior results relating kernel eigenstructure to test risk. Extending beyond kernel regression, we empirically find that MLPs in the feature-learning regime learn Hermite polynomials in the order predicted by the HEA. Our HEA framework is a proof of concept that an end-to-end theory of learning which maps dataset structure all the way to model performance is possible for nontrivial learning algorithms on real datasets.