The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks

Problem

Framing

Pruning had shown that trained networks contain massive redundancy, but it was unclear whether sparse subnetworks are trainable from the start rather than only after dense training. The paper argues that dense initializations already contain "winning tickets": subnetworks that, when reset to their original weights, match or exceed dense accuracy in no more iterations.

Currently Used Methods

Foundational

• @lecunGradientbasedLearningApplied1998 — LeNet-style CNNs for MNIST classification.
  • Limitation in context: dense training gives no rule for trainable sparse subnetworks.
• @heDeepResidualLearning2016 — residual CNNs that scale deep image classification.
  • Limitation in context: overparameterization remains essential during standard training.
• @srivastavaDropout2014 — stochastic unit dropping for regularization.
  • Limitation in context: preserves dense parameterization instead of fixed sparse subnetworks.
• @goodfellowGAN2014 — demonstrates optimization sensitivity to initialization and architecture.
  • Limitation in context: does not test sparse subnetworks reset to original weights.
• "Learning both Weights and Connections for Efficient Neural Networks" — magnitude pruning after training compresses dense models.
  • Limitation in context: sparse structure appears only after full dense optimization.

Proposed Method

Architecture

The method is architecture-agnostic: train a dense network, prune by magnitude, then retrain the surviving masked subnetwork from its original initialization $\theta_0$. The paper tests LeNet-300-100 on MNIST, Conv-2/4/6 on CIFAR-10, and later ResNet-18 and VGG-19.

Loss / Objective

A winning ticket is defined by matching dense-model accuracy and training time under the same optimizer.

Algorithm

Iterative magnitude pruning alternates training, pruning, and resetting surviving weights to $\theta_0$.

Training Procedure

• Initialization: Gaussian Glorot.
• LeNet optimizer: Adam, learning rate $1.2 \times 10^{-3}$.
• Conv-2 optimizer: Adam, learning rate $2 \times 10^{-4}$.
• Conv-4/6 optimizer: Adam, learning rate $3 \times 10^{-4}$.
• Iterations/batch: LeNet $50\text{K}/60$; Conv-2 $20\text{K}/60$; Conv-4 $25\text{K}/60$; Conv-6 $30\text{K}/60$.
• Pruning rate: LeNet fc $20\%$; Conv-2 conv $10\%$, fc $20\%$; Conv-4 conv $10\%$, fc $20\%$; Conv-6 conv $15\%$, fc $20\%$.

Evaluation

Datasets

• MNIST.
• CIFAR-10.
• Later experiments: ResNet-18 and VGG-19 on CIFAR-10.

Metrics

• Test accuracy at early stopping.
• Early-stop iteration, defined by minimum validation loss.
• Percent of weights remaining.
• Comparison against random sparse subnetworks and random reinitialization.

Headline results

• LeNet-300-100 (MNIST): winning tickets outperform random sparse subnetworks across heavy pruning levels.
• Conv-2 (CIFAR-10): best winning ticket reaches minimum validation loss $3.5\times$ faster at $8.8\%$ weights remaining.
• Conv-4 (CIFAR-10): best winning ticket reaches minimum validation loss $3.5\times$ faster at $9.2\%$ weights remaining.
• Conv-6 (CIFAR-10): best winning ticket reaches minimum validation loss $2.5\times$ faster at $15.1\%$ weights remaining.
• CIFAR-10 Conv-2/4/6: best test-accuracy gains are $+3.4$, $+3.5$, and $+3.3$ points at moderate sparsity.

Ablations

• Random reinitialization: sharply degrades sparse-subnetwork performance; structure alone is insufficient.
• Dropout training: still yields winning tickets, but speedups shrink relative to no-dropout training.
• Pruning target: pruning convolutions helps more than pruning FC layers alone.
• Learning rate: deeper models require lower rates to expose winning tickets reliably.

Method Strengths and Weaknesses

Strengths

• Separates sparsity structure from initialization by resetting survivors to $\theta_0$.
• Measures optimization speed, not just final accuracy, via early-stop iteration.
• Shows random reinitialization fails, isolating initialization as a core factor.
• Demonstrates the effect across MLPs and multiple CNN depths.

Weaknesses

• Finding tickets is expensive: repeated train-prune-reset cycles require many full trainings.
• Main positive results center on MNIST and CIFAR-10, not large-scale ImageNet.
• Success is sensitive to optimizer and learning rate, especially for deeper networks.
• The paper identifies tickets empirically, not with a predictive theory.

Suggestions from the authors

• Develop cheaper procedures for finding winning tickets on larger datasets such as ImageNet.
• Study which initialization properties make winning tickets especially easy to optimize.
• Explain why deeper networks need lower learning rates to reveal winning tickets.
• Characterize how architecture, dataset, and optimizer interact with ticket quality.

Links

Prior Papers

• @lecunGradientbasedLearningApplied1998 — provides the LeNet architecture family used for the MNIST experiments.
• @heDeepResidualLearning2016 — provides ResNet-18, one of the deeper architectures tested.
• @srivastavaDropout2014 — serves as a regularization baseline and ablation target in ticket experiments.

Further Papers

• @frantarGPTQ2022 — continues the theme of exploiting parameter redundancy for efficient neural networks through compression.
• @powerGrokking2022 — overlaps on optimization dynamics and the role of initialization in when subnetworks learn.
• @dettmersQLoRA2023 — extends the efficiency agenda by reducing memory and parameter costs during adaptation.