Differentially private SGD with non-smooth losses

Puyu Wang, Yunwen Lei, Yiming Ying*, Hai Zhang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

11 Citations (Scopus)

Abstract

In this paper, we are concerned with differentially private stochastic gradient descent (SGD) algorithms in the setting of stochastic convex optimization (SCO). Most of the existing work requires the loss to be Lipschitz continuous and strongly smooth, and the model parameter to be uniformly bounded. However, these assumptions are restrictive as many popular losses violate these conditions including the hinge loss for SVM, the absolute loss in robust regression, and even the least square loss in an unbounded domain. We significantly relax these restrictive assumptions and establish privacy and generalization (utility) guarantees for private SGD algorithms using output and gradient perturbations associated with non-smooth convex losses. Specifically, the loss function is relaxed to have an α-Hölder continuous gradient (referred to as α-Hölder smoothness) which instantiates the Lipschitz continuity (α=0) and the strong smoothness (α=1). We prove that noisy SGD with α-Hölder smooth losses using gradient perturbation can guarantee (ϵ,δ)-differential privacy (DP) and attain optimal excess population risk [Formula presented], up to logarithmic terms, with the gradient complexity [Formula presented]. This shows an important trade-off between α-Hölder smoothness of the loss and the computational complexity for private SGD with statistically optimal performance. In particular, our results indicate that α-Hölder smoothness with α≥1/2 is sufficient to guarantee (ϵ,δ)-DP of noisy SGD algorithms while achieving optimal excess risk with a linear gradient complexity O(n).

Original languageEnglish
Pages (from-to)306-336
Number of pages31
JournalApplied and Computational Harmonic Analysis
Volume56
Early online date15 Sept 2021
DOIs
Publication statusPublished - Jan 2022
Externally publishedYes

Scopus Subject Areas

  • Applied Mathematics

User-Defined Keywords

  • Algorithmic stability
  • Differential privacy
  • Generalization
  • Stochastic gradient descent

Fingerprint

Dive into the research topics of 'Differentially private SGD with non-smooth losses'. Together they form a unique fingerprint.

Cite this