The RDP composition theorem is the fundamental result establishing how Renyi differential privacy guarantees compose under sequential application of mechanisms. Proved as Proposition 1 in MIRONOV2017, it provides a dramatically simpler and tighter composition rule than the advanced composition theorem for standard epsilon-delta differential privacy.
The theorem states: let f: D → R_1 be (alpha, epsilon_1)-RDP and g: R_1 x D → R_2 be (alpha, epsilon_2)-RDP. Then the mechanism defined as (X, Y) where X ~ f(D) and Y ~ g(X, D) satisfies (alpha, epsilon_1 + epsilon_2)-RDP.
In other words, for any fixed order alpha, the RDP epsilon parameters simply add under adaptive sequential composition. This extends immediately to k-fold composition: k mechanisms, each satisfying (alpha, epsilon_i)-RDP, compose to (alpha, sum_{i=1}^{k} epsilon_i)-RDP.
The proof uses the multiplicative structure of the Renyi divergence. For the composed mechanism h(D) = (f(D), g(f(D), D)), one writes exp[((alpha-1)*D_alpha(h(D)||h(D’)))] as an integral over the joint output space and factors it using the data processing inequality (specifically, the analogue of Theorem 9 from the Renyi divergence literature) to obtain exp((alpha-1)*epsilon_1) * exp((alpha-1)epsilon_2) = exp((alpha-1)(epsilon_1 + epsilon_2)).
The key advantage over standard composition is the elimination of the “delta explosion” problem. Under (epsilon, delta)-DP, basic composition yields (kepsilon, kdelta)-DP (linear growth), and even advanced composition introduces additional delta’ failure probabilities. Under RDP, there is no delta at all during composition — the delta only appears at the very end when converting via the RDP to epsilon-delta DP conversion lemma. This is particularly beneficial for the Gaussian mechanism: n compositions of a Gaussian mechanism with parameter sigma yields (alpha, nalpha/(2sigma^2))-RDP, equivalent to a single Gaussian with parameter sigma/sqrt(n). The subsequent conversion to (epsilon, delta)-DP can then be optimized by choosing the best alpha for the desired delta.
Key Details
- The composition is additive for fixed alpha: (alpha, epsilon_1) + (alpha, epsilon_2) → (alpha, epsilon_1 + epsilon_2)
- The composition handles adaptive mechanisms: the choice of the second mechanism g can depend on the output of the first mechanism f
- For n identical Gaussian mechanisms with noise sigma: the composed mechanism is (alpha, nalpha/(2sigma^2))-RDP, as if using a single Gaussian with sigma/sqrt(n)
- Converting to (epsilon, delta)-DP after composition: epsilon = nalpha/(2sigma^2) + log(1/delta)/(alpha-1), optimized over alpha
- Comparison to advanced composition for the Gaussian mechanism: RDP composition gives tighter bounds across virtually all parameter regimes (see Figure 2 in MIRONOV2017)
- Heterogeneous composition is naturally supported: if mechanisms have different RDP curves, one simply sums the epsilon values at each alpha independently, then optimizes the conversion
- In certified unlearning, RDP composition governs the accumulation of privacy loss across T unlearning iterations, where each iteration contributes an (alpha, epsilon_t)-RDP guarantee from the noisy gradient or model clipping step