Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient

Abstract

The strong {\it lottery ticket hypothesis} (LTH) postulates that one can approximate any target neural network by only pruning the weights of a sufficiently over-parameterized random network. A recent work by Malach et al. \cite{MalachEtAl20} establishes the first theoretical analysis for the strong LTH: one can provably approximate a neural network of width $d$ and depth $l$, by pruning a random one that is a factor $O(d^4{l}^2)$ wider and twice as deep. This polynomial over-parameterization requirement is at odds with recent experimental research that achieves good approximation with networks that are a small factor wider than the target. In this work, we close the gap and offer an exponential improvement to the over-parameterization requirement for the existence of lottery tickets. We show that any target network of width $d$ and depth $l$ can be approximated by pruning a random network that is a factor $O(\log (dl))$ wider and twice as deep. Our analysis heavily relies on connecting pruning random ReLU networks to random instances of the \textsc{SubsetSum} problem. We then show that this logarithmic over-parameterization is essentially optimal for constant depth networks. Finally, we verify several of our theoretical insights with experiments.

References in corpus (13)

• SGDR: Stochastic Gradient Descent with Warm Restarts
• Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
• AMC: AutoML for Model Compression and Acceleration on Mobile Devices
• Binarized Neural Networks
• A Survey of Model Compression and Acceleration for Deep Neural Networks
• Trained Ternary Quantization
• Pruning Filters for Efficient ConvNets
• To prune, or not to prune: exploring the efficacy of pruning for model compression
• Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• The Search for Sparse, Robust Neural Networks
• Logarithmic Pruning is All You Need

Cited by in corpus (8)

• 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
• Logarithmic Pruning is All You Need
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness
• ExplainFix: Explainable Spatially Fixed Deep Networks
• Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough
• Finding Everything within Random Binary Networks