# Sparse Convex Optimization via Adaptively Regularized Hard Thresholding

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2020.

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

- [AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks](https://mlsanity.com/paper/2106.12379/) (2021)
- [Accurate Neural Network Pruning Requires Rethinking Sparse Optimization](https://mlsanity.com/paper/2308.02060/) (2023)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [Gradient Descent Converges Linearly for Logistic Regression on Separable Data](https://mlsanity.com/paper/2306.14381/) (2023)
- [Local Search Algorithms for Rank-Constrained Convex Optimization](https://mlsanity.com/paper/2101.06262/) (2021)
- [Straight-Through meets Sparse Recovery: the Support Exploration Algorithm](https://mlsanity.com/paper/2301.13584/) (2023)
- [The Condition-Number Barrier in Sparse Least Squares](https://mlsanity.com/paper/2608.02588/) (2026)
- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization](https://mlsanity.com/paper/2402.17902/) (2024)

## Abstract (arXiv)

The goal of Sparse Convex Optimization is to optimize a convex function f under a sparsity constraint s≤ s^*γ, where s^* is the target number of non-zero entries in a feasible solution (sparsity) and γ≥ 1 is an approximation factor. There has been a lot of work to analyze the sparsity guarantees of various algorithms (LASSO, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT)) in terms of the Restricted Condition Number kappa. The best known algorithms guarantee to find an approximate solution of value f(x^*)+ε with the sparsity bound of γ = Oleft(kappaminleftlog fracf(x0)-f(x^*)ε, kapparightright), where x^* is the target solution. We present a new Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes significant progress on this problem by bringing the bound down to γ=O(kappa), which has been shown to be tight for a general class of algorithms including LASSO, OMP, and IHT. This is achieved without significant sacrifice in the runtime efficiency compared to the fastest known algorithms. We also provide a new analysis of OMP with Replacement (OMPR) for general f, under the condition s > s^* frackappa24, which yields Compressed Sensing bounds under the Restricted Isometry Property (RIP). When compared to other Compressed Sensing approaches, it has the advantage of providing a strong tradeoff between the RIP condition and the solution sparsity, while working for any general function f that meets the RIP condition.