Research map / Learning theory and algorithms / Sample complexity
Improved Active Learning via Dependent Leverage Score Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes spatially-aware pivotal sampling (binary-tree tournament over leverage-score probabilities) for agnostic active linear regression, proving O(d log d + d/ε) sample complexity and showing fewer labels needed than Bernoulli leverage score sampling on PDE surrogate test problems.
Problem
Agnostic active linear regression: choosing few target entries to fit a linear model with near-optimal least squares error, motivated by surrogate modeling for parametric PDEs and uncertainty quantification.
Approach
Replace independent leverage-score (Bernoulli) sampling with pivotal sampling on a spatially structured binary tree (PCA or coordinate splitting), keeping marginal inclusion probabilities proportional to leverage scores while making samples negatively dependent and spatially spread; theory shows one-sided l_inf independence with D=2 suffices for the same guarantee.
Key results
- Pivotal sampling needs 487-ish fewer samples: for 1.1x OPT error with degree 12, pivotal requires 450 vs 924 samples for Bernoulli on the 2D damped oscillator (about 49% of Bernoulli's samples).
- Theory: pivotal sampling on a fixed binary tree is one-sided l_inf-independent with D=2, matching O(d log d + d/ε) sample complexity of i.i.d. leverage score sampling.
- For 2x OPT error, pivotal sampling requires 69-80% of the samples used by Bernoulli across four test problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Damped harmonic oscillator 2D, 1.1 × OPT error | samples required: 924 -> 450 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Heat equation, 1.1 × OPT error | samples required: 814 -> 442 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Surface reaction, 1.1 × OPT error | samples required: 903 -> 492 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Damped harmonic oscillator 3D, 1.1 × OPT error | samples required: 3121 -> 1943 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Damped harmonic oscillator 2D, 2 × OPT error | samples required: 574 -> 398 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Heat equation, 2 × OPT error | samples required: 554 -> 395 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Surface reaction, 2 × OPT error | samples required: 545 -> 390 | Helped |
| Use spatially aware pivotal sampling instead of Bernoulli leverage sampling | Active polynomial regression · Damped harmonic oscillator 3D, 2 × OPT error | samples required: 671 -> 533 | Helped |
| Use leverage-score inclusion probabilities instead of uniform probabilities | Bernoulli and pivotal sampling · Damped harmonic oscillator 2D | relative error | Helped |
Limitations
- Theory only matches, and does not explain why pivotal sampling outperforms, Bernoulli leverage score sampling.
- Coordinate-wise splitting variant is tailored to uniform domains.
- Runtime costs of pivotal sampling not analyzed in detail.
Experimental setup
Benchmarks: damped harmonic oscillator QoI heat equation QoI chemical surface reaction model
Metrics: normalized least squares error samples needed to reach 2x OPT and 1.1x OPT error
Baselines: Bernoulli leverage score sampling uniform sampling Chebyshev grid randomized BSS
Builds on: leverage score sampling pivotal sampling matrix Chernoff bounds for l_inf-independent distributions Chebyshev nodes
Closest papers by meaning
- Improved Leverage Score Sampling for Constrained Active Linear Regression (NeurIPS 2026 · similarity 0.90)
- Transductive Active Learning: Theory and Applications (NeurIPS 2024 · similarity 0.86)
- On the Benefits of Active Data Collection in Operator Learning (ICML 2025 · similarity 0.86)
- Deep Active Learning with Noise Stability (AAAI 2024 · similarity 0.85)
- Robust Sampling for Active Statistical Inference (NeurIPS 2025 · similarity 0.85)
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.