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.
1 Answer
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$– AryehMar 14, 2012 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$ Apr 18, 2020 at 18:38
-
$\begingroup$ @Aryeh Can you clarify Blum's example? What is $T_2$? $\endgroup$ Apr 18, 2020 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$– AryehApr 18, 2020 at 20:12