should output a collection of functions $f_{1},\ldots,f_{m}\in\mathcal{F}$, such that a (possibly-weighted) majority vote over $f_{1}\left(  x\right)  ,\ldots,f_{m}\left(  x\right)  $ predicts $f^{\ast}\left(  x\right)  $ ‘extremely well.’  It turns out [@schapire; @fs_adaboost] that this goal can be achieved in a very general setting.

Our majority-certificates lemma has strengths and weaknesses compared to boosting.  Our assumptions are much milder than those of boosting: rather than needing a weak learner, we assume only that the hypothesis class $S$ is ‘not too large.’  Also, we represent our target function $f^{\ast}$ *exactly* by $\operatorname*{MAJ}\left(
f_{1},\ldots,f_{m}\right)  $, not just approximately.  On the other hand, we do not give an efficient algorithm to *find* our majority-representation. Also, the $f_{i}$’s are not ‘explicitly given’: we only give a way to *recognize* each $f_{i}$, under the assumption that the function purporting to be $f_{i}$ is in fact drawn from the original hypothesis class.

The proof of our lemma also has similarities to boosting.  As an analogue of a ‘weak learner’, we show that for every distribution $\mathcal{D}$, there exists a function $f\in S$ which agrees with the target function $f^{\ast}$ on most $x\sim\mathcal{D}$, *and* which is isolatable in $S$ by specifying $O(\log|S|)$ queries.  Using the Minimax Theorem, we then nonconstructively 