lottery ticket hypothesis
In plain wordsThe idea that a large, randomly started neural network contains a much smaller network inside it that, trained alone from the same starting values, would learn just as well — a winning lottery ticket.
The conjecture, put forward by Jonathan Frankle and Michael Carbin, that a large randomly initialized network already contains a much sparser subnetwork, a 'winning ticket' often comprising 10–20% of the weights or fewer, which, if every other weight is deleted and it is trained alone from the very same starting values, reaches the full network's accuracy in about as many steps. Tickets are found by iterative magnitude pruningpruning, n.: Cutting away the parts of an AI model that contribute least, as a gardener trims branches, so the model becomes smaller or faster while still working nearly as well.: train the network, remove the smallest-magnitude weights, reset the survivors to their initial values, and repeat. Re-initializing a ticket randomly destroys its advantage, so the particular initial values matter. For larger networks such as ResNets on ImageNet and transformers, tickets appear reliably only when weights are 'rewound' to an early point in training rather than to initialization, a finding linked to the network becoming stable to SGD noise (linear mode connectivitymode connectivity, n.: The discovery that two separately trained versions of a network, though their settings look very different, can usually be joined by a path along which the model keeps working well.). The hypothesis recast overparameterizationoverparameterization, n.: Giving a model far more adjustable settings than it would seem to need — often more than it has training examples. Classic theory predicted this would backfire; in deep learning it usually helps. as buying many lottery draws and spurred work on pruning at initialization, but has not made large-model training cheaper, because finding a ticket requires training the dense network first.
Origin
Proposed by Jonathan Frankle and Michael Carbin of MIT in 'The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks' (arXiv March 2018), which received a best paper award at ICLR 2019; Frankle and colleagues introduced weight rewinding for larger networks in 2019–2020.
Related
- pruningpruning, n.: Cutting away the parts of an AI model that contribute least, as a gardener trims branches, so the model becomes smaller or faster while still working nearly as well.
- overparameterizationoverparameterization, n.: Giving a model far more adjustable settings than it would seem to need — often more than it has training examples. Classic theory predicted this would backfire; in deep learning it usually helps.
- weight initializationweight initialization, n.: Choosing the random starting values of a neural network's internal numbers before training. Good starting values keep signals from fading away or blowing up as they pass through many layers.
- sparsitysparsity, n.: The property of being mostly zeros or mostly switched off. AI systems exploit it by skipping the empty parts, so they need less memory and computation.
- mode connectivitymode connectivity, n.: The discovery that two separately trained versions of a network, though their settings look very different, can usually be joined by a path along which the model keeps working well.
- model compressionmodel compression, n.: The family of techniques for making AI models smaller, faster or cheaper to run while keeping almost all of their accuracy.
Sources
- Frankle, J. & Carbin, M. (2019). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. ICLR 2019. arxiv.org/abs/1803.03635
- Frankle, J., Dziugaite, G. K., Roy, D. M. & Carbin, M. (2020). Linear Mode Connectivity and the Lottery Ticket Hypothesis. ICML 2020.
Mentioned in
pruningpruning, n.: Cutting away the parts of an AI model that contribute least, as a gardener trims branches, so the model becomes smaller or faster while still working nearly as well., weight initializationweight initialization, n.: Choosing the random starting values of a neural network's internal numbers before training. Good starting values keep signals from fading away or blowing up as they pass through many layers., mode connectivitymode connectivity, n.: The discovery that two separately trained versions of a network, though their settings look very different, can usually be joined by a path along which the model keeps working well., overparameterizationoverparameterization, n.: Giving a model far more adjustable settings than it would seem to need — often more than it has training examples. Classic theory predicted this would backfire; in deep learning it usually helps.