Are there distribution properties which are "maximally" hard to test?

Question

A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required to decide (w.h.p) if $D\in P$ or $d(D,P)>\epsilon$ ($d$ here is usually the $\ell_1$ distance). The most common measure of complexity is the number of samples used by the algorithm.

Now, in standard property testing, where you have query access to some object, a linear lower bound on query complexity is obviously the strongest lower bound possible, since $n$ queries would reveal the entire object. Is this the case for distribution testing as well?

As far as I understand, the "trivial" upper bound for testing properties of distributions is $O(n^2\log n)$ --- by Chernoff bounds, this is enough to "write down" a distribution D' which is close to D in $\ell_1$ distance, and then we can just check if there are any distributions close to D' which are in P (this might take infinite time, but this is irrelevant to sample complexity).

• Is there a better "trivial" test for all distribution properties?
• Are there any distribution properties for which we know sample lower bounds stronger than linear?

Answer 1

Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea.

First, it looks like you performed your Chernoff bound with some slightly odd setting of parameters. Note that to perform your suggested "testing by learning" approach, it is sufficient to learn the distribution in total variation distance (or $\ell_1$, if you prefer, which is the same up to a factor 2) to distance $\frac{\varepsilon}{2}$. (before checking "offline" if there is any distribution $p'$ having the property $\mathcal{P}_n$ which itself is at distance at most $\frac{\varepsilon}{2}$ from your learnt hypothesis $\hat{p}$). This would naively lead to an $O\big(\frac{n\log n}{\varepsilon^2}\big)$ sample complexity upper bound for this approach; however, it is known (and "folklore") that learning an arbitrary distribution over a domain of size $n$ up to distance $\varepsilon$ (in total variation distance) can be done with only $O(\frac{n}{\varepsilon^2})$ samples (and this is tight).

So the baseline should actually be $O(\frac{n}{\varepsilon^2})$, which is already linear in $n$. Now, one can ask the next question -- are there "natural" properties for which testing (say, for constant $\varepsilon$) requires a linear dependence in the domain size $n$?

The answer is (as far as I know) "not quite, but close." Namely, following a significant line of work on estimating properties of distributions (or equivalently, tolerant property testing), the results of Valiant and Valiant imply (STOCS'11, FOCS'11, and some others) that the rather contrived property "being $1/10$-close to uniform" has sample complexity $\Theta_\varepsilon(\frac{n}{\log n})$.

(Note that it's a bit "cheating," in the sense that the property is simply a way to take a tolerant testing question and relabel it as testing of an ad hoc property).

If that is not entirely sufficient to quench your thirst, one can also show that for the (natural?) property of "being a $k$-histogram" (is the distribution piecewise constant on a set of $k$ unknown intervals?), setting $k=n/10$ for instance also results in an $\Omega(\frac{n}{\log n})$ lower bound (it's in a paper of mine from 2016; the lower bound follows from a rather simple reduction to the Valiants' result). Now, whether you consider "being an $\frac{n}{100}$-histogram" to be a natural property is up to you.