Proving the Lottery Ticket Hypothesis: Pruning is All You Need

Abstract

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.

References in corpus (13)

• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
• Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures
• A Convergence Theory for Deep Learning via Over-Parameterization
• Pruning Filters for Efficient ConvNets
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Diversity Networks: Neural Network Compression Using Determinantal Point Processes
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Complexity of Training ReLU Neural Network
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Limitations of Lazy Training of Two-layers Neural Networks

Cited by in corpus (34)

• Bringing AI To Edge: From Deep Learning's Perspective
• Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
• Kronecker CP Decomposition with Fast Multiplication for Compressing RNNs
• Rethinking Weight Decay For Efficient Neural Network Pruning
• Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• A Gradient Flow Framework For Analyzing Network Pruning
• Efficient Visual Recognition with Deep Neural Networks: A Survey on Recent Advances and New Directions
• Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot
• Pruning via Iterative Ranking of Sensitivity Statistics
• Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network
• Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning
• Supermasks in Superposition
• How Powerful are Shallow Neural Networks with Bandlimited Random Weights?
• Logarithmic Pruning is All You Need
• Pruning Randomly Initialized Neural Networks with Iterative Randomization
• Exploring Weight Importance and Hessian Bias in Model Pruning
• GANs Can Play Lottery Tickets Too
• Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough
• Drawing Robust Scratch Tickets: Subnetworks with Inborn Robustness Are Found within Randomly Initialized Networks
• ExplainFix: Explainable Spatially Fixed Deep Networks
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• Slot Machines: Discovering Winning Combinations of Random Weights in Neural Networks
• Convolutional neural networks compression with low rank and sparse tensor decompositions
• The curious case of developmental BERTology: On sparsity, transfer learning, generalization and the brain
• Finding Everything within Random Binary Networks
• HALO: Learning to Prune Neural Networks with Shrinkage
• On the Existence of Universal Lottery Tickets
• Learning Pruned Structure and Weights Simultaneously from Scratch: an Attention based Approach
• Plant 'n' Seek: Can You Find the Winning Ticket?
• Dense for the Price of Sparse: Improved Performance of Sparsely Initialized Networks via a Subspace Offset
• A Probabilistic Approach to Neural Network Pruning
• Membership Inference Attacks on Lottery Ticket Networks
• CAZSL: Zero-Shot Regression for Pushing Models by Generalizing Through Context