Active Regression for Single-Index Models with Unknown Link Functions

2026/08/02 by Chansophea Wathanak In, Yi Li, Wai Ming Tai +1
Computer Science · #cs.DS #cs.LG

paper · pdf

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

arxiv created 2026/08/02 · arxiv updated 2026/08/04

Abstract

This paper studies active regression for single-index models under general ℓ_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≥ 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(d^{p/2\vee 1}/ε^{p\vee 2}polylog(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.

Citations

• Near-optimal Active Regression of Single-Index Models
• One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models
• Agnostic Active Learning of Single Index Models with Linear Sample Complexity
• On computing approximate Lewis weights
• Active Learning for Single Neuron Models with Lipschitz Non-Linearities
• L1 Regression with Lewis Weights Subsampling
• Sharp and Simple Bounds for the raw Moments of the Binomial and Poisson Distributions