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.
Agnostic learning over arbitrary distributions
reference request;machine learning;lg.learning
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.