Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

Simple item page
dc.catalogadorfcr
dc.contributor.authorRaef Bassily
dc.contributor.authorVitaly Feldman
dc.contributor.authorGuzman Paredes, Cristobal Andres
dc.contributor.authorKunal Talwar
dc.date.accessioned2024-03-05T15:15:02Z
dc.date.available2024-03-05T15:15:02Z
dc.date.issued2020
dc.description.abstractUniform 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 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 bound 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, due to Feldman et al. [2020].
dc.fechaingreso.objetodigital2024-03-21
dc.fuente.origenORCID
dc.identifier.doi10.48550/arXiv.2006.06914
dc.identifier.urihttps://utwente-staging.elsevierpure.com/en/publications/a6913e6c-8ad8-4a4a-9ed3-bf0c67cff067
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/84095
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Guzman Paredes, Cristobal Andres; 0000-0002-1498-2055; 1041986
dc.language.isoen
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.titleStability of Stochastic Gradient Descent on Nonsmooth Convex Losses
dc.typecomunicación de congreso
sipa.codpersvinculados1041986
sipa.trazabilidadORCID;2024-01-22
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses.pdf
Size:
380.6 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de conferencia