# Logarithmic Pruning is All You Need

arXiv: https://arxiv.org/abs/2006.12156 · HTML: https://mlsanity.com/paper/2006.12156/

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2020.

## Built on by (most cited first, 30 of 71)

- [DepGraph: Towards Any Structural Pruning](https://mlsanity.com/paper/2301.12900/) (2023)
- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [Structured Pruning for Deep Convolutional Neural Networks: A survey](https://mlsanity.com/paper/2303.00566/) (2023)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness](https://mlsanity.com/paper/2106.09129/) (2021)
- [Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network](https://mlsanity.com/paper/2103.09377/) (2021)
- [Recent Advances on Neural Network Pruning at Initialization](https://mlsanity.com/paper/2103.06460/) (2021)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Rare Gems: Finding Lottery Tickets at Initialization](https://mlsanity.com/paper/2202.12002/) (2022)
- [On the Existence of Universal Lottery Tickets](https://mlsanity.com/paper/2111.11146/) (2021)
- [Why Random Pruning Is All We Need to Start Sparse](https://mlsanity.com/paper/2210.02412/) (2022)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Most Activation Functions Can Win the Lottery Without Excessive Depth](https://mlsanity.com/paper/2205.02321/) (2022)
- [Pruning Randomly Initialized Neural Networks with Iterative Randomization](https://mlsanity.com/paper/2106.09269/) (2021)
- [A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2206.04270/) (2022)
- [On the Surprising Effectiveness of Attention Transfer for Vision Transformers](https://mlsanity.com/paper/2411.09702/) (2024)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [A Probabilistic Approach to Neural Network Pruning](https://mlsanity.com/paper/2105.10065/) (2021)
- [Masks, Signs, And Learning Rate Rewinding](https://mlsanity.com/paper/2402.19262/) (2024)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [Plant 'n' Seek: Can You Find the Winning Ticket?](https://mlsanity.com/paper/2111.11153/) (2021)
- [Dimensionality Reduced Training by Pruning and Freezing Parts of a Deep Neural Network, a Survey](https://mlsanity.com/paper/2205.08099/) (2022)
- [Lottery Jackpots Exist in Pre-trained Models](https://mlsanity.com/paper/2104.08700/) (2021)
- [SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning](https://mlsanity.com/paper/2112.04002/) (2021)
- [Sparse Binary Transformers for Multivariate Time Series Modeling](https://mlsanity.com/paper/2308.04637/) (2023)
- [Optimal Recurrent Network Topologies for Dynamical Systems Reconstruction](https://mlsanity.com/paper/2406.04934/) (2024)
- [The Lottery Ticket Hypothesis for Self-attention in Convolutional Neural Network](https://mlsanity.com/paper/2207.07858/) (2022)
- [Survival of the Fittest Representation: A Case Study with Modular Addition](https://mlsanity.com/paper/2405.17420/) (2024)

## Abstract (arXiv)

The Lottery Ticket Hypothesis is a conjecture that every large neural network contains a subnetwork that, when trained in isolation, achieves comparable performance to the large network. An even stronger conjecture has been proven recently: Every sufficiently overparameterized network contains a subnetwork that, at random initialization, but without training, achieves comparable accuracy to the trained large network. This latter result, however, relies on a number of strong assumptions and guarantees a polynomial factor on the size of the large network compared to the target function. In this work, we remove the most limiting assumptions of this previous work while providing significantly tighter bounds:the overparameterized network only needs a logarithmic factor (in all variables but depth) number of neurons per weight of the target subnetwork.