The Separation Capacity of Random Neural Networks
Preprint
Abstract
Neural networks with random weights appear in a variety of machine learning applications, most prominently as the initialization of many deep learning algorithms and as a computationally cheap alternative to fully learned neural networks. In the present article, we enhance the theoretical understanding of random neural networks by addressing the following data separation problem: under what conditions can a random neural network make two classes $\mathcal{X}^-, \mathcal{X}^+ \subset \mathbb{R}^d$ (with positive distance) linearly separable? We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. Crucially, the number of required neurons is explicitly linked to geometric properties of the underlying sets $\mathcal{X}^-, \mathcal{X}^+$ and their mutual arrangement. This instance-specific viewpoint allows us to overcome the usual curse of dimensionality (exponential width of the layers) in non-pathological situations where the data carries low-complexity structure. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity (based on a localized version of Gaussian mean width), which leads to sound and informative separation guarantees. We connect our result with related lines of work on approximation, memorization, and generalization.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and BeyondIEEE Transactions on Pattern Analysis and Machine Intelligence, 2021
- Quantized Compressed Sensing by Rectified Linear UnitsIEEE Transactions on Information Theory, 2021
- Quantized compressive sensing with RIP matrices: the benefit of ditheringInformation and Inference: A Journal of the IMA, 2019
- A mean field view of the landscape of two-layer neural networksProceedings of the National Academy of Sciences, 2018
- Time for dithering: fast and quantized random embeddings via the restricted isometry propertyInformation and Inference: A Journal of the IMA, 2017
- Upper bounds on product and multiplier empirical processesStochastic Processes and their Applications, 2016
- Dimension Reduction by Random Hyperplane TessellationsDiscrete & Computational Geometry, 2013
- Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse VectorsIEEE Transactions on Information Theory, 2013
- The Convex Geometry of Linear Inverse ProblemsFoundations of Computational Mathematics, 2012
- Extreme learning machine: Theory and applicationsNeurocomputing, 2006