How many winning tickets are there in one DNN?

Kathrin Grosse, Michael BackesarXiv 2020 · OpenReview

Abstract

The recent lottery ticket hypothesis proposes that there is one sub-network that matches the accuracy of the original network when trained in isolation. We show that instead each network contains several winning tickets, even if the initial weights are fixed. The resulting winning sub-networks are not instances of the same network under weight space symmetry, and show no overlap or correlation significantly larger than expected by chance. If randomness during training is decreased, overlaps higher than chance occur, even if the networks are trained on different tasks. We conclude that there is rather a distribution over capable sub-networks, as opposed to a single winning ticket.

Introduction

Since the introduction of the Lottery Ticket Hypothesis (LTH) by Frankle and Carbin in 2019, research has focused on identifying sparse, trainable sub-networks that match full-model performance. A core question remained: is a winning ticket unique to its specific initialization? Standard LTH discovery uses Iterative Magnitude Pruning (IMP), where a network is trained, pruned, and rewound to its initial weights. This study investigates whether fixing the initial weights (the "seed") while varying training randomness—such as SGD batch sampling—leads to the same sub-network.

Methods

The authors isolated the effect of initial weights from training randomness using a controlled experimental setup:

  1. Fixed Initialization: A single set of initial weights was generated and locked for multiple trials.
  2. Independent Runs: The IMP process was executed five separate times on these identical weights, allowing only training randomness to vary.
  3. Statistical Baselines: Mask overlaps were compared against a hyper-geometric distribution to establish a "random chance" baseline.
  4. Symmetry Analysis: Output similarity was measured via L2 distance and Centered Kernel Alignment (CKA) to ensure tickets weren't merely permuted versions of each other.
Experimental setup for finding multiple winning tickets from a single initialization.

Key Results

The study reveals that the "winning ticket" is largely a product of the training process rather than being pre-determined by initialization.

  • Statistical Overlap: For a ResNet18 on CIFAR-10 pruned to 10%, the overlap between tickets from the same initialization was approximately 2.5%, matching the random chance baseline.
  • Absence of Core Weights: The number of weights shared across all five independent runs dropped to zero as pruning progressed, suggesting no "structurally vital" weights exist that every ticket must include.
  • Impact of Randomness: When training randomness was partially constrained, ticket overlap increased significantly. This effect persisted even when training on different datasets (e.g., MNIST vs. Fashion-MNIST), highlighting that SGD noise is the primary determinant of ticket structure.
Distribution of percent overlap across layers under different training conditions.

Discussion and Insights

The findings suggest that an initialization does not contain a single "winning ticket" but rather a distribution of capable sub-networks. The specific ticket extracted is a sample from this distribution, heavily biased by training noise. Furthermore, metrics like CKA and L2 distance confirm these sub-networks are functionally distinct, not just weight-space symmetries.

Limitations

The study utilized relatively small networks (up to ResNet18) and standard vision datasets. Training was limited to 15 epochs per pruning iteration; longer training might potentially lead to more uniform ticket convergence, though prior work suggests tickets emerge early.

Future Work

Future research should aim to characterize the distribution of capable sub-networks prior to training. Such insights could lead to improved initialization heuristics, enabling the direct instantiation of efficient sparse networks without the computational overhead of iterative pruning.

Summary updated

Abstract

The recent lottery ticket hypothesis proposes that there is one sub-network that matches the accuracy of the original network when trained in isolation. We show that instead each network contains several winning tickets, even if the initial weights are fixed. The resulting winning sub-networks are not instances of the same network under weight space symmetry, and show no overlap or correlation significantly larger than expected by chance. If randomness during training is decreased, overlaps higher than chance occur, even if the networks are trained on different tasks. We conclude that there is rather a distribution over capable sub-networks, as opposed to a single winning ticket.
BibTeX
@misc{grosse2020how,
  author = {Kathrin Grosse and Michael Backes},
  title = {{How many winning tickets are there in one DNN?}},
  year = {2020},
  eprint = {2006.07014},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.07014},
}
Figure