Seminar | October 9 | 2:30-3:30 p.m. | 540 Cory Hall
Zeyuan Allen-Zhu, Microsoft Research
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 1+varepsilon approximations for DTEG-optimality, and (2) the algorithm achieving 1+varepsilon approximation for AV-optimality require $k geq Omega(p^2/varepsilon)$