# Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 52 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Builds on (most cited first, 13 of 13)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [High-Dimensional Linear Regression via Implicit Regularization](https://mlsanity.com/paper/1903.09367/) (2019)
- [Sparse Recovery via Differential Inclusions](https://mlsanity.com/paper/1406.7728/) (2014)
- [New Perspectives on k-Support and Cluster Norms](https://mlsanity.com/paper/1512.08204/) (2015)
- [Anderson acceleration of coordinate descent](https://mlsanity.com/paper/2011.10065/) (2020)
- [Don't relax: early stopping for convex regularization](https://mlsanity.com/paper/1707.05422/) (2017)
- [Fitting Spectral Decay with the k-Support Norm](https://mlsanity.com/paper/1601.00449/) (2016)
- [Generalized Dantzig Selector: Application to the k-support norm](https://mlsanity.com/paper/1406.5291/) (2014)

## Abstract (arXiv)

Sparse recovery is ubiquitous in machine learning and signal processing. Due to the NP-hard nature of sparse recovery, existing methods are known to suffer either from restrictive (or even unknown) applicability conditions, or high computational cost. Recently, iterative regularization methods have emerged as a promising fast approach because they can achieve sparse recovery in one pass through early stopping, rather than the tedious grid-search used in the traditional methods. However, most of those iterative methods are based on the ℓ1 norm which requires restrictive applicability conditions and could fail in many cases. Therefore, achieving sparse recovery with iterative regularization methods under a wider range of conditions has yet to be further explored. To address this issue, we propose a novel iterative regularization algorithm, IRKSN, based on the k-support norm regularizer rather than the ℓ1 norm. We provide conditions for sparse recovery with IRKSN, and compare them with traditional conditions for recovery with ℓ1 norm regularizers. Additionally, we give an early stopping bound on the model error of IRKSN with explicit constants, achieving the standard linear rate for sparse recovery. Finally, we illustrate the applicability of our algorithm on several experiments, including a support recovery experiment with a correlated design matrix.