# Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough

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

## Key facts

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

## Built on by (most cited first, 11 of 11)

- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Rethinking Graph Lottery Tickets: Graph Sparsity Matters](https://mlsanity.com/paper/2305.02190/) (2023)
- [A Probabilistic Approach to Neural Network Pruning](https://mlsanity.com/paper/2105.10065/) (2021)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Lottery Jackpots Exist in Pre-trained Models](https://mlsanity.com/paper/2104.08700/) (2021)
- [How much pre-training is enough to discover a good subnetwork?](https://mlsanity.com/paper/2108.00259/) (2021)
- [Efficient Transformer-based 3D Object Detection with Dynamic Token Halting](https://mlsanity.com/paper/2303.05078/) (2023)
- [i-SpaSP: Structured Neural Pruning via Sparse Signal Recovery](https://mlsanity.com/paper/2112.04905/) (2021)
- [One-Shot Pruning for Fast-adapting Pre-trained Models on Devices](https://mlsanity.com/paper/2307.04365/) (2023)
- [Voting from Nearest Tasks: Meta-Vote Pruning of Pre-trained Models for Downstream Tasks](https://mlsanity.com/paper/2301.11560/) (2023)

## Abstract (arXiv)

Despite the great success of deep learning, recent works show that large deep neural networks are often highly redundant and can be significantly reduced in size. However, the theoretical question of how much we can prune a neural network given a specified tolerance of accuracy drop is still open. This paper provides one answer to this question by proposing a greedy optimization based pruning method. The proposed method has the guarantee that the discrepancy between the pruned network and the original network decays with exponentially fast rate w.r.t. the size of the pruned network, under weak assumptions that apply for most practical settings. Empirically, our method improves prior arts on pruning various network architectures including ResNet, MobilenetV2/V3 on ImageNet.