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. As such, greedy A-and E-optimal designs approach (1 − e −1 )-optimality. These results reconcile the empirical success of greedy experimental design with the non-supermodularity of the A-and E-optimality criteria.
This paper defines two types of approximate supermodularity, namely alpha-supermodularity and epsilon-supermodularity, both of which are extensions of the existing supermodularity definition. Then the authors show that the objectives of finding the A- and E-optimal Bayesian experimental design respectively belong to those two approximate supermodularity. Therefore, the greedy selection algorithm can obtain a good solution to the design problem that is within (1-e^{-1}) of the optimal, which is guaranteed by the standard result of supermodularity minimization.
This paper is nicely written and everything is easy to understand. I really enjoy reading it. The result gives a theoretical justification of the effectiveness of the greedy algorithm in finding A- and E- optimal design, which is further confirmed by experiments. 
However, I also see some limitations of the proposed framework:
1. The analysis seems to apply only to Bayesian experimental design that the theta must have a prior. If not for the regularization term in the equation 4, it might be impossible to use any greedy algorithm. On the contrary, existing approach such as [10] does not have such limitation.
2. The relative error is different from the traditional definition, as the objective function f is normalized that f(D) <= 0 for all D. I suspect this is the key that makes the proof valid. Will this framework be applied to the unnormalized objective?
Although there are limitations, I still think the paper is above the acceptance threshold of NIPS.