Near-Optimal Design of Experiments via Regret Minimization


Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, Yining Wang ;
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:126-135, 2017.


We consider computationally tractable methods for the experimental design problem, where k out of n design points of dimension p are selected so that certain optimality criteria are approximately satisfied. Our algorithm finds a $(1+\epsilon)$-approximate optimal design when k is a linear function of p; in contrast, existing results require k to be super-linear in p. Our algorithm also handles all popular optimality criteria, while existing ones only handle one or two such criteria. Numerical results on synthetic and real-world design problems verify the practical effectiveness of the proposed algorithm.

Related Material