Research map / Federated learning and privacy / Differential privacy
How Well Can Differential Privacy Be Audited in One Run?
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.
Characterizes the maximum efficacy and asymptotic tightness of one-run privacy auditing (ORA), identifies three gaps (non-worst-case element privacy, non-worst-case outputs, interference), and proposes multiple elements per coordinate plus Adaptive ORA to mitigate interference in DP-SGD auditing.
Problem
Understanding how precisely one-run privacy auditing can recover the true differential privacy parameter of an algorithm, and what limits its tightness, especially for DP-SGD.
Approach
Shows that ORA's optimal efficacy equals an average-element, average-case distributional DP quantity, which is exactly the gap between that and pure DP due to three effects; then introduces Adaptive ORA (guesser conditions on previously revealed bits) and placing multiple auditing elements per coordinate to trade off guess count against interference.
Key results
- With d=1000 and 100 guesses on DP-SGD, the mean epsilon bound is 0.49 (±0.01) with one element per coordinate and 0.62 (±0.01) with eight elements per coordinate.
- Adaptive ORA yields higher bounds than ORA on DP-SGD and keeps improving with more elements per coordinate, while ORA's bounds decrease beyond about 5 elements per coordinate.
- ORA is asymptotically tight for local algorithms and for Count-In-Sets when elements per coordinate s(n)=o(log n); a single counting query (s=n) gives efficacy approaching 1/2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase from 1 to 8 elements per coordinate (ablation) | ORA on DP-SGD · DP-SGD, 1000 dimensions, 100 steps | mean bound on ε: 0.49 (± 0.01) -> 0.62 (± 0.01) | Helped |
| Increase the number of elements per coordinate beyond the optimum (ablation) | ORA on DP-SGD · DP-SGD, 1000 dimensions, 100 steps | statistically corrected bound on ε | Hurt |
| Take only the highest-confidence guesses instead of more guesses (ablation) | ORA on DP-SGD · DP-SGD, 5000 elements | privacy estimation | Helped |
| Take more, less-confident guesses (ablation) | ORA on DP-SGD · DP-SGD, 5000 elements | efficacy | Hurt |
| Take more, less-confident guesses (ablation) | ORA on DP-SGD · DP-SGD, 5000 elements | statistically corrected bound on ε | Mixed |
| Use adaptive guessing conditioned on previously guessed bits (ablation) | AORA on DP-SGD · DP-SGD, single step and full batch | mean bound on ε | Helped |
| Increase the number of elements per coordinate (ablation) | AORA on DP-SGD · DP-SGD, single step and full batch | mean bound on ε | Helped |
Surprising findings
- Assigning more than one auditing element per coordinate can outperform the common one-element-per-coordinate Dirac canary setup for DP-SGD auditing.
- Optimal one-run auditing of the XOR algorithm without adaptivity has efficacy 1/2, i.e., no better than random guessing.
Limitations
- Experiments are simplified (single full-batch step for AORA comparison, T=100 steps and synthetic gradient canaries) and not a comprehensive evaluation on realistic settings.
- Analysis focuses on pure epsilon-DP; the approximate DP gap is only discussed empirically.
- Adaptive ORA's benefits are shown mainly in simplified settings; realistic adaptive attacks are left to future work.
Experimental setup
Metrics: efficacy privacy estimation epsilon statistically corrected epsilon lower bound
Baselines: ORA (non-adaptive) classic auditing one element per coordinate ORA
Builds on: one-run auditing (Steinke et al.) classic auditing Dirac canary noiseless privacy
Closest papers by meaning
- Auditing $f$-differential privacy in one run (ICML 2025 · similarity 0.92)
- Auditing Private Prediction (ICML 2024 · similarity 0.90)
- Nearly Tight Black-Box Auditing of Differentially Private Machine Learning (NeurIPS 2024 · similarity 0.87)
- One-shot Empirical Privacy Estimation for Federated Learning (ICLR 2024 · similarity 0.87)
- Monitoring Violations of Differential Privacy over Time (NeurIPS 2026 · similarity 0.87)
- Setting $\varepsilon$ is not the Issue in Differential Privacy (NeurIPS 2025 · 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.