mlsanityData to 7 Oct 2026

Differentially Private Approximate Quantiles

arXiv 2110.05429 ↗First posted 11 Oct 2021cs.LG cs.CR cs.DScited by 11

Not on the map. Why?

Abstract (arXiv)

In this work we study the problem of differentially private (DP) quantiles, in which given dataset X and quantiles q1, ..., qm ∈ [0,1], we want to output m quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call ApproximateQuantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 5 of its 19 references that are in the map. First posted on arXiv 11 Oct 2021.

Builds on

5 of 19 references.

References · 5

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  2. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
  3. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  4. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
  5. 2021Differentially Private Quantilescited by 22

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 1; 2025: 1; 2026: 4.

11 papers.

  1. 2023Unbounded Differentially Private Quantile and Maximum Estimationcited by 6
  2. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  3. 2022Private Quantiles Estimation in the Presence of Atomscited by 5
  4. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5
  5. 2023Private Statistical Estimation of Many Quantilescited by 3
  6. 2026How Much is Left? LLMs Linearly Encode Their Remaining Output Lengthcited by 2
  7. 2024End to End Collaborative Synthetic Data Generationcited by 0
  8. 2025Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptionscited by 0
  9. 2026DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacycited by 0
  10. 2026Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Treescited by 0
  11. 2026Workload-Preserving Differentially Private Synthetic Data for Causal Inference via Maximum-Entropy Calibrationcited by 0