Privacy amplification by iteration (PABI) is a technique showing that iterative noisy algorithms become more private as they run longer, because each contractive noisy iteration brings the process closer to its stationary distribution, amplifying the privacy guarantee beyond what composition theorems yield.
The key result (Feldman, Mironov, Talwar & Thakurta, 2018; refined by Altschuler & Talwar, 2022) states: for two contractive noisy iteration processes X_K and X_K’ with c-contractive updates, Gaussian noise ζ_k ~ N(0, σ²I_d), and initial W∞ distance Z, the Rényi divergence satisfies D_α(X_K || X_K’) ≤ αZ²/(2σ²) · c^{2K} when c < 1.
Key Details
- Contractive Noisy Iteration (c-CNI): X_{k+1} = ψ_{k+1}(X_k) + W_{k+1} where ψ_k is c-Lipschitz and W_k ~ ζ_k
- Strong convexity (c < 1): Exponential decay c^{2K} in Rényi divergence
- Convexity (c = 1): Linear decay 1/K in Rényi divergence
- Metric-aware: Uses W∞ distance as the initial divergence measure, not total variation or KL
- Connection to mixing time: Closely related to convergence analysis of Langevin Monte Carlo
- Critical for machine unlearning: converts geometric proximity of adjacent processes into Rényi privacy loss