# Incremental Methods for Weakly Convex Optimization

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

## Key facts

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

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

- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [Wasserstein Convergence of Score-based Generative Models under Semiconvexity and Discontinuous Gradients](https://mlsanity.com/paper/2505.03432/) (2025)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/2310.15976/) (2023)
- [Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees](https://mlsanity.com/paper/2509.04133/) (2025)

## Abstract (arXiv)

Incremental methods are widely utilized for solving finite-sum optimization problems in machine learning and signal processing. In this paper, we study a family of incremental methods -- including incremental subgradient, incremental proximal point, and incremental prox-linear methods -- for solving weakly convex optimization problems. Such a problem class covers many nonsmooth nonconvex instances that arise in engineering fields. We show that the three said incremental methods have an iteration complexity of O(varepsilon-4) for driving a natural stationarity measure to below varepsilon. Moreover, we show that if the weakly convex function satisfies a sharpness condition, then all three incremental methods, when properly initialized and equipped with geometrically diminishing stepsizes, can achieve a local linear rate of convergence. Our work is the first to extend the convergence rate analysis of incremental methods from the nonsmooth convex regime to the weakly convex regime. Lastly, we conduct numerical experiments on the robust matrix sensing problem to illustrate the convergence performance of the three incremental methods.