Research map / Federated learning and privacy / Differential privacy
Tuning-free Estimation and Inference of Cumulative Distribution Function under Local 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 a tuning-free, deterministic constrained isotonic estimator of the CDF under local differential privacy by mapping randomized-response binary queries to a current status problem, with L2/uniform consistency and asymptotic normality results.
Problem
Estimating the full CDF (all quantiles) of users' private values in [0,1] under local differential privacy, where the curator is untrusted and each user answers only one randomized binary query.
Approach
Connects the LDP randomized-response data collection to the current status problem in survival analysis, so that the LDP-perturbed binary responses can be treated as truthful responses to an alternative variable; then uses a constrained (monotone, range-clipped) nonparametric MLE computed via the greatest convex minorant, which is deterministic and hyperparameter-free.
Key results
- Maximum absolute error and L2 error decrease with n (e.g., U(0,1) with r=0.25 max error 0.262 at n=10^3 down to 0.019 at n=10^7).
- Coverage rate of the finite-grid asymptotic normal intervals (kappa=10) reaches about 0.95 for n>=10^5 across the three distributions.
- Algorithm runs in about 4 ms at n=10^5 and about 0.5 s at n=10^7 on a single CPU core.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase sample size from n=103 to n=107 at r=0.5 | Constrained isotonic estimator with uniform sampling on U(0, 1) · U(0, 1) | maximum absolute error: 0.183 -> 0.012 | Helped |
| Increase sample size from n=103 to n=107 at r=0.5 | Constrained isotonic estimator with uniform sampling on U(0, 1) · U(0, 1) | L2 error: 0.076 -> 0.004 | Helped |
| Increase truthful response rate from r=0.25 to r=0.9 | Constrained isotonic estimator with uniform sampling on U(0, 1), n=103 · U(0, 1) | maximum absolute error: 0.262 -> 0.127 | Helped |
| Use G=F instead of uniform sampling (ablation) | Constrained isotonic estimator · U(0, 1), n=103, r=0.5 | maximum absolute error: 0.183 -> 0.183 | No clear effect |
| Use G=F instead of uniform sampling (ablation) | Constrained isotonic estimator · Nc(0, 1, µ, σ2), n=103, r=0.5 | maximum absolute error: 0.199 -> 0.182 | Helped |
| Use G=F instead of uniform sampling (ablation) | Constrained isotonic estimator · CB(λ), n=103, r=0.5 | maximum absolute error: 0.185 -> 0.183 | No clear effect |
| Use preselected finite grids with κ=10 | Constrained isotonic estimator · Uniform sampling; U(0, 1), n=105, r=0.5 | coverage rate: 0.951 | Helped |
Surprising findings
- Uniform sampling performs nearly as well as sampling from the true CDF (G=F), so prior knowledge adds only marginal improvement.
Limitations
- Uniform consistency and asymptotic distribution hold pointwise only; the process is not tight in D[0,1], so full-curve weak convergence is not established.
- Convergence rate scales with 1/r, so strong privacy (small r) requires much larger samples.
- The estimator is non-differentiable, so density estimation is not directly available.
Experimental setup
Datasets: synthetic Uniform(0,1) synthetic truncated normal synthetic continuous Bernoulli
Benchmarks: synthetic Uniform(0,1), truncated normal, continuous Bernoulli simulations
Metrics: maximum absolute error L2 error relative chi-square error coverage rate computation time
Baselines: Laplace mechanism square wave mechanism with EM (Li et al., 2020) frequency oracle methods
Builds on: randomized response nonparametric maximum likelihood estimation for current status data (Huang & Wel shuffle model privacy amplification
Closest papers by meaning
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.89)
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.87)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.87)
- Private Statistical Estimation via Truncation (NeurIPS 2025 · similarity 0.87)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.87)
- On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · 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.