🤖 machine learning

Pruning Deep Neural Networks via the Marchenko--Pastur Distribution

This paper introduces a Marchenko-Pastur distribution-based pruning framework that achieves high-accuracy retention in deep neural networks with minimal fine-tuning by providing deterministic theoretical certificates for component removal, demonstrating significant performance and efficiency gains across various architectures like ViT, ResNet, and ConvNeXt on ImageNet-1k.

Original authors: Leonid Berlyand, Theo Bourdais, Houman Owhad, Yitzchak Shmalo

Published 2026-06-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Leonid Berlyand, Theo Bourdais, Houman Owhad, Yitzchak Shmalo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, incredibly detailed library (a Deep Neural Network) filled with millions of books (weights). You want to shrink this library down to fit in a small backpack so you can carry it easily, but you're terrified that if you throw out the wrong books, the library will stop making sense.

This paper is about a new, clever way to decide which books to throw away without needing to re-read the whole library afterward.

The Problem: The "Over-Engineered" Library

Deep Neural Networks are often "over-parameterized," meaning they have way more books than they actually need to tell a story. Usually, to shrink them, you'd have to:

Throw away some books.
Re-read the whole library to see what's missing.
Rewrite the remaining books to fix the story.
Repeat this many times.

This takes a long time and a lot of computing power. The authors wanted to know: Can we just throw away the right books once and be done?

The Solution: The "Marchenko–Pastur" Crystal Ball

The authors use a mathematical tool called Random Matrix Theory, specifically something called the Marchenko–Pastur (MP) distribution.

Think of the weights in a neural network layer as a giant crowd of people at a concert.

The "Noise" (The Bulk): Most of the crowd is just shuffling around randomly, making a general hum. In math terms, this is the "random noise" or the "bulk" of the data.
The "Signal" (The Spikes): A few people are standing on chairs, waving flags, or shouting specific instructions. These are the important patterns the network learned.

The Marchenko–Pastur distribution acts like a crystal ball that tells you exactly where the line is between the "shuffling crowd" (noise) and the "people on chairs" (signal).

The Method: How They Prune

Instead of just throwing away the smallest books (a common method called "magnitude pruning"), this paper uses the crystal ball to identify the "noise" books.

The Audit: They look at a layer of the network and ask, "Is this part of the random shuffling crowd, or is it a signal?"
The Cut: If the math says a group of weights is just "noise" (part of the Marchenko–Pastur bulk), they cut them out.
The "Restore" Trick: Sometimes, they cut too much by accident. So, they have a "restore" step. They look at the cut pieces and say, "Wait, this specific piece was actually important for the story, even if it looked like noise." They put just that piece back in.
- Analogy: Imagine you're packing a suitcase. You throw out all the socks. Then you realize you need one specific pair for a wedding. You put that one pair back. You still have a lighter suitcase, but you didn't lose the wedding sock.

The Results: Fast and Accurate

The paper tested this on famous image-recognition models (like those that identify cats, dogs, and cars in photos).

Speed: They didn't need to re-train the models for weeks. They only did a tiny bit of "fine-tuning" (like a quick 3-day check-up) after pruning.
Accuracy: Even after cutting out a huge chunk of the network (making it 50% to 60% smaller), the models still got almost the same score as the giant, full-size version.
- Example: A model called ViT-B/16 was shrunk down, and it still got 83.41% accuracy (only a tiny drop from the original).
Real-World Speed: Because the network is now smaller and has a specific pattern (like keeping 2 out of every 4 weights), it runs faster on modern computer chips (GPUs). They measured speedups of about 1.4x to 2.7x on specific hardware.

The "Certificates" (Why We Can Trust It)

The authors didn't just guess; they wrote mathematical "certificates."

Think of this like a safety guarantee. They proved mathematically that if the "noise" they removed was small enough, the "story" the network tells (the prediction) wouldn't change.
They also proved that if the network was trained long enough, the "noise" part naturally shrinks to nothing, leaving only the important "signal" spikes.

Summary

This paper is like finding a smart filter for a deep neural network. Instead of blindly deleting the smallest numbers, it uses a mathematical law (Marchenko–Pastur) to identify and remove the "background noise" of the network.

The result is a smaller, faster network that still works almost perfectly, achieved with very little extra work to fix it afterward. It's a way to make AI models lighter and faster without breaking them.

Technical Summary: Pruning Deep Neural Networks via the Marchenko–Pastur Distribution

1. Problem Statement

The paper addresses the challenge of compressing Deep Neural Networks (DNNs), specifically Vision Transformers (ViTs) and Convolutional Neural Networks (CNNs), for deployment under strict constraints. The primary goal is to achieve significant sparsity (reducing Multiply-Accumulate operations, or MACs) while retaining high accuracy, but with a critical constraint: minimal post-pruning fine-tuning budgets.

Existing pruning pipelines often rely on long retraining schedules or extensive re-optimization to recover accuracy after pruning. This work investigates whether a Marchenko–Pastur (MP) random-matrix approach can provide deterministic "data-path certificates" that allow for accurate pruning with very short calibration and fine-tuning schedules (e.g., one epoch per cycle or three distillation epochs). The core problem is distinguishing between "noise" (random-like components that can be removed) and "signal" (structured components that must be preserved) within trained weight matrices without access to validation or test data during the mask construction phase.

2. Methodology

2.1 Theoretical Framework: Signal vs. Noise

The authors propose a modeling assumption where a trained weight matrix $W$ at layer $\ell$ can be decomposed into a structured signal component $S$ and a random perturbation component $R$ :
$W = S + R$

Signal ( $S$ ): Assumed to be low-rank or approximately low-rank relative to the layer width, representing learned features.
Noise ( $R$ ): Modeled as an independent random perturbation. Under the Marchenko–Pastur (MP) law, the singular values of such random matrices form a "bulk" distribution with a known upper edge $\sigma_+$ .

The theory posits that if the removed component $R$ has a small propagated logit effect, pruning it decreases an elastic-net objective and preserves samples with sufficient dense margins.

2.2 Pruning Algorithms

The paper introduces two primary algorithmic strategies based on this theoretical framework:

SER (Sparsify–Estimate–Restore):
- Mechanism: Starts with an over-pruned candidate (removing weights based on MP-guided budgets). It then evaluates the "lost mass" through the data path and restores entries that are most useful for the target sparse model.
- Hybrid Magnitude–SER: Combines standard magnitude pruning (effective at low sparsity) with SER (effective at high sparsity) to leverage the stability of magnitude pruning and the spectral sensitivity of SER.
CAST (Structured Sparsity):
- Mechanism: Targets fixed $k:n$ structured sparsity patterns (e.g., 2:4, 6:12, 8:16), which are compatible with hardware accelerators like NVIDIA Tensor Cores.
- Process: Uses a "certificate-inspired" objective to select which entries to keep within a group. It employs a "free restoration" concept: within a group where the execution cost is already fixed by the sparsity pattern, restoring a kept entry can improve the theoretical certificate without changing the number of executed weights.
- ToMe Integration: For Vision Transformers, the method combines weight pruning with Token Merging (ToMe) to reduce the number of processed tokens, further reducing computational load.

2.3 Theoretical Certificates

The paper provides three main theoretical results to justify the pruning:

Deterministic Data-Path Certificate: Proves that if the removed component $R$ satisfies a bound on its propagated logit effect ( $L_s \|R\psi_1(s)\|_\infty$ ), pruning decreases an elastic-net objective and preserves training samples whose dense margin exceeds twice the perturbation.
Prune–Restore Certificate: Models structured sparsity, showing that restoring entries within a fixed sparse-execution group can improve the bound without altering the final execution pattern.
Additive $L_2$ -Regularized Theory: Demonstrates that under one-sided stationarity and local-path convergence, admissible random-like components vanish at the training limit, while persistent signal spikes stabilize as the MP bulk collapses.

3. Key Results

3.1 Unstructured Pruning (ViT-B/16)

On ImageNet-1k, the Hybrid Magnitude–SER method achieved 83.37% top-1 accuracy at 50% unstructured sparsity. This represents a drop of only 1.74 percentage points (pp) from the dense baseline (85.11%), achieved with a very short fine-tuning budget (one epoch per cycle). This outperformed both classical magnitude pruning (81.67%) and a direct Random Matrix Theory (RMT) baseline (82.57%) under identical conditions.

3.2 Structured Sparsity and Deployment

The paper reports results for structured $k:n$ patterns, distinguishing between accuracy/MAC accounting and actual hardware speedups:

ViT-B/16 (2:4 + ToMe): Achieved 83.41% top-1 (−1.70 pp) with a 59.81% reduction in sparse-execution MACs. On an NVIDIA A40, this checkpoint demonstrated a 1.388× native sparse Tensor Core speedup.
ViT-B/16 (No ToMe, A100): A separate endpoint achieved a 2.705× speedup when moving from dense to 2:4 sparsity without ToMe.
Wider Patterns:
- ViT-B/16 (6:12): 83.74% top-1.
- ViT-L/16 (8:16 dense+permutation): 85.33% top-1 (−0.51 pp).
- ConvNeXtV2-Base (12:16): 86.35% top-1 (−0.37 pp).
CNNs:
- ResNet50 (8:16 dense+permutation): 75.87% top-1 (−0.26 pp).
- ResNet152d (CAST-conv+permutation): 81.33% top-1 (−1.53 pp) with a 1.62× A40 im2col+2:4 sparse-GEMM speedup.

3.3 Scaling Laws

Empirical evidence suggests that larger dense checkpoints tend to incur smaller top-1 penalties at matched sparsity levels. The authors attribute this to the MP edge being an asymptotic spectral object better resolved in larger matrices, and wider overparameterized layers containing a larger "random-like bulk reservoir" whose removal has a minimal data-path effect.

4. Significance and Claims

The paper claims its main contributions are:

Accuracy Retention with Short Budgets: Demonstrating that high accuracy can be retained after pruning with minimal fine-tuning (e.g., 3 distillation epochs for CAST), contrasting with pipelines requiring long retraining.
Deterministic Certificates: Providing theoretical guarantees that link the removal of random-like components (identified via MP diagnostics) to the preservation of accuracy, specifically for samples with large margins.
Practical Deployability: Validating that these theoretical signals translate to real-world speedups on hardware (A40/A100) for both ViTs and CNNs, particularly when combined with structured sparsity patterns (2:4, 6:12, etc.).
Layerwise Allocation: Using MP spectral diagnostics to allocate different pruning budgets to different layers based on their spectral properties (treating MP-like layers as candidates for larger budgets while protecting non-MP or heavy-tailed layers).

The authors explicitly state that the MP edge serves as a sufficient random-matrix condition and a practical layerwise signal, rather than a complete certified bound for all transformer architectures. The work is presented as a "certificate-inspired" approach where the theory motivates the algorithm, and the empirical results validate the efficacy of the short-budget pruning strategy.