Dynamic Model Pruning with Feedback

Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, Martin Jaggi

TL;DR

This paper introduces Dynamic Pruning with Feedback (DPF), a novel method for creating sparse neural networks in a single training pass without requiring retraining. DPF achieves state-of-the-art accuracy, outperforming previous pruning techniques by dynamically adjusting the sparsity pattern and using a feedback mechanism to reactivate pruned weights, leading to more robust and performant sparse models.

What Problem Does This Paper Address?

Deep neural networks, while powerful, are often computationally expensive and memory-intensive, hindering their deployment on resource-constrained devices. Model pruning aims to reduce network size by removing redundant weights, but existing methods often suffer from several drawbacks:

  • Computational Cost: Many pruning techniques require extensive training and fine-tuning of dense models, which is time-consuming and resource-intensive.
  • Suboptimal Sparsity Patterns: One-shot pruning methods fix the sparsity mask early on, potentially leading to suboptimal performance or requiring significant fine-tuning to recover accuracy.
  • Hyperparameter Tuning: Dynamic pruning methods, which adjust sparsity during training, often require careful tuning of many hyperparameters, making them difficult to apply.
  • Inability to Recover from Errors: Some methods prune weights permanently, making it impossible to recover if a weight was prematurely deemed unimportant.

This paper addresses these challenges by proposing a method that efficiently finds a performant sparse model in a single training pass, without the need for retraining, and with minimal hyperparameter tuning.

Methods

The core of the paper is the Dynamic Pruning with Feedback (DPF) algorithm. DPF operates by:

  1. Dynamic Sparsity Pattern: The sparsity mask is not fixed but is updated dynamically throughout training. This allows the network to adapt its structure as it learns.
  2. Feedback Mechanism: Crucially, DPF maintains a parallel, dense version of the network. When a stochastic gradient is computed for the pruned (sparse) network, it is applied to the dense network. This "error feedback" mechanism allows the algorithm to recover from prematurely pruned weights. If a weight that was pruned starts to accumulate significant gradient updates in the dense model, it can be reactivated in the sparse model in subsequent iterations.
  3. Single Training Pass: DPF aims to find a well-performing sparse model directly during the initial training process, eliminating the need for separate pruning and fine-tuning stages.
  4. Magnitude-Based Pruning: For selecting which weights to prune, DPF uses a standard magnitude-based criterion (i.e., pruning weights with the smallest absolute values).

The algorithm can be summarized as: $w_{t+1} = w_t - \gamma_t g(m_t w_t)$, where $w_t$ is the dense model, $m_t$ is the sparsity mask, and $g(\cdot)$ is the stochastic gradient. The key insight is applying the gradient of the pruned model to update the dense model.

Datasets

The paper evaluates DPF on the following standard image classification benchmarks:

  • CIFAR-10: A dataset with 50K training and 10K test images across 10 classes.
  • ImageNet: A large-scale dataset with 1.28 million training and 50K validation images across 1000 classes.

Key Insights and Ideas

  • Feedback is Key for Robust Sparsity: The error feedback mechanism is crucial. It allows DPF to dynamically adjust the sparsity mask and recover from potentially suboptimal pruning decisions made early in training, leading to better generalization.
  • Single-Pass Efficiency: The ability to achieve state-of-the-art results in a single training pass without retraining is a significant practical advantage, saving considerable computational resources.
  • Implicit Neural Architecture Search: DPF's dynamic mask updates can be viewed as an implicit form of neural architecture search, where the network learns to prune entire blocks or layers, effectively searching for an optimal sparse structure.
  • DPF is Not a Lottery Ticket: The paper demonstrates that the sparse models found by DPF are not "lottery tickets" in the sense that retraining them from scratch with their original initialization does not recover the same performance. This suggests DPF finds a different kind of sparse solution, one optimized during training.

Key Results

  • State-of-the-Art Accuracy: DPF consistently achieves top-1 test accuracies comparable to or exceeding dense models, even at very high sparsity levels (e.g., 99%).
  • Outperforms Baselines: DPF outperforms existing state-of-the-art pruning methods (e.g., DSR, SM, SNIP, One-shot pruning) across various architectures and datasets, particularly at high sparsity ratios. For instance, on CIFAR-10 with WideResNet-28-2 at 99% sparsity, DPF achieves 93.62% accuracy, while other methods either fail to converge or achieve significantly lower accuracy.
  • High Sparsity Achieved: DPF demonstrates remarkable performance retention even at extreme sparsity levels (e.g., 99.9% on WideResNet-28-8), where other methods often fail.
  • Minimal Hyperparameter Tuning: The method requires very little hyperparameter tuning, with a fixed reparameterization period (p=16) working well across different tasks and architectures.
  • Structured Pruning Extension: The paper shows promising results for extending DPF to structured filter pruning, outperforming existing methods.

Limitations and Future Work

  • Lottery Ticket Hypothesis: As mentioned, DPF does not find lottery tickets. While this allows for high compression, it means the learned sparse structure is dependent on the training process and not necessarily a universally optimal sparse subnetwork discoverable through random initialization.
  • Theoretical Guarantees: The paper provides theoretical convergence analysis for both convex and non-convex objectives, showing convergence to a neighborhood of the optimal solution. However, the error term in the convergence analysis suggests that for non-convex objectives, the method converges to a stationary point rather than a global minimum.
  • Future Work: The authors suggest exploring better filter selection criteria for structured pruning and further investigating the implicit neural architecture search capabilities of DPF. They also note that while DPF achieves high sparsity, the practical speedup from this sparsity is not directly measured but is expected to be significant.

Summary updated

BibTeX
@inproceedings{lin2020dynamic,
  author = {Tao Lin and Sebastian U. Stich and Luis Barba and Daniil Dmitriev and Martin Jaggi},
  title = {{Dynamic Model Pruning with Feedback}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=Ify8JJbhGLw},
}
Figure