Speaker:

Yi Li (Nanyang Technological University)

Time:

• 10:20-11:20 Beijing Time
• March 4, 2025 (Tuesday)

Venue:

518, Research Building 4

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.