# Online Generalized Sparse Regression: How Does Overparametrization Help?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 18 Aug 2026.

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

- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Between hard and soft thresholding: optimal iterative thresholding algorithms](https://mlsanity.com/paper/1804.08841/) (2018)
- [Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP](https://mlsanity.com/paper/1706.04690/) (2017)
- [Inference on High-dimensional Single-index Models with Streaming Data](https://mlsanity.com/paper/2210.00937/) (2022)
- [The Statistics of Streaming Sparse Regression](https://mlsanity.com/paper/1412.4182/) (2014)
- [Online Linearized LASSO](https://mlsanity.com/paper/2211.06039/) (2022)

## Abstract (arXiv)

Regularized sparse regression has been extensively studied in the offline setting, but online formulation remains relatively under-explored. This gap stems from four key challenges: (i) the infeasibility of dynamically updating the regularization parameter in every online round, (ii) managing storage and memory complexity, (iii) enabling real-time computation via closed-form updates rather than solving full optimization problems at each round, and (iv) achieving optimal statistical guarantees under realistic assumptions. In this paper, we propose an online generalized-sparsity-constrained regression framework, focusing on online cardinality-constrained linear regression and low-rank matrix sensing. Unlike online regularized regression, our constrained formulation eliminates the need for dynamic parameter tuning. We introduce an efficient online hard-thresholding algorithm that performs closed-form updates and requires storing only summary statistics, making it computationally, memory, and storage efficient. Despite the inherent nonconvexity and combinatorial nature of the formulation, our algorithm achieves global convergence at the optimal statistical rate under realistic assumptions, provided that the projection set is properly overparameterized. Numerical experiments demonstrate that our method consistently outperforms state-of-the-art alternatives.