Research map / Architectures and efficiency / Pruning and efficient tuning

How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective

NeurIPS 2024 · Architectures and efficiency › Pruning and efficient tuning · approach: Structured network pruning · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives a first-principles fundamental limit on network pruning ratio via statistical dimension and the approximate kinematics formula, showing it depends on weight magnitude and Hessian sharpness, and validates it against l1-regularized one-shot magnitude pruning.

Problem

The fundamental limit of how sparse a trained deep network can be pruned without losing performance is not characterized theoretically.

Approach

Imposes the sparsity constraint directly on a Hessian-quadratic loss sublevel set and reduces pruning feasibility to a convex-cone intersection problem, then uses the approximate kinematics formula with Gaussian width of the projected ellipsoid to obtain matching lower and upper bounds on the pruning ratio; the limit depends on weight magnitude of pruned weights and Hessian trace (sharpness).

Key results

• Theoretical pruning ratio limits match empirical sparsity thresholds closely, e.g. VGG16 on CIFAR-10 theoretical 0.8% vs actual 0.8%, ResNet50 on TinyImageNet 2.6% vs 2.9%.
• Upper and lower bounds on pruning ratio differ by only 0.01% to 0.27% across eight tasks in the reported experiments.
• Improved SLQ spectrum estimation with added small eigenvalues is used to compute the Gaussian width for large Hessians.

Measured effects reported in the paper

Surprising findings

• Theoretical prediction of the pruning limit is at the sub-percent to few-percent level of weights retained, far below typical pruning ratios, implying extreme sparsity thresholds under the quadratic approximation.

Limitations

• Upper and lower bounds coincide only when removed weights are very small, which relies on l1 regularization being near-optimal.
• Analysis relies on a local quadratic (Hessian) approximation of the loss around the trained minimum.
• Negative Hessian eigenvalues require heuristic convexification of the deformed ellipsoid.

Experimental setup

Datasets: CIFAR-10 CIFAR-100 TinyImageNet

Benchmarks: CIFAR-10 CIFAR-100 TinyImageNet

Metrics: test accuracy test loss pruning ratio (theoretical vs actual difference)

Baselines: Iterative magnitude pruning Rare Gems

Builds on: Gaussian width / degrees of freedom analysis of DNNs approximate kinematics formula Stochastic Lanczos Quadrature Lottery Ticket Hypothesis iterative magnitude pruning

Closest papers by meaning

• Don’t just prune by magnitude! Your mask topology is a secret weapon (NeurIPS 2023 · similarity 0.91)
• Rethinking the Value of Network Pruning (ICLR 2019 · similarity 0.91)
• Sparsest Models Elude Pruning: An Exposé of Pruning’s Current Capabilities (ICML 2024 · similarity 0.91)
• The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training (ICLR 2022 · similarity 0.91)
• Pruning Deep Neural Networks from a Sparsity Perspective (ICLR 2023 · similarity 0.91)
• No Free Prune: Information-Theoretic Barriers to Pruning at Initialization (ICML 2024 · similarity 0.89)