Active Regression for Single-Index Models with Unknown Link Functions

arXiv:2608.01287v1 Announce Type: cross 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} |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 pgeq 1 and for unknown link functions only in the p=2 case, together with lower bounds for pleq 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/2ee 1}/epsilon^{pee 2}operatorname{poly}log(n/epsilon)) 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.

Source: arXiv cs.LG | 2026-08-04