Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
  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).
