hyperrefToken not allowed

# Sharp Constants in Uniformity Testing via the Huber Statistic

Shivam Gupta
The University of Texas at Austin
<EMAIL_ADDRESS>Eric Price
The University of Texas at Austin
<EMAIL_ADDRESS>
###### Abstract

Uniformity testing is one of the most well-studied problems in property
testing, with many known test statistics, including ones based on counting
collisions, singletons, and the empirical TV distance. It is known that the
optimal sample complexity to distinguish the uniform distribution on $m$
elements from any $\varepsilon$-far distribution with $1-\delta$ probability
is
$n=\Theta(\frac{\sqrt{m\log(1/\delta)}}{\varepsilon^{2}}+\frac{\log(1/\delta)}{\varepsilon^{2}})$,
which is achieved by the empirical TV tester. Yet in simulation, these
theoretical analyses are misleading: in many cases, they do not correctly rank
order the performance of existing testers, even in an asymptotic regime of all
parameters tending to $0$ or $\infty$.

We explain this discrepancy by studying the _constant factors_ required by the
algorithms. We show that the collisions tester achieves a sharp maximal
constant in the number of standard deviations of separation between uniform
and non-uniform inputs. We then introduce a new tester based on the Huber
loss, and show that it not only matches this separation, but also has tails
corresponding to a Gaussian with this separation. This leads to a sample
complexity of $(1+o(1))\frac{\sqrt{m\log(1/\delta)}}{\varepsilon^{2}}$ in the
regime where this term is dominant, unlike all other existing testers.

##  1 Introduction

Property testing of distributions is an area of study initiated in [21] and
[4]. The foundation of these works is a test for _uniformity_ : given $n$
samples from a distribution $q$ on $[m]$, can we distinguish the case that $q$
is uniform from the case that $q$ is $\varepsilon$-far from uniform, with
probability $1-\delta$? The remarkable result is that this is often possible
for $n\ll m$, when we cannot learn the actual distribution. Over the years,
several different tests and bounds have been established for uniformity. In
this paper we better understand and explain the relative performance of these
testers, then introduce a new uniformity tester that outperforms all of them.

The first uniformity tester introduced was the _collisions tester_ [21, 4],
which counts the number of collisions among the samples. It is equivalent to
Pearson’s $\chi^{2}$ test, or any other statistic quadratic in the histogram.
It succeeds with constant probability for $n=O(\sqrt{m}/\varepsilon^{2})$
[14], which is optimal [30].

What happens for high-probability bounds? Naive repetition gives a
multiplicative $O(\log\frac{1}{\delta})$ loss, but this can be improved: Huang
and Meyn [22] showed that the _singletons tester_ [30] achieves
$\sqrt{m\log\frac{1}{\delta}}/\varepsilon^{2}$, but only in the setting of
$n=o(m)$ and $\varepsilon=\Omega(1)$. The collisions tester, however, really
does involve a $\log\frac{1}{\delta}$ loss [31].

Achieving optimal dependence of the whole range is the empirical _TV tester_
[13], which measures the TV distance between the empirical distribution and
uniform. It needs

$\displaystyle
n=O\left(\frac{\sqrt{m\log\frac{1}{\delta}}}{\varepsilon^{2}}+\frac{\log\frac{1}{\delta}}{\varepsilon^{2}}\right)$
(1)

which is optimal in all settings of parameters.

To summarize 20 years of theory, the TV tester is asymptotically optimal while
the collisions tester has poor $\delta$ dependence and the singletons tester
is good for $n\ll m$ but fails when $n\gg m$. This suggests that, given an
actual example of a uniformity testing problem, the TV tester is as good as
possible.

In Figure 3 we compare the TV tester to the collisions tester in simulation.
We test the uniform distribution against the distribution that puts
$\frac{1+2\varepsilon}{m}$ mass on half the bins, and
$\frac{1-2\varepsilon}{m}$ mass on the remaining bins. This is the worst case
$\varepsilon$-far distribution for both these testers [13]. We find that,
contrary to the theoretical prediction, the collisions tester outperforms the
TV tester on the parameters we consider. In our first experiment, with
$m=n=10^{4}$ and $\varepsilon=1/8$, the TV tester has twice the error rate as
the collisions tester (3.3% vs 1.7%). In our second experiment, with
$m=n=10^{5}$ and $\varepsilon=1/10$, the gap _widens_ to a factor $10$
($10^{-4}$ vs $10^{-5}$) despite the error rate $\delta$—the parameter the
collisions tester is suboptimal in—becoming much smaller. This means that our
theory is giving the _wrong advice_ : a practitioner should prefer the
collisions tester to the TV tester here.

To better explain this, and to develop a new tester that outperforms all
existing ones, we need to start considering constant factors.

#### Designing a new tester.

How should we design an efficient tester for uniformity? We consider
“separable” testers that take as input the histogram $Y_{j}$ (so $Y_{j}$ is
the number of samples equal to $j$), compute a statistic

$S=\sum_{j=1}^{m}f(Y_{j}),$

and output YES or NO based on whether $S$ lies below some threshold $\tau$.
Existing testers are all either of this form, or use this as the main
subroutine (e.g., after Poissonization or taking the median of multiple
attempts). Differences lie in the choice of $f$. Quadratic functions
$f(k)=(k-n/m)^{2}$ or $f(k)=\binom{k}{2}$ give the $\chi^{2}$ or collisions
tester [21, 4], which are equivalent because $\sum_{j}Y_{j}=n$ is fixed, so
the two statistics $S$ are linearly related. The TV tester [13] uses
$f(k)=|k-n/m|$, while the singletons tester [30] uses $f(k)=1_{k=1}$. But how
would one design $f$ from first principles to work well?

In this paper we introduce a natural approach to designing a test statistic
with good asymptotic constants. First, we find the test statistic $f$ that
maximizes the number of standard deviations of separation between YES and NO
instances; then, we modify the tails of $f$ so that $S$ has Gaussian tails.
This approach is summarized in Figure 1.

Tester | Optimal variance? | Subgaussian tails?
---|---|---
Collisions/$\chi^{2}$ |  Yes (Theorem 1.1) | No (Theorem E.1)
TV | No (Theorem 1.5) | Yes
Huber (new) | Yes |  Yes (Theorem 1.2)
Figure 1: Our main contributions are (1) that the collisions statistic
achieves optimal variance, and (2) that the Huber statistic can get high-
probability bounds matching this variance.

#### Step 1: Optimize variance.

Intuitively, $S$ is a sum of $m$ terms $f(Y_{j})$ that are _nearly_
independent, so we expect central limit-type behavior

$S\stackrel{{\scriptstyle\scalebox{0.7}{$\approx$}}}{{\sim}}N(\operatorname*{\mathbb{E}}[S],\text{Var}[S]).$

That is, we expect our separable statistic to behave like a Gaussian, with
expectation and variance that depend on the particular statistic. Because the
hard alternative distributions $q$ are very close to $p$, typically
$\text{Var}_{q}[S]=(1+o(1))\text{Var}_{p}[S]$. Then our ability to distinguish
$p$ and $q$ depends on how this variance compares to the separation in means:
we want to minimize this _normalized variance_

$\operatorname{\widetilde{var}}_{p,q}(S):=\frac{\text{Var}_{p}[S]}{(\operatorname*{\mathbb{E}}_{q}[S]-\operatorname*{\mathbb{E}}_{p}[S])^{2}}.$

We can set our threshold to lie halfway between
$\operatorname*{\mathbb{E}}_{p}[S]$ and $\operatorname*{\mathbb{E}}_{q}[S]$,
so that, under the Gaussian approximation, the error probability will be given
by

$\displaystyle\delta\approx\exp\left(-\frac{\left(\left(\operatorname*{\mathbb{E}}_{q}[S]-\operatorname*{\mathbb{E}}_{p}[S]\right)/2\right)^{2}}{2\text{Var}_{p}[S]}\right)=\exp\left(-\frac{1}{8\operatorname{\widetilde{var}}_{p,q}(S)}\right)$
(2)

For any $q$, $\min_{f}\operatorname{\widetilde{var}}_{p,q}(S_{f})$ is a
quadratic program in $f$, so we can compute the variance-minimizing $f$ for
any setting of parameters. We can also approximate it analytically in the
asymptotic limit. We find that the quadratic statistics (like collisions or
$\chi^{2}$) are near-optimal:

######  Theorem 1.1.

Let $\varepsilon^{2}\ll\frac{n}{m}\lesssim 1$ and $n,m,1/\varepsilon\to\infty$
with $m\gtrsim 1/\varepsilon^{4}$. Any separable statistic $S$ has normalized
variance

$\operatorname{\widetilde{var}}_{p,q}(S)\geq(1+o(1))\frac{1}{8}\frac{m}{n^{2}\varepsilon^{4}}$

between the uniform distribution $p$ and the balanced nonuniform distribution
$q$ with $q_{k}=\frac{1\pm 2\varepsilon}{m}$.

Quadratic statistics (like collisions or $\chi^{2}$) match this, getting

$\displaystyle\operatorname{\widetilde{var}}_{p,q}(S)\leq(1+o(1))\frac{1}{8}\frac{m}{n^{2}\varepsilon^{4}}$
(3)

for _any_ $\varepsilon$-far distribution $q$.

Theorem 1.1 shows that, if the Gaussian approximations hold, the collisions
tester has optimal constants. Per (2), for failure probability $\delta$ we
need
$\operatorname{\widetilde{var}}_{p,q}(S)=\frac{1}{8\log\frac{1}{\delta}}$, or

$\displaystyle
n=(1+o(1))\frac{1}{\varepsilon^{2}}\sqrt{m\log\frac{1}{\delta}}$ (4)

samples. This matches the optimal complexity (1) in the large-$m$ regime, but
with a sharp constant of $1$. (Sharp in the sense that no other separable
statistic behaves better under its Gaussian approximation.) One could also
trade off the false positive and false negative errors by choosing a different
threshold between the means, getting

$\displaystyle
n=(1+o(1))\frac{1}{\varepsilon^{2}}\sqrt{m}\cdot\frac{\sqrt{\log\frac{1}{\delta_{+}}}+\sqrt{\log\frac{1}{\delta_{-}}}}{2}.$
(5)

for false positive/negative probabilities $\delta_{+}/\delta_{-}$.

By contrast, the TV tester has a constant factor worse normalized variance
than the quadratic tester (we shall state this constant precisely later).
Therefore the Gaussian approximation loses a constant factor relative to (4),
and it would be very surprising if the actual statistic avoided this
inefficiency.111Unsurprisingly, as we show in Theorem 1.5, the inefficiency is
real. So the Gaussian approximations predict the actual Figure 3 behavior.

Unfortunately, the Gaussian approximation does _not_ hold in general for the
collisions statistic, so it does not get (4) or (5). See Appendix E.1 for a
detailed example, due to [31], showing that for exponentially small $\delta$
the collisions tester does not achieve (1) for any constant much less
$1+o(1)$.

#### Step 2: Massage the tails.

The Gaussian tail bound implying (4) and (5) is given by its moment generating
function, so it would suffice to bound the MGF of $S$. The problem is that
$Y_{j}$ has roughly exponential tails for every $j$, so the MGF of $Y_{j}^{2}$
does not have a good bound. To get a good MGF for $f(Y_{j})$, we need to look
at an $f$ with at most linear growth.

So this is our situation: the quadratic $f(Y_{j})=Y_{j}^{2}$ has near-optimal
variance but a very large MGF, while the TV statistic $f(Y_{j})=|Y_{j}-n/m|$
has suboptimal variance but a pretty good MGF. Introducing the linear tail
with $f(Y_{j})=|Y_{j}-n/m|$ is how [13] achieved the
$\sqrt{\log\frac{1}{\delta}}$ dependence, but the worse variance means it
inherently performs worse than the quadratic for large $\delta$ where the
Gaussian approximation holds.

To achieve both good variance and MGF, we should _start_ with the good-
variance quadratic statistic, then attenuate the tail behavior to get good
concentration. We do this with the _Huber_ loss

$f(Y_{j})=h_{\beta}(Y_{j}-n/m)$

for

$h_{\beta}(x):=\min(x^{2},2\beta|x|-\beta^{2}).$

If we choose a tradeoff point $\beta\gg 1+\sqrt{n/m}$, most $Y_{j}$ will lie
in the quadratic region and we still get the variance bound (3). But now the
MGF is bounded. We show that, for a large range of parameters, this leads to
the tester that matches a Gaussian with the optimal variance:

######  Theorem 1.2 (Huber).

The Huber statistic for appropriate $\beta$ achieves (4) for $n/m\ll
1/\varepsilon^{2}$, $\varepsilon,\delta\ll 1$, and $m\geq C\log n$ for
sufficiently large constant $C$. It achieves (5) under the same conditions and
$\delta_{-},\delta_{+}\ll 1$.

Combined with Theorem 1.1, Theorem 1.2 shows that the Huber statistic gets the
optimal variance over separable statistics and matches the Gaussian
concentration with this variance.

The parameter regime is illustrated in Figure 2(a). The first three asymptotic
conditions for Theorem 1.2 delineate the boundaries of the “sublinear” regime,
where testing is possible, nontrivial, and the asymptotic sample complexity
(1) is dominated by the
$\frac{1}{\varepsilon^{2}}\sqrt{m\log\frac{1}{\delta}}$ term. The last
condition, that $m\geq C\log n$, is likely an artifact of our analysis but is
pretty mild.

$O(\log
n)$$\Theta(n)$$o(n^{2})$$O(1)$$\frac{1}{n^{1/2}}$$n=\Theta\left(\frac{m}{\varepsilon^{2}}\right)$$\frac{n^{2}\varepsilon^{4}}{m}=\omega(1)$,
a.k.a. $\delta=o(1)$$\varepsilon=o(1)$ Superlinear
---
regime (Thm 1.3)
Sublinear
---
regime (Thm 1.2)
Impossible
---
regime
$m$$\varepsilon$Best upper boundsHuber has $C_{1}=1$TV/Huber has
$C_{2}=2$Singletons has $C_{1}=1$ (a) The Huber statistic achieves the best
constant over almost the entire region of $\varepsilon\ll 1$. The singletons
statistic was previously known to achieve this for $\varepsilon=\Omega(1)$ and
$m\gg n$ [22].

$O(1)$$\Omega(n)$$n$$O(n)$$o(n^{2})$$O(1)$$\frac{\log^{1/4}n}{n^{1/8}}$$\frac{1}{n^{3/13}}$$\tilde{\Omega}\left(\frac{1}{n^{1/4}}\right)$$\frac{1}{n^{1/2}}$////$n=\Theta\left(\frac{m}{\varepsilon^{2}}\right)$$\frac{n^{2}\varepsilon^{4}}{m}=\omega(1)$,
a.k.a. $\delta=o(1)$$\varepsilon=o(1)$AB(Thm E.1)(Thm 1.5)(Thm 1.4)
Superlinear
---
regime
Impossible
---
regime
$m$$\varepsilon$Comparing collisions and TV testersTV has $C_{1}=1$Collisions
has $C_{1}=1$TV has $C_{1}>1$ Collisions has $C_{1}\gg 1$ (b) The constant
$C_{1}$ in different $(n,\varepsilon,\delta)$ parameter regimes. In region A,
the collisions tester performs better than the TV tester. In region B, both
the collisions and TV tester have $C_{1}>1$.

Figure 2: Our results in different regimes.

The rest of our results look at other regimes and other testers, and we
summarize our results in Figure 2. If we express the sample complexity (1) as

$\displaystyle
n=(C_{1}+o(1))\frac{\sqrt{m\log\frac{1}{\delta}}}{\varepsilon^{2}}+(C_{2}+o(1))\frac{\log\frac{1}{\delta}}{\varepsilon^{2}}$
(6)

then we can express the constants $C_{1},C_{2}$ in different regimes of
$(n,m,\varepsilon)$. In the “sublinear regime” of
$n/m\ll\frac{1}{\varepsilon^{2}}$, where we cannot reliably estimate the
distribution, what matters is $C_{1}$. For $n=m$, when $\log
n\ll\log\frac{1}{\delta}\ll n^{1/13}$ so that
$\tilde{\Omega}(n^{-1/4})\ll\varepsilon\ll n^{-3/13}$, that is, in regime A of
small $\varepsilon$/large $\delta$, collisions gets $C_{1}=1$ and TV has
$C_{1}>1$; in regime B of large $\varepsilon$/small $\delta$, collisions gets
$C_{1}\gg 1$ and TV has $1<C_{1}=O(1)$. The Huber statistic, by contrast, gets
$C_{1}=1$ for almost the whole regime. In the superlinear regime, where the
empirical distribution is $\varepsilon/2$-accurate, a simple union bound shows
that the TV statistic (and hence Huber statistic for $\beta=0$) gets the
optimal $C_{2}=2$:

######  Theorem 1.3 (Superlinear regime).

For $n/m\gg 1/\varepsilon^{2}$ and $\varepsilon\ll 1$, the TV statistic
achieves

$n=(2+o(1))\frac{\log\frac{1}{\delta}}{\varepsilon^{2}}$

and no other tester can do better.

#### Analysis of collisions.

While the $\chi^{2}$/collisions tester does not match the Gaussian tails to
achieve (4) everywhere, it still is a sum of mostly-independent variables and
so looks like a Gaussian outside the extreme tails. Hence the Gaussian
approximation (4) ought to hold when $\delta$ isn’t too small. Indeed, we show
this is true for $n=\Theta(m)$ and intermediate $\delta$:

######  Theorem 1.4 (Collisions for large $\delta$).

The quadratic statistic achieves (4) for $n/m=\Theta(1)$, $\log
n\ll\log\frac{1}{\delta}\ll n^{1/13}$ and $\varepsilon\ll 1$.

#### Analysis of TV.

The TV tester, for $n\leq m$, is equivalent to the tester that counts empty
bins. We show that this has

$\max_{q:\|p-q\|_{TV}\geq\varepsilon}\operatorname{\widetilde{var}}_{p,q}(f)=(1+o(1))\frac{(e^{n/m}-1-n/m)}{4(n/m)^{2}}\frac{m}{\varepsilon^{4}n^{2}}.$

rather than (3). For $n\ll m$ these are equivalent, but for $n=m$ it is 44%
larger, leading to about $20\%$ more samples.

######  Theorem 1.5 (TV).

The TV statistic uses

$n=(1+o(1))\sqrt{\frac{2(e^{n/m}-1-n/m)}{(n/m)^{2}}}\frac{\sqrt{m\log\frac{1}{\delta}}}{\varepsilon^{2}}$

for $n\leq m$, $n\gg 1$, and $\varepsilon,\delta\ll 1$.

Like Theorem 1.2, both Theorem 1.4 and Theorem 1.5 work by showing the
Gaussian approximation is accurate. Thus one could also trade off false
positive/negative probabilities, with a
$\frac{1}{2}(\sqrt{\log\frac{1}{\delta_{-}}}+\sqrt{\log\frac{1}{\delta_{+}}})$
dependence.

Figure 3: Empirical failure probability of different testers when
$n=m=(.7/\varepsilon)^{8.1}$, which is in region B of Figure 2(b). The $x$
axis is $n^{2}\varepsilon^{4}/m$, which should be linear in
$\log\frac{1}{\delta}$ per (6). The shaded region shows two standard
deviations of uncertainty.

#### Experimental performance.

In Figure 3, we compare the empirical performance of the new Huber tester to
the existing collisions and TV testers in a synthetic experiment. The
experiment has $m=n$, $\varepsilon=.7/n^{1/8.1}$ with alternative distribution
$q=\frac{1\pm 2\varepsilon}{n}$, and varies $n$ from $200$ to $600$. This is
in region B of Figure 2(b), and as predicted we find that the Huber tester has
lower failure probability than the TV or collisions testers.

###  1.1 Related work

The past twenty years have seen a large body of work in distribution testing;
see [20, 7] for surveys of the area. Uniformity testing has been either the
basis for, or a necessary subproblem in, many such results. Such extensions
include testing identity [3, 10, 20, 15, 33, 12], testing independence [9],
and testing uniformity over unknown domains [2, 16]. One particularly clean
relation is that you can black-box reduce testing identity to a fixed
distribution $p$ to uniformity testing with only a constant factor loss in
parameters [20].

Most of the above results do not focus on the dependence on $\delta$;
exceptions include [13, 25, 12, 22] which give algorithms within constant
factors of optimal for testing uniformity, identity, and independence.

Lower bounds for uniformity testing started with an $\Omega(\sqrt{m})$ bound
in [21], followed by $\Omega(\sqrt{m}/\varepsilon^{2})$ in [30] and
$\Omega(\frac{1}{\varepsilon^{2}}\sqrt{m\log 1/\delta}+\frac{\log
1/\delta}{\varepsilon^{2}})$ in [13].

When it comes to constant factors in distribution testing, the classical
regime of $\varepsilon,m$ constant and $n\to\infty$ was analyzed in [23] and
the likelihood ratio test was shown to be optimal. Alternatively, for
$m,\delta$ constant and $n,1/\varepsilon\to\infty$, Pearson’s $\chi^{2}$
tester—the quadratic tester—is known to be asymptotically near optimal for
identity testing (see [28], Chapter 14).

The most closely related work to our paper is Huang and Meyn [22], which
(unlike the classical results) studies constant factors in a regime where all
of $n,m,1/\delta\to\infty$. They consider the singletons tester, and show that
$C_{1}=1$ for constant $\varepsilon$ and $n\ll m$. They also show that no
algorithm can do better in this regime. However, for $n=\Theta(m)$ the
singletons tester loses constant factors and for $n\geq O(m\log m)$ it fails
with high probability.

###  1.2 Future work

As discussed above, uniformity testing has been the building block for many
other distribution testing problems, such as identity and independence
testing. Where there are direct reductions (as in testing identity to a fixed
distribution [20]), these reductions lose constant factors. However, these
tests still involve statistics that are the sum of mostly independent random
variables. We believe that our approach to constructing a test statistic—find
a statistic to optimize performance of the Gaussian approximation, then adjust
it to match the Gaussian tails—could lead to higher performance testers in
these problems as well.

Second, there are some settings of parameters that we have not analyzed. Most
interesting would be to analyze the intermediate regime of
$\frac{n}{m}=\Theta(\frac{1}{\varepsilon^{2}})$, where both sample complexity
terms in (1) are significant.

Third, we could consider constant factors for high probability bounds in other
settings. For example, it is known by the Cramér-Rao bound [11] that the
maximum likelihood estimator (MLE) in parametric statistics converges to a
Gaussian with variance equal to the inverse of the Fisher information under a
broad set of assumptions; but the tails of this estimator are less well
understood, and could likely be improved by modifying the estimator to be less
sensitive to outliers. Other examples lie in streaming algorithms. There has
been a line of work on understanding the constants in the space complexity of
cardinality estimation in streams [19, 18, 27, 32], but these have focused on
the constant $\delta$ regime. We believe our techniques could lead to optimal
high probability bounds on the space complexity for this problem.
Alternatively, for problems like heavy hitters [8, 29], the analysis has
focused on the high $\delta$ regime and ignored constant factors; but the
underlying algorithms involve sums of random variables that ought to converge
to Gaussians.

##  2 Proof Overview

###  2.1 Variance Optimality

To show Theorem 1.1, we write the optimization problem

$\displaystyle m^{2}\operatorname{\widetilde{var}}_{p,q}(S)=\qquad$
$\displaystyle\min\text{Var}_{p}[S_{f}]$ s.t.
$\displaystyle\operatorname*{\mathbb{E}}_{q}[S_{f}]-\operatorname*{\mathbb{E}}_{p}[S_{f}]=m$

as a quadratic program in the vector $f=(f_{0},\dotsc,f_{n})$. For
$\overline{p}_{k}=\operatorname*{\mathbb{P}}_{p}[Y_{1}=k]$ and
$\overline{q}_{k}=\operatorname*{\mathbb{E}}_{i\in[m]}\operatorname*{\mathbb{P}}_{q}[Y_{i}=k]$,
the constraint is that $(\overline{q}-\overline{p})\cdot f=1$, and the
objective is $f^{T}Qf$ for some matrix $Q$. The KKT condition [24, 26, 5]
shows that the optimum is achieved when $Qf=a(\overline{q}-\overline{p})$ for
some scalar $a$.

Solving this exactly requires the pseudoinverse $Q^{+}$, which would be
tricky. Instead, we show that the quadratic statistic $f_{k}=k^{2}$ satisfies
a slightly different condition

$Qf=a(q^{\prime}-\overline{p}),$

for a different distribution $q^{\prime}\in\mathbb{R}^{n+1}$ we can write
explicitly. Therefore the quadratic statistic minimizes the variance subject
to an expectation gap in $q^{\prime}$ relative to $\overline{p}$. Moreover,
this $q^{\prime}$ turns out to be precisely the Taylor approximation in
$\varepsilon$ to $\overline{q}$, with order $\varepsilon^{4}$ error. All that
remains is to show that this $O(\varepsilon^{4})$ distinction between
$\overline{q}$ and $q^{\prime}$ gives $1+o(1)$ loss in the program. That is,

$|\operatorname*{\mathbb{E}}_{q^{\prime}}f_{k}-\operatorname*{\mathbb{E}}_{\overline{p}}f_{k}|=(1+o(1))|\operatorname*{\mathbb{E}}_{\overline{q}}f_{k}-\operatorname*{\mathbb{E}}_{\overline{p}}f_{k}|,$

or equivalently

$\displaystyle|\operatorname*{\mathbb{E}}_{q^{\prime}}f_{k}-\operatorname*{\mathbb{E}}_{\overline{q}}f_{k}|\ll\frac{1}{m}|\operatorname*{\mathbb{E}}_{q}[S_{f}]-\operatorname*{\mathbb{E}}_{p}[S_{f}]|,$
(7)

for any statistic that we care about. We can bound this LHS in terms of the
variance of $f$:

$|\operatorname*{\mathbb{E}}_{q^{\prime}}f_{k}-\operatorname*{\mathbb{E}}_{\overline{q}}f_{k}|\lesssim\varepsilon^{4}\sqrt{\operatorname*{\mathbb{E}}_{\overline{p}}[f_{k}^{2}]}.$

Then we can relate the variance of $f$ to the variance of $S$:

$\operatorname*{\mathbb{E}}_{\overline{p}}[f_{k}^{2}]\lesssim\frac{1}{m}\text{Var}_{p}[S_{f}]$

using the fact that our statistic is indifferent to constant and linear terms,
so we can assume WLOG
$\operatorname*{\mathbb{E}}[f_{k}]=\operatorname*{\mathbb{E}}[kf_{k}]=0$.

Combining these results, we get that (7) holds whenever

$\operatorname{\widetilde{var}}_{p,q}(S)=\frac{\text{Var}_{p}[S_{f}]}{(\operatorname*{\mathbb{E}}_{q}[S_{f}]-\operatorname*{\mathbb{E}}_{p}[S_{f}])^{2}}\ll\frac{1}{\varepsilon^{8}m}.$

Since the quadratic has
$\operatorname{\widetilde{var}}_{p,q}(S)=\Theta(\frac{m}{\varepsilon^{4}n^{2}})$,
this holds for both the quadratic and the statistic of maximal separation
$\operatorname{\widetilde{var}}_{p,q}(S)$. Therefore this maximum is within
$1+o(1)$ of the quadratic.

###  2.2 Concentration of Tails

#### Setting.

In this proof overview we will focus on the Huber statistic in the regime
where $1\lesssim\frac{n}{m}\ll\frac{1}{\varepsilon^{2}}$, as well as
$\varepsilon,\delta\ll 1$ (so $\frac{n^{2}}{m}\varepsilon^{4}\gg 1$).

Let $X_{1},\dots,X_{n}$ be the $n$ samples drawn from distribution $\nu$
supported on $[m]$, and let
$Y_{j}^{n}=\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}=j\\}}$ be the number of balls
that end up in bin $j$.

#### The Huber statistic.

We consider the Huber statistic

$S=\sum_{j=1}^{m}h_{\beta}\left(Y_{j}^{n}-\frac{n}{m}\right)$ (8)

where

$\displaystyle h_{\beta}(x):=\left\\{\begin{array}[]{cl}x^{2}&\text{for
}|x|<\beta\\\ 2\beta|x|-\beta^{2}&\text{otherwise}\end{array}\right.$ (11)

is the Huber loss function, which continuously interpolates between a
quadratic center and linear tails. Note that this is twice the standard
definition, but the statistic’s performance is invariant under affine
transformations.

We will set $\beta$ large enough that most bins usually lie in the quadratic
regime in the uniform case. If we were to set $\beta=\infty$ (so $S$ is an
affine transformation of the collisions statistic), we would have
$\operatorname*{\mathbb{E}}_{p}[S]=n-n/m\approx n$ for the uniform
distribution $p$ and $\operatorname*{\mathbb{E}}_{q}[S]\geq
n-n/m+4n(n-1)\varepsilon^{2}/m\approx n+4n^{2}\varepsilon^{2}/m$ for any
$\varepsilon$-far distribution $q$. This motivates us to consider the rescaled
statistic:

$\tilde{S}=\frac{m}{n^{2}\varepsilon^{2}}\left[S-n\right]$ (12)

which (for $\beta=\infty$) has $\operatorname*{\mathbb{E}}[\tilde{S}]$ being
$o(1)$ or $\geq 4-o(1)$ in the uniform and far-from-uniform cases,
respectively.

Because $Y_{j}^{n}\sim B(n,1/m)$ in the uniform case, Bernstein’s inequality
shows that setting

$\beta=\omega\left(\log\left(\frac{1}{\Delta}\right)+\sqrt{\frac{n}{m}\log\left(\frac{1}{\Delta}\right)}\right)$
(13)

gives that each bin lies in the quadratic regime with probability
$1-\Delta^{2}$, for a parameter $\Delta\ll 1$ that we will constrain later.
Choosing this $\beta$ leads to smaller $\operatorname*{\mathbb{E}}[S]$ than
$\beta=\infty$, but the difference is only about $\beta^{2}\Delta^{2}m$
because each of the $m$ bins has a $\Delta^{2}$ chance of lying in the linear
region, and most of the differences happen at the boundary where the Huber
statistic is $\Theta(\beta^{2})$. This error is
$O(n\Delta^{2}\log^{2}\frac{1}{\Delta})<O(n\Delta^{1.5})$, so

$\operatorname*{\mathbb{E}}_{p}[\tilde{S}]=o(1)+O(\frac{m}{n^{2}\varepsilon^{2}}\Delta^{1.5}n)=o(1)$

as long as we have

$\displaystyle\Delta=O\left(\frac{n\varepsilon^{2}}{m}\right)$ (14)

which is $o(1)$. Similarly, this implies

$\operatorname*{\mathbb{E}}_{q}[\tilde{S}]\geq 4-o(1)$

for any $\varepsilon$-far distribution $q$.

Finally, we will need some constraint that $\beta$ is not too large/$\Delta$
too small. A third moment condition suffices, as we shall see in a few pages:

$(\beta^{2}\varepsilon^{2})^{3}=o\left(\Delta^{2}\right)$ (15)

One can check that $\beta$ and $\Delta$ can be chosen such that the
constraints (13), (14), and (15) hold in the regime we consider here.

#### Analyzing the Huber statistic.

Our tester will pick a threshold $\tau$, and “accept” the distribution as
uniform if $\tilde{S}\leq\tau$. We therefore need to understand the false
negative probability

$\delta_{-}:=\operatorname*{\mathbb{P}}_{p}[\tilde{S}\geq\tau]$

and similarly, for any $\varepsilon$-far distribution $q$, we need to bound
the false positive probability

$\delta_{+}:=\operatorname*{\mathbb{P}}_{q}[\tilde{S}\leq\tau].$

To bound the maximum error $\delta=\max(\delta_{-},\delta_{+})$, it suffices
to pick $\tau=2$, halfway between the expectation bounds in the uniform and
$\varepsilon$-far cases.

#### Completeness.

We start by describing how to analyze $\delta_{-}$. The bulk of our analysis
here is devoted to analyzing the moment generating function
$M_{\tilde{S},\nu}(t):=\operatorname*{\mathbb{E}}_{\nu}[\exp(t\tilde{S})]$.

A careful analysis (see, e.g., [14] Lemma 3) shows that when $\nu$ is the
uniform distribution, the number of collisions has variance
$(1+o(1))\frac{n^{2}}{2m}$. For large enough $\beta$ per (13), this implies

$\text{Var}[\tilde{S}]=(1+o(1))\frac{2m}{n^{2}\varepsilon^{4}}.$

Therefore we hope that $\tilde{S}$ has MGF close to a Gaussian with this
variance. In Lemma C.12 we show that this is in fact the case: for the uniform
distribution $p$,

$\displaystyle
M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)$
$\displaystyle=\left(1+O(1/n)\right)\exp\left\\{\frac{n^{2}}{m}\varepsilon^{4}\left(\theta^{2}+o\left(1\right)\right)\right\\}$
(16)

Here, we pulled out $\frac{n^{2}\varepsilon^{4}}{m}$ from the MGF parameter,
so that we will set $\theta$ to be constant at the end. Once we have this,
then standard Chernoff-type arguments imply

$\delta_{-}<\inf_{\theta\geq
0}\frac{M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)}{e^{\frac{n^{2}\varepsilon^{4}}{m}\theta(E_{p}[\tilde{S}]+\tau)}}<\inf_{\theta\geq
0}(1+O(1/n))\exp\left\\{\frac{n^{2}}{m}\varepsilon^{4}\left[\theta^{2}-\tau\theta+o\left(1\right)\right]\right\\}$

and hence

$\delta_{-}\leq(1+O(1/n))\exp(-J_{-}(1+o(1))\frac{n^{2}\varepsilon^{4}}{m})$

for “error exponent”

$J_{-}:=\sup_{\theta\geq 0}\left\\{-\frac{m}{n^{2}\varepsilon^{4}}\log
M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)+\theta\tau\right\\}\geq\sup_{\theta\geq
0}\\{\theta\tau-\theta^{2}\\}=\frac{\tau^{2}}{4}$ (17)

The above is an upper bound on $\delta_{-}$, but we can also get a lower
bound. Because the MGF bound (16) is tightly that of a Gaussian, with both
upper and lower bounds, we can apply the Gärtner-Ellis theorem (see Appendix
B.1) to show that the tail bound is tightly that of a Gaussian as well:
$\delta_{-}\gtrsim\exp(-(1+o(1))Jn^{2}\varepsilon^{4}/m)$.

#### Soundness.

Because the Huber statistic $S$ is convex, we can apply existing tools from
[13] to analyze the statistic for uniformity testing. In particular, it is
sufficient to consider alternate distributions of the form $q$ such that

$q_{j}=\begin{cases}1/m+\frac{\varepsilon}{l},&j\leq l\\\
1/m-\frac{\varepsilon}{m-l},&j>l\end{cases}$ (18)

for some $l\in[m]$. Our discussion of this appears in Appendix B.2. For
simplicity of this exposition, suppose $m$ is even and $l=m/2$. Using a
similar procedure as in the case of the uniform distribution, we show in Lemma
C.12 that for this alternate distribution $q$,

$\displaystyle
M_{\tilde{S},q}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\left[\theta^{2}+4\theta+o(1)\right]\right\\}.$
(19)

That is to say, except for a mean shift of $4+o(1)$, $\tilde{S}$ under $q$
concentrates as a Gaussian with the same variance as it did under $p$. This
gives us that

$\delta_{+}\leq(1+O(1/n))\exp\left(-J_{+}(1+o(1))\frac{n^{2}\varepsilon^{4}}{m}\right)$

for “error exponent”

$J_{+}:=\sup_{\theta\geq 0}\left\\{-\frac{m}{n^{2}\varepsilon^{4}}\log
M_{\tilde{S},q}\left(-\frac{n^{2}\varepsilon^{4}}{m}\theta\right)-\theta\tau\right\\}\geq\sup_{\theta\geq
0}\\{-\tau\theta-\theta^{2}+4\theta\\}=\frac{(\tau-4)^{2}}{4}$

Setting $\tau=2$ so that $J_{-}=J_{+}=1$ gives us that the error exponent
achieved by the Huber tester is $1$ for the uniformity testing problem in this
regime.

Alternatively, we could pick a different $\tau\in(0,4)$ to trade off
$\delta_{-}$ and $\delta_{+}$, always getting within $(1+o(1))$ of the
tradeoff given by the Gaussian approximation to $S$.

#### Analyzing the MGF.

The key question, therefore, is how to analyze the MGF. For this, we follow
the structure of [22], though with different approximations because of our
different regime.

We would like to analyze the MGF $M_{S_{n}}$ of our test statistic

$S_{n}=h_{\beta}(|Y_{j}^{n}-n/m|).$

If the $Y_{j}^{n}$ were independent over $j$, this would be easy: we would
simply bound the MGF of each individual term, and take the product. For the
same reason, it is easy to bound the MGF $A_{\lambda}(\theta)$ of the
_poissonized_ test statistic $S_{\text{Poi}(\lambda)}$, where
$\text{Poi}(\lambda)$ balls are drawn rather than $n$. We can get a Taylor
approximation to $A_{\lambda}$ that is quite accurate in our regime.

Unfortunately, we cannot just use the Poissonized MGF $A_{n}$ in place of the
true MGF $M_{S_{n}}$. The problem is that Poissonization inherently increases
the variance: the variance of the collisions statistic is
$(1+o(1))\frac{n^{2}}{2m}$ before Poissonization but
$(1+o(1))(\frac{n^{2}}{2m}+\frac{n^{3}}{m^{2}})$ after Poissonization. For
$n=\Theta(m)$ this is a constant factor we cannot afford to lose, and for
$n\gg m$ it’s even worse. So we need to “depoissonize” $A_{\lambda}$ into
$M_{S_{n}}$.

To depoissonize, we observe that the Poissonized MGF $A_{\lambda}$ is a
mixture of the non-Poissonized MGFs $M_{S_{k}}$ for $k\geq 0$, and in fact
$M_{S_{n}}$ is just (up to scaling) the $\lambda^{n}$ coefficient in the
Taylor expansion of $A_{\lambda}$. We then use Cauchy’s theorem to evaluate
this coefficient.

#### Comparison to Huang-Meyn

Our proof structure is similar to [22]. Differences arise from two causes:
first, [22] consider the simpler singletons tester $f(k)=1_{k=1}$, so the MGF
of $f(Y_{i})$ can be written in closed form. For the Huber statistic, we need
to bound the terms corresponding to the higher moments of the statistic, which
is done in Lemma C.2. Second, they use the asymptotic regime $n/m\ll 1$ rather
than $\varepsilon\ll 1$ for their Taylor series expansions to drop $o(1)$
terms, leading to a number of differences.

Finally, our proof for the alternate distributions is much simpler than the
proof in [22] since we make use of results from [13].

###  2.3 Organization of the Appendix

Appendix A shows Theorem 1.1, that quadratic statistics have asymptotically
optimal variance. The next sections show Theorem 1.2, that the Huber statistic
combines this variance with good concentration, in the main new regime of
$1\lesssim n/m\ll 1/\varepsilon^{2}$: some background is given in Appendix B,
the main argument in Appendix C, and some technical computations are deferred
to Appendix D.

The rest of the appendix includes our analyses of other testers and other
regimes. Proof of the asymptotically poor performance of the collisions and
singletons testers in some regimes is in Appendix E. The “superlinear” regime
of $n/m\gg 1/\varepsilon^{2}$ is covered in Appendix F. Analysis of the
collisions/quadratic statistic is in Appendix G, while the TV/empty bins
statistic for $n<m$ is in Appendix H.

##  3 Acknowledgments

Shivam Gupta and Eric Price are supported by NSF awards CCF-2008868,
CCF-1751040 (CAREER), and the NSF AI Institute for Foundations of Machine
Learning (IFML).

## References

  * Ash [90] Robert Ash.  Information Theory.  Dover books on advanced mathematics. Dover Publications, 1990.
  * BC [17] Tugkan Batu and Clément L Canonne.  Generalized uniformity testing.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 880–889. IEEE, 2017.
  * BFF+ [01] Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White.  Testing random variables for independence and identity.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 442–451. IEEE, 2001.
  * BFR+ [00] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren Smith, and Patrick White.  Testing that distributions are close.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 259–269, 2000.
  * BV [04] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, March 2004.
  * Can [17] Clément Canonne.  A short note on poisson tail bounds.  Unpublished, 2017.
  * Can [20] Clément L Canonne.  A survey on distribution testing: Your data is big. but is it blue?  Theory of Computing, pages 1–100, 2020.
  * CCF [02] Moses Charikar, Kevin Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  In Automata, Languages and Programming, pages 693–703. Springer, 2002.
  * CDKS [18] Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart.  Testing conditional independence of discrete distributions.  In 2018 Information Theory and Applications Workshop (ITA), pages 1–57. IEEE, 2018.
  * CDVV [14] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1193–1203. SIAM, 2014.
  * Cra [46] Harald Cramer.  Mathematical methods of statistics.  Princeton University Press Princeton, 1946.
  * DGK+ [21] Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price.  Optimal testing of discrete distributions with high probability.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 542–555, New York, NY, USA, 2021. Association for Computing Machinery.
  * DGPP [18] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Sample-optimal identity testing with high probability.  In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018\.
  * DGPP [19] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Collision-based testers are optimal for uniformity and closeness.  Chicago Journal of Theoretical Computer Science, 2019:1, 2019.
  * DK [16] Ilias Diakonikolas and Daniel M Kane.  A new approach for testing properties of discrete distributions.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685–694. IEEE, 2016.
  * DKS [18] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  Sharp bounds for generalized uniformity testing.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * DZ [98] A. Dembo and O. Zeitouni.  Large Deviations Techniques and Applications.  Applications of mathematics. Springer, 1998.
  * Ert [17] Otmar Ertl.  New cardinality estimation methods for hyperloglog sketches.  ArXiv, abs/1706.07290, 2017.
  * FFGM [07] Philippe Flajolet, Eric Fusy, Olivier Gandouet, and Frederic Meunier.  Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm.  In AOFA ’07: Proceedings of the 2007 International Conference on Analysis of Algorithms, 2007.
  * Gol [17] Oded Goldreich.  Introduction to property testing.  Cambridge University Press, 2017.
  * GR [11] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 68–75. Springer, 2011.
  * HM [13] Dayu Huang and Sean Meyn.  Generalized error exponents for small sample universal hypothesis testing.  IEEE transactions on information theory, 59(12):8157–8181, 2013\.
  * Hoe [65] Wassily Hoeffding.  Asymptotically optimal tests for multinomial distributions.  The Annals of Mathematical Statistics, 36(2):369 – 401, 1965.
  * Kar [39] William Karush.  Minima of functions of several variables with inequalities as side conditions.  Master’s thesis, Department of Mathematics, University of Chicago, Illinois, USA, 1939.
  * KBW [22] Ilmun Kim, Sivaraman Balakrishnan, and Larry Wasserman.  Minimax optimality of permutation tests.  The Annals of Statistics, 50(1):225 – 251, 2022.
  * KT [51] H. W. Kuhn and A. W. Tucker.  Nonlinear programming.  In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, pages 481–492, Berkeley and Los Angeles, 1951. University of California Press.
  * Lan [17] Kevin J. Lang.  Back to the future: an even more nearly optimal cardinality estimation algorithm.  CoRR, abs/1708.06839, 2017.
  * LRC [05] Erich Leo Lehmann, Joseph P Romano, and George Casella.  Testing statistical hypotheses, volume 3.  Springer, 2005.
  * MP [14] Gregory Minton and Eric Price.  Improved concentration bounds for count-sketch.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 669–686. Society for Industrial and Applied Mathematics, 2014.
  * Pan [08] Liam Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Transactions on Information Theory, 54(10):4750–4755, 2008\.
  * Pee [15] John Peebles.  Personal communication, 2015.
  * PW [21] Seth Pettie and Dingyu Wang.  Information theoretic limits of cardinality estimation: Fisher meets shannon.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 556–569, New York, NY, USA, 2021. Association for Computing Machinery.
  * VV [17] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  SIAM Journal on Computing, 46(1):429–455, 2017.

###### Contents of Appendix

  1. 1 Introduction
    1. 1.1 Related work
    2. 1.2 Future work
  2. 2 Proof Overview
    1. 2.1 Variance Optimality
    2. 2.2 Concentration of Tails
    3. 2.3 Organization of the Appendix
  3. 3 Acknowledgments
  4. A Variance Optimality (Theorem 1.1)
    1. A.1 Optimality under a different distribution $q^{\prime}$
    2. A.2 Relating the covariance of one bin to the whole
    3. A.3 Putting it together
  5. B Background for Tester Analysis
    1. B.1 Gärtner-Ellis Theorem
    2. B.2 Worst Case Distributions for Uniformity Testing
  6. C Huber Statistic in Sublinear Regime
    1. C.1 Regime
    2. C.2 Poissonization
    3. C.3 Depoissonization
    4. C.4 Application of the Gärtner-Ellis Theorem
    5. C.5 Setting the threshold
  7. D MGF computation Lemmas
    1. D.1 Huber Lemmas
    2. D.2 General Lemmas
  8. E Lower bounds
    1. E.1 The collisions tester is asymptotically bad when $n=\Theta(m)$ and $\varepsilon=\omega\left(\frac{\log^{1/4}n}{n^{1/8}}\right)$
    2. E.2 Paninski tester is asymptotically bad when $n\geq\Theta(m\log m)$
  9. F TV Tester in the Superlinear Regime
    1. F.1 Anticoncentration of a Binomial Variable
  10. G Squared Statistic in Sublinear Regime
    1. G.1 Poissonization
    2. G.2 Depoissonization
    3. G.3 Application of the Gärtner-Ellis Theorem
    4. G.4 Removing the conditioning
    5. G.5 Setting the threshold
  11. H Empty bins statistic in Sublinear Regime
    1. H.1 Poissonization
    2. H.2 Depoissonization
    3. H.3 Application of the Gärtner-Ellis Theorem
    4. H.4 Setting the threshold
    5. H.5 Empty bins lemmas

##  Appendix A Variance Optimality (Theorem 1.1)

#### Setting.

Consider throwing $n$ balls into $m$ bins, for $\lambda=n/m=O(1)$. Suppose
$m\gtrsim 1/\varepsilon^{4}$ (as is needed for constant success probability
when $n\lesssim m$). Let $k,k^{\prime}$ be the number of balls landing in bins
$1$ and $2$, respectively. For any $f$, let
$\sigma^{2}=\operatorname*{\mathbb{E}}_{k}[f_{k}^{2}]$.

###  A.1 Optimality under a different distribution $q^{\prime}$

We define

$\overline{p}_{k}:=Bin(n,1/m,k)$

to be the probability any given bin has $k$ balls in it under the uniform
distribution.

######  Lemma A.1.

For any alternative distribution $\overline{q}$, any statistic $f$ minimizing
the normalized variance

$\frac{\text{Var}_{p}[S_{F}]}{(\operatorname*{\mathbb{E}}_{k\sim\overline{q}}[f_{k}]-\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[f_{k}])^{2}}$

satisfies

$(Qf)_{k}=\alpha(\overline{p}_{k}-\overline{q}_{k})$

for some $\alpha$ and all $k$.

###### Proof.

This is the KKT condition for minimizing the quadratic
$\text{Var}_{p}[S_{f}]=\frac{1}{m}f^{T}Qf$ subject to
$\sum_{k}(\overline{p}_{k}-\overline{q}_{k})f_{k}=1$. ∎

Let
$\overline{q}_{k}:=\frac{1}{2}Bin(n,(1+2\varepsilon)/m,k)+\frac{1}{2}Bin(n,(1-2\varepsilon)/m,k)$.
We would like to show that a quadratic is $1-o(1)$-close to maximizing the
normalized separation between $\overline{p}$ and $\overline{q}$.

We have that

$\displaystyle\overline{p}_{k}$
$\displaystyle=\binom{n}{k}\frac{1}{m^{k}}(1-1/m)^{n-k}$
$\displaystyle\overline{q}_{k}$
$\displaystyle=\binom{n}{k}\frac{1}{m^{k}}\frac{1}{2}((1+2\varepsilon)^{k}(1-(1+2\varepsilon)/m)^{n-k}+(1-2\varepsilon)^{k}(1-(1-2\varepsilon)/m)^{n-k})$
$\displaystyle=\overline{p}_{k}\frac{(1+2\varepsilon)^{k}(1-(1+2\varepsilon)/m)^{n-k}+(1-2\varepsilon)^{k}(1-(1-2\varepsilon)/m)^{n-k}}{2(1-1/m)^{n-k}}$
$\displaystyle=\overline{p}_{k}\frac{1}{2}((1+2\varepsilon)^{k}(1-\frac{2\varepsilon}{m-1})^{n-k}+(1-2\varepsilon)^{k}(1+\frac{2\varepsilon}{m-1})^{n-k})$

Now, for $|a|\leq 2\varepsilon$,

$(1+a)=e^{a-\frac{1}{2}a^{2}+\frac{1}{3}a^{3}+O(\varepsilon^{4})},$

and

$(1+\frac{a}{m-1})^{n-k}=e^{a\lambda+O(|k-\lambda|a/m+a^{2}\lambda/m)}=e^{a\lambda+O(\varepsilon^{4})}$

for $k\lesssim 1/\varepsilon$ and our setting of $\lambda=O(1),m\gtrsim
1/\varepsilon^{4}$. Thus

$\displaystyle\overline{q}_{k}$
$\displaystyle=\overline{p}_{k}\frac{1}{2}(e^{2\varepsilon
k-2\varepsilon^{2}k+\frac{8}{3}\varepsilon^{3}k+O(\varepsilon^{4}k)}e^{-2\varepsilon\lambda+O(\varepsilon^{4})}+e^{-2\varepsilon
k-2\varepsilon^{2}k-\frac{8}{3}\varepsilon^{3}k+O(\varepsilon^{4}k)}e^{2\varepsilon\lambda+O(\varepsilon^{4})})$
$\displaystyle=\overline{p}_{k}e^{-2\varepsilon^{2}k+O(\varepsilon^{4}(k+1))}\cosh(2\varepsilon(k-\lambda)+\frac{8}{3}\varepsilon^{3}k)$
$\displaystyle=\overline{p}_{k}(1+2\varepsilon^{2}((k-\lambda)^{2}-k)+O(\varepsilon^{4}(k^{2}+1+(k-\lambda)^{4}))$

as long as the final error term is $o(1)$ We now define

$\displaystyle\alpha_{k}:=(k-\lambda)^{2}-k+\lambda/m$ (20)

so that

$\displaystyle\overline{q}_{k}=\overline{p}_{k}(1+2\varepsilon^{2}\alpha_{k}+O(\varepsilon^{4}(k^{4}+1)))$
(21)

under $k\lesssim\frac{1}{\varepsilon}$ and our assumptions. We make the
following simple observations:

######  Lemma A.2.

$\displaystyle\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[k]=\lambda$ (22)
$\displaystyle\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[(k-\lambda)^{2}]=\lambda(1-1/m)$
(23)
$\displaystyle\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[\alpha_{k}]=0.$
(24)

###### Proof.

The first two equations are just the mean and variance of a binomial random
variable, and the third follows trivially. ∎

Define

$q^{\prime}_{k}:=\overline{p}_{k}(1+2\varepsilon^{2}\alpha_{k})$

which is also a probability distribution, since
$\operatorname*{\mathbb{E}}_{\overline{p}}[\alpha_{k}]=0$ and
$\alpha_{k}\geq-O(\lambda)$ so it is positive. For $q^{\prime}$, the quadratic
statistics are _exactly_ optimal:

######  Lemma A.3.

Quadratic statistics $f_{k}=ak^{2}+bk+c$ minimize

$\frac{\text{Var}_{p}[S]}{(\operatorname*{\mathbb{E}}_{k\sim
q^{\prime}}[mf_{k}]-\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[mf_{k}])^{2}}$

over all $f$, attaining value

$\displaystyle(1+o(1))\frac{1}{8\varepsilon^{4}\lambda^{2}m}.$ (25)

###### Proof.

Value. We first measure the value obtained by the quadratic statistic. The
quadratic statistic $f(k)=(k-\lambda)^{2}$ has four times the variance of the
collisions statistic $\binom{k}{2}$, so Lemma 3 of [14] shows that

$\text{Var}_{p}[S]=4\binom{n}{2}(\frac{1}{m}-\frac{1}{m^{2}})=(1+o(1))2\lambda^{2}m.$

We also have, using the moments of a binomial, that

$\displaystyle\operatorname*{\mathbb{E}}_{k\sim
q^{\prime}}[f_{k}]-\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[f_{k}]$
$\displaystyle=\sum_{k}2\varepsilon^{2}\alpha_{k}\overline{p}_{k}f_{k}$
$\displaystyle=2\varepsilon^{2}\operatorname*{\mathbb{E}}_{\overline{p}}[(k-\lambda)^{4}-(k-\lambda)^{3}-(1-1/m)\lambda(k-\lambda)^{2}]$
$\displaystyle=2\varepsilon^{2}(1-1/m)(\lambda(1+\frac{3n-6}{m}(1-1/m))-\lambda(1-2/m)-\lambda^{2}(1-1/m))$
$\displaystyle=2\varepsilon^{2}(1+o(1))(\lambda+3\lambda^{2}-\lambda-\lambda^{2})$
$\displaystyle=4\varepsilon^{2}\lambda^{2}(1+o(1))$

Hence

$\frac{\text{Var}_{p}[S]}{(\operatorname*{\mathbb{E}}_{k\sim
q^{\prime}}[f_{k}]-\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[f_{k}])^{2}}=(1+o(1))\frac{m}{8\varepsilon^{4}\lambda^{2}}.$

Scaling by $m^{2}$ gives the result.

#### Optimality.

We now show that it is optimal. For any statistic $f$, we have that

$\text{Var}[S_{f}]=mf^{T}QF$

for a matrix $Q$ defined by

$Q_{k,k}=\overline{p}_{k}+(m-1)\overline{p}_{k}\overline{p}_{k^{\prime}\mid
k}-m\overline{p}_{k}^{2}$

and

$Q_{k,k^{\prime}}=(m-1)\overline{p}_{k}\overline{p}_{k^{\prime}\mid
k}-m\overline{p}_{k}\overline{p}_{k^{\prime}},$

where $\overline{p}_{k^{\prime}\mid
k}=\operatorname*{\mathbb{P}}[Y_{2}=k^{\prime}\mid Y_{1}=k]$.

For any statistic $S=\sum f(Y_{i})$, we have that

$(Qf)_{k}=\overline{p}_{k}(\operatorname*{\mathbb{E}}[S\mid
Y_{1}=k]-\operatorname*{\mathbb{E}}[S]).$

We also have that

$\operatorname*{\mathbb{E}}_{k\sim
q^{\prime}}[f_{k}]-\operatorname*{\mathbb{E}}_{k\sim\overline{p}}[f_{k}]=\sum_{k}2\varepsilon^{2}\alpha_{k}f_{k}.$

Therefore we can express the optimization as

$\displaystyle\begin{aligned} \min_{f}\quad&f^{T}Qf\\\
\textrm{s.t.}\quad&2\varepsilon^{2}\sum_{k}\alpha_{k}f_{k}=1/m.\end{aligned}$
(26)

The KKT condition for optimality is then that $Qf=a\alpha$ for some constant
$a$.

Now, the quadratic function $f_{k}=k^{2}$ satisfies

$\operatorname*{\mathbb{E}}[S]=\frac{n^{2}}{m}+n(1-\frac{1}{m}).$

Therefore

$\operatorname*{\mathbb{E}}[S\mid
Y_{1}=k]=k^{2}+\frac{(n-k)^{2}}{m-1}+(n-k)(1-\frac{1}{m-1}).$

so

$\displaystyle\operatorname*{\mathbb{E}}[S\mid
Y_{1}=k]-\operatorname*{\mathbb{E}}[S]$
$\displaystyle=\frac{m}{m-1}k^{2}-k(\frac{2n}{m-1}+(1-\frac{1}{m-1}))+(h_{1}(n,m))$
$\displaystyle=\frac{m}{m-1}\alpha_{k}+h_{2}(n,m)$

for some functions $h_{1},h_{2}$ of $n$ and $m$ but not $k$. But since the LHS
is zero in expectation over $k\sim\overline{p}$, and so is $\alpha_{k}$ by
Lemma A.2, we have $h_{2}=0$. Thus:

$Qf=\frac{m}{m-1}\alpha.$

Hence the quadratic satisfies the KKT condition, so it optimizes (26) when
scaled appropriately. ∎

We also note that the error in approximating $\overline{q}$ by $q^{\prime}$
has low moments:

######  Lemma A.4.

In our setting,

$\operatorname*{\mathbb{E}}_{\overline{p}}[(\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}})^{2}]\lesssim\varepsilon^{8}.$

###### Proof.

For $k\leq 1/\varepsilon$, we have by (21) that

$|\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}}|=|\alpha_{k}-\frac{\overline{q}_{k}}{\overline{p}_{k}}|\lesssim\varepsilon^{4}(k^{4}+1)$

such that

$\operatorname*{\mathbb{E}}_{\overline{p}}[(\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}})^{2}1_{k\leq
1/\varepsilon}]\lesssim\operatorname*{\mathbb{E}}_{\overline{p}}[\varepsilon^{8}(k^{8}+1)]\lesssim\varepsilon^{8}.$

On the other hand, for $k>1/\varepsilon$,

$\operatorname*{\mathbb{E}}_{\overline{p}}[(\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}})^{2}1_{k>1/\varepsilon}]\lesssim\operatorname*{\mathbb{E}}_{\overline{p}}[(\frac{\overline{q}_{k}}{\overline{p}_{k}})^{2}1_{k>1/\varepsilon}].$

Now, for $k>1/\varepsilon$, the $\lambda(1+\varepsilon)$ part of
$\overline{q}$ is more likely than the $\lambda(1-\varepsilon)$ part. Thus

$\frac{\overline{q}_{k}}{\overline{p}_{k}}\leq\frac{\binom{n}{k}((1+\varepsilon)/m)^{k}(1-(1+\varepsilon)/m)^{n-k}}{\binom{n}{k}(1/m)^{k}(1-1/m)^{n-k}}\leq(1+\varepsilon)^{k}$

while

$\overline{p}_{k}\leq(\frac{e\lambda}{k})^{k}=e^{O(k)-k\log k}$

so

$\operatorname*{\mathbb{E}}_{\overline{p}}[(\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}})^{2}1_{k>1/\varepsilon}]\leq\sum_{k\geq
1/\varepsilon}e^{2\varepsilon k}e^{O(k)-k\log
k}\lesssim\varepsilon^{\Omega(1/\varepsilon)}<\varepsilon^{8}$

giving the result. ∎

###  A.2 Relating the covariance of one bin to the whole

Recall that $\sigma^{2}=\operatorname*{\mathbb{E}}[f_{k}^{2}]$, for
$k\sim\overline{p}$.

######  Lemma A.5.

For any $B>2\lambda$, we have

$\operatorname*{\mathbb{E}}[f_{k^{\prime}}f_{k}1_{k^{\prime}>B}]\lesssim\sigma^{2}\sqrt{\operatorname*{\mathbb{P}}[k^{\prime}>B]}.$

###### Proof.

For any $t>B$, we have

$\operatorname*{\mathbb{P}}[k\mid
k^{\prime}=t]\lesssim\operatorname*{\mathbb{P}}[k]$

for all $k$. This is trivially true for small $k\leq O(1)$ because
$\operatorname*{\mathbb{P}}[k]=\Omega(1)$, and for large $k$—since $t$ is
above average—$\operatorname*{\mathbb{P}}[k\mid
k^{\prime}=t]<\operatorname*{\mathbb{P}}[k]$.

This implies

$\operatorname*{\mathbb{E}}[|f_{k}|\leavevmode\nobreak\ \mid
k^{\prime}=t]\lesssim\operatorname*{\mathbb{E}}_{k}[|f_{k}|]\leq\sigma.$

So

$\operatorname*{\mathbb{E}}[f_{k^{\prime}}f_{k}1_{k^{\prime}>B}]=\sum_{k^{\prime}>B}p_{k^{\prime}}f_{k^{\prime}}\operatorname*{\mathbb{E}}[f_{k}\mid
k^{\prime}]\lesssim\sigma\sum_{k^{\prime}>B}p_{k^{\prime}}|f_{k^{\prime}}|$

Of course, by Cauchy-Schwarz,

$\sum_{k^{\prime}>B}p_{k^{\prime}}|f_{k^{\prime}}|\leq\sqrt{(\sum_{k^{\prime}>B}p_{k^{\prime}})(\sum_{k^{\prime}>B}p_{k^{\prime}}f_{k^{\prime}}^{2})}\leq\sigma\sqrt{\operatorname*{\mathbb{P}}[k^{\prime}>B]}$

and hence

$\operatorname*{\mathbb{E}}[f_{k^{\prime}}f_{k}1_{k^{\prime}>B}]\lesssim\sigma^{2}\sqrt{\operatorname*{\mathbb{P}}[k^{\prime}>B]}.$

∎

######  Lemma A.6.

Let $f_{k}$ satisfy
$\operatorname*{\mathbb{E}}_{p}[f_{k}]=\operatorname*{\mathbb{E}}_{p}[kf_{k}]=0$.
For sufficiently large $n,m$ we have

$\sigma^{2}\lesssim\frac{1}{m}\text{Var}[S_{f}].$

###### Proof.

We can expand

$\text{Var}[S_{f}]=m\sigma^{2}+m(m-1)\operatorname*{\mathbb{E}}_{k,k^{\prime}}[f_{k}f_{k^{\prime}}].$

The lemma statement would be implied by

$\displaystyle|\operatorname*{\mathbb{E}}_{k,k^{\prime}}[f_{k}f_{k^{\prime}}]|\leq\frac{1}{2(m-1)}\sigma^{2},$
(27)

where $k$ is the number of balls in bin $1$ and $k^{\prime}$ is the number in
bin $2$. The probability that $k>B$ is at most

$2\binom{n}{B}\frac{1}{m^{B}}\leq
2(\frac{e\lambda}{B})^{B}<\frac{1}{n^{2}m^{4}}$

for $B=O(\log m)$. By Lemma A.5,

$|\operatorname*{\mathbb{E}}_{k,k^{\prime}}[f_{k}f_{k^{\prime}}1_{k>B\cup
k^{\prime}>B}]|\leq
2|\operatorname*{\mathbb{E}}_{k,k^{\prime}}[f_{k}f_{k^{\prime}}1_{k>B}]|\lesssim\sqrt{\frac{1}{m^{4}}}\sigma^{2}.$

Therefore it would suffice to show

$\displaystyle|\operatorname*{\mathbb{E}}_{k,k^{\prime}}[f_{k}f_{k^{\prime}}1_{k<B\cap
k^{\prime}<B}]|\ll\frac{\sigma^{2}}{m}.$ (28)

Let $\mathcal{B}$ be the event that $k<B\cap k^{\prime}<B$.

Let $\lambda^{\prime}:=(n-k^{\prime})/(m-1)=\lambda(1+\varepsilon^{\prime})$
for $\varepsilon^{\prime}=\frac{1}{m-1}\lambda(\lambda-k^{\prime})$, which
under $\mathcal{B}$ satisfies $|\varepsilon^{\prime}|\lesssim m^{-2/3}$. Then
$(k\mid k^{\prime})$ is $b(n-k^{\prime},1/(m-1))$, which is well approximated
by $Poi(\lambda^{\prime})$. This Poisson approximation gives

$\displaystyle p^{\prime}_{k}$
$\displaystyle=\frac{(\lambda^{\prime})^{k}e^{-\lambda^{\prime}}}{k!}=p_{k}(1+\varepsilon^{\prime})^{k}e^{-\lambda\varepsilon^{\prime}}$
$\displaystyle=p_{k}e^{(k-\lambda)\varepsilon^{\prime}+O((\varepsilon^{\prime})^{2}k)}$
$\displaystyle=p_{k}(1+(k-\lambda)\varepsilon^{\prime}+O((k+(k-\lambda)^{2})(\varepsilon^{\prime})^{2}))$

for $k\lesssim 1/|\varepsilon^{\prime}|$, which holds given $\mathcal{B}$.
Since
$\operatorname*{\mathbb{E}}_{p}[f_{k}]=\operatorname*{\mathbb{E}}_{p}[kf_{k}]=0$,
we have that

$\displaystyle|\sum_{k}p_{k}(1+(k-\lambda)\varepsilon^{\prime})f_{k}1_{k\leq
B}|$
$\displaystyle=|\sum_{k}p_{k}(1+(k-\lambda)\varepsilon^{\prime})f_{k}1_{k>B}|$
$\displaystyle\leq\sqrt{(\sum_{k>B}p_{k})\operatorname*{\mathbb{E}}_{k}(1+(k-\lambda)\varepsilon^{\prime})^{2}f_{k}^{2}}$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{P}}[k>B]}\sigma
n\varepsilon^{\prime}\leq\frac{1}{m^{2}}\sigma.$

Therefore, for any $k^{\prime}\leq B$,

$\displaystyle|\operatorname*{\mathbb{E}}_{k\mid k^{\prime}}[f_{k}1_{k\leq
B}]|$
$\displaystyle\leq\frac{\sigma}{m^{2}}+|\operatorname*{\mathbb{E}}_{k}[O(k+(k-\lambda)^{2})(\varepsilon^{\prime})^{2}f_{k}1_{k\leq
B}]|$
$\displaystyle\lesssim\frac{\sigma}{m^{2}}+(\varepsilon^{\prime})^{2}\sqrt{\operatorname*{\mathbb{E}}_{k}[(k+(k-\lambda)^{2})^{2}]\operatorname*{\mathbb{E}}_{k}[f_{k}^{2}]}$
$\displaystyle\eqsim(\frac{1}{m}+(\varepsilon^{\prime})^{2})\sigma$
$\displaystyle\lesssim\sigma/m^{4/3}.$

Therefore

$|\operatorname*{\mathbb{E}}_{k^{\prime},k}[f_{k^{\prime}}f_{k}1_{k,k^{\prime}\leq
B}]|=\operatorname*{\mathbb{E}}_{k^{\prime}}[|f_{k^{\prime}}1_{k^{\prime}\leq
B}\operatorname*{\mathbb{E}}_{k\mid k^{\prime}}[f_{k}1_{k\leq
B}]|]\lesssim\operatorname*{\mathbb{E}}_{k^{\prime}}[|f_{k^{\prime}}|1_{k^{\prime}\leq
B}\frac{\sigma}{m^{4/3}}]\lesssim\frac{\sigma^{2}}{m^{4/3}}$

which gives (28) as needed. ∎

###  A.3 Putting it together

See 1.1

###### Proof.

Because the normalized separation is invariant to adding any linear function
$ak+b$ to $f_{k}$, we can add use this degree of freedom to WLOG satisfy any
two linear constraints. We require that

$\operatorname*{\mathbb{E}}_{\overline{p}}[f_{k}]=0$

and

$\operatorname*{\mathbb{E}}_{\overline{p}}[kf_{k}]=0.$

Let $\widehat{f}_{k}=k^{2}+ak+b$ be the quadratic test statistic with $a$ and
$b$ set to satisfy these two constraints.. By Lemma A.3, $\widehat{f}$ is
optimal under $q^{\prime}$, so we have that

$\displaystyle
OPT:=(1+o(1))\frac{1}{8\varepsilon^{4}\lambda^{2}m}=\frac{\text{Var}[S_{\widehat{f}}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[m\widehat{f}_{k}]^{2}}\geq\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[mf_{k}]^{2}}.$
(29)

We have that

$\displaystyle(\operatorname*{\mathbb{E}}_{q^{\prime}}[f_{k}]-\operatorname*{\mathbb{E}}_{\overline{q}}[f_{k}])^{2}$
$\displaystyle=(\sum_{k}(q^{\prime}_{k}-\overline{q}_{k})f_{k})^{2}$
$\displaystyle=(\operatorname*{\mathbb{E}}_{\overline{p}}[\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}}f_{k}])^{2}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\overline{p}}[(\frac{q^{\prime}_{k}-\overline{q}_{k}}{\overline{p}_{k}})^{2}]\operatorname*{\mathbb{E}}_{\overline{p}}[f_{k}^{2}]$
$\displaystyle\lesssim\varepsilon^{8}\sigma_{f}^{2}$ (Lemma A.4)
$\displaystyle\lesssim\varepsilon^{8}\frac{1}{m}\text{Var}[S_{f}].$ (Lemma
A.5)

The same holds for $\widehat{f}$, where we also have by (29) that

$\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]^{2}=(1+o(1))\frac{1}{m}\text{Var}[S_{\widehat{f}}]\cdot
8\varepsilon^{4}\lambda^{2}$

so

$(\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]-\operatorname*{\mathbb{E}}_{\overline{q}}[\widehat{f}_{k}])^{2}\lesssim\varepsilon^{8}\frac{1}{m}\text{Var}[S_{\widehat{f}}]=\varepsilon^{4}\cdot(1+o(1))\frac{1}{8\lambda^{2}}\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]^{2}\ll\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]^{2}$

and hence

$\operatorname*{\mathbb{E}}_{\overline{q}}[\widehat{f}_{k}]^{2}=(1+o(1))\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]^{2}$

so

$\operatorname{\widetilde{var}}_{p,q}(S_{\widehat{f}})=\frac{\text{Var}_{p}[S_{\widehat{f}}]}{\operatorname*{\mathbb{E}}_{\overline{q}}[S_{\widehat{f}}]^{2}}=(1+o(1))OPT.$

For any alternative $f$, we split into two cases:

#### Reasonably good $f$.

When

$\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[mf_{k}]^{2}}\leq
100OPT,$

we again have

$\varepsilon^{8}\frac{1}{m}\text{Var}[S_{f}]\ll\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]^{2}$

so

$\operatorname*{\mathbb{E}}_{\overline{q}}[f_{k}]^{2}=(1+o(1))\operatorname*{\mathbb{E}}_{q^{\prime}}[\widehat{f}_{k}]^{2}$

and

$\operatorname{\widetilde{var}}_{p,q}(S_{f})=(1+o(1))\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[mf_{k}]^{2}}\geq(1+o(1))OPT.$

#### Bad $f$.

When

$\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[mf_{k}]^{2}}\geq
100OPT,$

we use $(a+b)^{2}\leq 2a^{2}+2b^{2}$ to observe that

$\displaystyle\operatorname{\widetilde{var}}_{p,q}(S_{f})$
$\displaystyle=\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q}[mf_{k}]^{2}}\geq\frac{1}{2}\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[mf_{k}]^{2}+m^{2}(\operatorname*{\mathbb{E}}_{q^{\prime}}[f_{k}]-\operatorname*{\mathbb{E}}_{\overline{q}}[f_{k}])^{2}}$
$\displaystyle=\frac{1}{2}\frac{\text{Var}[S_{f}]}{\operatorname*{\mathbb{E}}_{q^{\prime}}[mf_{k}]^{2}+O(\varepsilon^{8}m\text{Var}[S_{f}])}$
$\displaystyle\geq\frac{1}{2}\frac{1}{\frac{1}{100OPT}+\varepsilon^{8}m}$
$\displaystyle>OPT$

Thus, the quadratic tester achieves near-optimal separation for this $q$.

Finally, for arbitrary distributions $q$ $\varepsilon$-far from $p$ in TV, we
note that the collisions tester satisfies

$\operatorname*{\mathbb{E}}_{q}[S]=\binom{n}{2}\|q\|_{2}^{2}.$

By convexity the $\varepsilon$-far $q$ minimizing this has its values above
and below $1/m$ all equal; if there are $k$ values above $1/m$ this gives

$\displaystyle\frac{1}{\binom{n}{2}}\operatorname*{\mathbb{E}}_{q}[S]$
$\displaystyle=k(\frac{1}{m}+\frac{\varepsilon}{k})^{2}+(m-k)(\frac{1}{m}-\frac{\varepsilon}{m-k})^{2}$
$\displaystyle=\frac{1}{m}+\varepsilon^{2}\left(\frac{1}{k}+\frac{1}{m-k}\right)$

which is minimized at $k=m-k=m/2$, precisely the $q$ considered above. ∎

##  Appendix B Background for Tester Analysis

###  B.1 Gärtner-Ellis Theorem

The statements in this section are taken from [17].

Consider a sequence of random variables $Z_{n}\sim p_{n}$ and let the
logarithmic moment generating function of $Z_{n}$ be

$\Lambda_{n}(\theta):=\log\operatorname*{\mathbb{E}}[e^{\theta Z_{n}}]$

######  Assumption 1.

Suppose that for each $\theta\in\mathbb{R}$, the logarithmic moment generating
function, defined as the limit

$\Lambda(\theta)=\lim_{n\to\infty}\frac{1}{n}\Lambda_{n}(n\theta)$

exists as an extended real number, and that the origin lies in the interior of
the set
$\mathcal{D}_{\Lambda}:=\\{\theta\in\mathbb{R}:\Lambda(\theta)<\infty\\}$.

Let

$\Lambda^{*}(\tau)=\sup_{\theta\geq 0}\\{\theta\tau-\Lambda(\theta)\\}$ (30)

be the Fenchel-Legendre transform of $\Lambda$.

######  Definition B.1.

$\tau\in\mathbb{R}$ is an exposed point of $\Lambda^{*}$ if for some
$\lambda\in\mathbb{R}$, for every $x\neq y$,

$\lambda\tau-\Lambda^{*}(\tau)>\lambda x-\Lambda^{*}(x)$

Then, $\lambda$ is called an exposing hyperplane.

######  Theorem B.2 (Gärtner–Ellis).

Let Assumption 1 hold.

  1. (a)

For any closed set $F$,

$\limsup_{n\to\infty}\frac{1}{n}\log p_{n}(F)\leq-\inf_{x\in F}\Lambda^{*}(x)$

  2. (b)

For any open set $G$,

$\liminf_{n\to\infty}\frac{1}{n}\log p_{n}(G)\geq-\inf_{x\in G\cap
F}\Lambda^{*}(x)$

where $F$ is the set of exposed points of $\Lambda^{*}$ whose exposing
hyperplane belongs to $D^{o}_{\Lambda}$, where $D^{o}_{\Lambda}$ is the
interior of $D_{\Lambda}$.

###  B.2 Worst Case Distributions for Uniformity Testing

In this section, we study the worst-case $\varepsilon$-far distributions for
test statistics that are convex symmetric functions of the histogram (i.e.,
the number of times each domain element is sampled) of an arbitrary random
variable $Y$. This is an extension of the results in [13], which we recap
below.

#### Prior work.

We start with the following definition:

######  Definition B.3.

Let $p=(p_{1},\dots,p_{n}),q=(q_{1},\dots,q_{n})$ be probability distributions
and $p^{\downarrow},q^{\downarrow}$ denote the vectors with the same values as
$p$ and $q$ respectively, but sorted in non-increasing order. We say that $p$
_majorizes_ $q$ (denoted by $p\succ q$) if

$\forall
k:\sum_{i=1}^{k}p^{\downarrow}_{i}\geq\sum_{i=1}^{k}q^{\downarrow}_{i}\;.$
(31)

A proof of the following simple fact can be found in [13]:

######  Fact B.4.

Let $p$ be a probability distribution over $[n]$ and $S\subseteq[n]$. Let $q$
be the distribution which is identical to $p$ on $[n]\setminus S$, and for
every $i\in S$ we have $q_{i}=\frac{{p}(S)}{|S|}$, where $|S|$ denotes the
cardinality of $S$. Then, we have that $p\succ q$.

We also use the following standard terminology: we say that a real random
variable $A$ _stochastically dominates_ a real random variable $B$ if for all
$x\in\mathbb{R}$ it holds
$\operatorname*{\mathbb{P}}[A>x]\geq\operatorname*{\mathbb{P}}[B>x]$.

We say that a test statistic $S$ is “convex symmetric” if it is a convex
function of the histogram $(Y_{1},\dots,Y_{m})$ and invariant under
permutation of the $Y_{i}$. A “test” is given by a test statistic $S$ and
threshold $\tau$, and outputs “uniform” if $S\leq\tau$ and “non-uniform”
otherwise.

It was shown in [13] that if $p$ majorizes $q$, then a convex symmetric test
statistic of $p$ stochastically dominates one from $q$:

######  Lemma B.5 (Lemma 19 of [13]).

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a symmetric convex function and $p$ be
a distribution over $[n]$. Suppose that we draw $m$ samples from $p$, and let
$X_{i}$ denote the number of times we sample element $i$. Let $g(p)$ be the
random variable $f(X_{1},X_{2},\ldots,X_{n})$. Then, for any distribution $q$
over $[n]$ such that $p\succ q$, we have that $g(p)$ stochastically dominates
$g(q)$.

#### New claims.

We will show that it suffices to consider distributions that are “flat”,
meaning that $p_{i}$ takes only two values:

######  Definition B.6.

We say a probability distribution $p$ over $[n]$ is an _$\gamma$ -skewed flat
distribution_ if it takes the form:

$p_{i}=\left\\{\begin{array}[]{cl}a&i\in T\\\ b&i\notin T\end{array}\right.$

for some reals $a,b$ and set $T\subseteq[n]$ with $|T|\in[\gamma
n,(1-\gamma)n]$.

We make the following generalization of Lemma 21 in [13] (which is the
$\gamma=1/2$ case):

######  Lemma B.7.

Let $p$ be a probability distribution. For any $0<\gamma<1/2$, there exists an
$\gamma$-skewed flat distribution $p^{\prime}$ such that $p\succ p^{\prime}$
and

$(1-\gamma)\cdot\|p-U_{n}\|_{TV}\leq\|p^{\prime}-U_{n}\|_{TV}\leq\|p-U_{n}\|_{TV}.$

###### Proof.

Let $T=\\{i:p_{i}>1/n\\}$, so

$\displaystyle\|p-U_{n}\|_{TV}=\sum_{i\in T}(p_{i}-1/n)=\sum_{i\in[n]\setminus
T}(1/n-p_{i}).$ (32)

If $|T|\in[\gamma n,(1-\gamma)n]$, we can simply choose $p^{\prime}$ to be $p$
averaged over $T$, and $p$ averaged over $[n]\setminus T$—this is
$\gamma$-skewed and flat, has $p\succ p^{\prime}$ by Lemma B.4, and has
$\|p^{\prime}-U_{n}\|_{TV}=\|p-U_{n}\|_{TV}$. The only remaining cases have
$|T|\notin[\gamma n,(1-\gamma)n]$, since this approach would not be
$\gamma$-skewed.

Let $T^{\prime}\subset[n]$ contain the largest either $\gamma n$ or
$(1-\gamma)n$ coordinates of $p$, depending on whether $|T|<\gamma n$ or
$|T|>(1-\gamma)n$, and let $p^{\prime}$ average $p$ over $T^{\prime}$ and over
$[n]\setminus T$. This is $\gamma$-skewed and flat, and has $p\succ
p^{\prime}$ by Lemma B.4, so the only question is the TV bound.

We have that

$\|p^{\prime}-U_{n}\|_{TV}=\sum_{i\in
T^{\prime}}(p^{\prime}_{i}-1/n)=\sum_{i\in
T^{\prime}}(p_{i}-1/n)=\|p-U_{n}\|_{TV}-\sum_{i\in T\setminus
T^{\prime}}(p_{i}-1/n)-\sum_{i\in T^{\prime}\setminus T}(1/n-p_{i}).$

Every term in the right two sums is nonnegative, so
$\|p^{\prime}-U_{n}\|_{TV}\leq\|p-U_{n}\|_{TV}$.

Now, if $|T|<\gamma n$, then $T\setminus T^{\prime}$ is empty and, since
$T^{\prime}$ takes the largest coordinates in $p$, $p_{i}$ is larger on
average for $i\in T^{\prime}\setminus T$ than for $i\in[n]\setminus T$:

$\sum_{i\in T^{\prime}\setminus T}(1/n-p_{i})\leq\frac{|T^{\prime}\setminus
T|}{|[n]\setminus T|}\sum_{i\in[n]\setminus T}(1/n-p_{i})=\frac{\gamma
n-|T|}{n-|T|}\|p-U_{n}\|_{TV}\leq\gamma\|p-U_{n}\|_{TV}$

so

$\|p^{\prime}-U_{n}\|_{TV}\geq(1-\gamma)\|p-U_{n}\|_{TV}.$

Similarly, if $|T|>(1-\gamma)n$, then $T^{\prime}\setminus T$ is empty and

$\sum_{i\in T\setminus T^{\prime}}(p_{i}-1/n)\leq\frac{|T\setminus
T^{\prime}|}{|T|}\sum_{i\in
T}(p_{i}-1/n)=\frac{|T|-(1-\gamma)n}{|T|}\|p-U_{n}\|_{TV}\leq\gamma\|p-U_{n}\|_{TV},$

again giving

$\|p^{\prime}-U_{n}\|_{TV}\geq(1-\gamma)\|p-U_{n}\|_{TV}$

as desired. ∎

The above results mean that it suffices to prove that our algorithm can
distinguish the uniform distribution from $\gamma$-skewed flat distributions.
The inefficiency from not considering extremely skewed distributions is only
$1+O(\gamma)$:

######  Lemma B.8.

Suppose a convex symmetric test statistic $S$ and threshold has the property
that, when applied to any $\varepsilon$-far $\gamma$-skewed flat distribution
$p$, the false negative rate is at most $\delta$. Then the same statistic and
threshold, when applied to any $\frac{1}{1-\gamma}\varepsilon$-far
distribution $p^{\prime}$, also has false negative rate at most $\delta$.

###### Proof.

For any such $p^{\prime}$, Lemma B.7 states that there exists a $p$ that is
$\gamma$-skewed, $\varepsilon$-far from $U_{n}$ in TV, and with
$p^{\prime}\succ p$. Lemma B.5 then states that $S$ on $p^{\prime}$
stochastically dominates $S$ on $p$, so the chance of falling below the
threshold is smaller for $p^{\prime}$ than for $p$—and the latter is $\delta$
by assumption. ∎

#### Implication for Error Exponents.

Let $\varepsilon=\varepsilon(n)$, $m=m(n)$, and $\tau=\tau(n)$ be functions of
$n$. Let $p$ be uniform on $[m]$. The false positive error exponent
$c_{+}=c_{+}(\varepsilon,m)$ of a test $(S,\tau)$ is

$c_{+}=\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\operatorname*{\mathbb{P}}_{p}[S>\tau].$

For a _particular_ family of distributions $q$, the false negative error
exponent $c_{-}^{(q)}=c_{-}^{(q)}(\varepsilon,m)$ is

$c_{-}^{(q)}=\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\operatorname*{\mathbb{P}}_{q}[S\leq\tau].$

The false negative error exponent $c_{-}$ is the worst such exponent over all
$\varepsilon$-far distributions $q$:

$c_{-}=\inf_{q:\|p-q\|_{TV}\geq\varepsilon}c_{-}^{(q)}.$

Varying $\tau$ allows for a tradeoff between false negatives and false
positives. Balancing the two gives us the _error exponent_
$c=c(\varepsilon,m)$ for a test statistic $S$:

$c=\sup_{\tau}\min(c_{+},c_{-}).$

If a test statistic has error exponent $c$, it can distinguish the uniform
distribution from any non-uniform distribution with probability
$1-\exp(-(1+o(1))c\varepsilon^{4}n^{2}/m)$. Equivalently, it gets error
probability $\delta$ where

$n=\frac{1+o(1)}{\sqrt{c}}\cdot\frac{\sqrt{m\log\frac{1}{\delta}}}{\varepsilon^{2}}.$

We define $\overline{c}=\overline{c}(\varepsilon,m,\gamma)$ to denote an
alternative to $c$ where we only consider $\varepsilon$-far distributions $q$
that are $\gamma$-skewed and flat.

######  Lemma B.9.

For any functions $\varepsilon,m,\gamma$,

$(1-4\gamma)\cdot\overline{c}((1-\gamma)\varepsilon,m,\gamma)\leq
c(\varepsilon,m)\leq\overline{c}(\varepsilon,m,\gamma).$

###### Proof.

The upper bound on $c$ is trivial: as an infimum over a larger set of $q$,
$c_{-}\leq\overline{c}_{-}$, so $c\leq\overline{c}$.

For the lower bound on $c$, we note by Lemma B.8 that for any $q$ with
$\|p-q\|_{TV}\geq\varepsilon$ that there exists a $\gamma$-skewed flat
distribution $q^{\prime}$ with
$\|p-q^{\prime}\|_{TV}\geq(1-\gamma)\varepsilon$ such that

$\displaystyle\operatorname*{\mathbb{P}}_{q}[S\leq\tau]\leq\operatorname*{\mathbb{P}}_{q^{\prime}}[S\leq\tau].$
(33)

This implies that

$\displaystyle\frac{m}{n^{2}\varepsilon^{4}}\log\operatorname*{\mathbb{P}}_{q}[S\leq\tau]\leq(1-\gamma)^{4}\frac{m}{n^{2}(1-\gamma)^{4}\varepsilon^{4}}\log\operatorname*{\mathbb{P}}_{q^{\prime}}[S\leq\tau].$

so

$c_{-}^{(q)}(\varepsilon,m)\geq(1-\gamma)^{4}c_{-}^{(q^{\prime})}((1-\gamma)\varepsilon,m),$

and hence $c\geq(1-4\gamma)\overline{c}((1-\gamma)\varepsilon,m)$. ∎

######  Lemma B.10.

Let $S$ by a convex symmetric test statistic. Consider any family of
parameters $(n,\varepsilon,m)$. Suppose that there exists a constant
$\gamma^{\prime}$ such that, for any $\gamma=\Omega(1)>\gamma^{\prime}$ and
$\varepsilon^{\prime}$ that uniformly satisfies
$(1-\gamma^{\prime})\varepsilon(n)\leq\varepsilon^{\prime}(n)\leq\varepsilon(n)$,

$\overline{c}(\varepsilon^{\prime},m,\gamma)=c^{*}$

for a fixed value $c^{*}$ [that depends on the family $(n,\varepsilon,m)$ but
not on the value of $n$ or $\gamma,\gamma^{\prime}$].

Then

$c(\varepsilon,m)=c^{*}.$

###### Proof.

By Lemma B.9,

$c(\varepsilon,m)\leq\overline{c}(\varepsilon,m,\gamma)=c^{*}.$

Moreover, for any $C$ we have

$c(\varepsilon,m)\geq(1-4\gamma)c^{*}.$

where $c$ is a limit as $n\to\infty$ independent of $C$. But this means that
$c(\varepsilon,m)=c^{*}$, because it is larger than any fixed value less than
$c^{*}$. ∎

##  Appendix C Huber Statistic in Sublinear Regime

###  C.1 Regime

The Huber statistic is given by

$S=\sum_{j=1}^{m}h_{\beta}\left(Y_{j}^{n}-\frac{n}{m}\right)$ (8)

where

$\displaystyle h_{\beta}(x):=\left\\{\begin{array}[]{cl}x^{2}&\text{for
}|x|<\beta\\\ 2\beta|x|-\beta^{2}&\text{otherwise}\end{array}\right.$ (11)

is the Huber loss function. Here
$Y_{j}^{n}=\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}=j\\}}$ and $X_{1},\dots,X_{n}$
are the $n$ samples drawn from distribution $\nu$ supported on $[m]$.

######  Assumption 2.

$n=\Omega(m),n/m\ll\frac{1}{\varepsilon^{2}}$, $\varepsilon\ll 1$,
$\frac{n^{2}}{m}\varepsilon^{4}\gg 1$, and $m\geq C\log n$ for sufficiently
large constant $C$. In addition, we have the following constraints on $\beta$,
the Huber parameter, and $\Delta$.

$\beta=\omega\left(\log\left(\frac{1}{\Delta}\right)+\sqrt{\frac{n}{m}\log\left(\frac{1}{\Delta}\right)}\right)$
(13) $\displaystyle\Delta=O\left(\frac{n\varepsilon^{2}}{m}\right)$ (14)
$(\beta^{2}\varepsilon^{2})^{3}=o\left(\Delta^{2}\right)$ (15)

We will assume that Assumption 2 holds throughout this section.

Note that since $\Delta=o(1)$, (15) implies that

$\beta^{2}\varepsilon^{2}=o(1)$ (36)

Our goal is to compute an upper bound on the asymptotic expansion of the
cumulant generating function (also called the logarithmic moment generating
function) of this statistic.

For ease, instead of analyzing $S$ directly, we will analyze the statistic

$\tilde{S}=\frac{m}{n^{2}\varepsilon^{2}}\left[S-n\right]$ (37)

Note that this has the same error probability as $S$ since it simply applies a
translation and scaling to $S$.

Consider the moment generating function (MGF) of $\tilde{S}$ with respect to
distribution $\nu$, given by

$M_{\tilde{S},\nu}(\theta)=\operatorname*{\mathbb{E}}_{\nu}\left[\exp(\theta\tilde{S})\right]$

The logarithmic moment generating function of $\tilde{S}$ with respect to
distribution $\nu$ is given by

$\Lambda_{n,\nu}(\theta):=\log\left(M_{\tilde{S},\nu}(\theta)\right)$ (38)

We will compute an asymptotic expansion of the limiting logarithmic moment
generating function of $\tilde{S}$, given by

$\Lambda_{\nu}(\theta)=\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\Lambda_{n,\nu}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)$

For ease of exposition, we define a centering function

$\phi(k):=\left|k-\frac{n}{m}\right|$ (39)

###  C.2 Poissonization

Define $\tilde{S}_{Poi(\lambda)}$ to be the Poissonized statistic, that is the
statistic $\tilde{S}$ when the number of balls is chosen according to the
Poisson distribution with mean $\lambda$.

We begin by computing the MGF of $\tilde{S}_{Poi(\lambda)}$ with MGF parameter
$\frac{n^{2}\varepsilon^{4}}{m}\theta$. That is, let

$A_{\lambda}(\theta):=\operatorname*{\mathbb{E}}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}_{Poi(\lambda)}\right)\right]=\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right)\right]$
(40)

where $Z_{j}\sim Poi(\lambda\nu_{j})$ and are independent. Due to this
independence,

$A_{\lambda}(\theta)=\exp(-\varepsilon^{2}\theta
n)\prod_{j=1}^{m}\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta
h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right)\right]$

Define

$f(k):=1+\varepsilon^{2}\theta\phi(k)^{2}+\frac{\varepsilon^{4}\theta^{2}}{2}\phi(k)^{4}$
(41)

We will first show the following

######  Lemma C.1.

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}\left[h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right]=\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]+o(\Delta^{2})$
$\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}\left[h_{\beta}\left(Z_{j}-\frac{n}{m}\right)^{2}\right]=\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]+o(\Delta^{2})$
$\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}\left[h_{\beta}\left(Z_{j}-\frac{n}{m}\right)^{l}\right]=o(\Delta^{2})$

where $h_{\beta}$ is defined in (11), and $Z_{j}\sim Poi(\lambda\nu_{j})$, for
$\lambda=n(1+O(\varepsilon^{2}))$ and $\nu_{j}=1/m+O(\varepsilon/m)$ for all
$j$.

###### Proof.

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}\left[h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right]=\varepsilon^{2}\theta\left\\{\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\phi(Z_{j})^{2}\right]+\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\beta(2\phi(Z_{j})-\beta)\right]\right\\}$
$=\varepsilon^{2}\theta\
E[\phi(Z_{j})^{2}]-\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\phi(Z_{j})^{2}]+\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\beta(2\phi(Z_{j})-\beta)]$

By Lemma D.8, the second term is $o(\Delta^{2})$. For the third term,

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\beta(2\phi(Z_{j})-\beta)]\leq\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\exp(\varepsilon^{2}|\theta|\beta(2\phi(Z_{j})-\beta))]$

By Lemma D.10, this is $o(\Delta)^{2}$. So, we have the first claim. The
second claim can be proved in a similar way. For the third claim,

$\displaystyle\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}\left[h_{\beta}\left(Z_{j}-\frac{n}{m}\right)^{l}\right]=\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\phi(Z_{j})^{2l}\right]$
$\displaystyle+\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}(\beta(2\phi(Z_{j})-\beta))^{l}\right]$

By Lemma D.5, the first term is $o(\Delta^{2})$. For the second term, in a
similar fashion as before,

$\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}(\beta(2\phi(Z_{j})-\beta))^{l}\right]\leq\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\exp(\varepsilon^{2}|\theta|\beta(2\phi(Z_{j})-\beta))\right]$

By Lemma D.10, this is $o(\Delta^{2})$. ∎

######  Lemma C.2.

We have

$\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta
h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right)\right]=\operatorname*{\mathbb{E}}\left[f(Z_{j})\right]+o\left(\Delta^{2}\right)$
(42)

where $h_{\beta}$ is defined in (11), and
$Z_{j}\sim\text{Poi}(\lambda\nu_{j})$, for $\lambda=n(1+O(\varepsilon^{2}))$
and $\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$.

###### Proof.

Follows from Lemma C.1. ∎

###  C.3 Depoissonization

First, we will show that $A_{\lambda}(\theta)$ is analytic in $\lambda$.

######  Lemma C.3.

$A_{\lambda}(\theta)$ is analytic in $\lambda$.

###### Proof.

We will show that $\operatorname*{\mathbb{E}}[\exp\left(\varepsilon^{2}\theta
h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right)]$ can be written as a finite
sum of analytic functions in $\lambda$. Since the sum and product of analytic
functions also analytic, this will show that $A_{\lambda}(\theta)$ is
analytic. Let

$A:=\sum_{k:\phi(k)\leq\beta}\left[\frac{(\lambda\nu_{j})^{k}}{k!}e^{-\lambda\nu_{j}}\exp\left(\varepsilon^{2}\theta\phi(k)^{2}\right)\right]\\\
$

$B:=\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(Z_{j}-\frac{n}{m}\right)-\beta\right)\right\\}\right]$

$C:=\sum_{k:k<\frac{n}{m}-\beta}\left[\frac{(\lambda\nu_{j})^{k}}{k!}e^{-\lambda\nu_{j}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-k\right)-\beta\right)\right\\}-\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(k-\frac{n}{m}\right)-\beta\right)\right\\}\right]\right]$

Then, the expectations in $B$ and $C$ can be expressed in terms of the moments
and MGF of the Poisson distribution, and so, are analytic. Each of $A,B,C$ is
a finite sum of analytic functions, and so, is analytic. It is easy to verify
that

$\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta
h_{\beta}\left(Z_{j}-\frac{n}{m}\right)\right)\right]=A+B+C$

is thus analytic.

∎

Now, we want depoissonize $A_{\lambda}(\theta)$. For ease of exposition, we
will prove a more general result. First we assume the following.

######  Assumption 3.

Suppose $\xi$ is a function such that

$A_{\lambda}(\theta)=\exp(-\varepsilon^{2}\theta
n)\prod_{j=1}^{m}\operatorname*{\mathbb{E}}[\exp(\varepsilon^{2}\theta\xi(Z_{j}))]$

where $A_{\lambda}(\theta)$ is analytic in $\lambda$, and $Z_{j}\sim
Poi(\lambda\nu_{j})$.

We assume that, for $\lambda=n(1+O(\varepsilon^{2}))$ and
$\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$, we have

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\xi(Z_{j})]=\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]+o(\Delta^{2})$
(43)

$\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\xi(Z_{j})^{2}]=\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]+o(\Delta^{2})$
(44)

$\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}[\xi(Z_{j})^{l}]=o(\Delta^{2})$
(45)

so that

$\operatorname*{\mathbb{E}}[\exp(\varepsilon^{2}\theta\xi(Z_{j}))]=\operatorname*{\mathbb{E}}[f(Z_{j})]+o\left(\Delta^{2}\right)$

where $f$ is defined in (41).

Let $Y_{j}^{n}=\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}=j\\}}$ and
$X_{1},\dots,X_{n}$ be $n$ samples drawn from distribution $\nu$ supported on
$[m]$.

We will show the following:

######  Lemma C.4.

Suppose Assumption 3 holds. Then, if $\nu$ is the uniform distribution such
that $\nu_{j}=1/m$ for all $j$, we have

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\xi(Y_{j}^{n})\right)\right]=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}(\theta^{2}+o(1))\right\\}$

If $\nu$ is an alternate distribution such that
$\nu_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$, and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$, for
$\gamma=\Theta(1),1-\gamma=\Theta(1)$, we have

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\xi(Y_{j}^{n})\right)\right]=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\left(\theta^{2}+\theta\frac{1}{\gamma(1-\gamma)}+o(1)\right)\right\\}$

First, we have that our expression stated can be written as an integral.

######  Lemma C.5.

Consider any function $f:\mathbb{R}\to\mathbb{R}$. If we draw $Z_{j}\sim
Poi(\lambda\nu_{j})$ for $j\in[m]$, and

$\prod_{j=1}^{m}\operatorname*{\mathbb{E}}[f(Z_{j})]$

is analytic in $\lambda$, we have

$\operatorname*{\mathbb{E}}\left[\prod_{j=1}^{m}f(Y_{j}^{n})\right]=\frac{n!}{2\pi
i}\oint\frac{e^{\lambda}}{\lambda^{n+1}}\prod_{j=1}^{m}\operatorname*{\mathbb{E}}[f(Z_{j})]d\lambda$

where $Y_{1}^{n},\dots,Y_{m}^{n}$ are $n$ samples drawn according to $\nu$.

###### Proof.

Conditioning on $\sum_{j=1}^{m}Z_{j}=k$, we have

$\prod_{j=1}^{m}\operatorname*{\mathbb{E}}\left[f(Z_{j})\right]=\operatorname*{\mathbb{E}}\left[\prod_{j=1}^{m}f(Z_{j})\right]=\sum_{k=0}^{\infty}\operatorname*{\mathbb{P}}\left[\sum_{j=1}^{m}Z_{j}=k\right]\operatorname*{\mathbb{E}}\left[\prod_{j=1}^{m}f(Z_{j})\Big{|}\sum_{j=1}^{m}Z_{j}=k\right]$
$=\sum_{k=0}^{\infty}\frac{\lambda^{k}}{k!}e^{-\lambda}\operatorname*{\mathbb{E}}\left[\prod_{j=1}^{m}f(Y_{j}^{n})\right]$

Now, for any analytic function $\phi(\lambda)$ with power series expansion
given by

$\phi(\lambda)=\sum_{k=0}^{\infty}a_{k}\lambda^{k}$

we have by Cauchy’s theorem that

$a_{n}=\frac{1}{2\pi i}\oint\phi(\lambda)\frac{1}{\lambda^{n+1}}d\lambda.$

By assumption, $\prod_{j=1}^{m}\operatorname*{\mathbb{E}}[f(Z_{j})]$ is
analytic in $\lambda$. Therefore,

$\operatorname*{\mathbb{E}}\left[\prod_{j=1}^{m}f(Y_{j}^{n})\right]=\frac{n!}{2\pi
i}\oint\frac{e^{\lambda}}{\lambda^{n+1}}\prod_{j=1}^{m}\operatorname*{\mathbb{E}}[f(Z_{j})]d\lambda$

which is the desired bound.

∎

######  Corollary C.5.1.

Under Assumption 3,

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\xi(Y_{j}^{n})\right)\right]=\frac{n!}{2\pi
i}\oint e^{\lambda}A_{\lambda}(\theta)\frac{d\lambda}{\lambda^{n+1}}$ (46)

We will choose a contour passing through a particular $\lambda_{0}$, and this
will make it easy to evaluate the integral. We carry out the integration along
the contour given by $\lambda=\lambda_{0}e^{i\psi}$, where

$\lambda_{0}=n(1-\varepsilon^{2}\theta)$

We substitute $\lambda_{0}e^{i\psi}$ into (46) to get that

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\xi(Y_{j}^{n})\right)\right]=e^{-\varepsilon^{2}\theta
n}\frac{n!}{2\pi}\lambda_{0}^{-n}Re\left[\int_{-\pi}^{\pi}g(\psi)d\psi\right]$
(47)

with

$g(\psi):=e^{-in\psi}\prod_{j=1}^{m}\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k))\right\\}$
(48)

We will split this integral into $3$ parts. Let

$\begin{gathered}I_{1}=Re\left[\int_{-\pi/3}^{\pi/3}g(\psi)d\psi\right]\\\
I_{2}=Re\left[\int_{-\pi}^{-\pi/3}g(\psi)d\psi\right]\\\
I_{3}=Re\left[\int_{\pi/3}^{\pi}g(\psi)d\psi\right]\end{gathered}$ (49)

We will show that $I_{1}$ dominates. We show this by bounding $g(\psi)$ in the
region $\psi\in[-\pi,-\pi/3]\cup[\pi/3,\pi]$ as follows.

######  Lemma C.6.

Under Assumption 3, and $m\geq C\log n$ for sufficiently large constant $C$,
for $\psi\in[-\pi,-\pi/3]\cup[\pi/3,\pi]$,

$|g(\psi)|\leq O\left(\frac{e^{n}}{n}\right)$

###### Proof.

By definition of $g$ from (48), and using the assumption on $\xi$ from
Assumption 3, we have that,

$\displaystyle|g(\psi)|$
$\displaystyle=\left|e^{-in\psi}\prod_{j=1}^{m}\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k))\right\\}\right|$
$\displaystyle\leq\left|\prod_{j=1}^{m}\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\right\\}\right|+\left|\prod_{j=1}^{m}\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\left(\sum_{l=1}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\xi(k)^{l}\right)\right\\}\right|$

Now, for choice of $\lambda_{0}=n(1-\varepsilon^{2}\theta)$, and
$\psi\in[-\pi,-\pi/3]\cup[\pi/3,\pi]$,

$\left|\prod_{j=1}^{m}\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\right\\}\right|=\left|\prod_{j=1}^{m}e^{\lambda_{0}\nu_{j}e^{i\psi}}\right|=\left|e^{\lambda_{0}e^{i\psi}}\right|=|e^{n(1-\varepsilon^{2}\theta)e^{i\psi}}|\leq
O(e^{0.5n})$

For the second term, by Assumption 3, for our
$\lambda_{0}=n(1-\varepsilon^{2}\theta)$, and $\nu_{j}=1/m+O(\varepsilon/m)$
for all $m$, this is

$\displaystyle
e^{\lambda_{0}}\prod_{j=1}^{m}\left\\{\sum_{l=1}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}[\xi(Z_{j})^{l}]\right\\}$
$\displaystyle=e^{n(1-\varepsilon^{2}\theta)}\prod_{j=1}^{m}\left\\{\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]+\frac{\varepsilon^{4}}{2}\theta^{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]+o(\Delta^{2})\right\\}$

By Lemma D.1, and since $n=o(m/\varepsilon^{2})$, this is

$e^{n(1-\varepsilon^{2}\theta)}\prod_{j=1}^{m}O\left(\frac{n\varepsilon^{2}}{m}\right)\leq
e^{n(1-\varepsilon^{2}\theta)-\Omega(m)}$

Since $m\geq C\log n$ for sufficiently large constant $C$, the claim follows.
∎

Note that this implies that for the integrals defined in (49) that

$I_{2}+I_{3}=O\left(\frac{e^{n}}{n}\right)$ (50)

Now, we will compute $I_{1}$. Define $G(\psi):=\log(g(\psi))$. Then, by
definition of $g$ in (48),

$G(\psi)=-in\psi+\sum_{j=1}^{m}\log\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k))\right\\}$
(51)

Note that

$\text{Im}(G(0))=0$ (52)

Then, applying Lemma D.14,

$\text{Re}(G^{\prime}(0))=0$ (53)

Computing the asymptotic expansion of $G^{\prime\prime}(\psi)$ by Lemma D.4,
we have

$G^{\prime\prime}(\psi)=-ne^{i\psi}+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)+o(1)$
(54)

Now, by Taylor’s theorem, for any $\psi\in[-\pi/3,\pi/3]$ there exists
$\tilde{\psi}\in(0,\psi)$ such that

$G(\psi)=G(0)+G^{\prime}(0)\psi+\frac{G^{\prime\prime}(\tilde{\psi})}{2}\psi^{2}$
(55)

But, by (54), $Re[G^{\prime\prime}(\psi)]\leq-0.4n$ for any
$\psi\in[-\pi/3,\pi/3]$. So, for $\psi\in[-\pi/3,\pi/3]$,

$Re(G(\psi))\leq G(0)-0.2n\psi^{2}$ (56)

Now, we have the following upper bound on $I_{1}$.

######  Lemma C.7.

$I_{1}\leq e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{0.2n}}$

###### Proof.

$I_{1}=Re\left[\int_{-\pi/3}^{\pi/3}e^{G(\psi)}d\psi\right]\leq\int_{-\pi/3}^{\pi/3}e^{Re(G(\psi))}d\psi\leq
e^{G(0)}\int_{-\pi/3}^{\pi/3}e^{-0.2n\psi^{2}}d\psi$ (57)

∎

$\leq
e^{G(0)}\int_{-\infty}^{\infty}e^{-0.2n\psi^{2}}d\psi=e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{0.2n}}$

The next lemma shows that $I_{1}$ is also lower bounded by the above quantity
(up to constants).

######  Lemma C.8.

$I_{1}\geq e^{G(0)}\frac{0.5\sqrt{\pi}}{\sqrt{1.1n}}(1+o(1))$

where $I_{1}$ is defined in (49)

###### Proof.

By (54),
$\text{Im}(G^{\prime\prime}(\psi))=-n\sin(\psi)+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)$.
So, for large enough $n$, since $|\sin(\psi)|\leq|\psi|$, for any
$\psi\in[-\pi/3,\pi/3]$, $|\text{Im}(G^{\prime\prime}(\psi))|\leq 1.1n|\psi|$.
So, by (55), (52) and (53), we have that for constant $c>0$ and
$\psi\in[-\pi/3,\pi/3]$,

$|\text{Im}(G(\psi))|\leq 1.1n|\psi|^{3}+cn\varepsilon^{2}\psi^{2}$

Also, $\text{Re}(G^{\prime\prime}(\psi))\geq-1.1n$ by a similar argument. So,
by (55) and (53), for $\psi\in[-\pi/3,\pi/3]$,

$\text{Re}(G(\psi))\geq G(0)-1.1n\psi^{2}$

Now, for $t_{n}=0.1\min\\{n^{-1/3},\frac{1}{\varepsilon\sqrt{cn}}\\}$, we have
that for $\psi\in[-t_{n},t_{n}]$, $\cos(\text{Im}(G(\psi)))\geq 0.5$ so that
$\text{Re}(e^{G(\psi)})\geq 0.5e^{\text{Re}(G(\psi)}$. We can split $I_{1}$
further into $3$ parts:

$I_{1}=\text{Re}\left[\int_{-\pi/3}^{-t_{n}}e^{G(\psi)}d\psi\right]+\text{Re}\left[\int_{t_{n}}^{\pi/3}e^{G(\psi)}d\psi\right]+\text{Re}\left[\int_{-t_{n}}^{t_{n}}e^{G(\psi)}d\psi\right]$

Now, by (56),

$\left|\int_{-\pi/3}^{-t_{n}}e^{G(\psi)}d\psi\right|\leq
e^{G(0)}\int_{-\infty}^{-t_{n}}e^{-0.2n\psi^{2}}d\psi=t_{n}e^{G(0)}\int_{-\infty}^{-1}e^{-0.2nt_{n}^{2}\bar{\psi}^{2}}d\bar{\psi}$
$\leq
t_{n}e^{G(0)}\int_{-\infty}^{-1}e^{-0.2nt_{n}^{2}|\bar{\psi}|}d\bar{\psi}=e^{G(0)}O\left(\frac{1}{nt_{n}}\right)=e^{G(0)}o\left(\frac{1}{\sqrt{n}}\right)$

In a similar way, we can bound the second term. For the third term, we have

$\text{Re}\left[\int_{-t_{n}}^{t_{n}}e^{G(\psi)}d\psi\right]\geq\int_{-t_{n}}^{t_{n}}0.5e^{\text{Re}(G(\psi))}d\psi\geq
0.5e^{G(0)}\int_{-t_{n}}^{t_{n}}e^{-1.1n\psi^{2}}d\psi$

$\geq
0.5e^{G(0)}\left[\int_{-\infty}^{\infty}e^{-1.1n\psi^{2}}d\psi-2\int_{-\infty}^{-t_{n}}e^{-1.1n\psi^{2}}d\psi\right]$
$\geq
0.5e^{G(0)}\left(\frac{\sqrt{\pi}}{\sqrt{1.1n}}+O\left(\frac{1}{nt_{n}}\right)\right)=0.5e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{1.1n}}(1+o(1))$

Combining the bounds, we get that

$I_{1}\geq e^{G(0)}\frac{0.5\sqrt{\pi}}{\sqrt{1.1n}}(1+o(1))$

∎

Combining the upper bound on $I_{1}$ from Lemma C.7 and the lower bound from
Lemma C.8, we have

$I_{1}=e^{G(0)}\frac{1}{\sqrt{n}}e^{O(1)}$

So, by (47) and (50),

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}_{\nu}\left[\xi(Y_{j}^{n})\right]=e^{-\varepsilon^{2}\theta
n}\frac{n!}{2\pi}\lambda_{0}^{-n}e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{0.2n}}(1+o(1))$
(58)

So, it remains to compute $G(0)$.

######  Lemma C.9.

Under Assumption 3,

$G(0)=\lambda_{0}+\sum_{j=1}^{m}\left\\{\varepsilon^{2}\theta\left[(\lambda_{0}\nu_{j})^{2}+\lambda_{0}\nu_{j}-2\lambda_{0}\nu_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}\right]+\frac{\varepsilon^{4}\theta^{2}}{2}\left[4(\lambda_{0}\nu_{j})^{3}+6(\lambda_{0}\nu_{j})^{2}+(\lambda_{0}\nu_{j})-8(\lambda_{0}\nu_{j})^{2}\frac{n}{m}-4\frac{n}{m}(\lambda_{0}\nu_{j})+4\frac{n^{2}}{m^{2}}(\lambda_{0}\nu_{j})\right]+o\left(\Delta^{2}\right)\right\\}$
(59)

###### Proof.

Using equation (51), we have

$G(0)=\lambda_{0}+\sum_{j=1}^{m}\log\left\\{\operatorname*{\mathbb{E}}\left[\exp(\varepsilon^{2}\theta\xi(Z_{j}))\right]\right\\}$

where $Z_{j}\sim Poi(\lambda_{0}\nu_{j})$. By Assumption 3, we have that this
is

$\lambda_{0}+\sum_{j=1}^{m}\log\left\\{\operatorname*{\mathbb{E}}\left[f(Z_{j})\right]+o\left(\Delta^{2}\right)\right\\}$

Using the definition of $f$ from (41), this is

$\lambda_{0}+\sum_{j=1}^{m}\log\left\\{1+\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]+\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]+o\left(\Delta^{2}\right)\right\\}$

Since by Lemma D.1,
$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]$ and
$\varepsilon^{4}\frac{\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]$
are $o(1)$, using the fact that $\log(1+x)=x-x^{2}/2+O(x^{3})$ for $x\to 0$,
we have

$G(0)=\lambda_{0}+\sum_{j=1}^{m}\left\\{\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]+\frac{\varepsilon^{4}\theta^{2}}{2}\left(\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]-\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]^{2}\right)+o\left(\Delta^{2}\right)\right\\}$

Now, using Lemma D.11, we have that

$G(0)=\lambda_{0}+\sum_{j=1}^{m}\left\\{\varepsilon^{2}\theta\left[(\lambda_{0}\nu_{j})^{2}+\lambda_{0}\nu_{j}-2\lambda_{0}\nu_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}\right]+\frac{\varepsilon^{4}\theta^{2}}{2}\left[4(\lambda_{0}\nu_{j})^{3}+6(\lambda_{0}\nu_{j})^{2}+(\lambda_{0}\nu_{j})-8(\lambda_{0}\nu_{j})^{2}\frac{n}{m}-4\frac{n}{m}(\lambda_{0}\nu_{j})+4\frac{n^{2}}{m^{2}}(\lambda_{0}\nu_{j})\right]+o\left(\Delta^{2}\right)\right\\}$

∎

######  Lemma C.10.

For the uniform distribution so that $\nu_{j}=1/m$ for all $j$, and
$\lambda_{0}=n(1-\varepsilon^{2}\theta)$,

$G(0)=\lambda_{0}+\varepsilon^{2}\theta
n+\varepsilon^{4}\theta^{2}\left(-\frac{n}{2}+\frac{n^{2}}{m}\right)+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)$

###### Proof.

Substituting $\nu_{j}=1/m$ for all $j$, and
$\lambda_{0}=n(1-\varepsilon^{2}\theta)$, we have

$\sum_{j=1}^{m}\left[(\lambda_{0}\nu_{j})^{2}+\lambda_{0}\nu_{j}-2\lambda_{0}\nu_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}\right]=n-n\varepsilon^{2}\theta+\frac{n^{2}\varepsilon^{4}}{m}\theta^{2}$

$\sum_{j=1}^{m}\left[4(\lambda_{0}\nu_{j})^{3}+6(\lambda_{0}\nu_{j})^{2}+(\lambda_{0}\nu_{j})-8(\lambda_{0}\nu_{j})^{2}\frac{n}{m}-4\frac{n}{m}(\lambda_{0}\nu_{j})+4\frac{n^{2}}{m^{2}}(\lambda_{0}\nu_{j})\right]=n+2\frac{n^{2}}{m}+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)$

So, by Lemma C.9, we have

$G(0)=\lambda_{0}+\varepsilon^{2}\theta
n+\varepsilon^{4}\theta^{2}\left(\frac{-n}{2}+\frac{n^{2}}{m}\right)+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)$

∎

######  Lemma C.11.

For alternate distributions such that
$\nu_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$, and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma$, for
$\gamma=\Theta(1),1-\gamma=\Theta(1)$, and
$\lambda_{0}=n(1-\varepsilon^{2}\theta)$, we have

$G(0)=\lambda_{0}+\varepsilon^{2}\theta
n+\varepsilon^{4}\theta^{2}\left(\frac{n}{2}+\frac{n^{2}}{m}\right)+\varepsilon^{4}\theta\frac{n(\gamma
m^{2}\theta-\gamma^{2}m^{2}\theta-
mn)}{\gamma(\gamma-1)m^{2}}+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)$

###### Proof.

We have

$\sum_{j=1}^{m}\left[(\lambda_{0}\nu_{j})^{2}+\lambda_{0}\nu_{j}-2\lambda_{0}\nu_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}\right]=n-\frac{n(mn+\gamma^{2}m^{2}\theta-\gamma
m^{2}\theta)\varepsilon^{2}}{\gamma(\gamma-1)m^{2}}+o\left(\frac{n^{2}\varepsilon^{2}}{m}\right)$

$\sum_{j=1}^{m}\left[4(\lambda_{0}\nu_{j})^{3}+6(\lambda_{0}\nu_{j})^{2}+(\lambda_{0}\nu_{j})-8(\lambda_{0}\nu_{j})^{2}\frac{n}{m}-4\frac{n}{m}(\lambda_{0}\nu_{j})+4\frac{n^{2}}{m^{2}}(\lambda_{0}\nu_{j})\right]=n+2\frac{n^{2}}{m}+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)$

Thus, for this $\nu$, from Lemma C.9,

$G(0)=\lambda_{0}+\varepsilon^{2}\theta
n+\varepsilon^{4}\theta^{2}\left(\frac{n}{2}+\frac{n^{2}}{m}\right)+\varepsilon^{4}\theta\frac{n(\gamma
m^{2}\theta-\gamma^{2}m^{2}\theta-
mn)}{\gamma(\gamma-1)m^{2}}+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)$

∎

Finally, we prove the main lemma.

###### Proof of Lemma C.4.

By (58), substituting $\lambda_{0}=n(1-\varepsilon^{2}\theta)$ and $G(0)$ from
Lemma C.10, we have for uniform $\nu$,

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}_{\nu}\left[\xi(Y_{j}^{n})\right]=e^{-\varepsilon^{2}\theta
n}\frac{e^{n}n!}{\sqrt{2\pi
n}}(n(1-\varepsilon^{2}\theta))^{-n}\exp\left\\{-n\varepsilon^{2}\theta+n\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}\left(-\frac{n}{2}+\frac{n^{2}}{m}\right)+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)\right\\}$

$=e^{-\varepsilon^{2}\theta n}\frac{e^{n}n!}{n^{n}\sqrt{2\pi
n}}\exp\left\\{-n\left(-\varepsilon^{2}\theta-\frac{\varepsilon^{4}\theta^{2}}{2}\right)\right\\}\exp\left\\{\varepsilon^{4}\theta^{2}\left(-\frac{n}{2}+\frac{n^{2}}{m}\right)+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)\right\\}$

$=\frac{e^{n}n!}{n^{n}\sqrt{2\pi
n}}\exp\left\\{\varepsilon^{4}\theta^{2}\left(\frac{n^{2}}{m}\right)+o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)\right\\}$
$=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\left(\theta^{2}+o(1)\right)\right\\}$

By (58), substituting $\lambda_{0}=n(1-\varepsilon^{2}\theta)$ and $G(0)$ from
Lemma C.11, for $\nu$ such that $\nu_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma
m}$ for $j\leq\gamma m$ and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>(1-\gamma)m$,
with $\gamma=\Theta(1),(1-\gamma)=\Theta(1)$, we have

$\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}_{\nu}[\xi(Y_{j}^{n})]=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\left(\theta^{2}+\theta\frac{1}{\gamma(1-\gamma)}+o(1)\right)\right\\}$

∎

Finally, this gives us the MGF of the Huber statistic.

######  Lemma C.12.

We have that for uniform $\nu$ such that $\nu_{j}=1/m$ for all $j$,

$\operatorname*{\mathbb{E}}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)\right]=\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}h_{\beta}\left(Y_{j}^{n}-\frac{n}{m}\right)\right)\right]$
$=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}(\theta^{2}+o(1))\right\\}$

and for alternate $\nu$ such that
$\nu_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>(1-\gamma)m$, for
$\gamma=\Theta(1),1-\gamma=\Theta(1)$,

$\operatorname*{\mathbb{E}}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)\right]=\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}h_{\beta}\left(Y_{j}^{n}-\frac{n}{m}\right)\right)\right]$
$=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\left(\theta^{2}+\theta\frac{1}{\gamma(1-\gamma)}+o(1)\right)\right\\}$

###### Proof.

Note that Assumption 3 holds for $A_{\lambda}(\theta)$ as defined in (40) due
to Lemma C.1. So, by Lemma C.4, the claim holds. ∎

###  C.4 Application of the Gärtner-Ellis Theorem

In this section, we apply the Gärtner-Ellis Theorem to obtain the probability
that our statistic crosses a threshold, under the uniform distribution, and
under one of the worst-case $\varepsilon$-far distributions.

######  Lemma C.13.

Under the uniform distribution $p$, we have that for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\frac{\tau^{2}}{4}$

Under an $\varepsilon$-far distribution $q$ of the form
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq l$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>l$, and
$\gamma=\Theta(1)$, $1-\gamma=\Theta(1)$, for
$\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

###### Proof.

Note that by Lemma C.12, the limiting logarithmic moment generating function
with respect to the uniform distribution $p$ is given by

$\Lambda_{p}(\theta)=\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{E}}_{p}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)\right]\right)=\theta^{2}$

Thus, Assumption 1 holds for $\mathcal{D}_{\Lambda_{p}}=\mathbb{R}$.
Furthermore, the Fenchel-Legendre Transform (defined in equation 30) of
$\Lambda_{p}$ is given by

$\Lambda_{p}^{*}(\tau)=\sup_{\theta}\\{\theta\tau-\theta^{2}\\}=\frac{\tau^{2}}{4}$

This is a strongly convex function of $\tau$, so the set of exposed points of
$\Lambda_{p}^{*}$ whose exposing hyperplane belongs to
$\mathcal{D}_{\Lambda_{p}}^{o}$ is all of $\mathbb{R}$. Thus, by the Theorem
B.2 (Gärtner-Ellis), for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\inf_{x\geq\tau}\Lambda_{p}^{*}(x)=\frac{\tau^{2}}{4}$

Similarly, the limiting logarithmic moment generating function with respect to
an alternate distribution $q$ is given by

$\Lambda_{q}(\theta)=\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{E}}_{q}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)\right]\right)=\theta^{2}+\frac{1}{\gamma(1-\gamma)}\theta$

The Fenchel-Legendre transform is given by

$\Lambda_{q}^{*}(\tau)=\sup_{\theta}\left\\{\theta\tau-\theta^{2}-\frac{1}{\gamma(1-\gamma)}\theta\right\\}=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

Again, applying the Gärtner-Ellis Theorem gives, for
$\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}_{n}^{*}\leq\tau\right]\right)=\inf_{x\leq\tau}\Lambda^{*}_{q}(x)=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

∎

###  C.5 Setting the threshold

We need to set our threshold $\tau$ so that the minimum of the error
probability under the uniform distribution $p$, and any $\varepsilon$-far
distribution $q$ is maximized. Note that by Lemma C.13, it is sufficient to
consider a threshold $\tau$ such that $0<\tau<\frac{1}{\gamma(1-\gamma)}$,
since otherwise, the error probability in one of the two cases is at least
constant. To set our threshold, we will first observe that for any $\tau$ in
this range, the “error exponent” under $\varepsilon$-far distributions is
minimized for a particular $\varepsilon$-far distribution. Then, we will set
the threshold to maximize the minimum of the error exponent under the uniform
distribution, and under this $\varepsilon$-far distribution.

######  Lemma C.14.

Setting the threshold $\tau=2$, we have for the uniform distribution $p$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=1$

and for any $\varepsilon$-far distribution $q$ such that
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$ and
$\gamma=\Theta(1),1-\gamma=\Theta(1)$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq
1$

with equality for $q$ such that $q_{j}=\frac{1}{m}+\frac{2\varepsilon}{m}$ for
$j\leq m/2$ and $q_{j}=\frac{1}{m}-\frac{2\varepsilon}{m}$ for $j>m/2$.

###### Proof.

By Lemma C.13, for $0<\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

Now, the numerator of the right hand side is minimized when $\gamma=1/2$, and
the denominator is maximized when $\gamma=1/2$. Thus, the right hand side is
minimized when $\gamma=1/2$. So, we have that,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq\frac{1}{4}(\tau-4)^{2}$

with equality for distribution $q$ such that $q_{j}=1/m+2\varepsilon/m$ for
$j\leq m/2$ and $q_{j}=1/m-2\varepsilon/m$ for $j>m/2$.

Then, the claim follows by substituting in $\tau=2$ in the expression for the
uniform distribution in Lemma C.13 and in the above expression. ∎

Recall that our target sample complexity is

$\displaystyle n=(1+o(1))\sqrt{m\log\frac{1}{\delta}}/\varepsilon^{2}$ (4)

We have our result for the Huber tester.

######  Theorem C.15 (Huber with $n/m\gtrsim 1$).

The Huber statistic for appropriate $\beta$ achieves (4) for $1\lesssim n/m\ll
1/\varepsilon^{2}$, $\varepsilon,\delta\ll 1$ and $m\geq C\log n$ for
sufficiently large constant $C$.

###### Proof.

First we need to show that for every $(n,m,\varepsilon)$ that satisfy our
conditions, there is a $\beta,\Delta$ that satisfies (14), (13) and (15). We
will set

$\Delta=\frac{n\varepsilon^{2}}{m}$

so that (14) is satisfied. Then, observe that (13) and (15) can be satisfied
as long as

$\log\left(\frac{1}{\Delta}\right)+\sqrt{\frac{n}{m}\log\left(\frac{1}{\Delta}\right)}=o\left(\frac{\Delta^{1/3}}{\varepsilon}\right)$

Now, since $n=\Omega(m)$,

$\log\left(\frac{1}{\Delta}\right)=\log\left(\frac{m}{n\varepsilon^{2}}\right)=o\left(\log\left(\frac{1}{\varepsilon}\right)\right)=o\left(\frac{1}{\varepsilon^{1/3}}\right)=o\left(\frac{n^{1/3}}{m^{1/3}\varepsilon^{1/3}}\right)=o\left(\frac{\Delta^{1/3}}{\varepsilon}\right)$

and since
$n=o\left(\frac{m}{\varepsilon^{2}\log^{3}\left(\frac{m}{n\varepsilon^{2}}\right)}\right)$,

$\sqrt{\frac{n}{m}\log\left(\frac{1}{\Delta}\right)}=\sqrt{\frac{n}{m}\log\left(\frac{m}{n\varepsilon^{2}}\right)}=o\left(\frac{n^{1/3}}{m^{1/3}\varepsilon^{1/3}}\right)=o\left(\frac{\Delta^{1/3}}{\varepsilon}\right)$

By Lemma C.14, we have that $\bar{c}(\varepsilon,m,C)=1$ for every
$\varepsilon$ that satisfies our assumptions, and every $C>2$. In particular,
any $\varepsilon^{\prime}$ such that
$\left(1-\frac{1}{C^{\prime}}\right)\varepsilon(n)\leq\varepsilon^{\prime}(n)\leq\varepsilon(n)$
has $\bar{c}(\varepsilon^{\prime},m,C)=1$ for every $C>2$. Thus, by Lemma
B.10, we have that $c(\varepsilon,m)=1$ for every $\varepsilon$ that satisfies
our assumptions. The claim follows. ∎

Since the Huber statistic for $\beta=0$ is equivalent to the TV statistic,
Theorem C.15 and Theorem 1.5 together give us the main result. See 1.2

##  Appendix D MGF computation Lemmas

###  D.1 Huber Lemmas

######  Lemma D.1.

Suppose Assumption 2 holds. For $Z_{j}\sim Poi(\lambda_{0}\nu_{j})$ and
$\lambda_{0}=n(1-\varepsilon^{2}\theta)$,
$\nu_{j}=\frac{1}{m}+O\left(\frac{\varepsilon}{m}\right)$, and for
$n=\Omega(m)$

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j}+c)^{2}]=O\left(\frac{n\varepsilon^{2}}{m}\right)$
$\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j}+c)^{4}]=O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)$

for any $0\leq c\leq 4$

###### Proof.

Note that $\lambda_{0}\nu_{j}=\frac{n}{m}+O(\frac{n\varepsilon}{m})$. Then,
using Lemma D.11,

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]=\varepsilon^{2}\theta\left(\frac{n}{m}+O\left(\frac{n\varepsilon}{m}\right)+O\left(\frac{n^{2}\varepsilon^{2}}{m^{2}}\right)\right)=O\left(\frac{n\varepsilon^{2}}{m}\right)$

since $n=o(m/\varepsilon^{2})$.

Similarly,

$\varepsilon^{4}\frac{\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]=\varepsilon^{4}\frac{\theta^{2}}{2}\left[\frac{n}{m}+O(\frac{n^{2}}{m^{2}})+O(\frac{n^{3}\varepsilon^{2}}{m^{3}})+O(\frac{n^{4}\varepsilon^{4}}{m^{4}})\right]=O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)$

Now,

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j}+c)^{2}]=\varepsilon^{2}\theta\operatorname*{\mathbb{E}}\left[\left(Z_{j}+c-\frac{n}{m}\right)^{2}\right]=\varepsilon^{2}\theta\operatorname*{\mathbb{E}}\left[\phi(Z_{j})^{2}+2c\left(Z_{j}-\frac{n}{m}\right)+c^{2}\right]$
$=O\left(\frac{n\varepsilon^{2}}{m}\right)+O(\varepsilon^{2})=O\left(\frac{n\varepsilon^{2}}{m}\right)$

since $\varepsilon^{2}=O\left(\frac{n\varepsilon^{2}}{m}\right)$.

Similarly,

$\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j}+c)^{4}]=\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}\left[\phi(Z_{j})^{4}+4c\left(Z_{j}-\frac{n}{m}\right)^{3}+6c^{2}\phi(Z_{j})^{2}+4c^{3}\left(Z_{j}-\frac{n}{m}\right)+c^{4}\right]$

Now,

$\operatorname*{\mathbb{E}}\left[4c\left(Z_{j}-\frac{n}{m}\right)^{3}\right]=4\operatorname*{\mathbb{E}}\left[Z_{j}^{3}-3Z_{j}^{2}\frac{n}{m}+3Z_{j}\frac{n^{2}}{m^{2}}-\frac{n^{3}}{m^{3}}\right]$

By Lemma D.13, this is

$4\left[(\lambda_{0}\nu_{j})^{3}+3(\lambda_{0}\nu_{j})^{2}+\lambda_{0}\nu_{j}-3((\lambda_{0}\nu_{j})^{2}+\lambda_{0}\nu_{j})\frac{n}{m}+3\lambda_{0}\nu_{j}\frac{n^{2}}{m^{2}}-\frac{n^{3}}{m^{3}}\right]$

Now, since
$\lambda_{0}\nu_{j}=\frac{n}{m}+O\left(\frac{n\varepsilon}{m}\right)$, this is

$\frac{n}{m}+O\left(\frac{n^{2}\varepsilon}{m^{2}}\right)+O\left(\frac{n^{3}\varepsilon^{3}}{m^{3}}\right)$

so that

$\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}\left[4c\left(Z_{j}-\frac{n}{m}\right)^{3}\right]=O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)=O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)$

So, finally

$\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j}+c)^{4}]=O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)$

as required. ∎

######  Lemma D.2.

Suppose Assumption 2 holds. For $Z_{j}\sim Poi(\lambda_{0}\nu_{j})$, and
$\lambda_{0}=n(1-\varepsilon^{2}\theta)$,
$\nu_{j}=\frac{1}{m}+O(\frac{\varepsilon}{m})$ for all $j$,

$\prod_{j=1}^{m}\left\\{\operatorname*{\mathbb{E}}\left[f(Z_{j})\right]+o\left(\Delta^{2}\right)\right\\}=\exp\\{O(n\varepsilon^{2})\\}$

where $f$ is defined in (41)

###### Proof.

$\displaystyle\prod_{j=1}^{m}\left\\{\operatorname*{\mathbb{E}}\left[f(Z_{j})\right]+o\left(\Delta^{2}\right)\right\\}=\exp\left\\{\sum_{j=1}^{m}\log\left[\operatorname*{\mathbb{E}}\left[f(Z_{j})\right]+o\left(\Delta^{2}\right)\right]\right\\}$

Note that due to Lemma D.1, $\Delta=O\left(\frac{n\varepsilon^{2}}{m}\right)$,
and the fact that $n=o(m/\varepsilon^{2})$, the above is

$\exp\left\\{\sum_{j=1}^{m}\log\left[1+O\left(\frac{n\varepsilon^{2}}{m}\right)\right]\right\\}$

We can Taylor expand the $\log$ since it is of form $\log(1+o(1))$. The above
is then

$\exp\left\\{\sum_{j=1}^{m}\left[O\left(\frac{n\varepsilon^{2}}{m}\right)\right]\right\\}=\exp\\{O(n\varepsilon^{2})\\}$

Setting $\eta\geq 2$, this is

$\exp(O(n\varepsilon^{2}))$

∎

######  Lemma D.3.

Suppose Assumption 2 holds. For $\lambda_{0}=n(1-\varepsilon^{2}\theta)$ and
$\nu_{j}=\frac{1}{m}+O\left(\frac{\varepsilon}{m}\right)$ for all $j$, and for
$\xi$ that satisfies Assumption 3, where $Z_{j}\sim Poi(\lambda_{0}\nu_{j})$,
we have

$\displaystyle
e^{-2\lambda_{0}\nu_{j}}\left|\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k+1))\right)^{2}\right.$
$\displaystyle\left.-\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k))\right)\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k+2))\right)\right|=O(\varepsilon^{2})+O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)$

and

$e^{-2\lambda_{0}\nu_{j}}\left|\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k))\right)\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\exp(\varepsilon^{2}\theta\xi(k+1))\right)\right|=1+O\left(\frac{n\varepsilon^{2}}{m}\right)$

###### Proof.

Notation: For simplicity, let
$\tilde{\operatorname*{\mathbb{E}}}[f(W_{j})]=\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k)$
Note that

$\tilde{\operatorname*{\mathbb{E}}}[f(W_{j})+g(W_{j})]=\tilde{\operatorname*{\mathbb{E}}}[f(W_{j})]+\tilde{\operatorname*{\mathbb{E}}}[g(W_{j})]$

Also, note that
$\left|e^{-\lambda_{0}\nu_{j}}\tilde{\operatorname*{\mathbb{E}}}[f(W_{j})]\right|=\operatorname*{\mathbb{E}}[f(Z_{j})]$
where $Z_{j}\sim Poi(\lambda_{0}\nu_{j})$. We have that,

$\displaystyle\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}+1))]^{2}=\tilde{\operatorname*{\mathbb{E}}}\left[1+\varepsilon^{2}\theta\xi(W_{j}+1)+\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}+1))^{l}}{l!}\right]^{2}$
$\displaystyle=\tilde{\operatorname*{\mathbb{E}}}\left[1+\varepsilon^{2}\theta\xi(W_{j}+1)\right]^{2}+2\tilde{\operatorname*{\mathbb{E}}}\left[1+\varepsilon^{2}\theta\xi(W_{j}+1)\right]\tilde{\operatorname*{\mathbb{E}}}\left[\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}+1))^{l}}{l!}\right]+\tilde{\operatorname*{\mathbb{E}}}\left[\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}+1))^{l}}{l!}\right]^{2}$

Similarly,

$\displaystyle\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}))]\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}+2))]=\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j})]\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j}+2)]$
$\displaystyle+\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j})]\tilde{\operatorname*{\mathbb{E}}}\left[\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}+2))^{l}}{l!}\right]$
$\displaystyle+\tilde{\operatorname*{\mathbb{E}}}\left[\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}))^{l}}{l!}\right]\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j}+1)]+\tilde{\operatorname*{\mathbb{E}}}\left[\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}))^{l}}{l!}\right]\tilde{\operatorname*{\mathbb{E}}}\left[\sum_{l=2}^{\infty}\frac{(\varepsilon^{2}\theta\xi(W_{j}+2))^{l}}{l!}\right]$

So, using the properties of $\xi$ from Assumption 3, this first expression is

$\displaystyle
e^{-2\lambda_{0}\nu_{j}}\left|\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}+1))]^{2}-\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}))]\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}+2))]\right|$
$\displaystyle\leq
e^{-2\lambda_{0}\nu_{j}}\left|\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j}+1)]^{2}-\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j})]\tilde{\operatorname*{\mathbb{E}}}[1+\varepsilon^{2}\theta\xi(W_{j}+2)]\right|+o(\Delta^{2})$
$\displaystyle=e^{-2\lambda_{0}\nu_{j}}\left|\varepsilon^{2}\theta\tilde{\operatorname*{\mathbb{E}}}[1]\left\\{2\tilde{\operatorname*{\mathbb{E}}}[\xi(W_{j}+1)]-\tilde{\operatorname*{\mathbb{E}}}[\xi(W_{j})]-\tilde{\operatorname*{\mathbb{E}}}[\xi(W_{j}+2)]\right\\}\right.$
$\displaystyle\left.+\varepsilon^{4}\theta^{2}\left\\{\tilde{\operatorname*{\mathbb{E}}}[\xi(W_{j}+1)]^{2}-\tilde{\operatorname*{\mathbb{E}}}[\xi(W_{j})]\tilde{\operatorname*{\mathbb{E}}}[\xi(W_{j}+2)]\right\\}\right|+o(\Delta^{2})$
$\displaystyle=\varepsilon^{2}\theta\left\\{2\operatorname*{\mathbb{E}}[\xi(Z_{j}+1)]-\operatorname*{\mathbb{E}}[\xi(Z_{j})]-\operatorname*{\mathbb{E}}[\xi(Z_{j}+2)]\right\\}+\varepsilon^{4}\theta^{2}\left\\{\operatorname*{\mathbb{E}}[\xi(Z_{j}+1)]^{2}-\operatorname*{\mathbb{E}}[\xi(Z_{j})]\operatorname*{\mathbb{E}}[\xi(Z_{j}+2)]\right\\}+o(\Delta^{2})$

Using properties of $\xi$, this is

$\displaystyle\varepsilon^{2}\theta\left\\{2\operatorname*{\mathbb{E}}[\phi(Z_{j}+1)^{2}]-\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]-\operatorname*{\mathbb{E}}[\phi(Z_{j}+2)^{2}]\right\\}$
$\displaystyle+\varepsilon^{4}\theta^{2}\left\\{\operatorname*{\mathbb{E}}[\phi(Z_{j}+1)^{2}]^{2}-\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]\operatorname*{\mathbb{E}}[\phi(Z_{j}+2)^{2}]\right\\}+o(\Delta^{2})$

Simplifying using the definition of $\phi$, and applying Lemma D.1, this is

$O(\varepsilon^{2})+O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)$

This gives us the first claim. For the second claim, we have the expression

$\displaystyle
e^{-2\lambda_{0}\nu_{j}}|\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}))]\tilde{\operatorname*{\mathbb{E}}}[\exp(\varepsilon^{2}\theta\xi(W_{j}+1))]|=\operatorname*{\mathbb{E}}[\exp(\varepsilon^{2}\theta\xi(Z_{j}))]\operatorname*{\mathbb{E}}[\exp(\varepsilon^{2}\theta\xi(Z_{j}+1))]$

By properties of $\xi$ from Assumption 3, and using Lemma D.1, this is

$1+O\left(\frac{n\varepsilon^{2}}{m}\right)$

∎

######  Lemma D.4.

Suppose Assumption 2 holds. For $\lambda_{0}=n(1-\varepsilon^{2}\theta)$,
$\nu_{j}=\frac{1}{m}+O\left(\frac{\varepsilon}{m}\right)$, and $\xi$ that
satisfies Assumption 3,

and

$G(\psi)=-in\psi+\sum_{j=1}^{m}\log\left\\{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}\xi(k)\right\\}$

we have

$G^{\prime\prime}(\psi)=-ne^{i\psi}+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)$

###### Proof.

By Lemmas D.1, D.3 and D.14 we have

$G^{\prime\prime}(\psi)=\sum_{j=1}^{m}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{2}\left\\{O(\varepsilon^{2})+O\left(\left(\frac{n\varepsilon^{2}}{m}\right)^{2}\right)\right\\}-(\lambda_{0}\nu_{j}e^{i\psi})(1+O(\frac{n\varepsilon^{2}}{m}))}{(1+O(\frac{n\varepsilon^{2}}{m}))}$

By Lemma D.1, this is,

$\sum_{j=1}^{m}\left\\{O\left(\frac{n^{2}\varepsilon^{2}}{m^{2}}\right)-(\lambda_{0}\nu_{j}e^{i\psi})\left(1+O\left(\frac{n\varepsilon^{2}}{m}\right)\right)\right\\}\left(1+O\left(\frac{n\varepsilon^{2}}{m}\right)\right)$

$=-(\lambda_{0}e^{i\psi})\left(1+O\left(\frac{n\varepsilon^{2}}{m}\right)\right)+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)=-ne^{i\psi}+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)$

∎

######  Lemma D.5.

Suppose Assumption 2 holds. For $\lambda_{0}=n(1+O(\varepsilon^{2})$ and $\nu$
such that $\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$, and $\theta=O(1)$, we
have

$\left|\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)\leq\beta\\}}\left\\{\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta\phi(Z_{j}+c)^{2})^{l}}{l!}\right\\}\right]\right|=o\left(\Delta^{2}\right)$

where $Z_{j}\sim Poi(\lambda_{0}\nu_{j})$

###### Proof.

We have that

$\displaystyle\left|\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)\leq\beta\\}}\left\\{\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta\phi(Z_{j}+c)^{2})^{l}}{l!}\right\\}\right]\right|$
$\displaystyle\leq\left|\operatorname*{\mathbb{E}}\left[\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta\beta^{2})^{l}}{l!}\right]\right|$
$\displaystyle\leq\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta\beta^{2})^{l}}{l!}$
$\displaystyle=O\left((\varepsilon^{2}\theta\beta^{2})^{3}\sum_{l=0}^{\infty}\frac{(\varepsilon^{2}\theta\beta^{2})^{l}}{l!}\right)$

Also,

$\sum_{l=0}^{\infty}\frac{(\varepsilon^{2}\theta\beta^{2})^{l}}{l!}=\exp(\varepsilon^{2}\theta\beta^{2})$

But, by (36),

$\varepsilon^{2}\theta\beta^{2}=o(1)$

Thus, we have that

$\exp(\varepsilon^{2}\theta\beta^{2})=e^{o(1)}=O(1)$

Putting the above together gives us the claim. ∎

######  Lemma D.6.

Suppose Assumption 2 holds. For
$\lambda=n(1+O(\varepsilon^{2})+O(\frac{n}{m}\varepsilon^{2}))$ and $\nu$ such
that $\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$, for any $\beta$,

$\operatorname*{\mathbb{P}}[\phi(Z_{j}+c)>\beta]\leq
2\exp\left\\{-\frac{\Omega(\beta^{2})}{O(\frac{n}{m})}\right\\}+2\exp\left\\{-\Omega(\beta)\right\\}$

for integer $0\leq c\leq 3$ and any constant $\eta>0$.

###### Proof.

Note that for the conditions given,

$\lambda\nu_{j}=\frac{n}{m}+O(\frac{n\varepsilon}{m})$

Now, since $Z_{j}\sim Poi(\lambda\nu_{j})$ and
$\lambda=n(1+O(\varepsilon^{2})+O(\frac{n}{m}\varepsilon^{2}))$,

$\operatorname*{\mathbb{E}}[\mathbbm{1}_{\phi(Z_{j}+c)>\beta}]=\operatorname*{\mathbb{P}}[\phi(Z_{j}+c)>\beta]=\operatorname*{\mathbb{P}}\left[\left|Z_{j}+c-\frac{n}{m}\right|>\beta\right]$
$\leq\operatorname*{\mathbb{P}}\left[\left|Z_{j}-\lambda\nu_{j}\right|>\beta+\left|\lambda\nu_{j}+c-\frac{n}{m}\right|\right]\leq\operatorname*{\mathbb{P}}\left[\left|Z_{j}-\lambda\nu_{j}\right|>\beta+O(\frac{n\varepsilon}{m})\right]$

Using Poisson concentration bounds [6], this is at most

$2\exp\left\\{-\frac{\left(\beta+O(\frac{n\varepsilon}{m})\right)^{2}}{\lambda\nu_{j}+\left(\beta+O(\frac{n\varepsilon}{m})\right)}\right\\}=2\exp\left\\{-\frac{\left(\beta+O(\frac{n\varepsilon}{m})\right)^{2}}{\frac{n}{m}+\beta+O(\frac{n\varepsilon}{m})}\right\\}$

Now, if $\beta=O(\frac{n}{m})$, this is

$2\exp\left\\{-\frac{(\beta+O(\frac{n\varepsilon}{m}))^{2}}{O(\frac{n}{m})+O(\frac{n\varepsilon}{m})}\right\\}=2\exp\left\\{-\frac{\Omega(\beta^{2})}{O(\frac{n}{m})}\right\\}$

Similarly, if instead $\frac{n}{m}=O(\beta)$, the bound is

$2\exp\left\\{-\frac{(\beta+O(\frac{n\varepsilon}{m}))^{2}}{O(\beta)+O(\frac{n\varepsilon}{m})}\right\\}=2\exp\left\\{-\Omega(\beta)\right\\}$

The claim follows.

∎

######  Lemma D.7.

Suppose Assumption 2 holds. For
$\lambda=n(1+O(\varepsilon^{2})+O(\frac{n}{m}\varepsilon^{2}))$ and $\nu$ such
that $\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$, for $\beta$ such that (13) is
satisfied,

$\operatorname*{\mathbb{E}}[\mathbbm{1}_{\phi(Z_{j}+c)>\beta}]=O\left(\Delta^{2\eta}\right)$

for integer $0\leq c\leq 3$ and any constant $\eta>0$.

###### Proof.

By Lemma D.6,

$\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}]\leq
2\exp\left\\{-\frac{\Omega(\beta^{2})}{O(\frac{n}{m})}\right\\}+2\exp\left\\{-\Omega(\beta)\right\\}$

But by (13), this is

$4\exp\left\\{-\omega\left(\log\left(\frac{1}{\Delta}\right)\right)\right\\}=O\left(\Delta^{2\eta}\right)$

∎

######  Lemma D.8.

Suppose Assumption 2 holds. For $\lambda=n(1+O(\varepsilon^{2}))$,
$\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$, we have

$\left|\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}\varepsilon^{2}\theta\phi(Z_{j}+c)^{2}\right]\right|=o\left(\Delta^{2}\right)$

$\left|\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}\frac{\varepsilon^{4}\theta^{2}}{2}\phi(Z_{j}+c)^{4}\right]\right|=o\left(\Delta^{2}\right)$

for integer $0<c\leq 3$ and $Z_{j}\sim\text{Poi}(\lambda\nu_{j})$

###### Proof.

We have

$\left|\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}\varepsilon^{2}\theta\phi(Z_{j}+c)^{2}\right]\right|\leq\sum_{l=0}^{\infty}\left|\operatorname*{\mathbb{P}}\left[\phi(Z_{j}+c)>2^{l}\beta\right]\varepsilon^{2}\theta(2^{l+1}\beta)^{2}\right|$

By Lemma D.6, this is

$\sum_{l=0}^{\infty}\left|\left(2\exp\left\\{-\frac{\Omega(2^{2l}\beta^{2})}{O(\frac{n}{m})}\right\\}+2\exp\left\\{-\Omega(2^{l}\beta)\right\\}\right)\varepsilon^{2}\theta(2^{l+1}\beta)^{2}\right|$

By (13), this is

$\sum_{l=0}^{\infty}\left|O\left(\Delta^{2^{l}\eta}\right)\varepsilon^{2}\theta(2^{l+1}\beta)^{2}\right|$

Note that by (15), $\varepsilon^{2}\beta^{2}=o(1)$. Thus, this is

$\sum_{l=0}^{\infty}\left|O\left(\Delta^{2^{l}\eta}\right)o(1)2^{2(l+1)}\right|$

Setting $\eta\geq 3$, since $2^{2(l+1)}\leq O(2^{2^{l}})$ we have that this is
this is

$O\left(\Delta^{3}\right)\sum_{l=0}^{\infty}\left|o(1)^{2^{l}}\right|=O\left(\Delta^{3}\right)$

The first claim follows. The second claim can be proved in a similar way.

∎

######  Lemma D.9.

Suppose Assumption 2 holds. For
$\lambda=n(1+O(\varepsilon^{2})+O(\frac{n}{m}\varepsilon^{2}))$ and $\nu$ such
that $\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$,

$E\left[\exp(\varepsilon^{2}\theta\beta(2\phi(Z_{j}+c)-\beta))\right]=O(1)$

for integer $0\leq c\leq 3$

###### Proof.

$\exp(\varepsilon^{2}\theta\beta(2\phi(k)-\beta))=\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left|k-\frac{n}{m}\right|-\beta\right)\right\\}$

$=\exp\left\\{\varepsilon^{2}\theta\beta\left(\mathbbm{1}_{\\{k\leq\frac{n}{m}\\}}2\left(\frac{n}{m}-k\right)+\mathbbm{1}_{\\{k>\frac{n}{m}\\}}2\left(k-\frac{n}{m}\right)-\beta\right)\right\\}$
$=\mathbbm{1}_{\\{k\leq\frac{n}{m}\\}}\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-k\right)-\beta\right)\right\\}+\mathbbm{1}_{\\{k>\frac{n}{m}\\}}\exp\\{\left(2\theta\beta\left(2\left(k-\frac{n}{m}\right)-\beta\right)\right\\}$

Since $\exp(x)\geq 0$ for all $x$, this is at most

$\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-k\right)-\beta\right)\right\\}+\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(k-\frac{n}{m}\right)-\beta\right)\right\\}$

Thus,

$\operatorname*{\mathbb{E}}\left[\exp(\varepsilon^{2}\theta\beta(2\phi(Z_{j}+c)-\beta))\right]\leq\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-Z_{j}-c\right)-\beta\right)\right\\}\right]+\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(Z_{j}+c-\frac{n}{m}\right)-\beta\right)\right\\}\right]$

Now,

$E\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-Z_{j}-c\right)-\beta\right)\right\\}\right]=\exp\left\\{\varepsilon^{2}\theta\beta\left(\frac{2n}{m}-2c-\beta\right)\right\\}\operatorname*{\mathbb{E}}\left[\exp\left\\{-2\varepsilon^{2}\theta\beta
Z_{j}\right\\}\right]$ (60)

But, since $Z_{j}\sim Poi(\lambda\nu_{j})$, we have

$\operatorname*{\mathbb{E}}[\exp\\{-2\varepsilon^{2}\theta\beta
Z_{j}\\}]=\exp\left\\{\lambda\nu_{j}\left(e^{-2\varepsilon^{2}\theta\beta}-1\right)\right\\}$

Note that

$\lambda\nu_{j}=\frac{n}{m}+O(\frac{n\varepsilon}{m})$

So,

$\operatorname*{\mathbb{E}}[\exp\\{-2\varepsilon^{2}\theta\beta
Z_{j}\\}]=\exp\left\\{\frac{n}{m}(1+O(\varepsilon))\left(e^{-2\varepsilon^{2}\theta\beta}-1\right)\right\\}$

Using the fact that $e^{x}\leq 1+x$ for all $x$, the above is at most

$\exp\left\\{\frac{n}{m}(1+O(\varepsilon))(-2\varepsilon^{2}\theta\beta)\right\\}=\exp\left\\{-2\varepsilon^{2}\theta\beta\frac{n}{m}+O(\frac{n}{m}\varepsilon\theta\beta)\right\\}$

Since $n=o(m/\varepsilon^{2})$, and $\theta=\Theta(\varepsilon^{2})$,

$O\left(\frac{n}{m}\varepsilon\theta\beta\right)=o\left(\beta\varepsilon\right)$

Using (36), this is $o(1)$.

Thus,

$\operatorname*{\mathbb{E}}[\exp\\{-2\varepsilon^{2}\theta\beta
Z_{j}\\}]=\exp\left\\{-2\varepsilon^{2}\theta\beta\frac{n}{m}+o(1)\right\\}$

Thus, using this in (60), we have that

$\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-Z_{j}-c\right)-\beta\right)\right\\}\right]=\exp\left\\{-\varepsilon^{2}\theta\beta^{2}-2c\varepsilon^{2}\theta\beta+o(1)\right\\}$

Equation (36) tells us that

$\varepsilon^{2}\theta\beta^{2}=o(1)$

Similarly,

$\varepsilon^{2}\theta\beta=o(\varepsilon)$

So,

$\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(\frac{n}{m}-Z_{j}-c\right)-\beta\right)\right\\}\right]=\exp\left\\{o(1)\right\\}=O(1)$

Using a very similar argument, we can show that

$\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta\left(2\left(Z_{j}+c-\frac{n}{m}\right)-\beta\right)\right\\}\right]=O(1)$

.

So, by the above and (D.1),

$\operatorname*{\mathbb{E}}\left[\exp(\varepsilon^{2}\theta\beta(2\phi(Z_{j}+c)-\beta))\right]=O(1)$

∎

######  Lemma D.10.

Suppose Assumption 2 holds. For
$\lambda=n(1+O(\varepsilon^{2})+O(\frac{n}{m}\varepsilon^{2}))$ and $\nu$ such
that $\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$,

$\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}\exp\left\\{\varepsilon^{2}\theta\beta(2\phi(Z_{j}+c)-\beta)\right\\}\right]=O\left(\Delta^{\eta}\right)$