# Online Active Regression

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 13 Jul 2022.

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

- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Near Optimal Linear Algebra in the Online and Sliding Window Models](https://mlsanity.com/paper/1805.03765/) (2018)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Active Regression by Stratification](https://mlsanity.com/paper/1410.5920/) (2014)
- [Single Pass Spectral Sparsification in Dynamic Streams](https://mlsanity.com/paper/1407.1289/) (2014)
- [Online Active Linear Regression via Thresholding](https://mlsanity.com/paper/1602.02845/) (2016)

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

- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Streaming Active Learning for Regression Problems Using Regression via Classification](https://mlsanity.com/paper/2309.01013/) (2023)
- [One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models](https://mlsanity.com/paper/2405.14121/) (2024)
- [Near-optimal Active Regression of Single-Index Models](https://mlsanity.com/paper/2502.18213/) (2025)
- [Modeling of AUV Dynamics with Limited Resources: Efficient Online Learning Using Uncertainty](https://mlsanity.com/paper/2504.04583/) (2025)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)

## Abstract (arXiv)

Active regression considers a linear regression problem where the learner receives a large number of data points but can only observe a small number of labels. Since online algorithms can deal with incremental training data and take advantage of low computational cost, we consider an online extension of the active regression problem: the learner receives data points one by one and immediately decides whether it should collect the corresponding labels. The goal is to efficiently maintain the regression of received data points with a small budget of label queries. We propose novel algorithms for this problem under ℓp loss where p∈[1,2]. To achieve a (1+ε)-approximate solution, our proposed algorithms only require tildeO(ε-1 d log(nkappa)) queries of labels, where n is the number of data points and kappa is a quantity, called the condition number, of the data points. The numerical results verify our theoretical results and show that our methods have comparable performance with offline active regression algorithms.