Generalization error of spectral algorithms

• URL: http://arxiv.org/abs/2403.11696v1
• Date: Mon, 18 Mar 2024 11:52:33 GMT
• Title: Generalization error of spectral algorithms
• Authors: Maksim Velikanov, Maxim Panov, Dmitry Yarotsky,
• Abstract summary: We consider the training of kernels with a family of $textitspectral algorithms$ specified by profile $h(lambda)$. We derive the generalization error as a functional of learning profile $h(lambda)$ for two data models.
• Score: 17.93452027304691
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\textit{spectral algorithms}$ specified by profile $h(\lambda)$, and including KRR and GD as special cases. Then, we derive the generalization error as a functional of learning profile $h(\lambda)$ 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.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay [13.803850290216257]
  We rigorously provide a full characterization of the generalization error curves of the kernel gradient descent method. Thanks to the neural tangent kernel theory, these results greatly improve our understanding of the generalization behavior of training the wide neural networks.
  arXiv  Detail & Related papers  (2024-01-03T08:00:50Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Asymptotics of Ridge Regression in Convolutional Models [26.910291664252973]
  We derive exact formulae for estimation error of ridge estimators that hold in a certain high-dimensional regime. We show the double descent phenomenon in our experiments for convolutional models and show that our theoretical results match the experiments.
  arXiv  Detail & Related papers  (2021-03-08T05:56:43Z)
• Double-descent curves in neural networks: a new perspective using Gaussian processes [9.153116600213641]
  Double-descent curves in neural networks describe the phenomenon that the generalisation error initially descends with increasing parameters, then grows after reaching an optimal number of parameters. We use techniques from random matrix theory to characterize the spectral distribution of the empirical feature covariance matrix as a width-dependent of the spectrum of the neural network Gaussian process kernel.
  arXiv  Detail & Related papers  (2021-02-14T20:31:49Z)
• Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks [17.188280334580195]
  Generalization beyond a training dataset is a main goal of machine learning. Recent observations in deep neural networks contradict conventional wisdom from classical statistics. We show that more data may impair generalization when noisy or not expressible by the kernel.
  arXiv  Detail & Related papers  (2020-06-23T17:53:11Z)
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks [87.23360438947114]
  We show that noisy gradient descent with weight decay can still exhibit a " Kernel-like" behavior. This implies that the training loss converges linearly up to a certain accuracy. We also establish a novel generalization error bound for two-layer neural networks trained by noisy gradient descent with weight decay.
  arXiv  Detail & Related papers  (2020-02-10T18:56:15Z)
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks [17.188280334580195]
  We derive analytical expressions for the generalization performance of kernel regression as a function of the number of training samples. Our expressions apply to wide neural networks due to an equivalence between training them and kernel regression with the Neural Kernel Tangent (NTK) We verify our theory with simulations on synthetic data and MNIST dataset.
  arXiv  Detail & Related papers  (2020-02-07T00:03:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.