# Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2017.

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

- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation](https://mlsanity.com/paper/2205.00107/) (2022)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Learning Proximal Operators to Discover Multiple Optima](https://mlsanity.com/paper/2201.11945/) (2022)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions](https://mlsanity.com/paper/2405.18577/) (2024)
- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [Coordinate Descent Methods for Fractional Minimization](https://mlsanity.com/paper/2201.12691/) (2022)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Finding a stationary point of a stochastic convex problem](https://mlsanity.com/paper/2607.06883/) (2026)
- [Musec: MomentUm SpEctral Clipping for Stable Muon-type Training](https://mlsanity.com/paper/2609.11655/) (2026)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)
- [Singularity-aware Optimization via Randomized Geometric Probing: Towards Stable Non-smooth Optimization](https://mlsanity.com/paper/2605.29547/) (2026)
- [Robust Regression via Model Based Methods](https://mlsanity.com/paper/2106.10759/) (2021)
- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)
- [On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2409.10323/) (2024)
- [Learning-Based Surrogate Method for Stochastic Optimization under Decision-Dependent Uncertainty with Adaptive Random Designs](https://mlsanity.com/paper/2505.07298/) (2025)
- [Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2506.02504/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2605.24513/) (2026)
- [A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2608.05460/) (2026)

## Abstract (arXiv)

In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex composite classes. At a high-level, the method is an inexact proximal point iteration in which the strongly convex proximal subproblems are quickly solved with a specialized stochastic projected subgradient method. The primary contribution of this paper is a simple proof that the proposed algorithm converges at the same rate as the stochastic gradient method for smooth nonconvex problems. This result appears to be the first convergence rate analysis of a stochastic (or even deterministic) subgradient method for the class of weakly convex functions.