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

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+\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.

33 pages, 4 tables. A preliminary version of this paper titled "Near-Optimal Experimental Design via Regret Minimization" with weaker results appeared in the Proceedings of the 34th International Conference on Machine Learning (ICML 2017), Sydney

References in corpus (5)

• Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
• Greedy Sampling of Graph Signals
• Optimal CUR Matrix Decompositions
• Submodular Functions: from Discrete to Continous Domains
• Signal Representations on Graphs: Tools and Applications

Cited by in corpus (4)

• Active Learning for Graph Neural Networks via Node Feature Propagation
• Sequential Experimental Design for Transductive Linear Bandits
• A near-optimal algorithm for approximating the John Ellipsoid
• Gaussian Process Landmarking on Manifolds