# Online Sparse Linear Regression

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2016.

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

- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Generator Assisted Mixture of Experts For Feature Acquisition in Batch](https://mlsanity.com/paper/2312.12574/) (2023)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation](https://mlsanity.com/paper/2501.00799/) (2025)
- [A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions](https://mlsanity.com/paper/2510.27177/) (2025)

## Abstract (arXiv)

We consider the online sparse linear regression problem, which is the problem of sequentially making predictions observing only a limited number of features in each round, to minimize regret with respect to the best sparse linear regressor, where prediction accuracy is measured by square loss. We give an inefficient algorithm that obtains regret bounded by tildeO(√T) after T prediction rounds. We complement this result by showing that no algorithm running in polynomial time per iteration can achieve regret bounded by O(T1-δ) for any constant δ > 0 unless NP subseteq BPP. This computational hardness result resolves an open problem presented in COLT 2014 (Kale, 2014) and also posed by Zolghadr et al. (2013). This hardness result holds even if the algorithm is allowed to access more features than the best sparse linear regressor up to a logarithmic factor in the dimension.