Research map / Federated learning and privacy / Differential privacy
Lightweight Protocols for Distributed Private Quantile Estimation
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.
Gives sequentially adaptive LDP and shuffle-DP protocols for private median/quantile estimation over [B] that need fewer users than prior non-adaptive methods, with matching lower bounds.
Problem
Private quantile (median) estimation when each of n users holds one point in [B]; non-adaptive LDP and shuffle-DP protocols need polylog(B) more users than necessary.
Approach
Adapt Bayesian Screening Search (noisy binary search) to empirical data by sampling users without replacement, showing the empirical CDF drifts by at most alpha, and feed each user's randomized-response bit into the search; for shuffle-DP, run O(log B) adaptive rounds with shuffled batches.
Key results
- The adaptive LDP algorithm (DpBayeSS) needs O(log B / (eps^2 alpha^2)) users, versus O(log^3 B / (eps^2 alpha^2)) for the hierarchical mechanism.
- Lower bound shows the adaptive LDP sample complexity is optimal up to constants in the high-privacy regime, and non-adaptive protocols need an extra log B factor (Omega(log^2 B) when eps, alpha are constant).
- In experiments DpBayeSS achieves a far higher success rate than DpNaiveNBS and the Hierarchical Mechanism across eps in [0.1,5] and across domain sizes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DpBayeSS instead of DpNaiveNBS | Median estimation under LDP · Synthetic Pareto-like dataset (B=4^9, n=2500; ε varied from 0.1 to 5) | success rate | Helped |
| Use DpBayeSS instead of the Hierarchical Mechanism | Median estimation under LDP · Synthetic Pareto-like dataset (B=4^9, n=2500; ε varied from 0.1 to 5) | success rate | Helped |
| Use DpBayeSS instead of DpNaiveNBS | Median estimation under LDP · Synthetic Pareto-like dataset (B=4^9, n=2500, ε=0.57) | absolute quantile error | Helped |
| Use DpBayeSS instead of the Hierarchical Mechanism | Median estimation under LDP · Synthetic Pareto-like dataset (B=4^9, n=2500, ε=0.57) | absolute quantile error | Helped |
| Use DpBayeSS instead of DpNaiveNBS | Median estimation under LDP · Uniform distribution over random interval (B=10^3 to 10^6, n=2500, ε=1) | success rate | Helped |
| Use DpBayeSS instead of DpNaiveNBS | Median estimation under LDP · Uniform distribution over random interval (B=10^6, n=2500, ε=1) | absolute quantile error | Helped |
| Use DpBayeSS instead of the Hierarchical Mechanism | Median estimation under LDP · Synthetic Pareto-like dataset (B=4^9, n=2500) | success rate | Helped |
Surprising findings
- The hierarchical mechanism is reported to be unable to produce a meaningful median at the tested user count (n=2500).
Limitations
- Adaptive sequential protocols query one user per round, which is incompatible with shuffling and needs n rounds of coordination.
- Non-adaptive lower bound has large dependence on 1/alpha (log^4(1/alpha)) which the authors believe is a proof artifact.
- Continuous-domain setting is not covered by the guarantees.
Experimental setup
Datasets: synthetic Pareto distribution over [B] synthetic uniform distribution over random intervals
Benchmarks: synthetic Pareto data (B=4^9, n=2500) synthetic uniform data (varying B from 10^3 to 10^6)
Metrics: success rate absolute quantile error
Baselines: DpNaiveNBS Hierarchical Mechanism
Builds on: Bayesian Screening Search (BayeSS) hierarchical mechanism randomized response
Closest papers by meaning
- Online Local Differential Private Quantile Inference via Self-normalization (ICML 2023 · similarity 0.92)
- Differentially Private Quantiles (ICML 2021 · similarity 0.91)
- Privacy-Aware Data Integration for Enhanced Quantile Inference under Heterogeneity (ICML 2026 · similarity 0.91)
- Unbounded Differentially Private Quantile and Maximum Estimation (NeurIPS 2023 · similarity 0.91)
- Differentially Private Quantiles with Smaller Error (NeurIPS 2025 · similarity 0.90)
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.87)
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.