Differentially Private Quantiles with Smaller Error

Thanks for your questions and your valuable feedback. We structured our rebuttal by first providing a common response, followed by answers to specific questions.

Common Response

Justification

Our algorithms are designed to produce very accurate estimates for $m$ input quantiles, where $m$ is sufficiently small compared to $n$. This setting is practical and common—data analysts often care about a limited number of summary statistics (e.g., 10%, 20%, ..., 90%). A particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation, the subject of a long line of research (see related work section). For approximate DP, our gap assumption is relatively mild, at $O(\frac{1}{n \varepsilon}(\log(b) + \log(m) \log \frac{m}{\delta}))$---both terms are typically significantly less than $n$ in practice. For equally-spaced quantiles, this means that $\Omega(\frac{n}{\log n \log(n/\delta)})$ quantiles can be answered. For example, with $n = 500,000$ and reasonable choices of $\varepsilon, b, m, \delta$, this gap assumption worked out to less than 0.005 in our experiments, meaning that up to 200 equally-spaced quantiles could be answered. For pure DP, our gap assumption grows slightly as $O(\frac{1}{n \varepsilon} m \log(b) \log (m))$, but remains manageable as long as $\frac{m}{n} \ll \varepsilon \log (b) \log(m)$. This still permits answering $\Omega(\sqrt{\frac{n \varepsilon}{\log(b) \log(n)}})$ equally-spaced quantiles. Finally, note that our gap assumption can be eliminated altogether by merging overly close quantiles into a single representative quantile; this will then add the required gap to the error instead.

Comparison to prior work

The main comparison algorithms are that of Kaplan (2022) and Cohen (2023). For data domains which are not extremely large (such as $b = 2^{64})$, the algorithm of Kaplan (2022) is the prior state-of-the-art: it satisfies pure DP and makes no assumption on the quantile gap. However, if the quantiles have the spacing of the prior paragraph (for pure DP), then our algorithm enjoys lower error by a \min{log^2(m), \log(b)} factor. If one is willing to relax to approximate DP, our algorithm still has the lower error, and the gap assumption is significantly reduced. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be $O(\frac{1}{\varepsilon}(\log(b) + \log(m) \log \frac{m}{\delta}))$; this is still less than Kaplan (2022) when $\frac{1}{\delta} \ll b$, usually the case for larger data domains. For extremely large data domains, the algorithm of Cohen (2023) can start to outperform our algorithm using more advanced techniques than the exponential mechanism. Specifically, their algorithm can be used to answer any quantiles with error $\frac{1}{n \varepsilon} \log^*b \log^2(\frac{1}{\delta})$. However, for domain sizes encountered in practice, the $\log^2(\frac{1}{\delta})$ will likely outweigh this improvement. We will add the above discussion in a revised version.

Answering Specific Questions

1. Minimum Gap Requirement: ...

We stress that our gap quantile assumption refers to spacing between the input (queried) quantiles, and does not refer to any part of the data itself. Kaplan et al. make an assumption that each point in the dataset itself is separated from the others by a small gap, and enforce this in practice by adding a small amount of random noise to each point. We also do this. For a full discussion of our quantile gap assumption, see the common response.

2. Clarity of Presentation: ...

We thank the reviewer for the suggestion and we agree that this approach will enhance the intuition around our algorithm. We will clarify this in a revised version.

3. Potential Bias in Location Algorithm: ...

The location algorithm can be thought of as an interior point algorithm which aims at returning any data point inside a given range. Any pure DP interior point algorithm can be used as a building block of SliceQuantiles. However, it is necessary to carefully compute the length $2h$ of the slices so that no interior points algorithm fails. The choice of using the exponential mechanism to estimate the median of each slice was driven by two factors: it matches in utility a lower bound of $\Omega(\log b)$ for the interior problem under pure DP [1], and it solves it with high probability thus allowing to set $h = \Omega(\log(b) + \log(m))$. Nevertheless, any pure DP interior point mechanism that achieves rank error $O(h)$ with high probability in $m$ can be used.

[1]: Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions.

4. Empirical CDF/Quantile Function Plots: ...

We agree that adding plots of the dataset CDFs will be interesting to include. While our theoretical analysis applies to any interior point algorithm, experimentally we always apply the exponential mechanism, even for approximate DP; thus, we do not expect a significant difference in the empirical bias of our algorithm vs. that of Kaplan et al. We will consider adding plots of this in a later version.

5. Literature: ...

Thank you for raising these points, which we will discuss more thoroughly in the revision. As pointed out earlier, our gap assumption is an assumption about the query, not the data. The assumption of having a minimum gap of 1 in the data is made for simplicity and convenience to be able to state clear results that are directly comparable between the cases of discrete and continuous domains. The assumption can be enforced whp. by scaling the data and adding random noise to data values, but this makes the utility guarantee more complicated to state.

Concerning a comparison to Lalanne et al. (2023) we agree that it would be a good idea to include it as a baseline. Theoretically speaking, their method is vulnerable to situations in which the distribution of values is concentrated (or concentrated around a few values) in which case even the non-private histogram may not contain enough information to output good quantile estimates.

6. Notation and Clarity Issues:

Thank you for pointing out these issues, we will make sure to fix them.

7. Scalability and Limitations:

We show that approximate DP allows us to achieve the same error as we were able to show for pure DP with a weaker gap assumption than was required for pure DP, since the quantile gap requirement scales with $\log(m/\delta)$. Therefore, increasing $\delta$ will decrease the quantile gap required for good utility and make our results more applicable in higher-quantile regimes. It is correct that the utility bounds are independent of $\delta$, and $\delta$ only affects the gap assumption. See our common response for a full discussion of this interaction.

Thanks for your interest in our paper! We would like to answer your specific questions.

For clarity: please consider to i) add input dataset in algorithm 1, ii) add ticks in Figure 1, iii) compare with AppindExp (reference 12), and iv) include approximate quantile literatures in the streaming model such as Differentially private linear sketches: Efficient implementations and applications, Improved utility analysis of private countsketch, and Bounded space differentially private quantiles.

Thanks for this suggestion and we will incorporate them in the revised version. We chose to compare with Kaplan et al as our baseline since it is the state-of-the-art private quantile estimation algorithm in the central model and outperforms [12] (as validated via experiments in their paper).

Need more discussions or experiment on the query time complexity (perhaps appendix).

The running time of the algorithm is $O(n \log n)$, it is dominated by the time taken to sort the dataset. Experimentally, we were able to run our algorithm with 200 quantiles and 500,000 data points in under a second.

What happens to the utility guarantee under substitute model?

As the utility of our algorithm does not depend on $\delta$, the utility guarantee under substitution analysis is affected only by a factor of 2 in the privacy budget $\varepsilon$ (Corollary 5.2, 5.3 with privacy budget given in Corollary 4.4).

Thanks for your questions and your consideration of our paper. We structured our rebuttal by first providing a common response, followed by answers to specific questions.

Common Response

Justification

Our algorithms are designed to produce very accurate estimates for $m$ input quantiles, where $m$ is sufficiently small compared to $n$. This setting is practical and common—data analysts often care about a limited number of summary statistics (e.g., 10%, 20%, ..., 90%). A particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation, the subject of a long line of research (see related work section). For approximate DP, our gap assumption is relatively mild, at $O(\frac{1}{n \varepsilon}(\log(b) + \log(m) \log \frac{m}{\delta}))$---both terms are typically significantly less than $n$ in practice. For equally-spaced quantiles, this means that $\Omega(\frac{n}{\log n \log(n/\delta)})$ quantiles can be answered. For example, with $n = 500,000$ and reasonable choices of $\varepsilon, b, m, \delta$, this gap assumption worked out to less than 0.005 in our experiments, meaning that up to 200 equally-spaced quantiles could be answered. For pure DP, our gap assumption grows slightly as $O(\frac{1}{n \varepsilon} m \log(b) \log (m))$, but remains manageable as long as $\frac{m}{n} \ll \varepsilon \log (b) \log(m)$. This still permits answering $\Omega(\sqrt{\frac{n \varepsilon}{\log(b) \log(n)}})$ equally-spaced quantiles. Finally, note that our gap assumption can be eliminated altogether by merging overly close quantiles into a single representative quantile; this will then add the required gap to the error instead.

Comparison to prior work

The main comparison algorithms are that of Kaplan (2022) and Cohen (2023). For data domains which are not extremely large (such as $b = 2^{64})$, the algorithm of Kaplan (2022) is the prior state-of-the-art: it satisfies pure DP and makes no assumption on the quantile gap. However, if the quantiles have the spacing of the prior paragraph (for pure DP), then our algorithm enjoys lower error by a $\min(\log^2(m), \log(b))$ factor. If one is willing to relax to approximate DP, our algorithm still has the lower error, and the gap assumption is significantly reduced. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be $O(\frac{1}{\varepsilon}(\log(b) + \log(m) \log \frac{m}{\delta}))$; this is still less than Kaplan (2022) when $\frac{1}{\delta} \ll b$, usually the case for larger data domains. For extremely large data domains, the algorithm of Cohen (2023) can start to outperform our algorithm using more advanced techniques than the exponential mechanism. Specifically, their algorithm can be used to answer any quantiles with error $\frac{1}{n \varepsilon} \log^*b \log^2(\frac{1}{\delta})$. However, for domain sizes encountered in practice, the $\log^2(\frac{1}{\delta})$ will likely outweigh this improvement. We will add the above discussion in a revised version.

Answering Specific Questions

The core idea of slicing queries into independent subproblems is conceptually simple and may be seen as a straightforward extension.

Note that the queries are not treated as independent subproblems, as this is not private (full discussion in Section 3.1). Instead, our algorithm adds correlated noise to shift each quantile, and the privacy analysis only goes through on this global structure.

The spacing assumption imposed on the quantiles lacks sufficient justification or motivation, and its relationship to prior work is underexplored.

Please refer to our common response for more discussion on this. We will add this clarification in a revised version.

In the experiments section, could the authors provide a more detailed analysis of how the algorithm performs under varying values of the privacy parameters and ? This would help assess robustness across different privacy regimes.

$\delta$ does not affect the utility of the mechanism, but only the initial assumption, i.e. the smaller the $\delta$ the larger the quantile gap must be. We include some additional results for more values of $\varepsilon$. The observation is similar to the results provided in the main paper – our algorithm outperforms Kaplan et al. by a factor 2 and a factor 1.3 under substitution privacy for $\varepsilon = 0.5$ and $\varepsilon= 5$, respectively.

Thanks for your questions and your consideration of our paper. We structured our rebuttal by first providing a common response, followed by answers to specific questions.

Common Response

Justification

Our algorithms are designed to produce very accurate estimates for $m$ input quantiles, where $m$ is sufficiently small compared to $n$. This setting is practical and common—data analysts often care about a limited number of summary statistics (e.g., 10%, 20%, ..., 90%). A particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation, the subject of a long line of research (see related work section). For approximate DP, our gap assumption is relatively mild, at $O(\frac{1}{n \varepsilon}(\log(b) + \log(m) \log \frac{m}{\delta}))$---both terms are typically significantly less than $n$ in practice. For equally-spaced quantiles, this means that $\Omega(\frac{n}{\log n \log(n/\delta)})$ quantiles can be answered. For example, with $n = 500,000$ and reasonable choices of $\varepsilon, b, m, \delta$, this gap assumption worked out to less than 0.005 in our experiments, meaning that up to 200 equally-spaced quantiles could be answered. For pure DP, our gap assumption grows slightly as $O(\frac{1}{n \varepsilon} m \log(b) \log (m))$, but remains manageable as long as $\frac{m}{n} \ll \varepsilon \log (b) \log(m)$. This still permits answering $\Omega(\sqrt{\frac{n \varepsilon}{\log(b) \log(n)}})$ equally-spaced quantiles. Finally, note that our gap assumption can be eliminated altogether by merging overly close quantiles into a single representative quantile; this will then add the required gap to the error instead.

Comparison to prior work

The main comparison algorithms are that of Kaplan (2022) and Cohen (2023). For data domains which are not extremely large (such as $b = 2^{64})$, the algorithm of Kaplan (2022) is the prior state-of-the-art: it satisfies pure DP and makes no assumption on the quantile gap. However, if the quantiles have the spacing of the prior paragraph (for pure DP), then our algorithm enjoys lower error by a \min{log^2(m), \log(b)} factor. If one is willing to relax to approximate DP, our algorithm still has the lower error, and the gap assumption is significantly reduced. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be $O(\frac{1}{\varepsilon}(\log(b) + \log(m) \log \frac{m}{\delta}))$; this is still less than Kaplan (2022) when $\frac{1}{\delta} \ll b$, usually the case for larger data domains. For extremely large data domains, the algorithm of Cohen (2023) can start to outperform our algorithm using more advanced techniques than the exponential mechanism. Specifically, their algorithm can be used to answer any quantiles with error $\frac{1}{n \varepsilon} \log^*b \log^2(\frac{1}{\delta})$. However, for domain sizes encountered in practice, the $\log^2(\frac{1}{\delta})$ will likely outweigh this improvement. We will add the above discussion in a revised version.

Answering Specific Questions

the Technical Challenge section attempts to explain the difficulty of establishing the differential privacy condition by describing a failed approach. However, the exposition of this failed attempt is unclear, and it does not effectively elucidate the core technical challenge faced by the authors.

Briefly, our algorithm works by sorting the dataset and taking a contiguous subset of data around the desired quantile. We refer to each contiguous subset of data as a “slice”, and this is what is used to form a private estimate of the quantile. The intuition behind this approach is that the data points that are closest to the queried quantile should be used to privately estimate the quantile as accurately as possible.

The technical challenge of this approach is that, perhaps surprisingly, the above procedure is not private because modifying one data point can modify the data contained in many slices (see lines 126-134 for an example). To circumvent this issue, we add correlated noise to each quantile before forming the slices which has the effect of hiding the modifications created in all the slices by the change in a single data point. We will clarify this in a revised version.

Could the authors provide a clearer and earlier definition of what constitutes a "slice" and explain explicitly why a slice corresponds to a subproblem in their framework?

In summary, a part of the definition can be found in line 124 where we say that a slice is “a contiguous subsequence of the sorted input data”. Additionally, the slice must be centered on a specific rank. We will make sure to introduce this concept earlier in the paper and to define it properly.

The proposed setting relies on a minimal gap between quantiles, but verifying that this condition holds may be non-trivial. Can the authors provide guidance or practical procedures for how one might check or enforce this minimal gap in realistic applications? Also, what is the motivation behind the rank error metric?

We stress that the minimal gap assumption is an assumption about the quantiles being queried and can be easily checked by computing the differences between consecutive quantiles (which is publicly known). In particular, it does not rely on any assumption about the data. See the common response for a discussion of the gap assumption. The rank error metric is natural since it measures how far off an approximate quantile is from having the desired number of data points on each side. We note that under differential privacy it is impossible in general to achieve approximation of the value of a quantile because the value does not have small sensitivity. However, assuming that the data distribution is reasonably smooth, a small rank error implies a small error in value, too. For these reasons, rank error is the most common error measure for private quantile estimates and is the standard metric used in existing literature, e.g:

Gillenwater, Jennifer et al. “Differentially Private Quantiles.” ArXiv abs/2102.08244 (2021): n. pag.

Kaplan, H., Schnapp, S. & Stemmer, U.. (2022). Differentially Private Approximate Quantiles. Proceedings of the 39th International Conference on Machine Learning.

Bassily, Raef, and Adam Smith. "Local, private, efficient protocols for succinct histograms." Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015.

The performance deteriorates for larger $b$ and depend on minimal gap. How does $b$ and gap interacts? It appear to me that a larger minimal gap leads to a larger $b$.

Existing lower bounds show that the rank error must grow with $b$, both under pure and approximate differential privacy. The gap we need between quantiles is proportional to $\log(b)$. Since the gap is inversely proportional to the number of data points $n$, the value of $n$ needed to answer a given set of quantile queries grows proportionally with $\log(b)$.

Dear reviewer,

We are happy to answer any follow-up questions and comments that you might have. Thanks for your time and feedback!