Minimum complexity interpolation in random features models

Abstract

Despite their many appealing properties, kernel methods are heavily affected by the curse of dimensionality. For instance, in the case of inner product kernels in ${\mathbb{R}}^d$, the Reproducing Kernel Hilbert Space (RKHS) norm is often very large for functions that depend strongly on a small subset of directions (ridge functions). Correspondingly, such functions are difficult to learn using kernel methods. This observation has motivated the study of generalizations of kernel methods, whereby the RKHS norm -- which is equivalent to a weighted ${\ell }_2$ norm -- is replaced by a weighted functional ${\ell }_p$ norm, which we refer to as ${\mathcal{F}}_p$ norm. Unfortunately, tractability of these approaches is unclear. The kernel trick is not available and minimizing these norms requires to solve an infinite-dimensional convex problem. We study random features approximations to these norms and show that, for $p>1$, the number of random features required to approximate the original learning problem is upper bounded by a polynomial in the sample size. Hence, learning with ${\mathcal{F}}_p$ norms is tractable in these cases. We introduce a proof technique based on uniform concentration in the dual, which can be of broader interest in the study of overparametrized models. For $p=1$, our guarantees for the random features approximation break down. We prove instead that learning with the ${\mathcal{F}}_1$ norm is $\mathsf{NP}$-hard under a randomized reduction based on the problem of learning halfspaces with noise.

arXiv comment42 pages, 1 figure

References in corpus (11)

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalization Properties of Learning with Random Features
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Generalisation error in learning with random features and the hidden manifold model
• Geometry of Optimization and Implicit Regularization in Deep Learning
• When Do Neural Networks Outperform Kernel Methods?
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Universality Laws for High-Dimensional Learning with Random Features
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration