# Near-optimal Active Regression of Single-Index Models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 25 Feb 2025.

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

- [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)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Online Active Regression](https://mlsanity.com/paper/2207.05945/) (2022)
- [Computing Lewis Weights to High Precision](https://mlsanity.com/paper/2110.15563/) (2021)
- [One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models](https://mlsanity.com/paper/2405.14121/) (2024)

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

- [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)

The active regression problem of the single-index model is to solve minx lVert f(Ax)-brVertp, where A is fully accessible and b can only be accessed via entry queries, with the goal of minimizing the number of queries to the entries of b. When f is Lipschitz, previous results only obtain constant-factor approximations. This work presents the first algorithm that provides a (1+varepsilon)-approximation solution by querying tildeO(d^fracp2vee 1/varepsilonpvee 2) entries of b. This query complexity is also shown to be optimal up to logarithmic factors for p∈ [1,2] and the varepsilon-dependence of 1/varepsilonp is shown to be optimal for p>2.