# Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2018.

## Built on by (most cited first, 30 of 32)

- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances](https://mlsanity.com/paper/2210.09160/) (2022)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [Plug-and-Play image restoration with Stochastic deNOising REgularization](https://mlsanity.com/paper/2402.01779/) (2024)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Outlier-Robust Sparse Estimation via Non-Convex Optimization](https://mlsanity.com/paper/2109.11515/) (2021)
- [Weakly Convex Regularisers for Inverse Problems: Convergence of Critical Points and Primal-Dual Optimisation](https://mlsanity.com/paper/2402.01052/) (2024)
- [Weighted Distillation with Unlabeled Examples](https://mlsanity.com/paper/2210.06711/) (2022)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Learning with Logical Constraints but without Shortcut Satisfaction](https://mlsanity.com/paper/2403.00329/) (2024)
- [Min-Max Bilevel Multi-objective Optimization with Applications in Machine Learning](https://mlsanity.com/paper/2203.01924/) (2022)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Provable Policy Gradient Methods for Average-Reward Markov Potential Games](https://mlsanity.com/paper/2403.05738/) (2024)
- [Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution](https://mlsanity.com/paper/2207.07612/) (2022)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)
- [Oracle-Robust Online Alignment for Large Language Models](https://mlsanity.com/paper/2602.20457/) (2026)
- [Risk-Conditioned Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2609.08064/) (2026)
- [ScaLA: Accelerating Adaptation of Pre-Trained Transformer-Based Language Models via Efficient Large-Batch Adversarial Noise](https://mlsanity.com/paper/2201.12469/) (2022)
- [Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization](https://mlsanity.com/paper/2406.19475/) (2024)
- [Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises](https://mlsanity.com/paper/2507.13283/) (2025)
- [The Measure of Deception: An Analysis of Data Forging in Machine Unlearning](https://mlsanity.com/paper/2509.05865/) (2025)
- [Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning](https://mlsanity.com/paper/2602.00282/) (2026)

## Abstract (arXiv)

We prove that the proximal stochastic subgradient method, applied to a weakly convex problem, drives the gradient of the Moreau envelope to zero at the rate O(k-1/4). As a consequence, we resolve an open question on the convergence rate of the proximal stochastic gradient method for minimizing the sum of a smooth nonconvex function and a convex proximable function.