Near-optimal Active Regression of Single-Index Models

Abstract

The active regression problem of the single-index model is to solve ${\min }_x\Vert f(Ax)-b{\Vert }_p$, 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+\epsilon )$-approximation solution by querying $\tilde{O}(d^{\frac{p}{2}\vee 1}/{\epsilon }^{p\vee 2})$ entries of $b$. This query complexity is also shown to be optimal up to logarithmic factors for $p\in [1,2]$ and the $\epsilon$-dependence of $1/{\epsilon }^p$ is shown to be optimal for $p>2$.