<p>Take the class  <span class="math-container">$\mathcal{M}$</span> of monotone boolean functions under the uniform distribution on <span class="math-container">$\{0,1\}^n$</span>: </p>

<ul>
<li><p>it is known that <span class="math-container">$O(\sqrt{n}/\varepsilon^2)$</span> queries are sufficient to test it (even with non-adaptive testers) [KhotMinzerSafra15].</p></li>
<li><p>learning <span class="math-container">$\mathcal{M}$</span> under the uniform distribution, even allowing membership queries, requires <span class="math-container">$2^{\Omega(\sqrt{n}/\varepsilon)}$</span> queries ([BshoutyTamon96,BlaisCOST15]). </p></li>
</ul>

CC BY-SA 4.0
2018-12-13T17:23:49.207Z
Note: I guess this is not exactly addressing the question, since the class is not *learnable* at all (instead of merely "(presumably) hard to properly learn").
Clement C.
CC BY-SA 4.0
2018-12-13T16:31:14.037Z
2018-12-13T16:31:14.037Z
Clement C.
<p>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 -- then sure, that's efficiently doable.</p>

CC BY-SA 4.0
2018-12-12T01:02:29.120Z
Yeah, I see. I edited the problem to require the testing and learning under the same distribution (for simplicity one may assume the distribution is known and efficient sampleable).
Paul
CC BY-SA 4.0
2018-12-13T17:25:21.937Z
*"But if "testing" involves evaluating a fixed given 3-term DNF on some randomly drawn points" * $\leadsto$ what do you mean? Testing involves, given blackbox access to $f$, deciding whether $f$ is a (function represented by a) 3-term DNF, or $\varepsilon$-far (under the ambient distribution) from every such 3-term DNF.
Clement C.
CC BY-SA 4.0
2018-12-11T22:48:55.813Z
2018-12-11T22:48:55.813Z
Aryeh
<p>Let <span class="math-container">$H$</span> be a binary hypothesis class, it is easy to see that if <span class="math-container">$H$</span> is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or <span class="math-container">$\epsilon$</span>-far testable).</p>

<p>My question is:</p>

<blockquote>
  <p>Fixed a distribution, is there any known hypothesis class that is hard (say NP-hard) to properly learn (to avoid the problem to be trivial, we assume the class is statistically  PAC-learnable) under this specific distribution, but easy (say within polynomial time) to test under the same distribution?</p>
</blockquote>

<p>As far as I know most of the results for proving hardness of learning are reduced to the hardness of testing (i.e. decide a gap version of the risk minimization is hard).</p>

CC BY-SA 4.0
2018-12-11T22:46:02.797Z
I'll just note that there exist trivial unsatisfying answers (unless I'm misunderstanding the definition). E.g., take H to be the class of all functions. This is trivially testable, since everything is in it! But, it's certainly not learnable.
Noah Stephens-Davidowitz
CC BY-SA 4.0
2018-12-11T23:07:18.013Z
@NoahStephens-Davidowitz Yeah, I edited the problem, we now assume H to be statistically PAC-learnable.
Paul
CC BY-SA 4.0
2018-12-12T06:37:59.507Z
Is this “fixed distribution” easy to sample from?
Aryeh
CC BY-SA 4.0
2018-12-13T16:28:21.943Z
@Aryeh I am ssuming it is distribution-free testing-like setting: i.e., you get sample access to the distribution and query access to the function.
Clement C.
CC BY-SA 4.0
2018-12-13T16:32:28.220Z
@OP I am a bit confused by your comparison. Typically, testing involves membership queries, while PAC-learning only randomly drawn labelled samples. That hardly seems... "fair."
Clement C.
CC BY-SA 4.0
2018-12-13T16:42:04.303Z
So then wouldn't my example below with the 3-term DNF satisfy the OP's criteria?
Aryeh
CC BY-SA 4.0
2018-12-13T17:48:53.720Z
Do you want hardness of _improper_ or _proper_ PAC learning? I think it's challenging to show hardness of improper PAC learning, while proper is often easy.
Thomas Steinke
CC BY-SA 4.0
2018-12-13T18:09:13.327Z
@Thomas Not necessarily (see my answer). There are results about hardness of learning (information-theoretic), even under the uniform distribution.
Clement C.
CC BY-SA 4.0
2018-12-13T18:56:01.957Z
@ClementC. But that’s statistical hardness, not computational hardness, no? The question is for classes that are statistically easy but computationally hard.
Thomas Steinke
CC BY-SA 4.0
2018-12-13T19:02:38.513Z
Indeed (cf. comment below my answer).
Clement C.
CC BY-SA 4.0
2018-12-13T20:00:40.437Z
@ClementC. So my comment is pointing out that showing _computational_ hardness of _improper_ PAC learning is hard. Computational hardness of proper PAC learning should be easier.
Thomas Steinke
CC BY-SA 4.0
2018-12-13T20:02:53.227Z
I agree (sorry, I misinterpreted your earlier comment). @Thomas
Clement C.
<machine-learning><property-testing><pac-learning>
Are there hypothesis classes that are hard to learn but easy to test?
Paul
# Are there hypothesis classes that are hard to learn but easy to test?

(Asked by: username_0 on 2018-12-11)

Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\epsilon$-far testable).

My question is:

> Fixed a distribution, is there any known hypothesis class that is hard (say NP-hard) to properly learn (to avoid the problem to be trivial, we assume the class is statistically PAC-learnable) under this specific distribution, but easy (say within polynomial time) to test under the same distribution?

As far as I know most of the results for proving hardness of learning are reduced to the hardness of testing (i.e. decide a gap version of the risk minimization is hard).

**Tags:** machine-learning, property-testing, pac-learning
> **Comments:**
> **username_1**: I'll just note that there exist trivial unsatisfying answers (unless I'm misunderstanding the definition). E.g., take H to be the class of all functions. This is trivially testable, since everything is in it! But, it's certainly not learnable.  
> **username_0**: @NoahStephens-Davidowitz Yeah, I edited the problem, we now assume H to be statistically PAC-learnable.  
> **username_2**: Is this “fixed distribution” easy to sample from?  
> **username_3**: @Aryeh I am ssuming it is distribution-free testing-like setting: i.e., you get sample access to the distribution and query access to the function.  
> **username_3**: @OP I am a bit confused by your comparison. Typically, testing involves membership queries, while PAC-learning only randomly drawn labelled samples. That hardly seems... "fair."  
> **username_2**: So then wouldn't my example below with the 3-term DNF satisfy the OP's criteria?  
> **username_4**: Do you want hardness of _improper_ or _proper_ PAC learning? I think it's challenging to show hardness of improper PAC learning, while proper is often easy.  
> **username_3**: @Thomas Not necessarily (see my answer). There are results about hardness of learning (information-theoretic), even under the uniform distribution.  
> **username_4**: @ClementC. But that’s statistical hardness, not computational hardness, no? The question is for classes that are statistically easy but computationally hard.  
> **username_3**: Indeed (cf. comment below my answer).  
> **username_4**: @ClementC. So my comment is pointing out that showing _computational_ hardness of _improper_ PAC learning is hard. Computational hardness of proper PAC learning should be easier.  
> **username_3**: I agree (sorry, I misinterpreted your earlier comment). @Thomas  

---

## 2 answers

### Answer by username_3 on 2018-12-13. Score: 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}/\varepsilon)}$ queries ([BshoutyTamon96,BlaisCOST15]).

> **Comments:**
> **username_3**: Note: I guess this is not exactly addressing the question, since the class is not *learnable* at all (instead of merely "(presumably) hard to properly learn").  

---

### Answer by username_2 on 2018-12-11. Score: 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 -- then sure, that's efficiently doable.

> **Comments:**
> **username_0**: Yeah, I see. I edited the problem to require the testing and learning under the same distribution (for simplicity one may assume the distribution is known and efficient sampleable).  
> **username_3**: *"But if "testing" involves evaluating a fixed given 3-term DNF on some randomly drawn points" * $\leadsto$ what do you mean? Testing involves, given blackbox access to $f$, deciding whether $f$ is a (function represented by a) 3-term DNF, or $\varepsilon$-far (under the ambient distribution) from every such 3-term DNF.  

---

