11
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ This promise problem seems very similar to the one called statistical difference by Sahai and Vadhan, which is a complete problem for the class SZK (statistical zero knowledge); however, they use $L_1$ distance. cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf. (Edit: also I think they are assuming you have a circuit computing the distributions, not oracle access.) $\endgroup$ – usul Jul 16 '13 at 22:37
  • $\begingroup$ Hi, as mentioned in another comment, the difference between $L_2$ and $L_1$ norm is actually crucial here — further, in ther paper, they set up an explicit (and not arbitrary) threshold $\tau=1/3$ (in one of the remarks, they explain that this threshold needs to satisfy some particular constraint); and want to distinguish $d_1 \leq \tau$ vs. $d_2 \geq 1-\tau$ (which is somehow closer to tolerant testing/distance estimation than "usual testing", where you want to test $d_2=0$ vs. $d_2 \geq \epsilon$ (but for any fixed $\epsilon$)). $\endgroup$ – Clement C. Jul 18 '13 at 11:24
6
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ (I was referring to usul's answer starting with "I will attempt to atone for my previous error by showing something opposite[...]" — which is actually above this one. I didn't expect this :) ) As for the learning upper bound, it can be shown that the most naive algorithm (that is, the one that draws $m=O(1/\epsilon^2)$ samples, and outputs the empirical density this defines) yields a distribution $\hat{D}$ which is, with constant probability, $\epsilon$-close to $D$ in $L_2$ distance. $\endgroup$ – Clement C. Jul 29 '13 at 20:48
  • $\begingroup$ @D.W. I just edited my answer. $\endgroup$ – Clement C. Jul 29 '13 at 21:24
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Hi, Thanks for this — I have a few questions about the algorithm and the analysis (regarding a couple points I'm not sure to get): assuming I only want at the end a constant probability $2/3$ of success, that means that $M$ constant, if I understand correctly (unless I didn't get what $M$ was)? So in this case, turning to $X$: according to the algorithm, it becomes $\Theta(\log\frac{1}{\epsilon})$ — is that correct? $\endgroup$ – Clement C. Jul 25 '13 at 14:54
  • $\begingroup$ @ClementC. Sorry I was not very clear! The claim is that if we draw $\frac{1}{\epsilon^2} M \log(1/\epsilon^2)$ samples, then the probability of being wrong is $O(e^{-M})$, so for a constant probability of being wrong, its $O\left(\frac{1}{\epsilon^2} \log(1/\epsilon^2)\right)$ samples. $\endgroup$ – usul Jul 25 '13 at 19:58
  • $\begingroup$ OK, that's what I gathered. I'll go through the proof with this in mind — thanks again for the time you spent on this! $\endgroup$ – Clement C. Jul 25 '13 at 20:43
1
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ Hi, Thanks for your answer! However, I am interested in an asymptotic lower bound, when $n\to\infty$. In particular, the relation between $L_2$ and $L_1$ norms involves a $\sqrt{n}$ factor — meaning they are indeed equivalent for $n$ constant, but asymptotically very different; using the $L_1$ dstance as proxy is not an option, as far as I can tell (as for testing closeness in $L_1$ distance, the exact complexity is known to be $\Theta(n^{2/3}/{\rm{}poly}(\epsilon))$ [BFR+10,Val11] $\endgroup$ – Clement C. Jul 17 '13 at 12:37
0
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1. Do you really mean that $D_2$ differs from uniform by $\pm 1/\epsilon^2$ at each point? I suspect that's a typo and you meant $\pm \epsilon^2$. $\endgroup$ – D.W. Jul 20 '13 at 3:29
  • 1
    $\begingroup$ 2. I don't buy that distinguishing $D_1$ from $D_2$ requires $1/\epsilon^4$ samples. Looks to me like $\Theta(1/\epsilon^2)$ samples are enough. Explanation (intuition): suppose we gather $m=100/\epsilon^2$ samples and count how many times each possible value occurs. If they came from $D_1$, each should occur 100 times (with std dev 10). If they came from $D_2$, each should occur 200 times (std dev 14) for half of them, / 0 times (std dev 0) for the other half. That's easily enough to distinguish between the two, if you know you're dealing with either $D_1$ or $D_2$. $\endgroup$ – D.W. Jul 20 '13 at 3:30
  • $\begingroup$ @D.W. (1) you're right! Fixed. (2) As you put it, I agree, but I think with different choices of constants it is harder. I am picturing something like this: $n = 1/100\epsilon^2$, so $D_1$ puts probability $100\epsilon^2$ on each point. Then $D_2$ differs by $10\epsilon^2$ on each point (check that $L_2$ distance is $\epsilon$), so it puts probability $90\epsilon^2$ or $110\epsilon^2$ on each point. $\endgroup$ – usul Jul 20 '13 at 4:10
  • 1
    $\begingroup$ I think $O(1/\epsilon^2)$ samples still suffice. Gather $m=10^6n$ samples, and count how many times each possible value occurs. For $D_1$, each should occur 1,000,000 times (std dev $1000$). For $D_2$, each should occur 900,000 times (std dev $\approx 1000$) or 1,100,000 times (std dev $\approx 1000$). That's easily enough to distinguish between the two, if we know we're dealing with either $D_1$ or $D_2$, because the difference between 1,000,000 and 1,100,000 is 100 standard deviations, i.e., huge. $\endgroup$ – D.W. Jul 20 '13 at 4:30
  • $\begingroup$ @D.W. I thought about it more -- you're right. If their means differ by a constant multiplicative factor then a constant number of samples per point should distinguish them. It's the multiplicative not additive factor that matters. This approach then only gives a lower bound of $1/\epsilon^2$. $\endgroup$ – usul Jul 20 '13 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.