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

By Mao Ye, Lemeng Wu, Qiang Liu. 2020

17 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Efficiency & Compression

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, methodology): “Among these works only [Ye et al., 2020b] provides theoretical guarantees, showing an O ( e − ck ) error rate.”