Iterative Magnitude Pruning (IMP)

IMP is defined by its repeated cycle of training, pruning, and rewinding. Unlike one-shot post-training pruning, IMP applies the pruning schedule over multiple iterations. A common pattern is:

• Train the dense network to convergence or a high-accuracy checkpoint.
• Prune a fixed percentage (e.g., 20%) of the smallest-magnitude weights.
• Rewind the remaining weights to their values from an earlier training step.
• Retrain the pruned network from this rewound state. This cycle repeats until the target sparsity (e.g., 90%) is achieved, allowing the network topology to adapt gradually.

The algorithm uses a simple, highly effective heuristic: weight magnitude as a proxy for importance. At each pruning step, parameters are ranked by their absolute value (|w|). The smallest-magnitude weights—deemed to contribute least to the model's output—are removed (set to zero). This is a form of unstructured pruning, creating irregular sparsity patterns. The core assumption is that large weights are more critical for learned representations, while near-zero weights are redundant.

IMP is the experimental procedure that led to the formulation of the Lottery Ticket Hypothesis. Researchers found that the sparse subnetwork identified by IMP—the 'winning ticket'—when trained in isolation from its original initialization, could match the accuracy of the original dense network. This characteristic is critical: IMP doesn't just compress a trained model; it discovers a sparse, trainable architecture that exists within the initial random initialization of the overparameterized network.

A key differentiator from simple iterative pruning is the weight rewinding step. After pruning, network weights are not retrained from their final pruned values nor from the original random initialization. Instead, they are reset ('rewound') to their values from an earlier checkpoint in the initial dense network's training (e.g., at iteration k). Retraining then proceeds from this rewound state. This preserves the beneficial learning dynamics and optimization landscape needed for the sparse subnetwork to recover accuracy, which is often lost if retraining from scratch or from the final dense weights.

IMP performance is highly sensitive to its pruning schedule—the policy governing how much to prune and when. Aggressive early pruning can irrecoverably damage the network. Common schedules include:

• Gradual Magnitude Pruning (GMP): A smooth, often cubic, increase in sparsity from 0% to the final target over the training epochs.
• One-shot IMP: Large pruning steps (e.g., 50%) followed by full retraining cycles. IMP typically operates at a fine-grained granularity, pruning individual weights (unstructured pruning), which maximizes flexibility in finding the winning ticket but results in sparsity patterns that require specialized software or hardware for efficient inference.

The primary goal of IMP is to manage the sparsity-accuracy tradeoff more effectively than one-shot pruning. By pruning iteratively and allowing for recovery via retraining, IMP can achieve higher sparsity levels (e.g., 90%+ weights removed) with minimal final accuracy loss compared to the dense baseline. The process inherently performs a search for a high-performing sparse network within the dense parameter space. The final performance is a direct outcome of the interplay between the pruning rate, rewinding point, and the number of iterative cycles.

Magnitude-based pruning is the foundational heuristic used by IMP. It operates on the assumption that weights with smaller absolute values contribute less to the model's output. The algorithm sorts all weights (or weights within a layer) by their magnitude and removes the smallest ones.

• Core Principle: Small weights ≈ low importance.
• Implementation: Typically uses a global or local threshold.
• Limitation: A static, small-magnitude weight may be crucial for fine-grained adjustments; magnitude alone is a simple proxy for true parameter saliency.

The Lottery Ticket Hypothesis is the theoretical underpinning that makes IMP effective. It posits that within a dense, randomly-initialized network, there exists a sparse subnetwork (a 'winning ticket') that, when trained in isolation, can match the original network's performance.

• IMP Connection: IMP's iterative train-prune-rewind cycle is a practical algorithm for finding these winning tickets.
• Key Finding: The winning ticket must be trained from its original initial weights (rewound), not from scratch, to achieve matching performance.
• Significance: Explains why IMP can find highly sparse, performant networks where one-shot pruning fails.

Gradual Magnitude Pruning is the specific schedule often employed within the IMP framework. Instead of pruning to the target sparsity in one step, GMP slowly increases sparsity over many training iterations.

• Typical Schedule: Starts at 0% sparsity and ramps up to a final target (e.g., 90%) over a defined number of steps.
• Purpose: Allows the network to gradually adapt to the removed connections, preserving accuracy much better than aggressive one-shot pruning.
• Formula: The sparsity at step t is often calculated as a cubic or exponential function of the total training steps.

This dichotomy defines the pattern of sparsity. IMP typically results in unstructured pruning.

• Unstructured Pruning: Removes individual weights anywhere in the network. This creates irregular, fine-grained sparsity that offers high theoretical compression but requires specialized software libraries or hardware (e.g., sparse tensor cores) for efficient inference.
• Structured Pruning: Removes entire structural units like neurons, channels, or filters. This results in smaller, dense matrices that run efficiently on standard hardware but can be less flexible and potentially more damaging to accuracy.
• IMP Context: Standard IMP is unstructured. Variants like Iterative Channel Pruning apply the IMP philosophy to structured elements.

A pruning criterion is the metric used to score parameters for removal. IMP uses magnitude (|w|) as its criterion, but many alternatives exist, defining different pruning families.

• Magnitude (L1 Norm): score = |w|. Simple, computationally cheap. Used by IMP.
• Gradient-Based (e.g., Movement Pruning): score = |w * ∇w|. Removes weights whose value and gradient move in opposite directions during fine-tuning.
• Second-Order (e.g., Optimal Brain Damage): score = w² * H⁻¹. Approximates the loss increase from removing a weight using the Hessian matrix. More accurate but computationally expensive.
• Activation-Based: Uses statistics like average percentage of zeros in a neuron's activation to prune inactive pathways.

The sparsity-accuracy tradeoff is the fundamental engineering compromise in all pruning, including IMP. It describes the inverse relationship between the level of sparsity (compression) achieved and the model's resulting predictive accuracy.

• The Curve: Initially, removing redundant parameters (high sparsity) may have minimal impact on accuracy. Beyond a task-dependent 'critical sparsity', accuracy drops precipitously.
• IMP's Role: IMP aims to find the optimal point on this curve for a given sparsity target by allowing accuracy recovery through iterative retraining.
• Analysis: This tradeoff is quantified using evaluation metrics (e.g., accuracy, F1) plotted against sparsity levels or model size, guiding the selection of a final pruned model for deployment.