# Stochastic Separation Theorems

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2017.

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

- [Ultra-High-Resolution Detector Simulation with Intra-Event Aware GAN and Self-Supervised Relational Reasoning](https://mlsanity.com/paper/2303.08046/) (2023)
- [High-dimensional separability for one- and few-shot learning](https://mlsanity.com/paper/2106.15416/) (2021)
- [Demystification of Few-shot and One-shot Learning](https://mlsanity.com/paper/2104.12174/) (2021)
- [Relative intrinsic dimensionality is intrinsic to learning](https://mlsanity.com/paper/2311.07579/) (2023)
- [The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning](https://mlsanity.com/paper/2309.07072/) (2023)
- [Towards a mathematical understanding of learning from few examples with nonlinear feature maps](https://mlsanity.com/paper/2211.03607/) (2022)
- [Agile gesture recognition for capacitive sensing devices: adapting on-the-job](https://mlsanity.com/paper/2305.07624/) (2023)
- [Agile gesture recognition for low-power applications: customisation for generalisation](https://mlsanity.com/paper/2403.15421/) (2024)
- [Understanding the geometry of deep learning with decision boundary volume](https://mlsanity.com/paper/2603.14768/) (2026)
- [Stochastic Separability of Embedding Manifolds](https://mlsanity.com/paper/2608.22874/) (2026)

## Abstract (arXiv)

The problem of non-iterative one-shot and non-destructive correction of unavoidable mistakes arises in all Artificial Intelligence applications in the real world. Its solution requires robust separation of samples with errors from samples where the system works properly. We demonstrate that in (moderately) high dimension this separation could be achieved with probability close to one by linear discriminants. Surprisingly, separation of a new image from a very large set of known images is almost always possible even in moderately high dimensions by linear functionals, and coefficients of these functionals can be found explicitly. Based on fundamental properties of measure concentration, we show that for M<aexp(bn) random M-element sets in ℝn are linearly separable with probability p, p>1-vartheta, where 1>vartheta>0 is a given small constant. Exact values of a,b>0 depend on the probability distribution that determines how the random M-element sets are drawn, and on the constant vartheta. These em stochastic separation theorems provide a new instrument for the development, analysis, and assessment of machine learning methods and algorithms in high dimension. Theoretical statements are illustrated with numerical examples.