<p>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 $&lt;\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. </p>

<p>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. </p>

<p>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. </p>

CC BY-SA 4.0
2020-05-14T21:39:47.750Z
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:

https://cstheory.stackexchange.com/questions/40161/proper-pac-learning-vc-dimension-bounds
Aryeh
CC BY-SA 4.0
2020-05-14T21:40:36.663Z
There are scenarios where improper algorithms necessarily achieve better sample complexity than proper ones.
Aryeh
CC BY-SA 3.0
2014-04-21T00:48:32.487Z
2014-04-21T00:48:32.487Z
Aaron Roth
<p>How is the <a href="http://en.wikipedia.org/wiki/Property_testing">Property testing </a> is related to <a href="http://en.wikipedia.org/wiki/Probably_approximately_correct_learning">PAC</a> model of learning?</p>

<p>More precisely, </p>

<p>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&lt;\epsilon&lt;1$,  confidence interval $0&lt;\delta&lt;1/2$, and does the following:</p>

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

<p>-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$.</p>

<p>Now, I have following two questions:</p>

<p>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.</p>

<p>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?</p>

<p>Pls let me know if I am not able to put the question clearly.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2014-04-20T18:30:27.703Z
The paper of Goldreich, Goldwasser, and Ron should help a lot: http://groups.csail.mit.edu/cis/pubs/shafi/1998-jacm.pdf.
Sasho Nikolov
CC BY-SA 3.0
2014-04-21T12:19:28.427Z
You can have a look at [these lecture notes](http://www.cs.columbia.edu/~rocco/Teaching/S14/Scribe/lecture7.pdf) — they are quite short, and should answer your question.
Clement C.
<machine-learning><property-testing>
Is testing easier/harder than learning?
Ram
# Is testing easier/harder than learning?

(Asked by: username_0 on 2014-04-20)

How is the [Property testing](http://en.wikipedia.org/wiki/Property_testing)  is related to [PAC](http://en.wikipedia.org/wiki/Probably_approximately_correct_learning) 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.

Thanks.

**Tags:** machine-learning, property-testing

> **Comments:**
> **username_1**: The paper of Goldreich, Goldwasser, and Ron should help a lot: http://groups.csail.mit.edu/cis/pubs/shafi/1998-jacm.pdf.  
> **username_2**: You can have a look at [these lecture notes](http://www.cs.columbia.edu/~rocco/Teaching/S14/Scribe/lecture7.pdf) — they are quite short, and should answer your question.  

---

## 1 answers

### Answer by username_3 on 2014-04-21. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_4**: 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:  https://cstheory.stackexchange.com/questions/40161/proper-pac-learning-vc-dimension-bounds  
> **username_4**: There are scenarios where improper algorithms necessarily achieve better sample complexity than proper ones.  

---

