# Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

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

## Key facts

- Cited by 173 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

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

- [Detecting Pretraining Data from Large Language Models](https://mlsanity.com/paper/2310.16789/) (2023)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Stochastic Training is Not Necessary for Generalization](https://mlsanity.com/paper/2109.14119/) (2021)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (2022)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Private Fine-tuning of Large Language Models with Zeroth-order Optimization](https://mlsanity.com/paper/2401.04343/) (2024)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [Stability Analysis and Generalization Bounds of Adversarial Training](https://mlsanity.com/paper/2210.00960/) (2022)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)

## Abstract (arXiv)

Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. An influential work of Hardt et al. (2016) provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses. Our work is the first to address uniform stability of SGD on em nonsmooth convex losses. Specifically, we provide sharp upper and lower bounds for several forms of SGD and full-batch GD on arbitrary Lipschitz nonsmooth convex losses. Our lower bounds show that, in the nonsmooth case, (S)GD can be inherently less stable than in the smooth case. On the other hand, our upper bounds show that (S)GD is sufficiently stable for deriving new and useful bounds on generalization error. Most notably, we obtain the first dimension-independent generalization bounds for multi-pass SGD in the nonsmooth case. In addition, our bounds allow us to derive a new algorithm for differentially private nonsmooth stochastic convex optimization with optimal excess population risk. Our algorithm is simpler and more efficient than the best known algorithm for the nonsmooth case Feldman et al. (2020).