Randomization is an increasingly popular tool for solving optimal stopping problems numerically, for instance, in order to price Bermudan options. This means that stopping decisions are relaxed by randomizing them with respect to an independent noise, thereby mollifying the optimal control problem. We study two specific algorithms based on randomization. We consider a forward approach consisting of global optimization of properly parameterized randomized stopping times. As an alternative, we also consider a backward approach based on dynamic programming, i.e., optimizing a sequence of stopping decisions locally in time. We provide theoretical justification for the resulting simulation-based algorithms by a rigorous convergence analysis in the number of training trajectories. Therefore, this work contains partial convergence analysis of the recent machine learning approaches to optimal stopping problems.