Reduced Label Complexity For Tight ℓ2 Regression
Not on the map. Why?
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?
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 6 of its 41 references that are in the map. First posted on arXiv 12 May 2023.
Builds on
6 of 41 references.
References · 6
- 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
- 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
- 2017Active Regression via Linear-Sample Sparsificationcited by 36
- 2018Reverse iterative volume sampling for linear regressioncited by 9
- 2015Weighted SGD for ℓp Regression with Randomized Preconditioningcited by 6
- 2021Active learning for reducing labeling effort in text classification taskscited by 4
Built on by
Not cited yet.