Rigging the Lottery: Making All Tickets Winners

By Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, Erich Elsen. 2019

758 citations recorded by the source corpus.

Many applications require sparse neural networks due to space or inference time restrictions. There is a large body of work on training dense networks to yield sparse networks for inference, but this limits the size of the largest trainable sparse model to that of the largest trainable dense model. In this paper we introduce a method to train sparse neural networks with a fixed parameter count and a fixed computational cost throughout training, without sacrificing accuracy relative to existing dense-to-sparse training methods. Our method updates the topology of the sparse network during training by using parameter magnitudes and infrequent gradient calculations. We show that this approach requires fewer floating-point operations (FLOPs) to achieve a given level of accuracy compared to prior techniques. We demonstrate state-of-the-art sparse training results on a variety of networks and datasets, including ResNet-50, MobileNets on Imagenet-2012, and RNNs on WikiText-103. Finally, we provide some insights into why allowing the topology to change during the optimization can overcome local minima encountered when the topology remains static. Code used in our work can be found in this http URL.

Subfields: Artificial Intelligence, Economics and Econometrics, Efficiency & Compression

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 Economics and Econometrics

In Efficiency & Compression

Citations in the corpus

Train Large, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers (2020, background): “, 2018) and convolutional models for computer vision (Zhu & Gupta, 2018; Elsen et al., 2019; Evci et al., 2020; Kusupati et al., 2020).”
A Review of Sparse Expert Models in Deep Learning (2022, background): “These are a special case of sparse neural networks (Gale et al., 2019; Dettmers and Zettlemoyer, 2019; Evci et al., 2020) which are similar in that they only use a subset of parameters, but differ because they have potentially irregular sparsity patterns.”
Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints (2022, background): “More recently, the Lottery Ticket Hypothesis [12] has sparked interest in techniques that provide the storage and computation benefits of sparse models directly during training [35, 8].”
The Efficiency Misnomer (2021, background): “…to effectively use batched operations, while for unstructured sparsity, it is not possible for the corresponding low-level operations to reach the same efﬁciency as their dense counterparts on current hardware, where memory access is signiﬁcantly more expensive than compute (Gale et al., 2020).”
BASE Layers: Simplifying Training of Large, Sparse Models (2021, background): “Sparse training is a line of work where traditional architectures are trained with sparse instead of dense layers and the number of parameters allowed during training is restricted to a percentage of the dense layers (Dettmers & Zettlemoyer, 2019; Evci et al., 2020; Mostafa & Wang, 2019).”
NISPA: Neuro-Inspired Stability-Plasticity Adaptation for Continual Learning in Sparse Networks (2022, background): “Training sparse neural networks has been extensively explored (Bellec et al., 2018; Evci et al., 2020; Mocanu et al., 2018; Liu et al., 2021b; 2020; 2021a).”
The hardware lottery (2020, background): “For example, unstructured pruning (Hooker et al., 2019; Gale et al., 2019; Evci et al., 2019) and weight specific quantization (Zhen et al.”
The Lottery Ticket Hypothesis for Pre-trained BERT Networks (2020, background): “In parallel to this race for ever-larger models, an emerging subfield has explored the prospect of training smaller subnetworks in place of the full models without sacrificing performance [11–16].”
SpaceNet: Make Free Space For Continual Learning (2020, background): “In recent years, sparse training proved its success in achieving the same performance with dense neural networks for single task standard supervised/unsupervised learning, while having much faster training speed and much lower memory requirements [30, 2, 4, 5, 14, 32].”
A Survey on Deep Neural Network Pruning: Taxonomy, Comparison, Analysis, and Recommendations (2023, positive): “Byrepeatingtheprune-and-growcycleduringtraining,these methodkeepssearchingforbettersparsearchitecture,aprocess classiﬁedasdynamicsparsetrainingin[81].”
Branch-Train-Merge: Embarrassingly Parallel Training of Expert Language Models (2022, neutral): “Sparse Language Models Sparsely activated language models have been considered in a few forms (Evci et al., 2020; Mostafa and Wang, 2019; Dettmers and Zettlemoyer, 2019), but the Mixture-of-Experts (MoE) model is of particular note.”
WoodFisher: Efficient Second-Order Approximation for Neural Network Compression (2020, methodology): “[23, 24, 27, 45], which prune during regular training and can additionally allow the re-introduction of weights during training; (4) variational or regularization-based methods, e.”
Sparse Upcycling: Training Mixture-of-Experts from Dense Checkpoints (2022, methodology): “However, “dynamic pruning” (Evci et al., 2020) has also been used during training to ﬁnd sparser architectures from dense models.”
In the Wild: From ML Models to Pragmatic ML Systems (2020, background): “Pragmatic systems must measure this compute over the duration of their lifetime; not just measuring inference cost [34, 20, 24] but also update cost [10].”
Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch (2021, methodology): “…other is a one-stage scheme, which adopts the dynamic method to alternatively optimize parameters and prunes network architectures based on different criteria (Bellec et al., 2017; Mocanu et al., 2018; Mostafa & Wang, 2019; Evci et al., 2019b; Kusupati et al., 2020; Dettmers & Zettlemoyer, 2019).”
How Well Do Sparse ImageNet Models Transfer? (2021, methodology): “Additionally, we include the “The Rigged Lottery” (RigL) method [12] with Erdős-Rényi-Kernel (ERK) weight density.”