$\max(\mathcal{W}(P,A({\bf x})),\mathcal{W}(Q^{\prime\prime},A({\bf
x}^{\prime})))\geq\frac{1}{4C\varepsilon n}\left(q_{1-\frac{1}{C\varepsilon
n}}-q_{\frac{1}{C\varepsilon
n}}\right)+\frac{1}{4}\mathcal{W}(P,P|_{q_{\frac{1}{C\varepsilon
n}},q_{1-\frac{1}{C\varepsilon n}}}).$

We start with some notation. For any distribution $P$ with a density, let
$f_{P}$ denote its density function. Throughout this section, we will use
$q_{\alpha}$ to represent the $\alpha$-quantile of distribution $P$. Let
$L(P)$ be the ‘starting point’ of distribution $P$ (defined as
$\inf_{t\in\mathbb{R}}\\{t:F_{P}(t)>0\\}$ if the infimum exists, and $-\infty$
otherwise.

Next, we describe some results on differentially private testing that we will
use. We say that a testing algorithm $A_{test}$ distinguishes two
distributions $P$ and $Q$ with $n$ samples, if given the promise that a
dataset of size $n$ is drawn from either $P^{n}$ or $Q^{n}$, with probability
at least $\frac{2}{3}$, it outputs $P$ if the dataset was drawn from $P^{n}$
and $Q$ if it was drawn from $Q^{n}$. We now state a theorem lower bounding
the sample complexity of differentially private hypothesis testing.

######  Theorem 6.5 ([CKM+19, Theorem 1.2]).

Fix $n\in\mathbb{N},\varepsilon>0$. For every pair of distributions $P,Q$ over
$\mathbb{R}$, if there exists an $\varepsilon$-DP testing algorithm444The same
bounds (and hence all our results in this subsection) can be extended to
$(\varepsilon,\delta)$-DP (with $\delta\leq\varepsilon$) by using an
equivalence of pure and approximate DP for identity and closeness testing
[ASZ17, Lemma 5]. $A_{test}$ that distinguishes $P$ and $Q$ with $n$ samples,
then

$n=\Omega\left(\frac{1}{\varepsilon\tau(P,Q)+(1-\tau(P,Q))H^{2}(P^{\prime},Q^{\prime})}\right),$

where

$\tau(P,Q)=\max\Big{\\{}\int_{\mathbb{R}}\max\\{e^{\varepsilon}f_{P}(t)-f_{Q}(t),0\\}dt,\int_{\mathbb{R}}\max\\{e^{\varepsilon}f_{Q}(t)-f_{P}(t),0\\}dt\Big{\\}},$

and $H^{2}(\cdot,\cdot)$ is the squared Hellinger distance between
$P^{\prime}=\frac{\min(e^{\varepsilon}Q,P)}{1-\tau(P,Q)}$, and
$Q^{\prime}=\frac{\min(e^{\varepsilon^{\prime}}P,Q)}{1-\tau(P,Q)}$, where
$0\leq\varepsilon^{\prime}\leq\varepsilon$ is such that if
$\tau(P,Q)=\int_{\mathbb{R}}\max\\{f_{P}(t)-e^{\varepsilon}f_{Q}(t),0\\}dt$,
then $\varepsilon^{\prime}$ is the maximum value such that

$\tau(P,Q)=\int_{\mathbb{R}}\max\\{f_{Q}(t)-e^{\varepsilon^{\prime}}f_{P}(t),0\\}dt,$

else $\varepsilon^{\prime}$ is the maximum value such that

$\tau(P,Q)=\int_{\mathbb{R}}\max\\{f_{P}(t)-e^{\varepsilon^{\prime}}f_{Q}(t),0\\}dt.$

We now are ready to start proving our main theorem.

###### Proof.

(of Theorem 6.4) The idea is to construct $Q$ from $P$ by moving mass from the
leftmost quantiles to the rightmost quantile. We do this such that $Q$ is
statistically close enough to $P$ such that the two distributions can not be
distinguished with $n$ samples, but is also far from $P$ in Wasserstein
distance. This produces a lower bound of $(1/2)\mathcal{W}(P,Q)$ on how well
an algorithm can simultaneously estimate $P$ and $Q$ since if there was an
algorithm that produced good estimates of $P$ and $Q$ in Wasserstein distance
with $n$ samples, then we could tell them apart, and this would give a
contradiction.

Let $k$ be a quantity to be set later. Formally, we define $Q$ as the
distribution with the following density function.

$f_{Q}(t)=\left\\{\begin{array}[]{lr}\frac{1}{2}f_{P}(t),&\text{for
}t<q_{1/k}\\\ f_{P}(t),&\text{for }q_{1/k}\leq t<q_{1-\frac{1}{k}}\\\
\frac{3}{2}f_{P}(t)&\text{for }q_{1-\frac{1}{k}}\leq t\end{array}\right\\}$

Note that by the definition of $Q$, we have that $D_{\infty}(P,Q)\leq 2$.

We will prove that the sample complexity of telling apart $P$ and $Q$ under
$(\varepsilon,\delta)$-DP is $\Omega(k/\varepsilon)$, using known results on
hypothesis testing. Then, we will argue that the Wasserstein distance between
$P$ and $Q$ is sufficiently large. Setting $k$ appropriately will complete the
proof.

Define $SC_{\varepsilon,\delta}(P,Q)$ to be the smallest $n$ such that there
exists an $(\varepsilon,\delta)$-DP testing algorithm that distinguishes $P$
and $Q$; called the _sample complexity_ of privately distinguishing $P$ and
$Q$.

######  Lemma 6.6.

$SC_{\varepsilon,\delta}(P,Q)=\Omega(k/\varepsilon).$

The proof of this lemma is in Appendix F. We next argue that $P$ and $Q$ are
sufficiently far away in Wasserstein distance.

######  Lemma 6.7.

$\mathcal{W}(P,Q)\geq\frac{1}{2k}(q_{1-\frac{1}{k}}-q_{1/k})+\frac{1}{2}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$.

The proof of this lemma is also in Appendix F.

Finally, we are ready to prove the theorem. Assume that with probability
larger than $0.75$ over the draw of two datasets ${\bf x}\sim P^{n}$, ${\bf
x}^{\prime}\sim Q^{n}$, and the randomness used by invocations of algorithm
$A$ we have that $\max(\mathcal{W}(P,A({\bf x})),\mathcal{W}(Q,A({\bf
x}^{\prime}))<\frac{1}{2}\mathcal{W}(P,Q)$. Then, given a dataset ${\bf
x}^{\prime\prime}$ of size $n$, we can perform the following test: run the
differentially private algorithm $A$ on the dataset ${\bf x}^{\prime\prime}$
and compute $\mathcal{W}(P,A({\bf x}^{\prime\prime}))$ and
$\mathcal{W}(Q,A({\bf x}^{\prime\prime}))$ and output the distribution with
lower distance. Then, note that $\mathcal{W}(P,Q)\leq\mathcal{W}(P,A({\bf
x}^{\prime\prime}))+\mathcal{W}(Q,A({\bf x}^{\prime\prime}))$ which implies
that with probability at least $0.75$, $\mathcal{W}(Q,A({\bf
x}^{\prime\prime}))>\frac{1}{2}\mathcal{W}(P,Q)$ if the dataset ${\bf
x}^{\prime\prime}$ was sampled from $P^{n}$ (by the accuracy guarantee). A
similar argument shows that with probability at least $0.75$,
$\mathcal{W}(P,A({\bf x}^{\prime\prime}))>\frac{1}{2}\mathcal{W}(P,Q)$ if the
dataset ${\bf x}^{\prime\prime}$ was sampled from $Q^{n}$. Hence, with $n$
samples we have defined a test that distinguishes $P$ and $Q$. However, for
$k=C\varepsilon n$ for some constant $C$, by Lemma 6.6 we get that any
differentially private test distinguishing $P$ and $Q$ requires more than $n$
samples, which is a contradiction. Hence, with probability at least $0.25$
over the draw of two datasets ${\bf x}\sim P^{n}$, ${\bf x}^{\prime}\sim
Q^{n}$, and the randomness used by invocations of algorithm $A$ we have that
$\max(\mathcal{W}(P,A({\bf x})),\mathcal{W}(Q,A({\bf
x}^{\prime}))\geq\frac{1}{2}\mathcal{W}(P,Q)\geq\frac{1}{4C\varepsilon
n}(q_{1-\frac{1}{C\varepsilon n}}-q_{1/C\varepsilon
n})+\frac{1}{4}\mathcal{W}(P,P|_{q_{\frac{1}{C\varepsilon
n}},q_{1-\frac{1}{C\varepsilon n}}})$ ,where the last inequality is by
invoking Lemma 6.7 with $k=C\varepsilon n$.

∎

####  6.1.2 Empirical Term

In this section, we prove the following result.

######  Theorem 6.8.

Fix sufficiently large natural numbers $n,k>0$ and let $C,C^{\prime}>0$ be
sufficiently small constants. For all algorithms
$A:\mathbb{R}^{n}\to\Delta_{\mathbb{R}}$, the following holds. For all
continuous distributions $P$ over $\mathbb{R}$ with a density and with bounded
expectation, there exists another distribution $Q$ (with
$D_{\infty}(P,Q)\leq\ln 2$), that is indistinguishable from $P$ given $O(n)$
samples, such that with probability at least $0.25$ over the draws ${\bf
x}\sim P^{n}$, ${\bf x}^{\prime}\sim Q^{n}$, the following holds.

$\max(\mathcal{W}(P,A({\bf x})),\mathcal{W}(Q,A({\bf
x}^{\prime})))\geq\frac{C^{\prime}}{\sqrt{\log n}}\mathbb{E}_{{\bf
x}^{\prime\prime}\sim
P^{n}}\left[\mathcal{W}\left(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}\right)\right],$

where $q_{\alpha}$ is the $\alpha$-quantile of $P$.

Before going into the proof, we state the following result on the sample
complexity of testing. This is a folklore result but for a proof of the lower
bound see [BY02] and the upper bound see [Can17].

######  Theorem 6.9.

Fix $n\in\mathbb{N},\varepsilon>0$. For every pair of distributions $P,Q$ over
$\mathbb{R}$, if there exists a testing algorithm $A_{test}$ that
distinguishes $P$ and $Q$ with $n$ samples, then

$n=\Omega\left(\frac{1}{H^{2}(P,Q)}\right),$

wherer $H^{2}(\cdot,\cdot)$ represents the squared Hellinger distance between
$P$ and $Q$.

Throughout the proof, we will use $q_{\alpha}$ to represent the
$\alpha$-quantile of distribution $P$.

###### Proof of Theorem 6.8.

$Q$ is constructed by adding progressively more mass to $P$ up until $q_{1/2}$
and subtracting proportionate amounts of mass from $P$ afterwards.
Intuitively, this is done in such a way that to ‘change’ $P$ to $Q$, for all
$i\geq 2$ one has to move roughly
$\min\\{\frac{1}{\sqrt{2^{i}n}},\frac{1}{2^{i}}\\}$ mass from $q_{1/2^{i}}$ to
$q_{1-1/2^{i}}$. This ensures that the Wasserstein distance between $P$ and
$Q$ is larger than the expected Wasserstein distance between $P$ and its
empirical distribution on $n$ samples $\hat{P}_{n}$. This is carefully done to
ensure that $P$ is indistinguishable from $Q$.

Formally, consider $i$ in the range $[2,\log n-1)$. For all
$x\in(q_{1/2^{i}},q_{1/2^{i-1}}]$, we set
$f_{Q}(t)=f_{P}(t)\left[1+\sqrt{\frac{2^{i}}{n}}\right]$. For all
$t\in(q_{1-1/2^{i-1}},q_{1-1/2^{i}}]$, we set
$f_{Q}(t)=f_{P}(t)\left[1-\sqrt{\frac{2^{i}}{n}}\right]$. Next, consider $i$
in the range $[\log n,\infty)$. For all $t\in(q_{1/2^{i}},q_{1/2^{i-1}}]$, we
set $f_{Q}(t)=f_{P}(t)\left[1+\frac{1}{2}\right]$. For all
$t\in(q_{1-1/2^{i-1}},q_{1-1/2^{i}}]$, we set
$f_{Q}(t)=f_{P}(t)\left[1-\frac{1}{2}\right]$. Note that $P$ has bounded
expectation by assumption, and hence, so does $Q$. Additionally, note that
$D_{\infty}(P,Q)\leq\ln 2$.

There are two key considerations balanced in the design of $Q$. On one hand,
we need $Q$ to be indistinguishable from $P$ given $\tilde{O}(n)$ samples. On
the other hand, we need $Q$ to be sufficiently far away from $P$ in
Wasserstein distance. This ensures that given an accurate algorithm for
estimating the density of the distribution (in Wasserstein distance) given
access to $\tilde{O}(n)$ samples from it, we can design a test distinguishing
$P$ and $Q$ with that many samples, thereby contradicting their
indistinguishability.

Detailed proofs of claims below can be found in Appendix F. First, we show
that $P$ is indistinguishable from $Q$.

######  Lemma 6.10.

$KL(P,Q)=O(\log n/n).$

Next, we establish a lower bound on the Wasserstein distance between $P$ and
$Q$.

######  Lemma 6.11.

$\mathcal{W}(P,Q)\geq\frac{1}{4}\left[\sum_{j=2}^{\log
n-1}\frac{1}{\sqrt{2^{j}n}}\left[q_{1-1/2^{j}}-q_{1/2^{j}}\right]+\sum_{j=\log
n}^{\infty}\frac{1}{2^{j}}\left[q_{1-1/2^{j}}-q_{1/2^{j}}\right]\right].$

Next, we upper bound the expected Wasserstein distance between the
distribution $P$ and its empirical distribution on $n$ samples.

######  Lemma 6.12.

$\mathbb{E}[\mathcal{W}(P,\hat{P}_{n})]\leq 8\left[\sum_{i=2}^{\log
n-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\right]$

We now prove a simple claim regarding restrictions.

######  Claim 6.13 (Restrictions preserve Wasserstein distance).

For all datasets ${\bf x}$, and any natural number $k>1$ we have that

$\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})\leq\mathcal{W}(P,\hat{P}_{n}).$

Finally, we are ready to put the above lemmas together to prove Theorem 6.8.
Fix $n^{\prime}=\frac{n}{C\log n}$. Assume, for sake of contradiction, that
with probability larger than $0.75$ over the draw of two datasets ${\bf x}\sim
P^{n^{\prime}}$, ${\bf x}^{\prime}\sim Q^{n^{\prime}}$, and the randomness
used by invocations of algorithm $A$ we have that $\max(\mathcal{W}(P,A({\bf
x})),\mathcal{W}(Q,A({\bf x}^{\prime}))\leq\frac{1}{2}W_{1}(P,Q)$. Then, given
a dataset ${\bf x^{\prime\prime}}$ of size $n^{\prime}$, we perform the
following test: run the differentially private algorithm $A$ on the dataset
${\bf x}^{\prime\prime}$ and compute $\mathcal{W}(P,A({\bf
x}^{\prime\prime}))$ and $\mathcal{W}(Q,A({\bf x}^{\prime\prime}))$ and output
the distribution with lower distance. Then, note that
$\mathcal{W}(P,Q)\leq\mathcal{W}(P,A({\bf
x}^{\prime\prime}))+\mathcal{W}(Q,A({\bf x}^{\prime\prime}))$ which implies
that with probability at least $0.75$, $\mathcal{W}(Q,A({\bf
x}^{\prime\prime}))\geq\frac{1}{2}\mathcal{W}(P,Q)$ if ${\bf
x}^{\prime\prime}\sim P^{n^{\prime}}$ (by the accuracy guarantee). A similar
argument shows that with probability at least $0.75$, $\mathcal{W}(P,A({\bf
x}^{\prime\prime}))\geq\frac{1}{2}\mathcal{W}(P,Q)$ if ${\bf
x}^{\prime\prime}\sim Q^{n^{\prime}}$. Hence, with $n^{\prime}$ samples we
have defined a test that distinguishes $P$ and $Q$. However, by Lemma 6.10
bounding the $KL$ divergence between $P$ and $Q$, Theorem 6.9 on sample
complexity lower bounds for testing, and Lemma A.4 on the relationship between
KL and Hellinger distance, we get that any statistical test distinguishing $P$
and $Q$ requires more than $n^{\prime}$ samples, which is a contradiction.
Hence, with probability at least $0.25$ over the draw of two datasets ${\bf
x}\sim P^{n^{\prime}}$, ${\bf x}^{\prime}\sim Q^{n^{\prime}}$, and the
randomness used by invocations of algorithm $A$ we must have that

$\max(\mathcal{W}(P,A({\bf x})),\mathcal{W}(Q,A({\bf
x^{\prime}}))\geq\frac{1}{2}\mathcal{W}(P,Q).$ (9)

Next, note that by Lemma 6.12 (with value $n^{\prime}$), we have that

$\displaystyle\mathbb{E}[\mathcal{W}(P,\hat{P}_{n^{\prime}})]$
$\displaystyle\leq 8\left[\sum_{i=2}^{\log
n^{\prime}-1}\frac{1}{\sqrt{2^{i}n^{\prime}}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n^{\prime}}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\right]$
$\displaystyle=8\left[\sum_{i=2}^{\log\frac{n}{C\log n}-1}\frac{\sqrt{C\log
n}}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log\frac{n}{C\log
n}}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\right]$
$\displaystyle=8\Bigg{[}\sqrt{C\log n}\sum_{i=2}^{\log n-\log(C\log
n)-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n-\log(C\log n)}^{\log
n-1}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$
$\displaystyle+\sum_{i=\log
n}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\Bigg{]}$

Analyzing the middle term in the above sum, we have that

$\displaystyle\sum_{i=\log n-\log(C\log n)}^{\log
n-1}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$
$\displaystyle\leq\sum_{i=\log n-\log(C\log n)}^{\log
n-1}\frac{1}{\sqrt{2^{i}}}\frac{1}{\sqrt{2^{\log n-\log(C\log
n)}}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$ $\displaystyle\leq\sum_{i=\log
n-\log(C\log n)}^{\log n-1}\frac{1}{\sqrt{2^{i}}}\frac{\sqrt{C\log
n}}{\sqrt{n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$
$\displaystyle=\sqrt{C\log n}\sum_{i=\log n-\log(C\log n)}^{\log
n-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$

Substituting this back in the previous sum, we have that

$\displaystyle\mathbb{E}[\mathcal{W}(P,\hat{P}_{n^{\prime}})]$
$\displaystyle\leq 8\Bigg{[}\sqrt{C\log n}\sum_{i=2}^{\log n-\log(C\log
n)-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$
$\displaystyle\hskip 36.135pt+\sqrt{C\log n}\sum_{i=\log n-\log(C\log
n)}^{\log
n-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\Bigg{]}$
$\displaystyle\leq 8\sqrt{C\log n}\Bigg{[}\sum_{i=2}^{\log
n-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\Bigg{]}$
$\displaystyle\leq 16\sqrt{C\log n^{\prime}}\Bigg{[}\sum_{i=2}^{\log
n-1}\frac{1}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n}^{\infty}\frac{1}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]\Bigg{]}$

where in the last inequality we use the fact that $n^{\prime}\geq\sqrt{n}$.
Hence, by Lemma 6.11 (which gives a lower bound on $\mathcal{W}(P,Q)$) in
conjunction with the above equation, we have that
$\mathcal{W}(P,Q)\geq\frac{C^{\prime}}{\sqrt{\log
n^{\prime}}}\mathbb{E}[P,\hat{P}_{n^{\prime}}]$ for some sufficiently small
constant $C^{\prime}$. Substituting back in Equation 9, we have that with
probability at least $0.25$ over the draw of two datasets ${\bf x}\sim
P^{n^{\prime}}$, ${\bf x}^{\prime}\sim Q^{n^{\prime}}$, and the randomness
used by invocations of algorithm $A$ we have that

$\max(\mathcal{W}(P,A({\bf x})),\mathcal{W}(Q,A({\bf
x^{\prime}}))\geq\frac{1}{2}\frac{C^{\prime}}{\sqrt{\log
n^{\prime}}}\mathbb{E}[\mathcal{W}(P,\hat{P}_{n^{\prime}})]\geq\frac{1}{2}\frac{C^{\prime}}{\sqrt{\log
n^{\prime}}}\mathbb{E}\left[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n^{\prime}}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})\right],$

as required.

∎

###  6.2 Upper Bound

In this section, we describe an algorithm that achieves the instance optimal
rate described in the previous section (up to polylogarithmic factors in some
of the terms).

We will be looking at distributions $P$ supported on a discrete, ordered
interval $\\{a,a+\gamma,\dots,b-\gamma,b\\}$. Note that by a simple coupling
argument, any continuous distribution $P^{cont}$ on $[a,b]$ is at most
$\gamma$ away in Wasserstein distance from a distribution on this grid. The
dependence on $\gamma$ in our bounds for discrete distributions will be
inverse polylogarithmic (or better), and so our algorithms for estimating
distributions $P$ in the interval $\\{a,a+\gamma,\dots,b-\gamma,b\\}$ also
work to give similar bounds for continuous distributions on $[a,b]$, up to a
small additive factor of $\gamma$, which can be set to any inverse polynomial
in the dataset size without significantly affecting our bounds.

Formally, we will prove the following theorem (See Theorem 6.15 for a more
detailed statement).

######  Theorem 6.14.

Fix $\varepsilon,\beta\in(0,1]$, $a,b\in\mathbb{R}$, and
$\gamma<b-a\in\mathbb{R}$ such that $\frac{b-a}{\gamma}$ is an integer. Let
$n\in\mathbb{N}>c_{2}\frac{\log^{4}\frac{b-a}{\beta\gamma}}{\varepsilon}$ for
some sufficiently large constant $c_{2}$. There exists an algorithm $A$ that
for any distribution $P$ on $\\{a,a+\gamma,a+2\gamma,\dots,b-\gamma,b\\}$
satisfies the following. When run with input a random sample ${\bf x}\sim
P^{n}$, $A$ outputs a distribution $P^{DP}$ such that with probability at
least $1-\beta$ over the randomness of ${\bf x}$ and the algorithm,

$\mathcal{W}(P,P^{DP})=O\left(\frac{1}{k}\left(q_{1-\frac{1}{k}}-q_{\frac{1}{k}}\right)+\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+\sqrt{\log\frac{n}{\beta}}\mathbb{E}\left[\mathcal{W}\left(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}\right)\right]\right),$

where $\hat{P}_{n}$ is the empirical distribution on $n$ samples drawn
independently from $P$, $q_{\alpha}$ represents the $\alpha$-quantile of
distribution $P$, and $k=\lceil\frac{\varepsilon
n}{4c_{3}\log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}\rceil$ for a
sufficiently large constant $c_{3}$.

Since $k\approx\varepsilon n/\log(n)$, this upper bound matches the lower
bound in Theorem 6.3 in its dependence on $\varepsilon$ and its dependence on
$n$ (up to logarithmic factors in $n$). The algorithm that we will analyze
proceeds by estimating sufficiently many quantiles from the empirical
distribution and distributing mass evenly between the chosen quantiles. The
number of quantiles is chosen carefully to ensure that the estimated
$\alpha$-quantiles are also approximately $\alpha$-quantiles for the empirical
distribution (and hence also approximately for the true distribution), and to
ensure that the CDF of the output distribution closely tracks the CDF of the
empirical distribution. Through a careful analysis, we are able to leverage
these properties to give instance optimality guarantees for the accuracy of
the algorithm.

####  6.2.1 Algorithm for density estimation

Algorithm 5 is our algorithm for density estimation, and proceeds by
differentially privately estimating sufficiently many quantiles of the
distribution and placing equal mass on each of them. We argue that a simple
CDF based differentially private quantiles estimator $A_{quant}$ satisfies a
specific guarantee that will be key to our analysis. See Appendix E for more
details about the quantiles algorithm and formal statements and proofs
therein.

Algorithm 5 Algorithm $A$ for estimating a distribution on $\mathbb{R}$

1:Input: ${\bf x}=(x_{1},\dots,x_{n})\sim P^{n}$, privacy parameter
$\varepsilon$, interval end-points $a,b$, granularity $\gamma$, access to
algorithm $A_{quant}$

2:Output: Distribution $P^{DP}$ on $\mathbb{R}$.

3:Let $k$ be set to $\lceil\frac{\varepsilon
n}{4c_{3}\log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}\rceil$ for a
sufficiently large constant $c_{3}$.

4:Use Algorithm $A_{quant}$ referenced in Theorem E.2 with inputs interval end
points $a,b$, granularity $\gamma$, ${\bf
x}=(x_{1},\dots,x_{n})\in\\{a,a+\gamma,\dots,b-\gamma,b\\}^{n}$, and desired
quantile values ${\bf\alpha}=\\{1/2k,3/2k,5/2k,\dots,(2k-1)/2k\\}$, and let
the outputs be $\tilde{q}_{1}\dots,\tilde{q}_{k}$.

5:for $j\in[k]$ do

6: Set $P^{DP}(\tilde{q}_{j})=\frac{1}{k}$.

7:Output $P^{DP}$.

Observe that Algorithm 5 inherits the privacy of $A_{quant}$, since it simply
postprocesses the quantiles it receives from that subroutine, and hence is
also $\varepsilon$-DP.

Now, we are in a position to state our main theorem, which bounds the
Wasserstein distance between the distribution output by our algorithm, and the
underlying probability distribution $P$.

######  Theorem 6.15.

Fix $\varepsilon,\beta\in(0,1]$, $a,b\in\mathbb{R}$, and
$\gamma<b-a\in\mathbb{R}$ such that $\frac{b-a}{\gamma}$ is an integer. Let
$n\in\mathbb{N}>c_{2}\frac{\log^{4}\frac{b-a}{\gamma\beta\varepsilon}}{\varepsilon}$
for some sufficiently large constant $c_{2}$. Let $P$ be any distribution
supported on $\\{a,a+\gamma,a+2\gamma,\dots,b-\gamma,b\\}$, and ${\bf x}\sim
P^{n}$.

Then, Algorithm 5, when given inputs ${\bf x}$, privacy parameter
$\varepsilon$, interval end points $a,b$, and granularity $\gamma$, outputs a
distribution $P^{DP}$ such that with probability at least $1-O(\beta)$ over
the randomness of ${\bf x}$ and the algorithm,

$\mathcal{W}(P,P^{DP})\leq\sqrt{c\log
n}\cdot\mathbb{E}\left[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}\right]+C^{\prime\prime}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+\frac{2}{k}\left(q_{1-1/k}-q_{1/k}\right),$

where $\hat{P}_{n}$ is the uniform distribution on ${\bf x}$, $q_{\alpha}$
represents the $\alpha$-quantile of distribution $P$, $c,C^{\prime\prime}$ are
sufficiently large constants, and $k=\lceil\frac{\varepsilon
n}{4c_{3}\log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}\rceil$, where
$c_{3}$ is a sufficiently large constant.

We note that using more sophisticated differentially private CDF estimators to
estimate quantiles (such as ones in [BNSV15, CLN+23]), we can also obtain a
version of the same theorem for approximate differential privacy, with a
better dependence on the size of the domain $\frac{b-a}{\gamma}$ (only
$\log^{*}(\frac{b-a}{\gamma})$ as opposed to $poly\log(\frac{b-a}{\gamma})$,
where $\log^{*}t$ is the number of times $\log$ has to be applied to $t$ to
get it to be $\leq 1$). 555The theorem would be of the same form as Theorem
6.15, except that Algorithm 5 would be $(\varepsilon,\delta)$-DP, with the
lower bound on $n$ instead being
$n=\Omega\left(\frac{\operatorname{polylog}^{*}\frac{b-a}{\gamma\varepsilon\delta}\sqrt{\log
1/\delta}\log(1/\beta)}{\varepsilon}\right)$, and $k$ being set instead to
$O\left(\frac{\varepsilon
n}{\log^{*}\frac{b-a}{\gamma}\operatorname{polylog}\frac{n}{\beta}}\right)$.

To prove Theorem 6.15, we first relate the Wasserstein distance of interest
(between the true distribution $P$ and the algorithm’s output distribution
$P^{DP}$ to a quantity related to an appropriately chosen restriction. Let
$q_{\alpha}$ represent the $\alpha$-quantile of $P$ and $\hat{q}_{\alpha}$
represent the $\alpha$-quantile of $\hat{P}_{n}$ and $\tilde{q}_{\alpha}$
represent the $\alpha$-quantiles of $P^{DP}$. We also note that all these
distributions (and others that will come up in the proof) are bounded
distributions over the real line and so we can freely apply the triangle
inequality for Wasserstein distance, and the cumulative distribution formula
for Wasserstein distance (Lemma 2.3). The proof of the main theorem will
follow from the following lemmas (all proved in Appendix F).

######  Lemma 6.16.

Let $C^{\prime\prime}>0$ be a sufficiently large constant, and let $n>0$ be
sufficiently large. With probability at least $1-O(\beta)$ over the randomness
in data samples and Algorithm 5,

$\mathcal{W}(P,P^{DP})\leq\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+C^{\prime\prime}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}).$

######  Lemma 6.17 (Wasserstein in terms of quantiles).

For all datasets ${\bf x}$ (with data entries in $[a,b]$), with probability at
least $1-\beta$ over the randomness of Algorithm 5, we have that

$\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})\leq\frac{2}{k}\left(q_{1-1/k}-q_{1/k}\right),$

where $\hat{P}_{n}$ is the uniform distribution over ${\bf x}$.

Now, we argue about the concentration of the Wasserstein distance between
restrictions of the empirical distribution and restrictions of the true
distribution.

######  Claim 6.18.

Fix $\beta\in(0,1)$ and sufficiently large constants $c_{3},c_{6}$. Let $n>0$
be sufficiently large such that $n>\log n/\beta$ (as in Theorem 6.15). For all
$k$ such that $\frac{1}{k}>c_{3}\frac{\log\frac{n}{\beta}}{n}$, with
probability at least $1-O(\beta)$ over the randomness in the data,

$\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})\leq\sqrt{c_{6}\log\
\frac{n}{\beta}}\cdot\mathbb{E}[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})].$

Now, we give the proof of our main theorem.

###### Theorem 6.15.

Using Lemma 6.16, Claim 6.18 and the triangle inequality, we have that with
probability at least $1-O(\beta)$ over the randomness of the data and the
algorithm,

$\displaystyle\mathcal{W}(P,P^{DP})$
$\displaystyle\leq\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+C^{\prime\prime}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$
$\displaystyle\leq\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+C^{\prime\prime}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$
$\displaystyle\leq\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+\sqrt{c_{6}\log\frac{n}{\beta}}\mathbb{E}\left[\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})\right]+C^{\prime\prime}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$

Finally, applying Lemma 6.17 and taking a union bound over failure
probabilities, we get that with probability at least $1-O(\beta)$ over the
randomness of the data and the algorithm,

$\displaystyle\mathcal{W}(P,P^{DP})$
$\displaystyle\leq\frac{2}{k}\left(q_{1-1/k}-q_{1/k}\right)+\sqrt{c_{6}\log\frac{n}{\beta}}\mathbb{E}\left[\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})\right]+C^{\prime\prime}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$

as required. ∎

## References

  * [AAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath.  On the sample complexity of privately learning unbounded high-dimensional gaussians.  In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 185–216. PMLR, 2021.
  * [AAL23a] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw.  Mixtures of gaussians are privately learnable with a polynomial number of samples.  CoRR, abs/2309.03847, 2023.
  * [AAL23b] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw.  Polynomial time and private learning of unbounded gaussian mixture models.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 1018–1040. PMLR, 2023.
  * [ABC17] Peyman Afshani, Jérémy Barbay, and Timothy M. Chan.  Instance-optimal geometric algorithms.  J. ACM, 64(1), mar 2017.
  * [AD20] Hilal Asi and John C. Duchi.  Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [ADJ+11] Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, and Shengjun Pan.  Competitive closeness testing.  In Sham M. Kakade and Ulrike von Luxburg, editors, COLT 2011 - The 24th Annual Conference on Learning Theory, June 9-11, 2011, Budapest, Hungary, volume 19 of JMLR Proceedings, pages 47–68. JMLR.org, 2011\.
  * [ADJ+12] Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, and Ananda Theertha Suresh.  Competitive classification and closeness testing.  In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 22.1–22.18. JMLR.org, 2012.
  * [AJOS13a] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh.  A competitive test for uniformity of monotone distributions.  In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2013, Scottsdale, AZ, USA, April 29 - May 1, 2013, volume 31 of JMLR Workshop and Conference Proceedings, pages 57–65. JMLR.org, 2013.
  * [AJOS13b] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh.  Optimal probability estimation with applications to prediction and classification.  In Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 764–796. JMLR.org, 2013.
  * [AKT+23] Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang.  Privately estimating a gaussian: Efficient, robust, and optimal.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 483–496. ACM, 2023.
  * [AL22] Hassan Ashtiani and Christopher Liaw.  Private and polynomial time algorithms for learning gaussians and beyond.  In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1075–1076. PMLR, 2022.
  * [ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran.  Private PAC learning implies finite littlestone dimension.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852–860. ACM, 2019.
  * [ASSU24] Maryam Aliakbarpour, Rose Silver, Thomas Steinke, and Jonathan R. Ullman.  Differentially private medians and interior points for non-pathological data.  In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPIcs, pages 3:1–3:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
  * [ASZ17] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Differentially private testing of identity and closeness of discrete distributions.  CoRR, abs/1707.05128, 2017.
  * [ASZ20] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Differentially private assouad, fano, and le cam.  CoRR, abs/2004.06830, 2020.
  * [ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Differentially private Assouad, Fano, and Le Cam.  In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 48–78. PMLR, 16–19 Mar 2021.
  * [BA20] Victor-Emmanuel Brunel and Marco Avella-Medina.  Propose, test, release: Differentially private estimation with high probability.  CoRR, abs/2002.08774, 2020.
  * [Bar96] Yair Bartal.  Probabilistic approximations of metric spaces and its algorithmic applications.  In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193. IEEE Computer Society, 1996.
  * [BBDS13] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet.  Differentially private data analysis of social networks via restricted sensitivity.  In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 87–96. ACM, 2013.
  * [BG14] Emmanuel Boissard and Thibaut Le Gouic.  On the mean speed of convergence of empirical and occupation measures in Wasserstein distance.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 50(2):539 – 563, 2014.
  * [BGS+21] Gavin Brown, Marco Gaboardi, Adam D. Smith, Jonathan R. Ullman, and Lydia Zakynthinou.  Covariance-aware private mean estimation without private covariance estimation.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 7950–7964, 2021.
  * [BHS23] Gavin Brown, Samuel B. Hopkins, and Adam Smith.  Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions, 2023.
  * [BKM+21] Eugene Bagdasaryan, Peter Kairouz, Stefan Mellem, Adrià Gascón, Kallista Bonawitz, Deborah Estrin, and Marco Gruteser.  Towards sparse federated analytics: Location heatmaps under distributed differential privacy with secure aggregation.  arXiv preprint arXiv:2111.02356, 2021.
  * [BKSW21] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu.  Private hypothesis selection.  IEEE Trans. Inf. Theory, 67(3):1981–2000, 2021.
  * [BL19] Sergey G. Bobkov and Michel Ledoux.  One-dimensional empirical measures, order statistics, and kantorovich transport distances.  Memoirs of the American Mathematical Society, 2019.
  * [BM23] Daniel Bartl and Shahar Mendelson.  On a variance dependent Dvoretzky-Kiefer-Wolfowitz inequality.  arXiv e-prints, page arXiv:2308.04757, August 2023.
  * [BNNR09] Khanh Do Ba, Huy L. Nguyen, Huy Ngoc Nguyen, and Ronitt Rubinfeld.  Sublinear time algorithms for earth mover’s distance.  Theory of Computing Systems, 48:428–442, 2009.
  * [BNS16] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Private learning and sanitization: Pure vs. approximate differential privacy.  Theory Comput., 12(1):1–61, 2016.
  * [BNSV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan.  Differentially private release and learning of threshold functions.  CoRR, abs/1504.07553, 2015.
  * [BS19] Mark Bun and Thomas Steinke.  Average-case averages: Private algorithms for smooth sensitivity and mean estimation.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 181–191, 2019.
  * [BSV22] March Boedihardjo, Thomas Strohmer, and Roman Vershynin.  Private measures, random walks, and synthetic data, 2022.
  * [BUV18] Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan.  Fingerprinting codes and the price of approximate differential privacy.  SIAM J. Comput., 47(5):1888–1938, 2018.
  * [BY02] Z. Bar-Yossef.  The Complexity of Massive Data Set Computations.  University of California, Berkeley, 2002.
  * [Can17] Clément L. Canonne.  A short note on distinguishing discrete distributions., 2017.
  * [CB22] Graham Cormode and Akash Bharadwaj.  Sample-and-threshold differential privacy: Histograms and applications.  In International Conference on Artificial Intelligence and Statistics, pages 1420–1431. PMLR, 2022.
  * [CCD+23] Karan Chadha, Junye Chen, John Duchi, Vitaly Feldman, Hanieh Hashemi, Omid Javidbakht, Audra McMillan, and Kunal Talwar.  Differentially private heavy hitter detection using federated analytics, 2023.
  * [CD20] Rachel Cummings and David Durfee.  Individual sensitivity preprocessing for data privacy.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 528–547. SIAM, 2020.
  * [CDK17] Bryan Cai, Constantinos Daskalakis, and Gautam Kamath.  Priv’it: Private and sample efficient identity testing.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 635–644. PMLR, 2017.
  * [CKM+19] Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, and Jonathan R. Ullman.  The structure of optimal private tests for simple hypotheses.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 310–321. ACM, 2019.
  * [CL15] T. Tony Cai and Mark G. Low.  A framework for estimation of convex functions.  Statistica Sinica, 25(2):423–456, 2015.
  * [CLN+23] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer.  Optimal differentially private learning of thresholds and quasi-concave optimization.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 472–482. ACM, 2023.
  * [CR12] Guillermo D. Cañas and Lorenzo Rosasco.  Learning probability measures with respect to optimal transport metrics.  In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 2501–2509, 2012.
  * [CSS11] T.-H. Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011.
  * [CWZ19] T. Tony Cai, Yichen Wang, and Linjun Zhang.  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  CoRR, abs/1902.04495, 2019.
  * [CZ13] Shixi Chen and Shuigeng Zhou.  Recursive mechanism: towards node differential privacy and unrestricted joins.  In Kenneth A. Ross, Divesh Srivastava, and Dimitris Papadias, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, pages 653–664. ACM, 2013.
  * [DHS15] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt.  Differentially private learning of structured discrete distributions.  In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2566–2574, 2015.
  * [DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT ’06, pages 486–503, St. Petersburg, Russia, 2006.
  * [DKSS23] Travis Dick, Alex Kulesza, Ziteng Sun, and Ananda Theertha Suresh.  Subset-based instance optimality in private estimation.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 7992–8014. PMLR, 2023.
  * [DL91] David L. Donoho and Richard C. Liu.  Geometrizing Rates of Convergence, II.  The Annals of Statistics, 19(2):633 – 667, 1991.
  * [DL09] Cynthia Dwork and Jing Lei.  Differential privacy and robust statistics.  In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 371–380. ACM, 2009.
  * [DLSV23] Trung Dang, Jasper C.H. Lee, Maoyuan Song, and Paul Valiant.  Optimality in mean estimation: Beyond worst-case, beyond sub-gaussian, and beyond $1+\alpha$ moments.  In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
  * [DMNS17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  Journal of Privacy and Confidentiality, 7(3):17–51, 2017.
  * [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum.  Differential privacy under continual observation.  In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 715–724. ACM, 2010.
  * [DR18] John C. Duchi and Feng Ruan.  The right complexity measure in locally private estimation: It is not the fisher information.  CoRR, abs/1806.05756, 2018.
  * [DSS11] Steffen Dereich, Michael Scheutzow, and Reik Schottstedt.  Constructive quantization: Approximation by empirical measures.  Annales De L Institut Henri Poincare-probabilites Et Statistiques, 49:1183–1203, 2011.
  * [Dud69] R. M. Dudley.  The speed of mean glivenko-cantelli convergence.  The Annals of Mathematical Statistics, 40(1):40–50, 1969.
  * [DY95] Vladimir Dobric and Joseph E. Yukich.  Asymptotics for transportation cost in high dimensions.  Journal of Theoretical Probability, 8:97–118, 1995.
  * [FG15] Nicolas Fournier and Arnaud Guillin.  On the rate of convergence in Wasserstein distance of the empirical measure.  Probability Theory and Related Fields, 162(3-4):707, August 2015\.
  * [FLN01] Ronald Fagin, Amnon Lotem, and Moni Naor.  Optimal aggregation algorithms for middleware.  In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’01, page 102–113, New York, NY, USA, 2001. Association for Computing Machinery.
  * [Fou23] Nicolas Fournier.  Convergence of the empirical measure in expected wasserstein distance: non asymptotic explicit bounds in $\mathbb{R}^{d}$, 2023.
  * [FRT03] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, page 448–455, New York, NY, USA, 2003. Association for Computing Machinery.
  * [GHK+23] Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, and Nachiappan Valliappan.  Differentially private heatmaps.  In Brian Williams, Yiling Chen, and Jennifer Neville, editors, Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 7696–7704. AAAI Press, 2023.
  * [GJK21] Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza.  Differentially private quantiles.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3713–3722. PMLR, 2021.
  * [GKN20] Tomer Grossman, Ilan Komargodski, and Moni Naor.  Instance Complexity and Unlabeled Certificates in the Decision Tree Model.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:38, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [HKM22] Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid.  Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 1406–1417. ACM, 2022.
  * [HKMN23] Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan.  Robustness implies privacy in statistical estimation.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 497–506. ACM, 2023.
  * [HLY21] Ziyue Huang, Yuting Liang, and Ke Yi.  Instance-optimal mean estimation under differential privacy.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 25993–26004, 2021.
  * [HO19] Yi Hao and Alon Orlitsky.  Doubly-competitive distribution estimation.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2614–2623. PMLR, 2019.
  * [HVZ23] Yiyun He, Roman Vershynin, and Yizhe Zhu.  Algorithmically effective differentially private synthetic data, 2023\.
  * [KDH23] Rohith Kuditipudi, John C. Duchi, and Saminul Haque.  A pretty fast algorithm for adaptive private mean estimation.  In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 2511–2551. PMLR, 2023.
  * [KLM+20] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer.  Privately learning thresholds: Closing the exponential gap.  In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2263–2285. PMLR, 2020.
  * [KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman.  Privately learning high-dimensional distributions.  In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1853–1902. PMLR, 2019\.
  * [KMS22a] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal.  New lower bounds for private estimation and a generalized fingerprinting lemma.  In NeurIPS, 2022.
  * [KMS+22b] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan R. Ullman.  A private and computationally-efficient estimator for unbounded gaussians.  In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 544–572. PMLR, 2022.
  * [KMV22] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker.  Private robust estimation by stabilizing convex relaxations.  In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 723–777. PMLR, 2022.
  * [KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  Analyzing graphs with node differential privacy.  In Amit Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 457–476. Springer, 2013.
  * [KSS22] Haim Kaplan, Shachar Schnapp, and Uri Stemmer.  Differentially private approximate quantiles.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 10751–10761. PMLR, 2022.
  * [KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan R. Ullman.  Differentially private algorithms for learning mixtures of separated gaussians.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 168–180, 2019.
  * [KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan R. Ullman.  Private mean estimation of heavy-tailed distributions.  In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2204–2235. PMLR, 2020.
  * [KU20] Gautam Kamath and Jonathan R. Ullman.  A primer on private statistics.  CoRR, abs/2005.00010, 2020.
  * [KV18] Vishesh Karwa and Salil P. Vadhan.  Finite sample differentially private confidence intervals.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 44:1–44:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [Lei20] Jing Lei.  Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces.  Bernoulli, 26(1):767 – 798, 2020.
  * [LKO22] Xiyang Liu, Weihao Kong, and Sewoong Oh.  Differential privacy and robust statistics in high dimensions.  In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1167–1246. PMLR, 2022.
  * [MJT+22] Audra McMillan, Omid Javidbakht, Kunal Talwar, Elliot Briggs, Mike Chatzidakis, Junye Chen, John Duchi, Vitaly Feldman, Yusuf Goren, Michael Hesse, Vojta Jina, Anil Katti, Albert Liu, Cheney Lyford, Joey Meyer, Alex Palmer, David Park, Wonhee Park, Gianni Parsa, Paul Pelzl, Rehan Rishi, Congzheng Song, Shan Wang, and Shundong Zhou.  Private federated statistics in an interactive setting.  arXiv preprint arXiv:2211.10082, 2022.
  * [MSU22] Audra McMillan, Adam D. Smith, and Jonathan R. Ullman.  Instance-optimal differentially private estimation.  CoRR, abs/2210.15819, 2022.
  * [Nar23] Shyam Narayanan.  Better and simpler lower bounds for differentially private statistical estimation.  CoRR, abs/2310.06289, 2023.
  * [NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  Smooth sensitivity and sampling in private data analysis.  In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75–84. ACM, 2007.
  * [NWB19] Jonathan Niles-Weed and Quentin Berthet.  Minimax estimation of smooth densities in wasserstein distance.  The Annals of Statistics, 2019.
  * [OS15] Alon Orlitsky and Ananda Theertha Suresh.  Competitive distribution estimation: Why is good-turing good.  In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2143–2151, 2015.
  * [QYL12] Wahbeh Qardaji, Weining Yang, and Ninghui Li.  Differentially private grids for geospatial data.  Proceedings - International Conference on Data Engineering, 09 2012\.
  * [Rou21] Tim Roughgarden.  Beyond the Worst-Case Analysis of Algorithms.  Cambridge University Press, 2021.
  * [RS16] Sofya Raskhodnikova and Adam D. Smith.  Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism.  In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 495–504. IEEE Computer Society, 2016.
  * [Sin23] Vikrant Singhal.  A polynomial time, pure differentially private estimator for binary product distributions.  CoRR, abs/2304.06787, 2023.
  * [SP19] Shashank Singh and Barnabás Póczos.  Minimax distribution estimation in wasserstein distance, 2019.
  * [TCK+22] Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer.  Friendlycore: Practical differentially private aggregation.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 21828–21863. PMLR, 2022.
  * [vdV97] A. W. van der Vaart.  Superefficiency, pages 397–410.  Springer New York, New York, NY, 1997.
  * [Vov09] Vladimir Vovk.  Superefficiency from the Vantage Point of Computability.  Statistical Science, 24(1):73 – 86, 2009.
  * [VV16] Gregory Valiant and Paul Valiant.  Instance optimal learning of discrete distributions.  In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 142–155. ACM, 2016.
  * [WB19] Jonathan Weed and Francis Bach.  Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance.  Bernoulli, 25(4 A):2620–2648, 2019.
  * [Wol65] J. Wolfowitz.  Asymptotic efficiency of the maximum likelihood estimator.  Theory of Probability & Its Applications, 10(2):247–260, 1965\.
  * [ZKM+20] Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li.  Federated heavy hitters discovery with differential privacy.  In International Conference on Artificial Intelligence and Statistics, pages 3837–3847. PMLR, 2020.
  * [ZXX16] Jun Zhang, Xiaokui Xiao, and Xing Xie.  Privtree: A differentially private algorithm for hierarchical decompositions.  In Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, page 155–170, New York, NY, USA, 2016. Association for Computing Machinery.

##  Appendix A Preliminaries

###  A.1 Distribution Distances

A number of other distances between distributions are used in this work.

######  Definition A.1 ($KL$-divergence).

Given two distributions $P$ and $Q$ with $supp(P)\subseteq supp(Q)$, the KL
divergence $KL(P,Q)=\sum_{t\in supp(P)}P(t)\ln\frac{P(t)}{Q(t)}$, if $P$ and
$Q$ are discrete, and
$KL(P,Q)=\int_{t\in\mathbb{R}:f_{P}(t)>0}f_{P}(t)\ln\frac{f_{P}(t)}{f_{Q}(t)}dt$
if $P$ and $Q$ are distributions on $\mathbb{R}$, and have density functions.
If $supp(P)\not\subseteq supp(Q)$, then $KL(P,Q)=\infty$.

######  Definition A.2 (Hellinger distance).

Given two distributions $P$ and $Q$, the Hellinger distance
$H(P,Q)=\frac{1}{\sqrt{2}}\|\sqrt{P}-\sqrt{Q}\|_{2}$ (where we think of $P$
and $Q$ as vectors representing the probability masses, and the square root
being component-wise.), if $P$ and $Q$ are discrete. If $P$ and $Q$ are
distributions on $\mathbb{R}$, and have density functions, then
$H(P,Q)=\frac{1}{\sqrt{2}}\sqrt{\int_{t\in\mathbb{R}:f_{P}(t)>0}(\sqrt{f_{P}(t)}-\sqrt{f_{Q}(t)})^{2}dt}$.

Note that we use $H^{2}(P,Q)$ to represent the squared Hellinger distance.
Next, we define total variation distance, which will come up in our high-
dimensional results.

######  Definition A.3 (Total Variation distance).

Given two discrete distributions $P$ and $Q$, the Total Variation distance
$TV(P,Q)=\frac{1}{2}\|P-Q\|_{1},$ (where we think of $P$ and $Q$ as vectors
representing the probability masses). More generally, for any two probability
measures $P$ and $Q$ defined on $(\Omega,\mathcal{F})$, the total variation
distance is defined as $\sup_{A\in\mathcal{F}}|P(A)-Q(A)|$ where $P(A)$
represents the probability of $A$ under measure $P$ and likewise for $Q$.

We use the following relationship between Hellinger distance and KL
divergence.

######  Lemma A.4.

For all distributions $P,Q$ such that KL-divergence of $P,Q$ is well defined,
we have that

$H^{2}(P,Q)\leq KL(P,Q),\hskip 5.69054ptH^{2}(P,Q)\leq TV(P,Q)$ (10)

###  A.2 Differential Privacy

######  Lemma A.5 (Post-Processing [DMNS17]).

If Algorithm $\mathcal{A}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is
$(\varepsilon,\delta)$-differentially private, and
$\mathcal{B}:\mathcal{Y}\rightarrow\mathcal{Z}$ is any randomized function,
then the algorithm $\mathcal{B}\circ\mathcal{A}$ is
$(\varepsilon,\delta)$-differentially private.

Secondly, differential privacy is robust to adaptive composition.

######  Lemma A.6 (Composition of $(\varepsilon,\delta)$-differential privacy
[DMNS17]).

If $\mathcal{A}$ is an adaptive composition of $m$ differentially private
algorithms $\mathcal{A}_{1},\ldots,\mathcal{A}_{m}$, where $\mathcal{A}_{j}$
is $(\varepsilon_{j},\delta_{j})$ differentially private, then $\mathcal{A}$
is $\left(\sum_{j}\varepsilon_{j},\sum_{j}\delta_{j}\right)$-differentially
private.

Finally, we discuss the Laplace mechanism, which we will use in one of our
algorithms.

######  Definition A.7 ($\ell_{1}$-Sensitivity).

The $\ell_{1}$-sensitivity of a function
$f:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$ is

$\Delta_{f}=\max_{\begin{subarray}{c}{\bf x},{\bf
x}^{\prime}\in\mathcal{X}^{n}\\\ d_{ham}({\bf x},{\bf x}^{\prime})\leq
1\end{subarray}}\|f({\bf x})-f({\bf x}^{\prime})\|_{1}.$

######  Lemma A.8 (Laplace Mechanism).

Let $f:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$ be a function with
$\ell_{1}$-sensitivity $\Delta_{f}$. Then the Laplacian mechanism is algorithm

$\mathcal{A}_{f}({\bf x})=f({\bf x})+(Z_{1},\ldots,Z_{d}),$

where $Z_{i}\sim Lap\left(\frac{\Delta_{f}}{\varepsilon}\right)$ (and
$Z_{1},\dots,Z_{d}$ are mutually independent). Algorithm $\mathcal{A}_{f}$ is
$\varepsilon$-DP.

##  Appendix B Experiment Details

Below we describe the experiment referenced in the introduction.

The distribution: We have taken a distribution on $[0,999]$, which is
concentrated on two points $430$ and $440$, with $p_{430}=\frac{1}{3}$ and
$p_{440}=\frac{2}{3}$. These algorithms have been run with $n=1600$ samples
from this distribution.

Minimax Optimal Algorithm: The minimax-optimal algorithm here is the algorithm
PSMM from [HVZ23] that considers a fixed partitioning of the interval into
$\Omega(m^{\frac{1}{d}})$ equal intervals and places the empirical mass in
each interval on an arbitrary point in each interval. Here we consider this
algorithm with $\varepsilon=\infty$, so that no noise is added. We have run it
here with $K=40$ buckets.

Instance-optimal Algorithm: The instance-optimal algorithm finds $k$ quantiles
as in Algorithm 5. In this particular implementation, we used the recursive
exponential mechanism of [KSS22], but we expect other quantile algorithms
would work similarly. In this particular case, we use $k=10$ quantiles with
$\varepsilon=1$.

##  Appendix C Appendix for Section 5

See 5.6

###### Proof of Theorem 5.6.

Given a distribution $P$, let

$\mathcal{A}^{*}_{P}=\arg\min_{\mathcal{A}\text{ is
}\varepsilon\text{-DP}}\max_{Q\in\mathcal{N}(P)}\mathbb{E}_{D\sim
P^{n}}[\mathcal{W}(P,\mathcal{A}(D))]$

so
$\mathcal{R}_{\mathcal{N},n,\varepsilon}(P)=\max_{Q\in\mathcal{N}(P)}\mathbb{E}_{D\sim
Q^{n}}[\mathcal{W}(P,\mathcal{A}^{*}_{P}(D))].$ Let $\ell\in[0pt]$. We want to
define an algorithm $\mathcal{A}^{*}_{P_{\ell}}$ on the distributions in
$\mathcal{N}_{\ell}(P_{\ell})$ that achieves maximum error rate
$\frac{1}{r_{\ell}}\mathcal{R}_{\mathcal{N},n,\varepsilon}(P)$. Define a
randomised function $g_{P}$ which given a node $\nu_{\ell}$ at level $\ell$,
$g_{P}(\nu_{\ell})$ is sampled from the distribution $P$ restricted to the
leaf nodes that are children of $\nu_{\ell}$. Given a set of nodes at level
$\ell$, define $g_{P}(D)$ to be the set where $g_{D}$ is applied to each set
element individually. Then define
$\mathcal{A}^{*}_{P_{\ell}}(D)=(\mathcal{A}^{*}_{P}(g_{P}(D)))_{\ell}$. Since
$g_{P}$ is applied individually to each element in $D$,
$\mathcal{A}^{*}_{P_{\ell}}$ is $\varepsilon$-DP.

Given a distribution $Q^{\ell}\in\mathcal{N}_{\ell}(P_{\ell})$, define a
distribution $Q$ on the leaves of the tree as follows:

$Q(\nu)=\frac{Q^{\ell}(\nu_{\ell})}{P_{\ell}(\nu_{\ell})}*P(\nu),$

where $\nu_{\ell}$ is the parent node of $\nu$ at level $\ell$. Note
$Q\in\mathcal{N}(P)$, $g_{P}(Q^{\ell})=Q$ and $Q_{\ell}=Q^{\ell}$. Now,

$\displaystyle TV(Q^{\ell},\mathcal{A}^{*}_{P_{\ell}}(D))$
$\displaystyle=TV(Q_{\ell},(\mathcal{A}^{*}_{P}(g_{P}(D))_{\ell})$
$\displaystyle\leq\frac{1}{r_{\ell}}\sum_{\ell^{\prime}\in[0pt]}r_{\ell^{\prime}}TV(Q_{\ell^{\prime}},(\mathcal{A}^{*}_{P}(g_{P}(D))_{\ell^{\prime}})$
$\displaystyle=\frac{1}{r_{\ell}}\mathcal{W}(Q,\mathcal{A}^{*}_{P}(g_{P}(D)))$

where the first inequality follows by definition of
$\mathcal{A}^{*}_{P_{\ell}}$ and the fact $Q_{\ell}=Q^{\ell}$. Since
$g_{P}(Q^{\ell})=Q$, this implies that for all distributions in
$\mathcal{N}_{\ell}(P_{\ell})$,

$\mathbb{E}_{D\sim
Q^{\ell}}\left[TV(Q^{\ell},\mathcal{A}^{*}_{P_{\ell}}(D))\right]\leq\mathbb{E}_{D\sim
Q}\left[\frac{1}{r_{\ell}}\mathcal{W}(Q,\mathcal{A}^{*}_{P}(D))\right]\leq\frac{1}{r^{\ell}}\mathcal{R}_{\mathcal{N},n,\varepsilon}(P),$

which implies for all levels $\ell$,
$\mathcal{R}_{\mathcal{N}_{\ell},n,\varepsilon}(P_{\ell})\leq\frac{1}{r^{\ell}}\mathcal{R}_{\mathcal{N},n,\varepsilon}(P)$
and so we are done. ∎

See 5.8

###### Proof of Lemma 5.8.

We will follow the proof of Theorem 3 in [ASZ21]. Given an estimator
$\mathcal{A}$, define a classifier $\mathcal{A}^{*}$ by projecting on the
product of hypercubes so

$\mathcal{A}^{*}(X)=\arg\min_{u\in(\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots)}d(\mathcal{A}(X),\theta(p_{u})).$

By the triangle inequality and the definition of $\mathcal{A}^{*}$, for any
$p\in\mathcal{V}$,

$d(\theta(p_{\mathcal{A}^{*}(X)}),\theta(p))\leq
d(\mathcal{A}(X),\theta(p_{\mathcal{A}^{*}(X)}))+d(\mathcal{A}(X),\theta(p))\leq
2d(\mathcal{A}(X),\theta(p)).$

Therefore, we can restrict to a lower bound on the performance of DP
classifiers:

$\min_{\mathcal{A}\text{ is
}(\varepsilon,\delta)\text{-DP}}\max_{p\in\mathcal{V}}\mathcal{R}_{\mathcal{A},n}(p)\geq\frac{1}{2}\min_{\mathcal{A^{*}}\text{
is }(\varepsilon,\delta)\text{-DP}}\max_{p\in\mathcal{V}}\mathbb{E}_{X\sim
p^{n}}[d(\theta(p_{\mathcal{A}^{*}(X)}),\theta(p))].$ (11)

Also, for any $(\varepsilon,\delta)$-DP classifier $\mathcal{A}^{*}$,

$\displaystyle\max_{p\in\mathcal{V}}\mathbb{E}_{X\sim
p^{n}}[d(\theta(p_{\mathcal{A}^{*}(X)}),\theta(p))]$
$\displaystyle\geq\frac{1}{|\mathcal{V}|}\sum_{u\in(\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots)}\mathbb{E}_{X\sim
p_{u}^{n}}[d(\theta(p_{\mathcal{A}^{*}(X)}),\theta(p_{u}))]$
$\displaystyle\geq\frac{2}{|\mathcal{V}|}\sum_{s}\tau_{s}\sum_{j=1}^{k_{s}}\sum_{u\in\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots}\Pr_{X\sum
p_{u}^{n}}(\mathcal{A}^{*}(X)_{j}^{s}\neq u_{j}^{s}),$

where the first inequality follows from the fact that the max is greater than
the average, and the second follows from assumption (5). For each $(s,j)$
pair, we divide $\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots$
into two groups;

$\displaystyle\max_{p\in\mathcal{V}}$ $\displaystyle\mathbb{E}_{X\sim
p^{n}}[d(\theta(p_{\mathcal{A}^{*}(X)}),\theta(p))]$
$\displaystyle\geq\frac{2}{|\mathcal{V}|}\sum_{s}\tau_{s}\sum_{j=1}^{k_{s}}\left[\sum_{u\in(\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots)\;|\;u_{j}^{s}=+1}\Pr_{X\sum
p_{u}^{n}}(\mathcal{A}^{*}(X)_{j}^{s}\neq
u_{j}^{s})+\sum_{u\in(\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots)\;|\;u_{j}^{s}=-1}\Pr_{X\sim
p_{u}^{*}}(\mathcal{A}^{*}(X)_{j}^{s}\neq u_{j}^{s})\right]$
$\displaystyle\geq\frac{2}{|\mathcal{V}|}\sum_{s}\tau_{s}\sum_{j=1}^{k_{s}}\left[\sum_{u\in(\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots)\;|\;u_{j}^{s}=+1}\Pr_{X\sim
p_{u}^{n}}(\mathcal{A}^{*}(X)_{j}^{s}\neq
u_{j}^{s})+\sum_{u\in(\mathcal{E}_{k_{0}}\times\mathcal{E}_{k_{1}}\times\cdots)\;|\;u_{j}^{s}=-1}\Pr_{X\sim
p_{u}^{n}}(\mathcal{A}^{*}(X)_{j}^{s}\neq u_{j}^{s})\right]$
$\displaystyle\geq\sum_{s}\tau_{s}\sum_{j=1}^{k_{s}}(\Pr_{X\sim
p_{+(s,j)}^{n}}(\mathcal{A}^{*}(X)\neq+1)+\Pr_{X\sim
p_{-(s,j)}^{n}}(\mathcal{A}^{*}(X)\neq-1))$
$\displaystyle\geq\sum_{s}\tau_{s}\sum_{j=1}^{k_{s}}(\Pr_{X\sim
p_{+(s,j)}^{n}}(\phi_{s,j}(X)\neq+1)+\Pr_{X\sim
p_{-(s,j)}^{n}}(\phi_{s,j}(X)\neq-1)).$

Combining with eqn 11 we have the first statement. Next, since for each pair
$(s,j)$, there exists a coupling $(X,Y)$ between $p_{+(s,j)}$ and $p_{-(s,j)}$
such that $\mathbb{E}[d_{Ham}(X,Y)]\leq D_{s}$, we can use the DP version of
Le Cam’s method from [ASZ21] to give for any classifier $\phi_{s,j}$,

$\Pr_{X\sim p_{+(s,j)}^{n}}(\phi_{s,j}(X)\neq+1)+\Pr_{X\sim
p_{-(s,j)}^{n}}(\phi_{s,j}(X)\neq-1)\geq\frac{1}{2}(0.9e^{-10\varepsilon
D_{s}}-10D_{s}\delta),$

which implies the final result. ∎

See 5.12

###### Proof of Lemma 5.12.

A standard result in the statistics literature states that for any pair of
distributions $P$ and $Q$,

$\min_{\phi}\left(\Pr_{X\sim P^{n}}(\phi(X)=1)+\Pr_{X\sim
Q^{n}}(\phi(X)=-1)\right)=\frac{1}{2}(1-\text{\rm
TV}(P^{n},Q^{n}))\geq\frac{1}{2}(1-\sqrt{n\text{\rm KL}(P,Q)}),$

where the minimum is over all binary classifiers. If
$P=\texttt{Bernoulli}(p-\alpha)$ and $Q=\texttt{Bernoulli}(p+\alpha)$ where
$0\leq\alpha\leq\frac{1}{2}L(p)$ then

$\displaystyle\text{\rm KL}(Q,P)$
$\displaystyle=(p+\alpha)\ln\frac{p+\alpha}{p-\alpha}+(1-p-\alpha)\ln\frac{1-p-\alpha}{1-p+\alpha}$
$\displaystyle=(p+\alpha)\ln\left(1+\frac{2\alpha}{p-\alpha}\right)+(1-p-\alpha)\ln\left(1-\frac{2\alpha}{1-p+\alpha}\right)$
$\displaystyle\leq(p+\alpha)\frac{2\alpha}{p-\alpha}-(1-p-\alpha)\frac{2\alpha}{1-p+\alpha}$
$\displaystyle=\frac{4\alpha^{2}}{p-\alpha}+\frac{4\alpha^{2}}{1-p+\alpha}$
$\displaystyle=\frac{\alpha^{2}}{(p-\alpha)(1-p+\alpha)}$
$\displaystyle\leq\frac{1}{4n}.$

where the first inequality holds since $\ln(1+x)<x$ for $x\in[-1,1]$ and by
assumption $2\alpha/(p-\alpha),2\alpha/(1-p+\alpha)\in[0,1]$ and the second
follows again because of the constraint on $\alpha$. ∎

See 5.14

Lemma 5.14 is an immediate corollary of the following lemma.

######  Lemma C.1.

For any distribution $P$, if $\log(n/\beta)>1$ then with probability
$1-30pt\beta$,

$\mathfrak{W}(\widehat{\mathfrak{G}_{P}},\mathfrak{G}_{P})\leq\sum_{\ell\in[0pt]}\sum_{x\in[N_{\ell}]}\min\left\\{P_{\ell}(x),1-P_{\ell}(x),4\sqrt{3\frac{P_{\ell}(x)\log(n/\beta)}{n}},4\sqrt{3\frac{(1-P_{\ell}(x))\log(n/\beta)}{n}}\right\\}$

###### Proof of Lemma 5.14.

We’ll consider each level of the tree individually then use a union bound over
all the levels to obtain our final bound. Let $(\hat{P}_{\ell})_{n}$ be the
empirical distribution without truncation. The following conditions are
sufficient to ensure that the bounds hold for a single level $\ell$:

$\sup_{\nu\text{ s.t.
}P_{\ell}(\nu)\leq\frac{3\ln(n/\beta)}{n}}\hat{(P_{\ell})}_{n}(\nu)\leq\frac{7\ln(n/\beta)}{n}$
$\sup_{\nu\text{ s.t. }P_{\ell}(\nu)\geq
1-\frac{3\ln(n/\beta)}{n}}\hat{(P_{\ell})}_{n}(\nu)\geq
1-\frac{7\ln(n/\beta)}{n}$ $\forall\left(\nu\text{ s.t.
}P_{\ell}(\nu)\in\left[\frac{3\ln(n/\beta)}{n},1-\frac{3\ln(n/\beta)}{n}\right]\right),\hskip
144.54pt$ $\hskip
72.26999pt|\hat{(P_{\ell})}_{n}(x)-P_{\ell}(\nu)|\leq\min\left\\{\sqrt{\frac{3P_{\ell}(\nu)\ln(n/\beta)}{n}},\sqrt{\frac{3(1-P_{\ell}(x))\ln(n/\beta)}{n}}\right\\}$

We will begin by showing these conditions are sufficient. If
$P_{\ell}(\nu)\notin[\frac{3\ln(n/\beta)}{n},1-\frac{3\ln(n/\beta)}{n}]$ then
these conditions imply that the empirical density for node $\nu$ is truncated,
and hence the error that that node is either $P_{\ell}(\nu)$ or
$1-P_{\ell}(\nu)$ (when $P_{\ell}(\nu)<1/2$ and $P_{\ell}(\nu)>1/2$,
respectively), as required. If
$P_{\ell}(\nu)\in[\frac{3\ln(n/\beta)}{n},1-\frac{3\ln(n/\beta)}{n}]$ then
either the estimate is not truncated and the error is less than
$\min\left\\{\sqrt{\frac{3P_{\ell}(\nu)\ln(2n/\beta)}{n}},\sqrt{\frac{3(1-P_{\ell}(x))\ln(2n/\beta)}{n}}\right\\}\leq\min\\{P_{\ell}(\nu),1-P_{\ell}(\nu)\\}$,
as required. Or the estimate is truncated and the error is
$\min\\{P_{\ell}(\nu),1-P_{\ell}(\nu)\\}$. Under the above conditions, if
$P_{\ell}(\nu)\leq 1/2$ then truncation will only occur if

$P_{\ell}(\nu)-\sqrt{\frac{3p\ln(2n/\beta)}{n}}\leq\frac{7\ln(n/\beta)}{n}\leq\sqrt{\frac{7\ln(n/\beta)}{n}\frac{7}{3}\frac{3\ln(n/\beta)}{n}}\leq\sqrt{\frac{7\ln(n/\beta)}{n}\frac{7}{3}p}=\frac{7}{3}\sqrt{\frac{3\ln(n/\beta)}{n}p},$

in which case $P_{\ell}(nu)\leq 4\sqrt{\frac{3P_{\ell}(\nu)\ln(n/\beta)}{n}}$,
as required. Similarly, if $P_{\ell}(\nu)>1/2$ then truncation will only occur
if $1-P_{\ell}(\nu)\leq 4\sqrt{\frac{3(1-P_{\ell}(\nu))\ln(n/\beta)}{n}}$, as
required.

We will now show that these conditions hold simultaneously with probability at
least $1-3\beta$ for all the nodes at level $\ell$. If
$P_{\ell}(\nu)\leq\frac{1}{en}$ then using the multiplicative form of Chernoff
bound,

$\displaystyle\Pr((\hat{P_{\ell}})_{n}(\nu)\geq\frac{3\ln(n/\beta)}{n})$
$\displaystyle=\Pr((\hat{P_{\ell}})_{n}(\nu)\geq\left(1+\frac{3\ln(n/\beta)}{P_{\ell}(\nu)n}-1\right)P_{\ell}(\nu))$
$\displaystyle\leq\left(\frac{e^{\frac{3\ln(n/\beta)}{nP_{\ell}(\nu)}-1}}{(\frac{3\ln(n/\beta)}{nP_{\ell}(\nu)})^{\frac{3\ln(n/\beta)}{nP_{\ell}(\nu)}}}\right)^{P_{\ell}(\nu)n}$
$\displaystyle\leq\left(\frac{enP_{\ell}(\nu)}{3\ln(n/\beta)}\right)^{3\ln(n/\beta)}$
$\displaystyle\leq
P_{\ell}(\nu)n\left(\frac{e}{3\ln(n/\beta)}\right)^{3\ln(n/\beta)}(nP_{\ell}(\nu))^{3\ln(n/\beta)-1}$

Firstly, since $\ln(n/\beta)\geq 1$,
$\left(\frac{e}{3\ln(n/\beta)}\right)^{3\ln(n/\beta)}\leq 1$. Further,
$nP_{\ell}(\nu)\leq 1/e$ and $3\ln(n/\beta)-1\geq\ln(n/\beta)$ so
$(nP_{\ell}(\nu))^{3\ln(n/\beta)-1}\leq(1/e)^{\ln(n/\beta)}=\beta/n$.
Therefore,

$\Pr((\hat{P_{\ell}})_{n}(\nu)\geq\frac{3\ln(n/\beta)}{n})\leq
P_{\ell}(\nu)\beta.$ (12)

Let $\mathcal{S}=\\{x\in[N_{\ell}]\;|\;P_{\ell}(x)<1/(en)\\}$ then using a
union bound and Eqn (12) we have

$\displaystyle\Pr(\exists x\in\mathcal{S}\text{ s.t.
}\hat{(P_{\ell})}_{n}(x)\geq\frac{2\sqrt{2}\log(n/\beta)}{n})$
$\displaystyle\leq\sum_{x\in\mathcal{S}}P_{\ell}(\nu)\beta\leq\beta$

There exist at most $n$ elements in $[N_{\ell}]$ that do not belong in
$\mathcal{S}$. We will prove that, independently, each of these elements
satisfy the required condition with probability $\leq 2\beta/n$ then a union
bound proves the final result. If
$P_{\ell}(\nu)\in[\frac{3\ln(n/\beta)}{n},1-\frac{3\ln(n/\beta)}{n}]$ then
using the multiplicative form of Chernoff bound (If $X_{i}$ are all i.i.d. and
$0<\delta<1$, then $\Pr(|\sum_{i=1}^{n}X_{i}-n\mathbb{E}[X_{1}]|\geq\delta
n\mathbb{E}[X_{1}])\leq 2e^{-\delta^{2}n\mathbb{E}[X_{1}]/3}$),

$\displaystyle\Pr(|\hat{(P_{\ell})}_{n}(x)-P_{\ell}(x)|\geq\sqrt{\frac{3P_{\ell}(x)\log(n/\beta)}{n}})$
$\displaystyle=\Pr(|\hat{(P_{\ell})}_{n}(x)-P_{\ell}(x)|\geq\sqrt{\frac{3\log(n/\beta)}{P_{\ell}(x)n}}P_{\ell}(x))$
$\displaystyle\leq
2e^{\frac{-\left(\frac{3\log(n/\beta)}{P_{\ell}(x)n}\right)P_{\ell}(x)n}{3}}$
$\displaystyle=2\beta/n.$

Next, if $P_{\ell}(\nu)\leq\frac{3\ln(n/\beta)}{n}$ then using the additive
form of Chernoff bound (If $X_{i}$ are all i.i.d. and $\varepsilon\geq 0$,
then $\Pr(\frac{1}{n}\sum_{i=1}^{n}X_{i}\geq\mathbb{E}[X_{1}]+\varepsilon)\leq
e^{-\varepsilon^{2}n/(2(p+\varepsilon))}$)

$\displaystyle\Pr((\hat{P_{\ell}})_{n}(\nu)\geq\frac{7\ln(n/\beta)}{n})$
$\displaystyle\leq\Pr((\hat{P_{\ell}})_{n}(\nu)\geq
p+(7\frac{\ln(n/\beta)}{n}-p))$ $\displaystyle\leq
e^{-\frac{(7\frac{\ln(n/\beta)}{n}-p)^{2}n}{14\frac{\ln(n/\beta)}{n}}}$
$\displaystyle\leq
e^{-\frac{(4\frac{\ln(n/\beta)}{n})^{2}n}{14\frac{\ln(n/\beta)}{n}}}$
$\displaystyle\leq e^{-\ln(n/\beta)}$ $\displaystyle=\beta/n.$

By symmetry, if $P_{\ell}(\nu)\geq 1-\frac{3\ln(n/\beta)}{n}$ then

$\Pr((\hat{P_{\ell}})_{n}(\nu)\leq 1-\frac{7\ln(n/\beta)}{n})\leq\beta/n.$

∎

See 5.15

###### Proof of Lemma 5.15.

First notice that if a node $\nu$ is an $\alpha$-active node, then all of it’s
ancestor nodes are also $\alpha$-active. So, it suffices to show that (with
high probability) if at any stage a node makes to it Line 7 of Algorithm 3,
then if $\nu\notin\gamma_{{P}}\left({2\kappa}\right)$ then
$\widehat{\mathfrak{G}_{P}}(\nu)+\mathsf{Lap}(\frac{1}{\varepsilon n})\leq
2\kappa+\frac{\log(2/\beta)}{\varepsilon n}$ and if
$\nu\in\gamma_{{P}}\left({\max\left\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{\log(n/\beta)}{n}\right\\}}\right)$ then
$\widehat{\mathfrak{G}_{P}}(\nu)+\mathsf{Lap}(\frac{1}{\varepsilon
n}))>2\kappa+\frac{\log(2/\beta)}{\varepsilon n}$.

By Lemma 5.14, with probability $1-30pt\beta$, all nodes $\nu$ satisfy

$|\widehat{\mathfrak{G}_{P}}(\nu)-\mathfrak{G}_{P}(\nu)|\leq\min\left\\{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu)),4\sqrt{\frac{3\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu))\log(n/\beta)}{n}}\right\\}$

Further, if one samples $X$ independent samples from
$\mathsf{Lap}(\frac{1}{\varepsilon n})$ then with probability $1-X\beta$,

$\sup|\mathsf{Lap}(\frac{1}{\varepsilon
n})|\leq\frac{\ln(2/\beta)}{\varepsilon n}.$

So conditioning on both these events if
$x\notin\gamma_{{P}}\left({\frac{1}{2\varepsilon n}}\right)$,

$\widehat{\mathfrak{G}_{P}}(\nu)+\mathsf{Lap}(\frac{1}{\varepsilon
n})\leq\mathfrak{G}_{P}(\nu)+\frac{\ln(2/\beta)}{\varepsilon
n}\leq\frac{1}{2\varepsilon n}+\frac{\ln(2/\beta)}{\varepsilon n},$

so they will not survive Line 7 of Algorithm 3. If
$x\in\gamma_{{P}}\left({\max\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon n},\frac{192\log(n/\beta)}{n}\\}}\right)$
then

$\displaystyle\widehat{\mathfrak{G}_{P}}(\nu)+\mathsf{Lap}(\frac{1}{\varepsilon
n})$
$\displaystyle\geq\mathfrak{G}_{P}(\nu)-4\sqrt{3\frac{\mathfrak{G}_{P}(\nu)\log(n/\beta)}{n}}-\frac{\ln(2/\beta)}{\varepsilon
n}$
$\displaystyle\geq\frac{1}{2}\mathfrak{G}_{P}(\nu)-\frac{\log(2/\beta)}{\varepsilon
n}$ $\displaystyle\geq\frac{1}{\varepsilon n}+\frac{\log(2/\beta)}{n}$

Each level has at most $2\varepsilon n$ in
$\gamma_{{P}}\left({\frac{1}{2\varepsilon n}}\right)$ so we query at most
$4\varepsilon n$ nodes in the tree when running LocateActiveNodes since each
node has at most 2 children. Therefore, we can set $X=4\varepsilon n0pt$. ∎

See 5.16

###### Proof of Lemma 5.16.

The key component of this proof is that any discrepancy between the weight of
the nodes on $P$ and that assigned by $\widehat{\mathfrak{G}_{P}}$ was already
paid for in $\mathcal{W}(P,\widehat{\mathfrak{G}_{P}})$.

$\displaystyle\mathfrak{W}(\widehat{\mathfrak{G}_{P}},\widehat{\mathfrak{G}_{P}}|_{\hat{\gamma}_{\varepsilon}})$
$\displaystyle=\sum_{\nu\notin\hat{\gamma}_{\varepsilon}}r_{\nu}|\widehat{\mathfrak{G}_{P}}(\nu)|$
$\displaystyle\leq\sum_{\nu\notin\gamma_{{P}}\left({\max\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{192\log(n/\beta)}{n}\\}}\right)}r_{\nu}|\widehat{\mathfrak{G}_{P}}(\nu)|$
$\displaystyle=\sum_{\nu\notin\gamma_{{P}}\left({\max\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{192\log(n/\beta)}{n}\\}}\right)}r_{\nu}|\widehat{\mathfrak{G}_{P}}(\nu)-\mathfrak{G}_{P}(\nu)+\mathfrak{G}_{P}(\nu)|$
$\displaystyle\leq\sum_{\nu\notin\gamma_{{P}}\left({\max\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{192\log(n/\beta)}{n}\\}}\right)}r_{\nu}|\widehat{\mathfrak{G}_{P}}(\nu)-\mathfrak{G}_{P}(\nu)|$
$\displaystyle\hskip
144.54pt+\sum_{\nu\notin\gamma_{{P}}\left({\max\\{\frac{2}{\varepsilon
n}+2\frac{\log(2/\beta)}{n},\frac{192\log(n/\beta)}{n}\\}}\right)}r_{\nu}|\mathfrak{G}_{P}(\nu)|$
$\displaystyle\leq\mathfrak{W}(\mathfrak{G}_{P},\widehat{\mathfrak{G}_{P}})+\mathfrak{W}(\mathfrak{G}_{P},\mathfrak{G}_{P}|_{\gamma_{{P}}\left({\max\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{192\log(n/\beta)}{n}\\}}\right)})$

as required. ∎

See 5.17

###### Proof of Lemma 5.17.

We first note that for any pair of sequences of real values
$a_{1},\cdots,a_{k}$ and $b_{1},\cdots,b_{k}$, and constant $A$ such that
$\sum_{i}a_{i}\neq 0$,

$\sum|\frac{A}{\sum a_{i}}a_{i}-b_{i}|\leq\sum|\frac{A}{\sum
a_{i}}a_{i}-a_{i}|+|a_{i}-b_{i}|=|A-\sum a_{i}|+\sum|a_{i}-b_{i}|\leq|A-\sum
b_{i}|+2\sum|a_{i}-b_{i}|.$

Also if $\sum a_{i}=0$ then

$\sum|\frac{A}{k}-b_{i}|\leq\sum|\frac{A}{k}-\frac{\sum_{i}b_{i}}{k}|+|\frac{\sum_{i}b_{i}}{k}-b_{i}|=|A-\sum
b_{i}|+2\sum|b_{i}|=|A-\sum b_{i}|+2\sum|a_{i}-b_{i}|$

Let $\bar{\mathfrak{G}}^{\ell}$ be the function $\bar{\mathfrak{G}}$ after
only levels $0,\cdots,\ell$ have been updated. So $\bar{\mathfrak{G}}^{\ell}$
matches $\bar{\mathfrak{G}}^{\ell-1}$ on all levels except $\ell$. Let $\nu$
be a node in the $\ell$th level of the HST. If we suppose the sum is over the
normalised children of a node $\nu$, $A=\bar{\mathfrak{G}}^{\ell-1}(\nu)$, and
for all the children $\nu^{\prime}$ of $\nu$,
$a_{i}=\mathfrak{G}(\nu^{\prime})$ and $b_{i}=\mathfrak{G}_{P}(\nu^{\prime})$,
we can see that the contribution to the Wasserstein distance by the children
increases by an additive factor of
$|\mathfrak{G}^{\ell-1}(\nu)-\mathfrak{G}_{P}(\nu)|$. Iterating, we can see
that

$\mathcal{W}(P,\texttt{Projection}(\mathfrak{G}))\leq
2\sum_{\ell=0}^{0pt}\sum_{\nu\text{ at level }\ell}(r_{\ell}+r_{\ell+1}\cdots
r_{0pt})|\mathfrak{G}(\nu)-\mathfrak{G}_{P}(\nu)|\leq
4\sum_{\ell=0}^{0pt}\sum_{\nu\text{ at level
}\ell}r_{\ell}|\mathfrak{G}(\nu)-\mathfrak{G}_{P}(\nu)|,$

which is 4 times the wasserstein distance.

∎

##  Appendix D Local Minimality in the High Dimensional Setting

######  Theorem D.1.

Given any $\varepsilon>0$, and a distribution $P$, and let
$n^{\prime}=\frac{5}{4\min\\{W(\frac{0.45\varepsilon}{\delta}),0.6\\}}n$, then
for all $(\varepsilon,\delta)$-DP algorithms $\mathcal{A}^{\prime}$, there
exists a distribution $Q\in\mathcal{N}(P)$ such that with probability
$1-(0pt\log n+40pt\varepsilon n)\beta$,

$\mathcal{W}(Q,\hat{Q_{\varepsilon,n^{\prime}}})\leq\tilde{O}(\mathbb{E}_{X\sim
Q^{n},\mathcal{A^{\prime}}}(\mathcal{W}(\mathcal{A^{\prime}}(X),Q))),$

where $\hat{Q_{\varepsilon,n^{\prime}}}$ is the output of
$\texttt{PrivDensityEstTree}(Q)$ with $n^{\prime}$ samples.

###### Proof.

First, let us obtain a slightly simpler upper bound on
$\mathcal{W}(P,\hat{P}_{\varepsilon})$. From eqn (8) in the proof of Theorem
5.13 we have that for each level $\ell$,

$\mathcal{W}(P_{\ell},(\hat{P}_{\varepsilon})_{\ell})\leq
2\left(\mathfrak{W}((\mathfrak{G}_{P})_{\ell},(\widehat{\mathfrak{G}_{P}})_{\ell})+\mathfrak{W}((\widehat{\mathfrak{G}_{P}})_{\ell},(\widehat{\mathfrak{G}_{P}}|{\hat{\gamma}_{\varepsilon}})_{\ell})+\mathfrak{W}((\widehat{\mathfrak{G}_{P}}|{\hat{\gamma}_{\varepsilon}})_{\ell},(\widetilde{\mathfrak{G}_{\hat{P}_{n},\hat{\gamma}_{\varepsilon}}})_{\ell})\right),$

from Lemma 5.15 we have that with probability $1-0pt(\log n+4\varepsilon
n)\beta$,

$\gamma_{{P}}\left({\max\left\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{192\log(n/\beta)}{n}\right\\}}\right)\subset\hat{\gamma}_{\varepsilon}\subset\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right),$

and if one samples $4\varepsilon n0pt$ independent samples from
$\mathsf{Lap}(\frac{1}{\varepsilon n})$ then we have that with probability
$1-4\varepsilon n0pt\beta$,

$\sup|\mathsf{Lap}(\frac{1}{\varepsilon
n})|\leq\frac{\ln(2/\beta)}{\varepsilon n}.$

Therefore, for all $\nu\notin\hat{\gamma}_{\varepsilon}$ we have
$P_{\ell}(\nu)\leq\max\left\\{\frac{2}{\varepsilon
n}+4\frac{\log(2/\beta)}{\varepsilon
n},\frac{192\log(n/\beta)}{n}\right\\}\leq C\frac{\ln(n/\beta)}{\varepsilon
n}$ for some constant $C$ therefore,

$\displaystyle\mathfrak{W}((\widehat{\mathfrak{G}_{P}})_{\ell},(\widehat{\mathfrak{G}_{P}}|{\hat{\gamma}_{\varepsilon}})_{\ell})+\mathfrak{W}((\widehat{\mathfrak{G}_{P}}|{\hat{\gamma}_{\varepsilon}})_{\ell},(\widetilde{\mathfrak{G}_{\hat{P}_{n},\hat{\gamma}_{\varepsilon}}})_{\ell})$
$\displaystyle\leq\sum_{\nu\notin\hat{\gamma}_{\varepsilon}}P_{\ell}(\nu)+\sum_{\nu\in\hat{\gamma}_{\varepsilon}}\frac{\ln(2/\beta)}{\varepsilon
n}$ $\displaystyle\leq\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)}P_{\ell}(\nu)+\sum_{\nu\in\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)\backslash\hat{\gamma_{\varepsilon}}}C\frac{\ln(n/\beta)}{\varepsilon
n}+\sum_{\nu\in\hat{\gamma}_{\varepsilon}}\frac{\ln(2/\beta)}{\varepsilon n}$
$\displaystyle\leq\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)}P_{\ell}(\nu)+C\ln(n/\beta)\sum_{\nu\in\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)}\frac{1}{\varepsilon n}.$

For the same reason as in the proof of Theorem 5.13, we can upper bound
$\sum_{\nu\in\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)}\frac{1}{\varepsilon n}$ by
$(|\gamma_{{P}}\left({\frac{1}{2\varepsilon n}}\right)|-1)\frac{1}{\varepsilon
n}$ by dealing with the $|\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)|=1$ case separately. Therefore,

$\displaystyle\mathcal{W}(P,\hat{P}_{\varepsilon})$ $\displaystyle\leq
2C\ln(n/\beta)\left(\sum_{\nu}\min\left\\{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu)),\sqrt{\frac{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu))}{n}}\right\\}+\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)}\mathfrak{G}_{P}(\nu)+(|\gamma_{{P}}\left({\frac{1}{2\varepsilon
n}}\right)|-1)\frac{1}{\varepsilon n}\right),$

Further, by Theorem 5.7 and Theorem 5.6, given $\varepsilon>0$ and
$\delta\in[0,1]$, let $\kappa=\frac{1}{10\varepsilon
n}\min\\{W\left(\frac{0.45\varepsilon}{\delta}\right),0.6\\}$ where $W(x)$ is
the Lambert W function so $W(x)e^{W(x)}=x$. Given a distribution $P$, there
exists a constant $C^{\prime}$ such that

$\mathcal{R}_{\mathcal{N},n,\varepsilon}(P)\geq\frac{C^{\prime}}{D_{T}}\left(\sum_{\nu}\min\left\\{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu)),\sqrt{\frac{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu))}{n}}\right\\}+\sum_{\nu\notin\gamma_{{P}}\left({2\kappa}\right)}\mathfrak{G}_{P}(\nu)+(|\gamma_{{P}}\left({2\kappa}\right)|-1)\kappa\right)$

Let $Q\in\mathcal{N}(P)$, then $\gamma_{{P}}\left({\frac{1}{\varepsilon
n}}\right)\subset\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)\subset\gamma_{{P}}\left({\frac{1}{4\varepsilon n}}\right)$ so

$\displaystyle\sum_{\nu\notin\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)}\mathfrak{G}_{Q}(\nu)+(|\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)|-1)\frac{1}{\varepsilon n}$
$\displaystyle=\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{4\varepsilon
n}}\right)}\mathfrak{G}_{Q}(\nu)+\sum_{\nu\in\gamma_{{P}}\left({\frac{1}{4\varepsilon
n}}\right)\backslash\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)}\mathfrak{G}_{Q}(\nu)+(|\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)|-1)\frac{1}{\varepsilon n}$
$\displaystyle\leq\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{4\varepsilon
n}}\right)}2\mathfrak{G}_{P}(\nu)+\sum_{\nu\in\gamma_{{P}}\left({\frac{1}{4\varepsilon
n}}\right)\backslash\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)}\frac{1}{\varepsilon n}+(|\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n}}\right)|-1)\frac{1}{\varepsilon n}$
$\displaystyle\leq\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{4\varepsilon
n}}\right)}2\mathfrak{G}_{P}(\nu)+(|\gamma_{{P}}\left({\frac{1}{4\varepsilon
n}}\right)|-1)\frac{1}{\varepsilon n}.$

Now, let
$n^{\prime}=\frac{5}{4\min\\{W(\frac{0.45\varepsilon}{\delta}),0.6\\}}n\geq n$
so for all $Q\in\mathcal{N}(P)$,

$\displaystyle\mathcal{W}(Q,\hat{Q_{\varepsilon,n^{\prime}}})$
$\displaystyle\leq\tilde{O}\left(\sum_{\nu}\min\left\\{\mathfrak{G}_{Q}(\nu)(1-\mathfrak{G}_{Q}(\nu)),\sqrt{\frac{\mathfrak{G}_{Q}(\nu)(1-\mathfrak{G}_{Q}(\nu))}{n^{\prime}}}\right\\}+\sum_{\nu\notin\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n^{\prime}}}\right)}\mathfrak{G}_{Q}(\nu)+(|\gamma_{{Q}}\left({\frac{1}{2\varepsilon
n^{\prime}}}\right)|-1)\frac{1}{\varepsilon n^{\prime}}\right)$
$\displaystyle\leq\tilde{O}\left(\sum_{\nu}2\min\left\\{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu)),\sqrt{\frac{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu))}{n^{\prime}}}\right\\}+\sum_{\nu\notin\gamma_{{P}}\left({\frac{1}{4\varepsilon
n^{\prime}}}\right)}2\mathfrak{G}_{P}(\nu)+(|\gamma_{{P}}\left({\frac{1}{4\varepsilon
n^{\prime}}}\right)|-1)\frac{1}{\varepsilon n^{\prime}}\right)$
$\displaystyle=\tilde{O}\left(\sum_{\nu}2\min\left\\{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu)),\sqrt{\frac{\mathfrak{G}_{P}(\nu)(1-\mathfrak{G}_{P}(\nu))}{n}}\right\\}+\sum_{\nu\notin\gamma_{{P}}\left({2\kappa}\right)}2\mathfrak{G}_{P}(\nu)+(|\gamma_{{P}}\left({2\kappa}\right)|-1)\frac{1}{\varepsilon
n}\right)$
$\displaystyle\leq\tilde{O}\left(\min_{\mathcal{A}^{\prime}}\max_{Q^{\prime}\in\mathcal{N}(P)}\mathbb{E}_{X\sim
Q^{\prime
n},\mathcal{A^{\prime}}}(\mathcal{W}(\mathcal{A^{\prime}}(X),Q^{\prime}))\right).$

As in Proposition 3.5, since $\mathcal{N}(P)$ is compact, for all
$\mathcal{A}^{\prime}$, there exists a specific $Q^{*}\in\mathcal{N}(P)$ such
that

$\mathcal{W}(Q^{*},\hat{Q^{*}_{\varepsilon,n^{\prime}}})\leq\tilde{O}(\mathbb{E}_{X\sim(Q^{*})^{n},\mathcal{A^{\prime}}}(\mathcal{W}(\mathcal{A^{\prime}}(X),Q^{*})))$

∎

##  Appendix E Differentially Private Quantiles

Estimating appropriately chosen quantiles is the main part of our algorithm
for approximating the distribution over $\mathbb{R}$ in Wasserstein distance,
and so in this section, we describe some known differentially private
algorithms for this task and derive some corollaries that we use extensively
in our application. We will use $F$ to represent CDF functions, with $F_{P}$
representing the CDF of distribution $P$. We start by stating an important
theorem on private CDF estimation. This follows from a use of the binary tree
mechanism [CSS11, DNPR10]. A version of this theorem for approximate
differential privacy is described in a survey by Kamath and Ullman [KU20,
Theorem 4.1]. The version presented here for pure differential privacy follows
from a very similar argument, except using Laplace Noise instead of Gaussian
noise (and basic composition instead of advanced composition to analyze
privacy). Their accuracy was also in expectation, but a similar analysis
yields a high probability bound, as in the theorem below.

######  Theorem E.1.

[KU20, Theorem 4.1]

Let $\varepsilon,\beta\in(0,1]$, let $D$ be an ordered, finite domain, and let
${\bf x}\in D^{n}$ be a dataset. Let $\hat{P}_{n}$ be the uniform distribution
on ${\bf x}$. Then, there exists an $\varepsilon$-DP algorithm $A^{CDF}$ that
on input ${\bf x}$ and the domain $D$ outputs a vector $G$ over $D$ such that
with probability at least $1-\beta$ over the randomness of $A^{CDF}$:

$\|G-F_{\hat{P}_{n}}\|_{\infty}=O\left(\frac{\log^{3}\frac{|D|}{\beta}}{\varepsilon
n}\right).$

CDF estimation is intimately related to quantile estimation, and we use the
following quantitative statement that will follow from a simple application of
Theorem E.1.

######  Theorem E.2.

Fix any $n>0$, $\varepsilon,\beta\in(0,1]$, $a,b\in\mathbb{R}$, and
$\gamma<b-a\in\mathbb{R}$ such that $\frac{b-a}{\gamma}$ is an integer. Let
$C$ be a sufficiently large constant. Then, there exists an $\varepsilon$-DP
algorithm $A_{quant}$, that on input interval end points $a,b$, granularity
$\gamma$, ${\bf
x}=(x_{1},\dots,x_{n})\in\\{a,a+\gamma,\dots,b-\gamma,b\\}^{n}$, and desired
quantile values ${\bf\alpha}\in(0,1)^{k}$, outputs quantiles
$\tilde{q}\in\\{a,a+\gamma,\dots,b-\gamma,b\\}^{k}$ such that with probability
at least $1-\beta$ over the randomness of $A_{quant}$, for all $r\in[k]$,

$\alpha_{r}-F_{\hat{P}_{n}}(\tilde{q}_{r})\leq
C\frac{\log^{3}\frac{b-a}{\beta\gamma}}{\varepsilon n},$

and

$\Pr_{y\sim\hat{P}_{n}}(y<\tilde{q}_{r})<\alpha_{r}+C\frac{\log^{3}\frac{b-a}{\beta\gamma}}{\varepsilon
n},$

where $\hat{P}_{n}$ is the uniform distribution on the entries of ${\bf x}$.

###### Proof.

Algorithm $A_{quant}$ operates by running the algorithm $A^{CDF}$ referenced
in Theorem E.1 on ${\bf x}$ and domain $\\{a,a+\gamma,\dots,b-\gamma,b\\}$,
and postprocessing its outputs to get quantile estimates as follows. For every
quantile $\alpha_{r}$ that we are asked to estimate, $A_{quant}$ simply scans
the vector $G$ output by algorithm $A^{CDF}$ in order, and outputs the first
domain element whose CDF estimate in $G$ crosses $\alpha_{r}$. Conditioned on
the accuracy of the CDF estimation algorithm $G$, we have that this output
$\tilde{q}_{r}$ satisfies

$\alpha_{r}-F_{\hat{P}_{n}}(\tilde{q}_{r})\leq
C\frac{\log^{3}\frac{b-a}{\beta\gamma}}{\varepsilon n}.$

Additionally, since $\tilde{q}_{r}$ is the first domain element whose estimate
in $G$ crosses $\alpha_{r}$, we also have that

$Pr_{y\sim\hat{P}_{n}}(y<\tilde{q}_{r})<\alpha_{r}+C\frac{\log^{3}\frac{b-a}{\beta\gamma}}{\varepsilon
n}.$

Hence, with probability at least $1-\beta$, we have this property for all
$r\in[k]$. ∎

We now state a corollary of this theorem that we will use extensively in our
presentation.

######  Corollary E.3.

Fix any $\varepsilon,\beta\in(0,1]$, $a,b\in\mathbb{R}$, and
$\gamma<b-a\in\mathbb{R}$ such that $\frac{b-a}{\gamma}$ is an integer. Let
$n\in\mathbb{N}>\frac{4c_{2}\log^{4}(\frac{b-a}{\beta\gamma\varepsilon})}{\varepsilon}$,
such that $k$ set to $\lceil\frac{\varepsilon
n}{4c_{3}log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}\rceil$ is an
integer greater than or equal to $1$, where $c_{2}$ and $c_{3}$ are
sufficiently large constants. 666$k$ is set to be sufficiently small in order
to relate the accuracy of the quantiles algorithm to a parameter depending on
$k$, and $n$ is set sufficiently large that $k$ is not less than $1$. The
dependence on $\beta$ comes up in the proof of 6.18.

Then, there exists an $\varepsilon$-DP algorithm $A_{quant}$ (the same one
referenced in Theorem E.2), that on input interval end points $a,b$,
granularity $\gamma$, ${\bf
x}=(x_{1},\dots,x_{n})\in\\{a,a+\gamma,\dots,b-\gamma,b\\}^{n}$, and desired
quantile values ${\bf\alpha}=\\{1/2k,3/2k,5/2k,\dots,(2k-1)/2k\\}$, outputs
quantiles $\tilde{q}\in\\{a,a+\gamma,\dots,b-\gamma,b\\}^{k}$ such that with
probability at least $1-\beta$, for all $r\in[k]$,

$\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}}\leq\tilde{q}_{r}\leq\hat{q}_{\frac{2r-1}{2k}+\frac{1}{4k}},$

where $\hat{P}_{n}$ is the uniform distribution on the entries of ${\bf x}$
and for all $p\in(0,1)$, $\hat{q}_{p}$ is the $p$-quantile of $\hat{P}_{n}$.

###### Proof.

First, note that $k$ is set such that $\frac{1}{4k}\geq
C\frac{log^{3}\frac{b-a}{\beta\gamma}}{\varepsilon n}$.

Hence, by Theorem E.2, we have that with probability at least $0.99$,

for all $r\in[k]$,

$\frac{2r-1}{2k}-F_{\hat{P}_{n}}(\tilde{q}_{r})\leq\frac{1}{4k},$

and

$\Pr_{y\sim\hat{P}_{n}}(y<\tilde{q}_{r})<\frac{2r-1}{2k}+\frac{1}{4k}.$

Condition the event above for the rest of the proof. Note that the first
equation implies that for all $r\in[k]$,

$\Pr_{y\sim\hat{P}_{n}}(y\leq\tilde{q_{r}})\geq\frac{2r-1}{2k}-\frac{1}{4k},$

which implies that $\tilde{q_{r}}\geq\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}}$.

Next, note that we also have that for all $r\in[k]$,

$\Pr_{y\sim\hat{P}_{n}}(y<\tilde{q}_{r})<\frac{2r-1}{2k}+\frac{1}{4k}.$

This implies that for all $r\in[k]$,
$\tilde{q_{r}}\leq\hat{q}_{\frac{2r-1}{2k}+\frac{1}{4k}}$. ∎

##  Appendix F Proofs in Section 6

###  F.1 Omitted Proofs in Section 6.1.1

###### Proof of Lemma 6.6.

We evaluate the various terms in Theorem 6.5.

We start by evaluating
$\tau(P,Q)=\max\\{\int_{\mathbb{R}}\max(f_{P}(t)-e^{\varepsilon}f_{Q}(t),0)dt,\int_{\mathbb{R}}\max(f_{Q}(t)-e^{\varepsilon}f_{P}(t),0)dt$
}. Consider the first term in the outer maximum. For all $t\in[L(P),q_{1/k})$,
we have that $f_{Q}(t)=\frac{1}{2}f_{P}(t)$. For all other $t$, one can see
that the value of the integrand is $0$. Hence, the value of the first term is
$\int_{L(P)}^{q_{1/k}}\max(f_{P}(t)-\frac{e^{\varepsilon}}{2}f_{P}(t),0)dt=\max\\{\left(1-\frac{e^{\varepsilon}}{2}\right)\frac{1}{k},0\\}\leq\frac{1}{2k}$.
Now, consider the second term in the outer maximum. For all
$t<q_{1-\frac{1}{k}}$, the value of the integrand is $0$. For all
$q_{1-\frac{1}{k}}\leq t\leq q_{1}$, the value of the integrand is
$\max\\{\left(\frac{3}{2}-e^{\varepsilon}\right)f_{P}(t),0\\}$. Hence, the
second term is
$\max\\{\left(\frac{3}{2}-e^{\varepsilon}\right)\frac{1}{k},0\\}\leq\frac{1}{2k}$.
Put together, we get that $\tau(P,Q)\leq\frac{1}{2k}$.

When $\varepsilon\geq\ln 2$, we have that $1-\frac{e^{\varepsilon}}{2}\leq 0$,
and so we have that the largest value of
$\varepsilon^{\prime}\in[0,\varepsilon]$ that makes
$\int_{\mathbb{R}}\max(f_{Q}(t)-e^{\varepsilon^{\prime}}f_{P}(t),0)dt=\tau(P,Q)=0$,
is $\varepsilon^{\prime}=\varepsilon$. When $\varepsilon<\ln 2$, we have that
the value of $\varepsilon^{\prime}$ that makes
$\int_{\mathbb{R}}\max(f_{Q}(t)-e^{\varepsilon^{\prime}}f_{P}(t),0)dt=\max\\{\left(\frac{3}{2}-e^{\varepsilon}\right)\frac{1}{k},0\\}=\left(1-\frac{e^{\varepsilon}}{2}\right)\frac{1}{k}$,
is $\varepsilon^{\prime}=\ln\left(\frac{1+e^{\varepsilon}}{2}\right)$.

Finally, we describe the distributions $P^{\prime}$ and $Q^{\prime}$ and
compute the squared Hellinger distance between them. There are two cases,
based on the range of $\varepsilon$. First, consider $\varepsilon\geq\ln 2$.
First, we calculate $\tilde{P}\equiv\min\\{e^{\varepsilon}Q,P\\}$. This value
is equal to $\min\\{e^{\varepsilon}/2,1\\}f_{P}(t)=f_{P}(t)$ for
$t<q_{\frac{1}{k}}(P)$, and is also equal to $f_{P}(t)$ for
$q_{\frac{1}{k}}\leq t\leq q_{1}$. Similarly, consider
$\tilde{Q}\equiv\min\\{e^{\varepsilon^{\prime}}P,Q\\}=\min\\{e^{\varepsilon}P,Q\\}$;
it is equal to $\frac{f_{P}(t)}{2}$ for $t<q_{\frac{1}{k}}(P)$, and is equal
to $f_{P}(t)$ for $q_{\frac{1}{k}}\leq t\leq q_{1-\frac{1}{k}}$. It is also
equal to $\min(e^{\varepsilon},\frac{3}{2})f_{P}(t)=\frac{3}{2}f_{P}(t)$ for
$q_{\frac{1}{k}}\leq t\leq q_{1}$. Since $\tau(P,Q)=0$, and by the above
calculations, we have that $P^{\prime}=P$, and $Q^{\prime}=Q$. Upper bounding
the squared Hellinger distance between $P^{\prime}$ and $Q^{\prime}$ by the TV
distance (See Lemma A.4), we get that
$H^{2}(P^{\prime},Q^{\prime})=H^{2}(P,Q)\leq
TV(P,Q)=\frac{1}{2k}\leq\frac{\varepsilon}{2(\ln 2)k}$ (where we have used
that $\varepsilon\geq\ln 2$).

Next, consider $\varepsilon<\ln 2$. First, consider
$\tilde{P}\equiv\min\\{e^{\varepsilon}Q,P\\}$. This value is equal to
$\min\\{e^{\varepsilon}/2,1\\}f_{P}(t)=\frac{e^{\varepsilon}}{2}f_{P}(t)$ for
$t<q_{\frac{1}{k}}(P)$, and is also equal to $f_{P}(t)$ for
$q_{\frac{1}{k}}\leq t\leq q_{1}$. Similarly, consider
$\tilde{Q}\equiv\min\\{e^{\varepsilon^{\prime}}P,Q\\}=\min\\{\frac{1+e^{\varepsilon}}{2}P,Q\\}$;
it is equal to $\frac{1}{2}f_{P}(t)$ for $t<q_{\frac{1}{k}}(P)$, and is equal
to $f_{P}(t)$ at $q_{\frac{1}{k}}\leq t\leq q_{1-\frac{1}{k}}$. It is also
equal to
$\min\\{\frac{1+e^{\varepsilon}}{2},\frac{3}{2}\\}f_{P}(t)=\frac{1+e^{\varepsilon}}{2}f_{P}(t)$
at $q_{1-\frac{1}{k}}\leq t\leq q_{1}$. Note that
$\tau(P,Q)=\left(1-\frac{e^{\varepsilon}}{2}\right)\frac{1}{k}$. $P^{\prime}$
and $Q^{\prime}$ are the distributions created by normalizing $\tilde{P}$ and
$\tilde{Q}$ by dividing by a factor of $1-\tau(P,Q)$. Now, we upper bound the
squared Hellinger distance between $P^{\prime}$ and $Q^{\prime}$ by the TV
distance (See Lemma A.4), to get that $H^{2}(P^{\prime},Q^{\prime})\leq
TV(P^{\prime},Q^{\prime})=O(\frac{\varepsilon}{k})$.

Substituting into the lower bound for sample complexity of distinguishing $P$
and $Q$, this tells us that for all $\varepsilon\in(0,1]$,
$SC_{\varepsilon}(P,Q)=\Omega\left(\frac{1}{\varepsilon\cdot\frac{1}{k}}\right)=\Omega(k/\varepsilon)$.

∎

###### Proof of Lemma 6.7.

Note that $P$ has bounded expectation (and hence, so does $Q$). Hence, we can
use the following form of the Wasserstein distance:

$\mathcal{W}(P,Q)=\int_{\mathbb{R}}|F_{P}(t)-F_{Q}(t)|dt.$

Now, given the settings of $P$ and $Q$, we can precisely write the forms of
their cumulative distribution function as follows. Note that for $L(P)\leq
t<q_{1/k}(P)$, we have that $|F_{P}(t)-F_{Q}(t)|=\frac{1}{2}F_{p}(t)$. For
$q_{1/k}\leq t\leq q_{1-\frac{1}{k}}$, we have
$|F_{P}(t)-F_{Q}(t)|=\frac{1}{2k}$. Finally, for $q_{1-\frac{1}{k}}\leq t\leq
q_{1}$, we have that $F_{P}(t)=1-\frac{1}{k}+\int_{q_{1-1/k}}^{t}f_{P}(t)dt$
and $F_{Q}(t)=1-\frac{3}{2k}+\frac{3}{2}\int_{q_{1-1/k}}^{t}f_{P}(t)dt$, which
gives us that
$F_{P}(t)-F_{Q}(t)=\frac{1}{2k}-\frac{1}{2}\int_{q_{1-1/k}}^{t}f_{P}(t)dt=\frac{1}{2}[1-F_{P}(t)]$.

Hence, we have that

$\displaystyle\mathcal{W}(P,Q)$
$\displaystyle=\int_{\mathbb{R}}|F_{P}(t)-F_{Q}(t)|dt$
$\displaystyle=\frac{1}{2}\int_{L(P)}^{q_{1/k}}F_{P}(t)dt+\int_{q_{1/k}}^{q_{1-\frac{1}{k}}}|F_{P}(t)-F_{Q}(t)|dt+\int_{q_{1-\frac{1}{k}}}^{q_{1}}|F_{P}(t)-F_{Q}(t)|dt$
$\displaystyle\geq\frac{1}{2}\int_{L(P)}^{q_{1/k}}F_{P}(t)dt+\frac{1}{2}\int_{q_{1-\frac{1}{k}}}^{q_{1}}[1-F_{P}(t)]dt+\frac{1}{2k}(q_{1-\frac{1}{k}}-q_{\frac{1}{k}})$
$\displaystyle=\frac{1}{2}\int_{q_{1-\frac{1}{k}}}^{q_{1}}\Big{|}F_{P}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)\Big{|}dt+\frac{1}{2}\int_{L(P)}^{q_{1/k}}\Big{|}F_{P}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)\Big{|}dt+\frac{1}{2k}(q_{1-\frac{1}{k}}-q_{\frac{1}{k}})$
$\displaystyle=\frac{1}{2k}(q_{1-\frac{1}{k}}-q_{1/k})+\frac{1}{2}\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$

∎

###  F.2 Omitted proofs in Section 6.1.2

###### Proof of Lemma 6.10.

The KL divergence is defined as $\int_{t:f_{Q}(t)>0}f_{P}(t)\log
f_{P}(t)/f_{Q}(t)dt$. This can be broken up into a sum over the dyadic
quantiles as:

$\displaystyle KL(P,Q)$ $\displaystyle=\sum_{i=2}^{\log
n-1}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}f_{P}(t)\log\frac{f_{P}(t)}{f_{Q}(t)}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}f_{P}(t)\log\frac{f_{P}(t)}{f_{Q}(t)}dt$
$\displaystyle+\sum_{i=\log
n}^{\infty}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}f_{P}(t)\log\frac{f_{P}(t)}{f_{Q}(t)}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}f_{P}(t)\log\frac{f_{P}(t)}{f_{Q}(t)}dt$
$\displaystyle=\sum_{i=2}^{\log
n-1}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}f_{P}(t)\log\frac{1}{1+\sqrt{\frac{2^{i}}{n}}}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}f_{P}(t)\log\frac{1}{1-\sqrt{\frac{2^{i}}{n}}}dt$
$\displaystyle+\sum_{i=\log
n}^{\infty}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}f_{P}(t)\log\frac{1}{1+\frac{1}{2}}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}f_{P}(t)\log\frac{1}{1-\frac{1}{2}}dt$
$\displaystyle=\sum_{i=2}^{\log
4n}\frac{1}{2^{i}}\left[\log\frac{1}{1+\sqrt{\frac{2^{i}}{n}}}+\log\frac{1}{1-\sqrt{\frac{2^{i}}{n}}}\right]+\sum_{i=\log
n}^{\infty}\frac{1}{2^{i}}\left[\log\frac{1}{1+\frac{1}{2}}+\log\frac{1}{1-\frac{1}{2}}\right]$
$\displaystyle\leq\sum_{i=2}^{\log
n-1}\frac{1}{2^{i}}\log\frac{1}{1-\frac{2^{i}}{n}}+O\left(\frac{1}{n}\right)$
$\displaystyle\leq\sum_{i=2}^{\log
n-1}\frac{1}{2^{i}}2\frac{2^{i}}{n}+O\left(\frac{1}{n}\right)$
$\displaystyle=O\left(\frac{\log n}{n}\right),$

where the third inequality from last is by the fact that the geometric series
$\sum_{i=\log n}^{\infty}\frac{1}{2^{i}}$ converges to $O(\frac{1}{n})$, the
second inequality from last is from the fact that $\frac{2^{i}}{n}<1/2$, and
$\log(1/(1-y))<2y$ for $0<y<1/2$. ∎

###### Proof of Lemma 6.11.

First, we recall the definition of the 1-Wasserstein distance in terms of the
cumulative distribution function.

$\displaystyle\mathcal{W}(P,Q)=\int_{\mathbb{R}}|F_{P}(t)-F_{Q}(t)|dt$

Fix any $2\leq i<\log n-1$. Observe that by construction, for all
$t\in[q_{1/2^{i}},q_{1-1/2^{i}})$ and for all
$t\in[q_{1-1/2^{i-1}},q_{1-1/2^{i}})$,
$|F_{P}(t)-F_{Q}(t)|\geq\sum_{j=i+1}^{\log
n-1}\frac{1}{\sqrt{2^{j}n}}+\frac{1}{2}\sum_{j=\log
n}^{\infty}\frac{1}{2^{j}}$. Similarly, fix any $\log n-1\leq i<\infty$.
Observe that for all $t\in[q_{1/2^{i}},q_{1-1/2^{i}})$, and for all
$t\in[q_{1-1/2^{i-1}},q_{1-1/2^{i}})$, we have that
$|F_{P}(t)-F_{Q}(t)|\geq\frac{1}{2}\sum_{j=i+1}^{\infty}\frac{1}{2^{j}}$.
Substituting the above bounds in the formula for the Wasserstein distance, we
get that

$\displaystyle\mathcal{W}(P,Q)$ $\displaystyle\geq\sum_{i=2}^{\log
n-2}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\left[\sum_{j=i+1}^{\log
n-2}\frac{1}{\sqrt{2^{j}n}}+\frac{1}{2}\sum_{j=\log
n-1}^{\infty}\frac{1}{2^{j}}\right]dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\left[\sum_{j=i+1}^{\log
n-2}\frac{1}{\sqrt{2^{j}n}}+\frac{1}{2}\sum_{j=\log
n-1}^{\infty}\frac{1}{2^{j}}\right]dt$ $\displaystyle+\sum_{i=\log
n-1}^{\infty}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\frac{1}{2}\sum_{j=i+1}^{\infty}\frac{1}{2^{j}}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\frac{1}{2}\sum_{j=i+1}^{\infty}\frac{1}{2^{j}}dt$

Pulling the summation over $j$ outside the integral and grouping terms,

$\displaystyle\mathcal{W}(P,Q)$ $\displaystyle\geq\sum_{i=2}^{\log
n-2}\Bigg{[}\sum_{j=i+1}^{\log
n-2}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\frac{1}{\sqrt{2^{j}n}}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\frac{1}{\sqrt{2^{j}n}}dt+\frac{1}{2}\sum_{j=\log
n-1}^{\infty}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\frac{1}{2^{j}}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\frac{1}{2^{j}}dt\Bigg{]}$
$\displaystyle+\frac{1}{2}\sum_{i=\log
n-1}^{\infty}\sum_{j=i+1}^{\infty}\Bigg{[}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\frac{1}{2^{j}}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\frac{1}{2^{j}}dt\Bigg{]}$
$\displaystyle=\sum_{i=2}^{\log
n-2}\left[({q_{1/2^{i-1}}}-q_{1/2^{i}})+(q_{1-1/2^{i}}-{q_{1-1/2^{i-1}}})\right]\left[\sum_{j=i+1}^{\log
n-2}\frac{1}{\sqrt{2^{j}n}}+\frac{1}{2}\sum_{j=\log
n-1}^{\infty}\frac{1}{2^{j}}\right]$ $\displaystyle+\sum_{i=\log
n-1}^{\infty}\left[({q_{1/2^{i-1}}}-q_{1/2^{i}})+(q_{1-1/2^{i}}-{q_{1-1/2^{i-1}}})\right]\frac{1}{2}\sum_{j=i+1}^{\infty}\frac{1}{2^{j}}$

Switching the order of summation (summing over $j$ first), and grouping terms,
we get

$\displaystyle\mathcal{W}(P,Q)$ $\displaystyle\geq\sum_{j=3}^{\log
n-2}\frac{1}{\sqrt{2^{j}n}}\sum_{i=2}^{j-1}\left[({q_{1/2^{i-1}}}-q_{1/2^{i}}+(q_{1-1/2^{i}}-{q_{1-1/2^{i-1}}})\right]$
$\displaystyle+\frac{1}{2}\sum_{j=\log
n-1}^{\infty}\frac{1}{2^{j}}\sum_{i=2}^{j-1}\left[({q_{1/2^{i-1}}}-q_{1/2^{i}}+(q_{1-1/2^{i}}-{q_{1-1/2^{i-1}}})\right]$

Telescoping the inner sums over $i$ we get that

$\displaystyle\mathcal{W}(P,Q)$ $\displaystyle\geq\sum_{j=3}^{\log
n-2}\frac{1}{\sqrt{2^{j}n}}\left[q_{1-1/2^{j-1}}-q_{1/2^{j-1}}\right]+\frac{1}{2}\sum_{j=\log
n-1}^{\infty}\frac{1}{2^{j}}\left[q_{1-1/2^{j-1}}-q_{1/2^{j-1}}\right]$

A change of variables (where we now set $j$ to $j-1$) then gives

$\displaystyle\mathcal{W}(P,Q)$
$\displaystyle\geq\frac{1}{\sqrt{2}}\sum_{j=2}^{\log
n-3}\frac{1}{\sqrt{2^{j}n}}\left[q_{1-1/2^{j}}-q_{1/2^{j}}\right]+\frac{1}{4}\sum_{j=\log
n-2}^{\infty}\frac{1}{2^{j}}\left[q_{1-1/2^{j}}-q_{1/2^{j}}\right]$
$\displaystyle\geq\frac{1}{4}\sum_{j=2}^{\log
n-1}\frac{1}{\sqrt{2^{j}n}}\left[q_{1-1/2^{j}}-q_{1/2^{j}}\right]+\frac{1}{4}\sum_{j=\log
n}^{\infty}\frac{1}{2^{j}}\left[q_{1-1/2^{j}}-q_{1/2^{j}}\right],$

where the last inequality is by pulling the first two terms from the summation
in second term to the summation in the first term, and using the fact that for
$j=\log n-2,j=\log n-1$, we have that $\frac{1}{4\cdot
2^{j}}\geq\frac{1}{2\sqrt{2}}\frac{1}{\sqrt{2^{j}n}}$

∎

###### Proof of Lemma 6.12.

We first state a theorem of Bobkov and Ledoux [BL19].

######  Theorem F.1 (Theorem 3.5, [BL19]).

There is an absolute constant $c>0$, such that for all distributions $P$ over
$\mathbb{R}$, for every $n\geq 1$,

$c(A_{n}+B_{n})\leq\mathbb{E}[\mathcal{W}(P,\hat{P}_{n}]\leq A_{n}+B_{n}.$

where

$A_{n}=2\int_{F(t)[1-F(t)]\leq\frac{1}{4n}}F(t)[1-F(t)]dt,$

and

$B_{n}=\frac{1}{\sqrt{n}}\int_{F(t)[1-F(t)]\geq\frac{1}{4n}}\sqrt{F(t)[1-F(t)]}dt.$

Now, we are ready to prove the main theorem. Fix natural number $i\geq 2$.
Restricted to $t\leq q_{1/2}$, $F_{P}(t)(1-F_{P}(t))$ is an increasing
function, and hence for $t\in[q_{1/2^{i}},q_{1/2^{i-1}}]$, we have that
$F_{P}(t)(1-F_{P}(t))\leq\frac{1}{2^{i-1}}[1-\frac{1}{2^{i-1}}]$.

Similarly, restricted to $t>q_{1/2}$, $F_{P}(t)(1-F_{P}(t))$ is a decreasing
function, and hence for $t\in[1-q_{1/2^{i-1}},q_{1-1/2^{i}}]$, we have that
$F_{P}(t)(1-F_{P}(t))\leq\frac{1}{2^{i-1}}[1-\frac{1}{2^{i-1}}]$.

Using this, we can now upper bound the expected Wasserstein distance between
$P$ and its empirical distribution using Theorem F.1. Hence, we upper bound
the terms $B_{n}$ and $A_{n}$. We start by upper bounding $B_{n}$. Note that
for all $t\not\in[q_{\frac{1}{4n}},q_{1-\frac{1}{4n}}]$, we have that
$F_{P}(t)(1-F_{P}(t))\leq\frac{1}{4n}$. Hence,

$\displaystyle B_{n}$
$\displaystyle=\frac{1}{\sqrt{n}}\int_{F_{P}(t)[1-F_{P}(t)]\geq\frac{1}{4n}}\sqrt{F_{P}(t)[1-F_{P}(t)]}dt$
$\displaystyle\leq\frac{1}{\sqrt{n}}\int_{q_{\frac{1}{4n}}}^{q_{1-\frac{1}{4n}}}\sqrt{F_{P}(t)[1-F_{P}(t)]}dt$
$\displaystyle\leq\sum_{i=2}^{\log
4n}\frac{1}{\sqrt{n}}\left[\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\sqrt{F_{P}(t)[1-F_{P}(t)]}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\sqrt{F_{P}(t)[1-F_{P}(t)]}dt\right]$
$\displaystyle\leq\sum_{i=2}^{\log
4n}\frac{1}{\sqrt{n}}\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\sqrt{\frac{1}{2^{i-1}}\left[1-\frac{1}{2^{i-1}}\right]}dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\sqrt{\frac{1}{2^{i-1}}\left[1-\frac{1}{2^{i-1}}\right]}dt$
$\displaystyle=\sum_{i=2}^{\log
4n}\frac{1}{\sqrt{n}}\sqrt{\frac{1}{2^{i-1}}\left[1-\frac{1}{2^{i-1}}\right]}\left[q_{1/2^{i-1}}-q_{1/2^{i}}+q_{1-1/2^{i}}-q_{1-1/2^{i-1}}\right]$
$\displaystyle\leq\sum_{i=2}^{\log
4n}\frac{2}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$
$\displaystyle=\sum_{i=2}^{\log
n-1}\frac{2}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n}^{\log 4n}\frac{2}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$
$\displaystyle\leq\sum_{i=2}^{\log
n-1}\frac{2}{\sqrt{2^{i}n}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]+\sum_{i=\log
n}^{\log 4n}\frac{4}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right],$

where the last inequality is because for $i\leq\log(4n)$, we have that
$\frac{1}{n}\leq\frac{4}{2^{i}}$.

Next, we bound $A_{n}$. Note that for all $t\geq q_{1/2n}$ and for all $t\leq
q_{1-\frac{1}{2n}}$, we have that $F_{P}(t)(1-F_{P}(t))\not\leq\frac{1}{4n}$.
Hence,

$\displaystyle A_{n}$
$\displaystyle=2\int_{F_{P}(t)[1-F_{P}(t)]\leq\frac{1}{4n}}F_{P}(t)[1-F_{P}(t)]dt$
$\displaystyle\leq
2\left[\int_{-\infty}^{q_{\frac{1}{2n}}}F_{P}(t)[1-F_{P}(t)]dt+\int_{q_{1-\frac{1}{2n}}}^{\infty}F_{P}(t)[1-F_{P}(t)]dt\right]$
$\displaystyle=\sum_{i=1+\log
2n}^{\infty}2\left[\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}F_{P}(t)[1-F_{P}(t)]dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}F_{P}(t)[1-F_{P}(t)]dt\right]$
$\displaystyle\leq\sum_{i=1+\log
2n}^{\infty}2\left[\int_{q_{1/2^{i}}}^{q_{1/2^{i-1}}}\frac{1}{2^{i-1}}\left[1-\frac{1}{2^{i-1}}\right]dt+\int_{q_{1-1/2^{i-1}}}^{q_{1-1/2^{i}}}\frac{1}{2^{i-1}}\left[1-\frac{1}{2^{i-1}}\right]dt\right]$
$\displaystyle=\sum_{i=1+\log
2n}^{\infty}\frac{2}{2^{i-1}}\left[1-\frac{1}{2^{i-1}}\right]\left[q_{1/2^{i-1}}-q_{1/2^{i}}+q_{1-1/2^{i}}-q_{1-1/2^{i-1}}\right]$
$\displaystyle\leq\sum_{i=1+\log
2n}^{\infty}\frac{4}{2^{i}}\left[q_{1-1/2^{i}}-q_{1/2^{i}}\right]$

Then, using the upper bound in Theorem F.1, substituting in the bounds for
$A_{n}$ and $B_{n}$, and simplifying, we get the claim. ∎

###### Proof of Claim 6.13.

By the definition of Wasserstein distance and restrictions of distributions,
we have that

$\displaystyle\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$
$\displaystyle=\int_{a}^{b}\left|F_{\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)\right|dt$
$\displaystyle=\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\left|F_{\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)\right|dt$
$\displaystyle=\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\left|F_{\hat{P}_{n}}(t)-F_{P}(t)\right|dt\leq\mathcal{W}(P,\hat{P_{n}})$

∎

###  F.3 Omitted Proofs in Section 6.2

Before going into the proofs, we state the standard Chernoff concentration
bound that we will use multiple times.

######  Theorem F.2 (Binomial Concentration).

Let $X\sim Bin(n,p)$ with expectation $\mu=np$, and $0<\delta<1$. Then,

$\Pr(|X-\mu|\geq\delta\mu)\leq 2e^{\frac{-\delta^{2}\mu}{3}}.$

###### Proof of Lemma 6.16.

$\displaystyle\mathcal{W}(P,P^{DP})$
$\displaystyle=\int_{t}|F_{P}(t)-F_{P^{DP}}(t)|dt$ (13)
$\displaystyle\leq\int_{t=a}^{q_{1/k}}|F_{P}(t)-F_{P^{DP}}(t)|dt+\int_{t=q_{1/k}}^{q_{1-1/k}}|F_{P}(t)-F_{P^{DP}}(t)|dt+\int_{t=q_{1-1/k}}^{b}|F_{P}(t)-F_{P^{DP}}(t)|dt$
(14)

Note that for all $t\in[q_{1/k},q_{1-1/k}]$, we have that the cumulative
distribution functions of $P$ and its restricted version are identical and
likewise for $P^{DP}$. Additionally, the cumulative density functions for the
restricted versions of the two distributions are identical to each other
outside of this interval. Hence, we can simplify the middle term in the RHS of
the inequality above as follows:

$\displaystyle\int_{t=q_{1/k}}^{q_{1-1/k}(P)}|F_{P}(t)-F_{P^{DP}}(t)|dt=\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$

Next, we reason about the remaining terms.

Consider the term $\int_{t=a}^{q_{1/k}}|F_{P}(t)-F_{P^{DP}}(t)|dt$. First,
condition on the event in Theorem E.3 (on the accuracy of the private
quantiles for the empirical distribution), which tells us that with
probability at least $1-\beta$, we have for all $r\in[k]$, that

$\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}}\leq\tilde{q}_{\frac{2r-1}{2k}}\leq\hat{q}_{\frac{2r-1}{2k}+\frac{1}{4k}},$
(15)

which implies in particular that
$\hat{q}_{1/4k}\leq\tilde{q}_{1/2k}\leq\hat{q}_{3/4k}$.

Next, we argue that $\hat{q}_{1/4k}\geq q_{1/8k}$ with high probability. By
the definition of quantiles, we have that $Pr_{y\sim
P}(y<q_{1/8k})<\frac{1}{8k}$. The number of entries in the dataset ${\bf x}$
less than $q_{1/8k}$ is hence a Binomial with mean less than $\frac{n}{8k}$,
and hence, we have by Theorem F.2 (with $\delta$ set to $0.9)$ that with
probability at least $1-\beta$, the number of entries in the dataset less than
$q_{1/8k}$ is at most $1.9\frac{n}{8k}<\frac{n}{4k}$, which means the total
mass less than $q_{\frac{1}{8k}}$ in the empirical distribution is less than
$\frac{1}{4k}$. This implies that $\hat{q}_{1/4k}\geq q_{1/8k}$ by the
definition of quantiles.

Additionally, note that for all $t<q_{1/k}$, $F_{P}(t)<\frac{1}{k}$. The
number of entries in the dataset ${\bf x}$ that are less than $q_{1/k}$ is
hence a Binomial with success probability less than $\frac{1}{k}$. By Theorem
F.2, we can again argue that with probability at least $1-\beta$, there is a
constant $c^{\prime}$ such that the total mass of the empirical distribution
on values less than $q_{1/k}$ is less than $\frac{c^{\prime}}{k}$. Hence,
$q_{1/k}\leq\hat{q}_{c^{\prime}/k}$. This implies by Equation 15, that
$q_{1/k}\leq\tilde{q}_{c/k}$ for some constant $c$. Hence, for all
$t<q_{1/k}$, we have that $F_{P^{DP}}(t)\leq\frac{c}{k}$.

Hence, taking a union bound, with probability at least $1-O(\beta)$,

$\displaystyle\int_{t=a}^{q_{1/k}}|F_{P}(t)-F_{P^{DP}}(t)|dt$
$\displaystyle=\int_{t=a}^{\tilde{q}_{1/2k}}|F_{P}(t)-F_{P^{DP}}(t)|dt+\int_{\tilde{q}_{1/2k}}^{q_{1/k}}|F_{P}(t)-F_{P^{DP}}(t)|dt$
$\displaystyle\leq\int_{t=a}^{\tilde{q}_{1/2k}}|F_{P}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)|dt+\int_{q_{1/8k}}^{q_{1/k}}|F_{P}(t)-\frac{c}{k}|dt$
$\displaystyle\leq\int_{t=a}^{\tilde{q}_{1/2k}}|F_{P}(x)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)|dt+\int_{q_{1/8k}}^{q_{1/k}}|F_{P}(t)-8cF_{P}(t)|dt$
$\displaystyle\leq(1-8c)\left[\int_{t=a}^{\tilde{q}_{1/2k}}|F_{P}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)|dt+\int_{q_{1/8k}}^{q_{1/k}}|F_{P}(t)|dt\right]$
$\displaystyle\leq(1-8c)\left[\int_{t=a}^{\tilde{q}_{1/2k}}|F_{P}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)|dt+\int_{q_{1/8k}}^{q_{1/k}}|F_{P}(t)-F_{P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)|dt\right]$
$\displaystyle\leq
2(1-8c)\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$

By a symmetric argument, we also have that with probability at least
$1-O(\beta)$,

$\int_{t=q_{1-1/k}}^{b}|F_{P}(t)-F_{P^{DP}}(t)|dt\leq
2(1-8c)\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}).$

Taking a union bound to ensure that all terms in Equation 14 are bounded as
required, the proof is complete. ∎

###### Proof of Lemma 6.17.

First, we condition on the event in Corollary E.3 (on the accuracy of
differentially private quantile estimates) that for all $r\in[k]$,

$\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}}\leq\tilde{q}_{r}\leq\hat{q}_{\frac{2r-1}{2k}+\frac{1}{4k}},$

note that this event happens with probability at least $1-\beta$ over the
randomness of the algorithm.

Observe that this implies that $F_{DP}$ increases by $\frac{1}{k}$ somewhere
in the range
$[\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}},\hat{q}_{\frac{2r-1}{2k}+\frac{1}{4k}}]$
(for all $r\in[k]$) and remains constant outside these intervals.

Now, we show that for all $t\in[a,b]$, we have that
$|F_{P^{DP}}(t)-F_{\hat{P}_{n}}(t)|\leq\frac{2}{k}$.

If there exists $t\in[a,\hat{q}_{\frac{1}{4k}})$, we have that
$F_{P_{DP}}(t)=0$, and $F_{\hat{P}_{n}}(t)\leq\frac{1}{4k}$, which implies
that $|F_{DP}(t)-F_{\hat{P}_{n}}(t)|\leq\frac{1}{4k}$. If there exists no such
$t$, then we have that $a=\hat{q}_{\frac{1}{4k}}$, and the corresponding
interval collapses to a single point (which will fall in another interval
considered below).

Next, fix any $r\in[k-1]$. Note that if there exists
$t\in[\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}},\hat{q}_{\frac{2r+1}{2k}-\frac{1}{4k}})$,
we have for all such $t$ that $\frac{r-1}{k}\leq F_{DP}(t)<\frac{r}{k}$, and
$\frac{2r-1}{2k}-\frac{1}{4k}\leq
F_{\hat{P}_{n}}(t)\leq\frac{2r+1}{2k}+\frac{1}{4k}$. This implies that for all
such $t$, $|F_{DP}(t)-F_{\hat{P}_{n}}(t)|\leq\frac{2}{k}$. If there exists no
such $t$, then we have that
$\hat{q}_{\frac{2r-1}{2k}-\frac{1}{4k}}=\hat{q}_{\frac{2r+1}{2k}-\frac{1}{4k}}$,
and this $r$ is not relevant since the corresponding interval collapses to a
single point (that is considered in another interval).

Finally, for $t\in[\hat{q}_{\frac{2k-1}{2k}},b]$, we have that
$F_{P_{DP}}(t)\geq 1-\frac{1}{k}$, and $F_{\hat{P}_{n}}(t)\geq
1-\frac{1}{2k}$, so we have that
$|F_{DP}(t)-F_{\hat{P}_{n}}(t)|\leq\frac{1}{k}$.

Note that every $t\in[a,b]$ is considered in some interval above and hence we
have shown that for all $t\in[a,b]$, we have that
$|F_{P^{DP}}(t)-F_{\hat{P}_{n}}(t)|\leq\frac{2}{k}$.

Finally, using the formula for Wasserstein distance (and the definition of a
restriction), we have that

$\displaystyle\mathcal{W}(\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$
$\displaystyle=\int_{a}^{b}\left|F_{\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)-F_{P^{DP}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}}(t)\right|dt$
(16)
$\displaystyle=\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\left|F_{P}(t)-F_{P^{DP}}(t)\right|dt$
(17)
$\displaystyle\leq\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\frac{2}{k}dt$
(18) $\displaystyle\leq\frac{2}{k}\left(q_{1-1/k}-q_{1/k}\right)$ (19)

∎

Before the proof of Claim 6.18, we state the following variance-dependent
version of the DKW inequality that uniformly bounds the absolute difference in
CDFs between the true and empirical distribution.

######  Theorem F.3 (See for example Theorem 1.2 in [BM23]).

Fix $n>0$. There are absolute constants $c_{0},c_{1}$ such that for all
$\Delta\geq\frac{c_{0}\log\log n}{n}$,

$\displaystyle\Pr\left[\sup_{t:F_{P}(t)(1-F_{P}(t))\geq\Delta}\Big{|}F_{P}(t)-F_{\hat{P}_{n}}(t)\Big{|}\geq\sqrt{\Delta\cdot{F(t)(1-F(t)}}\right]\leq
2e^{-c_{1}\Delta n}$

We also state the following lemma on Binomial random variables, which is a
simple consequence of a Lemma by Bobkov and Ledoux [BL19].

######  Lemma F.4 (Lemma 3.8 in [BL19]).

Let $S_{n}=\sum_{i=1}^{n}\eta_{i}$ be the sum of $n$ independent Bernoulli
random variables with $\Pr[\eta_{i}=1]=p$ and $\Pr[\eta_{i}=0]=q=1-p$ (for all
$i$). Also assume $p\in[\frac{1}{n},1-\frac{1}{n}]$. Then, for some
sufficiently small constant $c$,

$\displaystyle c\sqrt{npq}\leq\mathbb{E}[|S_{n}-np|]\leq\sqrt{npq}$

###### Proof of Claim 6.18.

Now, by the formula for Wasserstein distance, the definition of restriction,
and Fubini’s theorem, we have that

$\displaystyle\mathbb{E}[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})]=\mathbb{E}\Big{[}\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\Big{|}F_{P}(t)-F_{\hat{P}_{n}}(t)\Big{|}dt\Big{]}=\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\mathbb{E}\Big{[}\Big{|}F_{P}(t)-F_{\hat{P}_{n}}(t)\Big{|}\Big{]}dt$

By Lemma F.4, using the fact that
$F_{\hat{P}_{n}}(t)=\sum_{i=1}^{n}\mathrm{1}[x_{i}\leq t]$, where each term in
the sum is an independent Bernoulli random variable with expectation
$F_{P}(t)$, with $q_{\frac{1}{k}}\leq t<q_{1-\frac{1}{k}}$ (ensuring that the
conditions of the lemma are met), we get that
$\mathbb{E}\Big{[}\Big{|}F_{P}(t)-F_{\hat{P}_{n}}(t)\Big{|}\Big{]}\geq
c\sqrt{\frac{F_{P}(t)[1-F_{P}(t)]}{n}}$, which gives

$\displaystyle\mathbb{E}[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})]$
$\displaystyle\geq
c\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\sqrt{\frac{F_{P}(t)[1-F_{P}(t)]}{n}}dt$

Now, consider the random variable
$\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$.
Note that $\frac{1}{k}\geq\frac{c_{3}\log\frac{n}{\beta}}{n}$ (for an
appropriately chosen $c_{3}$), and so we are in the regime where we can apply
Theorem F.3 for an appropriately chosen $\Delta$.

In particular, we have that for $t\in[q_{\frac{1}{k}},q_{1-\frac{1}{k}})$,
$F_{P}(t)\in[\frac{1}{k},1-\frac{1}{k})$.

Setting $\Delta=\frac{\log\frac{n}{\beta}}{c_{1}n}$, we have that $\Delta\geq
c_{0}\frac{\log\log n}{n}$, and $\Delta\leq\frac{1}{2k}$ (the second
inequality for sufficiently large $c_{3}$). In particular, this implies for
$t\in[q_{\frac{1}{k}},q_{1-\frac{1}{k}})$, $F_{P}(t)\in[2\Delta,1-2\Delta)$,
which implies that $F_{P}(t)(1-F_{P}(t))\geq\Delta$, as long as
$n>c_{4}\log\frac{n}{\beta}$ for some sufficiently large constant $c_{4}$.

Now, using Theorem F.3, we have that with probability at least
$1-2e^{-c_{1}\frac{\log\frac{n}{\beta}}{c_{1}n}n}\geq 1-O(\beta)$,

$\sup_{t\in[q_{\frac{1}{k}},q_{1-\frac{1}{k}})}\Big{|}F_{P}(t)-F_{\hat{P}_{n}}(t)\Big{|}\leq\sqrt{\frac{\log\frac{n}{\beta}}{c_{1}n}{F_{P}(t)(1-F_{P}(t))}}$

Condition on this for the rest of the proof. Then, we can write the following
set of equations.

$\displaystyle\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})$
$\displaystyle=\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}|F_{P}(t)-F_{\hat{P}_{n}}(t)|dt$
$\displaystyle\leq\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\sqrt{\frac{\log\frac{n}{\beta}}{c_{1}n}{F_{P}(t)(1-F_{P}(t))}}dt$
$\displaystyle\leq\sqrt{c_{5}\log\frac{n}{\beta}}\int_{q_{\frac{1}{k}}}^{q_{1-\frac{1}{k}}}\sqrt{\frac{F_{P}(t)(1-F_{P}(t))}{n}}dt$
$\displaystyle\leq\sqrt{c_{6}\log\frac{n}{\beta}}\mathbb{E}[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})]$

as required.

∎

###  F.4 Local Minimality in the One-Dimensional Setting

In this subsection, we argue that the instance-optimal algorithm discussed in
Section 6.2 is also locally-minimal (See Section 3.2 for a discussion of local
minimality).

First, we state a corollary of our upper bound for continuous distributions,
Theorem 6.14. This corollary follows by discretizing the distribution and
applying the previous upper bound to the discretized distribution. The
parameters of the discretized distribution are related to that of the original
distribution via simple coupling arguments.

######  Corollary F.5.

Fix $\varepsilon,\beta\in(0,1]$, $a,b\in\mathbb{R}$, $n\in\mathbb{N}$. Let $P$
be any continuous distribution supported on $[a,b]$. Consider any
$\gamma<b-a\in\mathbb{R}$ (such that $\gamma$ divides $b-a$), and let
$n>c_{2}\frac{\log^{4}\frac{b-a}{\gamma\beta\varepsilon}}{\varepsilon}$ for
some sufficiently large constant $c_{2}$. Then, there exists an algorithm,
that when given inputs ${\bf x}\sim P^{n}$, privacy parameter $\varepsilon$,
interval end points $a,b$, granularity $\gamma$, and access to algorithm
$A_{quant}$, outputs a distribution $P^{DP}$ such that with probability at
least $1-O(\beta)$ over the randomness of ${\bf x}$ and the algorithm,

$\mathcal{W}(P,P^{DP})=O\left(\sqrt{\log
n}\mathbb{E}\left[\mathcal{W}(P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}},\hat{P}_{n}|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}}\right]+\mathcal{W}(P,P|_{q_{\frac{1}{k}},q_{1-\frac{1}{k}}})+\frac{1}{k}\left(q_{1-1/k}-q_{1/k}\right)\right)+\gamma$

where $\hat{P}_{n}$ is the uniform distribution on ${\bf x}$, $q_{\alpha}$
represents the $\alpha$-quantile of distribution $P$, and
$k=\lceil\frac{\varepsilon
n}{4c_{3}\log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}\rceil$, where
$c_{3}$ is a sufficiently large constant.

We state a lemma of Ledoux and Bobkov that we will use in the main proof of
this section.

######  Lemma F.6 (Lemma 3.8 in [BL19]).

Let $S_{n}=\sum_{i=1}^{n}\eta_{i}$ be the sum of $n$ independent Bernoulli
random variables with $\Pr[\eta_{i}=1]=p$ and $\Pr[\eta_{i}=0]=q=1-p$ (for all
$i$). Then, for some sufficiently small constant $c$,

$\displaystyle
c\min\\{2npq,\sqrt{npq}\\}\leq\mathbb{E}[|S_{n}-np|]\leq\min\\{2npq,\sqrt{npq}\\}$

Now, we are ready to state and prove the local minimality result. Note that
the statement will reference the rates defined by Equation 1 in the
introduction.

######  Theorem F.7.

Let $a,b\in\mathbb{R}$, $\gamma\in\mathbb{R}$. For any continuous distribution
$P$ over $[a,b]$ with a density, let $N(P)=\\{Q:D_{\infty}(P,Q)\leq\log 2\\}$.
Fix $\beta,\gamma,\varepsilon\in(0,1]$, and let
$n=\Omega\left(\frac{\log^{4}\frac{b-a}{\gamma\varepsilon}}{\varepsilon}\right)$,
with $n^{\prime}=\frac{n}{c_{7}\log n\log^{3}\frac{b-a}{\gamma\varepsilon}}$
for some constant $c_{7}$. There exists an algorithm $\mathcal{A}$ such that
for all continuous distributions $P$, for all algorithms
$\mathcal{A}^{\prime}$, there exists a distribution $Q\in N(P)$ such that

$R_{\mathcal{A},n}(Q)\leq
O(\operatorname{polylog}n)\cdot\max\\{R_{\mathcal{A}^{\prime},\lceil
n^{\prime}\rceil}(Q),R_{\mathcal{A}^{\prime},\lfloor
n^{\prime}/4\rfloor}(Q)\\}+\gamma,$

###### Proof.

Let $k=\lceil\frac{\varepsilon
n}{4c_{3}\log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}\rceil$, and set
$n^{\prime}=\frac{2n}{c_{4}\log^{3}\frac{b-a}{\beta\gamma}\log\frac{n}{\beta}}$
for a sufficiently large constant $c_{4}$. Then, by Corollary F.5 with
appropriately chosen $\beta$ we have that with probability at least 0.95, for
any distribution $Q$ (and hence particularly any distribution $Q\in N(P)$,

$\displaystyle\mathcal{W}(Q,\mathcal{A}(\hat{Q}_{n})$
$\displaystyle=O\Bigg{(}\frac{1}{\varepsilon
n^{\prime}}\left(q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)-q_{\frac{2}{C\varepsilon
n^{\prime}}}(Q)\right)+\mathcal{W}(Q,Q|_{q_{\frac{2}{C\varepsilon
n^{\prime}}(Q)},q_{1-\frac{2}{C\varepsilon n^{\prime}}}(Q)})$
$\displaystyle+\sqrt{\log
n}\mathbb{E}\left[\mathcal{W}\left(Q|_{q_{\frac{2}{C\varepsilon
n^{\prime}}}(Q),q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)},\hat{Q}_{n}|_{q_{\frac{2}{C\varepsilon
n^{\prime}}}(Q),q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)}\right)\right]\Bigg{)}+\gamma,$

where $C$ is the constant referenced in Theorem 6.3. We will show that for
distribution $P$, each of the corresponding distribution-dependent terms is
closely related to the terms for $Q$.

First, consider $\frac{1}{\varepsilon
n^{\prime}}\left(q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)-q_{\frac{2}{C\varepsilon n^{\prime}}}(Q)\right)$. Firstly,
note that for all $\alpha\in(0,1)$, $q_{\alpha}(P)\geq q_{\alpha/2}(Q)$, and
$q_{\alpha}(P)\leq q_{2\alpha}(Q)$, since $D_{\infty}(P,Q)\leq\ln 2$, which
implies that $\frac{1}{2}F_{Q}(t)\leq F_{P}(t)\leq 2F_{Q}(t)$ for all
$t\in\mathbb{R}$. Similarly, note that for all $\alpha\in(0,1)$,
$q_{1-\alpha}(P)\geq q_{1-2\alpha}(Q)$, and $q_{1-\alpha}(P)\leq
q_{1-\frac{1}{2}\cdot\alpha}(Q)$. Hence, we have that

$\displaystyle\frac{1}{\varepsilon n^{\prime}}\left(q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)-q_{\frac{2}{C\varepsilon n^{\prime}}}(Q)\right)$
$\displaystyle\leq\frac{1}{\varepsilon
n^{\prime}}\left(q_{1-\frac{1}{C\varepsilon
n^{\prime}}}(P)-q_{\frac{1}{C\varepsilon n^{\prime}}}(P)\right)$

Next, consider $\mathcal{W}(P,P|_{q_{\frac{1}{C\varepsilon
n}}(P),q_{1-\frac{1}{C\varepsilon n}}(P)})$. Recall that
$q_{\frac{1}{C\varepsilon n}}(P)\leq q_{\frac{2}{C\varepsilon n}}(Q)$, and
$q_{1-\frac{1}{C\varepsilon n}}(P)\geq q_{1-\frac{2}{C\varepsilon n}}(Q)$.
Then, (noting that $L(P)=L(Q)$ and $q_{1}(P)=q_{1}(Q)$), we have that

$\displaystyle\mathcal{W}(Q,Q|_{q_{\frac{2}{C\varepsilon
n^{\prime}}}(Q),q_{1-\frac{2}{C\varepsilon n^{\prime}}}(Q)})$
$\displaystyle=\int_{L(Q)}^{q_{\frac{2}{C\varepsilon
n^{\prime}}}(Q)}F_{Q}(t)dt+\int_{q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)}^{q_{1}(Q)}|1-F_{Q}(t)|dt$ $\displaystyle\leq
2\int_{L(Q)}^{q_{\frac{2}{C\varepsilon
n^{\prime}}}(Q)}F_{P}(t)dt+2\int_{q_{1-\frac{1}{C\varepsilon
n^{\prime}}}(Q)}^{q_{1}(Q)}|1-F_{P}(t)|dt$ $\displaystyle\leq
2\int_{L(P)}^{q_{\frac{4}{C\varepsilon
n^{\prime}}}(P)}F_{P}(t)dt+2\int_{q_{1-\frac{1}{4C\varepsilon
n^{\prime}}}(P)}^{q_{1}(P)}|1-F_{P}(t)|dt$
$\displaystyle=2\mathcal{W}(P,P|_{q_{\frac{4}{C\varepsilon
n^{\prime}}}(P),q_{1-\frac{4}{C\varepsilon n}}(P)})$

Finally, consider $\frac{1}{\sqrt{\log
n}}\mathbb{E}\left[\mathcal{W}(P|_{q_{\frac{1}{C\varepsilon
n}(P)},q_{1-\frac{1}{C\varepsilon
n}}(P)},\hat{P}_{n}|_{q_{\frac{1}{C\varepsilon
n}(P)},q_{1-\frac{1}{C\varepsilon n}}(P)})\right]$. By Fubini’s theorem and
applying both inequalities in Lemma F.6, we have that

$\displaystyle\mathbb{E}\left[\mathcal{W}(Q|_{q_{\frac{2}{C\varepsilon
n^{\prime}}(Q)},q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)},\hat{Q}_{n}|_{q_{\frac{2}{C\varepsilon
n^{\prime}}(Q)},q_{1-\frac{2}{C\varepsilon n^{\prime}}}(Q)})\right]$
$\displaystyle=\int_{q_{\frac{2}{C\varepsilon
n^{\prime}}(Q)}}^{q_{1-\frac{2}{C\varepsilon
n^{\prime}}}(Q)}\mathbb{E}[|F_{Q}(t)-F_{\hat{Q}_{n}}(t)|]dt$
$\displaystyle\leq\int_{q_{\frac{1}{C\varepsilon
n^{\prime}}(P)}}^{q_{1-\frac{1}{C\varepsilon
n^{\prime}}}(P)}\mathbb{E}[|F_{Q}(t)-F_{\hat{Q}_{n}}(t)|]dt$
$\displaystyle\leq\int_{q_{\frac{1}{C\varepsilon
n^{\prime}}(P)}}^{q_{1-\frac{1}{C\varepsilon
n^{\prime}}}(P)}\min\left\\{2F_{Q}(t)[1-F_{Q}(t)],\sqrt{\frac{F_{Q}(t)[1-F_{Q}(t)]}{n}}\right\\}dt$
$\displaystyle\leq\int_{q_{\frac{1}{C\varepsilon
n^{\prime}}(P)}}^{q_{1-\frac{1}{C\varepsilon