Differential Privacy of Noisy (S)GD under Heavy-Tailed Perturbations
Umut Şimşekli Mert Gürbüzbalaban Sinan Yıldırım Lingjiong Zhu
Injecting heavy-tailed noise to the iterates of stochastic gradient descent
(SGD) has received increasing attention over the past few years. While various
theoretical properties of the resulting algorithm have been analyzed mainly
from learning theory and optimization perspectives, their privacy preservation
properties have not yet been established. Aiming to bridge this gap, we provide
differential privacy (DP) guarantees for noisy SGD, when the injected noise
follows an $\alpha$-stable distribution, which includes a spectrum of
heavy-tailed distributions (with infinite variance) as well as the Gaussian
distribution. Considering the $(\epsilon, \delta)$-DP framework, we show that
SGD with heavy-tailed perturbations achieves $(0, \tilde{\mathcal{O}}(1/n))$-DP
for a broad class of loss functions which can be non-convex, where $n$ is the
number of data points. As a remarkable byproduct, contrary to prior work that
necessitates bounded sensitivity for the gradients or clipping the iterates,
our theory reveals that under mild assumptions, such a projection step is not
actually necessary. We illustrate that the heavy-tailed noising mechanism
achieves similar DP guarantees compared to the Gaussian case, which suggests
that it can be a viable alternative to its light-tailed counterparts.