TL;DR
This paper extends the "Strong Lottery Ticket Hypothesis" by introducing $\epsilon$-perturbation to the initial weights of a neural network. This allows for a reduction in the over-parameterization required to find a sparse subnetwork that approximates a target network, and experimentally shows that Projected Gradient Descent (PGD) can find effective perturbations.
What Problem Does This Paper Address?
The Lottery Ticket Hypothesis (LTH) suggests that dense neural networks contain smaller subnetworks (winning tickets) that, when trained in isolation, can achieve performance comparable to the original dense network. The "Strong LTH" takes this further, proposing that a sufficiently over-parameterized, randomly initialized network can contain a subnetwork that approximates a target network without any training. However, the original Strong LTH requires significant over-parameterization. This paper asks: can we reduce this over-parameterization requirement by allowing a small perturbation ($\epsilon$) to the initial random weights? Furthermore, does the weight change achieved through standard training methods like SGD naturally lead to such beneficial perturbations?
Methods
The core of this work lies in extending the theoretical framework of the Strong LTH.
- Theoretical Extension of Subset Sum: The authors first generalize the subset sum problem, which is a key theoretical tool for proving the Strong LTH. They introduce an $\epsilon$-perturbation to the candidate values in the subset sum problem. This theoretical extension shows that as the perturbation scale $\epsilon$ increases, the required number of candidates (analogous to over-parameterization) decreases.
- Applying to Neural Networks: This theoretical result is then applied to neural networks. The authors prove that by allowing $\epsilon$-scale perturbation on the initial weights of a candidate network, the over-parameterization requirement for approximating a target network can be reduced by a factor of $O(1/(1 + \epsilon))$.
- Empirical Validation with Projected Gradient Descent (PGD): To address the second question about whether SGD-like methods find good perturbations, the authors propose a two-stage algorithm. First, they train an over-parameterized network using PGD, ensuring that the weights stay within an $\epsilon$-neighborhood of their initialization. Second, they apply a standard pruning technique (edge-popup) to this perturbed network. This allows them to investigate the relationship between the perturbation scale $\epsilon$ and the resulting accuracy.
Datasets
The paper mentions using the MNIST dataset for their experiments. They train a four-layer MLP with 500 hidden nodes per layer.
Key Insights and Ideas
- Perturbation as a Regularizer/Optimizer: The paper frames $\epsilon$-perturbation not just as a way to reduce over-parameterization, but also as a mechanism that can guide weight initialization towards better pruning performance.
- SGD's Role in Finding Good Perturbations: The experimental results suggest that SGD, when constrained by an $\epsilon$-neighborhood, can indeed find perturbations that lead to better pruned network performance compared to random perturbations. This implies that the training process, even in its early stages, can be beneficial for identifying winning tickets.
- Trade-off between Perturbation and Sparsity: The experiments reveal an interesting trade-off: as the perturbation scale $\epsilon$ increases, the optimal sparsity level (i.e., the percentage of weights to prune) tends to decrease to achieve the best accuracy. This suggests that larger perturbations might lead to more interconnected weights, making aggressive pruning detrimental.
Key Results
- Theoretical Reduction in Over-parameterization: The authors provide a theoretical guarantee that allowing $\epsilon$-perturbation reduces the over-parameterization requirement for the Strong LTH by a factor of $O(1/(1 + \epsilon))$.
- Empirical Performance Improvement: Experiments on MNIST show that as the perturbation scale $\epsilon$ increases, the best achievable accuracy of the pruned network also increases. For instance, with $\epsilon = 0.3$, they achieve accuracies close to 0.98, whereas with $\epsilon = 0$, the best accuracy is around 0.82.
- SGD-based Perturbations are Effective: The study indicates that perturbations derived from PGD lead to better pruned network performance than random perturbations.
Limitations and Future Work
- Theoretical Focus on Approximation: The theoretical results primarily focus on approximating a target network's function, rather than achieving optimal training performance on a specific task.
- Empirical Exploration of SGD: While experiments suggest SGD finds good perturbations, a deeper theoretical understanding of why SGD's $\epsilon$-bounded updates are beneficial for pruning is still an open question. The authors suggest this as a future research direction.
- Generalization to Other Architectures/Tasks: The current work focuses on MLPs and the MNIST dataset. Future work could explore these concepts with convolutional neural networks, recurrent neural networks, and more complex tasks.
Summary updated