[edit]
Bayesian experimental design using regularized determinantal point processes
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3197-3207, 2020.
Abstract
We establish a fundamental connection between Bayesian experimental design and determinantal point processes (DPPs). Experimental design is a classical task in combinatorial optimization, where we wish to select a small subset of d-dimensional vectors to minimize a statistical optimality criterion. We show that a new regularized variant of DPPs can be used to design efficient algorithms for finding (1+ϵ)-approximate solutions to experimental design under four commonly used optimality criteria: A-, C-, D- and V-optimality. A key novelty is that we offer improved guarantees under the Bayesian framework, where prior knowledge is incorporated into the criteria. Our algorithm returns a (1+ϵ)-approximate solution when the subset size k is Ω(dAϵ+log(11/epsilon)ϵ2), where dA<<d is an effective dimension determined by prior knowledge (via a precision matrix A).This is the first approximation guarantee where the dependence on d is replaced by an effective dimension. Moreover, the time complexity of our algorithm significantly improves on existing approaches with comparable guarantees.