Near-optimal Active Regression of Single-Index Models
This solves a theoretical optimization problem in machine learning with applications in query-efficient learning, representing a significant advance over previous constant-factor approximations.
The paper tackles the active regression problem for single-index models, where the goal is to minimize queries to entries of b while approximating the solution, and presents an algorithm achieving a (1+ε)-approximation with near-optimal query complexity, specifically Õ(d^(p/2 ∨ 1)/ε^(p ∨ 2)) entries, with optimality results for p in [1,2] and ε-dependence for p>2.
The active regression problem of the single-index model is to solve $\min_x \lVert f(Ax)-b\rVert_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+\varepsilon)$-approximation solution by querying $\tilde{O}(d^{\frac{p}{2}\vee 1}/\varepsilon^{p\vee 2})$ entries of $b$. This query complexity is also shown to be optimal up to logarithmic factors for $p\in [1,2]$ and the $\varepsilon$-dependence of $1/\varepsilon^p$ is shown to be optimal for $p>2$.