Near-optimal Active Regression of Single-Index Models

The active regression problem of the single-index model is to solve min x ∥f (Ax) -b∥ 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 + ε)-approximation solution by querying Õ(d p 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/ε p is shown to be optimal for p > 2.