11
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\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$ – Suresh Venkat Oct 13 '10 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 '10 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 '10 at 19:49
  • $\begingroup$ that sounds like agnostic learning with an upper bound on OPT(C,D) $\endgroup$ – Suresh Venkat Oct 13 '10 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 '10 at 23:37
9
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\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 '10 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 '10 at 20:53
  • $\begingroup$ so you want unbounded VC-dimension classes ? $\endgroup$ – Suresh Venkat Oct 13 '10 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 '10 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$ – Anirbit Mar 3 '18 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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