Active Regression for Single-Index Models with Unknown Link Functions

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