%AMadan, M%ASingh, M.%ATantipongpipat, U%AXie, W.%BJournal Name: Conference on Learning Theory, COLT 2019; Journal Volume: 99
%D2019%I
%JJournal Name: Conference on Learning Theory, COLT 2019; Journal Volume: 99
%K
%MOSTI ID: 10196079
%PMedium: X; Size: 2210-2258
%TCombinatorial Algorithms for Optimal Design
%XIn an optimal design problem, we are given a set of linear experiments v1,…,vn∈Rd and k≥d, and our goal is to select a set or a multiset S⊆[n] of size k such that Φ((∑i∈Sviv⊤i)−1) is minimized. When Φ(M)=Determinant(M)1/d, the problem is known as the D-optimal design problem, and when Φ(M)=Trace(M), it is known as the A-optimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Miller and Nguyen, 1994; Atkinson et al., 2007). However, despite its wide usage no theoretical bound has been proven for this algorithm. In this paper, we bridge this gap and prove approximation guarantees for the local search algorithms for D-optimal design and A-optimal design problems. We show that the local search algorithms are asymptotically optimal when kd is large. In addition to this, we also prove similar approximation guarantees for the greedy algorithms for D-optimal design and A-optimal design problems when kd is large.
%0Journal Article
Country unknown/Code not availableOSTI-MSA