Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC

Arun Ganesh, Kunal Talwar

Introduction

In Differential Privacy (DP), the Exponential Mechanism is a fundamental tool used to select an output that maximizes a specific "score function" $f$ while maintaining strict privacy guarantees. Implementing this mechanism requires sampling from a distribution proportional to $\exp(-f)$.

However, in high-dimensional spaces, this sampling process is computationally brutal. While practitioners often rely on fast Markov Chain Monte Carlo (MCMC) methods like Gibbs sampling, these heuristics lack formal privacy proofs. Conversely, theoretical computer science provides "log-concave" samplers with rigorous proofs, but their runtime scales poorly with dimension (e.g., $d^3$ or higher), rendering them impractical for real-world applications.

Langevin dynamics-based algorithms offer a much faster alternative in practice. Yet, their convergence is traditionally measured using "statistical distance" or "Wasserstein distance"—metrics that are insufficiently strong to guarantee Differential Privacy. To prove an algorithm is $(\epsilon, \delta)$-DP, one typically needs to bound the Rényi divergence. Until this paper, it remained unclear whether the "noise" introduced by discretizing the continuous Langevin process into discrete computational steps would destroy these crucial privacy properties. This work provides the first rigorous proof that discretized Langevin MCMC converges quickly under Rényi divergence, enabling high-speed samplers for the Exponential Mechanism with provable privacy and near-linear dimensional scaling.

Methodology

The authors analyze two distinct versions of Langevin MCMC:

  1. Overdamped: A first-order Langevin process.
  2. Underdamped: A second-order process that includes a "velocity" term to accelerate movement through the state space.

Their core technical innovation is a novel "continuous-to-discrete" comparison. Rather than attempting the difficult task of proving the discrete chain converges directly to the target (which is complicated by the discrete chain converging to a slightly biased distribution), they bound the Rényi divergence between the discrete steps and the continuous path. They rely on existing literature demonstrating that the continuous Langevin process converges rapidly to the target distribution in Rényi divergence.

Furthermore, because Brownian motion can occasionally cause massive jumps that violate standard smoothness assumptions, the authors develop a novel "unconditioning" lemma. This technique allows them to translate probabilistic tail bounds (limits on how far the sampler moves) into a deterministic bound on the Rényi divergence.

Key Insights

  • Privacy Tools for Algorithm Analysis: In an interesting twist, the authors utilize tools originating from the differential privacy literature (such as Rényi divergence properties) to analyze the convergence of the sampling algorithm itself.
  • Bypassing Stationary Bias: Most MCMC analyses struggle with "stationary distribution bias"—the reality that a discrete computer simulation never perfectly matches continuous physics. By comparing the discrete run to a finite-time continuous run rather than the infinite-time stationary distribution, they successfully bypass this hurdle.
  • Near-Linear Scaling: For smooth, strongly-convex functions, the number of iterations required scales near-linearly with the dimension ($d$). This is a massive leap forward from previous "polynomial-time" samplers that were theoretically sound but practically unusable.

Key Results

The paper establishes new upper bounds on the iteration complexity required to achieve a specific level of Rényi divergence (denoted by $\epsilon$ or $\varepsilon$).

Summary of iteration complexities for Overdamped and Underdamped Langevin MCMC to achieve Rényi divergence bounds.

As detailed in the table above, the authors prove the following complexities:

  • Overdamped Langevin: For a 1-strongly convex and $L$-smooth function, the iteration complexity is roughly $\tilde{O}(\frac{d \cdot \text{poly}(L)}{\epsilon^2})$.
  • Underdamped Langevin: The underdamped process achieves a quadratically better scaling with respect to dimension and error, requiring only $\tilde{O}(\frac{\sqrt{d} \cdot \text{poly}(L)}{\epsilon})$ iterations.

When applied to specific downstream tasks like Differentially Private Principal Component Analysis (DP PCA), these results dramatically improve the iteration complexity from previous bounds of $\tilde{O}(d^3/\delta^2)$ down to $\tilde{O}(d/\zeta^4)$, where $\zeta$ represents the privacy parameter.

Limitations and Future Work

While a significant theoretical breakthrough, the current proofs require the function $f$ to be both smooth and strongly convex. Many real-world machine learning landscapes involve non-convex or non-smooth functions.

Additionally, there is an "$\epsilon$ gap": the iteration complexity scales with $1/\epsilon^2$. Recent non-privacy-focused work suggests $1/\sqrt{\epsilon}$ might be achievable for KL-divergence, and the authors acknowledge their "unconditioning" argument might inherently sacrifice some efficiency here. Finally, while they prove the process is close to the target, whether the stationary distribution of the discrete chain itself is close in Rényi divergence remains an open theoretical question.

Summary updated

Abstract

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 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.
BibTeX
@inproceedings{ganesh2020faster,
  author = {Arun Ganesh and Kunal Talwar},
  title = {{Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=9zuPbp-0D9d},
}
Figure