Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions
We consider the problem of constructing differentially private nonparametric confidence intervals (CIs) for an arbitrary quantity using resampling. A growing body of work has adapted resampling ideas to the private setti…
Practical Attribution Guidance for Rashomon Sets
Different prediction models might perform equally well (Rashomon set) in the same task, but offer conflicting interpretations and conclusions about the data. The Rashomon effect in the context of Explainable AI (XAI) has…
Exploring the Whole Rashomon Set of Sparse Decision Trees
In any given machine learning problem, there may be many models that could explain the data almost equally well. However, most learning algorithms return only one of these models, leaving practitioners with no practical …
Differentially Private Learning Beyond the Classical Dimensionality Regime
We initiate the study of differentially private learning in the proportional dimensionality regime, in which the number of data samples $n$ and problem dimension $d$ approach infinity at rates proportional to one another…
regressionDifferentially-Private Sublinear-Time Clustering
Clustering is an essential primitive in unsupervised machine learning. We bring forth the problem of sublinear-time differentially-private clustering as a natural and well-motivated direction of research. We combine the …
Clustering