Instance-Optimality for Private KL Distribution Estimation

We study the fundamental problem of estimating an unknown discrete distribution p over d symbols, given n i.i.d. samples from the distribution. We are interested in minimizing the KL divergence between the true distribution and the algorithm's estimate. We first construct minimax optimal private estimators. Minimax optimality however fails to shed light on an algorithm's performance on individual (non-worst-case) instances p and simple minimax-optimal DP estimators can have poor empirical performance on real distributions. We then study this problem from an instance-optimality viewpoint, where the algorithm's error on p is compared to the minimum achievable estimation error over a small local neighborhood of p. Under natural notions of local neighborhood, we propose algorithms that achieve instance-optimality up to constant factors, with and without a differential privacy constraint. Our upper bounds rely on (private) variants of the Good-Turing estimator. Our lower bounds use additive local neighborhoods that more precisely captures the hardness of distribution estimation in KL divergence, compared to ones considered in prior works.

Problem Setting Let p ∈ ∆(d) := p ∈ R d : p 1 , • • • , p d ≥ 0 and d i=1 p i = 1 be an unknown distribution over d symbols. Let x ∈ N d be the histogram representation of a dataset consisting of empirical samples drawn from distribution p, where x i denotes the count of symbol i in the dataset. Following prior works [2, 49], we assume that the count of each symbol i is independently drawn from a Poisson distribution with mean np i , i.e., (

This assumption is a convenient choice for analysis as it ensures independent sampling of each symbol, while enjoying the benefit of being equivalent to sampling from multinomial distribution when conditioned on a fixed dataset size n. Our goal is to design an algorithm that accurately estimates the unknown distribution p in KL divergence given a sampled dataset x ∼ Poi(np).

We start by looking at the (private) KL distribution estimation problem from the standard minimax optimality objective, where the goal is to design estimators A that minimizes the KL error on the worst-case distribution instance.

where KL(p∥A(x)) = i p i log pi A(x)i , and the expectation is over the randomness of estimator A and over the sampling of x ∼ Poi(np). This minimax objective (1) is well-studied for non-DP algorithms, where simple add-constant estimators are proved to be minimax optimal with O ln 1 + d n rates [10, 52] (see Appendix C.1 for a complete discussion of the existing results). For the DP setting, to the best of our knowledge, there are no known results for the KL minimax rates. Nevertheless, in Appendix C.2, we show that a similarly simple algorithm (that truncates the Laplace perturbations of empirical counts) achieves the minimax optimal O ln 1 + d εn rates.

However, such simple estimators achieve poor performance in experiments (Section 4) on commonly occurring distributions such as power-law distributions. Similar observations, i.e., the poor performance of the minimax-optimal add-constant estimator (compared to the practical Good-Turing [33] estimator), have long existed in the non-DP setting. This is intuitively because minimax optimality only captures the worst-case error over all possible distributions, thus failing to indicate whether an algorithm performs well for each non-worst-case distribution p.

Instance-optimality Instance-optimality is a promising framework to address the above limitation of minimax optimality and shed light on the per-instance provable performance of an estimator. In the non-DP setting, many works have studied instance-optimality in different contexts, such as local minimax estimation [21,47,23], competitive distribution estimation [2, 49] or instance-by-instance analysis [59]. Remarkably, the seminal work of [49] proved that a simple variant of Good-Turing estimators is nearly instance-optimal, in that it estimates every distribution nearly as well as the best estimator designed with prior knowledge of the distribution up to a permutation. The recent work by Feldman, McMillan, Sivakumar and Talwar [30], further generalize this instance-optimality definition to other natural definitions of prior knowledge in the language of per-instance neighborhood. Formally, we follow Feldman, McMillan, Sivakumar and Talwar [30] and define instance-optimality as follows.

Definition 1.2 (Instance-Optimality to Neighborhood Map N [30]). We say an estimator A is instance-optimal with respect to a neighborhood map N if:

where lower(p, n, N )

That is, instance-optimality says that the algorithm A is competitive with any hypothetical algorithm A ′ that has auxiliary knowledge about the neighborhood N (p) of the input distribution p. We can further constrain the algorithm to be (ε, δ)-DP in establishing the per-instance lower bound as follows.

This is the lower bound that we will use for establishing instance-optimality of pr