Does anyone know of a concept class known to be (1) efficiently learnable under the uniform distribution but (1) NP-hard to learn under arbitrary [adversarial] distributions? I mean "learning" in the proper PAC sense.


Here is an example that may not be exactly what you want, but is still emblematic of a general class of problems. In this instance, the hardness is only for agnostic learning, and only for "proper" learning in the sense that the representation class is restricted, and the easyness over the uniform distribution is for trivial reasons.

Width-k conjunctions are NP hard to learn using halfspaces (and in particular using conjunctions) over arbitrary distributions, even for $k > \log(n)$: http://www.cs.cmu.edu/~yiwu/paper/mono.pdf

On the other hand, for $k \gg \log n$, width $k$ conjunctions are trivial to learn over the uniform distribution over examples using conjunctions, since every width-k conjunction will label a $1-1/2^k$ fraction of examples "0", so every width-k conjunction is a good hypothesis.

I would guess that there are similar examples that hold more broadly. Notice that easyness of learning over the uniform distribution holds for any "unbalanced" function, for the same trivial reason. Take a class of functions that is hard to learn even non-agnostically (poly-sized circuits, say). I would think that you could modify the lower-bound proof to hold even if you modify the circuits to be unbalanced: to evaluate to $1$ only on an $\epsilon$ fraction of random inputs. Meanwhile the hard distribution could still be one in which $\Pr[A(x) = 1] = 1/2$.

  • 1
    $\begingroup$ Avrim Blum's answer via email: "2-term DNF. NP-hard for proper learning in general, but easy over the uniform distribution (find some $x_i$ s.t. $Pr(+|x_i=0) < Pr(+)$, and then $T_2 = {x_j : Pr(+ | x_i=0,x_j=0) = 0})$." $\endgroup$ – Aryeh Mar 14 '12 at 7:27
  • $\begingroup$ I don't understand this comment: "since every width-k conjunction will label a $1-1/2^k$ fraction of examples 0, so every width-k conjunction is a good hypothesis." This does not seem to be true if $\epsilon$ is sufficiently small, i.e. $\epsilon < \frac{1}{2^k}$. In this case how would the learning algorithm proceed? $\endgroup$ – 6005 Apr 18 '20 at 18:38
  • $\begingroup$ @Aryeh Can you clarify Blum's example? What is $T_2$? $\endgroup$ – 6005 Apr 18 '20 at 18:49
  • 1
    $\begingroup$ @6005 We're talking about 2-term DNFs, i.e., expressions of the form $T_1\vee T_2$, where the $T_i$ are conjunctions of literals. $\endgroup$ – Aryeh Apr 18 '20 at 20:12

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.