PaperlayerView exact revision on arXiv

Source-linked AI summary

Winning the Lottery with Continuous Sparsification

Pedro Savarese, Hugo Silva, Michael Maire

arXiv:1912.04427v4cs.LGstat.ML

TL;DR

Sparse neural networks are commonly obtained by pruning overparameterized models, but heuristic pruning and costly ticket search leave open whether ℓ0-based optimization can find competitive sparse networks. The paper introduces Continuous Sparsification, a deterministic smooth approximation to ℓ0 regularization, and reports stronger pruning and ticket-search results across models and datasets. It also identifies efficient parallel ticket search as a practical consequence, while noting that predefined sparsity levels may require multiple runs.

  • Problem

    Heuristic pruning dominates sparse-network search, while prior ℓ0 approximations have struggled to compete and IMP ticket search requires repeated training and pruning.

  • Method

    Continuous Sparsification uses a deterministic smooth continuation from sigmoid soft gates to binary masks to approximate the intractable ℓ0-regularized objective.

  • Results

    Continuous Sparsification outperforms competing pruning methods and finds retrainable subnetworks that outperform IMP across VGG, ResNet-20, and ResNet-50 experiments.

  • Takeaways & Limitations

    The method provides a practical pruning approach and a parallelizable ticket-search framework whose search cost does not depend on the produced subnetwork’s sparsity.

  • Takeaways & Limitations

    Producing a subnetwork at a predefined sparsity level can require multiple runs with different hyperparameter settings.

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether sparse networks can achieve competitive performance without heuristic pruning and whether ℓ0-based methods can find trainable winning tickets. It introduces Continuous Sparsification, a deterministic ℓ0 approximation that improves pruning and ticket search.

  • Extreme overparameterization improves state-of-the-art performance but increases training costs and restricts memory- or inference-limited applications.
  • Prior ℓ0-approximation methods were few and failed to compete with heuristic-based pruning methods.
  • IMP finds winning tickets but requires repeated training and pruning rounds, making effective ticket search costly.
  • Continuous Sparsification deterministically approximates the intractable ℓ0 penalty and finds networks that perform competitively when fine-tuned or retrained.
  • Experiments show Continuous Sparsification outperforms heuristic pruning methods and finds retrainable subnetworks that outperform IMP tickets across VGG, ResNet-20, and ResNet-50.

2 Preliminaries

The preliminaries define subnetworks through binary masks and distinguish matching subnetworks, winning tickets, and ticket search by their initialization and training requirements.

  • A subnetwork applies a binary mask to parameters, retaining weights where the mask equals one and removing the rest.
  • A subnetwork has as many effective parameters as the mask’s ℓ0 norm, rather than the dense network’s full parameter count.
  • A matching subnetwork can be trained in isolation from an early trained iterate and must match the dense model under the same iteration budget.
  • A winning ticket is a matching subnetwork trained in isolation from the original initialization, corresponding to k = 0.
  • Ticket search finds a mask that induces a matching or potentially matching subnetwork for a given network and initialization.

3 Related Work

Related work contrasts heuristic pruning, which ranks weights using predefined statistics, with ℓ0 approximations and Lottery Ticket methods for discovering sparse trainable subnetworks.

  • Classical pruning ranks parameters using predefined statistics such as weight magnitude, usually after dense training.
  • ℓ0-based methods formulate sparsity through optimization, but stochastic mask approximations require gradient estimates that can be biased or high variance.
  • The Lottery Ticket Hypothesis proposes that sparse subnetworks can match dense-model performance when trained from suitable initial parameters.
  • IMP searches for winning tickets through repeated training, pruning, and rewinding, producing subnetworks at increasing sparsity levels.
  • Winning tickets have been associated with faster training, better final performance, and transfer across datasets and training methods in small-scale settings.

4 Method

Continuous Sparsification replaces discrete or stochastic pruning with deterministic soft masks whose hardness increases during optimization, converging toward binary subnetworks. The method supports pruning and ticket search while avoiding stochastic gradient estimators and training–inference mask gaps.

  • Continuous Sparsification optimizes a loss plus an ℓ1 penalty on sigmoid-gated parameters while increasing the inverse temperature β.
  • The underlying ℓ0 objective trades network loss against the number of retained parameters, while λ controls that trade-off.
  • A fully deterministic re-parameterization avoids the biased or noisy gradient estimators used by prior stochastic ℓ0 approximations.
  • The method approximates the binary Heaviside mask by σ(βs), interpolating from smooth soft gating at β = 1 toward discrete masking as β approaches infinity.
  • Negative mask variables drive corresponding weights toward zero, and the final Heaviside output guarantees a binary mask.
  • For ticket search, the method resets β between rounds and does not rewind weights between rounds, unlike IMP.
  • Continuous Sparsification produces consistent outputs across training passes and avoids a training–inference gap associated with stochastic masks.

5 Experiments

Experiments evaluate Continuous Sparsification (CS) for ticket search and one-shot pruning against IMP and other baselines on CIFAR-10 models. CS finds highly sparse, high-performing subnetworks and is especially efficient for parallel ticket search, while its sequential search and sparsity control remain constrained.

  • Ticket Search: CS finds subnetworks with diverse sparsity levels after 5 rounds, while IMP produces higher-performing tickets without weight rewinding.The ticket-search budget for CS is 5 × 85 = 425 epochs.
  • Ticket Search: CS produces sparser matching subnetworks with higher accuracy than IMP and IMP-C, and its best subnetworks outperform the original model by approximately 1% on VGG-16 and ResNet-20.IMP-C denotes IMP without rewinding between rounds.
  • Ticket Search: Parallel production of all displayed tickets takes CS 425 training epochs versus 2550 for IMP.CS is faster with sufficient parallelism, but sequential production takes 4675 epochs because each of 11 settings is run separately.
  • Pruning: The standard hard-concrete inference behavior performs nearly like random guessing above 90% sparsity, whereas selecting the best sampled mask improves high-sparsity results but remains weaker than alternatives.The comparison highlights a training–inference gap in stochastic ℓ0 approaches.
  • Pruning: For one-shot pruning, CS removes more parameters than competing methods while maintaining performance within 2% of the dense model on VGG-16 and ResNet-20.On ResNet-20, the CS network contains 60% fewer prunable parameters than the GMP network.
  • Pruning: CS and Slim prune over 98% of VGG weights without severe degradation, while CS and GMP achieve the strongest results on ResNet-20.CS provides state-of-the-art pruning results, including at high sparsity.
  • ImageNet: On ImageNet-scale ticket search, CS subnetworks outperform IMP after retraining, while methodological differences in schedules and epochs complicate direct comparisons.The reported comparison includes retrained CS† and IMP† subnetworks.

6 Discussion

The paper reframes winning-ticket search as an ℓ0-regularized optimization problem and introduces Continuous Sparsification, which deterministically and continuously removes parameters during training. It reports improved ticket-search and pruning results, including extreme VGG sparsification and faster parallel search.

  • Continuous Sparsification approximates ℓ0 regularization through a smooth relaxation of the step function.
  • The method deterministically removes parameters continuously during training within a unified optimization framework.
  • Continuous Sparsification improves ticket search and resulting sparsity, including extreme sparsification of VGG and efficient parallel search.
  • As a pruning method, Continuous Sparsification outperforms modern competitors on produced-subnetwork accuracy and sparsity.

A.1 Continuous Sparsification

The hyperparameter study examines how λ, β(T), and s(0) affect ticket accuracy and sparsity. Initial mask value chiefly controls sparsity, while temperature affects accuracy and sparsity conditionally; larger temperatures also cause earlier mask-gradient vanishing.

  • The study varies one of λ, β(T), and s(0) at a time while repeating experiments under different fixed settings.
  • λ has little effect on ticket accuracy or sparsity, except that λ = 10^-8 slightly increases sparsity in one setting.
  • β(T) = 200 yields better accuracy in all tested settings, but its sparsity effect depends on the fixed values of s(0) and λ.
  • Larger β(T) causes mask gradients to vanish earlier, stopping mask training; values around 150 or 200 are recommended.
  • s(0) strongly and consistently affects ticket sparsity, with smaller values promoting greater sparsity and lower performance.
  • IMP ticket performance decays when the pruning rate reaches 40%, with performance generally decreasing as fewer parameters remain.

B Iterative Stochastic Sparsification

Iterative Stochastic Sparsification (ISS) trains weights and stochastic mask parameters jointly, using a Bernoulli re-parameterization and straight-through gradients. Its iterative procedure permanently removes components whose mask parameters fall below their initialization, but successful mask training requires specialized optimization settings.

  • Iterative procedure: ISS initializes mask parameters with s(0), optimizes a loss plus an ℓ1 penalty for T iterations, and repeats this process across pruning rounds.At the end of the final round it samples a binary mask and outputs the masked rewound weights.
  • Method: ISS jointly trains network weights and stochastic Bernoulli mask parameters with gradient descent and a straight-through estimator.The method serves as a baseline for testing whether Continuous Sparsification’s deterministic re-parameterization improves optimization.
  • Iterative procedure: Components whose mask parameters decrease from initialization are permanently removed by setting their parameters to −∞ in later rounds.Without this step, ISS removed weights too slowly unless the regularization penalty was increased enough to reduce model performance.
  • Optimization: Mask parameters require substantially different optimization settings from CNN weights: learning rates near 0.1 barely update them, whereas prior work used a learning rate of 100.The authors attribute this difficulty likely to gradient estimators used to obtain update directions for the mask parameters.

C Supermask Search on a 6-layer CNN

The supermask experiment evaluates sparse binary masks on a randomly initialized 6-layer CIFAR-10 CNN with frozen weights. Continuous Sparsification finds substantially stronger and faster-learning sparse masks than Stochastic Sparsification, and its deterministic re-parameterization also yields better winning tickets than ISS.

  • Supermask setup: The experiment searches for binary supermasks on a 6-layer CIFAR-10 CNN while keeping randomly initialized weights fixed.Because the weights are neither updated during mask search nor comparison, the task is equivalent to pruning a randomly initialized network.
  • Supermask results: Stochastic Sparsification fails to find competitive supermasks above 50% sparsity.The comparison uses one 100-epoch round, with ISS equivalent to the cited stochastic supermask algorithm in this setting.
  • Supermask results: Continuous Sparsification finds supermasks with 25% or fewer remaining weights while achieving 75% test accuracy.This result is reported from the Figure 7 comparison of CS and SS.
  • Optimization: Continuous Sparsification learns masks significantly faster than Stochastic Sparsification while reaching similar early-stop performance.The authors connect the faster progress to avoiding gradient estimators during optimization.
  • Ticket search: With weight rewinding, Continuous Sparsification produces winning tickets superior to ISS in both sparsity and test accuracy.This comparison indicates that the deterministic re-parameterization is important for the ticket-search results.

E Additional Plots for Ticket Search Experiments

Additional ResNet-20 ticket-search plots compare Continuous Sparsification with Iterative Magnitude Pruning after retraining from epoch-2 weights. CS automatically determines per-round pruning and produces superior tickets even when IMP matches its changing pruning rate.

  • Experimental setup: The ResNet-20 ticket experiments retrain tickets from epoch-2 weights across 11 Continuous Sparsification mask initializations and five rounds.Each CS setting is paired with an IMP run using the same per-round pruning rate.
  • Continuous search: Continuous Sparsification automatically adjusts the pruning ratio at each round while selecting parameters that yield better tickets.The plots report this advantage across the different mask-initialization settings.
  • Comparison with IMP: Continuous Sparsification produces superior tickets even when IMP adopts a dynamic pruning ratio matched to CS at every round.Thus, the comparison controls for the pruning-rate schedule rather than attributing the difference only to a fixed schedule.
  • Comparison with IMP: The plotted comparisons include CS and IMP variants, including continued IMP without weight rewinding between rounds.The figure captions identify purple CS curves and blue IMP or continued-IMP curves.

F Sequential Search with Continuous Sparsification

Standard Continuous Sparsification lacks explicit control over ticket sparsity, which can favor IMP when predefined or varied sparsity levels are needed. Sequential Continuous Sparsification addresses this by removing a fixed fraction per round, but its ticket performance remains inferior to non-sequential CS in the reported ResNet-20 experiment.

  • Limitation of standard CS: Continuous Sparsification quickly sparsifies the network in early rounds and then roughly maintains its parameter count.Because it lacks an explicit sparsity-control mechanism, it is less suited to producing tickets at specified or varying sparsity levels in one run.
  • Limitation of standard CS: Iterative Magnitude Pruning has an advantage when one run must produce tickets with varying, predefined sparsity levels.A single IMP run can generate tickets across those target sparsities.
  • Sequential variant: Sequential Continuous Sparsification removes a fixed fraction of weights each round, making it better suited to controlled sequential ticket search.Unlike standard CS, it removes weights with the lowest mask values rather than all weights with negative mask parameters.
  • Results: In the reported ResNet-20 experiment, Sequential CS may compete with IMP, but its tickets are considerably worse than those found by standard CS.The experiment used 30 rounds and a 20% pruning rate per round, with one run at s(0) = 0.

G Learned Sparsity Structure

Continuous Sparsification and IMP are compared at the same overall sparsity to reveal how each method distributes pruning across VGG-16 layers. CS prunes earlier blocks more aggressively, while both methods strongly sparsify the widest layers and retain over 91% test accuracy.

  • Comparison setup: CS and IMP are compared on VGG-16 at the same 94.19% sparsity, isolating differences in layer-wise pruning allocation.CS is run with s(0) = 0, and IMP uses a global pruning rate of 94.19%, producing subnetworks with equal parameter counts.
  • Block structure: The comparison divides VGG’s 16 convolutional layers into 8 blocks of two consecutive layers.Figure 12 reports the final sparsity for each two-layer block.
  • Layer-wise pattern: CS prunes the first VGG blocks at roughly twice the rate used by IMP.The methods therefore produce different layer-wise sparsity patterns despite matching overall sparsity.
  • Layer-wise pattern: Both methods heavily sparsify VGG’s widest layers, corresponding to blocks 5 to 8, while achieving over 91% test accuracy.Earlier layers can have greater inference-speed impact because their weights are reused more times and contribute more FLOPs.
Loading 1912.04427v4…