Separation result for proper learning under the uniform vs. adversarial distributions?

Question

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.

Answer 1

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