# Agnostic Active Learning of Single Index Models with Linear Sample Complexity

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 64 references that are in the map.
- First posted on arXiv 15 May 2024.

## Builds on (most cited first, 30 of 31)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Model Reduction and Neural Networks for Parametric PDEs](https://mlsanity.com/paper/2005.03180/) (2020)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Quantifying total uncertainty in physics-informed neural networks for solving forward and inverse stochastic problems](https://mlsanity.com/paper/1809.08327/) (2018)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Deep UQ: Learning deep neural network surrogate models for high dimensional uncertainty quantification](https://mlsanity.com/paper/1802.00850/) (2018)
- [A Theoretical Analysis of Deep Neural Networks and Parametric PDEs](https://mlsanity.com/paper/1904.00377/) (2019)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Derivative-Informed Projected Neural Networks for High-Dimensional Parametric Maps Governed by PDEs](https://mlsanity.com/paper/2011.15110/) (2020)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Numerical Solution of the Parametric Diffusion Equation by Deep Neural Networks](https://mlsanity.com/paper/2004.12131/) (2020)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [A Fast and Scalable Method for A-Optimal Design of Experiments for Infinite-dimensional Bayesian Nonlinear Inverse Problems](https://mlsanity.com/paper/1410.5899/) (2014)
- [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)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)

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

- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models](https://mlsanity.com/paper/2405.14121/) (2024)
- [Near-optimal Active Regression of Single-Index Models](https://mlsanity.com/paper/2502.18213/) (2025)
- [A model-agnostic active learning approach for animal detection from camera traps](https://mlsanity.com/paper/2507.06537/) (2025)
- [Active Learning for Decision Trees with Provable Guarantees](https://mlsanity.com/paper/2601.20775/) (2026)
- [Near-Polynomially Competitive Active Logistic Regression](https://mlsanity.com/paper/2503.05981/) (2025)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Robust Regression of General ReLUs with Queries](https://mlsanity.com/paper/2606.11130/) (2026)
- [Active Regression for Single-Index Models with Unknown Link Functions](https://mlsanity.com/paper/2608.01287/) (2026)

## Abstract (arXiv)

We study active learning methods for single index models of the form F(mathbf x) = f(langle mathbf w, mathbf xrangle), where f:ℝ → ℝ and mathbf x,mathbf w ∈ ℝd. In addition to their theoretical interest as simple examples of non-linear neural networks, single index models have received significant recent attention due to applications in scientific machine learning like surrogate modeling for partial differential equations (PDEs). Such applications require sample-efficient active learning methods that are robust to adversarial noise. I.e., that work even in the challenging agnostic learning setting. We provide two main results on agnostic active learning of single index models. First, when f is known and Lipschitz, we show that tildeO(d) samples collected via statistical leverage score sampling are sufficient to learn a near-optimal single index model. Leverage score sampling is simple to implement, efficient, and already widely used for actively learning linear models. Our result requires no assumptions on the data distribution, is optimal up to log factors, and improves quadratically on a recent O(d2) bound of citegajjar2023active. Second, we show that tildeO(d) samples suffice even in the more difficult setting when f is unknown. Our results leverage tools from high dimensional probability, including Dudley's inequality and dual Sudakov minoration, as well as a novel, distribution-aware discretization of the class of Lipschitz functions.