Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

By Raef Bassily, Vitaly Feldman, Crist'obal Guzm'an, Kunal Talwar. 2020

235 citations recorded by the source corpus.

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).

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “√ While the results in [7, 8, 29] have a tighter (and optimal) excess population risk of (cid:101) Θ(1 / n + √ p/ ( εn )) , they either require convexity to ensure privacy for a single pass algorithm, or need to make n -passes over the data.”
Detecting Pretraining Data from Large Language Models (2023, background): “This aligns with findings that LMs better memorize tail outliers (Feldman, 2020; Zhang et al., 2021).”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “For example Bassily et al. (2014) show that training larger models results in worse generalization when using DP training. This is due to the fact that the norm of the noise needed for DP training is proportional to the (square root of) the number of model parameters Bassily et al. (2014); Tramèr & ”