Winning the Lottery Ahead of Time: Efficient Early Network Pruning

John Rachwan, Daniel Zügner, Bertrand Charpentier, Simon Geisler, Morgane Ayle, Stephan Günnemann

Introduction

Deep learning models are notoriously over-parameterized, often containing far more weights than necessary for their given tasks. The Lottery Ticket Hypothesis (LTH) suggests that within these massive networks exist sparse sub-networks—"winning tickets"—that can achieve the same performance as the full model if trained in isolation.

However, finding these winning tickets is traditionally a computational nightmare. Standard methods like Iterative Magnitude Pruning (IMP) require training the full dense model to completion multiple times. Furthermore, most research focuses on unstructured pruning (zeroing out individual weights), which fails to speed up training or save memory on standard GPUs because the underlying matrix dimensions remain unchanged.

To address the extreme cost of finding sparse models and the lack of practical hardware benefits from unstructured pruning, researchers introduce EarlyCroP (Early Compression via Gradient Flow Preservation). EarlyCroP identifies high-performing sparse sub-networks early in the training process, slashing training time, memory usage, and carbon emissions while maintaining near-dense accuracy.

The EarlyCroP Methodology

EarlyCroP shifts the pruning paradigm from post-convergence to the early stages of training through several core innovations:

  • Gradient Flow (GF) Preservation: Instead of pruning based on weight magnitude, EarlyCroP removes weights that have the least impact on the network's gradient flow. This ensures the training dynamics of the sparse model closely mimic the original dense model.
  • The NTK Connection: The authors provide a theoretical bridge showing that preserving Gradient Flow also preserves the Neural Tangent Kernel (NTK). Because the NTK describes how a network's predictions evolve during training, keeping it stable ensures the sparse model learns similarly to the dense one.
  • Structured Pruning (EarlyCroP-S): To achieve real-world speedups, the GF criterion is adapted to remove entire neurons or convolutional channels using auxiliary "gates." This directly reduces the VRAM footprint and computation time on commodity GPUs.
  • Automatic Timing: Pruning at initialization (epoch 0) often hurts performance, while pruning at the end is wasteful. EarlyCroP identifies the transition to the "lazy kernel regime"—a point early in training where learning dynamics stabilize. A simple heuristic based on the relative change in weight norms is used to trigger pruning automatically.
Correlation between pruning time and final accuracy. The star indicates the automatically detected optimal pruning point.

As illustrated above, there is a clear correlation between timing and accuracy: waiting for the learning dynamics to stabilize (the blue line dropping) leads to significantly higher final test accuracy (the purple dots rising).

Key Results and Real-World Impact

The researchers evaluated EarlyCroP across a wide variety of domains, including Computer Vision (CIFAR, ImageNet), Regression (NYU Depth Estimation), NLP (BERT on GLUE), and Reinforcement Learning.

Efficiency vs. Accuracy EarlyCroP-S provides a superior trade-off compared to other structured pruning methods. For example, on VGG16 trained on CIFAR-100, it achieves higher accuracy with significantly less GPU RAM than unstructured baselines.

Trade-off between Relative GPU RAM and Test Accuracy. EarlyCroP-S (orange) maintains high accuracy while using substantially less memory.

Concrete Savings and Scaling * Speed and Performance: On ResNet18/CIFAR-10 at 95% sparsity, EarlyCroP-S reached 91.0% accuracy (compared to the dense 91.5%) while reducing training time by 33% and batch time by 39%. * Environmental Impact: By pruning early and efficiently, the method can reduce carbon emissions by up to 70% compared to standard training. * Democratizing Large Models: Because EarlyCroP-S reduces memory requirements early, it allows researchers to train massive models on mid-range hardware. The authors successfully trained a ResNext101 model (829M parameters) on a commodity GPU by pruning it to 98.5% sparsity early in training. The resulting sparse model outperformed a smaller dense model of similar size while being 7x faster to train.

Limitations and Future Directions

While EarlyCroP represents a significant step forward, it is not without limitations. Because structured pruning saves memory after the cut, the very first few epochs still require the full dense model's VRAM. Users might need to reduce batch sizes initially or perform the first pruning step on a CPU. Additionally, unstructured pruning (EarlyCroP-U) still holds a slight accuracy edge over structured pruning on the most complex datasets, suggesting room for improvement in structured scoring mechanisms.

Future work may explore more sophisticated ways to detect the transition to the lazy kernel regime and apply these "early-bird" techniques to diverse architectures like Transformers.

Summary updated

Abstract

Pruning, the task of sparsifying deep neural networks, received increasing attention recently. Although state-of-the-art pruning methods extract highly sparse models, they neglect two main challenges: (1) the process of finding these sparse models is often very expensive; (2) unstructured pruning does not provide benefits in terms of GPU memory, training time, or carbon emissions. We propose Early Compression via Gradient Flow Preservation (EarlyCroP), which efficiently extracts state-of-the-art sparse models before or early in training addressing challenge (1), and can be applied in a structured manner addressing challenge (2). This enables us to train sparse networks on commodity GPUs whose dense versions would be too large, thereby saving costs and reducing hardware requirements. We empirically show that EarlyCroP outperforms a rich set of baselines for many tasks (incl. classification, regression) and domains (incl. computer vision, natural language processing, and reinforcment learning). EarlyCroP leads to accuracy comparable to dense training while outperforming pruning baselines.
BibTeX
@inproceedings{rachwan2022winning,
  author = {John Rachwan and Daniel Zügner and Bertrand Charpentier and Simon Geisler and Morgane Ayle and Stephan Günnemann},
  title = {{Winning the Lottery Ahead of Time: Efficient Early Network Pruning}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=wnrEwDFIHMT},
}
Figure