Abstract: We design a randomized Greedy algorithm that draws parameter samples from a clever probability distribution to effectively build a training set at each iteration. We prove that this algorithm provides certification with high probability over the entire parameter set, utilizing results from sampling discretization theory and concentration of measure phenomena. Moreover, we demonstrate favorable properties of the algorithm’s sampling complexity to break the curse of dimensionality encountered by e.g. the deterministic Greedy algorithm when choosing a suitable training set. We present preliminary numerical results of the algorithm’s performance at building reduced approximation spaces for benchmark PDE problems. Finally, we discuss potential applications of the algorithm in the setting of localized model order reduction for linear and nonlinear PDEs. Within the digital twin framework, this approach would potentially allow for an efficient construction of reduced local approximation spaces that accurately capture multiscale aspects of the system with high probability, even for parameters not seen in the training phase.