Near-optimal discrete optimization for experimental design: a regret minimization approach
Near-optimal discrete optimization for experimental design: a regret minimization approach
复制标题
DOI：
10.1007/s10107-019-01464-2
复制
发表时间：
2017-11
影响因子：
2.7
通讯作者：
Zeyuan Allen-Zhu;Yuanzhi Li;Aarti Singh;Yining Wang
中科院分区：
文献类型：
--
作者：
Zeyuan Allen-Zhu;Yuanzhi Li;Aarti Singh;Yining Wang
实验设计问题涉及从一个潜在的大的p维向量设计池中选择k个点，以便最大化在所选择的k个设计点上回归的统计效率。统计效率的衡量标准是最优性，包括A（最优），D（不确定），T（种族），E（遗传），V（变异）和G-最优。除了T-最优性，精确优化是具有挑战性的，并且对于D/E-最优性的某些情况，精确优化甚至近似优化被证明是NP-难的。我们提出了一个多项式时间后悔最小化框架，以实现近似只有设计点，所有的最优性标准以上。相比之下，据我们所知，在我们的工作之前，没有多项式时间算法的D/E/G-最优近似，和最好的多时间算法的A/V-最优近似需要设计点。
The experimental design problem concerns the selection ofkpoints from a potentially large design pool ofp-dimensional vectors, so as to maximize the statistical efficiency regressed on the selectedkdesign points. Statistical efficiency is measured byoptimality 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 aapproximation with onlydesign points, for all the optimality criteria above. In contrast, to the best of our knowledge, before our work, no polynomial-time algorithm achievesapproximations for D/E/G-optimality, and the best poly-time algorithm achieving-approximation for A/V-optimality requiresdesign points.