# Finding Everything within Random Binary Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 39 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [AMC: AutoML for Model Compression and Acceleration on Mobile Devices](https://mlsanity.com/paper/1802.03494/) (2018)
- [A Survey of Model Compression and Acceleration for Deep Neural Networks](https://mlsanity.com/paper/1710.09282/) (2017)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Quantized Convolutional Neural Networks for Mobile Devices](https://mlsanity.com/paper/1512.06473/) (2015)
- [Trained Ternary Quantization](https://mlsanity.com/paper/1612.01064/) (2016)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Pruning from Scratch](https://mlsanity.com/paper/1909.12579/) (2019)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network](https://mlsanity.com/paper/2103.09377/) (2021)
- [The universal approximation power of finite-width deep ReLU networks](https://mlsanity.com/paper/1806.01528/) (2018)

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

- [Rare Gems: Finding Lottery Tickets at Initialization](https://mlsanity.com/paper/2202.12002/) (2022)
- [The Augmented Image Prior: Distilling 1000 Classes by Extrapolating from a Single Image](https://mlsanity.com/paper/2112.00725/) (2021)
- [Pruning Before Training May Improve Generalization, Provably](https://mlsanity.com/paper/2301.00335/) (2023)
- ["Understanding Robustness Lottery": A Geometric Visual Comparative Analysis of Neural Network Pruning Approaches](https://mlsanity.com/paper/2206.07918/) (2022)

## Abstract (arXiv)

A recent work by Ramanujan et al. (2020) provides significant empirical evidence that sufficiently overparameterized, random neural networks contain untrained subnetworks that achieve state-of-the-art accuracy on several predictive tasks. A follow-up line of theoretical work provides justification of these findings by proving that slightly overparameterized neural networks, with commonly used continuous-valued random initializations can indeed be pruned to approximate any target network. In this work, we show that the amplitude of those random weights does not even matter. We prove that any target network can be approximated up to arbitrary accuracy by simply pruning a random network of binary ±1 weights that is only a polylogarithmic factor wider and deeper than the target network.