2019/06/10 by Michał Dereziński, Dereziński, Michał, Feynman Liang +3
Computer Science · Decision Sciences · Mathematics · #Advanced Multi-Objective Optimization Algorithms #Advanced Statistical Methods and Models #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimal Experimental Design Methods
paper · pdf · doi:10.48550/arxiv.1906.04133
openalex publication_date 2019/06/10 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
In experimental design, we are given n vectors in d dimensions, and our\ngoal is to select k\≪ n of them to perform expensive measurements, e.g., to\nobtain labels/responses, for a linear regression task. Many statistical\ncriteria have been proposed for choosing the optimal design, with popular\nchoices including A- and D-optimality. If prior knowledge is given, typically\nin the form of a d\× d precision matrix mathbf A, then all of the\ncriteria can be extended to incorporate that information via a Bayesian\nframework. In this paper, we demonstrate a new fundamental connection between\nBayesian experimental design and determinantal point processes, the latter\nbeing widely used for sampling diverse subsets of data. We use this connection\nto develop new efficient algorithms for finding (1+\ε)-approximations\nof optimal designs under four optimality criteria: A, C, D and V. Our\nalgorithms can achieve this when the desired subset size k is\n\Ω( fracd mathbf A\ε + \(\log 1/\ε)/(\ε2)),\nwhere d mathbf A\≤ d is the mathbf A-effective dimension, which can\noften be much smaller than d. Our results offer direct improvements over a\nnumber of prior works, for both Bayesian and classical experimental design, in\nterms of algorithm efficiency, approximation quality, and range of applicable\ncriteria.\n