Lower bound for testing closeness in $L_2$ norm?

Question

I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:

Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, test (whp) whether

• $D_1=D_2$
• or $\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon$

Batu et al. [BFR+00] showed that $O\left(\frac{1}{\epsilon^4}\right)$ samples were sufficient, but I haven't found any mention of a lower bound?

I reckon one could always show a $\Omega(\frac{1}{\epsilon^2})$ lower bound by reducing the task of distinguishing a fair vs. $\epsilon$-biased coin to this problem (simulating a distribution supported on only two points, and answering the queries of the tester according to the iid coin tosses), but that still leaves a quadratic gap...

(Another point I'd be interested in is a lower bound in estimating (up to an additive $\epsilon$) this $L_2$ distance — again, I have found no reference to such result in the literature)

Thanks for your help,

Answer 1

It appears that $O(1/\epsilon^2)$ samples — as usul showed below — is enough for testing, so that the sample complexity is exactly $\Theta(1/\epsilon^2)$; actually, it turns out this number of samples us even enough for learning $D$ up to an additive $\epsilon$ wrt the $L_2$ norm.

---

Let $\hat{D}$ be the empirical density function obtained by drawing $m$ i.i.d. samples $s_1,\dots, s_m\sim D$ and setting $$ \hat{D}(k) \stackrel{\rm{}def}{=} \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}},\qquad k\in[n] $$ Then $$ \begin{align*} \lVert D - \hat{D} \rVert_2^2 &= \sum_{k=1}^n \left( \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - D(k) \right)^2 = \frac{1}{m^2}\sum_{k=1}^n \left( \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - mD(k) \right)^2 \\ &= \frac{1}{m^2}\sum_{k=1}^n \left( X_k - \mathbb{E} X_k \right)^2 \end{align*} $$ where $X_k\stackrel{\rm{}def}{=} \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}}\sim\operatorname{Bin}( m, D(k) )$. The $X_k$'s (for $k\in[n]$) are not independent, but we can write $$ \begin{align*} \mathbb{E}\lVert D - \hat{D} \rVert_2^2 &= \frac{1}{m^2}\sum_{k=1}^n \mathbb{E}\left[ \left( X_k - \mathbb{E} X_k \right)^2 \right] = \frac{1}{m^2}\sum_{k=1}^n \operatorname{Var} X_k \\ &= \frac{1}{m^2}\sum_{k=1}^n mD(k)\left( 1- D(k) \right) \leq \frac{1}{m}\sum_{k=1}^n D(k) \\ &= \frac{1}{m} \end{align*} $$ so that for $m\geq \frac{3}{\epsilon^2}$, \begin{equation} \mathbb{E}\lVert D - \hat{D} \rVert_2^2 \leq \frac{\epsilon^2}{3} \end{equation} and applying Markov's inequality \begin{equation} \mathbb{P}\left\{ \lVert D - \hat{D} \rVert_2 \geq \epsilon \right\} \leq \frac{1}{3}. \end{equation}

Answer 2

I will attempt to atone for my previous error by showing something opposite -- that $\tilde{\Theta}\left(\frac{1}{\epsilon^2}\right)$ samples are sufficient (the lower bound of $1/\epsilon^2$ is almost tight)! See what you think....

The key intuition starts from two observations. First, in order for distributions to have an $L_2$ distance of $\epsilon$, there must be points with high probability ($\Omega(\epsilon^2)$). For example, if we had $1/\epsilon^3$ points of probability $\epsilon^3$, we'd have $\|D_1 - D_2\|_2 \leq \sqrt{\frac{1}{\epsilon^3} (\epsilon^3)^2} = \epsilon^{3/2} < \epsilon$.

Second, consider uniform distributions with an $L_2$ distance of $\epsilon$. If we had $O(1)$ points of probability $O(1)$, then they would each differ by $O(\epsilon)$ and $1/\epsilon^2$ samples would suffice. On the other hand, if we had $O(1/\epsilon^2)$ points, they would each need to differ by $O(\epsilon^2)$ and again $O(1/\epsilon^2)$ samples (a constant number per point) suffices. So we might hope that, among the high-probability points mentioned earlier, there is always some point differing "enough" that $O(1/\epsilon^2)$ draws distinguishes it.

Algorithm. Given $\epsilon$ and a confidence parameter $M$, let $X = M \log(1/\epsilon^2)$. Draw $\frac{X}{\epsilon^2}$ samples from each distribution. Let $a_i,b_i$ be the respective higher,lower number of samples for point $i$. If there is any point $i \in [n]$ for which $a_i \geq \frac{X}{8}$ and $a_i-b_i \geq \sqrt{a_i} \frac{\sqrt{X}}{4}$, declare the distributions different. Otherwise, declare them the same.

The correctness and confidence bounds ($1-e^{-\Omega(M)}$) depend on the following lemma which says that all of the deviation in $L_2$ distance comes from points whose probabilities differ by $\Omega(\epsilon^2)$.

Claim. Suppose $\|D_1 - D_2\|_2 \geq \epsilon$. Let $\delta_i = |D_1(i) - D_2(i)|$. Let $S_k = \{i : \delta_i > \frac{\epsilon^2}{k}\}$. Then $$\sum_{i \in S_k} \delta_i^2 \geq \epsilon^2\left(1-\frac{2}{k}\right).$$

Proof. We have $$ \sum_{i \in S_k} \delta_i^2 ~ + ~ \sum_{i \not\in S_k} \delta_i^2 \geq \epsilon^2. $$ Let us bound the second sum; we wish to maximize $\sum_{i \not\in S_k} \delta_i^2$ subject to $\sum_{i \not\in S_k} \delta_i \leq 2$. Since the function $x \mapsto x^2$ is strictly convex and increasing, we can increase the objective by taking any $\delta_i \geq \delta_j$ and increasing $\delta_i$ by $\gamma$ while decreasing $\delta_j$ by $\gamma$. Thus, the objective will be maximized with as many terms as possible at their maximum values, and the rest at $0$. The maximum value of each term is $\frac{\epsilon^2}{k}$, and there are at most $\frac{2k}{\epsilon^2}$ terms of this value (since they sum to at most $2$). So $$ \sum_{i \not\in S_k} \delta_i^2 \leq \frac{2k}{\epsilon^2}\left(\frac{\epsilon^2}{k}\right)^2 = \frac{2\epsilon^2}{k} . ~~~~ \square $$

Claim. Let $p_i = \max\{D_1(i),D_2(i)\}$. If $\|D_1 - D_2\|_2 \geq \epsilon$, there exists at least one point $i \in [n]$ with $p_i > \frac{\epsilon^2}{4}$ and $\delta_i \geq \frac{\epsilon \sqrt{p_i}}{2}$.

Proof. First, all points in $S_k$ have $p_i \geq \delta_i > \frac{\epsilon^2}{k}$ by definition (and $S_k$ cannot be empty for $k > 2$ by the previous claim).

Second, because $\sum_i p_i \leq 2$, we have $$ \sum_{i \in S_k} \delta_i^2 \geq \epsilon^2 \left(\frac{1}{2} - \frac{1}{k}\right) \sum_{i \in S_k} p_i, $$ or, rearranging, $$ \sum_{i \in S_k} \left( \delta_i^2 - p_i \epsilon^2 \left(\frac{1}{2} - \frac{1}{k}\right)\right) \geq 0 , $$ so the inequality $$ \delta_i^2 \geq p_i \epsilon^2 \left(\frac{1}{2} - \frac{1}{k}\right) $$ holds for at least one point in $S_k$. Now pick $k=4$. $\square$

Claim (false positives). If $D_1 = D_2$, our algorithm declares them different with probability at most $e^{-\Omega(M)}$.

Sketch. Consider two cases: $p_i < \epsilon^2/16$ and $p_i \geq \epsilon^2/16$. In the first case, the number of samples of $i$ will not exceed $X/8$ from either distribution: The mean number of samples is $< X/16$ and a tail bound says that with probability $e^{-\Omega(X/p_i)} = \epsilon^2 e^{-\Omega(M/p_i)}$, $i$'s samples do not exceed their mean by an additive $X/16$; if we are careful to keep the value $p_i$ in the tail bound, we can union bound over them no matter how many such points there are (intuitively, the bound decreases exponentially in the number of possible points).

In the case $p_i \geq \epsilon^2/16$, we can use a Chernoff bound: It says that, when we take $m$ samples and a point is drawn with probability $p$, the probability of differing from its mean $pm$ by $c \sqrt{pm}$ is at most $e^{-\Omega((c\sqrt{pm})^2/pm)} = e^{-\Omega(c^2)}$. Here, let $c = \frac{\sqrt{X}}{16}$, so the probability is bounded by $e^{-\Omega(X)} = \epsilon^2 e^{-\Omega(M)}$.

So with probability $1-\epsilon^2e^{-\Omega(M)}$, (for both distributions) the number of samples of $i$ is within $\sqrt{p_i\frac{X}{\epsilon^2}}\frac{\sqrt{X}}{16}$ of its mean $p_i\frac{X}{\epsilon^2}$. Thus, our test will not catch these points (they are very close to each other), and we can union bound over all $16/\epsilon^2$ of them. $\square$

Claim (false negatives). If $\|D_1 - D_2\|_2 \geq \epsilon$, our algorithm declares them identical with probability at most $\epsilon^2 e^{-\Omega(M)}$.

Sketch. There is some point $i$ with $p_i > \epsilon^2/4$ and $\delta_i \geq \epsilon \sqrt{p_i}/2$. The same Chernoff bound as in the previous claim says that with probability $1-\epsilon^2 e^{-\Omega(M)}$, the number of samples of $i$ differs from its mean $p_i m$ by at most $\sqrt{p_i m} \frac{\sqrt{X}}{16}$. That is for (WLOG) distribution $1$ which has $p_i = D_1(i) = D_2(i) + \delta_i$; but there is an even lower probability of the number of samples of $i$ from distribution $2$ differing from its mean by this additive amount (as the mean and variance are lower).

So with high probability the number of samples of $i$ from each distribution is within $\sqrt{\frac{p_i X}{\epsilon^2}} \frac{\sqrt{X}}{16}$ of its mean; but their probabilities differ by $\delta_i$, so their means differ by $$ \frac{X}{\epsilon^2}\delta_i \geq \frac{X \sqrt{p_i}}{2\epsilon} = \sqrt{\frac{p_i X}{\epsilon^2}} \frac{\sqrt{X}}{2} . $$

So with high probability, for point $i$, the number of samples differs by at least $\sqrt{\# samples(1)} \frac{\sqrt{X}}{4}$. $\square$

To complete the sketches, we would need to more rigorously show that, for $M$ big enough, the number of samples of $i$ is close enough to its mean that, when the algorithm uses $\sqrt{\# samples}$ rather than $\sqrt{mean}$, it doesn't change anything (which should be straightforward by leaving some wiggle room in the constants).

Answer 3

You might start by trying to resolve this for the case $n=2$. I'm pretty sure $\Theta(1/\epsilon^2)$ samples will be necessary and sufficient, in that case.

It's possible you might find it helpful to look at converting between the $L_2$ distance and the $L_1$ distance (total variation distance).

• It's known that, with one sample, if the distributions are known, the total variation distance perfectly characterizes the advantage with which one can distinguish $D_1$ from $D_2$. Thus, if the total variation distance is large and the distributions are known, one can build a test that is correct with high probability; if the total variation distance is small, one cannot. I don't know what one can say about the case where the total variation distance is large but the distributions are unknown.

• Next you might look at the product distributions, $D_1^n$ and $D_2^n$. Using the total variation distance ($L_1$ distance), there don't seem to be any good bounds that relate $||D_1^n - D_2^n||_1$ to $||D_1 - D_2||_1$. However, when using the $L_2$ distance, I believe there are good estimates of $||D_1^n - D_2^n||_2$ as a function of $||D_1 - D_2||_2$. (Unfortunately, I can't seem to dig up a specific reference to those estimates/bounds, so I hope I'm not misremembering.) There are also known bounds that allow you to estimate the $L_1$ distance as a function of the $L_2$ distance.

• Therefore, one approach you might try would be to bound $||D_1^n - D_2^n||_2$, then from that getting a bound on $||D_1^n - D_2^n||_1$.

I don't know whether this will lead anywhere good or not; it's just an idea. Probably the authors of the paper you cite will already have tried or considered something like this.

Possibly helpful references:

• The product distribution: how fast does dissimilarity increase as a function of number of samples?

• Hypothesis testing and total variation distance vs. Kullback-Leibler divergence

• What is the relationship of 1 (total variation) distance to hypothesis testing?

• On error probability bounds in Bayesian hypothesis testing

• Implications of lower-bounded total variation distance on hypothesis testing

• Pinsker's Inequality for Bayesian hypothesis testing

• How does one express the decrease in minimal type II error bound for each observation added?

Answer 4

EDIT: this is incorrect! See the discussion in the comments -- I will point out the flaw below.

I think we can say that $\frac{1}{\epsilon^4}$ are required.

Set $n = \Theta\left(\frac{1}{\epsilon^2}\right)$. Let $D_1$ be the uniform distribution (probability of each point $= \Theta(\epsilon^2)$) and let $D_2$ differ from uniform by an additive amount $\pm \Theta\left(\epsilon^2\right)$ at each point. Check that the $L_2$ distance is $\epsilon$.

So we have to distinguish an $n$-sided fair coin from an $n$-sided $\Theta(\epsilon^2)$-biased coin. I think this should be at least as hard as telling a $2$-sided fair coin from a $2$-sided $\Theta(\epsilon^2)$-biased coin, which would require $\Theta\left(\frac{1}{(\epsilon^2)^2}\right) = \Theta\left(\frac{1}{\epsilon^4}\right)$ samples. Edit: this is incorrect! The coin is additively $\epsilon^2$-biased, but it is biased multiplicatively by a constant factor. As D.W. points out, that means that a constant number of samples per point distinguishes $D_1$ from $D_2$.

---

Notice that $\frac{1}{\epsilon^4}$ is as far as we can push this line of argument. Concretely, suppose we tried to increase $n$ to, say, $\frac{1}{\epsilon^3}$. In the uniform distribution, each point has probability $\epsilon^3$. But in $D_2$, we'd need each point to vary from uniform by $\epsilon^{2.5}$. That isn't possible since $\epsilon^{2.5} \gg \epsilon^3$.

More abstractly, suppose we want each point to vary from uniform by $\epsilon^k$. Then the most we can set $n$ to would be $\frac{1}{\epsilon^k}$. To get an $L_2$ distance of $\epsilon$, we need to satisfy that the square root of the sum of the distances is $\epsilon$, so $\sqrt{n(\epsilon^k)^2} = \epsilon$, so $\epsilon^{k/2} = \epsilon$ so $k = 2$, and we get $n = \frac{1}{\epsilon^2}$.

Also, I think the same argument says that, if we're interested in $L_p$ distance with $p > 1$, we require $k = \frac{p}{p-1}$, so we'd pick $n = 1/\epsilon^{\frac{p}{p-1}}$, so the number of samples would be $1 / \epsilon^{2\frac{p}{p-1}}$. I think this makes sense as a bound that is independent of $n$. It approaches infinity as $p \to 1$. If you were trying to distinguish two distributions at $L_1$ distance of $\epsilon$ with no bound on $n$, I would make $n$ unboundedly large and spread out the difference arbitrarily thin, so you could never distinguish them (i.e. no fixed number of samples suffices for all $n$). It also approaches $\frac{1}{\epsilon^3}$ as $p \to \infty$; this makes sense as a bound because, for the $L_{\infty}$ norm, we can set $n = \frac{1}{\epsilon}$ and let every point differ by $\Theta(\epsilon)$; we need to sample some point $\frac{1}{\epsilon^2}$ times to be sure it differs from uniform, which will take $\frac{1}{\epsilon^3}$ samples.