  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 $\mathcal{O}(1)$ neurons, where a 2-layer deterministic network was
shown to require $\Omega(e^d)$ 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.
