Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization

Authors: Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
Published: 2022-04-04 | Updated: 2023-08-28

Source: https://arxiv.org/abs/2204.01585

PDF: https://arxiv.org/pdf/2204.01585

AIにより推定されたラベル

プライバシー評価 アルゴリズム プライバシー保護メカニズム

※ こちらのラベルはAIによって自動的に追加されました。そのため、正確でないことがあります。
詳細は文献データベースについてをご覧ください。

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