Finding Everything within Random Binary Networks
This provides a theoretical foundation for pruning random binary networks, which could simplify neural network initialization and training, though it is incremental as it builds on prior work on random weight networks.
The paper tackles the problem of approximating target neural networks by pruning random binary networks, proving that any target network can be approximated with arbitrary accuracy using binary weights and only a polylogarithmic increase in width and depth.
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 $\{\pm1\}$ weights that is only a polylogarithmic factor wider and deeper than the target network.