# Stochastic model-based minimization under high-order growth

arXiv: https://arxiv.org/abs/1807.00255 · HTML: https://mlsanity.com/paper/1807.00255/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2018.

## Built on by (most cited first, 7 of 7)

- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [Natural Gradient VI: Guarantees for Non-Conjugate Models](https://mlsanity.com/paper/2510.19163/) (2025)
- [Efficient algorithms for implementing incremental proximal-point methods](https://mlsanity.com/paper/2205.01457/) (2022)
- [Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity](https://mlsanity.com/paper/2305.14161/) (2023)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)

## Abstract (arXiv)

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 widetildeO(k-1), respectively. We discuss consequences for stochastic proximal point, mirror descent, regularized Gauss-Newton, and saddle point algorithms.