Research map / Architectures and efficiency / Pruning and efficient tuning
No Free Prune: Information-Theoretic Barriers to Pruning at Initialization
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.
Proposes an information-theoretic "effective parameter count" (nonzero weights plus mutual information between mask and data) to explain why pruning at initialization fails to find matching lottery tickets, with theory and small-scale experiments.
Problem
Why pruning at initialization generally fails to find sparse trainable subnetworks (lottery tickets) that match dense-model accuracy, while such tickets exist and can be found by training-based pruning.
Approach
Define an effective parameter count p_eff = mutual information between the sparsity mask and the data plus the expected number of unmasked parameters, and prove a modified Law of Robustness where Lipschitz constant lower bounds scale with p_eff; masks learned from data (e.g., IMP) carry high mutual information and thus higher effective capacity than data-agnostic masks.
Key results
- On noisy-label memorization experiments, IMP-derived subnetworks memorize more training points than SNIP, GraSP, and SynFlow at the same number of unmasked parameters.
- For IMP on a student-teacher task, correlation with label noise (a lower-bound proxy for mutual information) rises during training and falls after pruning, reaching decay near ~9 pruning iterations (~10% weights remaining).
- Toy 21-parameter MLP exact mutual information estimates show IMP and post-training magnitude pruning have higher mutual information than SNIP, GraSP, and SynFlow, though all methods hit layer collapse at high sparsity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IMP instead of other pruning methods at the same number of unmasked parameters | Two-hidden-layer ReLU networks and a convNet · Gaussian data, FashionMNIST, noisy CIFAR-10, and random Boolean labels | memorization capacity | Helped |
| Prune after training rather than at initialization | Sparse networks · Toy MLPs | mask mutual information | Helped |
| Increase the learning rate (ablation) | Student-teacher task · Student-teacher task | rate of increase in correlation with label noise | Helped |
| Add noise to gradients (ablation) | Student-teacher task · Student-teacher task | correlation with label noise | Hurt |
| Iteratively prune the lowest-magnitude weights during IMP (ablation) | Student network · Student-teacher task | correlation with label noise | Mixed |
| Continue IMP until extreme sparsity, leaving almost no parameters (ablation) | Student network · Student-teacher task | correlation with label noise | Hurt |
| Prune at initialization instead of using masks selected through training | Sparse networks · Noisy-data memorization experiments | memorization capacity | Hurt |
Surprising findings
- Pruning at initialization methods with data-dependent scores (SNIP, GraSP) perform no better than data-agnostic SynFlow in prior empirical work, suggesting a shared information-theoretic barrier.
- Brute-force search over masks creates high mutual information with data, so it does not evade the bound.
Limitations
- Theory applies only when the fitted function fits below the noise level, which may not hold for LLMs trained online.
- Results are non-constructive; no optimal pruning algorithm is derived.
- Experiments use tiny networks and proxies for mutual information rather than direct MI estimates at scale; ImageNet-scale behavior is untested.
Experimental setup
Datasets: Gaussian synthetic data FashionMNIST CIFAR-10 student-teacher synthetic data
Benchmarks: FashionMNIST memorization CIFAR-10 noisy memorization Gaussian memorization
Metrics: memorization capacity (train accuracy on noisy labels) correlation with label noise exact mutual information on toy model
Baselines: SNIP GraSP SynFlow IMP magnitude pruning after training
Builds on: Law of Robustness Lottery Ticket Hypothesis SynFlow Frankle et al. 2020 pruning at initialization comparison
Closest papers by meaning
- Why Random Pruning Is All We Need to Start Sparse (ICML 2023 · similarity 0.92)
- Pruning neural networks without any data by iteratively conserving synaptic flow (NeurIPS 2020 · similarity 0.91)
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks (ICLR 2019 · similarity 0.91)
- The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training (ICLR 2022 · similarity 0.91)
- How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective (NeurIPS 2024 · similarity 0.89)
- Sparsest Models Elude Pruning: An Exposé of Pruning’s Current Capabilities (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.