Winning the Lottery with Continuous Sparsification

Pedro Savarese, Hugo Silva, Michael Maire

Deep neural networks are notoriously overparameterized, leading to massive memory and computational costs. While the Lottery Ticket Hypothesis conjectures that much smaller "subnetworks" can match the performance of the full model when trained from scratch, finding these winning tickets is notoriously difficult.

Existing methods generally fall into two camps: heuristic-based pruning (like Iterative Magnitude Pruning, or IMP), which is effective but computationally expensive, and stochastic $\ell_0$ approximations, which attempt to optimize for sparsity directly but rely on noisy gradient estimators that often underperform simple heuristics.

This paper introduces Continuous Sparsification (CS), a deterministic optimization framework that approximates intractable $\ell_0$ regularization to find highly sparse neural networks. By smoothly transitioning from soft-gating to hard binary masks during training, CS outperforms state-of-the-art pruning heuristics and offers a faster, more effective way to find winning tickets.

The Continuous Sparsification Method

Instead of using a fixed heuristic or a random mask, CS learns a mask $m$ alongside the network weights $w$. The authors frame pruning as a loss minimization problem: $\min L(w, m) + \lambda \|m\|_1$, where $m$ is a binary mask.

To make the discrete mask $m \in \{0, 1\}$ differentiable, they represent it as a function of a learnable parameter $s$: $m = H(s)$, where $H$ is the Heaviside step function. Because the step function has zero gradients almost everywhere, CS approximates it using a sigmoid function: $\sigma(\beta s)$.

During training, the method employs Temperature Annealing. It starts with $\beta=1$ (a smooth sigmoid) and exponentially increases $\beta$. As $\beta \to \infty$, the sigmoid converges to the true step function. This "continuation method" allows the optimizer to slowly commit to which weights to keep and which to discard.

Furthermore, unlike IMP, which is inherently sequential and requires multiple rounds of training and rewinding, CS can be run in parallel with different initializations or penalty strengths ($\lambda$). This makes the search for winning tickets significantly faster in a multi-GPU environment.

Key Insights

  • Deterministic over Stochastic: The high variance and bias in previous stochastic $\ell_0$ methods often hindered performance. By remaining deterministic, CS provides stable gradients that allow the optimizer to find superior sparse structures.
  • Sparsity as Optimization: CS demonstrates that we do not need to rely on weight "magnitude" as a proxy for importance. The network can learn which parameters are redundant directly through regularized empirical risk minimization.
  • Parallel Efficiency: Because CS finds a sparse subnetwork in a single (or very few) training runs, it is much more parallel-friendly than IMP.

Empirical Results

The authors evaluated CS on standard computer vision benchmarks, including CIFAR-10 (VGG-16 and ResNet-20) and ImageNet (ResNet-50).

Pruning Performance

CS consistently outperforms existing pruning methods across various sparsity levels.

Pruning performance of CS compared to baselines on VGG-16 and ResNet-20 (CIFAR-10).
  • VGG-16 on CIFAR-10: CS found a subnetwork with only 1.7% of the original weights that matched the dense model's accuracy. At its best-performing level, it actually beat the dense model's accuracy while using only 2.4% of the parameters.
  • ResNet-20 on CIFAR-10: CS achieved 94.4% sparsity while staying within 2% of the original accuracy, significantly higher than the 86% achieved by the next best method (GMP).
  • ResNet-50 on ImageNet: CS reached 70% Top-1 accuracy at 98% sparsity. In the high-sparsity regime (95%+), CS consistently outperformed IMP and other state-of-the-art pruning methods like STR and DNW.

CS doesn't just find sparse models; it finds better sparse models that can be successfully re-trained from early iterates.

Ticket search performance showing CS outperforming Iterative Magnitude Pruning at high sparsity.

The subnetworks found by CS often outperform those found by the gold-standard IMP, especially at extreme sparsity levels where IMP's performance begins to degrade sharply. While CS adds about 10% wall-clock overhead per epoch due to the extra mask parameters, its ability to find tickets in fewer rounds makes it faster overall than iterative methods when parallel resources are available.

Limitations and Future Work

While highly effective, CS has a few limitations. The sparsity of the final model is sensitive to the initial values of the mask parameters and the penalty $\lambda$, meaning targeting an exact sparsity percentage may require trial runs. Additionally, storing the mask parameters during training effectively doubles the parameter count (though not the activations) during the search phase.

Currently, the method focuses on unstructured pruning (removing individual weights). Extending Continuous Sparsification to structured pruning—removing entire filters or channels—remains a highly promising direction for future hardware-accelerated inference.

Summary updated

Abstract

The search for efficient, sparse deep neural network models is most prominently performed by pruning: training a dense, overparameterized network and removing parameters, usually via following a manually-crafted heuristic. Additionally, the recent Lottery Ticket Hypothesis conjectures that, for a typically-sized neural network, it is possible to find small sub-networks which, when trained from scratch on a comparable budget, match the performance of the original dense counterpart. We revisit fundamental aspects of pruning algorithms, pointing out missing ingredients in previous approaches, and develop a method, Continuous Sparsification, which searches for sparse networks based on a novel approximation of an intractable $\ell_0$ regularization. We compare against dominant heuristic-based methods on pruning as well as ticket search -- finding sparse subnetworks that can be successfully re-trained from an early iterate. Empirical results show that we surpass the state-of-the-art for both objectives, across models and datasets, including VGG trained on CIFAR-10 and ResNet-50 trained on ImageNet. In addition to setting a new standard for pruning, Continuous Sparsification also offers fast parallel ticket search, opening doors to new applications of the Lottery Ticket Hypothesis.
BibTeX
@inproceedings{savarese2020winning,
  author = {Pedro Savarese and Hugo Silva and Michael Maire},
  title = {{Winning the Lottery with Continuous Sparsification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=VCyborV1rDL},
}
Figure