and not too large gets replaced by a more subtle assumption: namely, an upper bound on the so-called *fat-shattering dimension* of $S$.  To prove our generalization, we use powerful results of Alon et al. [@abch] and Bartlett and Long [@bartlettlong] on the learnability of real-valued functions.  We then use a bound on the fat-shattering dimension of real-valued functions defined by quantum states (from Aaronson [@aar:learn], building on Ambainis et al. [@antv]). Figure \[yqpflow\] shows the overall dependency structure of the proof.

\[ptb\]

[yqpflow2.eps]{}

Majority-Certificates Lemma in Context\[MAJCERDISCUSSION\]
----------------------------------------------------------

The majority-certificates lemma is closely related to the seminal notion of *boosting* [@schapire] from computational learning theory.  Boosting is a broad topic with a vast literature, but a common ‘generic’ form of the boosting problem is as follows: we want to learn some target function $f^{\ast}$, given sample data of the form $\left(  x,f^{\ast}\left(  x\right)
\right)  $.  We assume we have a *weak learning algorithm* $A^{f^{\ast},\mathcal{D}}$, with the property that, for any probability distribution $\mathcal{D}$ over inputs $x$, with high probability $A$ finds a hypothesis $f\in\mathcal{F}$ which predicts $f^{\ast
}\left(  x\right)  $ ‘reasonably well’ when $x\sim\mathcal{D}$.  The task is to ‘boost’ this weak learner into a *strong* learner $B^{f^{\ast}}$.  The strong learner 