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} \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\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+\epsilon)$-approximation using $O(d^{p/2\vee 1}/\epsilon^{p\vee 2}\text{poly}\log(n/\epsilon))$ queries. Nearly tight lower bounds are also established for non-adaptive queries when $p>2$. These results close much of the remaining gap in active $\ell_p$ regression for single-index models.

This paper studies how to fit a prediction model when the input data are available, but the output values are expensive to inspect. The model first combines the input features linearly, then passes the result through an unknown but smooth transformation function. The main challenge is to learn both the linear part and the unknown transformation while querying only a small number of output entries. Previous work handled easier cases, such as when the transformation was known or when the error was squared loss. This paper gives a non-adaptive sampling method that achieves nearly optimal accuracy for general $\ell_p$-losses.