Lottery Ticket Hypothesis

A winning ticket is the core discovery of the hypothesis: a sparse subnetwork found within a larger, randomly initialized model. When this subnetwork is isolated—meaning all other weights are pruned and set to zero—and then re-initialized to its original starting values and trained, it can achieve test accuracy comparable to the original dense network, often in fewer training iterations. This suggests the initial network's success depends on a fortunate, trainable initialization within a specific sparse architecture.

The primary algorithm used to discover winning tickets. It is an iterative process:

• Train a dense network to completion or near-completion.
• Prune a small percentage (e.g., 20%) of the weights with the smallest magnitude.
• Reset the remaining weights to their original initial values from the start of training (this 'rewinding' is critical).
• Repeat the train-prune-reset cycle until the desired sparsity level is reached. The final sparse, rewound network is the hypothesized winning ticket.

A crucial, non-intuitive component of the original hypothesis. After each pruning step, the network's remaining weights are not fine-tuned from their current trained values. Instead, they are 'rewound' to the values they held at an early training iteration (e.g., iteration 0 or a few epochs in). This resets the optimization state. Training the rewound subnetwork from this point consistently finds a solution that generalizes as well as the original network, which training from a random re-initialization or from the final trained values often does not.

Winning tickets can be categorized by their sparsity pattern:

• Unstructured Tickets: The classic form, where individual weights are pruned irrespective of layer structure. This creates highly sparse, irregular networks that are theoretically efficient but require specialized software/hardware (e.g., sparse matrix libraries) for actual speedup.
• Structured Tickets: Later research found winning tickets can also exist at a coarser granularity, such as pruned convolutional filters or attention heads. These structured subnetworks are immediately executable on standard hardware, making them more practical for deployment, though they may be harder to find.

An optimization on the original hypothesis. Research found that winning ticket structures can be identified very early in training—often within the first few epochs—rather than after training the dense network to convergence. This Early-Bird (EB) Ticket phenomenon drastically reduces the computational cost of the ticket-finding process. The EB signal is detected by monitoring when the sparsity mask (the pattern of pruned weights) stabilizes across training iterations.

The hypothesis challenges traditional views on network initialization and capacity:

• Pruning as Discovery: It reframes pruning not just as compression, but as a search algorithm for optimal sparse architectures hidden at initialization.
• Initialization is Critical: The success of a winning ticket is tied to its specific initial values, suggesting that lottery ticket initialization could be a powerful technique for training sparse networks from scratch.
• The Role of Overparameterization: It provides a compelling explanation for why large, overparameterized models train so well: they contain many potential winning tickets, increasing the probability of the optimizer finding one.

Iterative Magnitude Pruning (IMP) is the foundational algorithm used to discover winning tickets. It operates in a repeating cycle:

• Train a dense network to completion.
• Prune a fixed percentage (e.g., 20%) of the smallest-magnitude weights.
• Reset the remaining weights to their original initial values (rewinding).
• Retrain the pruned subnetwork from this rewound state. This iterative process of pruning and rewinding is what empirically validates the hypothesis by showing the sparse subnetwork can be trained to match the original network's performance.

Pruning at Initialization (PaI) is a related but distinct paradigm that seeks to identify and remove unimportant weights before any training occurs. Unlike the Lottery Ticket Hypothesis, which requires training to find a mask, PaI methods use metrics like:

• SNIP (Single-shot Network Pruning): Scores connections based on their effect on the loss gradient.
• GraSP (Gradient Signal Preservation): Prunes to preserve the gradient flow.
• SynFlow: Uses a synaptic saliency score that is invariant to scaling. These methods aim for efficiency but often find subnetworks that require more training iterations to match the performance of tickets found via IMP.

Weight rewinding is the critical step in IMP where, after pruning, the remaining unpruned weights are not fine-tuned from their final trained values. Instead, they are reset to an earlier checkpoint from the initial training run (e.g., iteration 1k). This is distinct from fine-tuning. The theory suggests rewinding resets the optimization trajectory, allowing the sparse architecture to learn effectively from a point where the winning ticket's structure is still compatible with the optimizer's state. The rewinding point is a key hyperparameter.

The original Lottery Ticket Hypothesis focused on unstructured pruning, which removes individual weights, creating irregular sparsity. This is contrasted with structured pruning, which removes entire structural units (filters, channels, attention heads).

• Unstructured Tickets: Yield highly sparse models but require specialized software/hardware (e.g., sparse kernels) for speedup.
• Structured Tickets: Produce smaller, dense models that run efficiently on standard hardware but may be harder to find, as removing entire structures is a more aggressive operation. Research explores finding "structured winning tickets."

Stability Training is a technique inspired by the hypothesis that makes networks more amenable to identifying winning tickets. It involves adding a regularization term during initial training that encourages the final trained weights to remain close to their initial values. This process creates a dense network whose optimization landscape is smoother and where the important subnetworks (winning tickets) are more clearly defined and stable, often leading to tickets that are easier to find and that generalize better.

A Supermask is a binary mask applied to an untrained, randomly initialized network that, when applied, yields a subnetwork with non-trivial accuracy without any weight training. This concept, explored in "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks," shows that the architecture (the connectivity pattern) itself holds significant inductive bias. The existence of supermasks supports the idea that initialization is not purely random noise but contains useful computational subgraphs that can be selected via a clever mask.