Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How is the Property testing is related to PAC model of learning?

More precisely,

Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$ which receives as input a size parameter $n$ (labeled input $(x_1,f(x_1)), (x_2,f(x_2)),...,(x_n,f(x_n))$), distance parameter $0<\epsilon<1$, confidence interval $0<\delta<1/2$, and does the following:

-if $f\in \mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ accepts $f$.

-if $f$ is $\epsilon$-far from $\mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ rejects $f$.

Now, I have following two questions:

1) Now, how this tester $\mathcal{A}$ can be used to generate learning algorithm (under PAC learning model) for the concept class $\mathcal{F_n}$, and vice versa. And how does VC-dim of $\mathcal{F_n}$ plays role in the reduction.

2) Can we give some sort of characterization (for example, on the basis of VC-dim) over the concept class for which testing is easier/harder than learning?

Pls let me know if I am not able to put the question clearly.


share|cite|improve this question
The paper of Goldreich, Goldwasser, and Ron should help a lot: – Sasho Nikolov Apr 20 '14 at 18:30
You can have a look at these lecture notes — they are quite short, and should answer your question. – Clement C. Apr 21 '14 at 12:19
up vote 11 down vote accepted

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 is a constructive proof that the function you are testing has distance at most $\epsilon$ from $F_n$. If the algorithm was a PAC learning algorithm for $F_n$, then when $f \in F_n$, it must generate such a hypothesis. So any proper learning algorithm can be converted to a testing algorithm with only an additional $\approx 1/\epsilon^2$ samples at most.

Moreover, if you are only worried about sample complexity and not computational efficiency, then without loss of generality you can always use a proper PAC learning algorithm. Since the sample complexity of learning is $\mathrm{VCDIM}(F_n)/\epsilon^2$, this means you can always test with at most this many samples.

However, generally testing is easier than learning. For example, linear functions in $d$ dimensions require $d$ samples to learn, but only a constant number of samples to test.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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