# Are there hypothesis classes that are hard to learn but easy to test?

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).

• 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 Dec 11 '18 at 22:46
• @NoahStephens-Davidowitz Yeah, I edited the problem, we now assume H to be statistically PAC-learnable. – Paul Dec 11 '18 at 23:07
• Is this “fixed distribution” easy to sample from? – Aryeh Dec 12 '18 at 6:37
• @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. Dec 13 '18 at 16:28
• @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. Dec 13 '18 at 16:32

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]).

• 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. Dec 13 '18 at 17:23

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.

• 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 Dec 12 '18 at 1:02
• *"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. Dec 13 '18 at 17:25