Generalization Bounds for Sparse Random Feature Expansions

Abstract

Random feature methods have been successful in various machine learning tasks, are easy to compute, and come with theoretical accuracy bounds. They serve as an alternative approach to standard neural networks since they can represent similar function spaces without a costly training phase. However, for accuracy, random feature methods require more measurements than trainable parameters, limiting their use for data-scarce applications or problems in scientific machine learning. This paper introduces the sparse random feature expansion to obtain parsimonious random feature models. Specifically, we leverage ideas from compressive sensing to generate random feature expansions with theoretical guarantees even in the data-scarce setting. In particular, we provide generalization bounds for functions in a certain class (that is dense in a reproducing kernel Hilbert space) depending on the number of samples and the distribution of features. The generalization bounds improve with additional structural conditions, such as coordinate sparsity, compact clusters of the spectrum, or rapid spectral decay. In particular, by introducing sparse features, i.e. features with random sparse weights, we provide improved bounds for low order functions. We show that the sparse random feature expansions outperforms shallow networks in several scientific machine learning tasks.

References in corpus (16)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Active subspace methods in theory and practice: applications to kriging surfaces
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalization Properties of Learning with Random Features
• Exploiting Active Subspaces to Quantify Uncertainty in the Numerical Simulation of the HyShot II Scramjet
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Few-Shot Learning via Learning the Representation, Provably
• A near-stationary subspace for ridge approximation
• Optimal Rates for Random Fourier Features
• Approximation of high-dimensional periodic functions with Fourier-based methods
• On Kernel Derivative Approximation with Random Fourier Features
• Learning multivariate functions with low-dimensional structures using polynomial bases
• Additive function approximation in the brain

Cited by in corpus (9)

• Operator Learning Using Random Features: A Tool for Scientific Computing
• HARFE: Hard-Ridge Random Feature Expansion
• Random Feature Models for Learning Interacting Dynamical Systems
• SPADE4: Sparsity and Delay Embedding based Forecasting of Epidemics
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error
• Variance-based sensitivity of Bayesian inverse problems to the prior distribution
• Extreme learning machines for variance-based global sensitivity analysis
• Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms
• Slicing of Radial Functions: a Dimension Walk in the Fourier Space