Pruning at Initialization -- A Sketching Perspective
Not on the map. Why?
Abstract (arXiv)
The lottery ticket hypothesis (LTH) has increased attention to pruning neural networks at initialization. We study this problem in the linear setting. We show that finding a sparse mask at initialization is equivalent to the sketching problem introduced for efficient matrix multiplication. This gives us tools to analyze the LTH problem and gain insights into it. Specifically, using the mask found at initialization, we bound the approximation error of the pruned linear model at the end of training. We theoretically justify previous empirical evidence that the search for sparse networks may be data independent. By using the sketching perspective, we suggest a generic improvement to existing algorithms for pruning at initialization, which we show to be beneficial in the data-independent case.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 67 of its 89 references that are in the map. First posted on arXiv 27 May 2023.
Builds on
67 of 89 references.
References · 67
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,267
- 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
- 2016Wide Residual Networkscited by 3,057
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,250
- 2015Learning both Weights and Connections for Efficient Neural Networkscited by 1,998
- 2018SNIP: Single-shot Network Pruning based on Connection Sensitivitycited by 802
- 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
- 2019Linear Mode Connectivity and the Lottery Ticket Hypothesiscited by 627
- 2017Learning Sparse Neural Networks through L0 Regularizationcited by 571
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
38 more
- 2019Rigging the Lottery: Making All Tickets Winnerscited by 491
- 2020Pruning neural networks without any data by iteratively conserving synaptic flowcited by 475
- 2020Picking Winning Tickets Before Training by Preserving Gradient Flowcited by 467
- 2017Robust Loss Functions under Label Noise for Deep Neural Networkscited by 441
- 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
- 2017Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Sciencecited by 325
- 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
- 2014Speeding up Convolutional Neural Networks with Low Rank Expansionscited by 283
- 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
- 2015Tensorizing Neural Networkscited by 246
- 2020Neural Architecture Search without Trainingcited by 241
- 2019What's Hidden in a Randomly Weighted Neural Network?cited by 236
- 2016Dynamic Network Surgery for Efficient DNNscited by 233
- 2020Proving the Lottery Ticket Hypothesis: Pruning is All You Needcited by 200
- 2021Zero-Cost Proxies for Lightweight NAScited by 194
- 2019Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterizationcited by 187
- 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 180
- 2019Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networkscited by 160
- 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
- 2017Deep Rewiring: Training very sparse deep networkscited by 136
- 2019One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizerscited by 102
- 2019A Signal Propagation Perspective for Pruning Neural Networks at Initializationcited by 96
- 2020The Lottery Tickets Hypothesis for Supervised and Self-supervised Pre-training in Computer Vision Modelscited by 91
- 2021How Powerful are Performance Predictors in Neural Architecture Search?cited by 88
- 2020Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficientcited by 81
- 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
- 2020A Unifying View on Implicit Bias in Training Linear Neural Networkscited by 74
- 2020Logarithmic Pruning is All You Needcited by 71
- 2021Only Train Once: A One-Shot Neural Network Training And Pruning Frameworkcited by 70
- 2017On Loss Functions for Deep Neural Networks in Classificationcited by 68
- 2020Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpotcited by 66
- 2020Progressive Skeletonization: Trimming more fat from a network at initializationcited by 64
- 2020An Overview of Neural Network Compressioncited by 59
- 2019The Generalization-Stability Tradeoff In Neural Network Pruningcited by 54
- 2022Revisiting Random Channel Pruning for Neural Network Compressioncited by 50
- 2021Efficient Lottery Ticket Finding: Less Data is Morecited by 44
- 2021When to Prune? A Policy towards Early Structural Pruningcited by 38
- 2022Prospect Pruning: Finding Trainable Weights at Initialization using Meta-Gradientscited by 34
50 most cited of 67 All 67 (JSON)
Built on by
Citing papers per year: 2024: 1; 2025: 0; 2026: 1.
2 papers.