Active Regression for Single-Index Models with Unknown Link Functions

This paper studies active regression for single-index models under general \ell_p-loss with an unknown 1-Lipschitz link function f, formulated as \min_{f,x} |f(Ax)-b|_p^p with full access to A but coordinate-query access to b. Prior work established upper bounds for known link functions for all p\geq 1 and for unknown link functions only in the p=2 case, together with lower bounds for p\leq 2. This work addresses the more challenging setting of unknown link functions and general p \geq 1. A non-adaptive sampling algorithm is presented that achieves a (1+ε)-approximation using O(d^{p/2\vee 1}/ε^{p\vee 2}\operatorname{poly}\log(n/ε)) queries. Nearly tight lower bounds are also established for p>2. These results close much of the remaining gap in active \ell_p-regression for single-index models.