Stochastic model-based minimization under high-order growth
This work addresses optimization challenges in machine learning and related fields, offering incremental improvements to existing stochastic methods.
The paper tackles the problem of nonsmooth, nonconvex minimization by proposing algorithms that use stochastic convex models, achieving a stationarity measure rate of O(k^{-1/4}) and, under convexity assumptions, function value convergence rates of O(k^{-1/2}) and O(k^{-1}).
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.