Active Regression for Single-Index Models with Unknown Link Functions

Abstract

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}\Vert f(Ax)-b{\Vert }_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\ge 1$ and for unknown link functions only in the $p=2$ case, together with lower bounds for $p\le 2$. This work addresses the more challenging setting of unknown link functions and general $p\ge 1$. A non-adaptive sampling algorithm is presented that achieves a $(1+\hat{I}\mu )$-approximation using $O(d^{p/2\vee 1}/\hat{I}{\mu }^{p\vee 2}\mathrm{poly}\log (n/\hat{I}\mu ))$ 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.

Earlier version accepted to ICML 2026; the lower bound has been extended to adaptive queries