Privacy Amplification via Iteration for Shuffled and Online PNSGD

Matteo Sordello, Zhiqi Bu, Jinshuo Dong

Abstract

This paper provides the first formal privacy guarantees for shuffled and online Projected Noisy Stochastic Gradient Descent (PNSGD). By leveraging the principle of privacy amplification via iteration, the authors prove that data shuffling yields tighter privacy bounds than previously studied methods. Additionally, the work introduces specific noise-decay schemes that maintain constant privacy loss in online settings as datasets grow indefinitely.

1. Introduction

In Differential Privacy (DP), privacy loss is typically tracked using composition theorems, which can be overly pessimistic. Privacy amplification via iteration suggests that if intermediate updates are hidden, the iterative nature of algorithms like SGD naturally obscures individual data contributions. This paper addresses two critical gaps: the effect of shuffling—a standard practice in machine learning—and the maintenance of privacy in continuous online learning scenarios.

2. Methods and Framework

The authors analyze Projected Noisy Stochastic Gradient Descent (PNSGD), which incorporates noise injection (Gaussian or Laplace) and projection onto a convex constraint set. The mathematical framework utilizes the contraction coefficient of Markov kernels under hockey-stick divergence ($E_\gamma$-divergence).

2.1 Shuffled Analysis

Shuffling is modeled as a uniform probability that a differing data point appears at any position in a sequence. Using Jensen’s inequality, the privacy loss is averaged across all permutations, leading to a more reliable privacy-strengthening effect than random stopping.

2.2 Online Learning Analysis

For streaming data, the authors derive noise-decay rates—specifically using the Lambert W function for Gaussian noise—to ensure that the cumulative privacy loss ($\delta$) converges to a non-zero constant as the number of samples ($n$) approaches infinity.

3. Key Results

3.1 Shuffling as a Privacy Multiplier

The study demonstrates that shuffling is a superior privacy mechanism. It provides a tighter privacy bound than "randomly-stopped" PNSGD. This is validated through simulations on Linear and Logistic Regression tasks, where shuffling not only provides better privacy but also maintains competitive model performance.

Performance comparison of Shuffled vs. Randomly-Stopped PNSGD on Linear and Logistic Regression tasks.

3.2 Convergence and Online Stability

The paper proves that for Laplace noise, privacy loss $\delta$ converges at a rate of $1/n$, while Gaussian noise converges at $1/\log(n)$. The online noise-decay scheme allows systems to remain private indefinitely without requiring excessive noise that would degrade model utility.

Convergence of privacy loss delta and the decay of the gap as a function of the number of samples n.

4. Discussion and Limitations

While "amplification via iteration" provides significant benefits, it relies on the assumption that intermediate model weights are never revealed. If an adversary can observe the model after every gradient step, the tighter bounds are lost. Future work remains to unify these results with multi-epoch training and further refine the conservative upper bounds found in the online analysis.

Summary updated

BibTeX
@inproceedings{sordello2021privacy,
  author = {Matteo Sordello and Zhiqi Bu and Jinshuo Dong},
  title = {{Privacy Amplification via Iteration for Shuffled and Online PNSGD}},
  booktitle = {ECML/PKDD},
  year = {2021},
  doi = {10.1007/978-3-030-86520-7\_49},
}
Figure