Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
Arun Ganesh Google Research. Part of this work was done at UC Berkeley while being supported in part by NSF CCF-1816861. Abhradeep Thakurta Google DeepMind. Jalaj Upadhyay Rutgers University. This work was supported by the Decanal Research grant from Rutgers University.
Abstract
In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism [57], whose privacy analysis does not depend on convexity and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from the Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.
中文速览
差分隐私优化领域长期面临两个难题：如何在不依赖凸性假设的前提下保证隐私，以及如何同时获得紧的经验风险与泛化误差界。本文提出了一个基于朗之万扩散（Langevin Diffusion, LD）的算法框架，将从吉布斯分布（Gibbs distribution）采样与差分隐私（Differential Privacy, DP）分析统一起来，证明了连续时间轨迹满足隐私性（无需凸性）、算法可在任意时刻停止而不泄露隐私，并为强凸和凸损失函数分别给出了 O(1/n) 和 O(1/√n) 的紧一致稳定性（uniform stability）保证，从而在纯DP和近似DP两种设置下均达到最优的超额风险界。此外，该框架还首次实现了对拉什蒙集合（Rashomon set，即所有近似最优模型的集合）的差分隐私均匀采样，为可解释机器学习、公平性分析等应用提供了隐私保护工具，意义在于将采样视角与隐私优化的理论界同时推向最优，并拓展到此前算法无法处理的场景。
原文 arXiv:2204.01585;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2204.01585v4