On the Approximation Properties of Random ReLU Features

Abstract

We study the approximation properties of random ReLU features through their reproducing kernel Hilbert space (RKHS). We first prove a universality theorem for the RKHS induced by random features whose feature maps are of the form of nodes in neural networks. The universality result implies that the random ReLU features method is a universally consistent learning algorithm. We prove that despite the universality of the RKHS induced by the random ReLU features, composition of functions in it generates substantially more complicated functions that are harder to approximate than those functions simply in the RKHS. We also prove that such composite functions can be efficiently approximated by multi-layer ReLU networks with bounded weights. This depth separation result shows that the random ReLU features models suffer from the same weakness as that of shallow models. We show in experiments that the performance of random ReLU features is comparable to that of random Fourier features and, in general, has a lower computational cost. We also demonstrate that when the target function is the composite function as described in the depth separation theorem, 3-layer neural networks indeed outperform both random ReLU features and 2-layer neural networks.

References in corpus (3)

• Generalization Properties of Learning with Random Features
• On the ability of neural nets to express distributions
• Learning with SGD and Random Features

Cited by in corpus (13)

• The Random Feature Model for Input-Output Maps between Banach Spaces
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• A closer look at the approximation capabilities of neural networks
• Generalization and Memorization: The Bias Potential Model
• Approximation power of random neural networks
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• A Mathematical Framework for Learning Probability Distributions
• On the Approximation Power of Two-Layer Networks of Random ReLUs
• MRCpy: A Library for Minimax Risk Classifiers
• The Separation Capacity of Random Neural Networks
• Good Classifiers are Abundant in the Interpolating Regime
• Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamics