# Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP

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

## Key facts

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

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

- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Online Linearized LASSO](https://mlsanity.com/paper/2211.06039/) (2022)
- [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)
- [Online Generalized Sparse Regression: How Does Overparametrization Help?](https://mlsanity.com/paper/2608.17466/) (2026)

## Abstract (arXiv)

Online sparse linear regression is an online problem where an algorithm repeatedly chooses a subset of coordinates to observe in an adversarially chosen feature vector, makes a real-valued prediction, receives the true label, and incurs the squared loss. The goal is to design an online learning algorithm with sublinear regret to the best sparse linear predictor in hindsight. Without any assumptions, this problem is known to be computationally intractable. In this paper, we make the assumption that data matrix satisfies restricted isometry property, and show that this assumption leads to computationally efficient algorithms with sublinear regret for two variants of the problem. In the first variant, the true label is generated according to a sparse linear model with additive Gaussian noise. In the second, the true label is chosen adversarially.