This work demonstrates a $(1+B5)$-approximation solution for active regression in single-index models, highlighting improved query complexity.
The active regression problem of the single-index model is to solve minₓ f(Ax)-bₚ, 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+ε)-approximation solution by querying Õ(dp/2 1/εp 2) entries of b. This query complexity is also shown to be optimal up to logarithmic factors for p∈ [1,2] and the ε-dependence of 1/εᵖ is shown to be optimal for $p>2$.
No takes yet. Share an insight, caveat, or question.
Li et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: