# Stochastic model-based minimization under high-order growth

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.