Approximate Supermodularity Bounds for Experimental Design
This work addresses the theoretical gap for experimental design in statistics and machine learning, offering incremental insights by reconciling empirical success with non-supermodularity.
The paper tackled the problem of providing performance guarantees for greedy solutions in A- and E-optimal experimental design, where typical supermodularity-based guarantees do not apply, by deriving non-asymptotic worst-case suboptimality bounds using approximate supermodularity, showing that greedy designs approach (1-1/e)-optimality as SNR decreases.
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.