Rényi Differential Privacy

The Moments Accountant is the privacy accounting algorithm that made RDP practical for deep learning. It tracks the moment-generating function of the privacy loss random variable at multiple orders (α), enabling the computation of tight bounds on the overall privacy cost after many iterations of DP-SGD.

• Computes the log moment for each α at every training step
• Converts accumulated RDP guarantees to standard (ε, δ)-DP bounds
• Provides significantly tighter composition than basic or advanced composition theorems
• Enables training deep neural networks with meaningful privacy guarantees

The Privacy Loss Distribution characterizes the full probabilistic behavior of the privacy loss random variable when a mechanism is applied to adjacent datasets. Rather than relying on worst-case bounds, it captures the entire distribution of possible privacy losses.

• Defined as the log-ratio of output probabilities on adjacent datasets
• Rényi divergence of order α is the α-moment of this distribution
• Tails of the distribution determine the (ε, δ)-DP parameters
• Precise characterization enables tight privacy accounting without overestimating risk

Subsampling amplification is a phenomenon where randomly selecting a subset of data before applying a differentially private mechanism yields a stronger overall privacy guarantee. Under RDP, subsampling provides a privacy amplification by sampling effect.

• If a mechanism satisfies (α, ε)-RDP, applying it to a random q-fraction subsample yields improved bounds
• The amplified RDP parameter depends on the sampling probability q and the order α
• Essential for DP-SGD, where each step operates on a random mini-batch
• Enables training on large datasets with per-example privacy guarantees

The Gaussian Mechanism is the fundamental building block for achieving Rényi differential privacy. It adds isotropic Gaussian noise calibrated to the L2 sensitivity of the query function.

• For a function f with L2 sensitivity Δ₂, adding noise from N(0, σ²) achieves (α, αΔ₂²/2σ²)-RDP
• The RDP parameter grows linearly with the order α
• Forms the noise injection step in DP-SGD after per-sample gradient clipping
• Preferred over the Laplace mechanism for high-dimensional queries due to L2 sensitivity scaling

The Privacy Budget is the cumulative limit on privacy loss that a system is permitted to expend. RDP provides a more accurate ledger for tracking this expenditure across composed mechanisms.

• Parameterized by ε (privacy loss) and δ (failure probability)
• RDP tracks privacy loss at multiple orders α simultaneously
• Conversion from RDP to (ε, δ)-DP allows selecting the optimal α for the tightest bound
• Exceeding the budget triggers training termination or data access restrictions

DP-SGD is the training algorithm where Rényi differential privacy finds its most critical application. It modifies standard stochastic gradient descent by clipping per-sample gradients and adding Gaussian noise, with RDP providing the tight composition analysis.

• Per-sample gradient clipping bounds the L2 sensitivity to a fixed constant C
• Gaussian noise with scale σ is added to the summed clipped gradients
• The Moments Accountant tracks RDP loss across thousands of training iterations
• Enables training deep neural networks with provable membership inference resistance