Introduction In machine learning, the lottery ticket hypothesis is that artificial neural networks with random weights can contain a subnetwork which (entirely by chance) can be tuned to a similar performance as tuning the whole network., published as a conference paper at ICLR 2019.
LTH was traditionally viewed as only a post-processing step, and that pruned networks cannot be trained from scratch. Recently, a new idea emerged that not only takes pruning one step further but also changes our understanding of the most fundamental aspects of Neural network training. It is the Lottery Ticket Hypothesis (Frankle, Carbin, 2019).
By using pruned networks, we can create what we call winning tickets. By taking the pruned network and changing the non-zero weights back to the original random initializations that were made at the start of the training process, resulting in the network called the winning ticket. The winning ticket can then be trained from scratch and achieve the same or better performance as the original network. The only condition is that, after pruning, the remaining weights are changed back to their original initialization. The combination of the pruning mask and lucky initial weights is essential to the success of a winning ticket. The winning tickets we find have won the initialization lottery: their connections have initial weights that make training particularly effective.
Lottery ticket hypothesis The original algorithm is:
Randomily initialize dense network: weights . Train for iterations → weights . Magnitude pruning: build a bitmask by setting to 0 the lowest-magnitude weights in each layer (one-shot), or repeat train → prune across rounds to reach higher sparsity (iterative). Reset surviving weights to initialization: use as the starting point. Here is elementwise multiplication. Train the masked network with the same optimizer, schedule, and data. Declare "winning ticket" if it achieves comparable test accuracy in iterations.
The term derived from considering the probability of a tunable subnetwork as the equivalent to a winning lottery ticket; the chance of any given ticket winning is tiny, but if you buy enough of them you are certain to win, and the number of possible subnetworks increases exponentially as the power set of the set of connections, making the number of possible subnetworks astronomical for any reasonably large network.
Such networks are a priori difficult to find, since before training, one does not know which of the exponentially many subnetwork would be "lottery tickets". However, after training, these lottery tickets can be discovered by the pruning algorithm.
It was found that during the original training of the initial dense network, the weights that would end up in the winning ticket change a lot, but the other weights change little.
It was found that if instead of , they re-sampled a different random initialization , and used instead, the trained would perform much worse. This indicates that what makes a ticket winning is both its connection graph and the precise initial weights of the connections.
Evidence Following the initial experiments on small convolutional networks, the hypothesis was tested across larger architectures and different learning tasks. On deeper models such as ResNet-50 on ImageNet, subnetworks reset strictly to their initial weights () did not consistently achieve the accuracy of the unpruned network. Frankle et al. (2019) found that this was caused by sensitivity to gradient noise during early stochastic gradient descent, proposing instead that weights be "rewound" to a checkpoint from early in training () to stabilize subsequent training.
Winning tickets have also been identified in natural language processing and reinforcement learning. In pre-trained transformer models like BERT, researchers found that subnetworks pruned to between 40% and 70% sparsity matched full fine-tuning performance across standard GLUE benchmark tasks; some of these tickets transferred to other downstream tasks without re-pruning. Similar sparse, trainable subnetworks have been observed in policy gradient and Q-learning networks evaluated on continuous control benchmarks.
The relative importance of initial weight values compared to network architecture remains debated. Liu et al. (2019) demonstrated that for structured (channel-level) pruning, retraining the pruned architecture from a new random initialization often yields accuracy comparable to rewinding the original weights, suggesting that in some pruning regimes, architecture topology dominates the choice of initial weights.
Subsequent work Malach et al. proved a stronger version of the hypothesis, namely that a sufficiently overparameterized untuned network will typically contain a subnetwork that is already an approximation to the given goal, even before tuning. published in Proceedings of the 37th International Conference on Machine Learning, Online, PMLR 119, 2020 A similar result has been proven for the special case of convolutional neural networks.
See also Grokking (machine learning) Pruning (artificial neural network)
References