Refined bounds for randomized experimental design
This work provides theoretical guarantees for randomized experimental design strategies, offering a more tractable approach for researchers and practitioners dealing with NP-hard optimal design problems.
This paper investigates randomized strategies for E and G-optimal experimental design, which are typically NP-hard to compute. The authors provide theoretical guarantees for these randomized strategies, demonstrating their performance through experiments, especially for G-optimal design in linear bandits.
Experimental design is an approach for selecting samples among a given set so as to obtain the best estimator for a given criterion. In the context of linear regression, several optimal designs have been derived, each associated with a different criterion: mean square error, robustness, \emph{etc}. Computing such designs is generally an NP-hard problem and one can instead rely on a convex relaxation that considers probability distributions over the samples. Although greedy strategies and rounding procedures have received a lot of attention, straightforward sampling from the optimal distribution has hardly been investigated. In this paper, we propose theoretical guarantees for randomized strategies on E and G-optimal design. To this end, we develop a new concentration inequality for the eigenvalues of random matrices using a refined version of the intrinsic dimension that enables us to quantify the performance of such randomized strategies. Finally, we evidence the validity of our analysis through experiments, with particular attention on the G-optimal design applied to the best arm identification problem for linear bandits.