  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.
