Research map / Federated learning and privacy / Differential privacy
Differentially Private Quantiles with Smaller Error
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 SliceQuantiles, which uses continual counting to add correlated noise to target ranks and then applies the exponential mechanism to the resulting disjoint slices, giving multi-quantile DP with error improved over prior pure-DP work and independent of delta under approximate DP.
Problem
Estimating m quantiles of a real-valued dataset under differential privacy with rank error, where prior pure-DP methods have error log(b)log^2(m)/eps and approximate-DP methods degrade with small delta.
Approach
Randomize target ranks with correlated noise from continual counting so that changing one data point shifts at most one slice, enabling parallel composition over m slices; an injective mapping argument handles adjacency, and mixing with uniform output converts approximate DP to pure DP.
Key results
- Under pure DP, error O((log b + log^2 m)/eps) under a minimum quantile gap, improving over the prior O((log b log^2 m + log^3 m)/eps) by a factor of min(log b, log^2 m).
- Experiments on AdultAge/AdultHours (n about 500k, eps=1, delta=1e-16): SliceQuantiles outperforms AQ, with about 2x accuracy improvement for 200 quantiles under substitute adjacency.
- Approximate-DP variant has error independent of delta, but requires a quantile gap depending on log(m)log(m/delta)/(eps n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SliceQuantiles instead of Approximate Quantiles | Approximate quantile estimation under substitute adjacency · AdultAge and AdultHours | average maximum rank error: factor of 2 | Helped |
| Use SliceQuantiles instead of Approximate Quantiles | Approximate quantile estimation · AdultAge and AdultHours | average maximum rank error | Helped |
| Use Approximate Quantiles with approximate DP instead of its pure-DP version | Approximate Quantiles · AdultAge and AdultHours | average maximum rank error | Hurt |
Limitations
- Requires a minimum gap between queried quantiles, which can be large (e.g., 1.3e7 data points needed for m=100, b=2^32).
- Gap assumption not present in prior work; may be unnecessary with tighter analysis.
- Experiments use a practical discrete-Laplace k-ary tree variant rather than the exact theoretical mechanism.
Experimental setup
Datasets: AdultAge AdultHours
Benchmarks: AdultAge AdultHours
Metrics: average maximum rank error 95% bootstrap confidence intervals
Baselines: Approximate Quantiles (AQ) AppIndExp histogram-based method
Builds on: binary tree mechanism exponential mechanism Approximate Quantiles (Kaplan, Schnapp, Stemmer)
Closest papers by meaning
- Differentially Private Approximate Quantiles (ICML 2022 · similarity 0.95)
- Differentially Private Quantiles (ICML 2021 · similarity 0.93)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.90)
- Differentially Private Equivalence Testing for Continuous Distributions and Applications (NeurIPS 2024 · similarity 0.85)
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.85)
- Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy (ICLR 2024 · similarity 0.84)
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.