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

Arun Ganesh, Kunal Talwar

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 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.

Introduction

Differentially private (DP) algorithms often rely on the Exponential Mechanism, which necessitates sampling from a distribution proportional to $\exp(-f(x))$. In high-dimensional settings, this sampling step frequently becomes a major computational bottleneck. While heuristic methods like Gibbs sampling are common in practice, they lack the rigorous convergence proofs required to formally guarantee privacy. Existing "provably private" samplers often utilize classical log-concave sampling techniques that, while polynomial-time, involve high-degree polynomials (e.g., $d^{10}$ or $d^3$), rendering them impractical for large-scale applications.

Furthermore, most recent analyses of "fast" Markov Chain Monte Carlo (MCMC) focus on statistical distance or Wasserstein distance. These metrics are insufficient for DP; a sampler might be close in statistical distance but still leak significant private information. DP necessitates closeness in more stringent measures like Rényi divergence, which effectively bounds the "worst-case" ratio between distributions. This paper provides the first rapid convergence guarantees for Langevin MCMC algorithms under Rényi divergence.

Methodology: Path-Based Analysis

The authors analyze two primary algorithms: Overdamped Langevin Dynamics (analogous to noisy gradient descent) and Underdamped Langevin Dynamics (which incorporates a "momentum" or velocity term).

The core methodological innovation is a "path-based" analysis. Rather than attempting to prove that the discrete algorithm's stationary distribution is close to the target—a difficult task due to discretization bias—the authors bound the Rényi divergence between the discrete process (the actual algorithm) and the continuous process (the idealized physics-based path).

Since the continuous process is known to converge rapidly to the target distribution in Rényi divergence, the challenge shifts to proving that the discrete steps do not drift significantly from the continuous flow. The authors employ tools similar to those used in DP composition, such as the Adaptive Composition Theorem, to aggregate the divergence introduced at each discrete step. Additionally, they introduce an "unconditioning" trick—a lemma that translates conditional moment bounds into unconditional Rényi divergence bounds—to handle potential large jumps caused by Brownian motion.

Key Results and Complexity Bounds

The analysis yields the first Rényi convergence results for smooth and strongly convex functions using discretized Langevin MCMC. A significant finding is that momentum matters: while the overdamped version scales roughly linearly with the dimension $d$, the underdamped version achieves a square-root speedup, scaling with $\sqrt{d}$.

Summary of step sizes (\eta) and iteration complexities for discretized Langevin dynamics under different assumptions.

As shown in the table above, for the overdamped case with 1-strongly convex functions, the iteration complexity is approximately $\tilde{O}(d/\epsilon^2)$. In the underdamped case, this improves to $\tilde{O}(\sqrt{d}/\epsilon)$, offering significantly better scaling for high-dimensional problems. These results directly improve the efficiency of DP mechanisms. For instance, applying these bounds to known DP mechanisms for mean estimation and logistic regression improves proven iteration complexity from $\tilde{O}(d^3)$ to $\tilde{O}(d)$.

Discussion and Limitations

While this work marks a significant advancement, several areas for future research remain:

  • Dependence on $\epsilon$: The iteration complexity for the overdamped case scales with $1/\epsilon^2$, which is slower than some results for weaker distance measures like KL divergence (which can reach $1/\sqrt{\epsilon}$). This may be an inherent cost of the "unconditioning" argument.
  • Strong Convexity Assumption: The primary results assume $f$ is smooth and strongly convex. Although a basic result for Lipschitz functions is provided, extending high-efficiency guarantees to non-convex or non-smooth functions is an open challenge.
  • Stationary Distribution Gap: The proof demonstrates that the process is close to the target at a specific time $T$, but it remains unknown if the stationary distribution of the discrete chain itself is close in Rényi divergence.

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 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.
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