Title: Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach,
Abstract: The experimental design problem concerns the selection of k points from a
potentially large design pool of p-dimensional vectors, so as to maximize the
statistical efficiency regressed on the selected k design points. Statistical
efficiency is measured by optimality criteria, including A(verage),
D(eterminant), T(race), E(igen), V(ariance) and G-optimality. Except for the
T-optimality, exact optimization is NP-hard.
We propose a polynomial-time regret minimization framework to achieve a
$(1+\varepsilon)$ approximation with only $O(p/\varepsilon^2)$ design points,
for all the optimality criteria above.
In contrast, to the best of our knowledge, before our work, no
polynomial-time algorithm achieves $(1+\varepsilon)$ approximations for
D/E/G-optimality, and the best poly-time algorithm achieving
$(1+\varepsilon)$-approximation for A/V-optimality requires $k =
\Omega(p^2/\varepsilon)$ design points.