论文标题
通过离散的Langevin MCMC进行差异差异分析差异私人采样器
Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
论文作者
论文摘要
各种差异性私有算法实例化了指数机制，并需要从分发$ \ exp（-f）$进行合适的功能$ f $的采样。当分布的域是高维的时，该采样在计算上可能具有挑战性。使用诸如Gibbs抽样之类的启发式抽样方案并不一定会带来可证明的隐私。当$ f $是凸面时，尽管具有较大的多项式，但来自log-concave采样的技术导致多项式时间算法。基于Langevin动力学的算法在统计距离之类的距离测量中提供了更快的替代方法。在这项工作中，我们在距离测量中为这些算法建立了快速的融合，更适合差异隐私。对于平滑，强烈的convex $ f $，我们给出了第一个结果，证明了RényiDivergence的融合。这为我们提供了这种$ f $的快速差异私人算法。我们的技术，简单而通用，也适用于阻尼不足的Langevin动力学。
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ényi divergence. This gives us fast differentially private algorithms for such $f$. Our techniques and simple and generic and apply also to underdamped Langevin dynamics.
