Draft:The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks

• Comment: Could you please add sources that aren't from arXiv, WP:PREPRINT aren't considered reliable sources. I know the preprint has a lot of citations but still having the peer reviewed paper would be an improvement. Dr vulpes (Talk) 17:43, 24 October 2024 (UTC)

---

Neural networks have become integral to modern machine learning, achieving remarkable performance in tasks like image recognition and natural language processing. However, these models are often over-parameterized, containing far more weights and connections than necessary. Although pruning can reduce network size after training by removing up to 90% of parameters without sacrificing accuracy, the sparse architectures resulting from pruning are challenging to train from scratch, which would otherwise enhance training efficiency and achieve similar accuracy.

The Lottery Ticket Hypothesis, proposed by Jonathan Frankle and Michael Carbin in their 2018 paper, offers a different perspective. It suggests that within a randomly initialized, dense neural network lies a smaller, sparse subnetwork—referred to as a “winning ticket”—that, when trained independently from its original initialization, can match or exceed the performance of the full network. These subnetworks “win the initialization lottery,” meaning their specific initial weights make them particularly suited for effective training.

Through experiments on fully connected and convolutional networks, the authors demonstrate that these winning tickets, which are often only 10-20% the size of the original model, can be trained to achieve as much or more accuracy than larger networks.

The Lottery Ticket Hypothesis

Statement of the Hypothesis

The Lottery Ticket Hypothesis proposes that within a large, randomly-initialized, dense neural network, there exists a much smaller subnetwork that can be trained in isolation to achieve comparable performance to the full network. This subnetwork, when trained from its original random initialization, can achieve comparable or better accuracy in lesser number of training steps with significantly less number of parameters.

Formal Explanation

Consider a dense feed-forward neural network $f(x;\theta )$ with initial parameters $\theta =\theta _{0}\sim D_{\theta }$, where $D_{\theta }$ represents the distribution from which the weights are randomly initialized. When this network is optimized using stochastic gradient descent (SGD), it reaches a minimum validation loss $l$ after $j$ iterations and achieves a test accuracy $a$.

Now, introduce a binary mask $m\in \{0,1\}^{|\theta |}$ where each entry in the mask corresponds to a weight in the network. The mask defines a subnetwork by turning off some weights in $\theta$. The subnetwork is trained with the remaining weights initialized to their original random values, $m\odot \theta _{0}$ (where $\odot$ represents element-wise multiplication).

The Lottery Ticket Hypothesis predicts that there exists a mask $m$ such that the pruned subnetwork, when trained using the same dataset and optimization method, will:

• Reach the same or lower validation loss $l'$ in at most the same number of iterations $j'\leq j$,
• Achieve comparable or higher test accuracy $a'\geq a$,
• Use significantly fewer parameters, such that $\|m\|_{0}\ll |\theta |$ (meaning the subnetwork contains far fewer non-zero weights than the original network).

Identifying Winning Tickets

A winning ticket identified by training a network and pruning its smallest-magnitude weights. The remaining, unpruned connections form the architecture of the winning ticket. After pruning, each unpruned connection's value is reset to its original initialization before training. The process of identifying a winning ticket is as follows:

1. Randomly initialize a neural network $f(x;\theta _{0})$ where $\theta _{0}\sim D_{\theta }$.
2. Train the network for $j$ iterations, resulting in parameters $\theta _{j}$.
3. Prune $p\%$ of the parameters in $\theta _{j}$, creating a mask $m$.
4. Reset the remaining parameters to their initial values from $\theta _{0}$, creating the winning ticket $f(x;m\odot \theta _{0})$.

This pruning approach is called one-shot pruning: the network is trained once, $p\%$ of weights are pruned, and the surviving weights are reset to their initial values. However the authors primarily focus on iterative pruning, which repeats this process over $n$ rounds. In each round, ${\frac {p}{n}}\%$ of the weights that survived the previous round are pruned. Results show that iterative pruning finds winning tickets that achieve the same accuracy as the original network with a smaller number of parameters compared to one-shot pruning.

Authors

The Lottery Ticket Hypothesis was proposed by Jonathan Frankle and Michael Carbin in 2019. At the time, both authors were affiliated with the Massachusetts Institute of Technology (MIT), working in the field of computer science, specifically focussing on Machine Learning.

• Jonathan Frankle was a PhD student at MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) at the time of the paper's publication. His main line of research during his PhD was on the Lottery Ticket Hypothesis. Currently (Oct 2024) he works as a Chief Neural Network Scientist at Databricks, where he lead the Mosaic Research lab.
• Michael Carbin is currently an Associate Professor at MIT in the Electrical Engineering and Computer Science department. He leads the MIT Programming Systems Group.

Experimental Setup:

Types of Architectures:

The authors tested the Lottery Ticket Hypothesis on three types of neural network architectures:

1. Fully Connected Networks: These were used for experiments on the MNIST dataset. Specifically, the authors used the LeNet-300-100 architecture, a simple three-layer fully connected network with 300 units in the first hidden layer, 100 units in the second hidden layer, and 10 output units.
2. Convolutional Neural Network (CNNs): The authors also tested convolutional neural networks (CNNs) on the CIFAR-10 dataset. They used several variations of the VGG-style architecture, including networks with two, four, and six convolutional layers (referred to as Conv-2, Conv-4, and Conv-6). Additionally they study effects of dropout strategy.
3. Deeper Architectures: Additional experiments were performed on deeper networks such as ResNet-18 and VGG-19, which are commonly used in large-scale image recognition tasks.

Each architecture was trained using standard optimization techniques, such as stochastic gradient descent (SGD).

Pruning Strategies:

The pruning strategy involved unstructured pruning, where individual weights, rather than entire neurons or layers, were removed. The authors used a simple pruning heuristic where the weights with the smallest magnitudes (in terms of absolute value) were pruned first. This method allowed the authors to iteratively reduce the size of the network while maintaining its structure.

For some experiments, the authors compared the performance of winning tickets found through one-shot pruning versus iterative pruning:

• One-shot pruning: The network was pruned once by a large percentage (e.g., 50%), and then retrained from scratch.
• Iterative pruning: The network was pruned by a small percentage (e.g., 10-20%) at each stage, with the remaining weights reset to their initial values and retrained after each round.
• Global Pruning: For ResNet-18 and VGG-19, the networks are pruned globally instead of pruning each layer, removing the lowest-magnitude weights collectively across all convolutional layers.

Key Findings from Experiments

1. Winning tickets exist: In both fully connected and convolutional networks, they were able to find winning tickets that, when trained in isolation from their original initialization, matched or exceeded the performance of the full, unpruned network.
2. Winning tickets are much smaller: The pruned subnetworks (winning tickets) often contained less than 10-20% of the parameters of the original network, yet achieved similar test accuracy in a comparable number of training iterations.
3. Initialization matters: Winning tickets only performed well when their weights were reset to their original initialization. When the weights of the pruned network were randomly reinitialized, the network performed significantly worse, supporting the hypothesis that these winning tickets "won the initialization lottery."
4. Iterative pruning outperforms one-shot pruning: Iterative pruning consistently found smaller winning tickets that performed better than those found through one-shot pruning. This suggests that progressively reducing the size of the network helps in identifying the most critical weights and connections.

Implications

1. Improve training performance
2. Design better networks
3. Improve our theoretical understanding of neural networks

Historical context

Over-parameterization and Network Simplification

In modern neural networks, over-parameterization has become a common phenomenon. This means that networks often contain more parameters than are strictly necessary to learn the target function. Despite this excess capacity, neural networks still manage to find simpler functions during training, indicating that even over-parameterized networks can generalize well without memorizing the entire dataset.

Techniques for Reducing Network Complexity:

Distillation and Pruning:

• Distillation: Developed by Ba & Caruana (2014) and Hinton et al. (2015), distillation compresses large models into smaller ones by training a small network to mimic the behavior of a large, complex network. This reduces computational resources and makes deployment on devices easier.
• Pruning: Techniques like those introduced by LeCun et al. (1990) and later refined by Han et al. (2015), allow for the removal of unnecessary weights from a trained network, maintaining accuracy while significantly reducing the size of the model. This is particularly useful for reducing computational costs during inference