Generalization error of spectral algorithms

The asymptotically precise estimation of the generalization of kernel methods has recently received attention due to the parallels between neural networks and their associated kernels. However, prior works derive such estimates for training by kernel ridge regression (KRR), whereas neural networks are typically trained with gradient descent (GD). In the present work, we consider the training of kernels with a family of spectral algorithms specified by profile h(λ), and including KRR and GD as special cases. Then, we derive the generalization error as a functional of learning profile h(λ) for two data models: high-dimensional Gaussian and low-dimensional translation-invariant model. Under power-law assumptions on the spectrum of the kernel and target, we use our framework to (i) give full loss asymptotics for both noisy and noiseless observations (ii) show that the loss localizes on certain spectral scales, giving a new perspective on the KRR saturation phenomenon (iii) conjecture, and demonstrate for the considered data models, the universality of the loss w.r.t. non-spectral details of the problem, but only in case of noisy observation. Generalization error. We evaluate the estimator f (x) with its squared prediction error | f (x)f * (x)| 2 , averaged over inputs x drawn from a population density p(x), and then all the randomness in training dataset D N : where ε = (ε 1 , . . . , ε N ) ∼ N (0, I), ∥f ∥ 2 ≡ ⟨f, f ⟩, and angle brackets denote the scalar product ⟨f, g⟩ ≡ f (x)g(x)p(x)dx. Population spectrum. Central to our approach is the connection between generalization error L f and spectral distributions λ l , c l of the problem, defined by Mercer theorem as Here, λ l are the kernel eigenvalues, c l are the target function coefficients, and ϕ l (x) are the eigenfeatures of the kernel. In the most interesting scenarios, the number P of features ϕ l is infinite, and the respective eigenvalues λ l → 0 as l → ∞. In this work, we aim at two levels of results w.r.t. the population spectrum λ l , c l . First, we want to obtain a characterization of L f for a general λ l , c l , similar to what is done in the classic result (1). Second, we will assume the power-laws (2) to obtain a more detailed description of the generalization error L f . An important object is the empirical kernel matrix K ∈ R N ×N composed of evaluation of the kernel on training points (K) ij = K(x i , x j ). Let us additionally denote by y = f * + ε ∈ R N the observation vector with components (y) i = f * (x i ) + ε i ; by Λ ∈ R P ×P the diagonal matrix with (Λ) ll = λ l ; and by Φ ∈ R P ×N the matrix of kernel features evaluated at training points, Φ li = ϕ l (x i ). Then, spectral decomposition (4) allows to write empirical kernel matrix as Data models. A standard approach to analyzing the generalization error consists in considering general families of kernels K(x, x ′ ) and targets f * (x), typically defined by regularity assumptions, and deriving upper and lower generalization bounds (e.g., see (Caponnetto & De Vito, 2007) ). We adopt a different approach that allows us to go beyond just the bounds and describe generalization error L f with more quantitative detail. To this end, we consider two particular models, Circle and Wishart, that represent extreme low-and high-dimensional cases of the kernel learning setting.