11
If the learning algorithm is proper (i.e. it always produces a hypothesis from the class $F_n$), then it also gives a testing algorithm -- simply run the learning algorithm, and see whether the hypothesis it produced has error rate $<\epsilon$, which can be done with only $\approx 1/\epsilon^2$ samples. If it does, since the hypothesis is in $F_n$, this ...
10
The lines oracle is used to decrease the query complexity of the test from $d+1$ to $2$, at the expense of using a larger alphabet.
If you don't mind making $d+1$ queries, then the lines oracle is indeed unnecessary. However, it is usually better to make two queries over a large alphabet than $d+1$ queries over a small alphabet.
One reason is that, very ...
8
Yes. Such families are called "averaging samplers", and there are plenty of constructions for them. You can find a more information about them (and about the more general notion of sampler) in this survey.
The notion of averaging samplers was introduced in this paper, which also showed that they are equivalent to randomness extractors. There are many ...
7
You might find this short note helpful ($\LaTeX$ code available [1]
if the binary link breaks). I am reproducing the relevant part below:
Theorem. (Folklore) Learning an unknown distribution over a known domain of size $n$, up to total variation $\varepsilon\in(0,1]$, and with error probability $\delta\in(0,1]$, has sample complexity $O\!\left(\frac{n+\...
6
No, you can't beat $\Theta(\sqrt{n})$ queries. I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms. This is all anticipated in exfret's answer; I am just filling in some of the details.
Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $...
5
Let’s assume we can only query the $i$th edge of a given vertex’s adjacency list (which I am assuming is not sorted) or whether two given vertices are adjacent. In this case it should take $\sqrt n$ queries to even find a cycle. This is because there is a $1-o(1)$ chance that all our queries of the first type return different vertices and that all of our ...
5
Here are the lower bounds I can show. I conjecture that for a fixed $\epsilon$, the right lower bound is $\Omega( \log n)$, but naturally I might be wrong.
I am going to use a decreasing sequence (just for convenience). The basic mechanism is breaking the sequence into $L$ blocks. In the $i$th block there are going to be $n_i$ elements (i.e., $\sum_i n_i = ...
5
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 $\...
4
The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations where the magnitude of the noise is what matters (rather than the more brittle Hamming distance). (Some results pertaining to $L_p$ distances can also be found ...
4
Lower bound
At least $\Omega(1/\sqrt{\epsilon})$ queries are necessary to distinguish the two cases.
Consider the sequence $a_1,\dots,a_n$ given by $\epsilon,2\epsilon,3\epsilon,4\epsilon,\dots$, with $n$ chosen so that $a_1+\dots+a_n = 1$. In particular, we can take $n \approx 1/\sqrt{2\epsilon}$.
Now construct a new sequence $a'_1,\dots,a'_n$ by ...
4
What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, i.e. any Boolean vector is at most $\frac{N}{2}-\frac{\sqrt{N}}{2}$ Hamming distance away from some code word of the punctured Hadamard code. The $O(\sqrt{N})$ ...
4
First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - ...
3
Here's a counter-example showing your desired bound is not possible, unless I am mistaken. It's a simple variant of the example in Roei's comment.
Fix any $n$ and $N\ge 4n$. Take $D$ to contain $N/2$ points that are all the same (or all within distance 1 from each other), and $N/2$ points that are all widely separated (at distance at least 1 from every ...
3
There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument.
Suppose there is a hitting set $H=\{\alpha_{1},\dots,\alpha_{k}\}$
of size $k$. We will show that there is always {-1,0,1}-linear
form $f$ such that $f(\alpha_{i})=0$ for all $i$ when $k\le c_{0}n/\log n$
and $c_{0}$ is small enough.
For each $S\subseteq[n]$, let $f_{S}=\...
3
Take the class $\mathcal{M}$ of monotone boolean functions under the uniform distribution on $\{0,1\}^n$:
it is known that $O(\sqrt{n}/\varepsilon^2)$ queries are sufficient to test it (even with non-adaptive testers) [KhotMinzerSafra15].
learning $\mathcal{M}$ under the uniform distribution, even allowing membership queries, requires $2^{\Omega(\sqrt{n}/\...
2
Chapter 10.5.1 of Oded Goldreich's Introduction to Property Testing (2017) discusses exactly that question. (See his website for an overview of the book, and (free) access to the drafts.)
Now, Theorem 10.15 states there are properties, for instance cycle-freeness, subgraph-freeness, and degree regularity, which have $O_\varepsilon(1)$-query testers in the ...
2
Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins. Let $D$ be a decider that is not one-sided. For $x \in \mathcal{Y}$, let $\mathcal{W}_x = \{r \in \{0,1\}^m : D(x,r)=\textsf{no}\}$ be the set of random strings $r$ such that $D$ outputs the wrong answer. Consider a distribution $R$ that, ...
2
Let's denote $N:=|\Omega|$. Then $\Theta(|N|/\epsilon^2)$ examples are both necessary and sufficient to learn the distribution to additive precision $\epsilon$ in total variation. This follows from classic VC analysis, since
for two distributions $p,q$ on $\Omega$, we have
$$ \sum_{x\in\Omega}|p_x-q_x| = 2\max_{A\subseteq\Omega}|p(A)-q(A)|.$$
Now the concept ...
1
Please define testing precisely (under what distribution? known/unknown?). In the meantime, here is an example of what you may be looking for. Consider the example in the Kearns-Vazirani book, of learning 3-term DNFs. This class of functions is hard to learn properly. But if "testing" involves evaluating a fixed given 3-term DNF on some randomly drawn points ...
Only top voted, non community-wiki answers of a minimum length are eligible