Near-optimal Active Regression of Single-Index Models

Yi Li, Wai Ming Tai · 2025

Read Near-optimal Active Regression of Single-Index Models by Yi Li, Wai Ming Tai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-18213.txt.

Description

Yi Li and Wai Ming Tai present an active regression algorithm for single index models in this 2025 paper. In this setup the design matrix is fully known, but the response vector can only be read entry by entry. Each query has a cost, so few queries are the goal. Prior methods gave only rough constant factor approximations.

Their algorithm returns a solution within a factor of one plus epsilon of optimal. The query count is proved near optimal for a range of error norms. For steeper norms the dependence on epsilon is also optimal. Logarithmic factors are the only slack in the bounds. The result closes a gap between what was achievable and what is provably necessary for this problem.

Catalog record

CREATORYi Li, Wai Ming Tai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-18213

Browse the full library · About the Tower of Babel