Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

Abstract

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

arXiv comment32 pages

References in corpus (8)

• Deep Learning with Differential Privacy
• Private Stochastic Convex Optimization with Optimal Rates
• Data-Dependent Stability of Stochastic Gradient Descent
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• Algorithmic stability and hypothesis complexity
• Sharper bounds for uniformly stable algorithms
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Privacy-preserving Prediction

Cited by in corpus (7)

• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps
• Stability of SGD: Tightness Analysis and Improved Bounds
• Optimal Rates for Random Order Online Optimization
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics