Research map / Federated learning and privacy / Differential privacy

Differential Privacy Guarantees of Markov Chain Monte Carlo Algorithms

ICML 2025 · Federated learning and privacy › Differential privacy · approach: Private training with public data · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives differential privacy and Rényi-DP guarantees for MCMC outputs (samples, estimators, and chain paths), and for ULA and SGLD in non-convex settings via Girsanov's theorem and a perturbation trick.

Problem

Privacy guarantees for MCMC algorithms: relating DP of the target posterior to DP of chain outputs, and obtaining uniform-in-time DP for the final state of Langevin-based samplers in non-convex, unbounded settings.

Approach

Bounds the Radon-Nikodym derivative between laws of diffusion-based chains with different datasets using Girsanov's theorem plus a perturbation of the final time step, yielding dimension-free, step-count-independent DP for the final draw; also connects posterior DP and TV convergence to chain DP.

Key results

• ULA final-state privacy is (eps_delta, delta)-DP with C_3=c^2(2(L+1)/(a-gamma L^2/2)+1)^2, independent of the number of steps n and of the state-space radius.
• Entire ULA trajectory after n steps is (alpha, alpha*C_5(n)/4)-Rényi DP with C_5(n)=n*gamma*c^2, matching Rényi composition bounds.
• Showing that if the posterior is not (eps,delta')-DP, the MCMC output after enough iterations fails (eps,delta)-DP for delta<delta' (Proposition on non-privacy).

Surprising findings

• Privacy of the final ULA draw does not depend on the number of iterations and does not blow up as the step size goes to 0, unlike earlier bounds that depend on state-space radius or step size.

Limitations

• Results require gradient-boundedness assumptions on the data-dependent part of the potential (sup |grad V| <= c), which restrict the setting.
• Privacy of the trajectory is not improved by using the stochastic gradient's randomness; authors leave this for future work.
• Bound does not improve with dataset size m in the non-strongly-convex case of noisy SGD; the dependence on m and s is an open problem.

Experimental setup

Metrics: epsilon-delta differential privacy Rényi differential privacy

Builds on: Rényi differential privacy unadjusted Langevin algorithm stochastic gradient Langevin dynamics Girsanov's theorem

Closest papers by meaning

• Differentially Private Markov Chain Monte Carlo (NeurIPS 2019 · similarity 0.93)
• Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy (ICLR 2024 · similarity 0.93)
• Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.88)
• Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.87)
• On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · similarity 0.87)
• Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.87)