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.



1 Answer 1


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.

  • $\begingroup$ I don't entirely agree with "without loss of generality you can always use a proper PAC learning algorithm" -- see Steve Hanneke's answer here: cstheory.stackexchange.com/questions/40161/… $\endgroup$
    – Aryeh
    May 14, 2020 at 21:39
  • $\begingroup$ There are scenarios where improper algorithms necessarily achieve better sample complexity than proper ones. $\endgroup$
    – Aryeh
    May 14, 2020 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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