1
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach

Preprint

, , ,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### 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.

### Most cited references8

• Record: found

### Graph Sparsification by Effective Resistances

(2011)
Bookmark
• Record: found

### Relative-Error $CUR$ Matrix Decompositions

(2008)
Bookmark
• Record: found

### Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

(2004)
Bookmark

### Author and article information

###### Journal
14 November 2017
###### Article
1711.05174