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.

  • $\begingroup$ 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 $\endgroup$ Oct 13, 2010 at 15:05
  • $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Oct 13, 2010 at 15:08
  • $\begingroup$ 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. $\endgroup$
    – Lev Reyzin
    Oct 13, 2010 at 19:49
  • $\begingroup$ that sounds like agnostic learning with an upper bound on OPT(C,D) $\endgroup$ Oct 13, 2010 at 22:23
  • $\begingroup$ 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). $\endgroup$
    – Lev Reyzin
    Oct 13, 2010 at 23:37

1 Answer 1


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 and this)
  • 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 on agnostic learning may also interest you.

  • $\begingroup$ 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? $\endgroup$
    – Aaron Roth
    Oct 13, 2010 at 20:22
  • $\begingroup$ 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. $\endgroup$
    – Lev Reyzin
    Oct 13, 2010 at 20:53
  • $\begingroup$ so you want unbounded VC-dimension classes ? $\endgroup$ Oct 13, 2010 at 22:24
  • $\begingroup$ unbounded VC dimension would certainly be interesting, but large finite (for fixed d) classes are already extremely interesting (and seem to be rare) $\endgroup$
    – Aaron Roth
    Oct 13, 2010 at 22:51
  • 1
    $\begingroup$ @LevReyzin The Kalai lectures link is not working. Could you kindly fix this? I searched on the net but couldnt find this either. $\endgroup$
    – Student
    Mar 3, 2018 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.