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).
-
$\begingroup$ 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. $\endgroup$Noah Stephens-Davidowitz– Noah Stephens-Davidowitz2018年12月11日 22:46:02 +00:00Commented Dec 11, 2018 at 22:46
-
1$\begingroup$ @NoahStephens-Davidowitz Yeah, I edited the problem, we now assume H to be statistically PAC-learnable. $\endgroup$Paul– Paul2018年12月11日 23:07:18 +00:00Commented Dec 11, 2018 at 23:07
-
$\begingroup$ Is this "fixed distribution" easy to sample from? $\endgroup$Aryeh– Aryeh2018年12月12日 06:37:59 +00:00Commented Dec 12, 2018 at 6:37
-
$\begingroup$ @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. $\endgroup$Clement C.– Clement C.2018年12月13日 16:28:21 +00:00Commented Dec 13, 2018 at 16:28
-
$\begingroup$ @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." $\endgroup$Clement C.– Clement C.2018年12月13日 16:32:28 +00:00Commented Dec 13, 2018 at 16:32
2 Answers 2
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]).
-
$\begingroup$ 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"). $\endgroup$Clement C.– Clement C.2018年12月13日 17:23:49 +00:00Commented Dec 13, 2018 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.
-
$\begingroup$ 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). $\endgroup$Paul– Paul2018年12月12日 01:02:29 +00:00Commented Dec 12, 2018 at 1:02
-
$\begingroup$ *"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. $\endgroup$Clement C.– Clement C.2018年12月13日 17:25:21 +00:00Commented Dec 13, 2018 at 17:25
Explore related questions
See similar questions with these tags.