Instance-Optimality for Private KL Distribution Estimation
Authors: Jiayuan Ye
Vitaly Feldman
Kunal Talwar
Venue: NeurIPS 2025 spotlight ()
Keywords: Differential Privacy
Distribution Estimation
Instance-Optimality
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: 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.

Instance-Optimality for Private KL Distribution Estimation
Jiayuan Ye" National University of Singapore
Vitaly Feldman Apple
Kunal Talwar Apple
Abstract
We study 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 opti- mality however fails to shed light on an algorithm's 's performance on individual noon-worst-case) instances and simple minimax-optimal DP estimators have poor empirical performance on real distributions. We then study this problem from instance-optimaliiy viewpoint, where the algorithm's 's error 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
to constant factors, with and without a differential privacy constraint. Our upper bounds rely on (private) variants of the Good-Turing esti- mator. Our lower bounds use additive local neighborhoods that more precisely captures the hardness of distribution estimation in KL divergence, compared ones considered in prior works.
1 Introduction
Accurately estimating a discrete distribution (over d symbols) from the empirical samples is fundamental task in statistical machine learning. An especially important distribution estimation (KL) divergence error, as it is crucial in promoting diversity and
objective is the Kullback-Leibe smoothness by penalizing zero-mass assignment to unseen symbols. Noticeably and language modeling communities, negative log likelihood on a test set (which up to translation the measure that has been found best correlate with the performance of the model [3] 14], and is therefore the standard loss being optimized for. Additionally, KI. error is well-established in the coding community [8 422 the context of data compression (i.e., identifying encoding that represents the information with fewer bits). Due to this reason, KL distribution estimation has been extensively studied [62
ppeech-recognition
the KI. divergence)
52
However, overly fine-grained release of statistics make it possible to infer the memberships 37
55
or even reconstruct the values 20 12 of input data records. To this end, differential privacy 226 offers powerful mathematical defimition to provably control the associated privacy risk.
28
56
Definition 1.1 (Differential Privacy (DP) (6)). A (randomized) algorithm A is (s, d)iffeerrentl private ((E, 8D-D if for all neighboring datasets æ, x' that differ at most one sample, and any measurable output set T, Pr[A(x) T < e Pr(A((') e T 8.
Our work aims to provide an understanding of the KL error of private distribution estimation. Below present the problem setting and summarize known results and our contributions.
Research done while at Apple
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Problem Setting p E (dd = {p E P..... PP 2 0 and P: = 1} be an unknown distribution over d symbols. Let x: E Nd be the histogram representation of a dataset consisting of empirical samples drawn from distribution p. where x; denotes the count of symbol in the dataset. Following prior works 2 [9, we assume that the count of each symbol i is independently drawn from a Poisson distribution with mean rip;, i.e. (2I,...,, ~ Poi(up) := Poi(npI) x x... X Poi(npa)) This assumption is 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 fixed dataset size Our goal is to design algorithm that accurately estimates the unknown distribution p in KL divergence given a sampled dataset x ~ Poi(np).
Minimax Optimality Results (and Their Limitations) 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 the worst-case distribution instance.
min max E [KL(p, A(x)) KL(PIIA(z)) = Σ ps log pEA(d)
Ps
(1)
A(x),
Ps where (L(p]|A(x)) = E; log A(z). and the expectation is over the randomness of estimator A and over the sampling of x Poi(np). This minimax objective ( is well-studied for non-DP algo- rithms, where simple add-constant estimators are proved to be minimax optimal with O (In (1 + #)) rates [10 52) (see Appendix [C. a complete discussion of the existing results). For the DP setting, 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 (In (1 + )d)) 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 perfor- mance of the minimax-optimal add-constant estimator (compared to the practical Good-Turinn 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.
[33
Instance-optimality Instance-optimalliy is 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 eestance-optimaliy in different contexts, such as local minimax estimation [21 47 23), competitive distribution estimation 2 44 or instance-be caetnnce-b--intttte by-instance analysis [59]. Remarkably, the seminal work of [49] proved that simple variant of Good-Turing estimators is nearly -ostance-optimal,, in that estimates every distribution nearly as well as the best estimator designed with prior knowledge of the distribution up permutation. The recent work by Feldman, McMillan, Sivakumar and Talwar (30, further generalize this instance-optimality definition other natural definitions of prior knowledge in the language of per-instance neighborhood. Formally, we follow Feldman, McMillan, Sivakumar and Talwar 330 and define instance-opiimaliy as follows.
Definition 1.2 (Instance-Optimality to Neighborhood Map N instance-optimal with respect to neighborhood map N if:
30
We say an estimator A is
Vp E (d) : E[ A(x)) < O (lower(p, n, N)) where lower(p, n, N) def
min max E (KL(g.A((z))) for neighborhood ((p) of (2) gEN(p)
That is, instance-opiimality says that the algorithm A is competitive with any hypothetical algorithm A' that has auxiliary knowledge about the neighborhood (p) of the input distribution p. We can further constrain the algorithm to be (s, DD in establishing the per-instance lower bound as follows.
lower a (p. N)
min max E [KL A(r))
Ais (P...))DPPEENN
This is the lower bound that we will use for establishing instance-optimality of private algorithms.

---

Limitations of Prior Instance-Optimality Objectives for KL Error In instance-optimalle results, the smaller the neighborhood, the stronger the result. This is because we are proving that our algorithm is competitive with a hypothetical algorithm that already knows that the input distribution is in the neighborhood. However, if the neighborhood too small, then no algorithm can be instance-optimal, as the baseline estimator's ' knowledge of the instance is overly precise. (As an extreme example, when (p)) = {p} contains only the target distribution p. the per-instance lower bounds (2) and (3) trivially become zero (as achieved by an estimator that always outputs A(x) = p regardless of the input dataset).) Below we review existing choices of neighborhood N (p) in the literature, and show they either too large too small to accurately capture the per-instane instanct estimation hardness in KL.
(x) = {q 3 permutation π s.t. q: Proi, Vi E [d]]. i.e., all distributions obtained by permuting the probability values. On the one hand, prior work [30] has argued that this neighborhood is too large, as practical estimators often have stronger knowledge about which symbols are more frequent than others (e.g.. the word "and" is often more frequent than "differential", thus assuming the two words are permutable is not reasonable). On the other hand, permutation neighborhood can be too small, in that provably does not allow for multiplicative instance optimality guarantees, as discussed in Section 2.2. Indeed, permutation neighborhood assumes precise knowledge of the set of true probability values, which can be overly strong for any realistic estimator to satisfy.
Permutation neighborhood 22
49 59]:
Two-point neighborhood 23 : N2(p) = {pp q) contains the target instance p and another alternative distribution 9 that is "close" p. This neighborhood reduces the per- instance hardness to binary hypothesis testing of whether the observed samples are from p q. Under appropriate notions of "close", this neighborhood allows matching per-instance upper and lower bounds for estimating one-parameter (exponential) families distribution under central DP (47 and local DP [33. as well as for general one-dimensional statistical estimation problems [8] However, for high-dimensional problems, this neighborhood is provably too small, as the per-instance lower bound remain constant under growing data dimension, despite the growing hardness for distribution estimation under higher dimension. For example, there exist instances (such as long-tailed instances in our particular distribution estimation problem) whose estimation error inevitably grows with data dimension (e.g., of scale In d/16 in our Theorem G.9 construction), indicating that the two- two-point neighborhood and multiplicative neighborhood are too small. Indeed testing can be provably easier than learning in simple settings.
(x {q 1p; 5 S: S 2p,, Vi E [d]] It allows matching per-instance upper and lower bounds for distribution estimation in Wasserstein distance. However, this neighborhood is too small to capture the KL error: the per-instance lower bound is at most a constant (since an algorithm that is tailored to N()) can achieve O(1) error), whereas such error bound is provably unachievable for some distributions (c.g., our Thcorem G.9 construction).
Multiplicative neighborhood 30
5 on instance- optimal DP estimation also considered other variants of neighborhoods that have similar limitations. 7 only deals with oinedimnnsl quantities, and 6 discusses high-dimensional problems defined on the dataset (rather than on the distribution as in work). The notion of local minimax optimality there includes all datasets at a certain distance, whereas their second notion only competes with unbiased algorithms. These limitations call for new definitions of local neighborhood to precisely capture the per-instance hardness of distribution estimation in KL divergence, which we study in this paper.
Besides the above three representative types of neighborhoods, earlier works 7
Our Main Contributions: Instance-Optimal Results
We define instance-optimality objectives that more precisely capture the hardness of private KL distribution estimation. This is by constructing new neighborhoods 44) and (6) that additively perturb the probability values p; of individual symbols. We use small perturbation scales- 1/n, 1/nc, and Vp,/n to ensure the dataset (sampled by p) could plausibly have come from other distribution in the neighborhood. (See Section 2 and 3 for more rationales on the neighborhood sizes.) This is stronger than permutation neighborhood 2 49. [59] in allowing auxiliary knowledge of frequency order among symbols, and is thus a very strong notion of instance-optimallty. Furthermore, we show in Section
3.1 that our
3

---

additive neighborhoods are (up to constants) the smallest that still allow for instance- optimal algorithms.
Under such additive neighborhoods, we propose a new non-DP algorithm and prove it to be instance-optimal (Section 2.1). Our algorithm resembles the idea of the Good-Turing esti- mator (which is known to be instance-optimal in prior works), while ensuring significantly smaller sensitivity to adjacent datasets (in the DP sense). This reduced sensitivity the key that makes our algorithm easier to privatize. We then propose a DP version of this algorithm and show that
instance-optimal amongst DP algorithms (Section 3.1
We validate the performance of our instance-optimal estimators via experiments (Section 4 and show the reward from studying instance-optimallty: while the Add-constant (DP) algorithm is already minimax-optimal, our instance-optima algorithms achieve significantly better performance on many instances of practical interest, such as power-law distributions and real-word token distributions.
1.1 Technical Contributions
Generalized Assouad's 's method for decomposable statistical distance Standard tools for proving lower bounds, such as (DP) Assouad's method [65]
3 30], only apply to symmetric statistical distance, which is not satisfied by KL divergence. To prove KL per-instance lower bound, we propose
generalized (DP) Assouad's 's method (Theorem A.3 and A.4) that applies to general decomposable
statistical distance (Definition A.T This allows us prove strong per-instance lower bounds.
Reducing the Sensitivity of Good-Turing Estimator via "Sampling Twice" The challenge of privatizing the prior (near) mastance-optima Tord-Turing estimators lie in its excessively high sensitivity to neighboring datasets. At the core, Good-Turing estimator motivated by observing that estimating "unseen" symbols as zero- puro-probability is biased, as the symbols that appeared exactly once would intuitively have similar probability values (which are non-zero). To correct this bias, recursively uses the counts of symbols with frequency ++ to estimate the probability of symbols that appeared times, for all low-frequency symbols (e.g.. t t= 1,... 1/33 in Orlitsky and Suresh [49). Such computations suffer from high sensitivity, as one record could change the combined counts of symbols with frequency / by i 1/3 in the worst-case. To address this limitation, we perform bias-correction via an alternative "sampling twice" approach: partitioning the dataset into two halves, using one for identifying "unseen" symbols and the other for estimating their combined mass. The resulting Algorithm[ is conceptually simpler than prior Good-Turing estimators, while achieving tight instance-optimality guarantees (up constants) and being empirically competitive in experiments. Crucially, this "Sampling Twice" design reduces sensitivity to just one (making the estimator easy to privatize), and is the key to achieving opttiacy-y in the DP setting.
Effectively Privatizing Good Moriig Estimator via Calibrated Thresholding The Good-Turing estimator is based on the intuition that the probability values of symbols that appeared zero times (in the dataset) are similar to those of symbols that appeared exactly once. However, this simple zero-or-one thresholding does not remain effective for private algorithms, because DP estimates cannot differ significantly on neighboring input datasets. This forces us to use a larger threshold. To identify the best threshold for DP distribution estimation, given every possible threshold, separately analyze (Thcorem E.2 and the DP estimation eиror due to False Negatives (FN) (i.c., sighhprbbbbbiittyy symbols being below-threshole versus False Positives (FP) (i.e., proobabbyyyyity symbols being threso.hressold.. This analysis allows us to choose a threshold that balances the FN and FP errors, and achieves DP instance-opiimality up constant factor (Section 3.11..
1.2 Other Related Works
The Good -oriig estimator, originally developed by [3 and simplified by [1|49]
49 has been widely
observed to yield empirically accurate distribution estimates (especially for language modeling under large vocabulary size). Several later works prove it to be minimax optimal [46]
tasks 40
[
22
50
as well as instance-optimal 2 49 for discrete distribution estimation in various metrics.
However, to our knowledge, no prior works have designed or analyzed DP variants of Good-Turing
estimator, which is the main technical innovation of this paper.

---

For DP discrete distribution estimation, minimax optimality is well-studied across a variety of models
for DP, including central DP [9 31. local DP
[24 38 64 25 | and user-level DP 44
Existing
works also focus on different error metrics, such as total variation distance (i.e., l error) 19 and &
error (3] (see summary results in 3 Table 1-2)). Our work falls into the central DP setting, and
the first to study the KI. divergence error. Additionally, we establish the stronger instance-opiimality (rather than minimax optimality). The closest work to our paper in the literature is [30], where the authors study instance-optimad density estimation in Wasserstein distance (that covers discrete distribution estimation in & error as a special case). The results in (30 are largely incomparable to analysis, due to the lack of (tight) conversions between total variation distance error and KL divergence error. (See Appendix C.2 for a nuanced comparison between prior TV distance lower bounds and our KL lower bound for DP minimax distribution estimation.) Indeed, achieving optimality under KI. often requires non-trivial change to the algorithm and analysis compared to L error, evidenced by the abundant literature distribution estimation in KI. 10 52 2 49)
closely related problem frequency estimation (a.k.a. histogram estimation), where the goal is to privately and accurately estimate the empirical distribution. DP histogram estimation is extensively studied in a variety of models for DP, including central DP [34 63], local DP (9 61], and shuffle
DP 229 15 32
Due to sampling error, algorithms for empirical frequency estimation typically do not directly yield good utility for distribution estimation.
2 Tighter Instance-Optimalit for Non-DP Estimation
We first define Instance-optimalle under additive neighborhoods, that get around the limitations of previously studied neighborhood notions as discussed in Section
Neighborhood Choices As discussed in Section D a good neighborhood should be as small as possible and contain distributions that similarly hard estimate compared to the target distribution instance. Additive neighborhood is thus a natural choice as intuitively, the hardness of distribution estimation does not change lot when perturbing each symbol's probability by a small amount. The key question is how small should the scale be. To this end, our main design choices are
1. For every symbol, we allow up to t/n perturbation, for small t 1. This only changes its expected count to f, and thus from the the empirically sampled count, it is hard to distinguish the perturbed distribution from the target distribution.
2. For symbol with large p; t/n, we allow larger / P/// perturbation, for small 2 1. This captures the fact that with constant probability. counts sampled from Poi(np;) and Poi(ni: + /rip:) are "indistngguihaable" due to the statistical variance in sampling. Indeed these are related to the standard confidence intervals for binomial estimation [6
On top of these design choices, we try reduce the size of the neighborhood as much as possible. Thus we add a constraint that the combined mass of small symbols (with p; I & given small t 2 1) should not change by more than & - this added condition only makes the results stronger (as the resulting neighborhood is smaller). As a result, we obtain the following additive neighborhood.
(p) { q Vi E [d], la. - pvl S min
Ps
and Σ ge S max {
Σ S
ptj
Per-Instance Lower Bound We next prove per-instance lower bound under this neighborhood (p).). Our analysis requires generalized variants of Assouad's method (discussed in Section 1.1
We defer all proofs to Appendix [D. and only present the per-instance lower bound below.
Theorem 2.1. Let p Add) be an arbitrarily fixed distribution instance. Let N (p) be the additive neighborhood defined in (4) If d 2 2 and n Z 4, then we have
In(1 + dsmat (L')) Paamall (L') (1+
dsmaulL') (L') Tip Topomatt( (L) + Σ min pis n1
#)
1
lower(p, n, N
n
(5)
for any t 2 and any set L' S [d], where Psmali())
Σ
P; and d demat(lL)
Σ
1.
iEL $
iEL
S.
5

---

KL Error Bound
Reference
Pi Σ
lower(p, Na))
?
21=0 poPoi(np))
Σ
In
40
Lemma 4 & 5]
N,: permutation neighborhood
Add-constant
lower(p, n, Nx)
min
1/3 11/3
Lemma 1]
Good Turing
lower(p, n,, Na) ) +
min n2
1/3
49
Theorem 1]
Smoothed
lower(p, N₂) O
min
1/2
49
Theorem 2]
Good-Turing
2
Theorem 2]
Any estimator
lower(p, n, N,)
min
71
2/3
Theorem 3J
Table I: Prior instance-optimality results of Non-DP estimators
Algorithm Non-DP "Sampling Twice"
Data partition ratio a = 0.5. Independently sampled datasets x ~ Poi(a np) and x' Poi((1 a:) np) s.t. x. + x' Poi(np). Threshold Thresholding: = {i E [d] 02 ST}
Input:
Estimate combined mass for symbols L: ē= max 1EiEL x/,1}
Truncate individual estimates: let T; max (1/, 13 for = 1,...
C Eier 3g
B
i L
Return A(x) with A(x);
N
where N =ē Eiel
i
N
To interpret this lower bound, first observe that (5) is always smaller than the (1 + d) minimax lower bound, especially when there are many small symbols (with p; < = that jointly takes a small combined mass Psmat (I'). As extreme example, imagine highly concentrated distribution p = (1/3, 2/3, 0, ... 0), then our per-instance lower bound ( is as small as In(1+d) This is significantly smaller than the In(1 + 4) minimax lower bound for high-dimenssonal setting (d + oo), thus correctly indicating that p is an extremely easy-to-estimate distribution. Achieving error upper bound that matches this small per-instance lower bound (5), then serves as a strong requirement for optimal algorithm fulfill (which we prove in the next section).
2.1 An Instance-Optimal "Sampling Twice" Estimator
We now present simple "sampling twice" Algorithm D and prove that it is instance-optimal to constants. Compared to the minimax optimal add add-constantt estimator, this algorithm observes that simply estimating "unseen" symbols as gero-probability (or constant-probabile procedure to correct the bias of low-frequency symbols.
is heavily biased,
and use a conceptual "sampling-
As discussed in Section 1.1 this bias-correction idea originates from prior (near) pestance-opting
Good-Turine Turing algorithm [33 31 49 and maintains their utility benefit. The key benefit of our "sampling- twice" design lies in significantly reducing the estimator's 's sensitivity to neighboring dataset (making easier to privatize), enabling instance-opiimality under DP (as we will show in Section 3).
Instance-optimality Guarantee In Theorem E.2 we prove a per-instance KL error upper bounds In Corollary E.3 we further prove that this
for the "sampling twice" estimator (Algorithm
upper bound can be rewritten as E KL A(x)) s O (lower(p, n, N4)) for any choice of
z~~Po((p))
neighborhood size 2 s.t. e 1 1/ d. Specifically, we can choose t = min in
2.2 Comparison to Prior Instance-Optimality Results
In this section, we discuss and compare with prior instance-pptimality results, which mainly cover two representative DP estimators the add-constan estimator and the Good-Turing (GT) estimator.

---

Add-constant Estimator Given by A(x) 2; + c, vi [d] for a constant > 0. the add-constamt estimator one of the oldest and simplest distribution estimator. Its variants cover several known estimators, such as Laplace smoothing (c 1) and Krichevskk-Trofimox estimator 42 (c 1/2).
Good-Turing Estimator 3
The Good-Turing estimator 33 when combined with add-constant
estimator, has long been observed to yield strong empirical performance. Many variants of GT estimator exist in the literature 33 Turing estimators proposed in Orlitsky and Suresh [49], that is also provably (near) instance-optimal under the "permutation neighborhood", i.e. distributions obtained by permuting the distribution.
31 49]. the comparison, we use the simplified variant of Good-
We summarize these prior instance-optimaliy results under permutation neighborhood in Table T Apart from the fact that this neighborhood may be too large be appropriate for some applications (as discussed in Section D. the last row of Table T shows a lower bound for the suboptimality it shows that no algorithm can do better than an additive min (n- # compared to a hypothetical algorithm that already knows the neighborhood. Observe that this additive gap is lot larger than the per-instance lower bounds for certain distributions, e.g., highly concentrated distributions. Thus, multiplicative instance optimality not achievable with permutation neighborhood. By contrast, tight instance-optimlliy (up constant) is achievable under our additive neighborhood, as proved in Section 2. We will also discuss Section 3.J that our additive neighborhoods are the smallest (up to constants) that can still allow for the possibility of any DP instance-optimal algorithms.
Additionally, the existing analysis for Good- would result in ln n/n additive gap compared to the lower bound we obtain under additive neighborhood. The main gap is that the Good-Turing ' error for combined probability estimate is In n/n (as in Lemma 19 of [49] due delicate correlations between partitioned buckets (of small symbols) and their combined mass estimates, rather than 1 1/n in our sampling-twice estimator (as in (T9)) that applies Lemma [B 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.
DP Instance-Optimality
In this section, we present the first results for DP instance-optimallty of KI. distribution estimation.
Neighborhood Choices To define appropriate DP instance-optimality objective, we modify the N neighborhood (4) with perturbations calibrated to the privacy parameters. For small 2 1, let
N (p. n) 9: ::: pul S
1 for any E [d] and
Σ ipp.
2i S max
Σ MP
Ps
(6)
Compared to (4), the main change is that we allow the perturbation scale for individual symbols to be proportional to 1/s. This corresponds to the obliviousness of (e, 5)-DP algorithm to dataset changes up to O (2) hamming distance (which allows an additional ne change in probability).
DP Per-Instance Lower Bound Under the above neighborhood Ng (p,n) that is calibrated to (e, 5DD guarantee, we prove the below per-instance lower bound.
Theorem 3.1. Let p (dd) be an arbitrary distribution instance, and let Ne - (p) be the additive neighborhood defined in 66. 1f6 S d d 2, and nE 2 1, then we have
lowers.8 (p.n, N, N 2 Ω Σ min
1 Pi: pi n²E²
In (1 demall (L))
ME
+ Psmall (L') In (1+ dL'mal(L')
(7)
ne Pomati (I.)
for any 2 and any set L' C [d]. where PsmallL1
Σ
pi and demau(L')
Σ 1. K +
7

---

Algorithm 2 e-DP "Sampling Twice" (Instance-Opimaa))
Inputs: Data partition ratio = 0.5. Independently sampled datasets x Poi(a np) and x' Poi((1 - ar) up) s.t. x + x' Poi(up). Threshold = 4 In
=
for symbol i= 1, .... do
Private Thresholding: If 24 min (e.( for 2, Lap (0, 2 add i to L end for
Estimate small symbols' combined mass: == max Eiel H Lap (0, : minte.ly }
Estimate individual large symbols: for E [d] \ I, L, x2 + of for o ~ Lap (0. 2
Truncation:
Fy = max T2.. min(c,1) for
E LA Iz = (1
a) maxx Tii min max f minte,ll }) for E [d] \ I.
1
ē Eier
iEL L
Return A(x) with A(x),
N
where N = c Σiel Zz
1
i i
N
The proofs are deferred to Appendix The lower bound 7 consists of three terms:
1. Cost of privacy for large symbols p; ne corresponding non-DP lower bound ( in (5) when is large enough, i.c., privacy is free for sufficiently large ps.
is " which is significantly smaller than the
In In(I+dmmmu (T.')
2. Cost of privacy for combined mass estimate of small symbols S +. is which is non-zero whenever there exist small symbols L'.
3. Cost of privacy for small symbols p; < f ns
is Psmall In (1+ demait ne-Pomait
Σ Pi:
i<
which is larger than the corresponding non-DP lower bound in for small symbols whenever << 1, i.e. in the high privacy regime.
3.1 Privatized Instance-Optimal "Sampling Twice" Estimator
We then propose privatized variant of "sampling- ttiie" Algorithm 2 by applying the Laplace Mechanism [26]. The e-DP guarantee follows from standard results in DP by observing that the & sensitivity of 1=1,- ... Ty, x'. x'a) one. The main novel ingredient (as discussed in Section I.1 is to choose calibrated threshold for privately selecting a set of small symbols. This selected set then used for estimating the combined mass of small symbols on fresh samples. An accurate combined mass estimate is the key to reducing KL eтrоr.
Instance-optimaalit Guarantee In Theorem G.6 we prove a per-instance upper bound for Algo- rithm 2 In Corollary G.7, we further prove that this upper bound can be controlled by the per-instance lower bound under the combination of our Non-DP addditive neighborhood N+(p) in (4) and our (c, 6DP calibrated neighborhood in (6). Specifically, under neighborhood size t = 24 In d, we prove
that E p>-Poinp)
(KL(P,A(x))) & 0 [lwwer (, N+
Discussions the Neighborhood Size We have established instance-optimality under local neighborhood N Natun . It is a natural question to ask whether the size of such neighborhoods could be further reduced to enable stronger instance-optimall this neighborhood size necessary up to constants-no no DP estimator can be instance-optimal for neighborhood N 2iin with 5 o1).
notions. In Theorem (.9 we prove that
Discussions on Approximate DP variants Our per-instance lower bounds hold for (e, -apppox- DP with 5 < E, and match the upper bound achieved by pure-DP algorithms. This indicates that our pure-DP algorithm, while enjoying better privacy guarantees, 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, however, the Gaussian mechanism may he practically better in some regime of parameters (due to the lighter distribution tails compared Laplace mechanism). And our algorithm (after substituting Laplace mechanism with Gaussian mechanism and changing threshold to calibrate to delta) achieves instance optimality up log(1/8) factor (see the Gaussian variants of our algorithm and its instance-optimality proof in Appendix G.5
Experiments
We now evaluate the performance of our algorithms and compare them with baselines. All experi- ments are performed on a MacOS intergrated CPU (S 30 minutes) with 18GB RAM. All reported performance numbers are averaged across five random trials of data sampling and estimators.
Add-constant (DP)
Good Turing
Our Algorithm
Our Algorithm (DP)
8.5
10
7.5
8
9
7
7.5
10
105
10
105
10-2
10-1
100
Dataset size n2
Dataset size n
Specified E
(a) d = 30522, 1 (Bert)
(b) d 50257, (GPT2)
(c) 10 d 50257 (GPT2)
Figure 1: (Reddit Token Distribution Estimation) KI. error versus dataset size n, distribution dimension d, and DP guarantee for our methods compared with the simple minimax optimal Add-constant (DP) baseline, and the strongest non-DP baseline of prior (near) instancc-optimal Good-Turing estimator.
Add-constant (DP)
Good-Turing Turing
Our Algorithm
Our Algorithm (DP))
2
KL Error
2
1.5
1
1
0.5
0
102
103
10a
10
102 10a 10a 105
10-1
10
10
Dataset size
Data dimension d
Specified
(a) d = 50000, E =1
(b) n = 2000, E =
(c) n 1000, d 10000
Figure 2: (Power law distribution p: 3)) KL error versus dataset size n, distribution dimension d, and DP guarantee e for our methods compared with the simple minimax optimal Add-constant (DP) baseline, and the strongest non-DP baseline of prior (near) instance-optinal Good- Good-Turing estimator.
Datasets We evaluate on both synthetic and real-world data distributions. For synthetic data, we evaluate power law distributions Pt şrr over range of parameters 3 >> O. We choose power law because of its practical relevance: word frequencies from a text corpus have long been observed experiment
to roughly follow power law distributions (54 533 48 17 randomly drawn tokens from Reddit [60]. Enron-email
For real-word data, where each token
and MMLU 36 35
is one (sensitive) record. We chose Reddit and Emrin-email datasets because they are user-specific and thus bear a natural notion of privacy risk (compared to e.g., wikipedia), and are standard and widely used text datasets in the private learning literature [58 43 45) We additionally evaluate on MMLU to simulate diverse text domains. To vary the distribution dimension (specified by the number of all possible tokens), we use types of tokenizers (GPT2 and Bert).
One challenge for evaluating real-word dataset is the unknown ground-truth distribution p (as only empirical samples are given). To address this, we independently sample two equal-size datasets

---

and z', thus ensuring E | x' = ps for any ì [d]. We then compute that
] - In
E (p.
Σ
Ps
A(T):
Pi
| In (A(z)),)
Negative Entropy of p
Negative Log Likelihood (NLL)
Observe that the entropy term is independent of the estimator. Thus in experiments we only report the negative log likelihood ratio term to compare different estimators A.
Hyperparameters Although our proposed Algorithm I a 2 are provably instance-optimal. they separately use two disjoint fractions of the dataset. Thus in the extreme scenarios when all symbols ahove below threshold (e.g., when n. d are exceedingly large small), Algorithm T and incur twice as much noise compared to the add-one estimator, incurring a suboptimal multiplicative constant of two. To address this limitation, we perform grid search for the optimal hyperparameters over E {0.01, 0.1, 0.25, 0.5, 0.75, 0.9, 0.99) and E {0, 0.0625, 0.125, 0.25, 0.5, 1, 2, 4] x In d, and use the tumed hyperparameters T = 0, a = 0.5 for Algorithm for Algorithm 2 in all experiments.
and min { 1.0} x In d, a = 0.9
Observations We show results power law distributions Ps je for =, 1,5,, 2(igure and Reddit corpus (Figure []. Enron-email corpus(Figure and MMLU corpus (Figure 6). all experiments, our DP instance-optimal Algorithm Srnnittmmmosiiseeeetyyyyy outperforms the simple minimax optimal Add-constant (DP) baseline, and our non-DP instance-optimal Algorithm[l] [ is consistently competitive (within constants) to the strongest prior non-DP baseline of (near) instance-optimal Turing (50) The gain of our algorithms are especially significant for real-world datasets, validating the effectiveness of our algorithms, We also remark that instance optimality means that algorithm will provably adapt to any input distribution, and no other algorithm can be significantly better (across neighborhood).
2
Good-Turing
Conclusion
We provide tight instance-optimaliin analysis for private KL distribution estimation, in terms of achieving provably competitive error to the best possible estimator in small additive local neighbor- hood of each instance. Furthermore, our constructed neighborhood's size necessary up to constants for instance-optimality
the worst-case instances. Additionally, proved instance-optimality up to constants, and leave open the question of whether exact instance-optimality is achievable. Such results, if possible, would require improving the constants in per-instance privacy lower bounds and/or designing better estimators.
Acknowledgements
The authors thank Audra McMillan and Satchit Sivakumar for insightful discussions the literature, and Daogao Liu for valuable feedback on earlier drafts. Jiayuan is supported by the Apple Scholars in AI/ML PhD fellowship.
References
[1] Jayadev Acharya and Ziteng Sun. Communication complexity in locally private distribution estimation and heavy hitters. In International Conference on Machine Learning, pages 51-60. PMLR, 2019.
[2] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Optimal probability estimation with applications to prediction and classification. In Conference Learning Theory, pages 764-796. PMLR. 2013.
[3] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory, pages 48-78. PMLR, 2021.
10

---

[4] Alan Agresti and Brent A Coull. Approximate is better than "exact" for interval estimation of binomial proportions. The American Statistician, 52(2):19--226, 1998.
[5] David Aldous. Random walks on finite groups and rapidly mixing markov chains. Séminaire de Probabilités XVII 1981/82: Proceedings, pages 243 297. Springer, 1983.
[6] Hilal Asi and John C Duchi. Instance-opimmalit in differential privacy via approximate inverse sensitivity mechanisms. Advances neural information processing systems, 33:14106-14117, 2020.
[7] Hilal Asi and John C Duchi. Near instance-optimality in differential privacy. arXiv preprint arXiv:2005. 10630, 2020.
[8] Hilal Asi, John C Duchi, Saminul Haque, Zewei Li, and Feng Ruan. Universally instance- optimal mechanisms for private statistical estimation. In The Thirty Seventh Annual Conference on Learning Theory, pages 221-259. PMLR, 2024.
[9] Raef Bassily and Adam Smith. Local, private, efficient protocols for succinet histograms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 127-135, 2015.
[10] Dietrich Braess and Thomas Sauer. Bernstein polynomials and learning theory. Journal of Approximation Theory, 128(2):187-206, 2004.
[11] Dietrich Braess, Jürgen Forster, Tomas Sauer, and Hans U Simon. How to achieve mini- max expected kullback-leibler distance from an unknown finite distribution. In International Conference Algorithmic Learning Theory, pages 380-394. Springer, 2002.
[12] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 2/), pages 2633 2650, 2021.
[13] Stanley Chen and Joshua Goodman. An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4):359-394 1999.
[14] Stanley F Chen, Douglas Beeferman, and Roni Rosenfeld. Evaluation metrics for language models. 1998.
[15] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Advances in Frypooogy-EUROOCYYPP 2019: 38th An- nual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part 1 18, pages 375-403. Springer, 2019.
[16] Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-411 1934.
[17] Brian Conrad and Michael Mitzenmacher. Power laws for monkeys typing randomly: the case of unequal probabilities. IEEE Transactions on information theory, 1007):1403-1414 2004.
[18] Thomas Cover. Broadcast channels. IEEE Transactions on Information Theory, 18(1):2-14, 1972.
[19] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. Advances in Neural Information Processing Systems, 28, 2015.
[20] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMODDSIGACTTSIGART symposium on Principles of database systems, pages 202-210, 2003.
[21] David L Donoho and Iain M Johnstone. Ideal spatial adaptation by wavelet shrinkage. biometrika, 8253):225-455, 1994.
[22] Exgeny Drukh and Yishay Mansour. Concentration bounds for unigram language models. Journal of Machine Learning Research, 6(8), 2005.

---

[23] John C Duchi and Feng Ruan. The right complexity measure in locally private estimation: It is not the fisher information. The Annals of Statistics, 52(1):1-51, 2024.
[24] John C Duchi, Michael I Jordan, and Martin Wainwright, Local privacy, data processing inequalities, and minimax rates. arXiv preprini arXiv: 2013.
[25] John C Duchi, Michael Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-201, 2018.
[26] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-286 284. Springer, 2006.
[27] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- fions and Trends@ in Theoretical Computer Science, 9(3-4):211-44) 2014.
[28] Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 650-669. IEEE, 2015.
[29] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468-2479. SIAM, 2019.
[30] Vitaly Feldman, Audra McMillan, Satchit Sivakumar, and Kunal Talwar. Instance-optimal private density estimation in the wasserstein distance. arXiv preprint arXiv:2406. 19566, 2024.
[31] William A Gale and Geoffrey Sampson. Good-turing frequency estimation without tears. Journal of quantitative linguisticss 2(3):2172377, 1995.
[32] Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages: Frequency estimation and selection in the shuffle model of differential privacy. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 463-488. Springer, 2021.
[33] Irving J Good. The population frequencies of species and the estimation of population parame- ters. Biometrika, 40(3-4)237-264, 1953.
[34] Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially-prinnn histograms through consistency. arXiv preprint arXiv:0904.09. 0942, 2009.
[35] Dan Hendrycks, Collin Burns, Steven Basart, Andrew Critch, Jerry Li, Dawn Song, and Jacob Steinhardt. Aligning ai with shared human values. Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[36] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[37] Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muchling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolv- ing individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLoS genetics, 4(8):e Te0x=e000011 1000167, 2008.
[38] Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. In International Conference on Machine Learning, pages 2436-24464 2444. PMLR, 2016.
[39] Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. On learning distributions from their samples. In Conference on Learning Theory, pages 1066-1 100. PMLR,, 2015.
12

---

[40] Slava Katz. Estimation of probabilities from sparse data for the language model component of speech recognizer. IEEE transactions on acoustics, speech, and signal processing, 35(3): 400-401, 1987.
[41] Bryan Klimt and Yiming Yang. The enron corpus: A new dataset for email classification research. In Jean-François Boulicaut, Floriana Esposito, Fosca Giannotti, and Dino Pedreschi, editors, Machine Learning: ECML 2004. pages 217-226, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978-3-540-30115-4
[42] Raphail Krichevsky and Victor Trofimov. The performance of universal encoding. IEEE Transactions on Information Theory, 2792):199-207, 1981.
[43] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. arXiv preprint 1/Xi::2100005699 2021.
[44] Yuhan Liu, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: user vs item-level privacy, Advances Neural Information Processing Systems, 33:20965-20977 2020.
[45] Nils Lukas, Ahmed Salem, Robert Sim, Shruti Tople, Lukas Wutschitz, and Santiago Zanella- Béguelin. Analyzing leakage of personally identifiable information in language models. In 2023 IEFE Symposium on Security and Privacy (SP), pages 346-363. IEEE, 2023.
[46] David A McAllester and Robert E Schapire. On the convergence rate of good-turing estimators. In COLT, pages 1-6, 2000.
[47] Audra McMillan, Adam Smith, and Jon Ullman. Instance-optimal differentially private estima- tion. arXiv preprini arXiv:2210. 15819, 2022.
[48] Michael Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet mathematics, (2)):226-55) 2004.
[49] Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why is good-turing good. Advances in Neural Information Processing Systems, 28, 2015.
[50] Alon Orlitsky, Narayana Santhanam, and Junan Zhang. Always good turing: Asymptotically optimal probability estimation. Science, 302(5644):427 431-13,,, 2003.
[51] Liam Paninski. Estimation of entropy and mutual information. Neural computation, 15(6): 1191-1253, 2003.
[52] Liam Paninski. Variational minimax estimation of discrete distributions under kl loss. Advances in Neural Information Processing Systems, 17, 2004.
[53] Steven T Piantadosi. Zipf's word frequency law in natural language: A critical review and future directions. Psychonomic bulletin & review, 21:1112-1113 2014.
[54] David MW Powers. Applications and explanations of zipf's 's law. In New methods in language processing and computational natural language learning. 1998.
[55] Sriram Sankararaman, Guillaume Obozinski, Michael I Jordan, and Eran Halperin. Genomic privacy and limits of individual detection a pool. Nature genetics, 41(9):965-966 2009.
[56] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEF, 2017.
[57] Michael Short. Improved inequalities for the poisson and binomial distribution and upper tail quantile functions. International Scholarly Research Notices, 2013, 2013.
[58] Congzheng Song, Thomas Ristenpart, and Vitaly Shmatikov. Machine learning models that remember too much. In Proceedings of the 2017 ACM SIGSAC Conference on computer and communicattons security, pages 587-601, 2017.
13

---

[59] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing, 46(1):429-455, 2017.
[60] Michael Voolse, Martin Potthast, Shahbaz Syed, and Benno Stein. TL,DR: Mining Reddit to learn automatic summarization. In Proceedings of the Workshop on New Frontiers in Summa- rization, pages 59 63, Copenhagen, Denmark, September 2017. Association for Computational
Linguistics. doi: W17-4508
URL https:: /www aclweb. org/ anthology/
[61] Tianhao Wang. Jeremiah Blocki, Ninghui Li, and Somesh Jha. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17), pages 729-745, 2017.
[62] Qun Xie and Andrew R Barron. Minimax redundancy for the class of memoryless sources. IEEE Transactions on Information Theory, 43(2):646-655 667, 1997.
[63] Jia Xu, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, Ge Yu, and Marianne Winslett. Differentially private histogram publication. The VLDB journal, 22:797-822. 2013.
[64] Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Transactions on Information Theory, 64(8):5662-561) 2018.
[65] Bin Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam: research papers in probability and statistics, pages 423 435. Springer, 1997.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims in the abstract are elaborated in the introduction, and all claims in the introduction are followed by references their discussed sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the conclusion Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
14

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
See the statements in Section and 3.1 and proofs in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Algorithm pseudocodes are given in Algorithm [add] and hyperparameters are given in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same datasct, provide access to the model. In general. releasing code and data is often
15

---

one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The paper does not provide access to the code, but only uses opensource
datasets in Section and provides algorithm pseudocode in Algorithm I and
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
public//uiides/odeSSttee was.bmmmsssioooocccii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
wttpl/icigggi/eeeeeeeeeeeeeeeeee httpa////ggiiee//eeeubbbiiibii www.himiisiiooooooooii.o for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Hyperparameters are given in Section Guidelines:
16

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All our experiments (Figure and Appendix G.4 report 1-sigma error bars across five runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p::///euris...o..o httpa//ppp...p.pbi///hhccaaaaaaa
Answer: [Yes]
17

---

Justification:
We reviewed the NeurIPS Code of Ethics and ensured it is respected.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not see potential such risks of this paper, as we only used synthetic and open-source datasets validation.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: We do not foresee any no potential ethical harms, as the paper only uses synthetic and open-source datasets for validation.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
18

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All used datasets are referenced in Section and have licenses that allow research use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. wwt.coo///aaaaae camadataeete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
19

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs are only used for checking grammar and formatting.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.M for what should or should not be described.
20

---

Contents
Introduction
1.1
Technical Contributions
1.2
Other Related Works
2
Tighter Instance-Optimality for Non-DP Estimation
An Instance-Optimal "Sampling Twice" Estimator
2.2
Comparison Prior Instance- Results
3
DP Instance-Optimality
3.1
Privatized Instance-Optimal "Sampling Twice" Estimator
4
Experiments
Conclusion
10
Tools for Lower Bounds
22
Useful Lemmas for Poisson and Laplace Random Variables
26
Deferred Minimax Optimality Results
30
Recap: Non-DP Minimax Results
30
C.1.1 Recap: Non-DP Minimax KI. Error Lower Bound
30
................................
C.1.2 Recap: Non-DP Minimax KL Error Upper Bound
................................
31
Our DP Minimax Results
33
C.2.1 DP Minimax Lower Bound
33
C.2.2 DP Minimax Upper Bound
34
D Deferred Proofs for Non- DP Per- Instance Lower Bound Theorem 2.1
35
D.I Useful Lemmas
36
D.2 Non-DP Per-Instance Lower Bound under N
(p)
36
D.3 Non-DP Per-Instance Lower Bound under N Natat (p)
39
E
Deferred Proofs for Non-DP Per-Instance Upper Bounds
41
Non-DP Ins-anst Upper Bound (Sampling Twice Algorithm)
E.2 Proof for Matching Lower and Upper Bound
42
Deferred Proofs for DP Per-Instance Lower Bound Theorem 3.1
43
F1 Lower Bound: neighhorhood
43
F2 DP Lower Bound: neighborhood
44
Deferred Proofs for DP Per-Instance Upper Bounds
47
G.I Upper Bound: DP Sampling Twice Algorithm
47
21

---

G.2
Proof for Matching Lower and Upper Bound
53
G.3
Discussions the Neighborhood Size
54
Additional Experiments on More Datasets
56
G.5
Instance Optimality of Gaussian Variant of Our Algorithm
56
Tools for Lower Bounds
Below first define decomposable statistical distance.
Definition A.1 (Decomposable Statistical Distance). Let E N and let dist A(d) A(d) - R be non-negen non-negative function such that dist(p. g) 0 if and only if p = 9. We say dist is decomposable, for any disjoint sets of symbols B,, B, S [d]. and for any distributions p. E Ad). the case that
dist(p. 9) 2
Σ 1=1
Σ
Pj
dist(pli.
(8)
jEB
where for any distribution E (d), and any i = 1,
ki we have denoted
if E for i = 1.. k
Eee, Ps
pl
otherwise
Lemma A.2 (KL divergence is decomposable). KL divergence is decomposable, that is, for any disjoint sets of symbols B,,..., Be and any p, E (d), it is the case that
KL(p.9) 2
Σ JEB;
Pj
KL (p)..gls)
(9)
1=1
Proof. Let p.q A(d). Denote B = =(d] \ ( B.), then by definition compute
KL(p.9) = Σ
ln
Pi
Σ
Py In
Pj
(10)
i=1 jEB;
JEB
Σ EjEB, Pj ΣjEB Fj
Σ jEB;
Pi
KL (ple,
Σ Pj
In
(11)
i=1
jEB;
Σ jeB: Pj EjEB Pj
Σ Pj JEB
KL (pl
Σ Pj JEB
In
(12)
Σ Pj 1=1 jEB,
KL (p)..
(13)
where the last inequality is by non-negativity of KI. divergence KL (pps:,9/s)) and E EjEB, P3) In LscB EjsB, 9) (Eje p.) In Ei
Theorem A.3 (Generalized Assouad's method for decomposable statistical distance). Let dist be a decomposable statistic distance as per Definition A.7 Let By.... BB S [d] be l disjoint sets of symbols. For each i 1.... k, let P, be set of distributions supported B.. For fixed wi. wikk 2 0 such that Σ Di=1 Wi L, let be the following composed packing set:
p Σ
wap p¹ EPP
(14)
1=1
the following two conditions hold:
22

---

1. There exists non-negative function f such that For any E A(d),
Σ
1 1))
2 2'
(15)
P.
PEP.
2. For each i E [k), there exists Ti 0 and p' P, such that for any fixed p E Pj.. + holds that
MAEN min P'EP, dS, wip' Ljji Wyp') dS wap'
dS(n, ΣØ= Wyp')
Ewupp) (16)
j#1
where we have denoted S(n,p) as the distribution of histogram representation of dataset sampled from distribution p E A(d) with target sample size n.
Then for any fixed E > 0, 5E
min (e,
max E PEP Sm.(()p)
[dist(p. A(x)) 2 w To f(P.)
(17)
Proof. We will reduce the estimation problem over all symbols to the estimation problem over each bucket B. For any distribution p Add) denote its conditional distribution on B,
j E B;
p/c
Jes
for i 1,... kk
(18)
otherwise
And for any (e, 6)-D estimator A given dataset supported on B, similarly denote
A(r), A(x)1: Exe, A(x)y
if B; for 1,..,,
(19)
otherwise
Then by definition, for any fixed i 1,.... ,,, we have
f(P,)
E
A(x))))
E S(a.))..
(20)
S (n.P).A
PP]
PEP
PEP
S(P:)
Σ
Σ
E
EA 1 dist(pp' ((a1))2/(PP)]
(21)
11 (Pyl piEP ptPp
z~ (n. mip!
f(Ps)
dS(n, Σ Wyp')
E p'EP, 2~8( Sn.wnn + E wip!)
Σ
min p'EP:
(T)
Σ
EA [laistep AA00))222)))
11 (Pyl
dS(n, (n, WiF² jzz wipp)
P'EP.
(22)
f(P.)
dS(n, E}=ı Wpp')
E 2n Eigr wip!)
min PeEP. ds(n, wiy Ejqe Wpp')
(z)
(23)
2
>Ti .(P:) 2
(24)
where 20 is by Markov inequality, is by definition and by moving the sum of p² P, inside
w,p") expectation (as ž and minp'eP; dS(n, woppt Exer ";pi) (z) are independent of the choice of p²) 23
dS(n. E
is by the packing assumption (23). and (44 is by the dataset distance assumption (16).
We now use (23) prove lower bound on the expected KL error for estimating the whole distribution over all possible distributions in the packing set P. By Lemma
A.2 it follows that
1
E S(n.))
(tst(p,A(x)))
W
E S.n.))
(ist(pp).AAx))
(25)
P
P
pEp 1=1
Σ
W/ Ti f(P))
(26)
2
i=1
23

---

where the last inequality 26 is by 23 This suffice to prove 17 by observing that average is
smaller than maximum.
Theorem A.4 (Generalized DP Assouad's method for decomposable statistical distance). Let dist be a decomposable statistic distance as per Defimition A Let Bi.... _Bx C [d] be disjoint
sets of symbols. For each = 1,... ,k, let P. be set of distributions supported on B For fixed w1,"" Wik 2 0 such that Σ k
Li=1" W4 1, let P be the following composed packing set:
q 99 3 wap' p E
(27)
For any (d), denote S(n, p) as the distribution of histogram representation of dataset sampled from p with target sample size n. If the following two conditions hold:
1. There exists a non-negative function f such that
For any q E (d).
1dis((p-)22((P))
2 2'
(28)
PEP:
2. For each i E [kb] there exists T3 2 0 and p E Ps, such that for any fixed p E p..j =
1.... k. it holds that
(m.a) ||| =111] S T3
(29)
for a coupling (x, 3) between distributions S(n, Σj=1 w ) and S(n, way + Eees Wyp').
Then for any fixed e 0, 8 S
(1 46 -
max E (s, DP pEp S-n((n))
min
(pi A(x))
S(P:)
(30)
10
Proof. We will reduce the estimation problem over all d symbols to the estimation problem over each bucket B; For any distribution p E A(d), we denote pl: as its conditional distribution on B, as defined in (8]. And for any (e, 8DP estimator A given dataset x supported on B, we denote A(z)];
as the conditional estimate B, defined in (19). Then by definition, for any fixed i = 1,... k.
we have
S(P.) PP]
E (m.p).
(dist(pl; A(x))) 2
E S(
(31)
P
PEP
PEP
f(Pi)
Σ
Σ
E
Pr
dist(p' A(x))a) f(P)]]
(32)
1= (Pyl piEP, fif pigp.
k
2 2~ (n. wip!)
S(P.)
> I1 [Pyl
Σ
Σ
- 2111
Pr ( 2 [(P:)] - 5. | - =1b
(z,7)
piEPijti p'EP,
(33)
S(P.) Σ
Σ
- Pr Pr[dist(p' A(F))) [(P.) C 1| >
Pr
11 [Pyl pEPiiti ptPp
(z,z)
(34)
f(P.)
E
Σ
Pr [dist(p' ((())) f(P.] A
- -8 -.. P
11 [Pyl
plEPiiiii
PPEP,
Σ
Pr ||| æ/|1 2111>11.11
(35)
(2,2)
p
e C
- C - ) ((P.)
(36)
1
48 1g:75 ((P,)
(37)
10
24

---

where (31 is by Markov inequality. (33) is by group privacy and holds for arbitrary constant C' > 0,
(35) by moving the sum of p' E P; inside expectation (as T is independent of the choice of p'
given coupling (z,ā) between distributions S(n, E wyp') and S(n, wap is by the packing assumption
i Wpp' )) (36)
28 and v & and the dataset distance assumption and 37 is by
choosing C
46-ri"
We now use (37 to prove a lower bound on the expected error for estimating the whole distribution
over possible distributions in the packing set P. By Lemma A.2
it follows that
E
[ist(pp,
wi
E I S(
A(z)()):.(z))a))
(38)
P
x~ P
P
PEP
pEp
1
Wi
48 Ti
((P.)
(39)
10
where the last inequality 39 is by 37 This suffice to prove
330
by observing that average is
smaller than maximum.
Finally, we provide two useful constructions of packing set that satisfy (5) and 28
Lemma A.5 (Packing over Two Symbols). Let B = {i1.22) be a set of two symbols. Given < A < a < let P {p.p-} be packing set containing the following two distributions on B.
j j ==1 j2
a 1-a+
j= j= j2
p(i)
1 -
and p])
j E [d] (i1.12)
0
j E [d] \ Kinn22)
If F <
2. then
(1 (1 (IK((p))222 + 1 2
1
1
For any q A(d)
kL(p= 41 A2
2
(40)
2
Proof. We will prove this claim by separating the analysis for different q.
1. If q3 Sa .. by definition, we compute that
a
1 1-a
KL 9) =a
+ (1 - a)
1 (a kn
2a
(1 a) Qi
(41)
1
A
(42)
8
a
where 44 is by In(1 + x) < x
2
for x S 0, and by In(1 + S x for x 2 0, and the
last inequality is by li + 0i <' and by using the condition that (j S a 2
2. If qj >a -. by definition, we compute that
A
1-a+1
KL(p =(a - An
+ (1 a An
9i
4/2
(a A qi )²
2a A
Ui
+ (1
A)
-ia
(43)
a
A
(44)
where (43 is by In + x) < x
a² for 0 < x < 2. and by In + x) / x for x 2 0, and
4
the last inequality is by 4n g/2 and by using the condition that gj /
A
25

---

Lemma A.6 (Dirac Distribution Packing over x. Symbols). Let B = -...... 3x) ) be a set of k. 2 symbols. Let P {p.p-) be packing set containing the following dirac distributions on B.
j ji p'(i) = {
jE ld] (11 for ,,.
Then holds that
1
For any q E A(d)
2 KLW a))22(1+
(45)
Proof. We prove by contradiction, suppose that there exists E A(d), such that
Σ
KLU (26011)))((144)) < A
(46)
1=1
Then by definition of KL divergence, we have
1aa S 144
(47)
Observe that Ex= 1 9, $ 114
is integer, 47 implies that
0
K =
(48)
1+
2x
K 2 3
1=1
Thus
(49)
+
1+
1
S 14g
4
1=1
1=1
(50)
3
where (50) is by 447 This contradicts q A(d).
B Useful Lemmas for Poisson and Laplace Random Variables
Lemma B.1 (Expectation of inverse Poisson random variable). Let p E [0, 1).m E N, and let
Poi(mp). Then
(51)
vm&p
Proof.
By definition, we compute that
(mp))
8
(mp)²
1
E
mp
mp
(1 e mp S
F
1+1
mp
t!
mp
mp
(52)
Lemma B.2 (Tail bound for Sum of Poisson and Laplace Random Variables). For any a, b, Suppose that x ~ Poi(a), ~ Lap (0, b), then we have that
Pr|z + +
4 4e( (-$+ 5
moxto.IT
and
Pr
+
cl
-
max
(53)
3
3
26

---

Proof. We first compute the moment generating function of x + 2, i.e., the convolution of Poisson random variable and Laplace noise. For any = 5. by definition, we have that
M=+:(0) (0) =E e (((++))
E [c Ce Laplo.))) ae [
1
(54)
6282
Then, by using Markov inequality, for 0 [0, 1)), we have
Pr(a S c) = Pr 0(x+)) Mn Ma+z(-0)
cale -o(e-"-1)+a0
(55)
6-00
112622
By choosing 0 m then by observing =0 - 1 - 50 for 2
2' we prove
that
4 el ++4) e( max
Pr(a s -
(56)
Similarly, prove bound for the upper tail by Markov inequality.
Pr[z ž c] - Pr (Clxxta) 2 c00) Ma+a(0)
11-0cc ea(e" -1)--
= mux(b.
(57)
e0c
0282
3
where the last incquality is by choosing 0 2 [b,17
Lemma B.3 (Bias of Truncated Laplace Random Variable). Let X 2 0, n E N. Let Poi(A) and let Z ~ Lap(O, b). Then the noisy estimator given by ā = max fx + Z, c} satisfies
E i
Aj bbcc
(58)
Proof. We first prove the left inequality in Lemma B.3
By definition,
E [ A| = R [ - x] = E Z 1222 + (c - x)
1 1xt2<d = E| + [(c x - Z) 1,t2ed 2
We then prove the right inequality in Lemma B.3
By 2 max(2 + c), we compute that
E
X]
E [ x| < E mmxx (c. [Z]]] - [[] + b+c
(59)
Lemma B.4 (Conditional Bias under Thresholding). Let X be a random variable over R. Then for any
E X 2 d) E
and E X < <d s B[X]
(60)
Proof. We first prove the first inequality in Lemma B.4 If c < [[X], then by definition,
If 2 [[X] then E[X 2 cl
c
[[
E [X- - E E(X]) 1 > [( XX - E [ = 0
(61)
where the inequality is by x - E[ S c E[ < 0 for x S c. The proof for the second inequality in Lemma Bs similar.
O
Corollary B.5 (Conditional Bias of Truncated Sum of Poisson and Laplace Random Variable). Let
6 > 0. e, R (-00 to0}. Let x Poi(A) and let Z Lap(O, b). Then the noisy estimator given by & = max {x + 2, satisfies
E f A/x +
& sb+c
(62)
and
- 2 - 220
(63)
27

---

Proof. We first prove 662
By Lemma
B. we have that
B
A/ 7 d]
E
i
b
where the last inequality is by Lemma B.3 We then prove
663p p.
By Lemma B.4 we have that
- A|r + Z 2 E
220 0
where the last inequality is by Lemma B.3
Lemma B.6. Let > 0 and e E I. and let Z ~ (ap(O, b). Then
E 7 Z v max (c, 0) +
(64)
Proof. We separate our discussion for c 2 0 and < 0.
1. If O, have that
226
Pr|Z = 2|Z2d=
(65)
2<c
Thus
+000
E 1ZZZ 2 c)
2
be
da
< 0 (c b)
(66)
2. If e < O, we have that
Pr[Z 2 Z 2 c)
<
26
e
b
11
(67)
b
2
Thus
+000
1
1:1
+00
E
E 22
b
dz
<
b
8
d2
< (b)
(68)
5c
Lemma B.7. Let >> 0, b 0 and e E R. Let X
Poi(X) and Z ~ Lap(0, b) be independent
random variables. Then
E Z + 222 c
0})
(69)
Proof. By definition,
B + Z|X - -22 = Σ
Pr[X = f] (L+ 2 c)))
(70)
1=0
<B|X] + Σ
Pr[X .0 Omaxfe 1,00 + +
(71)
< + 0 maxfc, 0})
(72)
where 7I is by applying Lemma B.6
Lemma B.8 (KL Divergence between Poisson Distributions [57 Theorem 2]). Let m, k > 0 be fixed. Then the KL divergence between two Poisson distributions Poi(m) and Poi(k) satisfies
KL (Poi (m), Poi (k)) = m * 4 ln
(73)
28

---

Lemma B.9 (Total Variation Distance between Poisson Distributions). Ler A1, 22 > 0 be fixed. If A S X2.
Then
22)2
TV (P)) Poi (A2)) S
(74)
A1
Proof. By Pinsker's inequality, we have
KL (Poi (A2), Poi (A1))
TV (Poi (A1), Poi (A2)) S/
(75)
2
1/
x1 +
A1
In
Az
(76)
2
1 (A1
X2)
(77)
2
A1
where (6) is by Lemma B.8. and the last inequality is by In(1 + x) 2 - for 20.
Lemma B.10. Let p m E N, CI, C2 R u (+oo,- -00]. b 0. and max(b,1) 1}. Let I ~ Poi(mp) and les Z ~ Lap (0,b) be independent of x. Then the noisy estimator given by maxfa + c. satisfies
E 1asot25o> (pin
mp T
3 mp
]
b² + c
(78)
m m maxte, mp}
m
Proof. We separate the discussions for p S and p > e
m
If S an by In(1 t) S for any > -1, 1, we have that
mp
+ T mp
1 10 155
pll
(79)
(mp 5
mp
T
T
m7p
<E
1a S55z
(80)
(mp- - 2)2
<E
(81)
2mmp x1)² + 2(x -
<E
(82)
mc
22p
4b2 + 2c
6 + c²
<E
0
+
(83)
mc
mc
m
mc
where the 81 is by ã 2 and by (mp 2)2
82
is by
(a + 6)2 2a² 262 and
the last incquality by E[(mp- 2²² = mp, E (x
< 2 + + 26 c² and
If -: Observe that by In(y)
2 1 (y
1)2 for any y 2 1. have that
mp
$ mp
E
1asx+25a
pln
+
1 72 mmp
(84)
m
t mp
(5 mp)
5 mp
<E
105x+t50
1 12+2 1mp
(85)
mp
(mp)²
m
(5 (pmpp)
=E
1 Sa140225e
1 1 mp
(86)
m²p
2E
2 + 6 + (x - m
0 (
1/2 + c
(87)
m² p
m2p
29

---

8 and by 7²2 + c² + (x mp E [xx - mp)
where the first inequality in
is by (a + b)² - 2(a² + b²) and (Ø -z) < - + c².
0: the last equality in (87) is by T. [ = 전 and
mp.
On the other hand, by Lemma B.2 we have that Pr(z + Z < mpl Thus we have that
S <0
max [.J
E
1a Sot
pln
mp
+ I
1 I1+ S
In my
+ p
(88)
m
max
[0.3]
mmx (b. 1)
x xl((1) +
max max (0, 1,
max
(b, 1}
In
m
ex/3
mar
n
e
max
(89)
<0 max (b, 112 00
(90)
m² p
m²
=l((x) where the inequality in (90) is by c=/6 < (2) and , -0 for 2 0, and by
e max/b, 1) This suffice to prove the bound in the statement.
C Deferred Minimax Optimality Results
C.1 Recap: Non-DP Minimax Results
The minimax rate for non-DP distribution estimation in KL divergence error is well-studied 10
51
52
summarized below in Table 2
Estimator/Bound
Expected KI. Error
Reference
Upper Bound
In +
10
Theorem 8)
Addd-Constant Estimator)
Recap: Theorem
Lower Bound
Ω [n
Recap: Theorem
Table 2: Non-DP Minimax Rates for Distribution Estimation in KL. Divergences
For completeness, below we offer simple proofs for the minimax upper and lower bounds.
C.1.1 Recap: Non-DP Minimax KL Error Lower Bound
The minimax lower bound for distribution estimation in KL divergence error is well-understood to be 22(1 + 4). e.g., see the variational lower bounds in [52]. For completeness, below we provide an alternative proof via the tools in this paper, i.e., the generalized DP Assouad's method for decomposable statistical distance (in our case KL divergence) in Lemma A.2
Theorem C.1 (Lower Bound for Non-DP Estimation). Let be fixed. Then for any estimator A. we have that
Ω 11 (1)) d
d $ 2n
1 (1+))
d)
max P M.-
KT(EIAA(=))]
St Inn
(91)
2n
Proof sketch The idea is to design to be uniform over a random support of symbols with small probability mass, and then reduce the problem to the difficulty of inferring the support given limited samples.
Proof.
Dense Case d - 1 2n: Assume d mod 2 for convenience. We decompose
d symbols into d-1 buckets B, {2i 1, 1, for 1.... d We then construct the 2
30

---

packing as follows. For i = 1,-. d-1
d-1
For i = 1,
P. = 1,2s-1,02) 62;)
(92)
2
where d; means point distribution on symbol i. We then construct a set of distributions.
(1
d-1)
d
da p' E E for any = 1,... d 1 /
p
p
(93)
72
2n
Then by Lemma
A.2 for any algorithm A we have that
A(x))
2
[KT[p]s A(x)))] (94)
M-lu(((.p))
n IPI
s..uul((.p))
pep
i= pEp
E Mull())))))
A(z))) T2--1 x2z =2 =0]
(95)
P
im
pEP
(d ln
1n(2)
(96)
71C
2ne
(97)
Thus for any A, there must exist one p E P such that
I s--Mult(n.pp)))
(K((,A(x))) 2 2( -1)
[=11 2 and to for convenience. We decompose d symbols into & buckets B; = {K " construct the packing follows.
Sparse Case: d - > 2n: Denote
K + 1, K. if for i = 1, ... k. We then
For i = ,,,,, k P. = (5 )x.)
(98)
where 6; means point distribution symbol i. We then construct set of distributions.
P p
p': P. for any i= L. k
(99)
Then by Lemma A.2 for any algorithm A we have that
(L(p,A(x)))
[(L(pl:A(x)lb)) (100)
P
Mul((n)pp))
PEP Mull(pp.p)
pEp
b
E M)lut(nppp)
((<p)::A(<)bb)) EXS- = 2xx = 0]
=xa=
(101)
ne P
pEp
klnk
d -
In(x)
In
(102)
ne
n
(103)
Thus for any A, there must exist one p E P such that
[KL A(x))
QIn d-1
C.1.2 Recap: Non-DP Minimax KL Error Upper Bound
The minimax upper bound for distribution estimation is well-studied, and various works 110 51 52 have shown that simple add-constant estimators could achieve the optimal (In (1 + :)) minimax KL error. Below offer simple proof for completeness.
31

---

Theorem C.2 (Non-DP Distribution Estimation KL Upper Bound), There exists estimator such that for any p E A(d), given n empirical data samples Mult(n, p), it satisfies that
d
E
s In 1
(104)
z>-Muli(n.p))
n2
Proof. We use that the following simple add-constant estimator.
1 24 +++1 1
A(x);
(105)
+
n
Then by definition
E
(L(P)LA(
d
Pi
E a (ub()n)
In
Ij + ] In 1+ (1+=] mn
np:
(106)
Muli(
d
z~Muh((n.p) Lo; + 1 1 + In |+ +
Pi In
npp:
(107)
d
rip;
In
+
+
(108)
E Jo-Mull(
[3
i=1
d
In 1
(109)
T2
where (107) is by concavity of the function In(x), and (08 is by Lemma C.3
Lemma C.3. Let $1.-.. ,K be K independent Bernoulli random variables with parameter Pl. PK. Let e 2 be a positive constant. Then we have that
E
(110)
K
K
k=
8k
=k=1 Pk:
Proof. Conditioned on any fixed value for 83, ... , ,8K, denote e' = c Ekeg 8% we have that
PiP2
P1 - p2) (1 - p1)p2
pi (1 p2)
E
$3
8K
(111)
c
k=
Sk
22
C' c'+1
c'
1
2
1
1 (
+
1
1
PP12
2
c'+1
+
(pi + p2)
c'+1 c
+
(112)
+
P2
1
2
+
1
+ (p1 22)
c' c++1 - -
(113)
2
22
c++
where the last inequality is by
1
2
+ e
1
> 0 for d'
> 0. By similar argument, we have that
d42
d+1
1
E
< E
E 1+8
(114)
c+
Ek=1
K
Sk.
c+
where s ~ Bin(K,p) p) where p = K
Σ
x=
Ps.
Then by simple algebraic tricks, we have that
K
Ks- 1
1 (1
(115)
K k==
j+1 [ (K+1)
8k
1
Σ
p² - kp)
(116)
(K + 1)p
i+1
3=
1
(117)
Kp
Σk -k Pk
32

---

Method
KL Error Bound
Conditions
Reference
Any (s. (E.
Ω [In[1 + min
d 2 4, S
Theorem C.4
Add-constant ((e, 8D- In
0, 8
Theorem C.5
nimin [c.1)
(Laplace Mechanism)
Table 3: DP Minimax Kl. error bounds
C.2 Our DP Minimax Results
We first summarize our derived DP minimax rates in Table 3 observe that simple variants of Laplace mechanism is minimax optimal.
We comment that our KL minimax lower bound is stronger than naive conversions of prior TV distance lower bounds to KL lower bounds applying Pinsker inequality to the prior Ω (#) TV
lower bounds
19 only gives KL lower bound of Ω (min
d²a [=
}))). which is significantly (=
weaker than our bound Ω (In (1 + ) in Table especially for large
Below we present the proofs for the minimax lower bounds and upper bounds.
C.2.1 DP Minimax Lower Bound
Theorem CA4 (Minimax Lower Bound for DPP estimation). Let N, 2 and 8 E [0, be fixed. If d 2 4, 5 <e, e, then
1+ d
max (d)(d) p>Pon(p.))
E
[L(p.
2 Ω
In
(118)
EN
Proof. Let k E N be defined as follows.
2
To0ma S 2
1 [80e
160nE < 2
2 and 80ns 2 1 and k
2 and 80ng 2 1. (119)
160nc
160ms
160nc
[
and 80ng
and 80ns
160ma
160mg
Thus by > 2, have
d
k
2 2 and K
and
K k
2
and
(120)
160me
2
For 1, ... we construct a packing set of distributions supported on symbols (1: 1 K 1.... J as follows.
For = 1,....k P. = 10 8
(121)
We construct the following set of distributions that lie in the additive neighborhood of
1
D
+
q
and q¹ E Pe for any i = 1, k
160ne
160ns
==1
(122)
where
=00
(0
j == 1, ... K k
(123)
d= j = k kt + 1....
One can verify that the distributions in P are well-defined (i.e., normalized). Now by applying Lemma to P, for each i 1,... k. we prove that for any g' e A(d), it holds that
1KI(a0)25(P) 2 where f(P:) In (1+ x 4
1
(124)
P OEP.
33

---

Thus the first condition of Theorem A.4 holds.
Below we analyze the second
condition of Theorem A.4 For each
[k] and fixed qd E Pj.j
1. and fixed q¹ P.. Let
Poi n, (1 160ne
wy q' and
y Poi n, 160ns
w wy q') be independent Poisson random vari-
jff
ables.
Then we could construct the following coupling (I, between distributions
Poi
n1, (1 160ne
B
qf
+
Σ W/ qd and Poi (1 16ūne) d - q + Σ wj q¹)
yl
= n k + 1, ,, x.
31
(125)
21
le [d] \ fn-i- i 1 , 1
By definition, we compute that
E ||
E | - wlll S
[ + 3i]
E
80c = T
(126)
[=x---+1
[=di-R41
where the inequality is by triangle inequality for & distance. By applying Theorem A.4 under our proved conditions (124) and (126), we finally prove that
max E [KL A A(x))
Wi
10 4E 45. f(P.)
In
4
K)
(127)
QEP
160ns 20
In (1 + 5)
160ns <
160-20ne
[80ne] In (1 +
160
160m=
and 80ne 2 and 80ns
(128)
In (1 1
160-20ne
160nr
In (1 }
< 2
160-20ne-8
160ms
[80ns] In 8-160-nE
d
2 and 80ne 2 1
(129)
160ng
160-20ne In (1 d
160nz 2 and 80ns < 1
d
20 In 1
(130)
ne
where (28 is by using the definitions of k and k in (119). 119 is by [x] 2 for any x 2 1. 130
by In(1 + Ar) S A-IIn [1++0) x) S x for s and for X > 1 and x > 0.
O, and by A An + x>) 2 In(1 +
C.2.2 DP Minimax Upper Bound
Theorem C.5 (Upper Bound Pure DP). There exists an (s, D)-P estimator A such that for any fixed N,
KL(PlIA())) so (In (1(1 n min
d
E po.Poi(
(131)
Proof. This can be achieved by a simple estimator that combines an add-constant estimator and Laplace mechanism as follows.
1 Tj N n
A(x):
where E, max Z3 24. min 1,
(132)
where 2 ~ Lap (0. 1) and = Σ, v, is the normalization constant. The (c, DD- guarantee follows by observing that the é éi-seniitvvity of vector release (zi,... ,aa is one, and by applying the DP guarantee for Laplace Mechanism in (26 Theorem 1]. Below we focus on bounding the KL
34

---

Neighborhood N
lower(p, N) 2
Conditions
Reference
Nge
136
?
In(1 In(1id Pamall (L') In (1+
demulill2) ippemiie!!)))
L' [d].
Theorem D.3
d2 2, n 24 d
Na (p)
137
a Σ min {pi, b;}
Theorem D.4
Table 4; Non-DP per-instance lower bounds, where Pamaii(L'))
E
pi and dsmait(L')
E
1.
SE P:
emror. By concavity of In(() on > O, we have
(KL(O|A(())]
Σ
Pe In
Pi-
+ ln
1
E T
pi]
pp)
71
Σ
Ps In
Pi P
42 Pi
In
1
Σ
E
[ Pi
72
72
ippe mlmn
Eppe mmin
(133)
E
HP13 [L.c]
iP mumu [1.c]
00
+ In 1+0
(134)
m.ii
mmin(1,,)
<0 1 mmin(,,e)
(135)
where 133 is by In
Pi-n < 0 for pi < mmmm by E[ xx] 2 0 for any i (by Lemma B.3
and by In(1 1 + r + y) S x + In 3) for any 2, y > 0: 134 is by applying Lemma B.10 under
setting n, C1 -00, C2 +00,
and min (1.c) for pt min(1
1 and by applying
Lemma B.3 for p: b>0 0.
and 135 is by a a 1nIn b) < In + 2a + 26) for 0 < < and
(..))
D Deferred Proofs for Non-DP Per-Instance Lower Bound Theorem 2.1
For ease of presentation and understanding, we break up the neighborhood N (p) into two sub- neighborhoods: one No S (p) with the same small perturbation for every symbol, and the other Nstat C (p) (based statistical variance) with larger perturbations for large symbols, defined as follows.
Ns4 (p)
q: 1q: psl for any E [d] and Σ qi
S max
Σ Pi
(136)
n
n
i:p:
S
E
1
Nstae()) = q: 9::9: - -pll < min
Ps.
Pi
for any i E [d]
9
19: Psl -
(137)
We then prove per-instance lower bounds under the sub-neighborhoods Nu (p) and Notat (p) respectively, By definition 2 their average a lower bound for the per-instance lower bound under N (p), i.e., lower(p, n,, N+) -looer(pp n,, No ) ------ooorrpp n, Nstat). (This is because one can construct distribution over hard instances, choosing the hard instance(s) in Ng (p) and Natat (p) with 1 /2 probability respectively.) Our per-instance lower bounds under the two sub-neighborhood summarized in Table
35

---

D.1 Useful Lemmas
Lemma D.1 (Coupling Lemma
[ Lemma 3.6]). Let random variables Zι, Zn have distributions
V2 Then
(V 12) S Pr [Z # Zz] Conversely, given probability distributions v1, U2, there exists (71, 7x2) such that
(138)
TV (U1, v2) = Pr 11 + Zz
(139)
where Z1, Z2 have distributions V1, 12 respectively.
Lemma D.2 (Total Variation Inequality between Product Mcasures). Let μ1, P2 be probability distributions over Q and let pl μu be probability distributions over Y' Denote μn X pr as the product measure of μ1 and μ over S2 x St,, and similarly denote P2 x μl as the product measure of l2 and 112 over Q x S. Then
TV(n P1, x 14) S TV( 12) + TVppI-pb)
(140)
Proof. By the coupling lemma Lemma D.1 there exists (Z Zi) such that Z1 ~ μt. Z ~ pl
and TV Pr[Z] * 7 Similarly, there exists (Z2, Z2) such that Zz μ2, Z 12 and
TV = Pr[Z2 * Z Let Z (Z1, 2 and Z' = (Z2, Z2). Then Z ~ in x μy and Z l12 x u12
By again using the coupling lemma Lemma D.I] we prove that
TV(n x p1.22 P2 x )و) < Pr|z + z'] < Pr[Zi + z + PriZz + 23] = TV(nI, - TV 12) (141)
where the second inequality is by union bound.
D.2 Non-DP Per-Instance Lower Bound under Ne. (p)
We now prove the per-instance lower bound Table Jnder additive neighborhood N& (p) for low-probability symbols.
Theorem D.3. Let p E (dd be fixed. For >> O, let Ng: (p) be the below additive local neighbor-
hood of p as defined in 136
55 (p) = q la - 10plpl
S t and Σ 41 S max
Σ Ps
(142)
n
n
E
Epp h
1 1, d. 2 and 2 4, then for any L' C [d].
KL(g.A(2)) 2 Ω In(1 + demall (L'))
dematt (L')
+ Pemati In (1+
max VEN L (p) p--Poi(
7ppsmall (L)
(143)
where Pemail (L')
Σ
Dt and demall (L')
Σ 1.
VEL'
Proof. We separate the discussions for different d'small (I').
1. If demaal(') = 0, then Psmaul (L') = 0 and thus (43 trivially holds.
2. If 1 < dsmall (L') < Without loss generality, assume that (i e L' : pı < + =
{1. ... dsmall (L')}.
(a) If ((ddeaaaL)/m Pt < 1. Then the neighborhood Nata defined in 137 is subset of Ne1 defined in (I22), i.c., Natat S NNs. Thus 143 holds by observ-
ing that (143) is dominated by the lower bound in Theorem D.4 Specifically, by
In(x))
for any 0 and by dematl (L') < 3, prove that In( (1+ (L')) damau(E')
12 1= min {p., 1)
Psmalt (L') In (1 + apsmalt(T.)
2L'm n
<
5 n I
where the last inequality is by 2.
36

---

(b) If maXie(d (deomm > n. without loss of generality, assume that > 1. Then we construct packing set of distributions p = {pt, } that contains the following two distributions.
n.
j j= 1
p p+())=
Pj +
d-1
] == 2, ... d
(144)
Pd
2m
P1 d-1
j j=
and
] ;= j = 2, ... -1
An
PT (T()-
(
=
Pj
P1 + d-1
(145)
Pd
4n
j = d
One validate that the distributions in P are well-defined and in the additive neighborhood Ng (v) (by observing that S 1 and d 2 2, and thus ب S f. By
applying Lemma A.5 (under setting and A T.. we further prove that for any q' A(d),
1 where S(P)
1KLG))2//(1)
(146)
8n
PEP
Thus the first condition of Theorem A.3 holds. Below we analyze the second condition
of Theorem A.3 By definition of P we compute that
/
dPoi (n, 9) dPoi (n.
dPoi (n.p*) -f min {dPoi (n.p*) .dPoi (n,p²)
min 9EP
(147)
=1 TV (Poi (n.p" (o.pt). Poi (n,p")
(148)
1
21 TV
Poi
Poi
n
2n
4n
ni1
TV
Poi
+
Poi
ripa
(149)
2
d
4
n²
1
1
(1)
21
(150)
2
n2a
2
+
d-1
pt.
1
21
(151)
4
2
where 147 is by definition for P that only contains two distributions, 148) is by using the definition of total variation distance, [149) by the total variation inequality for product measures (Lemma D.2). 150) is by Lemma B.9 Thus the second condition of
Theorem A.3 holds. By applying Theorem A.3 under our proved conditions (146) and
A.30
151
we finally prove that
1 f(P) 1
max E M A(x))
(152)
'EP
32n
In(1 + damall (!)) >n
Psmail (I') In (1+
dsmall (I')
(153)
npsmall (L')
where
153)
by observing that Iu(1+d (ill+dmmi((L))) + Damall (L') In 1 domaull')
repamatt (L')
2d'matt('
6 (due to In(x)
for any 0 and the condition that
dymall (I') < 3).
3. If dsmall (L") 2 4: Without loss of generality, assume that {i E L' : < 9)
{1.... dematl (L'). For brevity, denote d = domay(l)) > 2 and p Σ Pt. Without
37

---

loss of generality, also assume that p1 2 ... 2 (T)) then
dz (Lm) and i 2 Psmali()) (L))
(154)
3
Let Ki l E N be defined as follows.
2 d
S
1 S
K
and ni
<
h
and nő < 1.
(155)
and nep 2 [np] and nd 2
np
Thus by definition, we have
2 2 and k 2 and K k s Vemou(L))
2 and h: n
max p: n
(156)
For i 1,... we construct a packing set of distributions supported on symbols B, {k- i K + 1, 8 as follows.
For i = 1,.., k P. = f0x-i- ,
(157)
We construct the following set of distributions that lie in the additive neighborhood of p.
1. 72
1 n
W/ q' wa and of E P. for any 1,...
9
(158)
where
1.... .
max (p.
qo(i)= =
Pj +
dsmatl (1))
d + 1,... (L')
(159)
Pi
1 max B
j = dsmall (L') 1....,,
Pomali
One can verify that the distributions in P are well-defined (i.e., normalized) and lie in the neighborhood N (p) defined in (T36). This is by < for j = 1,... d, and under (56) and d < demett (L),, and by under 154 and n 2 4, and by observing that 2 i max {ūx } 2 for any j = dsmau (I') + 1....,.. .d.
by 0 < max [1
v max 1 1
d domall (I.)
A max p.
1/n
I Pomaiel (')
3/n
-- maxe www.xappp.. 1
02 Pj
I- I-Pamet(
Now by applying Lemma to P: for each i = k. we prove that for any of E Add).
it holds that
Σ 1KL())2//R)) PEP.
2 where S(P:) In (1 7)
(160)
P2
Thus the first condition of Theorem A.3 Below analyze the second condition of
Theorem A.3 By definition of P, for any fixed i E [k] and any fixed == (1 4) of
E q P, we compute that
(n. 1 + 1a0') dPoi
dPoi (n.p) = =f
min P'EP.
min dPoi q'EP.
n.
9
q'
dPoi (n.p) p)
(161)
2 min 8 PP Poi(nn 1 2 +
Pr
[Rei-R41 = xxc]] 6
(162)
38

---

where 162 is by probability mass function of Poisson distributions Poi 0) and Poi (n )). By applying Theorem A.3 under our proved conditions (60)) and (162) we finally prove that
1
k 2en
In 1 7
max E ((L
wi f(P:)
(163)
1 2en
d L2
- In (1 (1+ 2))
d < 2
up
In
1 +
d'
and nő
(164)
ap
[np]
In
1 +
4 (
d 4 and nő 2 1
2en
ap
Ω
< 4
Ω
In
+
and ni < 1
(165)
p
1+
and nó 2
up
up
In d 20
d
p In
1
(166)
n
np
In(1 + dsmall (L')
dsmati (L')
20
+ Psmatt (L)) In 1
(167)
n
nPssmal( T2)
where (644) is by using the definitions of and k in (155
(65) is by [x] 2/8 for any x 2 1, (166) is by A + x) 2 In (1 + Xx) for X 2 I and x > O. and by In + Ax) s
X In (1 x) for 0 I X I and O, and the last inequality is by applying (154).
D.3 Non-DP Per-Instance Lower Bound under Notat (p)
We now prove the per-instance lower bound in Table Table under neighborhood Natat (p) Theorem D.4. Let n, N and p A(d) be fixed. Let (p) be the following additive local neighborhood of p as defined in (37p.
137
Notat (p) = fa: : 1g: pil min Pss V n
Pi for any E [d]]
Σ 14: pel s n
1 } (168)
q
Then if d 2 2, it holds that
E qE Natue (p) an Poi(nnn)))
max
KL(q,A(z)) 2 Ω
Σ min
pis
n #1
(169)
Proof. We will apply Theorem A.3 to prove the lower bound. Below we first construct the packing set. Without loss of generality, assume that p1 2 ... 2 Pa. For brevity, denote
We P2x-1 + P28
and A 2 min
PaR.
P2k n
for ls -1....
d
(170)
2
Let P be the following packing set distributions.
1
wk aº gx Pr = (ot.
p
9
(171)
where
P2k
j = 2k- -
(p2k + Ax)
j = 2k 1
aet (0)
P2k
j 2k
and +
1
(p2x Ak)
j 2k
16
we
0
j E [d] \ {2k 1,2k]
j E [d] {2kk - 1,2k]
39

---

One can verify that distributions in the packing set P are normalized and lie in the statistical neighborhood N (pt by observing that min
Pr-1
2 min (Pa. v E for any i. By
1i-1.
applying Lemma A.5 (under setting
Pat
and
A
) further prove that for any
we.
q E Ad))
(KLGg~a)2/00 2 dtEP
Σ
1 where f(Pk)
mii
P2k- 7
1
(172)
|Pkl
Pak
32wR
we
Thus the first condition of Theorem A.3 holds. We now analyze the second condition of Theorem A.3 For any k and any fixed o' E Pı, k. by definition of Pk we compute that
dPoi n, Σ wi w))
min EtEP dPoi
dPoi
n. uk o + Σ wi g'
(173)
n. wk 4 + Eiee wi ...)))
=
min
dPoi
n, Wk 4 + Σ
ur .o'
dPoi
n, Wi 9 + Σ
wi of
(174)
ip
=1- TV
Poi
n. Wk gt + Σ
Wi g¹
.oi
n, Wk 9 + Σ wi of
(175)
21
TV (Poi (np2)- 1).
Poi (n222-1 nd+)) TV (Poi (np2x)
Poi (npe* nAx))
(176)
1
A
1
n²A? K
21 2
(177)
1P2k-1 1
2
np2k nAk
21 min (mpak: 1)
Tk
(178)
where (74) is because Ps only contains two distributions, 175 is by using the definition of total
variation distance. (766 is by the total variation incquality for product measures (Lemma D.2). (177)
by Lemma B.9 178 is by P2k-1 2 P2s and by definition 170p of A, 1 min {P2k: v PaR S
Pas Thus the second condition of Theorem A.3 holds. By applying Theorem A.3 under our proved conditions (12) and (178). we finally prove that
2
1
1
max (KT(g, 9EP
Wk To [(Pk) = 128
min
P2k
(179)
n2
k=1
1=1
1
Pis 2
min
(180)
256
n2
where 180 is by observing that for P1 2 2 Pa. the case that DL# min {Pax: #}
>
1 min (Pmin(22+1.d), J. We now separate the discussions for the remaining (at most two)
symbols.
1. If D min (p:. 4) (by observing that there is only one remaining symbol).
2 then 180) suffice to prove the bound (169 in the statement
2. If > d 2i min {pi, + 2n then it must be the case that Pı 1 2n P2 2 and
Σ min {pr, 11 < 2n
3.
By repeating the proof for new packing P' = {pppp) where
P1
j ==1
2n
P()
P2
+
2n
j=
(181)
j j= 3, .......
similarly prove new lower bound of 1. p' is also in the neighborhood Natat
One can also validate that the new packing
[37 This suffice to prove (169) in the statement.
40

---

E Deferred Proofs for Non-DP Per-Instance Upper Bounds
E.1 Non-DP Per-Instance Upper Bound (Sampling Twice Algorithm)
We will use the following lemma for bounding the estimation error on zero-count symbols.
Lemma E.1 (Error of Algorithm I on zero-count Symbols). Let p E A(d) be discrete distribution over d symbols. Let N. Then Algorithm satisfies
E
E
Σ
ps In
Evel B4
Pi
E
Σ VieL
Pi
In
1+
Eier.
IEL
npp
(182)
Liez
Proof. By definition, we have that
Σ Pi In
Eier P
E
Σ
Pt
In
r2p:/2
+E
Σ pi
In
EiEl &z Eier. mppl
Tj.
Liel
LiEL
(183)
We first analyze
1 By concavity of In(t) over t > 0 and by H. S xz + 1, we have that
I S E,
Σ
Pi
In
np: 2
E
(184)
LiEL
where the last inequality is Lemma B.1 under m over > 0, we have that
2. We then analyze 2
By concavity of In())
E r2ps/2] )
2 S EL
Σ Liet
ps In
1
IEL
(185)
Eier np:/2
2 Σ
S
EL
Σ Pi
In
1+
V
(186)
EiEl DiEL
np
VEEL
where the last inequality is by applying Lemma
B.3 with b = 0 0nnd -= 1.
We are now ready to prove the Non-DP per-instance upper bound for the non-dp "sampling twice" algorithm Algorithm
Theorem E.2 (Per-Instance Upper Bound Sampling Twice Algorithm). Let A the estimator given by Algorithm 7 If > 2, then for any and any p E A(d),
ΣJEL1
)
+ + min Pt: n #1) (187)
1
KL(pI|A(2)) So
E Σ Pi In 1+ Djjr, Pj
p>
LiEL.
41

---

Proof. By definition,
E
(188)
2. p.
Σ Pi SEL
E
Σ IEL
ps ln
Ps/ E DjELP! Pj Ti/ EJel $3
+
Σ ps
In
+ Σ
pi
In
Pi
+ In
ē +
Liel 31
n/2
BEL
n//2
EeT.
12/2
(189)
2 2 jEL. 1
Σ
Pi
<R
Σ Pi In
1
+ E
Σ
Pt
In
EET.
+
ZjEL
np;
n//
LEEL
VEL
n//
+ E
Σ
P
In
Pi
+ Σ
24 n2p//2
(190)
n12
L
L
11/2
L
<0
E
Σ
In
1
Σ IJEL! DjELP) Pj
+ R
Σ
1
(191)
n1/2
n/2
VEL
L
<0
E
Σ
Ps
In
1+ ΣjEl
12 Σ jEL
+ Σ
min
1 Ps+ n2
(192)
LieL.
where (190) is by In(t) < t for any 0 and by applying Lemma E.1 191) is by applying
Lemma 10 under m = n/2, c1 = 00, C2 = +00, = 0 and e = 1, and the last inequality is by nP,
Pr(i &
1), and by Σ, min (pr. ) 2 for d > 2.
L
E.2 Proof for Matching Lower and Upper Bound
Corollary E.3. Let A be the estimator given by Algorithm
Let sp and N 1 (p) be the
additive neighborhoods defined in (37) and (36)) respectively. Then for any n and any p E (d),
E P--PPi(T.p))
KL(PIA(())
O (lowerlp, n, Notat) + lower(p, n, Nst))
(193)
for any choice of neighborhood size 1 2 such that L.e S Ind Specifically, we can always choose t min {1, 2n
Eo 1 Proof. We will use the upper bound given by Theorem E.2 Observe that by Ex S
have soyos P5.
1+ EjEL! n EjELPi Ps
(1+
] EsELnps Ps
EjELm st
E
Σ
p.
S
Σ ln 1+
(194)
iEL:pI
iEL:P:
lower(p, n, Ng4) in Theorem D.3
(195)
Additionally, by definition, we compute that
Σ
ΣjEL 1 pi In
1+ n
SE
Σ In [+
(+++)
(196)
DjEn,, Ps
iELipi>> L =
1 [1 a
Σ
Pic ane In
(197)
k:p;> !
00
Σ
1
-lower(p, n, Notat) in Theorem F2
h:p
(198)
42

---

Neighborhood N
lowers, & (p, n, N)
Conditions
Reference
N 6
Ω
Σ
P: +
Σ
n=
E, 22.222 2
Theorem F.1
sips
Iu (1ddamal(L))) ?
N 6
C S [4) 12 1,d22
Theorem F.2
ne
Pemalt(L') In (1+ dematt(L)) ns Pamaal
8 E, 21
Table 5: DP per-instance lower bounds, where PL')
Σ
Pi and (L') E iE 1EL/
1
iEP/sp me
where (997) is by L E [d] = 0} and by probability mass function of Poisson random variables, and (198) is by choosing & such that t- e hnd Specifically, can choose t min {1, 2 In Ind).
F Deferred Proofs for DP Per-Instance Lower Bound Theorem 3.1
For ease of presentation and understanding, we break up the neighborhood N - (p) for given small 2 into two sub-neighborhoods: one N = with the same small perturbation for every symbol, and the other Nu - (p) with larger perturbations for small symbols, defined follows.
We then prove per-instance lower bounds under the sub-neighborhoods (p)()) and N& (p) respectively. By definition (2). their average is a lower bound for the per-instance lower bound under N (p) i.e., lower(p, n, No N& ) 2 lower(p, N + lower(p, n, N& ). (This is because one can construct distribution over hard instances, choosing the hard instance(s) in N& $ (p) and Nstor()) with 1/2 probability respectively.)
Our results for DP per-instance lower bounds under neighborhoods Ng 2 2 1 are summarized in T
F. DP Lower Bound:
N
neighborhood
In this section, prove the per-instance DP estimation lower bound in Table 5 under additive neighborhood. We first prove a lower bound under add- nz neighborhood.
Theorem F.1 (Lower Bound N me Neighborhood), Let d E N, 0 and 0 s á < 1, p A(d)
be fixed. Let N& (p) be the additive neighborhood defined in (6 for t follows.
N (p) m2
{1: q: 1::1: - ppl S
for any E [d] and Σ 4 S max
Σ
ne
ME
Spi
Epp
(199)
8 < E and d 2 2, then the expected KL error of any (e, 8)D estimator A satisfies
1 Σ min { Pt. pi n²=²
max gEN
((L(),A(())) 20
(200)
(p) po)o)(().))
Proof. We will apply Theorem A.4 to prove the lower bound. Below we first construct the packing
set. Without loss of generality, assume that that d mod 2 = 0. (Otherwise, sort the symbols to
satisfy min { Pr, pi n==a 2 ..... min Pa, n=ea and ignore the last symbol the below
constructions.) For brevity, denote
wk = P2k + P2k
and A = min P2k. for k = 1.... ..... 160
(201)
43

---

Let P be the following packing set of distributions.
p
1 =
of mu Ep = (04.
(202)
where
P2k-1
j 2k
1
(P2k-1 + Ab)
j = 2k -1
-
P2k
j 2k
and +
(p2x
A&)
j 2k
0
j E [4] \ {2k 1, 2
0
j E [4] 12k - 1, 2k
One can verify that distributions in the packing set P are normalized and lie in the additive neigh- borhood N² (p) by observing that ne 2 min {pi-1, ne 2 min {Pss 1
ne for any i. By applying
Lemma
(under setting a P2k-1 and A
Ae ), we further prove that for any g E A(d). wig
mi
[Pal
() 2 where f(Pk) P"EPk
Σ
Pak
1602 wk
miin
P2k-
P2k n2
(203)
Thus the first condition of Theorem A.4 holds. We now analyze the second condition of Theorem A.4 For any and any fixed qf Pı, 1,... & and fixed qk Pk. Let Poi nz. Din wy d' and y Poi (n A&) and y Poi (n As) be independent Poisson random variables. Then
we could construct the following coupling (z, σ) between distributions Poi (n. Σi wi g¹) and
Poi n, Wk g² + Eijx wi )
x y
1 = 2k
It
I y/
I 2k
(204)
I [d] \ {2k - 1,
By definition, we compute that
1
[|
=||
E
3/
(205)
80c
where the inequality is by definition A & 160ms Thus the second condition of Theorem A.4 holds.
By applying Theorem A.4 under our proved conditions (203) and (205). we prove that
f(Px) (1)
1
max E [K((,, PEP
2 wk
P2k-
20 8 160
P2k n²
(206)
By repeating the constructions under A prove that
min {P2x 1. 1 ne for k = 1,... we similarly
160
max E K L(q,A()))) OEP
2 20
min P28-11 P2k n2
(207)
8 160
By combining 206 and 207
we prove the bound 200 in the statement.
F.2
DP Lower Bound: N
neighborhood
In this section, we prove the per-instance DP estimation lower bound in Table for low probability symbols.
44

---

Theorem F22 (Lower Bound low probability symbols). Letp E A(d be fixed. For any t > 0, let N be the additive neighborhood defined as follows.
t
No. (p.m) (9: 9: 99: Pal
for any i E [d] and
Σ
9: S max
Ps
ne
nE
(208)
Then ò S ne 2 1, 1 and d 2, then for any L' [d], the expected KL error of any (e, estimator A satisfies
KI(g.A(x)) 20 In + dismal(L')
demait(
E gEN& (p.n) po)Po((
max
ne
+ P Psmall (I') In (1+
'Psmall (T!)
(209)
where Psmall (L')
Σ and dsmall (L')
E 1. BEL PPIS
VELL PP
Proof.
1. If damall (L') = 0, then Pemall (L') and thus 209 trivially holds.
2. If 1 & dsmalt [2) S 3: Without loss of generality, assume that {i E T'' : :4 S ne =
{1.... dsmall (L) We construct a packing set of distributions p = {p- P that
contains the following two distributions.
j=1
++()+
80mE
(210)
80ns
(pj
PL
j= == 2, ...
and
j=1 j = 2, ... . d d-1
160ns
pT (f)
(1
80me
+ d-1
(211)
50mz
Pd
7-1
160ng
==d d
One can validate that the distributions P are well-defined and are the additive neigh-
borhood N + (p) (by observing that 0 S pı f for d 2 2 and thus 1 S (.)) By
applying Lemma A.5 (under setting a s0ne and A 1n0me we further prove that for
any E A(d),
Σ SEP
1 kkLgg
2 where f(P)
(212)
P
a
320ns
Thus the first condition of Theorem A.4 holds. Below we analyze the second condition
Let ; = pt. For any E P, let y ~ Poi(n min(p*, ,p- }) and let y' Poi(n max {pt P pー} min(pt P })))). Then we could construct the following coupling (x, σ) between distributions Poi (n, g) and Poi (n, g):
Theorem A.4
+ v y
1
and 5. = yt
= 1, 1.... d -
(213)
1 2,
1 + vk
1= d
By definition, compute that
I|
1|11| =E M// + v/l
=
(214)
80s
Thus the second condition of Theorem A.4 holds. By applying Theorem A.4 under our proved conditions (12) and (15 finally prove that
max IE (KL(g.A(x))) 21
45 45
((P)
(215)
gEP
10
20 320ns
In (1 + dsmalt( (I'))
+ Pommal In (1t dsmatt (I.')
>0
nE
Pemali L') nE
(216)
where 216 is by the assumption that dematl (L)) < 3 and by In (1 + æ) for 0.
45

---

3. If dsmallL') 2 4: Without loss of generality, assume that fi L' : S [ consists of
symbols 1, (Lmo For brevity, denote d damall (L') > 2 and Σ Pi- Without loss of generality, assume that p1 ... ... 2 Pdomat then follows that
d2 damall (L') and p 2 Psmall (L') (L')
(217)
3
Let le E N be defined as follows.
2
T60nep S 2
S 2
160nep d
K
d
T60nep > 2 and 160neý <
160nep
> and 160neý <
d
and 160nsø 2
[160nep]
and 160neø 2
1600ng
160nep
160nep
(218)
Thus by definition,
and R. k ds dsmall (L')
k
K 2 2 and h 221
and
& max
2
160ns
160ng
(219)
For i 1,... we construct a packing set of distributions supported on symbols B, ( - K +, 8m.1 follows.
For i = 1, k P. = ... 5
(220)
We construct the following set of distributions that lie in the additive neighborhood of p.
k
k
1 and g² E P, for any i = 1,,
p
d +
g¹
160ns
160ne
1=1
(221)
where
j 1,... ,
max Pirane
Teons
j à + 1,, (T)) (222)
(e(
1-
Toone
Pj
BemaiilL))-
max P. Teane
Pj
1
j = damau (L') + I,...,
I- Pamolt
100ms
One can verify that the distributions in are well-defined (i.e., normalized) and lie in the neighborhood Nz (p) defined in (6). This is by observing that S +. for j = 1, ...
ne
and that <
max max Pe } nea
< max [g. {
due to 219 and < damail LL',
damall (L')
160ns
--max (oaxx pnome
and by 0 2 1- 1-PomoielL')
100ms 106ne
under (177 and ne 2 and by N
G- 1--max( (F: ra0ne
Pj I-PamalllL")
I60nE'
Now by applying Lemma A.6 to P3 for Bareach 1,... ,,, we prove that for any of E A(d).
where f(P.) = In (1 (1+ #t)
(223)
PP.
2
qEP:
Thus the first condition of Theorem A.4 holds. Below analyze the second
condition of Theorem A.4 For each i E [k] and fixed q¹ E P,.j = 1 1.....k k
k
and fixed g' E P..
Let x
Poi n, (1 T 9et + Σ wj g and
y
Poi n, (1-
160ne d + Wl o
+ Σ
Wi qd)
independent Poisson
J
46

---

random variables.
Then
we could construct the following coupling (x,
q + Σ w q²) and distribution k
between
distribution
Poi n, (1 100ns
j=1
Poi n, (1- 160ns
9ºh + ws q + Σ wj qd)
1/1
k. K + 1, 1,... 15
(224)
1 E
[d]
(nr - - k + 1. .1}
By definition, we compute that
K-1
Kid
E ||
2|11|
B| ul 1
E E
+ yol
(225)
80c
where the inequality is by triangle inequality for & distance. By applying Theorem under our proved conditions (223) and (225), we finally prove that
A.4
max R ((T((;A((a))) PEP
48 48 ((P.) = 160 20
k In
1 +
K 4
10
(226)
2 In (1 2))
160mEp $
160-ms
In 1 t
> 2 and 160neø < 1
(227)
160mn
160ne
|160mEp)
In + 21 100nep
d
160nep > 2 and 160neø 2 1
160me
d
S
ns
I6Unsp
Ω ne
In
1 d
d I6Unep
2 and 160nep
(228)
Ω p In
1
d
d 160nep
> 2 and 160neø 2 1
nep
In 1 + d)
20
+ G. In
1+ NE D
(229)
ne
[In1 + dematt (L))
Pemoul (L') In [1 demals (L')
20
(230)
T1S
NE Pemall (L')
where
227
is by using the definitions of and ls in (218) 228 is by [x] > 5 for any
x 2 1, 229
is by Aln(1 + x) 2 In (1 + Xz) for X 2 and x O, and by In + Xr) S
X
for S and x > 0, and the last inequality is by (217).
G Deferred Proofs for DP Per-Instance Upper Bounds
G.1 Upper Bound: DP Sampling Twice Algorithm
For convenience, we first prove the following lemma about the probability of small symbols going above threshold, and the probability of large symbols going below threshold.
Lemma G.1 (Probability of False Positive). Let m E N. 0, > 0 and E > 0. Let x ~ Poi(mp)
and 2 ~ Lap (t). !fp min then
Pr +
T
{0
(231)
min
47

---

Proof. By applying Lemma B.2 under setting a = mp,, b = and c= min we prove that
Pr + min (e, 13
4
min min(s.1)
2
$ 50 0 (c
(232)
3
where the last inequality is by S min(e.1)
Lemma G.2 (Probability of False Negative). Let m E N. p. T > 0, and & > 0. Let x ~ Poi(mp)
and 2 ~ Lap (1) I Z minfs,1] for = 6r 2 1, then for any constant 2 0,
0 20 m min 1 Pr + min (e,
(233)
Proof. By applying Lemma B.2 under setting a mp,, b 1 and minfe,1f prove that
4
min(r.1) B
0 0
min(1.))
Pr x +
S min ( 1]
(234)
3
1
50 -
(235)
mn 1
where (34)) is by 2
mp, min(1.e] < < mpp min(1.e) for P. m mmin(1.e) undersetting t 67,
and the last inequality by e s 0 (2-) for mp, [ 2 t 2 and y 0.
We then prove two lemmas that bounds KL estimation on (small) symbols below threshold and (large) symbols above threshold. Lemma G.3 (Error of Algorithm on Small Symbols reused samples). Algorithm satisfies
E
Σ Ps LiEb
Liel Pi Bi Ever.
50 E
Σ
ps
In
14
min EIEL amps)
EL
(236)
2,
iEL
+
Σ
1
1
(237)
an
nn min 132p,
ipp omn min (..1
where we have denoted L dependent subset in Algorithm
ii::; rr + Lap (0, min } as the randomized instance-
Proof. By definition, have that
Σ Pr In
Eier Pi CEE
=
Σ Lieb
Ps In
ammp
+E
Σ viEL
Pi
in
EiEL H; EEEL amp:
Z
(238)
We first analyze 1
By amp; < min(e, 13 < 3; under P. S
we compute that
min
<E
Σ
Pe In
ampi
(239)
T;
iETap:> e
48

---

We then analyze 2 By concavity of In(t) over t > O. we have that
Eier Blū
ampili
4
S E,
Σ pi In
1+
EiEl Eietamp anpi
(240)
LIEL
Σ
E [ amp,l E L)
iELipi (2.)
L
< Eσ
Σ IEL
In 1
Eier. ampi
(241)
E1 1 IEL.
0O
E
Σn pi
In
+
Σ
3 ampi
min(l,e) DiEL ampi
on
VEL
iELipi > on minge,
(242)
where we have denoted L ii: + Lap (0,
as the randomized instance-
min(e.))
dependent subset in Algorithm (241) is by applying Corollary B.5 242 is by In 1 + x + y) s
In(1 + x:) + y for any 0 and any y.
By plugging (239 and 242 into 238
we prove that
Pt
E
Σ LEL
Pi
In
21 Exer
Eiee
(243)
E
-
00
E
Σ IEL
In
14
+
Σ
piln
amp,
+
I;
min = DiEL cnpp
an
L:p1 minfe.1)
Σ 1
00
E
Σ
In
1+
REL.
+
Σ
+ a minte. 1)
min (1,)
ΣiEL DEEL cmpp
JEL
kpp2>
minfe.))
(244)
where 244 is by applying Lemma B.10 under setting m an, = -oo and min b
and c min(s.1) for p; mln)
Lemma G.4 (Error of Algorithm 2 on Large Symbols reused samples). Algorithm satisfies
max
G4. min
ampi
anp:
ln In
(245)
L
max
Fis (in(e.]]
an
50 dre 1. 1 1min p.S. Sonnmiten
Σ
+ pi a min(s, 1}2
(246)
anmin(e,1)
kp. mineeay
where we have denoted L dependent subset in Algorithm 2
(i:m; + Lap (0 z min(e.1) ʃ as the randomized instance-
49

---

Proof. By definition and by 7 2 1, we compute that
anp:
max
min
anpi
E
Pi
In
(247)
i L
max
Tis
min{s.1}
am
=E
Σ
pi
ampi
24 anp:
+ E
Σ
pi ln
anpi
2, anp;
Iz
QY
I;
on
i [
ip LApE S an m.a
(248)
We analyze
By applying Lemma B.10 under setting on, 61 min C2 +00, prove that
b 1 and [
1 10
<0
Σ
+
1
(249)
pi a minfe, 1)2
ipp min(frll
We finally analyze
2
By 34 amp; for & I. and ps an 1,e we prove that
Σ
Prip & L)
LJ
amp:
50
d. mins ps Conmtrte.
On
kpp an mnm(ae().)
Error
(250)
1 mim P.S. min an 1n,
-0 dre dre 1
(251)
where the second inequality in (250) is by applying Lemma G.1 under setting an, and by
applying Lemma B.7 under setting À omp, and mi By plugging (249) and (251)
into 248
we obtaun the bound in the statement.
Lemma G.5 (Error of Algorithm 2 on Large Symbols fresh samples). Algorithm 2 satisfies
max 8 min(z,1) } 1- (1 ak) npp
(1 ampp
E Σ
pn In
(252)
(1-a)m
max
[c.1]
50
Σ
1
pi (1 a1-m) min 1], + de
1
min, P. mnnt [.
a1-am
a)n
(1 0 an min (c, 1}
Eip:
(253)
(i::; + Lap (0) z min(e.1) }
where we have denoted L dependent subset in Algorithm 2
ʃ as the randomized instance-
50

---

Proof. By the independence between set L and noisy estimate 2 (as they are computed on indepen- dently sampled datasets x and x' respectively). we compute that
(1 mpp
max
47 min - (1 om)p:
252
Pr(i & L. E In
3/ (in
(1 a.n
max
(254)
<0
Σ
+ 1
+ (1 a min (1,
Σ
e
(1 (1-ajh aI-a)n ps (1 nn² minfE, 133
k:. Cnnnanniin min(e.1)
Eps min(e.1)
Eror on TP
Error on FP (255)
50
Σ
1
+
1
+ de
1 min D: mine T.c
an
Di
(1 - a2 min 1)2
(1 am min(e 1)
[c,]]
(256)
where the first term in 255 by Pr(i $ L] S 1 for p: (i,) (by definition) and by applying
Lemma B.10 under = (1 - a)n, b 1.4 c 1.c)
-00 and c2 +oo; the second term
in 255 by applying Lemma G. under
256 is by definition.
We are now ready prove the per-instance upper bound for Algorithm Theorem G.6 (DP "Sampling Twice" Algorithm). The estimator A given by Algorithm and satisfies the following error bound for any fixed A(d).
E-
Σ 1
KL(D|IA(x)) 5o E Σ Pt iEL
1+
SEL
+
p>
min [1 Eiet upi
n2 min 1,
(257)
1
Σ
(258)
Pi n² min (e, 1322
kp:2 [l.]
where L {i + Lap (0. !) s (i.)c.1)) as defined Algorithum
Proof.
By the definition of Algorithm] 2
we compute that
E
[[LL(p, A(x))
(259)
pc/ EjELPS
EiELPi
2 Σ 1i Tz
=E
Σ Paln In I.T.
+
Σ Ps iet.
In
+ +Z P: In
pi (1-a)n
+ In
2// ΣEEL 3z
(1 an
[1-a)m
EEL
ps/ E'EELL Pj
EiEr (1 - a)mpi
č -- E1 aamp:
E
pi In
Rzl Σjet Tzj
E
Pi
In
(1 - a)m
LiEL
iiL
(260)
pi ((1 (1-a)npp
3. (1 mpp
+ E
(261)
Fi
(1 nn
LigT.
51

---

where the last inequality is by In(t) I t for any & >> 0. We first analyze
By applying
Lemma G.3
we prove that
Σ
1
50
00
E
Σ LE
Pi
1+
min(1,E) EIEL ampi
Σ
an +
a² pt
an minie.t)
(262)
Σ 1 IEL min
<0
E
Σ pi
In 1+
Σ
L Ti
(1, EIEL np:
n²s²pp
PPp wmintc.]
(263)
where (63 is by 0.5 in Algorithm We then analyze ② By the independence between L and č in Algorithm 2 (due to independent sampling of datasets and x') conditioned on fixed L, we apply Lemma B. under setting m an,, p EiEL Ps. G1 oc, C2 = +00, and
min and prove that
1 1670
1)
1 1
2 S0
EL
- E
(264)
(1 a)n min
min
n
where (264) is by setting a 0.5 in Algorithm i L, we compute that
We finally analyze
3
By definition of 2; for
npi
3
EE
Pr In
(265)
ig L
max
Tis minte.1)
max Tht minte.1y
max
T2 (r.1)
+ max
R/. min(c.1)
npp
(266)
max
T. minfe.1]
amp:
<a E
Σ
pi In
amp,
L
max
Ti min(s.1)
am
(1 a )mpp
max
1 min
(1 az) rmpp
+ (1 a) E
Σ pt In
(1 an
max 1/ min m (2.1)
i
(267)
0
Σ
min, S n man 2.13 n mminfe,1)
(268)
Pi n min(e, 1]2
1::2 aminge.yy
<0
Σ
1
Pr[L + 0] n (onin(e,11 1]
(269)
Pi n² 1)2
2p:1 min
where 267 is by the joint convexity of the function æIn with regard to arguments x, P. 2 0: (268 is by applying Lemma G.4 and Lemma G.5 under setting 0.5 and 4 d in
Algorithm 2 and (269) is by Pr L] 2 (1) for p. < n min[[.s) under a = 0.5 and r = 4
in Algorithm 2 (by applying Lemma B.2 under setting a amp; 1 and min ). By
plugging our proved bound (263)
264 and (269 for
and 3 into (26 we prove the
bound in the statement.
52

---

G.2 Proof for Matching Lower and Upper Bound
Corollary G.7. Let be the estimator given by Algorithm
Let Natat, No N.. N be the respectively. Then for any n and any E (d),
additive neighborhoods defined in (37).
136
(6
E
{L(W]AA(>))
so
lower (p, n, Natat) + lower (p,n, NsA
s-PPii(..p)
Non Per Ver-instance Lower Bonand
+ lower,, n,, ne lower P. n.
(270)
Lower
under choosing neighborhood size 6T for = 4lnd.
Proof. We will use the upper bound given by Theorem G.6
Observe that for any >
min 1, (M where dsmaul
dymut (L.
Σ
1 and Psmaai =
min 1,e) 1,e)iic
sEL:p: mimme.a
Σ
Ps- Thus the first term in Theorem G.6 satisfies
Ve LEL:
S om 1y
Σ1
E
Σ Ps
In 1+ min(1, (1, Eiel vipe
SLL
L
(271)
min (1,8)
Pssmall (b) In 11+ min e rop repooaat )
dematt (L)
Pi-In In 1 d 4
<
Σ
Prli E m.]
kpp: minde,1)
(272)
minse PC mi
Pr(i E L m (c,
+ E
+
Σ
(273)
n nmin 1
2pp min(e..)
dsmall (L)
In (1 + demaui amin 1}
In de t
<B
Psmall (L) In
+0
Σ
(s) min(1,8)
n2 min {1,8)
i:p+> minnfe.)
(274)
dsmalt (I')
(1 + demau( nmin(e,1)
1
< max L'Cld
('smalLL') In
+
+0
Σ
Psmoul (L') min(1,e}
n min }
kpp.
(275)
=0 (Theorem D.3 Theorem
Theorem D.4 + Theorem
(276)
Σ
where (72 is by min (1,6] LEe np
REL
(Lmait()
for any t > 0 and dematt (L)
min Anpmtttt
(.)
Σ
1 and (smalt(L)
Σ
ps 273 is Pr[L
* 0] S
veTaps S maitta
iETops minite
Pr minps S an minfe,11 iEL
Σ
Pr(i E T.] (ensured by union bound); 274 is by
kp: an mintc.lf
1 minngr Pr on
In 1+
Σ
In + dymatt (L)), and by applying
VEL-PIS min
Lemma under setting m = an and choosing t = 6:; and (75) is by setting T = 4 d as defined in Algorithm 2 and 276 by definition. Additionally, observe that by definition, the second term II S O (TTeorem D.4 + Theorem E.I. Combining
in Theorem G.6 is
this with 276 suffice to prove the bound in the statement.
53

---

G.3 Discussions on the Neighborhood Size
Lemma G.8 (Generalized Packing Argument). Let d 2 16 and let O be an output space. Let err : O x O + R be an eroor function. Given p' Pp' E O. For E [d]. denote S(p') ) as the distribution of histogram sampled from distribution p'. Assume that
1. for any i.j E [d]
In d E (araa) [1| x 1111 16s
(277)
for coupling (x, between the distributions S(p') and S(p');
2. for any q O and any S S [d] such that |S| 2 d/ it holds that
Ind err (p's 2 4
Σ iES
(278)
S
Then for any (eP algorithm A with 8 e we have
d 16
max S(n)( [err (p' A(x))) 2
(279)
Proof. We will prove the lemma by contradiction. Consider bipartite graph (V, E) on V = [d] x O, where ui, u) E E if and only if err(p", 4) < Ind Then
4
For any O, degree(v) < d'/1
(280)
Otherwise the set of neighbors Nbr(v) {i [d] (1, E} violates 278 Suppose that (799) does not hold, then
In d
For any E [d], Ex~S(n) Jerr (p' ((x)))))]
<
(281)
16
Denote the neighbor Nbr(i) {u E O: (i, E EJ. Then by Markov's inequality
err (p',A(z)) z Ind
21 BewS(p')
[err A(:)) Ind
Pr [A(x)= Nbr(i)] =1 a~S(pp))
Pr x~S((p)
(282)
where the last equality is by (881
On the other hand, for any [d], let (x,x²) be the coupling between S(p') and S(p') in 277 we prove that
In d
In d
Pr (A(x)= Nbr(i)) an.S(p))
< Pr (a,,0)
A(x)) Nbr(i) and |
d'll1
+ Pr (2,2")
|| x' |1
4e
(283)
< E
lad
Pr [A(z') E Nbr(i)) (2,22)
In
e Ind
8
B(a.,a)
[||
x x1111]
48
Ind
4c
(284)
1 Pr AA(x) E Nbr(i)] +
1/4
(285)
Spp)
where (83) is by applying union bound; the first term in (84) is by recursive usage of definition of Ind,
(c, DDP to datasets (x, with hamming distance bounded by 4 the second term in (284 is by
applying Markov's 's inequality; and (285) is by applying condition (277) and S Ind'
By combining
(282 and 285 it follows that
Pr (A(x)) Nbr(i)) 2 4d'/4 av'((p))
(286)
54

---

By summing 286 over all i, we prove that
d3/1
Σ
Pr S~p(
(A(x) E Nbr(())]
(287)
4
Thus there exists O, such that
d3/1
(eNb(()) 2 /
(288)
where the last inequality is by 16. This contradicts with (280)
Theorem G.9. Let n. d > 4 E N.
in(d) 16n and 0 S 8 z d'i'nd For y I
1 32
let Ny) be the
local neighborhood as defined in (6) for t y In
(p) = q: 19: ----p -pol
y IInd d ne
for any E [d] and Σ q S max
y ynn
Σ Ps
nE
kpp.
kP:
2nn
(289)
Then there exists set P of distribution instances (dd), and a per-neighborhood estimator AN. under neighborhood size ", such that
max max pEP NEN, (P) a--pning))
E
(N, S 48y In
(290)
while for any (e, DD estimator A, we have
(p, 2 Ind
max PEP poi(ppp))
(291)
16
Thus if S o(1, then no 8)DP estimator A could satisfy (otherwise it contradicts 290 and 229
Proof. Consider the following construction of P.
P pt = for i [d]]
(292)
Then
{
In d
In for any j # i
q 2 -
ne 2j S r.
(293)
me
Thus the following construction of neighbbohooo estimator satisfies (290).
Y Ind ne
j
AN,(ot)(x)
(294)
j + i
(d-
This is because
1
In
max gEN, (p') Po)())
KL A AN, Sln
1 1-7 7
Ind
+
ns
IIndd - 1)
(295)
me
Ind
(In d)²
<2y
+
S 48y
In
(296)
where (966) is by
Ind me
< under 7 Σ 32 and by
Ind
2n
Below we focus on proving 1291] by applying Lemma G.8 conditions of Lemma G. hold.
We only need to validate that the two
1. The first condition
277 holds by ln
55

---

2. The second condition of (288) holds by convexity of the function In ( on t > 0, which ensures that for any S dd) with [S] d!/4 and any q Ad)) have
KL g)
In
In
In([S)) 2 In (297)
[
1 3]
Eies
where the second-to-last inequality is by Eies qi S 1, and the last inequality is by |S| z d/4
G.4 Additional Experiments on More Datasets
In this section, we further evaluate on more data distributions: power law distributions p; for
B 1.5, 2 in Figure 3 and Enron-email corpus in Figure 5
and MMLUU corpus in Figure 6
Add-constant (DP)
Good Good-Turing
Our Algorithm
Our Algorithm (DP)
4
4
KL Error
2
Fiid
0
102
103
10a
10
10a
10a
10
10
10
100
10a
Dataset size n
Data dimension d
Specified &
(a) d = 50000, E
(b) n 2000, = =
(c) n2 1000, d 10000
Figure 3: (Power law distribution p; (τ. KL
dataset size distribution dimension d, and DP
guarantee our methods compared with the simple minimax optimal Add-constant (DP) baseline, and strongest non-DP baseline of prior (near) instance-optimal Good-Ture Mood-Turing estimator.
Add-constant (DP)
Good- Turing
Our Algorithm
Our Algorithm (DP)
KL Error
2
0
102 10 10
10
10a 10t
10a 100
10
100
10
Dataset size
Data dimension d
Specified E
(a) d = 50000, E =
(b) n = 2000, : =
(c) m 1000,
10000
Figure 4: (Power law distribution pt = KI. versus dataset size n, distribution dimension and DP guarantee our methods compared with the simple minimax optimal Add-constant (DP) baseline, and strongest non-DP baseline of prior (near) instance-optimal Good-Turing estimator.
G.S Instance Optimality of Gaussian Variant of Our Algorithm
Below we present Gaussian variant of our algorithm, and prove that it is near instance optimal up to (18) factor.
56

---

Add-constant (DP)
Good Guring
Our Algorithm
Our Algorithm 2 (DP)
7.5
8.5
10
NLL
7
8
9
8
6.5
7.5
10a
109
10a
10
10
2
10
10
Dataset size
Dataset size
Specified
(a) = 30522, = 1 (Bert)
(b) d 50257, E = (GPT2)
(c) n 10 50257 (GPT2)
Figure 5: (Enron-emails Token Distribution Estimation) KI. error versus dataset size distribution dimension d,
and DP guarantee for methods compared with the simple minimax optimal Add-constant (DP) baseline. the strongest non-DP baseline of prior (near) instance-optimal Good -orring estimator.
Add Add-constant (DP)
Good Turing
Our Algorithm
Our Algorithm (DP)
8.5
10
7.5
9
7.5
7
10a
10
10a
10
10 2
10
100
Dataset size
Dataset size
Specified
(a) d 30522, (Bert)
d 50257, (GPT2)
10 d 50257 (GPT2)
Figure 6: (MMLU Token Distribution Estimation) KI. error versus dataset size n, distribution dimension d, and DP guarantee for our methods compared with the simple minimax optimal Add-constant (DP) baseline, and the strongest non-DP baseline of prior (near) instance-optimal Good Good-Turing estimator.
Algorithm 3 (e, 6DP "Sampling Twice" (Instance-Optimal)
Inputs: Data partition ratio a = 0.5. Independently sampled datasets x a' Poi((1 a) np) s.t. x + x' Poi(np)) Threshold 4 d. Noise magnitude
Poi(a np) and
(i((1/5)
L 0
for symbol = , do
Private Thresholding: If vi S TVV 22n(L (2l(LL2268)) min(e.))
for zi N (0, add to L.
end for
Estimate small symbols' combined mass: ē max
Eiel o + (0,
/ 221(11
min(e.1)
Estimate individual large symbols:
for i E [d] L. J
x o for N (0,
2 (
Truncation:
Fz
max
min(s.1)
for
L; Dt
(1
/ lm.125/8)
(n(1225/8)
)) for forie(d] [d]
a)
max 2
+ max
1/
min(e.1)
min(s,1)
i L
Return
A(x) with A(x);
Eier
where N 7 Eigr Ti
i i L
57

---

Theorem G.10. The estimator A given by Algorithm bound for any fixed p E Ald).
is (E, 6)-DP and satisfies the following error
Σ1
{L(p]|A(x))
22 (1.25/0) o E ΣpL
ps
In 1+
IEL
+
r
p..Po)(
min [1 Lier. npi
momi
(1,6 11,5
iEL
(298)
Σ
(299)
Pi min 1
4:P (1.E)
where L is the randomized set as defined in Algorithm
Proof. The (E, 8)- guarantee follows by observing that the éz-sensitivity of vector release (01, ... Ed. 2'. x'a) is one, and by applying the (eP guarantee for Gaussian mecha- nism in [27 Theorem A.1]. The KI. error bound follows identically as Appendix G.T after re- placing all Laplace Tail bounds under Lap(1 1/)) with Gaussian Tail bounds under N0, for (21m(1255/6)
58


Reviews:
[{"review_id": "256vg0XVg2", "reviewer": "Reviewer_s8di", "summary": "The paper considers the problem of private discrete distribution estimation with respect to the KL-distance. This is a fundamental question which has been considered extensively in the non-private statistics literature. When addressing this problem, it is possible to design two types of algorithms, depending on the target guarantee: i) minimax optimal algorithms, and ii) instance optimal algorithms. Minimax optimal algorithms have optimal performance when one considers the worst possible distribution in the class. This is a strong guarantee, but can be too conservative in practice. Conversely, instance optimal algorithms yield guarantees on a per-instance basis, adapting to easier instances, while recovering the guarantees promised by minimax optimal algorithms for worst-case instances.\nBased on the above description, instance optimal algorithms are very desirable, due to their potential for good performance on practical instances. However, designing them and establishing their guarantees can be a hard task. Additionally, it is generally a non-trivial matter how one defines instance optimality depending on the setting. The specific notions of instance optimality considered in this work are inspired by the older work of [FMST24], where the idea is that an algorithm $\\mathcal{A}$ running on input from a distribution $p$ must be competitive with the best algorithm $\\mathcal{A}'$ that receives samples from a distribution $q$ that is in a neighbourhood of $p$ (which is known to $\\mathcal{A}'$). The neighbourhoods considered in this work involve small additive perturbations.\nThe paper gives nearly matching upper and lower bounds for both minimax and instance optimal discrete distribution estimation with respect to the KL-distance under $\\varepsilon$-DP. The upper bounds are obtained by designing low sensitivity variants of well-known estimators (namely add-constant estimators and the Good-Turing estimator) and then privatizing them. The lower bounds are obtained via a novel generalization of Assouad's method for decomposable statistical distances. Empirical evaluation of the performance of the algorithms is also given.\n\n[FMST24] Vitaly Feldman, Audra McMillan, Satchit Sivakumar, and Kunal Talwar. Instanceoptimal private density estimation in the wasserstein distance. arXiv preprint arXiv:2406.19566, 2024.", "questions": "I have one question that is slightly broader. What challenges would the authors expect to arise when considering the problem under approx-DP? Pure-DP can be somewhat restrictive, and is not the variant of DP that is most commonly used in practice. Can the authors provide a short discussion of the extent to which they believe their approach would also work for approx-DP?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1) The problem that the paper considers is important and well-motivated. KL-discrete distribution estimation is a fundamental topic in density estimation, and so is attaining instance optimality.\n2) The results exhibited a non-trivial degree of technical hardness and novelty. In particular, the decomposable generalization of Assouad could be of broader interest.\n3) Algorithm 1 could also be of broader interest as an alternative to Good-Turing.\n\nWeaknesses:\n1) One thing I had a slight issue with was the presentation. The way the main body is structured, the main results of the work are not stated properly. The results are described briefly in text, and then pointers are given to the appendix, where the full statements are included. This bothered me slightly while reading the paper, since I felt that the main body does not really stand on its own, and I had to do some back and forth. Additionally, the bounds were hard to parse (but I guess this is inherent to some extent when it comes to instance optimality). It would be great if the authors edited the manuscript in a future update to address this issue.\n\nOverall, I think this is a good paper that merits acceptance.", "was_revised": true, "final_justification": "My view of the paper was positive from the beginning, and still is, after the rebuttal.", "rebuttal": "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.\n\n> Approx-DP\n\nOur 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).\n\nIn 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."}, {"review_id": "tpUQRDc6N0", "reviewer": "Reviewer_4xxz", "summary": "The paper considers instance-optimal differentially private (DP) KL distribution estimation with multivariate Poisson data. They first define a new notion of instance-optimality based on a neighborhood of additively perturbed probability values and show that these new neighborhoods are the smallest that still allow for instance-optimal algorithms. They then propose a new non-private instance-optimal (w.r.t. these neighborhoods) algorithm. A private variation of said algorithm is also shown to be instance-optimal (among DP algorithms). Numerical experiments show advantages of the proposed method over baselines on distribution instances of practical interest.", "questions": "Is the $n \\epsilon > 1$ requirement in the lower bound (7) necessary? If not, what are the challenges to obtaining a lower bound that holds for all $\\epsilon \\geq 0$? \n\nIntuition for ``privacy for free' regime in line 264?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n1. The new notion of neighborhood is intuitive and the ``minimality'' result for this notion is quite nice.\n2. Instance-optimal algorithms (up to constants) are provided for non-DP and DP setting. \n3. The algorithms are novel and the lower bound proof requires some novel techniques as well. \n\n**Weaknesses:**\n1. Discussion of why 2-point and multiplicative neighborhoods are ``too small'' could be clarified. It seems the main idea is that these nbhds don't permit instance-optimal algorithms, but the explanation about why is not totally clear to me.\n2. I didn't see citation/discussion of Asi & Duchi's earlier works on instance-optimal DP estimation. \n3. A table summarizing the many previous works desdcribed in paragraph 2 of Sec 1.2 (in comparison to the submission) would be nice.\n4. The technical aspects are presented in a dense manner, with many important details and result statements deferred to the appendix. While I was able to get the high-level ideas from reading, it would be nice if the authors could streamline the presentation a bit (e.g. get rid of some redundancies and defer some less important things to the appendix) to make room for clearer presentation of the most important technical aspects. Of course this is not easy with the 9-page limit, but hopefully the camera-ready version can be improved if the paper is accepted. \n5.  Abstract could be improved to better describe the paper's core contributions (as discussed in the introduction)", "was_revised": true, "final_justification": "No updates", "rebuttal": "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.\n\n> Two-point neighborhood and multiplicative neighborhood\n\nWe 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. \n\n- 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]. \n- 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. \n\nBy 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.\n\n> Discussion of Asi & Duchi’s earlier works on instance-optimal DP estimation: \n\nWe 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.\n\n- [a] Asi, H., & Duchi, J. C. (2020). Near instance-optimality in differential privacy. arXiv preprint arXiv:2005.10630.\n- [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.\n\n> A table summarizing many previous works described in paragraph 2 of Section 1.2\n\nFor 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\n\n> $n \\varepsilon>1$ requirement\n\nThis 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.\n\nTechnically, 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.\n\n\n> Intuition for “privacy for free” regime in line 264\n\nIntuitively, 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."}, {"review_id": "1TL52jIUN5", "reviewer": "Reviewer_y5SW", "summary": "This paper studies the problem of estimating a discrete distribution over [d] in KL divergence. Specifically, it focuses on locally minimax rates: bounds which are optimal even if the estimator knows the distribution lives in some local neighborhood. The authors study this problem in both private and non-private settings.\n\nThe main contributions are as follows: first they define a notion of neighbourhood for this problem. The main idea is as follows: They consider a standard perturbation based neighbourhood where around the current distribution we can perturb each symbol to be O(1/n). Also, the neighbourhood requires that the mass of small-probability symbols doesn't change significantly in the neighborhood. The first technical result is an extension of Assouad-based lower bound to prove a fundamental lower bound for the rate achievable by any algorithm based on this neighbourhood.\n\nThen, they propose a non-private algorithm for this task. The algorithm is quite simple and intuitive. The idea is double sampling and Good-Turing based trick: we sample two datasets of size n/2. Using the first dataset we estimate the low probability symbols and then use the second dataset to estimate the individual probabilities. The authors show that this approach achieves the desired local minimax property.\n\nFinally, they show a generalized version of the algorithm to handle the private case. It is similar to the non-private version however, we use Laplace distribution to privatize various components of the non-private algorithm.", "questions": "n/a", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper is very interesting, both in terms of results and techniques. The estimators and neighborhood relations are non-trivial and nuanced. Also the results are complete in the sense that there are not many gaps in the results. Also, the authors do a good job in reviewing existing neighbourhood definitions and discuss their limitations.\nI can't think of that much weakness in this work.\nTypo in Algorithm 1→ it seems N should be n.", "was_revised": true, "final_justification": "no updates. This paper merits acceptance.", "rebuttal": "We thank the reviewer for the recognition and feedback. We will be sure to address the typo in the revised paper."}, {"review_id": "7KWtodqFkn", "reviewer": "Reviewer_VYJJ", "summary": "This paper studies the problem of estimating distributions over $d$ symbols under KL divergence and differential privacy. It introduces a notion of *multiplicative* instance-optimality, in which an estimator’s performance is measured against the best oracle estimator that knows a specified neighbourhood of the true distribution. The authors focus on a particular neighbourhood defined by additive perturbations of the probability masses. They then construct a “sampling-twice” estimator that attains instance-optimality for this neighbourhood and show that the same idea extends to the private setting by adding calibrated Laplace noise to the histogram. Conceptually, the work is most comparable to [27], which introduced multiplicative instance-optimality for the Wasserstein distance rather than KL divergence.", "questions": "See weakness section.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The extension of the \"multiplicative\" instance-optimality framework to KL divergence is a natural and fundamental problem. The authors also argue that the additive perturbation neighbourhood is the “right” notion for attaining instance-optimality under KL divergence.\n2. The paper introduces several technical innovations, such as a \"Generalized Assouad’s method\" for deriving lower bounds and the \"Sampling Twice\" estimator for the upper bound.\n3. The overall proof strategy appears reasonable and sound. However, due to limited time, I did not verify all details carefully.\n\n**Weaknesses:**\n\n1. My main reservation about the paper is its presentation. The authors completely omit proofs from the main text, which makes it quite difficult to assess the core technical contributions. I suggest including at least proof sketches for the main theorems. Additionally, the non-DP instance-optimality result seems to be a substantial contribution on its own, while the DP part feels more like an add-on and could be discussed briefly in the main text.\n2. The authors state that the main motivation for the \"Sampling Twice\" trick is to reduce the bias of classical Good-Turing estimates, yet the experiments show that Good-Turing outperforms all compared estimators. This makes the narrative somewhat confusing. Is there a formal proof that Good-Turing cannot attain instance-optimality under your additive neighbourhood?\n3. Typos: “Poof” → “Proof” and “optimlity” → “optimality” appear multiple times in the appendix.", "was_revised": true, "final_justification": "I agree with the other reviewers that this is a solid work and have no issues accepting it.", "rebuttal": "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. \n\n> Comparison to Good-Turing estimator\n\nWe apologize for the confusion, we discussed the comparison briefly in line 137-151, but will devote more space to further clarify this important question.\n\n\nBoth 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.)\n\nIn 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. \n\n> Does Good-Turing attain instance optimality under additive neighborhood\n\nThis 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."}]

Author rebuttal:

Meta-review: All of the reviewers agree that this paper deserved to be accepted. It addresses a natural and fundamental problem about instance-optimal distribution estimation, and provides significant new results. The only consistent concerns were related to the quality of the presentation, so the authors are encouraged to focus their camera-ready efforts there, using the reviewer comments as a guide.
Decision: Accept (spotlight)