Pruning Deep Neural Networks from a Sparsity Perspective

Enmao Diao, Ganghua Wang, Jiawei Zhang, Yuhong Yang, Jie Ding, Vahid Tarokh

Introduction

Deep learning models are growing at an unprecedented rate, with architectures like GPT-3 boasting hundreds of billions of parameters. While powerful, these massive models are incredibly difficult to deploy on mobile phones, edge devices, or any hardware with strict computation and memory constraints. Pruning—the process of identifying and removing redundant weights, neurons, or layers—has become the standard solution to compress these networks while attempting to retain test performance.

However, a significant challenge remains: most current pruning algorithms rely on a "fixed-rate" heuristic approach (e.g., blindly removing 20% of weights every iteration). This relies heavily on guesswork. Prune too little, and the model remains bloated; prune too much, and the model "collapses," leading to plummeting performance. The field has lacked a quantifiable way to measure a sub-network's "compressibility" in real-time during the pruning process. This paper addresses that gap by treating pruning not just as a heuristic, but as a measurable transition in sparsity.

Methodology: Measuring Compressibility

To solve the under- and over-pruning problem, the researchers introduce two major contributions:

  1. PQ Index (PQI): A novel mathematical measure to quantify the sparsity and compressibility of deep neural networks. Unlike the commonly used Gini Index, PQI is based on the ratio of two different vector norms ($l_p$ and $l_q$). The authors prove that PQI satisfies six essential mathematical properties for a "perfect" sparsity measure, including scale invariance and sensitivity to "Robin Hood" transfers (where moving energy from large to small weights decreases sparsity).
  2. Sparsity-informed Adaptive Pruning (SAP): Leveraging the PQI, the authors developed the SAP algorithm. Instead of using a hardcoded pruning percentage, SAP calculates a theoretical lower bound on how many parameters are actually needed to maintain performance. It adaptively decides the pruning ratio at each iteration: if the PQI suggests the model is highly compressible, SAP prunes aggressively; if the model is reaching its limit, it slows down.

The authors validated their approach across standard computer vision benchmarks (FashionMNIST, CIFAR-10, CIFAR-100, and TinyImageNet) using various architectures, including MLPs, standard CNNs, and modern residual networks like ResNet-18, ResNet-50, and WideResNet-28x8.

Key Insights

The Sparsity Lifecycle

A core discovery of this work is that during the pruning process, the PQI follows a predictable, quantifiable path that maps to the network's health and efficiency.

The three stages of pruning: Regularization, Compression, and Collapse.

As illustrated above, the network undergoes three distinct phases:

  • Regularization: Initially, PQI decreases as the large model is effectively regularized (removing noise and redundant weights).
  • Compression: PQI then increases as the model reaches its compressibility limit—the "sweet spot" right before underfitting begins.
  • Collapse: Finally, PQI decreases again right before the model collapses and significant performance deterioration occurs.

Global vs. Local Perspective

The researchers also noted that pruning the whole model at once ("Global Pruning") can sometimes ignore the fact that different layers operate at different scales. They found that SAP can be applied "Neuron-wise" or "Layer-wise" to ensure that critical early layers aren't accidentally gutted too early in the process.

Key Results

The empirical results demonstrate that SAP is highly effective, outperforming traditional iterative pruning algorithms like the Lottery Ticket Hypothesis in both efficiency and robustness.

Comparison of SAP against Lottery Ticket and One-Shot pruning across iterations.
  • Superior Efficiency: SAP (with specific $p, q$ settings) achieves the same performance as the famous "Lottery Ticket" method but reaches higher compression levels much faster. For example, on FashionMNIST, SAP reached a specific performance target in 10 iterations that took the baseline 25 iterations.
  • Fast Pruning Phenomenon: By choosing the right norms (e.g., $p=1.0, q=2.0$), SAP can compress models extremely aggressively in the early stages without sacrificing accuracy, effectively "finding" the core sub-network much earlier in the training lifecycle.
  • Robustness: Because SAP is adaptive, it dynamically protects the network. It is significantly less likely to "over-prune" a model into a state of unrecoverable performance loss compared to fixed-rate methods.

Limitations and Future Work

While SAP reduces the need to guess pruning rates, it does introduce new hyper-parameters, such as the scaling factor $\gamma$ and the norm powers $p$ and $q$. Finding the optimal settings for a brand-new architecture might still require some initial tuning. Additionally, calculating the PQI and the adaptive bound adds a small computational overhead to each pruning step, the impact of which remains to be fully explored on massive-scale training runs (like LLMs).

Looking forward, the authors suggest that PQI could be utilized beyond just pruning. It could potentially serve as a regularization term during initial training, encouraging models to naturally develop a more "compressible" structure from the very beginning.

Summary updated

Abstract

In recent years, deep network pruning has attracted significant attention in order to enable the rapid deployment of AI into small devices with computation and memory constraints. Pruning is often achieved by dropping redundant weights, neurons, or layers of a deep network while attempting to retain a comparable test performance. Many deep pruning algorithms have been proposed with impressive empirical success. However, existing approaches lack a quantifiable measure to estimate the compressibility of a sub-network during each pruning iteration and thus may under-prune or over-prune the model. In this work, we propose PQ Index (PQI) to measure the potential compressibility of deep neural networks and use this to develop a Sparsity-informed Adaptive Pruning (SAP) algorithm. Our extensive experiments corroborate the hypothesis that for a generic pruning procedure, PQI decreases first when a large model is being effectively regularized and then increases when its compressibility reaches a limit that appears to correspond to the beginning of underfitting. Subsequently, PQI decreases again when the model collapse and significant deterioration in the performance of the model start to occur. Additionally, our experiments demonstrate that the proposed adaptive pruning algorithm with proper choice of hyper-parameters is superior to the iterative pruning algorithms such as the lottery ticket-based pruning methods, in terms of both compression efficiency and robustness.
BibTeX
@inproceedings{diao2023pruning,
  author = {Enmao Diao and Ganghua Wang and Jiawei Zhang and Yuhong Yang and Jie Ding and Vahid Tarokh},
  title = {{Pruning Deep Neural Networks from a Sparsity Perspective}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=i-DleYh34BM},
}
Figure