# A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 34 references that are in the map.
- First posted on arXiv 31 Oct 2025.

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

- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP](https://mlsanity.com/paper/1706.04690/) (2017)
- [Online Sparse Linear Regression](https://mlsanity.com/paper/1603.02250/) (2016)
- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)
- [Sample Efficient Stochastic Gradient Iterative Hard Thresholding Method for Stochastic Sparse Linear Regression with Limited Attribute Observation](https://mlsanity.com/paper/1809.01765/) (2018)
- [Online Linearized LASSO](https://mlsanity.com/paper/2211.06039/) (2022)

## Abstract (arXiv)

In this paper, we study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only k out of d attributes per instance for prediction, which was proved to be NP-hard. Previous work gave polynomial-time algorithms assuming the data matrix satisfies the linear independence of features, the compatibility condition, or the restricted isometry property. We introduce a new polynomial-time algorithm, which significantly improves previous regret bounds (Ito et al., 2017) under the compatibility condition that is weaker than the other two assumptions. The improvements benefit from a tighter convergence rate of the ℓ1-norm error of our estimators. Our algorithm leverages the well-studied Dantzig Selector, but importantly with several novel techniques, including an algorithm-dependent sampling scheme for estimating the covariance matrix, an adaptive parameter tuning scheme, and a batching online Newton step with careful initializations. We also give novel and non-trivial analyses, including an induction method for analyzing the ℓ1-norm error, careful analyses on the covariance of non-independent random variables, and a decomposition on the regret. We further extend our algorithm to OSLR with additional observations where the algorithms can observe additional k0 attributes after each prediction, and improve previous regret bounds (Kale et al., 2017; Ito et al., 2017).