Definition 1 ([1]}, Definition 1.4) 
Let \(\mathcal {H}\subseteq [k]^\mathcal {X}\)  and let \(R : \mathbb {N}\rightarrow [0,1],\)  with \(R(n) \rightarrow 0\) , be a rate function.
We say that
\(\mathcal {H}\)  is learnable at rate \(R\) if there exists a learning algorithm \(\widehat{h}_n\)  such that for every realizable distribution \(P\)  on \(\mathcal {X}\times [k]\)  with respect to \(\mathcal {H}\) , there exist distribution-dependent \(C,c > 0\)  for which \(\mathop {\bf E}[\mathrm {er}(\widehat{h}_n)] \le C R(cn),\)  for all \(n \in \mathbb {N}\) .
Also, \(\mathcal {H}\)  is not learnable at rate faster than \(R\) if for any learning algorithm \(\widehat{h}_n\) , there exists a realizable distribution \(P\)  on \(\mathcal {X}\times [k]\)  with respect to \(\mathcal {H}\)  and distribution-dependent \(C,c > 0\)  for which \(\mathop {\bf E}[\mathrm {er}(\widehat{h}_n)] \ge C R(cn)\)  for infinitely many \(n \in \mathbb {N}\) .
\(\mathcal {H}\)  is learnable with optimal rate \(R\) if it is learnable at rate \(R\)  and is not learnable faster than \(R\) .
Finally, \(\mathcal {H}\)  requires arbitrarily slow rates if, for every \(R(n) \rightarrow 0\) , \(\mathcal {H}\)  is not learnable at rate faster than \(R\) .

