Stochastic model-based minimization under high-order growth

Abstract

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 $\tilde{O}(k^{-1})$, respectively. We discuss consequences for stochastic proximal point, mirror descent, regularized Gauss-Newton, and saddle point algorithms.

30 pages

References in corpus (4)

• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Regularizing with Bregman-Moreau envelopes
• "Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent

Cited by in corpus (8)

• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Bregman Proximal Framework for Deep Linear Neural Networks
• Model Function Based Conditional Gradient Method with Armijo-like Line Search
• About some works of Boris Polyak on convergence of gradient methods and their development
• First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approach