# Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC

arXiv: https://arxiv.org/abs/2010.14658 · HTML: https://mlsanity.com/paper/2010.14658/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

## Built on by (most cited first, 27 of 27)

- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [One Parameter Defense -- Defending against Data Inference Attacks via Differential Privacy](https://mlsanity.com/paper/2203.06580/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Certified Machine Unlearning via Noisy Stochastic Gradient Descent](https://mlsanity.com/paper/2403.17105/) (2024)
- [Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks](https://mlsanity.com/paper/2310.20579/) (2023)
- [Sampling from Log-Concave Distributions with Infinity-Distance Guarantees](https://mlsanity.com/paper/2111.04089/) (2021)
- [The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models](https://mlsanity.com/paper/2405.17068/) (2024)
- [Convergence of the Inexact Langevin Algorithm in KL Divergence with Application to Score-based Generative Models](https://mlsanity.com/paper/2211.01512/) (2022)
- [Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization](https://mlsanity.com/paper/2204.01585/) (2022)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Can Stochastic Gradient Langevin Dynamics Provide Differential Privacy for Deep Learning?](https://mlsanity.com/paper/2110.05057/) (2021)
- [Privacy Risk for anisotropic Langevin dynamics using relative entropy bounds](https://mlsanity.com/paper/2302.00766/) (2023)
- [Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk](https://mlsanity.com/paper/2206.09384/) (2022)
- [Recycling Scraps: Improving Private Learning by Leveraging Intermediate Checkpoints](https://mlsanity.com/paper/2210.01864/) (2022)
- [Differentially Private Topological Data Analysis](https://mlsanity.com/paper/2305.03609/) (2023)
- [Differentially Private Statistical Inference through β-Divergence One Posterior Sampling](https://mlsanity.com/paper/2307.05194/) (2023)
- [Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds](https://mlsanity.com/paper/2506.07614/) (2025)
- [R'enyi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincar'e Inequalities](https://mlsanity.com/paper/2511.15634/) (2025)
- [On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacy](https://mlsanity.com/paper/2605.23879/) (2026)

## Abstract (arXiv)

Various differentially private algorithms instantiate the exponential mechanism, and require sampling from the distribution exp(-f) for a suitable function f. When the domain of the distribution is high-dimensional, this sampling can be computationally challenging. Using heuristic sampling schemes such as Gibbs sampling does not necessarily lead to provable privacy. When f is convex, techniques from log-concave sampling lead to polynomial-time algorithms, albeit with large polynomials. Langevin dynamics-based algorithms offer much faster alternatives under some distance measures such as statistical distance. In this work, we establish rapid convergence for these algorithms under distance measures more suitable for differential privacy. For smooth, strongly-convex f, we give the first results proving convergence in R'enyi divergence. This gives us fast differentially private algorithms for such f. Our techniques and simple and generic and apply also to underdamped Langevin dynamics.