How isotropic kernels perform on simple invariants

Abstract

We investigate how the training curve of isotropic kernel methods depends on the symmetry of the task to be learned, in several settings. (i) We consider a regression task, where the target function is a Gaussian random field that depends only on $d_{\parallel }$ variables, fewer than the input dimension $d$. We compute the expected test error $\epsilon$ that follows $\epsilon \sim p^{-\beta }$ where $p$ is the size of the training set. We find that $\beta \sim 1/d$ independently of $d_{\parallel }$, supporting previous findings that the presence of invariants does not resolve the curse of dimensionality for kernel regression. (ii) Next we consider support-vector binary classification and introduce the stripe model where the data label depends on a single coordinate $y(\underline{x})=y(x_1)$, corresponding to parallel decision boundaries separating labels of different signs, and consider that there is no margin at these interfaces. We argue and confirm numerically that for large bandwidth, $\beta =\frac{d-1+\xi }{3d-3+\xi }$, where $\xi \in (0,2)$ is the exponent characterizing the singularity of the kernel at the origin. This estimation improves classical bounds obtainable from Rademacher complexity. In this setting there is no curse of dimensionality since $\beta \to 1/3$ as $d\to \infty$. (iii) We confirm these findings for the spherical model for which $y(\underline{x})=y(|\underline{x}|)$. (iv) In the stripe model, we show that if the data are compressed along their invariants by some factor $\lambda$ (an operation believed to take place in deep networks), the test error is reduced by a factor ${\lambda }^{-\frac{2(d-1)}{3d-3+\xi }}$.

References in corpus (20)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Opening the Black Box of Deep Neural Networks via Information
• Estimating the intrinsic dimension of datasets by a minimal neighborhood information
• On Exact Computation with an Infinitely Wide Neural Net
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Scaling description of generalization with number of parameters in deep learning
• Statistical Mechanics of Support Vector Networks
• Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Generalisation error in learning with random features and the hidden manifold model
• Geometry of Optimization and Implicit Regularization in Deep Learning
• On Fourier transforms of radial functions and distributions
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Jamming in multilayer supervised learning models
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
• Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model
• Minnorm training: an algorithm for training over-parameterized deep neural networks