Research map / Federated learning and privacy / Differential privacy
Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ASAP, an MCMC-based posterior sampler that stays pure DP / pure GDP by adding noise scaled to the W∞ distance from an exact pure-DP reference, and combines it with localization and a constrained MALA to get nearly linear-time optimal DP-ERM for strongly convex smooth losses.
Problem
Posterior sampling gives pure DP in theory, but practical MCMC approximations degrade guarantees to approximate (epsilon,delta)-DP; efficient MCMC that preserves pure DP is lacking for DP-ERM.
Approach
Perturb an approximate MCMC sample with Laplace (or Gaussian) noise scaled to its W∞ distance from an exact pure-DP reference distribution, and convert TV-accurate MALA samples into W∞ guarantees via a TV-to-W∞ lemma on bounded log-concave densities.
Key results
- Localized ASAP achieves excess empirical risk O(d^2 G^2 (ln d + ln kappa)/(alpha n eps^2)) under pure DP with expected runtime nearly linear in n (Theta(n) up to polylog factors for kappa=polylog(n)).
- Under Gaussian DP the method attains the optimal rate O(d G^2/(alpha n mu^2)) with nearly linear runtime, improving the dimension dependence from d^2 to d.
- Experiments on Wine Quality datasets report that the proposed algorithms outperform output perturbation and DP-GD baselines under both epsilon-DP and mu-GDP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use localized ASAP for the private learning algorithm | DP-ERM learners · Red Wine Quality and White Wine Quality | excess empirical risk | Helped |
| Use localized ASAP rather than the prior risk analysis with an O(κ) dependency | Strongly convex DP-ERM · Strongly convex DP-ERM | excess empirical risk condition-number dependence: from O(\kappa) to O(\log\kappa) | Helped |
| Use the Gaussian DP risk bound rather than converting the pure-DP bound to Gaussian DP | Localized ASAP · Strongly convex DP-ERM under Gaussian DP | excess empirical risk dimensionality dependence: from \tilde\mathcal{O} \lrp{d^2} to \mathcal{O}(d) | Helped |
Surprising findings
- Under pure DP, no choice of gamma and lambda in the exponential mechanism achieves the optimal DP-ERM rate unless the domain is already localized.
Limitations
- Optimal rates for general convex Lipschitz losses without smoothness or strong convexity are not attained with fast computation.
- Requires strong convexity and smoothness assumptions and bounded domain localization for the W∞ conversion lemma.
- Experiments are small-scale regression on two UCI datasets.
Experimental setup
Datasets: Red Wine Quality (UCI) White Wine Quality (UCI)
Benchmarks: Red Wine Quality regression White Wine Quality regression
Metrics: excess empirical risk runtime complexity
Baselines: Noisy GD NoisySGD PosteriorSample ExponentialMechanism output perturbation DP-GD
Builds on: exponential mechanism posterior sampling MALA output perturbation
Closest papers by meaning
- Differential Privacy Guarantees of Markov Chain Monte Carlo Algorithms (ICML 2025 · similarity 0.93)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.90)
- On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · similarity 0.90)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.88)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.88)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.