mlsanityData to 14 Oct 2026

Randomly Initialized One-Layer Neural Networks Make Data Linearly Separable

arXiv 2205.11716 ↗First posted 24 May 2022cs.LG math.PR stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

Recently, neural networks have demonstrated remarkable capabilities in mapping two arbitrary sets to two linearly separable sets. The prospect of achieving this with randomly initialized neural networks is particularly appealing due to the computational efficiency compared to fully trained networks. This paper contributes by establishing that, given sufficient width, a randomly initialized one-layer neural network can, with high probability, transform two sets into two linearly separable sets without any training. Moreover, we furnish precise bounds on the necessary width of the neural network for this phenomenon to occur. Our initial bound exhibits exponential dependence on the input dimension while maintaining polynomial dependence on all other parameters. In contrast, our second bound is independent of input dimension, effectively surmounting the curse of dimensionality. The main tools used in our proof heavily relies on a fusion of geometric principles and concentration of random matrices.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 22 of its 56 references that are in the map. First posted on arXiv 24 May 2022.

Builds on

22 of 56 references.

References · 22

  1. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  5. 2014Deep Learning in Neural Networks: An Overviewcited by 770
  6. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  7. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  8. 2016Generalization Properties of Learning with Random Featurescited by 164
  9. 2014Deep Learning Face Representation by Joint Identification-Verificationcited by 162
  10. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
  11. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  12. 2016Identity Matters in Deep Learningcited by 109
10 more
  1. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  2. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 78
  3. 2019Convergence of Adversarial Training in Overparametrized Neural Networkscited by 58
  4. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  5. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  6. 2020Random Vector Functional Link Networks for Function Approximation on Manifoldscited by 19
  7. 2021The Separation Capacity of Random Neural Networkscited by 14
  8. 2019The Benefits of Over-parameterization at Initialization in Deep ReLU Networkscited by 8
  9. 2015Near-Optimal Bounds for Binary Embeddings of Arbitrary Setscited by 5
  10. 2014Compressive classification and the rare eclipse problemcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 2; 2026: 2.

6 papers.

  1. 2024Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codescited by 19
  2. 2023Memorization With Neural Nets: Going Beyond the Worst Casecited by 2
  3. 2025Linearly Separable Features in Shallow Nonlinear Networks: Width Scales Polynomially with Intrinsic Data Dimensioncited by 2
  4. 2025Position: Pause Recycling LoRAs and Prioritize Mechanisms to Uncover Limits and Effectivenesscited by 0
  5. 2026Directional Linear Separability of Neural Representations: Geometry and Transformationscited by 0
  6. 2026Dimension-Free Rank Lifting from Random Hyperplane Arrangementscited by 0