Zeyuan Allen-Zhu (Microsoft Research)

Oct 9, 2017.

Title and Abstract

Optimal Experimental Design via A New Regret Minimization Framework

The experimental design problem concerns the selection of k points from a potentially very large design pool of p-dimensional vectors, so as to maximize the statistical efficiency regressed on the selected k design points.

We achieve $1+varepsilon$ approximations to all popular optimality criteria for this problem, including A-optimality, D-optimality, T-optimality, E-optimality, V-optimality and G-optimality, with only $k = O(p/varepsilon^2)$ design points.

In contrast, to the best of our knowledge, previously (1) no polynomial-time algorithm exists for achieving any $1varepsilon$ approximations for D,E,G-optimality, and (2) the algorithm achieving $1varepsilon$ approximation for AV-optimality require $k geq Omega(p^2varepsilon)$.

Joint work with Yuanzhi Li, Aarti Singh, and Yining Wang.


Zeyuan Allen-Zhu is a researcher at MSR Redmond. Previously he received an Sc.D. from MIT and spent two years as a postdoc at Princeton and IAS. He works on the mathematical foundations of optimization and machine learning, and applies them to subjects across data mining, theoretical computer science, and statistics.