# Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing

arXiv: https://arxiv.org/abs/2303.11453 · HTML: https://mlsanity.com/paper/2303.11453/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 73 references that are in the map.
- First posted on arXiv 20 Mar 2023.

## Builds on (most cited first, 30 of 45)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned](https://mlsanity.com/paper/1905.09418/) (2019)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [Learning Efficient Convolutional Networks through Network Slimming](https://mlsanity.com/paper/1708.06519/) (2017)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Quantizing deep convolutional networks for efficient inference: A whitepaper](https://mlsanity.com/paper/1806.08342/) (2018)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Soft Filter Pruning for Accelerating Deep Convolutional Neural Networks](https://mlsanity.com/paper/1808.06866/) (2018)
- [Model compression via distillation and quantization](https://mlsanity.com/paper/1802.05668/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [NISP: Pruning Networks using Neuron Importance Score Propagation](https://mlsanity.com/paper/1711.05908/) (2017)
- [Structured Pruning of Large Language Models](https://mlsanity.com/paper/1910.04732/) (2019)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Rethinking the Smaller-Norm-Less-Informative Assumption in Channel Pruning of Convolution Layers](https://mlsanity.com/paper/1802.00124/) (2018)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Group Sparse Regularization for Deep Neural Networks](https://mlsanity.com/paper/1607.00485/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Fast ConvNets Using Group-wise Brain Damage](https://mlsanity.com/paper/1506.02515/) (2015)

## Built on by (most cited first, 1 of 1)

- [Enhanced Structured Lasso Pruning with Class-wise Information](https://mlsanity.com/paper/2502.09125/) (2025)

## Abstract (arXiv)

Pruning schemes have been widely used in practice to reduce the complexity of trained models with a massive number of parameters. In fact, several practical studies have shown that if a pruned model is fine-tuned with some gradient-based updates it generalizes well to new samples. Although the above pipeline, which we refer to as pruning + fine-tuning, has been extremely successful in lowering the complexity of trained models, there is very little known about the theory behind this success. In this paper, we address this issue by investigating the pruning + fine-tuning framework on the overparameterized matrix sensing problem with the ground truth U_star ∈ ℝd × r and the overparameterized model U ∈ ℝd × k with k gg r. We study the approximate local minima of the mean square error, augmented with a smooth version of a group Lasso regularizer, sumi=1k | U ei |2. In particular, we provably show that pruning all the columns below a certain explicit ℓ2-norm threshold results in a solution Uprune which has the minimum number of columns r, yet close to the ground truth in training loss. Moreover, in the subsequent fine-tuning phase, gradient descent initialized at Uprune converges at a linear rate to its limit. While our analysis provides insights into the role of regularization in pruning, we also show that running gradient descent in the absence of regularization results in models which are not suitable for greedy pruning, i.e., many columns could have their ℓ2 norm comparable to that of the maximum. To the best of our knowledge, our results provide the first rigorous insights on why greedy pruning + fine-tuning leads to smaller models which also generalize well.