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.

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v70-allen-zhu17e, title = {Near-Optimal Design of Experiments via Regret Minimization}, author = {Zeyuan Allen-Zhu and Yuanzhi Li and Aarti Singh and Yining Wang}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {126--135}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/allen-zhu17e/allen-zhu17e.pdf}, url = { http://proceedings.mlr.press/v70/allen-zhu17e.html }, abstract = {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.} }
Endnote
%0 Conference Paper %T Near-Optimal Design of Experiments via Regret Minimization %A Zeyuan Allen-Zhu %A Yuanzhi Li %A Aarti Singh %A Yining Wang %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-allen-zhu17e %I PMLR %P 126--135 %U http://proceedings.mlr.press/v70/allen-zhu17e.html %V 70 %X 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.
APA
Allen-Zhu, Z., Li, Y., Singh, A. & Wang, Y.. (2017). Near-Optimal Design of Experiments via Regret Minimization. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:126-135 Available from http://proceedings.mlr.press/v70/allen-zhu17e.html .

Related Material