Near-optimal Active Regression of Single-Index Models
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 7 of its 18 references that are in the map. First posted on arXiv 25 Feb 2025.
Builds on
7 of 18 references.
References · 7
- 2017Active Regression via Linear-Sample Sparsificationcited by 36
- 2020Approximation Schemes for ReLU Regressioncited by 34
- 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
- 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
- 2022Online Active Regressioncited by 8
- 2021Computing Lewis Weights to High Precisioncited by 7
- 2024One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Modelscited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.