TL;DR
This paper introduces a novel algorithm, L-mIMP, for efficiently training deep neural networks with N:M structured sparsity. By adapting the Lottery Ticket Hypothesis to this specific sparsity pattern, they significantly reduce training time (over 20x) without sacrificing accuracy, making highly efficient sparse models more accessible.
What Problem Does This Paper Address?
Deep neural networks (DNNs) achieve impressive performance but come with substantial computational and memory costs, hindering their deployment on resource-constrained devices. DNN pruning is a key technique to alleviate this, but traditional methods face trade-offs: unstructured pruning offers high sparsity but is hardware-inefficient, while coarse-grained structured pruning is hardware-friendly but often degrades accuracy. Fine-grained structured sparsity, specifically N:M sparsity (where at most N out of M consecutive weights are non-zero), offers a promising middle ground, enabling hardware acceleration. However, efficiently training DNNs with this N:M sparsity pattern, particularly finding "winning tickets" (sparse sub-networks that match or exceed dense network performance), has been a challenge. This paper aims to bridge this gap by developing an efficient iterative pruning method for N:M sparsity.
Methods
The core of the paper is the masked Iterative Magnitude Pruning (mIMP) algorithm, designed to learn N:M sparse DNNs. mIMP operates in rounds, where each round involves training, identifying "local losing tickets" (weights to be pruned within each M-weight group), accumulating them in a pool, and then pruning a percentage of the smallest weights from this pool.
To further accelerate training, two key enhancements are introduced:
- Proactive Local Pruning (PLP): Leveraging the regular structure of N:M sparsity, PLP proactively identifies and prunes weights that are likely to be unimportant at later stages. It does this by normalizing weights within each M-group and pruning those with normalized magnitudes below a threshold ($\alpha$). This allows for earlier elimination of redundant weights.
- Early-Bird (EB) Ticket Detection: Inspired by prior work, this method identifies winning tickets at earlier training iterations within a pruning round. By monitoring the similarity of weight masks over time and stopping training early when a stable pattern emerges (based on a threshold $\beta$), it reduces the training time per round.
These two techniques are integrated into Light-mIMP (L-mIMP), which combines PLP and EB detection with mIMP to drastically cut down training costs.
Datasets
The paper evaluates its methods on several standard datasets:
- CIFAR-10: Used for training and evaluating ResNet-18, ResNet-20, ResNet-56, and VGG-16 models.
- ImageNet: Used for training and evaluating ResNet-18, ResNet-50, and VGG-16 models.
- GLUE benchmark: Used for evaluating the performance of pruned BERT models on tasks like MRPC, SST-2, MNLI, CoLA, QQP, QNLI, WNLI, RTE, and STS-B.
Key Insights and Ideas
- N:M Sparsity Enables Efficient Winning Ticket Discovery: The structured nature of N:M sparsity, with its predictable weight patterns, provides a more regular distribution of winning tickets compared to unstructured sparsity. This regularity is key to identifying unimportant weights earlier and more effectively.
- Proactive Local Pruning (PLP) Accelerates Convergence: By looking at relative weight magnitudes within groups, PLP can identify and remove redundant weights much earlier in the pruning process than standard magnitude pruning, significantly reducing the number of pruning rounds needed.
- Early-Bird Tickets are Robust to N:M Sparsity: The phenomenon of finding high-performing sparse sub-networks early in training (Early-Bird tickets) is shown to exist even under N:M sparsity constraints, offering another avenue for training cost reduction.
- L-mIMP Achieves Dramatic Speedups: The combination of PLP and EB detection with mIMP leads to substantial reductions in training time (over 20x reported) without compromising model accuracy, making N:M sparse models much more practical.
Key Results
- Significant Training Cost Reduction: L-mIMP achieves over 20x reduction in training cost compared to standard mIMP, while maintaining comparable accuracy. For example, on CIFAR-10, L-mIMP shows a ~9.8x FLOPs reduction for 2:4 sparsity and ~11.8x for 1:4 sparsity compared to mIMP.
- Competitive Accuracy: L-mIMP achieves accuracy very close to, and sometimes even slightly better than, mIMP and other baseline methods, often matching the dense model's accuracy. For instance, on CIFAR-10, L-mIMP achieves accuracies like 93.09% (VGG-16, 2:4 sparsity) compared to dense 93.21%.
- BERT Performance: L-mIMP also demonstrates strong performance on the BERT model for GLUE tasks, achieving similar accuracy to mIMP but with a ~10x reduction in training FLOPs.
- Ablation Studies: The paper shows that the thresholds $\alpha$ and $\beta$ for PLP and EB detection can be tuned to balance accuracy and training cost, with smaller thresholds leading to slightly lower accuracy but much greater cost savings.
Limitations and Future Work
- Hyperparameter Tuning: The performance of L-mIMP is sensitive to the chosen thresholds $\alpha$ and $\beta$. While the paper provides guidance and shows trade-offs, optimal tuning might require experimentation for different architectures and tasks.
- Generalizability of EB Tickets: While EB tickets are shown to exist for N:M sparsity, further investigation into their robustness across a wider range of models and tasks could be beneficial.
- Hardware Implementation: The paper focuses on algorithmic efficiency. While N:M sparsity is designed for hardware acceleration, the paper doesn't deeply explore the direct hardware implementation benefits of the specific sparse patterns learned by L-mIMP.
The authors suggest that their work provides a strong foundation for efficient N:M structured sparsity training, and future work could explore more advanced pruning criteria or adaptive sparsity patterns.
Summary updated