On the Existence of Universal Lottery Tickets

Abstract

The lottery ticket hypothesis conjectures the existence of sparse subnetworks of large randomly initialized deep neural networks that can be successfully trained in isolation. Recent work has experimentally observed that some of these tickets can be practically reused across a variety of tasks, hinting at some form of universality. We formalize this concept and theoretically prove that not only do such universal tickets exist but they also do not require further training. Our proofs introduce a couple of technical innovations related to pruning for strong lottery tickets, including extensions of subset sum results and a strategy to leverage higher amounts of depth. Our explicit sparse constructions of universal function families might be of independent interest, as they highlight representational benefits induced by univariate convolutional architectures.

Accepted for publication at The Tenth International Conference on Learning Representations (ICLR 2022)

References in corpus (10)

• Deep Learning in Neural Networks: An Overview
• Reconciling modern machine learning practice and the bias-variance trade-off
• SNIP: Single-shot Network Pruning based on Connection Sensitivity
• Picking Winning Tickets Before Training by Preserving Gradient Flow
• Optimal approximation of continuous functions by very deep ReLU networks
• The Cost of Training NLP Models: A Concise Overview
• Dynamic Model Pruning with Feedback
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Winning the Lottery with Continuous Sparsification
• Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network