Kernel Alignment Risk Estimator: Risk Prediction from Training Data

Abstract

We study the risk (i.e. generalization error) of Kernel Ridge Regression (KRR) for a kernel $K$ with ridge $\lambda >0$ and i.i.d. observations. For this, we introduce two objects: the Signal Capture Threshold (SCT) and the Kernel Alignment Risk Estimator (KARE). The SCT ${\vartheta }_{K,\lambda }$ is a function of the data distribution: it can be used to identify the components of the data that the KRR predictor captures, and to approximate the (expected) KRR risk. This then leads to a KRR risk approximation by the KARE ${\rho }_{K,\lambda }$, an explicit function of the training data, agnostic of the true data distribution. We phrase the regression problem in a functional setting. The key results then follow from a finite-size analysis of the Stieltjes transform of general Wishart random matrices. Under a natural universality assumption (that the KRR moments depend asymptotically on the first two moments of the observations) we capture the mean and variance of the KRR predictor. We numerically investigate our findings on the Higgs and MNIST datasets for various classical kernels: the KARE gives an excellent approximation of the risk, thus supporting our universality assumption. Using the KARE, one can compare choices of Kernels and hyperparameters directly from the training set. The KARE thus provides a promising data-dependent procedure to select Kernels that generalize well.

References in corpus (9)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Enhanced Convolutional Neural Tangent Kernels
• Neural Kernels Without Tangents
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
• Combinatorial theory of permutation-invariant random matrices II: cumulants, freeness and Levy processes
• Implicit Regularization of Random Feature Models
• Large permutation invariant random matrices are asymptotically free over the diagonal

Cited by in corpus (15)

• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Learning with invariances in random features and kernel models
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Gaussian Universality of Perceptrons with Random Labels
• Learning curves for the multi-class teacher-student perceptron
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
• A Random Matrix Perspective on Mixtures of Nonlinearities for Deep Learning
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
• Learning with convolution and pooling operations in kernel methods
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Learning Curves for SGD on Structured Features
• Simplified derivations for high-dimensional convex learning problems
• Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks