Research map / Federated learning and privacy / Differential privacy
Sequentially Auditing 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 an MMD-based anytime-valid sequential test (betting/e-process style with online gradient ascent and online Newton step) for black-box approximate differential privacy auditing, detecting violations with hundreds of samples and enabling DP-SGD audits within one training run.
Problem
Black-box auditing of approximate differential privacy requires large, fixed batch sample sizes, which is impractical for expensive mechanisms such as DP-SGD.
Approach
A one-sided sequential MMD test with a nonnegative supermartingale built from a witness function learned by online gradient ascent and a betting fraction learned by online Newton step, combined with a tighter MMD–hockey-stick (total variation) bound that converts MMD thresholds into (epsilon, delta)-DP.
Key results
- NonDPGaussian1 and NonDPLaplace2 detected with 100% rejection in under 350 observations at epsilon=0.01, while the fixed-sample MMD tester failed even with 500,000 observations for NonDPLaplace2.
- Private mechanisms DPGaussian and DPLaplace showed zero rejections at both epsilon=0.01 and 0.1 (Type I error control).
- For non-private DP-SGD, the sequential audit rejected epsilon_canary<=0.01 in about 60 observations and gave an empirical lower bound of epsilon=0.43 after 250 observations, while the private implementation was not rejected after 500 observations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply sequential DP auditing to DPGaussian and DPLaplace | DP-compliant mean mechanisms · Mean estimation, ε = 0.01 and ε = 0.1 | rejection rate: 0.0 ± 0.0 | No clear effect |
| Audit NonDPGaussian1 with the sequential tester | NonDPGaussian1 · Mean estimation, ε = 0.01 | rejection rate: 1.0 ± 0.0; 264 ± 9.3 observations | Helped |
| Audit NonDPGaussian2 with the sequential tester | NonDPGaussian2 · Mean estimation, ε = 0.01 | rejection rate: 0.85 ± 0.08; 1139 ± 126.1 observations | Helped |
| Audit NonDPGaussian1 with the sequential tester | NonDPGaussian1 · Mean estimation, ε = 0.1 | rejection rate: 1.0 ± 0.0; 562 ± 29.2 observations | Helped |
| Audit NonDPGaussian2 with the sequential tester | NonDPGaussian2 · Mean estimation, ε = 0.1 | rejection rate: 0.05 ± 0.05; 4776 ± 219.0 observations | Mixed |
| Audit NonDPLaplace1 with the sequential tester | NonDPLaplace1 · Mean estimation, ε = 0.01 | rejection rate: 1.0 ± 0.0; 331 ± 14.5 observations | Helped |
| Audit NonDPLaplace2 with the sequential tester | NonDPLaplace2 · Mean estimation, ε = 0.01 | rejection rate: 1.0 ± 0.0; 192 ± 18.4 observations | Helped |
| Audit NonDPLaplace1 with the sequential tester | NonDPLaplace1 · Mean estimation, ε = 0.1 | rejection rate: 1.0 ± 0.0; 920 ± 61.6 observations | Helped |
| Audit NonDPLaplace2 with the sequential tester | NonDPLaplace2 · Mean estimation, ε = 0.1 | rejection rate: 0.95 ± 0.05; 770 ± 262.3 observations | Helped |
| Use a sequential tester rather than the fixed-sample-size MMD tester | NonDPLaplace2 and NonDPGaussian2 · Mean estimation, ε = 0.01 | violation detection: 500,000 observations | Helped |
| Audit private DP-SGD sequentially during training | Private DP-SGD · DP-SGD, ε_canary = 0.01 | null rejection: 500 observations; 5 runs | No clear effect |
| Audit non-private DP-SGD sequentially during training | Non-private DP-SGD · DP-SGD, ε_canary ≤ 0.01 | observations to reject: 60 observations | Helped |
Surprising findings
- NonDPGaussian2 is hard to detect at epsilon=0.1, with rejection rate only 5%.
- MMD-based tests become very sample-hungry for large epsilon (around 0.6 and above), where the MMD gap shrinks.
Limitations
- Large epsilon regimes (above about 0.6) require very large sample sizes due to vanishing MMD gap.
- Relies on a fixed pair of neighboring datasets rather than searching for a worst-case pair.
- Currently limited to approximate DP; extension to Renyi DP or f-DP left for future work.
Experimental setup
Datasets: synthetic Gaussian and perturbed uniform distributions simulated additive-noise mean mechanisms DP-SGD canary gradients
Benchmarks: additive-noise mean mechanisms (DPGaussian, DPLaplace, NonDP variants) DP-SGD white-box canary audit
Metrics: rejection rate average samples to reject empirical epsilon lower bound Type I error
Baselines: fixed-sample-size MMD auditing (batch) Hockey-stick batch auditing DP-SGD black-box audit
Builds on: Maximum Mean Discrepancy Ville's inequality Online Newton Step Online Gradient Ascent sequential kernel betting
Closest papers by meaning
- Monitoring Violations of Differential Privacy over Time (NeurIPS 2026 · similarity 0.89)
- Auditing $f$-differential privacy in one run (ICML 2025 · similarity 0.89)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.88)
- 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.87)
- Beyond the Calibration Point: Mechanism Comparison in Differential Privacy (ICML 2024 · similarity 0.87)
- Nearly Tight Black-Box Auditing of Differentially Private Machine Learning (NeurIPS 2024 · similarity 0.86)
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.