  Given a nonsmooth, nonconvex minimization problem, we consider algorithms
that iteratively sample and minimize stochastic convex models of the objective
function. Assuming that the one-sided approximation quality and the variation
of the models is controlled by a Bregman divergence, we show that the scheme
drives a natural stationarity measure to zero at the rate $O(k^{-1/4})$. Under
additional convexity and relative strong convexity assumptions, the function
values converge to the minimum at the rate of $O(k^{-1/2})$ and
$\widetilde{O}(k^{-1})$, respectively. We discuss consequences for stochastic
proximal point, mirror descent, regularized Gauss-Newton, and saddle point
algorithms.
