Proving the Lottery Ticket Hypothesis: Pruning is All You Need

By Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, Ohad Shamir. 2020

335 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Materials Chemistry, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Materials Chemistry

In Evaluation & Benchmarks

Citations in the corpus

Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints (2022, background): “However, finding “good” sparse sub-networks at initialization remains a central challenge for these techniques [13, 33].”
Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models (2021, background): “Many insightful studies [Morcos et al., 2019, Orseau et al., 2020, Frankle et al., 2019, 2020, Malach et al., 2020, Pensia et al., 2020] are carried out to analyze these tickets, but it remains difficult to generalize to large models due to training cost.”
Parameter-Efficient Fine-Tuning for Large Models: A Comprehensive Survey (2024, methodology): “LT-SFT [3] introduces another technique to determines parameter importance inspired by the Lottery Ticket Hypothesis [46], [130], where the the subset of parameters that change the most during an initial fine-tuning stage is selected to form the mask M .”
Playing Lottery Tickets with Vision and Language (2021, background): “LTH has been shown great success in various fields [76, 57, 6], and its properties have been widely studied [50, 53, 17].”
Provable and Efficient Continual Representation Learning (2022, background): “Zhou et al. (2019); Malach et al. (2020); Pensia et al. (2020) demonstrate that there are subsets with good test performance even without any training and provide theoretical guarantees.”
A Survey on Deep Neural Network Pruning: Taxonomy, Comparison, Analysis, and Recommendations (2023, positive): “…classes: (1) proposing a stronger lottery ticket hypothesis, (2) exploring the transferability of LTH, (3) generalizing LTH to other contexts, (4) theoretical justiﬁcation, and (5) revisiting and questioning LTH. 1) Some recent works ([113], [118], [119]) prove stronger hypothesis than LTH [48].”