Iterative magnitude pruning can be run on a small, pruning-aware critical (PrAC) subset of the training data rather than the full dataset, yet the resulting extremely sparse subnetworks sometimes generalize better than tickets found on all the data. The source work states this surprising regularization-like effect without explaining it and defers its investigation to future work. The open problem is to explain when and why data-level sparsity improves the generalization of the subnetworks discovered by the train-prune-retrain process at extreme sparsity.

Background

The lottery ticket hypothesis (LTH) observes that a dense, randomly initialized neural network contains a sparse subnetwork — a winning ticket — that, trained in isolation from a suitable early initialization, matches the full network's accuracy (Frankle and Carbin, arXiv:1803.03635). Winning tickets are typically found by iterative magnitude pruning (IMP): repeatedly train the network, remove the smallest-magnitude weights, and rewind to the initialization; each round is a train-prune-retrain cycle. The process is expensive because every cycle trains on the full dataset. A separate line of work on example forgetting (Toneva et al., arXiv:1812.05159) showed that training examples differ systematically in difficulty: some are learned late or never, and others are periodically forgotten when a correctly learned prediction later flips to incorrect. Zhang, Chen, Chen, and Wang (arXiv:2106.03225, ICML 2021) combined these observations: they construct a Pruning-Aware Critical (PrAC) set with two components — training examples that are hard to learn or easily forgotten, selected by forgetting statistics collected over a per-epoch budget TT with a forgetting threshold EF\mathcal{E}_\text{F}, together with, re-added at each pruning round, the examples on which the dense model and the current pruned subnetwork disagree — and run the entire ticket-finding process on this compact subset (35-78% of the training data on CIFAR-10, CIFAR-100, and Tiny ImageNet with ResNet and VGG networks). The found PrAC tickets match vanilla tickets at moderate sparsity. Surprisingly, at the highest sparsity levels (for example 96.48% on CIFAR-10), tickets found on the reduced dataset can outperform those found on the full dataset, as if discarding easy, non-critical examples regularizes the pruning search; the authors explicitly leave this regularization-like effect for future work. Existing theory does not cover this phenomenon: analyses of pruning at initialization in linear models via a sketching equivalence (Bar and Giryes, arXiv:2305.17559) even suggest that sparse-mask search can be data-independent, which sharpens but does not explain the observed interaction between data selection and ticket quality at extreme sparsity. Follow-up work by the same group extends the sparsity-plus-data-efficiency recipe to new settings — data-efficient GAN training with lottery tickets (Chen, Cheng, Gan, Liu, and Wang, arXiv:2103.00397) and sparse adversarial training with better robust generalization (Chen, Zhang, Wang, Balachandra, Ma, Wang, and Wang, arXiv:2202.09844) — and a 2024 survey (Liu et al., arXiv:2403.04861) still lists the efficiency and scope of ticket finding among open issues, but none of these explains the mechanism.

Problem Statement

Explain the mechanism by which training on a pruning-aware critical (PrAC) subset of the data — rather than the full training set — can improve the generalization of the extremely sparse subnetworks that iterative magnitude pruning discovers. Concretely, with explicitly stated assumptions: derive conditions on the data-selection rule (both the forgetting/hard-example statistics and the per-round re-addition of examples where the dense and pruned models disagree), the pruning schedule, and the sparsity level under which the train-prune-retrain process run on the reduced dataset yields subnetworks generalizing better than those found on the full dataset, and predict the regime pattern observed in the source work (parity at moderate sparsity, and outperformance at the very high sparsity levels — for example the 96.48% sparsity of the source's headline comparison, within a published sweep spanning 0% to 99.85%, where PrAC tickets beat vanilla tickets on CIFAR-10 and CIFAR-100 with ResNets). The exact reported sparsity values need not be reproduced; the relevant regime pattern is qualitative.

References

  1. Zhang, Zhenyu; Chen, Xuxi; Chen, Tianlong; Wang, Zhangyang (2021). Efficient Lottery Ticket Finding: Less Data is More. arXiv:2106.03225, DOI 10.48550/arXiv.2106.03225, https://arxiv.org/abs/2106.03225
  2. Frankle, Jonathan; Carbin, Michael (2018). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. arXiv:1803.03635, DOI 10.48550/arXiv.1803.03635, https://arxiv.org/abs/1803.03635
  3. Toneva, Mariya; Sordoni, Alessandro; Tachet des Combes, Remi; Trischler, Adam; Bengio, Yoshua; Gordon, Geoffrey J. (2018). An Empirical Study of Example Forgetting during Deep Neural Network Learning. arXiv:1812.05159, DOI 10.48550/arXiv.1812.05159, https://arxiv.org/abs/1812.05159
  4. Chen, Tianlong; Cheng, Yu; Gan, Zhe; Liu, Jingjing; Wang, Zhangyang (2021). Data-Efficient GAN Training Beyond (Just) Augmentations: A Lottery Ticket Perspective. arXiv:2103.00397, DOI 10.48550/arXiv.2103.00397, https://arxiv.org/abs/2103.00397
  5. Chen, Tianlong; Zhang, Zhenyu; Wang, Pengjun; Balachandra, Santosh; Ma, Haoyu; Wang, Zehao; Wang, Zhangyang (2022). Sparsity Winning Twice: Better Robust Generalization from More Efficient Training. arXiv:2202.09844, DOI 10.48550/arXiv.2202.09844, https://arxiv.org/abs/2202.09844
  6. Bar, Noga; Giryes, Raja (2023). Pruning at Initialization - A Sketching Perspective. arXiv:2305.17559, DOI 10.48550/arXiv.2305.17559, https://arxiv.org/abs/2305.17559
  7. Liu, Bohan; Zhang, Zijie; He, Peixiong; Wang, Zhensen; Xiao, Yang; Ye, Ruimeng; Zhou, Yang; Ku, Wei-Shinn; Hui, Bo (2024). A Survey of Lottery Ticket Hypothesis. arXiv:2403.04861, DOI 10.48550/arXiv.2403.04861, https://arxiv.org/abs/2403.04861