Approximate Supermodularity Bounds for Experimental Design

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 nonasymptotic 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.