# The Separation Capacity of Random Neural Networks

arXiv: https://arxiv.org/abs/2108.00207 · HTML: https://mlsanity.com/paper/2108.00207/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 66 references that are in the map.
- First posted on arXiv 31 Jul 2021.

## Builds on (most cited first, 30 of 31)

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1902.01384/) (2019)
- [Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?](https://mlsanity.com/paper/1504.08291/) (2015)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems](https://mlsanity.com/paper/1905.09870/) (2019)
- [Random Vector Functional Link Networks for Function Approximation on Manifolds](https://mlsanity.com/paper/2007.15776/) (2020)
- [A Corrective View of Neural Networks: Representation, Memorization and Learning](https://mlsanity.com/paper/2002.00274/) (2020)
- [The Benefits of Over-parameterization at Initialization in Deep ReLU Networks](https://mlsanity.com/paper/1901.03611/) (2019)
- [Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets](https://mlsanity.com/paper/1512.04433/) (2015)
- [Compressive classification and the rare eclipse problem](https://mlsanity.com/paper/1404.3203/) (2014)
- [Robust one-bit compressed sensing with partial circulant matrices](https://mlsanity.com/paper/1812.06719/) (2018)

## Built on by (most cited first, 14 of 14)

- [Sampling weights of deep neural networks](https://mlsanity.com/paper/2306.16830/) (2023)
- [Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes](https://mlsanity.com/paper/2410.23126/) (2024)
- [Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2307.06887/) (2023)
- [Randomly Initialized One-Layer Neural Networks Make Data Linearly Separable](https://mlsanity.com/paper/2205.11716/) (2022)
- [Memorization With Neural Nets: Going Beyond the Worst Case](https://mlsanity.com/paper/2310.00327/) (2023)
- [Upper and lower bounds for the Lipschitz constant of random neural networks](https://mlsanity.com/paper/2311.01356/) (2023)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [Linearly Separable Features in Shallow Nonlinear Networks: Width Scales Polynomially with Intrinsic Data Dimension](https://mlsanity.com/paper/2501.02364/) (2025)
- [Activation Subspaces for Out-of-Distribution Detection](https://mlsanity.com/paper/2508.21695/) (2025)
- [Separation capacity of linear reservoirs with random connectivity matrix](https://mlsanity.com/paper/2404.17429/) (2024)
- [Online Federation For Mixtures of Proprietary Agents with Black-Box Encoders](https://mlsanity.com/paper/2505.00216/) (2025)
- [Position: Pause Recycling LoRAs and Prioritize Mechanisms to Uncover Limits and Effectiveness](https://mlsanity.com/paper/2506.13479/) (2025)
- [Convex Optimization of Spiking Neural Networks with Global and Approximation Guarantees](https://mlsanity.com/paper/2605.08022/) (2026)
- [Dimension-Free Rank Lifting from Random Hyperplane Arrangements](https://mlsanity.com/paper/2609.39855/) (2026)

## Abstract (arXiv)

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 X^-, X^+ subset ℝ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 X^-, 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.