Computational Mathematics Colloquium | Generalization Bounds for Sparse Random Feature Expansions

Zoom: please contact compmath@uwaterloo.ca for the meeting link

Speaker

Giang Tran| Department of Applied Mathematics, University of Waterloo 

Title

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. In this work, we propose the sparse random feature expansion method, which enhances the compressive sensing approach to allow for more flexible functional relationships between inputs and a more complex feature space. We provide generalization bounds on the approximation error for functions in a reproducing kernel Hilbert space depending on the number of samples and the distribution of features. The error bounds improve with additional structural conditions, such as coordinate sparsity, compact clusters of the spectrum, or rapid spectral decay.  We show that the sparse random feature expansion method outperforms shallow networks for well-structured functions and applications to scientific machine learning tasks including function approximation and signal decomposition.