Lottery ticket hypothesis

On this page 7

The lottery ticket hypothesis is the proposition that a randomly initialized dense neural network contains a sparse subnetwork, called a winning ticket, which, when trained in isolation from its original initial weights, reaches test accuracy comparable to the full network in a similar number of training iterations. It was formulated by Jonathan Frankle and Michael Carbin in 2018 and has become a central reference point for research on neural network pruning and model sparsity.

In edge AI, the hypothesis matters because it suggests that much of a trained model is redundant from the start. If a network at 10 to 20 percent of its original size can learn just as well, the path to models small enough for phones, microcontrollers and embedded devices becomes a question of finding the right subnetwork, not only of compressing a finished model.

How winning tickets are found

Winning tickets are found with iterative magnitude pruning, usually abbreviated IMP. The procedure trains the dense network, removes the weights with the smallest absolute values, resets the surviving weights to their original initial values and trains again. Repeating this cycle produces progressively sparser subnetworks while the original initialization is preserved.

  1. Initialize the dense network randomly and store the initial weights.
  2. Train the network to convergence or for a fixed budget.
  3. Prune a fixed fraction of the remaining weights, typically about 20 percent per round, by magnitude.
  4. Reset the surviving weights to their stored values, which is called resetting or rewinding.
  5. Repeat training and pruning until the target sparsity is reached or accuracy starts to fall.

The decisive control experiment is random reinitialization. When the same sparse structure is kept but its weights receive new random values, accuracy typically drops sharply. This shows that a winning ticket is defined by the combination of mask and initial values, not by the sparse architecture alone.

Key findings and variants of the hypothesis

The original experiments used small fully connected and convolutional networks on MNIST and CIFAR-10, where winning tickets were found at roughly 10 to 20 percent of the original parameters, sometimes training faster and generalizing slightly better than the dense model. Later work refined, extended and challenged these results, producing several named variants.

VariantCore claimPractical meaning
Original hypothesisTickets train well from exact initial weightsWorks on small networks
Weight rewindingReset to an early training iteration, not iteration zeroNeeded for deep networks such as ResNet-50
Learning rate rewindingKeep final weights, replay the learning rate scheduleSimpler retraining with strong accuracy
Strong hypothesisUntrained networks contain accurate subnetworksPruning alone can yield a working model
Early-bird ticketsMasks stabilize early in trainingCuts the cost of finding tickets
Ticket transferTickets found on one dataset help on othersReuse of masks across related tasks
Main variants and extensions of the lottery ticket hypothesis

The shift to weight rewinding was the most important correction. For large networks on ImageNet, resetting to iteration zero did not produce winning tickets, but rewinding to a point early in training, often after a small percentage of total iterations, did. This finding is linked to linear mode connectivity, the property that training runs from the same rewound state converge to solutions connected by a low-loss linear path.

Lottery tickets compared with other compression methods

The lottery ticket hypothesis is a statement about trainability, while most edge compression methods are engineering techniques applied to finished models. Comparing them clarifies what the hypothesis does and does not offer to engineers building on-device models.

ApproachWhen it is appliedMain costHardware speedup
Iterative magnitude pruning with rewindingAcross repeated training runsMany full training cyclesOnly with sparse kernels
One-shot magnitude pruningAfter training, then fine-tuningOne fine-tuning phaseOnly with sparse kernels
Structured pruningDuring or after trainingSome accuracy lossDirect on most hardware
Pruning at initializationBefore training, for example SNIP or SynFlowWeaker at high sparsityOnly with sparse kernels
Post-training quantizationAfter trainingCalibration dataDirect with INT8 support
Knowledge distillationTraining a smaller studentExtra training runDirect, smaller dense model
Lottery ticket pruning compared with related compression approaches

Lottery tickets produce unstructured sparsity: individual weights are removed anywhere in the network. Standard CPUs, GPUs and neural processing units execute dense matrix operations, so an unstructured sparse model usually saves storage but not latency unless a runtime provides efficient sparse kernels or the sparsity follows a supported pattern such as 2:4 sparsity.

Practical relevance for edge AI

For on-device deployment, the hypothesis is valuable mainly as evidence that high sparsity is reachable without large accuracy loss, and as a source of training recipes. Engineers rarely run full lottery ticket searches in production, but they routinely use its ideas: iterative pruning schedules, rewinding and retraining from early checkpoints.

The table below summarizes typical decisions when lottery ticket methods are considered for a constrained device. The sparsity levels are indicative and depend strongly on the architecture, dataset and acceptable accuracy loss.

SituationRecommended choiceReason
Flash storage is the bottleneckIMP with rewinding, compressed sparse storageSparsity of 80 to 90 percent shrinks files
Latency is the bottleneckStructured pruning plus quantizationDense kernels run fewer operations
Training budget is smallEarly-bird tickets or one-shot pruningAvoids many full retraining rounds
Runtime supports sparse kernelsUnstructured tickets at high sparsitySparsity turns into real speedup
Many related tasksTransfer one ticket across tasksSearch cost is paid once
Decision guide for lottery ticket methods on edge targets

Lottery ticket pruning combines well with post-training quantization or quantization-aware training. A model pruned to high sparsity and stored in INT8 can be an order of magnitude smaller than its dense 32-bit original, which matters for microcontrollers with only hundreds of kilobytes of memory.

Limitations and open questions

The biggest practical limitation is the computational cost of finding a ticket. Iterative magnitude pruning needs ten or more complete training runs to reach high sparsity, so the procedure is far more expensive than training the dense model once. This makes it a research tool rather than a routine step for large models.

  • Scale dependence: the original reset-to-initialization result does not hold for deep networks without rewinding.
  • No speedup by default: unstructured sparsity rarely reduces latency on common edge hardware.
  • Disputed explanations: why winning tickets exist, and whether they reflect special initial values or optimization dynamics, is still debated.
  • Mixed evidence for transformers: tickets have been found in language models, but results depend on task and pruning method.
  • A common misconception is that the hypothesis proves dense training is wasteful; tickets are identified only after the dense network has been trained.

In everyday language

Imagine buying a huge bundle of lottery tickets. Most of them lose, but one small group of tickets wins. The lottery ticket hypothesis says a large neural network is similar: inside it hides a much smaller network that can learn the same task just as well.

The catch is that you only discover which tickets win after the draw. Researchers first train the big network, see which connections mattered, and then keep only that small winning part. For phones and small devices, this is good news, because it shows that much smaller AI models can work almost as well as the large ones.

Seen in the real world

An embedded engineering team builds a keyword spotting model for a battery-powered smart sensor with a small microcontroller. Their dense convolutional network reaches good accuracy but does not fit the available flash memory alongside the firmware and audio pipeline.

The team applies iterative magnitude pruning, removing 20 percent of the remaining weights per round and rewinding to an early training checkpoint each time. After eight rounds, about 83 percent of the weights are gone, and the accuracy on their validation set stays within about half a percentage point of the dense model. They then quantize the remaining weights to INT8 and store them in a compressed sparse format.

The result is a model several times smaller that fits the device with room for an update slot. Because their runtime has no sparse kernels, inference speed barely changes, so the team adds a small amount of structured channel pruning in the next release to reduce latency as well.