Iterative Magnitude Pruning (IMP)

IMP does not prune the network to its target sparsity in one step. Instead, it follows a pruning schedule, typically removing a small percentage (e.g., 20%) of the smallest-magnitude weights in each cycle. This gradual approach prevents the severe pruning-induced accuracy drop associated with aggressive one-shot pruning, allowing the network to adapt its remaining parameters incrementally.

The core heuristic for selecting weights to remove is their absolute value or L1 norm. The algorithm operates on the principle that weights with smaller magnitudes contribute less to the model's output. This is a simple, efficient, and surprisingly effective pruning criterion that requires no second-order information, making it scalable to large models.

• Process: After a training phase, all weights are scored by their absolute value.
• Selection: The bottom p% of weights (by magnitude) are set to zero.

After each pruning step, the sparsified network is retrained (or fine-tuned) on the original training data. This is the critical 'recovery' phase where the network redistributes representational capacity among its remaining, non-zero parameters to compensate for the lost connections. The combination of pruning and retraining forms one complete IMP cycle.

IMP is the experimental procedure that led to the discovery of the Lottery Ticket Hypothesis. Researchers found that the sparse subnetwork identified by IMP (the 'winning ticket'), when rewound to its initial weights and trained anew, could often match the accuracy of the original dense network. This revealed that sparse, trainable subnetworks exist at initialization within larger overparameterized models.

Standard IMP creates unstructured sparsity. It removes individual weights anywhere in the network, resulting in an irregular sparsity pattern. While this allows for high compression rates with minimal accuracy loss, it does not translate directly to speedups on standard hardware (like GPUs) without specialized libraries for sparse matrix multiplication.

IMP is a foundational algorithm that clearly demonstrates the feasibility of high levels of pruning. However, its major drawback is computational cost. The repeated cycles of training from a warm start (or rewinding) to high performance can require total training time exceeding that of the original dense model. This makes it more suitable for research and offline compression than for rapid, on-the-fly optimization.

A foundational theory that underpins IMP. It posits that within a dense, randomly-initialized neural network, there exist sparse subnetworks ('winning tickets') that, when trained in isolation from the same initialization, can match or exceed the performance of the original network. IMP is a practical algorithm for discovering these tickets through iterative pruning and rewinding weights to early training checkpoints.

These are the two primary classes of pruning granularity that define the resulting model architecture.

• Unstructured Pruning: Removes individual weights based on a criterion like magnitude, creating an irregular, sparse pattern. This achieves high theoretical compression but requires specialized software/hardware (e.g., sparse kernels) for speedup.
• Structured Pruning: Removes entire, coherent structures like filters, channels, or attention heads. This results in a smaller, dense model that runs efficiently on standard hardware but may be less aggressive in compression.

The heuristic used to score parameter importance for removal. While IMP uses weight magnitude (L1 norm) as its criterion, others include:

• Gradient-based criteria (e.g., Movement Pruning): Score weights by how much their value changes during training.
• Activation-based criteria: Use statistics from feature maps to identify less important channels.
• Loss-based criteria (e.g., SNIP): Estimate a connection's effect on the loss before any training. The choice of criterion directly impacts which subnetworks are discovered.

Critical phases in the IMP cycle that recover accuracy after pruning.

• Sparse Fine-Tuning: Retrains the pruned network (with the sparsity pattern fixed) on the task data to recover lost accuracy.
• Rewinding: A specific strategy where, after pruning, network weights are reset not to their final trained values, but to an earlier checkpoint from the initial training (e.g., epoch 1). This is a key finding of the Lottery Ticket Hypothesis and often leads to better recovery than fine-tuning from final weights.

A hardware-friendly, semi-structured sparsity pattern. It mandates that for every block of M consecutive weights (e.g., in a 1x4 vector), at most N are non-zero (e.g., 2:4 sparsity). This pattern, supported by modern NVIDIA Ampere/Ada/Hopper GPUs via the Sparse Tensor Core instruction, allows for efficient execution of pruned models without custom kernels. It bridges the gap between the flexibility of unstructured pruning and the efficiency of structured pruning.

A class of techniques aiming to identify and remove weights before any training occurs, based on metrics like gradient flow (SNIP) or synaptic saliency. The goal is to avoid the expensive train-prune-retrain cycle of IMP. While promising for rapid compression, methods like SNIP typically identify less performant subnetworks compared to those found by IMP, which leverages information from full training. These methods represent an alternative paradigm to iterative approaches.