When training machine learning models on sensitive data, every iteration—such as a gradient descent step—leaks a small amount of private information. To guarantee overall privacy, we must track how this leakage accumulates over thousands of training steps.
Under standard $(\epsilon, \delta)$-Differential Privacy (DP), tracking this cumulative loss is notoriously loose. The traditional advanced composition theorem introduces a compounding mathematical "slack" that overestimates the total privacy risk. This forces practitioners to inject excessive noise into their models, severely degrading utility.
To solve this composition bottleneck, researchers shifted from tracking $(\epsilon, \delta)$ directly during training to an alternative accounting framework: Rényi Differential Privacy (RDP). By changing the underlying metric used to measure privacy loss, RDP turns complex, loose composition curves into a simple, exact addition problem.
The Core Mechanism: Shifting the Privacy Metric
Standard $(\epsilon, \delta)$-DP bounds the probability ratio of an algorithm's outputs on two neighboring datasets (differing by just one individual) up to a factor of $e^\epsilon$, with a small failure probability $\delta$. While intuitive, the inclusion of the $\delta$ parameter makes sequential composition highly non-linear and difficult to track precisely.
RDP replaces this formulation by measuring the distance between output distributions using Rényi divergence of order $\alpha$. A mechanism satisfies $(\alpha, \chi)$-RDP if the Rényi divergence between its outputs on any two neighboring datasets is bounded by $\chi$.
This shift completely changes the geometry of privacy accounting. As shown by Bun et al. in their work on Zero-Concentrated Differential Privacy (zCDP), bounding the Rényi divergence ensures that the privacy loss random variable behaves like a subgaussian distribution. For the standard Gaussian noise mechanism used throughout deep learning, this subgaussian behavior matches the noise profile perfectly, allowing for a mathematically elegant and tight representation of privacy loss.
Why It Works: The Power of Additive Composition
The primary reason RDP has become the industry standard for privacy accounting is its composition theorem.
In standard $(\epsilon, \delta)$-DP, composing $T$ independent steps requires complex formulas that trade off increases in $\epsilon$ against increases in $\delta$. This approximation introduces loose bounds that rapidly deplete the privacy budget.
In contrast, Rényi divergence satisfies a powerful property: it is strictly additive under sequential composition. If an algorithm consists of two sequential steps where the first satisfies $(\alpha, \chi_1)$-RDP and the second satisfies $(\alpha, \chi_2)$-RDP, the entire algorithm satisfies exactly:
$$\ (\alpha, \chi_1 + \chi_2)\text{-RDP} $$
Because composition is perfectly linear, an accountant can track thousands of iterations without losing any mathematical precision to approximation slack. As noted by Stock et al., this granular tracking provides a much more precise accounting ledger, which translates directly into stronger protection for rare data samples against reconstruction attacks without requiring extra noise.
Amplification by Subsampling and Shuffling
In practical machine learning algorithms like DP-SGD, we rarely compute gradients on the entire dataset at once. Instead, we sample random minibatches. This randomness introduces an inherent layer of privacy: if an individual's data isn't selected in a given minibatch, their privacy cannot be leaked during that step. This phenomenon is known as privacy amplification.
Integrating amplification into privacy accounting requires specialized tools:
- Subsampling: Birrell et al. derived refined RDP guarantees for fixed-size minibatches sampled without replacement. Their analysis tightens computable privacy bounds by a factor of four over older methods, allowing models to achieve higher accuracy for the same privacy budget. Similarly, Huang et al. utilized RDP to track the cumulative privacy expenditure of Poisson-subsampled Latent Dirichlet Allocation (LDA) models.
- Shuffling: Privacy can also be amplified by shuffling user data anonymously in a distributed network before the central server observes it. Girgis et al. leveraged RDP to analyze this shuffle model, demonstrating significant reductions in loose privacy bounds over thousands of distributed training steps. However, as Feldman et al. pointed out, while numerical methods can estimate these shuffled bounds, finding simple, closed-form expressions remains an active area of refinement to simplify real-world deployment.
Accounting for Hyperparameter Tuning
A frequently overlooked source of privacy leakage is hyperparameter tuning. If a researcher trains a private model 50 times with different learning rates to find the best one, the final chosen model implicitly leaks information from all 50 runs.
RDP provides a rigorous way to account for this multi-run leakage. Papernot et al. developed an RDP framework for hyperparameter selection, proving that by randomizing the number of training runs, practitioners can find optimal configurations with only a minimal "privacy tax." To optimize this further, Koskela et al. designed accounting workflows that split data into disjoint partitions for tuning and final training, exploiting the structural properties of RDP composition to avoid wasting the core privacy budget.
The Final Step: Converting Back to Standard DP
While RDP is an exceptional internal ledger for tracking privacy loss during computation, the broader privacy community and regulatory frameworks rely on standard $(\epsilon, \delta)$-DP metrics. Therefore, at the very end of the training process, the accumulated RDP bound must be translated back.
Iterative Steps (DP-SGD)
│
▼
Add up RDP bounds exactly: (α, χ₁) + (α, χ₂) + ... = (α, χ_total)
│
▼
Convert to standard DP via optimal α selection ──► Final (ε, δ)-DP Guarantee
This conversion is done by finding the optimal order $\alpha$ that minimizes the resulting $\epsilon$ for a target $\delta$. Balle et al. bridged the gap between these frameworks by providing refined mathematical conversion rules based on hypothesis testing interpretations. These tighter conversion bounds ensure that practitioners do not lose the precision gained during the RDP accounting phase when reporting their final $(\epsilon, \delta)$ parameters.
By acting as a lossless intermediate representation, Rényi Differential Privacy allows complex iterative algorithms—ranging from alternating direction optimization (Shang et al.) to interactive stochastic processes (Lyu)—to maintain high utility while providing mathematically rigorous, tight privacy guarantees.
Key Foundational Work
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds (2016) — contributed 2 concept elements to this direction.
Scalable Private Learning with PATE (2018) — contributed 1 concept elements to this direction.