# Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization arXiv: https://arxiv.org/abs/2106.03034 ยท HTML: https://mlsanity.com/paper/2106.03034/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 27 of its 38 references that are in the map. - First posted on arXiv 6 Jun 2021. ## Builds on (most cited first, 27 of 27) - [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013) - [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015) - [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020) - [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018) - [Practical Gauss-Newton Optimisation for Deep Learning](https://mlsanity.com/paper/1706.03662/) (2017) - [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020) - [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014) - [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018) - [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016) - [A Unified Analysis of Stochastic Momentum Methods for Deep Learning](https://mlsanity.com/paper/1808.10396/) (2018) - [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017) - [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017) - [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019) - [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021) - [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019) - [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020) - [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019) - [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017) - [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021) - [Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions](https://mlsanity.com/paper/2002.04130/) (2020) - [Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox](https://mlsanity.com/paper/1702.06269/) (2017) - [Generalized Momentum-Based Methods: A Hamiltonian Perspective](https://mlsanity.com/paper/1906.00436/) (2019) - [Deep Frank-Wolfe For Neural Network Optimization](https://mlsanity.com/paper/1811.07591/) (2018) - [Proximal Backpropagation](https://mlsanity.com/paper/1706.04638/) (2017) - [Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization](https://mlsanity.com/paper/2004.04357/) (2020) - [Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball](https://mlsanity.com/paper/2006.07867/) (2020) - [Distributed Mini-Batch SDCA](https://mlsanity.com/paper/1507.08322/) (2015) ## Built on by (most cited first, 10 of 10) - [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022) - [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023) - [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021) - [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023) - [Data-driven Piecewise Affine Decision Rules for Stochastic Programming with Covariate Information](https://mlsanity.com/paper/2304.13646/) (2023) - [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024) - [Adaptive Memory Momentum via a Model-Based Framework for Deep Learning Optimization](https://mlsanity.com/paper/2510.04988/) (2025) - [A Unified Momentum-based Paradigm of Decentralized SGD for Non-Convex Models and Heterogeneous Data](https://mlsanity.com/paper/2303.00179/) (2023) - [Learning-Based Surrogate Method for Stochastic Optimization under Decision-Dependent Uncertainty with Adaptive Random Designs](https://mlsanity.com/paper/2505.07298/) (2025) - [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025) ## Abstract (arXiv) Stochastic model-based methods have received increasing attention lately due to their appealing robustness to the stepsize selection and provable efficiency guarantee. We make two important extensions for improving model-based methods on stochastic weakly convex optimization. First, we propose new minibatch model-based methods by involving a set of samples to approximate the model function in each iteration. For the first time, we show that stochastic algorithms achieve linear speedup over the batch size even for non-smooth and non-convex (particularly, weakly convex) problems. To this end, we develop a novel sensitivity analysis of the proximal mapping involved in each algorithm iteration. Our analysis appears to be of independent interests in more general settings. Second, motivated by the success of momentum stochastic gradient descent, we propose a new stochastic extrapolated model-based method, greatly extending the classic Polyak momentum technique to a wider class of stochastic algorithms for weakly convex optimization. The rate of convergence to some natural stationarity condition is established over a fairly flexible range of extrapolation terms. While mainly focusing on weakly convex optimization, we also extend our work to convex optimization. We apply the minibatch and extrapolated model-based methods to stochastic convex optimization, for which we provide a new complexity bound and promising linear speedup in batch size. Moreover, an accelerated model-based method based on Nesterov's momentum is presented, for which we establish an optimal complexity bound for reaching optimality.