4
$\begingroup$

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

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

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

$\endgroup$
  • $\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. Dec 13 '18 at 17:23
1
$\begingroup$

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.

$\endgroup$
  • $\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 Dec 12 '18 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. Dec 13 '18 at 17:25

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.