2020

Proving the Lottery Ticket Hypothesis: Pruning is All You Need

Malach, Eran, Yehudai, Gilad, Shalev-Shwartz, Shai et al.

Understand

The lottery ticket hypothesis (Frankle and Carbin, 2018), states that a randomly-initialized network contains a small subnetwork such that, when trained in isolation, can compete with the performance of the original network.

We prove an even stronger hypothesis (as was also conjectured in Ramanujan et al., 2019), showing that for every bounded distribution and every target network with bounded weights, a sufficiently over-parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network, without any further training.

Built on

Linearized two-layers neural networks in high dimension
Original
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari · 1904
Earlier work this paper cites.
Limitations of lazy training of two-layers neural networks
Original
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari · 1906
Earlier work this paper cites.
Universal approximation using feedforward networks with non-sigmoid hidden layer activation functions
M. Stinchcombe and H. White · 1989
Earlier work this paper cites.
Optimal brain damage
Y. LeCun, J. S. Denker, and S. A. Solla · 1990
Earlier work this paper cites.
Second order derivatives for network pruning: Optimal brain surgeon
B. Hassibi and D. G. Stork · 1993
Earlier work this paper cites.
Multilayer feedforward networks with a nonpolynomial activation function can approximate any function
M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken · 1993
Earlier work this paper cites.
Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results
F. Scarselli and A. C. Tsoi · 1998
Earlier work this paper cites.
Uniform approximation of functions with random bases
A. Rahimi and B. Recht · 2008
Earlier work this paper cites.
On the computational efficiency of training neural networks
R. Livni, S. Shalev-Shwartz, and O. Shamir · 2014
Earlier work this paper cites.
Understanding machine learning: From theory to algorithms
S. Shalev-Shwartz and S. Ben-David · 2014
Earlier work this paper cites.
Learning both weights and connections for efficient neural network
S. Han, J. Pool, J. Tran, and W. Dally · 2015
Earlier work this paper cites.
Diversity networks: Neural network compression using determinantal point processes
Original
Z. Mariet and S. Sra · 2015
Earlier work this paper cites.

Similar

Data-free parameter pruning for deep neural networks
Original
S. Srinivas and R. V. Babu · 2015
Cited alongside, same era.
Network trimming: A data-driven neuron pruning approach towards efficient deep architectures
Original
H. Hu, R. Peng, Y.-W. Tai, and C.-K. Tang · 2016
Cited alongside, same era.
Pruning filters for efficient convnets
Original
H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf · 2016
Cited alongside, same era.
SGD learns the conjugate kernel class of the network
A. Daniely · 2017
Cited alongside, same era.
Learning to prune deep neural networks via layer-wise optimal brain surgeon
X. Dong, S. Chen, and S. Pan · 2017
Cited alongside, same era.
Thinet: A filter level pruning method for deep neural network compression
J.-H. Luo, J. Wu, and W. Lin · 2017
Cited alongside, same era.
Variational dropout sparsifies deep neural networks
D. Molchanov, A. Ashukha, and D. Vetrov · 2017
Cited alongside, same era.
Failures of gradient-based deep learning
S. Shalev-Shwartz, O. Shamir, and S. Shammah · 2017
Cited alongside, same era.
Designing energy-efficient convolutional neural networks using energy-aware pruning
T.-J. Yang, Y.-H. Chen, and V. Sze · 2017
Cited alongside, same era.
A convergence theory for deep learning via over-parameterization
Original
Z. Allen-Zhu, Y. Li, and Z. Song · 2018
Cited alongside, same era.
Complexity of training relu neural network
Original
D. Boob, S. S. Dey, and G. Lan · 2018
Cited alongside, same era.
Gradient descent finds global minima of deep neural networks
Original
S. S. Du, J. D. Lee, H. Li, L. Wang, and X. Zhai
Cited in the paper.

Then

The lottery ticket hypothesis: Finding sparse, trainable neural networks
Original
J. Frankle and M. Carbin · 2018
Later among the works it cites.
The computational complexity of training relu (s)
Original
P. Manurangsi and D. Reichman · 2018
Later among the works it cites.
Distribution-specific hardness of learning neural networks
O. Shamir · 2018
Later among the works it cites.
Random ReLU features: Universality, approximation, and composition
Original
Y. Sun, A. Gilbert, and A. Tewari · 2018
Later among the works it cites.
Learning and generalization in overparameterized neural networks, going beyond two layers
Z. Allen-Zhu, Y. Li, and Y. Liang · 2019
Later among the works it cites.
Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks
Original
S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang · 2019
Later among the works it cites.
A generalization theory of gradient descent for learning over-parameterized deep ReLU networks
Original
Y. Cao and Q. Gu · 2019
Later among the works it cites.
Effect of activation functions on the training of overparametrized neural nets
Original
A. Panigrahi, A. Shetty, and N. Goyal · 2019
Later among the works it cites.
What’s hidden in a randomly weighted neural network?
Original
V. Ramanujan, M. Wortsman, A. Kembhavi, A. Farhadi, and M. Rastegari · 2019
Later among the works it cites.
On the power and limitations of random features for understanding neural networks
G. Yehudai and O. Shamir · 2019
Later among the works it cites.
Deconstructing lottery tickets: Zeros, signs, and the supermask
Original
H. Zhou, J. Lan, R. Liu, and J. Yosinski · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…