# Reduced Label Complexity For Tight ℓ2 Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 41 references that are in the map.
- First posted on arXiv 12 May 2023.

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

- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [Weighted SGD for ℓp Regression with Randomized Preconditioning](https://mlsanity.com/paper/1502.03571/) (2015)
- [Active learning for reducing labeling effort in text classification tasks](https://mlsanity.com/paper/2109.04847/) (2021)

## Abstract (arXiv)

Given data rm X∈ℝn× d and labels y∈ℝn the goal is find w∈ℝd to minimize Vertrm Xw-yVert2. We give a polynomial algorithm that, emphoblivious to y, throws out n/(d+√n) data points and is a (1+d/n)-approximation to optimal in expectation. The motivation is tight approximation with reduced label complexity (number of labels revealed). We reduce label complexity by Omega(√n). Open question: Can label complexity be reduced by Omega(n) with tight (1+d/n)-approximation?