# Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 41 references that are in the map.
- First posted on arXiv 3 Feb 2021.

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

- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [Unbiased estimates for linear regression via volume sampling](https://mlsanity.com/paper/1705.06908/) (2017)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression](https://mlsanity.com/paper/1902.00995/) (2019)
- [Unbiased estimators for random design regression](https://mlsanity.com/paper/1907.03411/) (2019)
- [Correcting the bias in least squares regression with volume-rescaled sampling](https://mlsanity.com/paper/1810.02453/) (2018)

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

- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond](https://mlsanity.com/paper/2402.17327/) (2024)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Online Active Regression](https://mlsanity.com/paper/2207.05945/) (2022)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models](https://mlsanity.com/paper/2405.14121/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Active Learning with Low-Rank Structure for Data Selection](https://mlsanity.com/paper/2606.16045/) (2026)

## Abstract (arXiv)

Consider a regression problem where the learner is given a large collection of d-dimensional data points, but can only query a small subset of the real-valued labels. How many queries are needed to obtain a 1+ε relative error approximation of the optimum? While this problem has been extensively studied for least squares regression, little is known for other losses. An important example is least absolute deviation regression (ℓ1 regression) which enjoys superior robustness to outliers compared to least squares. We develop a new framework for analyzing importance sampling methods in regression problems, which enables us to show that the query complexity of least absolute deviation regression is Theta(d/ε2) up to logarithmic factors. We further extend our techniques to show the first bounds on the query complexity for any ℓp loss with p∈(1,2). As a key novelty in our analysis, we introduce the notion of robust uniform convergence, which is a new approximation guarantee for the empirical loss. While it is inspired by uniform convergence in statistical learning, our approach additionally incorporates a correction term to avoid unnecessary variance due to outliers. This can be viewed as a new connection between statistical learning theory and variance reduction techniques in stochastic optimization, which should be of independent interest.