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$ Commented 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
    Commented Dec 11, 2018 at 23:07
  • $\begingroup$ Is this “fixed distribution” easy to sample from? $\endgroup$
    – Aryeh
    Commented 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.
    Commented 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.
    Commented 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.
    Commented 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
    Commented 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.
    Commented Dec 13, 2018 at 17:25

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.