Privacy Amplification by Mixing and Diffusion Mechanisms

Borja Balle, Gilles Barthe, Marco Gaboardi, Joseph Geumlek

Introduction

In the realm of Differential Privacy (DP), the "post-processing inequality" serves as a foundational safety net: it guarantees that if a mechanism is private, any further computation on its output will not degrade that privacy. However, this rule is often pessimistic. When post-processing involves randomness—such as adding noise or running a stochastic algorithm—the final result is frequently significantly more private than the initial output.

While it is a well-known rule that you cannot break privacy by post-processing data, this paper explores the opposite phenomenon: when does post-processing actually improve privacy? Historically, quantifying this "privacy amplification" has been challenging. Although specific rules exist for operations like subsampling or shuffling data, the field has lacked a general, systematic framework for understanding how stochastic transitions (modeled as Markov operators) "forget" sensitive information over time. By applying tools from Markov chain theory and diffusion processes, the authors provide new, tighter bounds for iterative algorithms like Noisy Stochastic Gradient Descent (SGD) and introduce a novel "Ornstein-Uhlenbeck" mechanism.

Methodological Framework

The authors approach the problem of privacy amplification through three distinct mathematical lenses:

1. Uniform Mixing The paper treats post-processing as a Markov operator $K$. If $K$ satisfies certain "mixing" conditions (such as the Dobrushin or Doeblin conditions), the process quickly loses track of its starting state. The authors successfully translate these classical probability concepts into formal DP amplification bounds.

Mapping between classical mixing conditions and Local Differential Privacy (LDP) bounds.

2. Coupling Arguments Because uniform mixing is often too strict for continuous spaces (like $\mathbb{R}^d$), the authors employ "couplings"—a technique for comparing two different probability distributions by observing how they evolve together. This approach allows them to analyze Rényi Differential Privacy (RDP) for iterative maps, such as those commonly found in machine learning optimization.

3. Diffusion Mechanisms Moving into continuous-time territory, the authors examine diffusion processes defined by Stochastic Differential Equations (SDEs). They utilize a "heat flow" argument to demonstrate how privacy guarantees evolve and strengthen as a process diffuses over time.

Key Insights and Results

As a theoretical paper focused on mathematical proofs and algorithmic analysis, the study does not rely on empirical datasets. Instead, its results are expressed through mathematical theorems and comparisons of error rates (e.g., Mean Squared Error) between different privacy mechanisms.

  • The "Forgetfulness" Factor: The core insight of the paper is that privacy amplification is fundamentally analogous to "mixing" in Markov chains. If a process is sufficiently "forgetful" that two different starting points eventually converge to look the same, it effectively hides the influence of any single individual's data.
  • Tighter Bounds for Iteration: The authors provide a generalized "shift-reduction lemma" that operates in general measure-theoretic settings, extending beyond standard normed vector spaces.
  • Exponential Gains in Noisy SGD: One of the most impactful findings relates to Noisy Projected Stochastic Gradient Descent. For "strongly convex" loss functions (a common class in machine learning), the authors prove that privacy improves exponentially with the number of iterations. Specifically, the privacy parameter $\epsilon$ at index $i$ improves at an exponential rate $O((1 - \eta\rho)^{n-i})$, where $\eta$ is the learning rate and $\rho$ is the strong convexity parameter. Previous work had only suggested a much slower, linear improvement.
  • The Ornstein-Uhlenbeck (OU) Mechanism: The paper introduces a new mechanism based on the OU process—a "mean-reverting" diffusion that pulls values toward a center while adding noise. The authors prove this mechanism is "uniformly better" than the standard Gaussian mechanism in certain settings (specifically when inputs are bounded) because it naturally trades off bias and variance to achieve a lower total Mean Squared Error (MSE). It effectively matches the performance of an "optimally" post-processed Gaussian mechanism.

Limitations and Future Directions

While the theoretical contributions are significant, the authors note a few limitations and areas for future exploration:

  • Bias in the OU Mechanism: Unlike the standard Gaussian mechanism, the Ornstein-Uhlenbeck mechanism is biased, as it pulls the answer toward the origin. While this characteristic aids privacy and can reduce total error, it may not be suitable for applications where strict unbiasedness is required.
  • Stringency of Mixing Conditions: The authors acknowledge that "uniform mixing" conditions are often too harsh for practical high-dimensional settings. This limitation motivated their pivot to coupling and diffusion arguments to derive more practical results.
  • Future Work: The authors suggest applying these techniques to "Hierarchical Differential Privacy," a scenario where data might be released to different groups (e.g., internal teams versus the public) under increasingly strict privacy constraints. They also highlight the potential of exploring more complex, non-symmetric diffusion processes to further expand the toolkit for privacy amplification.

Summary updated

Abstract

A fundamental result in differential privacy states that the privacy guarantees of a mechanism are preserved by any post-processing of its output. In this paper we investigate under what conditions stochastic post-processing can amplify the privacy of a mechanism. By interpreting post-processing as the application of a Markov operator, we first give a series of amplification results in terms of uniform mixing properties of the Markov process defined by said operator. Next we provide amplification bounds in terms of coupling arguments which can be applied in cases where uniform mixing is not available. Finally, we introduce a new family of mechanisms based on diffusion processes which are closed under post-processing, and analyze their privacy via a novel heat flow argument. On the applied side, we generalize the analysis of "privacy amplification by iteration" in Noisy SGD and show it admits an exponential improvement in the strongly convex case, and study a mechanism based on the Ornstein-Uhlenbeck diffusion process which contains the Gaussian mechanism with optimal post-processing on bounded inputs as a special case.
BibTeX
@inproceedings{balle2019privacy,
  author = {Borja Balle and Gilles Barthe and Marco Gaboardi and Joseph Geumlek},
  title = {{Privacy Amplification by Mixing and Diffusion Mechanisms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure