Near-optimal Active Regression of Single-Index Models

Abstract

The active regression problem of the single-index model is to solve _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^p2 1/^p 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.

Tasks

Reproductions