Lottery Ticket Hypothesis

A winning ticket is a sparse subnetwork, identified within a larger, randomly-initialized network, that—when trained in isolation from the same initial weights—can match the test accuracy of the original dense network. The core finding is that these subnetworks exist at initialization, before any training occurs on the dense network.

• Key Property: The subnetwork must be trained from the original initialization of the weights that survived pruning. Rewinding the weights to this point is critical for the ticket to 'win'.
• Example: In the original 2019 paper, researchers found winning tickets in fully-connected networks on MNIST and convolutional networks on CIFAR10 that could be pruned to 10-20% of their original size and still achieve original performance.

Iterative Magnitude Pruning is the primary algorithm used to discover winning tickets. It operates through a repeated cycle of training, pruning the smallest-magnitude weights, and resetting the remaining weights to their values from an earlier point in training (the rewind point).

• Process: 1) Train the dense network for j iterations. 2) Prune a percentage of lowest-magnitude weights. 3) Reset the unpruned weights to their values from iteration j. 4) Repeat steps 1-3 until target sparsity is reached.
• Rewind Point: Critical to the hypothesis. Resetting to early training (often iteration 0 for simple tasks, or a later 'late rewinding' point for complex ones) allows the sparse architecture to be effectively trained from a favorable starting point.

A key mechanism enabling winning tickets is that large, over-parameterized networks provide a rich substrate of possible subnetworks. The hypothesis suggests these networks are easier to train because stochastic gradient descent (SGD) effectively searches through this combinatorial space of subnetworks to find a trainable one.

• Stability: Winning tickets are stable; small perturbations to their initial weights often prevent them from achieving high performance. This indicates the specific initial configuration is crucial.
• Lottery Ticket Principle: Dense networks are easier to train because they contain many potential winning tickets. The role of training is to amplify the signal within one of these lucky subnetworks while suppressing noise in the rest.

The pruning mask is a binary matrix with the same dimensions as the network's weight tensors, where a value of 1 indicates the weight is part of the winning ticket subnetwork and 0 indicates it is pruned. This mask defines the sparse architecture.

• Fixed Connectivity: Once identified, the mask is fixed. Training only updates the weights where the mask is 1; pruned connections remain at zero permanently.
• Transferability: A fascinating finding is that winning ticket masks found on one task can sometimes be transferred to a different, but related, task and still outperform random sparse masks, suggesting they encode generally useful inductive biases.

Subsequent research refined the original hypothesis, showing that for modern, large-scale networks (e.g., ResNets on ImageNet), winning tickets must be rewound to a point later in training (late rewinding), not iteration 0. This connects to the concept of linear mode connectivity.

• Late Rewinding: Resetting to weights after some period of training (e.g., several epochs) is necessary for tickets to be found in deeper networks. This suggests the early phase of training finds a loss landscape basin conducive to sparse training.
• Linear Mode Connectivity: Two models are linearly mode connected if a linear interpolation between their parameters maintains low loss. Winning tickets and the dense network are often linearly mode connected from the rewind point, explaining why training the sparse network succeeds.

The hypothesis has profound implications for model compression and efficient training. It suggests we may not need to train large, dense models fully, but could instead identify and train sparse subnetworks from the start.

• Pruning at Initialization: Spurred research into algorithms like SNIP and GraSP that score and prune weights before any training, aiming to find a winning ticket a priori.
• Efficient Training Pipelines: The goal is to reduce the massive computational cost of training giant models by only training the small, performant subnetwork. This is a core motivation behind research into sparse training and dynamic sparsity.
• Hardware-Software Co-design: Winning tickets often create unstructured sparsity, which is challenging for hardware acceleration. This has driven work on finding structured winning tickets (pruning entire filters/channels) that align with hardware capabilities.

A core algorithm for discovering winning tickets. It involves repeated cycles of:

• Pruning: Removing a percentage of the smallest-magnitude weights.
• Rewinding: Resetting the remaining weights to their original initial values (a key distinction from standard fine-tuning).
• Retraining: Training the sparse subnetwork from this rewound state. This process is repeated until a target sparsity is reached, empirically isolating high-performing subnetworks that validate the hypothesis.

A pruning paradigm that removes entire structural components (e.g., filters, channels, attention heads) rather than individual weights. Unlike the unstructured sparsity found in a classic 'winning ticket,' structured pruning produces hardware-friendly sparsity patterns that leverage efficient matrix multiplication and kernel execution on GPUs and NPUs. Schedules for structured pruning must account for layer sensitivity to maintain accuracy.

A predefined strategy dictating the timing, rate, and criteria for removing parameters. For lottery ticket discovery, schedules are critical. Key schedule types include:

• One-Shot: Prune to target sparsity in a single step, then retrain.
• Graudal/Iterative: Increase sparsity slowly over many epochs (e.g., using a cosine schedule).
• Adaptive: Dynamically adjust the pruning rate based on training feedback like gradient norms.

The automated process of discovering optimal neural network architectures. NAS is conceptually related to the Lottery Ticket Hypothesis as both search for high-performing subnetworks within a larger space. Differentiable NAS (DNAS) and Hardware-Aware NAS (HW-NAS) are advanced forms that can directly search for efficient, compressed architectures suitable for on-device deployment, often yielding more hardware-optimal solutions than post-hoc pruning.

A framework that uses reinforcement learning or other search algorithms to automatically determine the optimal compression policy (pruning ratio, quantization bit-width) per layer. AMC treats the model as an environment and the compression strategy as actions, seeking to maximize accuracy under constraints like FLOPs or model size. It automates the scheduling decisions implied by the Lottery Ticket Hypothesis.

The runtime execution of pruned neural networks. Discovering a winning ticket is only valuable if it can be executed efficiently. This requires:

• Sparse Tensor Formats: Like CSR (Compressed Sparse Row) or CSC to store only non-zero values.
• Specialized Kernels: Linear algebra routines optimized for sparse computation.
• Hardware Support: Dedicated sparsity support in modern NPUs (e.g., sparse matrix compute units). Without efficient inference, the theoretical benefits of sparsity are lost.