Composition of Differential Privacy & Privacy Amplification by Subsampling

Thomas Steinke, Thomas Steinke 0002arXiv 2022 · DOI · arXiv

Introduction

In the field of data privacy, the fundamental challenge is not merely protecting a single data point during a single analysis, but ensuring that privacy remains intact across a sequence of many analyses. This challenge, known as the composition problem, is the central focus of Thomas Steinke’s work on privacy accounting. As data systems become increasingly complex—particularly in the training of large-scale machine learning models—the ability to rigorously calculate and bound the cumulative privacy loss is essential. This paper explores the mathematical frameworks that allow for tight privacy guarantees, moving beyond pessimistic bounds to enable practical, privacy-preserving AI.

The Composition Problem and the Limits of Basic Accounting

Differential Privacy (DP) provides a mathematically rigorous definition of privacy, typically parameterized by $\epsilon$ (the privacy loss). However, privacy does not exist in a vacuum. When multiple queries are made against the same sensitive dataset, an adversary can potentially combine the outputs to "triangulate" specific individual information—a phenomenon known as a differencing attack.

In the earliest iterations of DP, the Basic Composition theorem was the primary tool for accounting. It states that if you run $k$ analyses, each with a privacy cost of $\epsilon$, the total privacy cost is simply the sum: $k\epsilon$. While mathematically sound, this linear growth is often too pessimistic for modern applications. For a machine learning model involving thousands of training steps, basic composition would result in a privacy budget so depleted that the model would require an unusable amount of noise to remain "safe."

Advanced Accounting Frameworks

To address the inefficiency of basic composition, Steinke details several advanced mathematical techniques that provide much tighter, more realistic bounds on privacy loss.

Privacy Loss Distributions (PLDs)

One of the most powerful shifts in privacy accounting is treating privacy loss not as a fixed scalar, but as a random variable. By analyzing the Privacy Loss Distribution (PLD), researchers can use the laws of probability to observe how privacy loss "concentrates" over time. The paper demonstrates that when multiple independent private algorithms are executed, the total privacy loss is the convolution of their individual PLDs. This perspective allows for the application of tools similar to the Central Limit Theorem, showing that as the number of queries increases, the total loss distribution tends toward a Gaussian shape, which is significantly easier to bound than a simple linear sum.

Rényi and Concentrated DP

Building on the PLD concept, the paper highlights Rényi Differential Privacy (RDP) and Zero-Concentrated Differential Privacy (zCDP). These are "relaxed" versions of the standard DP definition designed specifically to handle composition elegantly. In these frameworks, the privacy loss of the Gaussian mechanism—the workhorse of private machine learning—can be tracked with near-perfect precision. This leads to the "$\sqrt{k}$ advantage": for approximate DP, the privacy loss grows closer to the square root of the number of queries ($k$) rather than linearly, which is the difference between a functional model and one overwhelmed by noise.

Privacy Amplification by Subsampling

A critical component of making DP practical for deep learning is Privacy Amplification by Subsampling. In many algorithms, such as Stochastic Gradient Descent (SGD), the model only observes a small random subset (a "minibatch") of the data at each step.

The paper provides a rigorous analysis of Poisson Subsampling, proving that if an algorithm only looks at a small fraction of the data, the privacy guarantee is amplified. Intuitively, if a specific individual's data is only included in a 1% sample, an attacker faces the immediate uncertainty of whether that individual was even part of the computation. Steinke provides "sharp" formulas for this amplification, which serve as the mathematical engine for modern privacy libraries like TensorFlow Privacy and PyTorch’s Opacus.

Theoretical and Practical Significance

The implications of these frameworks are both theoretical and practical:

  • Optimality: The paper proves that the $\sqrt{k}$ scaling for error in private mean estimation is asymptotically optimal; no algorithm can achieve better accuracy without violating the privacy constraint.
  • Adaptive Composition: Crucially, these bounds hold even under adaptive composition, where a researcher chooses their next query based on the results of previous ones. This is vital for the iterative nature of scientific discovery and model tuning.
  • Unified View: The work connects disparate mathematical concepts—such as Hockey-stick divergence, KL-divergence, and Total Variation distance—into a unified view of privacy through the lens of the PLD.

Conclusion and Future Directions

While the mathematical foundations for privacy accounting are now robust, challenges remain in implementation. Calculating exact optimal composition for heterogeneous algorithms (where each step has a different $\epsilon$) is computationally difficult (#P-complete). Current research focuses on using Fourier transforms to approximate these bounds efficiently. Furthermore, while this work focuses on the "central" model of DP, future extensions into "local" DP and "shuffling" mechanisms continue to build upon these core composition principles. Ultimately, these mathematical tools act as the "glue" that allows us to build complex, multi-step data systems without sacrificing individual privacy.

Summary updated

Abstract

This chapter is meant to be part of the book "Differential Privacy for Artificial Intelligence Applications." We give an introduction to the most important property of differential privacy -- composition: running multiple independent analyses on the data of a set of people will still be differentially private as long as each of the analyses is private on its own -- as well as the related topic of privacy amplification by subsampling. This chapter introduces the basic concepts and gives proofs of the key results needed to apply these tools in practice.
BibTeX
@misc{steinke2022composition,
  author = {Thomas Steinke and Thomas Steinke},
  title = {{Composition of Differential Privacy \& Privacy Amplification by Subsampling}},
  year = {2022},
  eprint = {2210.00597},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.00597},
}
Figure