Near-optimal Active Regression of Single-Index Models

2025/02/25 by Yi Li, Li, Yi, Wai Ming Tai +1 · 1 citation
Engineering · #Advanced Control Systems Optimization #Control Systems and Identification #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Fault Detection and Control Systems #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2502.18213

openalex publication_date 2025/02/25 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

Abstract

The active regression problem of the single-index model is to solve min_x ‖ f(Ax)-b‖_p, where A is fully accessible and b can only be accessed via entry queries, with the goal of minimizing the number of queries to the entries of b. When f is Lipschitz, previous results only obtain constant-factor approximations. This work presents the first algorithm that provides a (1+ε)-approximation solution by querying O(d^{(p)/(2)\vee 1}/ε^{p\vee 2}) entries of b. This query complexity is also shown to be optimal up to logarithmic factors for p∈ [1,2] and the ε-dependence of 1/ε^p is shown to be optimal for p>2.

Cited by

• Active Regression for Single-Index Models with Unknown Link Functions

Related

• Agnostic Active Learning of Single Index Models with Linear Sample Complexity
• Conditional regression for single-index models
• Estimating multi-index models with response-conditional least squares
• Semi-supervised Active Regression
• Active Linear Regression for ℓ_p Norms and Beyond