# PAC learning vs. learning on uniform distribution

The class of function $$\mathcal{F}$$ is PAC-learnable if there exists an algorithm $$A$$ such that for any distribution $$D$$, any unknown function $$f$$ and any $$\epsilon, \delta$$ it holds that there exists $$m$$ such that on an input of $$m$$ i.i.d samples $$(x, f(x))$$ where $$x\sim D$$, $$A$$ returns, with probability larger than $$1-\delta$$, a function which is $$\epsilon$$-close to $$f$$ (with respect to $$D$$). The class $$\mathcal{F}$$ is efficiently PAC learnable if it is PAC learnable, and $$A$$ runs in time $$\text{poly}(1/\epsilon, 1/\delta, n)$$ (where $$|x| = n$$) and the description of $$f$$.

Is there a case where a class $$\mathcal{F}$$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?

Is there a case where a class $$\mathcal{F}$$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?
This has been asked on TCS.SE. It looks like the short answer is yes -- Aaron Roth gives the example of width-$$k$$ conjunctions for $$k \gg \log n$$. And in the comments, Avrim Blum is quoted as giving the answer of $$2$$-term DNF.
I don't totally understand the examples there -- it must take a bit more work to really derive the result (I will update this answer if I find a self-contained proof). But the general problem here with the uniform distribution is that if the target function $$f$$ is "sparse", meaning it labels at most a $$\delta$$ fraction of the input distribution with $$1$$, then it is easy to learn by simply guessing $$0$$.