Title: Approximate Supermodularity Bounds for Experimental Design,
Abstract: This work provides performance guarantees for the greedy solution of
experimental design problems. In particular, it focuses on A- and E-optimal
designs, for which typical guarantees do not apply since the mean-square error
and the maximum eigenvalue of the estimation error covariance matrix are not
supermodular. To do so, it leverages the concept of approximate supermodularity
to derive non-asymptotic worst-case suboptimality bounds for these greedy
solutions. These bounds reveal that as the SNR of the experiments decreases,
these cost functions behave increasingly as supermodular functions. As such,
greedy A- and E-optimal designs approach (1-1/e)-optimality. These results
reconcile the empirical success of greedy experimental design with the
non-supermodularity of the A- and E-optimality criteria.