<p>If no class is too simple, then here are some agnostically PAC learnable classes.  In response to the comments, the classes with polynomially many hypotheses are crossed out:</p>

<ul>
<li><s>constant depth decision trees (and other classes having only poly many hypotheses)</s></li>
<li><s>hyperplanes in $R^2$ (only $O(n^2)$ hypotheses producing distinct labelings)</s></li>
<li>unions of intervals (dynamic programming)</li>
<li>parity on some of the first $\log(k)\log\log(k)$ of $n$ bits (see <a href="http://portal.acm.org/citation.cfm?id=335355" rel="nofollow">this</a> and <a href="http://portal.acm.org/citation.cfm?id=1374466" rel="nofollow">this</a>)</li>
<li><s>other hypothesis classes in low dimensional settings.</s></li>
</ul>

<p>Pretty much everything else is NP-Hard to (at least properly) agnostically PAC learn.</p>

<p>Adam Kalai's <a href="http://kalai.wik.is/@api/deki/files/8/=nips-tut.pdf" rel="nofollow">tutorial</a> on agnostic learning may also interest you.</p>

CC BY-SA 3.0
2018-03-03T18:38:28.397Z
@LevReyzin The Kalai lectures link is not working. Could you kindly fix this? I searched on the net but couldnt find this either.
Student
CC BY-SA 2.5
2010-10-13T20:22:16.573Z
Thanks. So constant depth decision trees, 2-dimensional hyperplanes, (I assume the other low dimensional settings you refer to) all fall into the category of having only polynomially many functions, which can be learned by exhaustion. Parities on log(k)loglog(k) bits and unions of intervals are interesting in that they contain superpolynomially many functions. Are there others like these?
Aaron Roth
CC BY-SA 2.5
2010-10-13T20:53:49.110Z
Right, though there are infinitely many hyperplanes in R^2, just O(n^2) w.r.t. classifying the data points differently. I don't know any other interesting classes off the top of my head, but if I think of / find any, I'll edit my answer.
Lev Reyzin
CC BY-SA 2.5
2010-10-13T22:24:29.070Z
so you want unbounded VC-dimension classes ?
Suresh Venkat
CC BY-SA 2.5
2010-10-13T22:51:42.673Z
unbounded VC dimension would certainly be interesting, but large finite (for fixed d) classes are already extremely interesting (and seem to be rare)
Aaron Roth
CC BY-SA 3.0
2010-10-13T19:08:37.767Z
2014-02-01T19:24:54.193Z
2014-02-01T19:24:54.193Z
Lev Reyzin
<p>Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:
$$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$$
and let:
$$OPT(C,D) = \min_{f \in C}\ err(f,D)$$
Say that an algorithm $A$ agnostically learns $C$ over any distribution, if for any $D$ it can with probability $2/3$ find a function $f$ such that $err(f,D) \leq OPT(C,D) + \epsilon$, given time and a number of samples from $D$ that is bounded by a polynomial in $d$ and $1/\epsilon$. </p>

<blockquote>
  <p>Question: What classes of functions $C$ are known to be agnostically learnable over arbitrary distributions?</p>
</blockquote>

<p>No class is too simple! I know that even monotone conjunctions are not known to be agnostically learnable over arbitrary distributions, so I'm just looking for nontrivial classes of functions.</p>

CC BY-SA 2.5
2010-10-13T15:05:08.783Z
worth pointing out for the uninitiated that agnostic learning is focused on the case when OPT(C, D) > 0 (i.e you have the wrong hypothesis class
Suresh Venkat
CC BY-SA 2.5
2010-10-13T15:08:44.340Z
Good point. In the special case when OPT(C,D) = 0, this is PAC learning, and is much easier. For agnostic learning, the guarantee must hold no matter what OPT(C,D) is.
Aaron Roth
CC BY-SA 2.5
2010-10-13T19:49:26.093Z
There's also the "PAC w/ Classification Noise" case where OPT(C,D) > 0, and even though you have the right hypothesis class (realizable setting) there's some error because the labels are randomly flipped due to noise... I wish the names of the different settings were less confusing.
Lev Reyzin
CC BY-SA 2.5
2010-10-13T22:23:50.303Z
that sounds like agnostic learning with an upper bound on OPT(C,D)
Suresh Venkat
CC BY-SA 2.5
2010-10-13T23:37:27.863Z
Not quite, because the noise is not allowed to be arbitrary in the classification noise model.  So if there were some adversarial noise pattern that made learning (or finding the empirical risk minimizer) hard in the agnostic model, it might not occur often in the classification noise model (ie fall into the PAC delta parameter).
Lev Reyzin
<reference-request><machine-learning><lg.learning>
Agnostic learning over arbitrary distributions
Aaron Roth
# Agnostic learning over arbitrary distributions

(Asked by: username_0 on 2010-10-13)

Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:
$$err(f,D) = \Pr\_{(x,y) \sim D}[f(x) \neq y]$$
and let:
$$OPT(C,D) = \min\_{f \in C}\ err(f,D)$$
Say that an algorithm $A$ agnostically learns $C$ over any distribution, if for any $D$ it can with probability $2/3$ find a function $f$ such that $err(f,D) \leq OPT(C,D) + \epsilon$, given time and a number of samples from $D$ that is bounded by a polynomial in $d$ and $1/\epsilon$.

> Question: What classes of functions $C$ are known to be agnostically learnable over arbitrary distributions?

No class is too simple! I know that even monotone conjunctions are not known to be agnostically learnable over arbitrary distributions, so I'm just looking for nontrivial classes of functions.

**Tags:** reference-request, machine-learning, lg.learning
> **Comments:**
> **username_1**: worth pointing out for the uninitiated that agnostic learning is focused on the case when OPT(C, D) > 0 (i.e you have the wrong hypothesis class  
> **username_0**: Good point. In the special case when OPT(C,D) = 0, this is PAC learning, and is much easier. For agnostic learning, the guarantee must hold no matter what OPT(C,D) is.  
> **username_2**: There's also the "PAC w/ Classification Noise" case where OPT(C,D) > 0, and even though you have the right hypothesis class (realizable setting) there's some error because the labels are randomly flipped due to noise... I wish the names of the different settings were less confusing.  
> **username_1**: that sounds like agnostic learning with an upper bound on OPT(C,D)  
> **username_2**: Not quite, because the noise is not allowed to be arbitrary in the classification noise model.  So if there were some adversarial noise pattern that made learning (or finding the empirical risk minimizer) hard in the agnostic model, it might not occur often in the classification noise model (ie fall into the PAC delta parameter).  

---

## 1 answers

### Answer by username_2 on 2010-10-13. Score: 9 | Accepted answer

If no class is too simple, then here are some agnostically PAC learnable classes. In response to the comments, the classes with polynomially many hypotheses are crossed out:

* ~~constant depth decision trees (and other classes having only poly many hypotheses)~~
* ~~hyperplanes in $R^2$ (only $O(n^2)$ hypotheses producing distinct labelings)~~
* unions of intervals (dynamic programming)
* parity on some of the first $\log(k)\log\log(k)$ of $n$ bits (see [this](http://portal.acm.org/citation.cfm?id=335355) and [this](http://portal.acm.org/citation.cfm?id=1374466))
* ~~other hypothesis classes in low dimensional settings.~~

Pretty much everything else is NP-Hard to (at least properly) agnostically PAC learn.

Adam Kalai's [tutorial](http://kalai.wik.is/@api/deki/files/8/=nips-tut.pdf) on agnostic learning may also interest you.

> **Comments:**
> **username_0**: Thanks. So constant depth decision trees, 2-dimensional hyperplanes, (I assume the other low dimensional settings you refer to) all fall into the category of having only polynomially many functions, which can be learned by exhaustion. Parities on log(k)loglog(k) bits and unions of intervals are interesting in that they contain superpolynomially many functions. Are there others like these?  
> **username_2**: Right, though there are infinitely many hyperplanes in R^2, just O(n^2) w.r.t. classifying the data points differently. I don't know any other interesting classes off the top of my head, but if I think of / find any, I'll edit my answer.  
> **username_1**: so you want unbounded VC-dimension classes ?  
> **username_0**: unbounded VC dimension would certainly be interesting, but large finite (for fixed d) classes are already extremely interesting (and seem to be rare)  
> **username_3**: @LevReyzin The Kalai lectures link is not working. Could you kindly fix this? I searched on the net but couldnt find this either.  

---

