Proving the Lottery Ticket Hypothesis: Pruning is All You Need
This provides a theoretical foundation for pruning in neural networks, potentially reducing computational costs for AI practitioners, though it is incremental on prior conjectures.
The paper proves a stronger version of the lottery ticket hypothesis, showing that for bounded distributions and target networks, a sufficiently over-parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network without training.
The lottery ticket hypothesis (Frankle and Carbin, 2018), states that a randomly-initialized network contains a small subnetwork such that, when trained in isolation, can compete with the performance of the original network. We prove an even stronger hypothesis (as was also conjectured in Ramanujan et al., 2019), showing that for every bounded distribution and every target network with bounded weights, a sufficiently over-parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network, without any further training.