# Coin Flipping Neural Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 46 references that are in the map.
- First posted on arXiv 18 Jun 2022.

## Builds on (most cited first, 26 of 26)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Conditional Generative Adversarial Nets](https://mlsanity.com/paper/1411.1784/) (2014)
- [Alias-Free Generative Adversarial Networks](https://mlsanity.com/paper/2106.12423/) (2021)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets](https://mlsanity.com/paper/1606.03657/) (2016)
- [Tutorial on Variational Autoencoders](https://mlsanity.com/paper/1606.05908/) (2016)
- [Parallel WaveGAN: A fast waveform generation model based on generative adversarial networks with multi-resolution spectrogram](https://mlsanity.com/paper/1910.11480/) (2019)
- [Hands-on Bayesian Neural Networks -- a Tutorial for Deep Learning Users](https://mlsanity.com/paper/2007.06823/) (2020)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Deep Learning in Spiking Neural Networks](https://mlsanity.com/paper/1804.08150/) (2018)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [A Tutorial on Learning With Bayesian Networks](https://mlsanity.com/paper/2002.00269/) (2020)
- [Hypermodels for Exploration](https://mlsanity.com/paper/2006.07464/) (2020)
- [Deep Randomized Neural Networks](https://mlsanity.com/paper/2002.12287/) (2020)
- [Stochastic Deep Networks](https://mlsanity.com/paper/1811.07429/) (2018)
- [Modeling Documents with Deep Boltzmann Machines](https://mlsanity.com/paper/1309.6865/) (2013)
- [Deep Neural Network Ensembles](https://mlsanity.com/paper/1904.05488/) (2019)
- [Stochastic Feedforward Neural Networks: Universal Approximation](https://mlsanity.com/paper/1910.09763/) (2019)
- [Boltzmann machines and energy-based models](https://mlsanity.com/paper/1708.06008/) (2017)
- [On the Universal Approximation Property and Equivalence of Stochastic Computing-based Neural Networks and Binary Neural Networks](https://mlsanity.com/paper/1803.05391/) (2018)
- [Realization of Stochastic Neural Networks and Its Potential Applications](https://mlsanity.com/paper/2011.06427/) (2020)

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

- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Revisiting Non-separable Binary Classification and its Applications in Anomaly Detection](https://mlsanity.com/paper/2312.01541/) (2023)
- [Probabilistic Invariant Learning with Randomized Linear Classifiers](https://mlsanity.com/paper/2308.04412/) (2023)

## Abstract (arXiv)

We show that neural networks with access to randomness can outperform deterministic networks by using amplification. We call such networks Coin-Flipping Neural Networks, or CFNNs. We show that a CFNN can approximate the indicator of a d-dimensional ball to arbitrary accuracy with only 2 layers and O(1) neurons, where a 2-layer deterministic network was shown to require Omega(ed) neurons, an exponential improvement (arXiv:1610.09887). We prove a highly non-trivial result, that for almost any classification problem, there exists a trivially simple network that solves it given a sufficiently powerful generator for the network's weights. Combining these results we conjecture that for most classification problems, there is a CFNN which solves them with higher accuracy or fewer neurons than any deterministic network. Finally, we verify our proofs experimentally using novel CFNN architectures on CIFAR10 and CIFAR100, reaching an improvement of 9.25% from the baseline.