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
| CREATOR | Yi Li, Wai Ming Tai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-18213