We examine the extent to which sublinear-sample property testing and
estimation applies to settings where samples are independently but not
identically distributed. Specifically, we consider the following distributional
property testing framework: Suppose there is a set of distributions over a
discrete support of size $k$, $\textbf{p}_1, \textbf{p}_2,\ldots,\textbf{p}_T$,
and we obtain $c$ independent draws from each distribution. Suppose the goal is
to learn or test a property of the average distribution,
$\textbf{p}_{\mathrm{avg}}$. This setup models a number of important practical
settings where the individual distributions correspond to heterogeneous
entities -- either individuals, chronologically distinct time periods,
spatially separated data sources, etc. From a learning standpoint, even with
$c=1$ samples from each distribution, $\Theta(k/\varepsilon^2)$ samples are
necessary and sufficient to learn $\textbf{p}_{\mathrm{avg}}$ to within error
$\varepsilon$ in TV distance. To test uniformity or identity -- distinguishing
the case that $\textbf{p}_{\mathrm{avg}}$ is equal to some reference
distribution, versus has $\ell_1$ distance at least $\varepsilon$ from the
reference distribution, we show that a linear number of samples in $k$ is
necessary given $c=1$ samples from each distribution. In contrast, for $c \ge
2$, we recover the usual sublinear sample testing of the i.i.d. setting: we
show that $O(\sqrt{k}/\varepsilon^2 + 1/\varepsilon^4)$ samples are sufficient,
matching the optimal sample complexity in the i.i.d. case in the regime where
$\varepsilon \ge k^{-1/4}$. Additionally, we show that in the $c=2$ case, there
is a constant $\rho > 0$ such that even in the linear regime with $\rho k$
samples, no tester that considers the multiset of samples (ignoring which
samples were drawn from the same $\textbf{p}_i$) can perform uniformity
testing.

在非独立同分布的样本情况下，研究子线性样本属性测试和估计在哪些情形适用；给定一组分布，考虑学习或测试平均分布的属性，在某些情况下需要 $\Theta (k/\varepsilon^2)$ 样本；对于均匀性或相似性的测试，给定 $c=1$ 个样本，需要线性数量级的 $k$ 样本；$c \geq 2$ 时，恢复了独立同分布的亚线性样本测试，需要 $O (\sqrt {k}/\varepsilon^2 + 1/\varepsilon^4)$ 样本，且在 $c=2$ 的情况下，即使是线性数量级的 $\rho k$ 样本，也不能进行均匀性测试。

非同分布样本的测试

Testing with Non-identically Distributed Samples

A centrally differentially private algorithm maps raw data to differentially
private outputs. In contrast, a locally differentially private algorithm may
only access data through public interaction with data holders, and this
interaction must be a differentially private function of the data. We study the
intermediate model of pan-privacy. Unlike a locally private algorithm, a
pan-private algorithm receives data in the clear. Unlike a centrally private
algorithm, the algorithm receives data one element at a time and must maintain
a differentially private internal state while processing this stream.
First, we show that pure pan-privacy against multiple intrusions on the
internal state is equivalent to sequentially interactive local privacy. Next,
we contextualize pan-privacy against a single intrusion by analyzing the sample
complexity of uniformity testing over domain $[k]$. Focusing on the dependence
on $k$, centrally private uniformity testing has sample complexity
$\Theta(\sqrt{k})$, while noninteractive locally private uniformity testing has
sample complexity $\Theta(k)$. We show that the sample complexity of pure
pan-private uniformity testing is $\Theta(k^{2/3})$. By a new $\Omega(k)$ lower
bound for the sequentially interactive setting, we also separate pan-private
from sequentially interactive locally private and multi-intrusion pan-private
uniformity testing.

该论文研究了中心差分隐私算法、本地差分隐私算法和中间模型的全局隐私算法，分析了其对单次和多次干扰的影响，并通过分析样本复杂度，提供了纯全局隐私均匀性测试的近似最优算法。

全局隐私均匀性检验

Pan-Private Uniformity Testing

We study the problem of testing identity against a given distribution with a
focus on the high confidence regime. More precisely, given samples from an
unknown distribution $p$ over $n$ elements, an explicitly given distribution
$q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em
with probability at least $1-\delta$}, whether the distributions are identical
versus $\varepsilon$-far in total variation distance. Most prior work focused
on the case that $\delta = \Omega(1)$, for which the sample complexity of
identity testing is known to be $\Theta(\sqrt{n}/\epsilon^2)$. Given such an
algorithm, one can achieve arbitrarily small values of $\delta$ via black-box
amplification, which multiplies the required number of samples by
$\Theta(\log(1/\delta))$.
We show that black-box amplification is suboptimal for any $\delta = o(1)$,
and give a new identity tester that achieves the optimal sample complexity. Our
new upper and lower bounds show that the optimal sample complexity of identity
testing is \[
\Theta\left( \frac{1}{\epsilon^2}\left(\sqrt{n \log(1/\delta)} +
\log(1/\delta) \right)\right) \] for any $n, \varepsilon$, and $\delta$. For
the special case of uniformity testing, where the given distribution is the
uniform distribution $U_n$ over the domain, our new tester is surprisingly
simple: to test whether $p = U_n$ versus $d_{\mathrm TV}(p, U_n) \geq
\varepsilon$, we simply threshold $d_{\mathrm TV}(\widehat{p}, U_n)$, where
$\widehat{p}$ is the empirical probability distribution. The fact that this
simple "plug-in" estimator is sample-optimal is surprising, even in the
constant $\delta$ case. Indeed, it was believed that such a tester would not
attain sublinear sample complexity even for constant values of $\varepsilon$
and $\delta$.

本研究主要研究了如何在高置信度条件下，通过有限样本同时检验分布 $q$ 和 $p$ 是否相同，其结果给出了最优样本复杂度并表明了经验分布在均匀性检测中的高效性。