Research map / Federated learning and privacy / Differential privacy
Private Hyperparameter Tuning with Ex-Post Guarantee
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 the first ex-post differential privacy hyperparameter tuning algorithm (random dropping with correlated geometric/exponential noise), giving at most ~2x the privacy cost of the selected base mechanism, plus an ex-post Rényi DP extension and a privacy filter.
Problem
Utility-first privacy: practitioners want to reach a utility bar (or tune hyperparameters including privacy budget) and pay only the privacy cost of the output actually released, but prior ex-post DP work covers only simple Laplace/Gaussian mechanisms and existing hyperparameter tuning methods requi
Approach
Sample one correlated noise level k shared across all mechanisms and randomly drop each mechanism run with probability e^{-eps_i k}; take the maximum surviving output. The privacy loss of the returned output from M_i is about 2*eps_i + eps', regardless of other mechanisms run, and an RDP variant uses exponential noise with shifted couplings.
Key results
- Under pure-DP analytics with Laplace, the proposed method produces about 20.37 answers on S8000 versus 14.77 for doubling at similar precision (~0.91).
- On ML tasks, the proposed method's average ex-post epsilon is 0.28 (Twitter), 0.32 (MNIST), 0.23 (Gisette) versus 0.55, 0.38, 0.54 for the doubling mechanism.
- In the approximate-DP analytics setting with Gaussian noise, the proposed method underperforms doubling with zCDP budgeting and Brownian motion (e.g., 6.69 vs 17.20 answers on S8000).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed tuning algorithm with Laplace noise instead of the doubling mechanism | Pure-DP answer estimation · S8000–S128000 and Reddit | Produced Answers: 14.77 -> 20.37 (S8000); 76.09 -> 102.1 (S128000); 279.7 -> 327.5 (Reddit) | Helped |
| Use the proposed tuning algorithm with Gaussian noise instead of Brownian Motion | Approximate-DP answer estimation · S8000–S128000 | Produced Answers: 28.63 -> 6.694 (S8000); 269.7 -> 52.33 (S128000) | Hurt |
| Use the proposed tuning algorithm instead of Brownian Motion | Machine-learning privacy tuning · Twitter, MNIST, and Gisette | Ex-post (ε, 10⁻⁶)-DP guarantee: 0.77 -> 0.28 (Twitter); 0.62 -> 0.32 (MNIST); 0.33 -> 0.23 (Gisette) | Helped |
| Use the proposed tuning algorithm instead of the doubling mechanism | DP-SGD hyperparameter tuning · Twitter, MNIST, and Gisette | Ex-post (ε, 10⁻⁶)-DP guarantee: 0.55 -> 0.28 (Twitter); 0.38 -> 0.32 (MNIST); 0.54 -> 0.23 (Gisette) | Helped |
Surprising findings
- The tuning mechanism's ex-post privacy cost for a released output from M_i does not increase with higher-budget mechanisms M_j run en route, despite them being included in the selection.
- In the approximate-DP analytics setting, the proposed method underperforms the zCDP-based doubling and Brownian motion baselines.
Limitations
- Ex-post RDP bound pays a privacy cost even when output is perp (no answer), unlike pure-DP case.
- Requires a parameter l_i in the RDP bound; the authors leave removing these as open.
- Gaussian/zCDP version is not proven and the method underperforms zCDP baselines in the approximate-DP analytics experiment.
Experimental setup
Datasets: Synthetic power-law histograms (N from 8000 to 128000) webis/tldr-17 Reddit Twitter time series (100000 subsample) MNIST Gisette
Benchmarks: Synthetic power-law histograms Reddit tldr-17 histogram Twitter linear regression MSE MNIST accuracy Gisette accuracy
Metrics: number of produced answers precision (fraction within 10% relative error) average ex-post epsilon at delta=1e-6
Baselines: Doubling mechanism Noise reduction mechanism (Laplace) Brownian motion mechanism with AboveThreshold Doubling mechanism with Gaussian and zCDP Opacus DP-SGD
Builds on: AboveThreshold / sparse vector technique Liu and Talwar hyperparameter tuning Brownian motion noise reduction (Whitehouse et al.) DP-SGD Opacus
Closest papers by meaning
- Private Lossless Multiple Release (ICML 2025 · similarity 0.88)
- Beyond the Calibration Point: Mechanism Comparison in Differential Privacy (ICML 2024 · similarity 0.87)
- 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.87)
- Instance-Wise Laplace Mechanism via Deep Reinforcement Learning (Student Abstract) (AAAI 2024 · similarity 0.87)
- Purifying Approximate Differential Privacy with Randomized Post-processing (NeurIPS 2025 · similarity 0.86)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (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.