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.
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.
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