Instance-Optimality for Private KL Distribution Estimation

We thank the reviewer for their feedback and suggestions, and we will be sure to rearrange proofs and correct the typos to improve the presentation clarity in the revised paper.

Comparison to Good-Turing estimator

We apologize for the confusion, we discussed the comparison briefly in line 137-151, but will devote more space to further clarify this important question.

Both the Good-Turing estimator and our “sampling twice” estimator reduce the bias (compared to the empirical estimator), by estimating and distributing combined mass. The main advantage of the “sampling twice” trick compared to the Good-Turing estimator lies not in utility, but rather in its significantly lower sensitivity to neighboring datasets, thus being easier to privatize and remain instance-optimal even in the DP setting. (See Line 139-151 for detailed sensitivity comparison.)

In terms of practical performance, the Good-Turing estimator as well as its hyperparameter choice has been extensively studied in prior works and thus the existing baselines are very strong. Our work gives the first provably instance-optimal (up to constants) algorithm, and gets very close to the best existing baselines. However, since our sampling-twice approach processes two disjoint subsets, it incurs twice the (sampling) noise in extreme cases (e.g., when all symbols are above or below threshold), leading to a suboptimal constant of two. This tradeoff can be partially mitigated through hyperparameter tuning, such as adjusting the dataset partition ratio, as discussed in Section 4.

Does Good-Turing attain instance optimality under additive neighborhood

This is a great question. We are unaware of negative results. Nevertheless, the existing analysis for Good-Turing would result in a $\ln(n)/n$ additive gap compared to the lower bound we obtain under additive neighborhood. The main gap is that the Good-Turing’s error for combined probability estimate is $\ln n/n$ (as in Lemma 19 of Orlitsky & Suresh (2015)) due to delicate correlations between partitioned buckets (of small symbols) and their combined mass estimates, rather than $1/n$ in our sampling-twice estimator (as in eq 191 that applies Lemma B.10) facilitated by using fresh counts for small symbols to estimate combined mass. We will add this discussion in the revised version to clarify the comparison.

We thank the reviewer for the recognition and feedback. We will be sure to address the typo in the revised paper.

We thank the reviewer for their comments and feedback. We will improve the presentation and arrangements of statements and proof for better clarity in future revisions. Below we address the questions.

Two-point neighborhood and multiplicative neighborhood

We apologize for the confusion and will clarify the existing results better in an updated version. Yes, Line 92-101 discusses their main limitation as being too small to permit instance-optimal algorithms, as their lower bounds largely remain unchanged under growing dimensionality of the problem.

• Two-point neighborhood: the lower bound comes from distinguishing two hypotheses based on the observed data. The primary factor determining this lower bound is how “separated” the two hypotheses are, not the number of features or dimensions of the data. Consequently, lower bounds for two-point neighborhoods typically do not grow with dimensionality of the problem, as evidenced by prior works [21,44,6].
• Multiplicative neighborhood: the lower bound comes from distinguishing the target instance with other distributions that lie in its multiplicative neighborhood (e.g. of a factor of 1/2). Consequently, the lower bound is at most a constant that equals the multiplicative ratio (e.g., 1/2) of the neighbourhood size.

By contrast, there are instances (such as long-tailed instances in our particular distribution estimation problem) whose estimation error inevitably grows with data dimension (e.g., of scale $\ln d/16$ in our Theorem G.9 construction), indicating that the two-point neighborhood and multiplicative neighborhood are too small.

Discussion of Asi & Duchi’s earlier works on instance-optimal DP estimation:

We thank the reviewer for pointing out that we missed discussing the works of Asi and Duchi [a, b]. Their first work only deals with one-dimensional quantities. Their Neurips 2020 work discusses high-dimensional problems defined on the dataset (rather than on the distribution as in our work). The notion of local minimax optimality there includes all datasets at a certain distance, whereas their second notion only competes with unbiased algorithms. We will add discussion of these works to the final version.

• [a] Asi, H., & Duchi, J. C. (2020). Near instance-optimality in differential privacy. arXiv preprint arXiv:2005.10630.
• [b] Asi, H., & Duchi, J. C. (2020). Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems, 33, 14106-14117.

A table summarizing many previous works described in paragraph 2 of Section 1.2

For the DP setting, to the best of our knowledge, there are no known results for the KL minimax rates or instance-optimal rates, thus we only summarized our results in Tables 3, 4, and 5, and summarized prior non-DP results in Tables 1 and 2. Guarantees in $\ell_1$ and $\ell_2$ error are nicely summarized in [Acharya, Sun, and Zhang 2021, Table 1-2].

$n \varepsilon>1$ requirement

This is a great question. Typically private estimation considers the scenario of epsilon>1/n. Indeed if $\varepsilon<1/n$, then by group privacy, the output distributions of the algorithm on any two datasets D and D’ (of size n) should be within a constant factor of each other. In other words, the algorithm output is essentially independent of the input dataset, and this is an uninteresting regime.

Technically, our proof requires $n \varepsilon>1$ mainly to ensure that perturbing low probability symbols to $1/n\epsilon$ is valid, i.e., $1/n\epsilon<1$. Thus essentially this constant 1 can be relaxed to any other constant, albeit changing the multiplicative constant in our obtained lower bound.

Intuition for “privacy for free” regime in line 264

Intuitively, for symbols with large enough probability, the noise added due to privacy has variance 1/\epsilon^2, while the inevitable statistical variance of the symbol’s frequency under natural poisson data sampling is $np_i$. Thus when $p_i$ is large enough, the error due to privacy is negligible compared to the statistical error, i.e., privacy is “for free”. The $1/n^2\epsilon^2p_i$ term in our DP lower bound (Eq 7), compared to the $1/n$ term in our non-DP lower bound (Eq 5), captures this phenomenon.

We thank the reviewer for their suggestions, and will incorporate them to improve the presentation to make the main body more self-contained. Below we answer the questions.

Approx-DP

Our per-instance lower bounds hold for (eps, delta) approx-DP with delta<epsilon, and match the upper bound achieved by pure-DP algorithms. This indicates that our pure-DP algorithm, while enjoying better privacy guarantees, is also instance-optimal under approximate DP. Similar phenomena have previously been observed for the histogram estimation problem under approx-DP, where in the asymptotic sense, approx DP (e.g., Gaussian mechanism) offers little advantage over pure DP (e.g., Laplace).

In the practical sense, indeed the Gaussian mechanism may be practically better in some regime of parameters (due to the lighter distribution tails compared to Laplace mechanism). And our algorithm (after substituting Laplace mechanism with Gaussian mechanism and changing threshold to calibrate to delta) achieves instance optimality up to a log(1/\delta) factor. We will include the Gaussian variants of our algorithm and its instance-optimality proof in the future revised paper.