# Performance of ℓ1 Regularization for Sparse Convex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 46 of its 103 references that are in the map.
- First posted on arXiv 14 Jul 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [TabNet: Attentive Interpretable Tabular Learning](https://mlsanity.com/paper/1908.07442/) (2019)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [The Unsurprising Effectiveness of Pre-Trained Vision Models for Control](https://mlsanity.com/paper/2203.03580/) (2022)
- [Group Sparse Regularization for Deep Neural Networks](https://mlsanity.com/paper/1607.00485/) (2016)
- [Fast ConvNets Using Group-wise Brain Damage](https://mlsanity.com/paper/1506.02515/) (2015)
- [Learning the Number of Neurons in Deep Networks](https://mlsanity.com/paper/1611.06321/) (2016)
- [SBNet: Sparse Blocks Network for Fast Inference](https://mlsanity.com/paper/1801.02108/) (2018)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Block-Sparse Recurrent Neural Networks](https://mlsanity.com/paper/1711.02782/) (2017)
- [Neural Programmer: Inducing Latent Programs with Gradient Descent](https://mlsanity.com/paper/1511.04834/) (2015)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measures](https://mlsanity.com/paper/2105.08368/) (2021)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Towards a Zero-One Law for Column Subset Selection](https://mlsanity.com/paper/1811.01442/) (2018)
- [Average Case Column Subset Selection for Entrywise ℓ1-Norm Loss](https://mlsanity.com/paper/2004.07986/) (2020)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [A General Framework for Fast Stagewise Algorithms](https://mlsanity.com/paper/1408.5801/) (2014)
- [Feature Selection Using Batch-Wise Attenuation and Feature Mask Normalization](https://mlsanity.com/paper/2010.13631/) (2020)

## Abstract (arXiv)

Despite widespread adoption in practice, guarantees for the LASSO and Group LASSO are strikingly lacking in settings beyond statistical problems, and these algorithms are usually considered to be a heuristic in the context of sparse convex optimization on deterministic inputs. We give the first recovery guarantees for the Group LASSO for sparse convex optimization with vector-valued features. We show that if a sufficiently large Group LASSO regularization is applied when minimizing a strictly convex function l, then the minimizer is a sparse vector supported on vector-valued features with the largest ℓ2 norm of the gradient. Thus, repeating this procedure selects the same set of features as the Orthogonal Matching Pursuit algorithm, which admits recovery guarantees for any function l with restricted strong convexity and smoothness via weak submodularity arguments. This answers open questions of Tibshirani et al. and Yasuda et al. Our result is the first to theoretically explain the empirical success of the Group LASSO for convex functions under general input instances assuming only restricted strong convexity and smoothness. Our result also generalizes provable guarantees for the Sequential Attention algorithm, which is a feature selection algorithm inspired by the attention mechanism proposed by Yasuda et al. As an application of our result, we give new results for the column subset selection problem, which is well-studied when the loss is the Frobenius norm or other entrywise matrix losses. We give the first result for general loss functions for this problem that requires only restricted strong convexity and smoothness.