Yi Li: Near-optimal Active Regression of Single-Index Models

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. I shall present an algorithm that provides a $(1+\epsilon)$-approximation solution by querying $\tilde{O}(d^{\frac{p}{2}\vee 1}/\epsilon^{p\vee 2})$ entries of $b$. I shall also show that this query complexity is optimal up to logarithmic factors for $p\in [1,2]$ and that the $\epsilon$-dependence of $1/\epsilon^p$ is optimal for $p>2$.

Speaker Bio

Yi Li is an associate professor in the Division of Mathematical Sciences and holds a joint appointment in the School of Computing and Data Science at Nanyang Technological University. His main research interests lie in algorithms for massive datasets and sublinear time streaming algorithms, with a particular focus on randomized numerical linear algebra in recent years.