# Unbounded Differentially Private Quantile and Maximum Estimation

arXiv: https://arxiv.org/abs/2305.01177 · HTML: https://mlsanity.com/paper/2305.01177/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 57 references that are in the map.
- First posted on arXiv 2 May 2023.

## Builds on (most cited first, 29 of 29)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM](https://mlsanity.com/paper/1705.10829/) (2017)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [Privately Answering Classification Queries in the Agnostic PAC Model](https://mlsanity.com/paper/1907.13553/) (2019)
- [Private Multiplicative Weights Beyond Linear Queries](https://mlsanity.com/paper/1407.1571/) (2014)
- [The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise](https://mlsanity.com/paper/2105.07260/) (2021)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [The Sparse Vector Technique, Revisited](https://mlsanity.com/paper/2010.00917/) (2020)
- [Bounded Space Differentially Private Quantiles](https://mlsanity.com/paper/2201.03380/) (2022)
- [Privacy and Truthful Equilibrium Selection for Aggregative Games](https://mlsanity.com/paper/1407.7740/) (2014)
- [Proving Differential Privacy via Probabilistic Couplings](https://mlsanity.com/paper/1601.05047/) (2016)
- [How to Find a Point in the Convex Hull Privately](https://mlsanity.com/paper/2003.13192/) (2020)
- [Free Gap Estimates from the Exponential Mechanism, Sparse Vector, Noisy Max and Related Algorithms](https://mlsanity.com/paper/2012.01592/) (2020)
- [Privately detecting changes in unknown distributions](https://mlsanity.com/paper/1910.01327/) (2019)
- [Advanced Probabilistic Couplings for Differential Privacy](https://mlsanity.com/paper/1606.07143/) (2016)

## Built on by (most cited first, 6 of 6)

- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Improved subsample-and-aggregate via the private modified winsorized mean](https://mlsanity.com/paper/2501.14095/) (2025)
- [Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions](https://mlsanity.com/paper/2511.01303/) (2025)
- [Instance-Specific Asymmetric Sensitivity in Differential Privacy](https://mlsanity.com/paper/2311.14681/) (2023)
- [End to End Collaborative Synthetic Data Generation](https://mlsanity.com/paper/2412.03766/) (2024)
- [Computationally tractable robust differentially private mean estimation](https://mlsanity.com/paper/2606.12654/) (2026)

## Abstract (arXiv)

In this work we consider the problem of differentially private computation of quantiles for the data, especially the highest quantiles such as maximum, but with an unbounded range for the dataset. We show that this can be done efficiently through a simple invocation of textttAboveThreshold, a subroutine that is iteratively called in the fundamental Sparse Vector Technique, even when there is no upper bound on the data. In particular, we show that this procedure can give more accurate and robust estimates on the highest quantiles with applications towards clipping that is essential for differentially private sum and mean estimation. In addition, we show how two invocations can handle the fully unbounded data setting. Within our study, we show that an improved analysis of textttAboveThreshold can improve the privacy guarantees for the widely used Sparse Vector Technique that is of independent interest. We give a more general characterization of privacy loss for textttAboveThreshold which we immediately apply to our method for improved privacy guarantees. Our algorithm only requires one O(n) pass through the data, which can be unsorted, and each subsequent query takes O(1) time. We empirically compare our unbounded algorithm with the state-of-the-art algorithms in the bounded setting. For inner quantiles, we find that our method often performs better on non-synthetic datasets. For the maximal quantiles, which we apply to differentially private sum computation, we find that our method performs significantly better.