TL;DR
This paper introduces RigL, a novel method for training sparse neural networks that dynamically adjusts the network's topology during training. RigL achieves state-of-the-art accuracy with significantly fewer computational resources (FLOPs) compared to existing methods, effectively "rigging the lottery" to make more sparse networks winners.
What Problem Does This Paper Address?
Training sparse neural networks is crucial for applications with limited computational resources, such as mobile devices or edge computing, due to their reduced memory footprint and faster inference times. However, current methods often fall into two categories: either they train a dense network and then prune it (dense-to-sparse), which limits the final sparse model's size to that of the largest trainable dense model, or they train sparse networks with a fixed topology. The latter can lead to suboptimal performance by getting stuck in local minima. This paper addresses the challenge of training highly accurate sparse neural networks with a fixed computational budget and parameter count, without sacrificing performance and overcoming the limitations of static sparse network topologies.
Methods
The core of RigL is its dynamic approach to sparsity. Instead of a fixed mask, RigL iteratively updates the network's connectivity during training. At regular intervals, it prunes a fraction of the least important connections (based on magnitude) and simultaneously grows new connections based on the magnitude of their gradients. This "grow and prune" strategy, guided by gradient information, allows the network to adapt its structure. RigL maintains a fixed parameter count and computational cost throughout training, making it efficient. The paper also explores different strategies for distributing sparsity across layers (Uniform, Erdős-Rényi, Erdős-Rényi-Kernel) and various update schedules.
Datasets
The authors evaluated RigL on several standard benchmarks:
- ImageNet-2012: For image classification using ResNet-50 and MobileNets (v1 and v2).
- CIFAR-10: For image classification using WideResNet-22-2.
- WikiText-103: For character-level language modeling using RNNs.
- MNIST: For comparing against structured pruning algorithms using a LeNet-300-100 network.
Key Insights and Ideas
- Dynamic Topology is Key: Allowing the network's connectivity to change during training is crucial for escaping local minima and achieving higher accuracy, especially compared to static sparse networks.
- Gradient-Guided Growth: Using gradient magnitudes to decide which new connections to grow is more effective than random growth or other initialization strategies.
- Fixed Budget, High Performance: RigL demonstrates that it's possible to achieve state-of-the-art accuracy with a fixed computational budget, challenging the notion that more FLOPs are always necessary for better performance.
- "Rigging the Lottery": The name itself is a key insight. Unlike the Lottery Ticket Hypothesis which relies on finding specific "winning tickets" (initializations), RigL suggests that by dynamically rewiring, all tickets (connections) can be made winners, leading to robust performance.
- Sparsity Distribution Matters: The Erdős-Rényi-Kernel (ERK) sparsity distribution, which allocates sparsity based on layer size and kernel dimensions, consistently outperforms uniform sparsity.
Key Results
- State-of-the-Art Accuracy: RigL achieved state-of-the-art sparse training results on ResNet-50, MobileNets, and RNNs across various datasets. For instance, on ImageNet-2012, RigL with 96.5% sparsity achieved 72.75% Top-1 accuracy, significantly outperforming prior methods.
- Computational Efficiency: RigL requires fewer FLOPs for training to achieve a given accuracy level compared to existing dense-to-sparse and sparse-to-sparse methods. For example, it achieved higher accuracy with less training cost than iterative pruning methods.
- Improved MobileNet Performance: RigL significantly boosted the accuracy of MobileNet models, even achieving a 4.3% absolute improvement in Top-1 accuracy on ImageNet-2012 for a sparse MobileNet-v1 with the same FLOPs and parameter count as its dense counterpart.
- Overcoming Local Minima: Experiments analyzing the loss landscape showed that RigL's dynamic connectivity helps it escape suboptimal solutions that static sparse training methods get stuck in.
Limitations and Future Work
- Hardware Support: The paper notes that while RigL offers significant advantages, the full potential of sparse networks is still limited by the lack of widespread hardware and software support for sparsity.
- Character-Level LM Performance: While RigL performed well on character-level language modeling, it did not quite match the performance of traditional pruning methods in this specific setting, suggesting an area for future work.
- Hyperparameter Sensitivity: While RigL is generally robust, the paper mentions that optimal performance can depend on hyperparameter choices like the update interval (ΔT) and initial drop fraction (α), and suggests further exploration of these.
- Lottery Ticket Hypothesis: The paper's experiments suggest that RigL might not benefit from specific "lottery ticket" initializations, indicating that dynamic rewiring is the primary driver of its success, rather than finding a lucky initial sparse network.
Summary updated