Near-optimal discrete optimization for experimental design: a regret minimization approach

• 成果类型: Article
• 署名作者: Allen-Zhu, Zeyuan; Li, Yuanzhi; Singh, Aarti; Wang, Yining
• 署名单位: Microsoft; Carnegie Mellon University; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01464-2
• 发表日期: 2021
• 页码: 439-478
• 关键词: subset-selection; matrix; algorithms; approximation

摘要

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 challenging, and for certain instances of D/E-optimality exact or even approximate optimization is proven to be NP-hard. We propose a polynomial-time regret minimization framework to achieve a (1 + epsilon) approximation with only O(p/epsilon(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 + epsilon) approximations for D/E/G-optimality, and the best poly-time algorithm achieving (1+ epsilon)-approximation for A/V-optimality requires k = Omega(p(2)/epsilon) design points.