# Stochastic subgradient method converges on tame functions

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

## Key facts

- Cited by 124 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2018.

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

- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [Nonsmooth Implicit Differentiation for Machine Learning and Optimization](https://mlsanity.com/paper/2106.04350/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [Training invariances and the low-rank phenomenon: beyond linear networks](https://mlsanity.com/paper/2201.11968/) (2022)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networks](https://mlsanity.com/paper/2210.03820/) (2022)
- [Adam with model exponential moving average is effective for nonconvex optimization](https://mlsanity.com/paper/2405.18199/) (2024)
- [A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians](https://mlsanity.com/paper/2106.13015/) (2021)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [Adam-family Methods for Nonsmooth Optimization with Convergence Guarantees](https://mlsanity.com/paper/2305.03938/) (2023)
- [Towards Understanding Learning in Neural Networks with Linear Teachers](https://mlsanity.com/paper/2101.02533/) (2021)
- [Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2410.22069/) (2024)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [Asymptotic normality and optimality in nonsmooth stochastic approximation](https://mlsanity.com/paper/2301.06632/) (2023)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Improving Metric Dimensionality Reduction with Distributed Topology](https://mlsanity.com/paper/2106.07613/) (2021)
- [Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization](https://mlsanity.com/paper/2108.11832/) (2021)
- [Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networks](https://mlsanity.com/paper/2402.09226/) (2024)
- [The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks](https://mlsanity.com/paper/2602.16340/) (2026)
- [Adversarial Reprogramming Revisited](https://mlsanity.com/paper/2206.03466/) (2022)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions](https://mlsanity.com/paper/2108.02072/) (2021)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Importance Tempering: Group Robustness for Overparameterized Models](https://mlsanity.com/paper/2209.08745/) (2022)

## Abstract (arXiv)

This work considers the question: what convergence guarantees does the stochastic subgradient method have in the absence of smoothness and convexity? We prove that the stochastic subgradient method, on any semialgebraic locally Lipschitz function, produces limit points that are all first-order stationary. More generally, our result applies to any function with a Whitney stratifiable graph. In particular, this work endows the stochastic subgradient method, and its proximal extension, with rigorous convergence guarantees for a wide class of problems arising in data science---including all popular deep learning architectures.