Summary
The paper considers the problem of computing the quantile q of a dataset with differential privacy. The prior standard technique for this problem was the exponential mechanism with the loss of an output T being the difference between the number of examples less than T and qn. An issue with the exponential mechanism (and most mechanisms for quantile estimation) is that it requires the user to bound the range of possible values in the dataset. The authors propose an alternate algorithm which does not require a prior bound, and takes advantage of the AboveThreshold algorithm. They propose using the AboveThreshold on queries of the form "how many examples in the dataset are less than T?", where T is exponentially increasing, and return the value T that AboveThreshold reports has more than qn elements less than T. As part of the analysis, the authors give an improved analysis of AboveThreshold, showing it has improved privacy guarantees for monotonic queries when using Exponential or Gumbel noise; previously, this was shown for Laplace noise. The Exponential distribution has lower variance, so this allows them to get a lower-variance estimate without sacrificing privacy. The authors perform experiments to compare to the exponential mechanism, as well as the aggregate tree method. On synthetic datasets, the exponential mechanism performs slightly better, but otherwise the authors' result is better for quantile estimation. For sum estimation, when using parameters agnostic to the dataset, the authors' algorithm by far outperforms the baselines, due to not relying on a good prior range estimate.
Strengths
Overall I enjoyed reading the paper and feel it makes a substantial contribution to the field. Private quantile selection is an extremely important problem with a number of applications, including any setting where we wish to compute a private sum. The problem of needing a bounded range for these problems has always been a troublesome part of DP research and application, and having a seemingly robust approach that at least partially gets around this issue is thus of significant impact. The main idea in the paper is simple to describe, which makes it more likely to see adoption and further development in follow-up works, but at the same time requires new analyses to achieve competitive privacy-utility tradeoffs. Finally, I felt the paper was overall a pretty easy read, in part due to the elegance of the algorithmic ideas but also the quality and clarity of the writing.
Weaknesses
I think the only major weakness is that one still needs to choose beta appropriately. The authors mention this in the discussion in Appendix D, but this discussion is somewhat incomplete. Still, I believe that beta is a much easier parameter for a practitioner to choose appropriately than the range of the dataset, especially since the experiments show beta is somewhat dataset-agnostic, so this is a minor weakness.
Questions
Intuitively it seems like smaller beta is more likely to underestimate the quantile and larger beta is more likely to overestimate, is this correct? Also, for e.g. a bimodal dataset such as the Gaussian mixture 0.5 * N(0, 1) + 0.5 * N(Delta, 1), Delta >> 1, for estimating the 75th percentile, how would you expect UQE to compare to EMQ? (with a good or bad range estimate)
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
Yes, in the appendix the authors discuss the main limitation/weakness. N/A on negative societal impact.