Reproduce “Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Yingyu Lin, Yi-An Ma, Yu-Xiang Wang, Rachel Redberg, Zhiqi Bu
Researchers developed the Approximate SAample Perturbation (ASAP) framework, which enables the first nearly linear-time algorithm for differentially private empirical risk minimization under pure and Gaussian differential privacy. This method simultaneously achieves optimal statistical utility rates for strongly convex and smooth losses.
Key insights
- Wasserstein-infinity (W∞) distance is the critical metric for linking MCMC approximations to rigorous pure DP and Gaussian DP guarantees, providing almost-sure bounds on sample distances.
- Efficient MCMC methods, which typically provide TV distance convergence, can be leveraged for pure DP by demonstrating a quantifiable conversion from TV to W∞ distance under specific conditions.
- Combining a localization step, constrained MCMC, and W∞-distance-calibrated output perturbation collectively forms an end-to-end framework that achieves strong privacy with optimal utility and high computational efficiency.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.