mlsanityData to 7 Oct 2026

Differentially Private Quantiles

arXiv 2102.08244 ↗First posted 16 Feb 2021cs.LG cs.CRcited by 22

Not on the map. Why?

Abstract (arXiv)

Quantiles are often used for summarizing and understanding data. If that data is sensitive, it may be necessary to compute quantiles in a way that is differentially private, providing theoretical guarantees that the result does not reveal private information. However, when multiple quantiles are needed, existing differentially private algorithms fare poorly: they either compute quantiles individually, splitting the privacy budget, or summarize the entire distribution, wasting effort. In either case the result is reduced accuracy. In this work we propose an instance of the exponential mechanism that simultaneously estimates exactly m quantiles from n data points while guaranteeing differential privacy. The utility function is carefully structured to allow for an efficient implementation that returns estimates of all m quantiles in time O(mnlog(n) + m2n). Experiments show that our method significantly outperforms the current state of the art on both real and synthetic data while remaining efficient enough to be practical.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 13 of its 48 references that are in the map. First posted on arXiv 16 Feb 2021.

Builds on

13 of 48 references.

References · 13

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  2. 2013The Composition Theorem for Differential Privacycited by 290
  3. 2016Concentrated Differential Privacycited by 139
  4. 2020The Discrete Gaussian for Differential Privacycited by 134
  5. 2019Graphical-model based estimation and inference for differential privacycited by 73
  6. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  7. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  8. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
  9. 2020A Primer on Private Statisticscited by 30
  10. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13
  11. 2017Differentially Private Learning of Undirected Graphical Models using Collective Graphical Modelscited by 6
  12. 2020Duff: A Dataset-Distance-Based Utility Function Family for the Exponential Mechanismcited by 6
1 more
  1. 2019Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivitycited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 3; 2023: 5; 2024: 4; 2025: 3; 2026: 4.

22 papers.

Sort:

By area:

  1. 2023Conformal Prediction for Federated Uncertainty Quantification Under Label Shiftcited by 29
  2. 2021Differentially Private Approximate Quantilescited by 11
  3. 2021Non-parametric Differentially Private Confidence Intervals for the Mediancited by 7
  4. 2023Unbounded Differentially Private Quantile and Maximum Estimationcited by 6
  5. 2024A Survey of Privacy-Preserving Model Explanations: Privacy Risks, Attacks, and Countermeasurescited by 6
  6. 2022Private Quantiles Estimation in the Presence of Atomscited by 5
  7. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5
  8. 2021DP-XGBoost: Private Machine Learning at Scalecited by 3
  9. 2023Private Statistical Estimation of Many Quantilescited by 3
  10. 2024Towards Biologically Plausible and Private Gene Expression Data Generationcited by 2
  11. 2025Federated Learning of Quantile Inference under Local Differential Privacycited by 2
  12. 2026How Much is Left? LLMs Linearly Encode Their Remaining Output Lengthcited by 2
10 more
  1. 2023Differentially-Private Decision Trees and Provable Robustness to Data Poisoningcited by 1
  2. 2022Differentially Private Maximal Information Coefficientscited by 0
  3. 2023DPpack: An R Package for Differentially Private Statistical Analysis and Machine Learningcited by 0
  4. 2024DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)cited by 0
  5. 2024End to End Collaborative Synthetic Data Generationcited by 0
  6. 2025Federated Computation of ROC and PR Curvescited by 0
  7. 2025Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptionscited by 0
  8. 2026The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimizationcited by 0
  9. 2026Workload-Preserving Differentially Private Synthetic Data for Causal Inference via Maximum-Entropy Calibrationcited by 0
  10. 2026FinancialAuditBench: Benchmark Construction under Differential Privacy Using Real-World Priorscited by 0