<p>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. </p>

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

<p>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.</p>

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

CC BY-SA 3.0
2012-03-14T07:27:06.860Z
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})$."
Aryeh
CC BY-SA 4.0
2020-04-18T18:38:56.803Z
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?
Caleb Stanford
CC BY-SA 4.0
2020-04-18T18:49:20.573Z
@Aryeh Can you clarify Blum's example? What is $T_2$?
Caleb Stanford
CC BY-SA 4.0
2020-04-18T20:12:01.443Z
@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.
Aryeh
CC BY-SA 3.0
2012-03-13T19:56:36.887Z
2012-03-13T22:07:12.637Z
2012-03-13T22:07:12.637Z
Aaron Roth
<p>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.</p>

<machine-learning><lg.learning>
Separation result for proper learning under the uniform vs. adversarial distributions?
Aryeh
# Separation result for proper learning under the uniform vs. adversarial distributions?

(Asked by: username_0 on 2012-03-13)

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.

**Tags:** machine-learning, lg.learning


---

## 1 answers

### Answer by username_1 on 2012-03-13. Score: 6

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

> **Comments:**
> **username_0**: 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})$."  
> **username_2**: 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?  
> **username_2**: @username_0 Can you clarify Blum's example? What is $T_2$?  
> **username_0**: @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.  

---

