# Improved Active Learning via Dependent Leverage Score Sampling

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 43 references that are in the map.
- First posted on arXiv 8 Oct 2023.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark](https://mlsanity.com/paper/2002.01290/) (2020)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Near-Linear Sample Complexity for Lp Polynomial Regression](https://mlsanity.com/paper/2211.06790/) (2022)
- [Robust polynomial regression up to the information theoretic limit](https://mlsanity.com/paper/1708.03257/) (2017)

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

- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [AQKA: Active Quantum Kernel Acquisition Under a Shot Budget](https://mlsanity.com/paper/2605.14672/) (2026)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Core-elements Subsampling for Alternating Least Squares](https://mlsanity.com/paper/2509.18024/) (2025)

## Abstract (arXiv)

We show how to obtain improved active learning methods in the agnostic (adversarial noise) setting by combining marginal leverage score sampling with non-independent sampling strategies that promote spatial coverage. In particular, we propose an easily implemented method based on the pivotal sampling algorithm, which we test on problems motivated by learning-based methods for parametric PDEs and uncertainty quantification. In comparison to independent sampling, our method reduces the number of samples needed to reach a given target accuracy by up to 50%. We support our findings with two theoretical results. First, we show that any non-independent leverage score sampling method that obeys a weak emphone-sided ℓ∞ independence condition (which includes pivotal sampling) can actively learn d dimensional linear functions with O(dlog d) samples, matching independent sampling. This result extends recent work on matrix Chernoff bounds under ℓ∞ independence, and may be of interest for analyzing other sampling strategies beyond pivotal sampling. Second, we show that, for the important case of polynomial regression, our pivotal method obtains an improved bound on O(d) samples.