Stochastic model-based minimization under high-order growth

作者：Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee · 发表于：arXiv (Cornell University) · 年份：2018 · DOI：10.48550/arxiv.1807.00255 · 被引用次数：13 · 研究领域：Stochastic Gradient Optimization Techniques、Sparse and Compressive Sensing Techniques、Markov Chains and Monte Carlo Methods

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.