The above result guarantees that the expected error of the learning algorithm tends to zero as \(t\)  goes to infinity, i.e., we have established that that \(\mathop {\bf E}[\mathrm {er}(\widehat{y}_t)] \rightarrow 0\)  as \(t \rightarrow \infty \) . This means that the ordinal SOA is a consistent algorithm in the statistical setting. However, this fact is not enough to establish the exponential convergence rate. We follow the approach of [1]} to come up with an algorithm that achieves this guarantee.
The first step is to observe that there is some distribution-dependent \(t^{\star }\)  such that
\(\mathop {\bf Pr}[\mathrm {er}(\widehat{y}_{t^{\star }}) > 0] < 1/4\) . If we were to know this \(t^{\star }\)  one way to get the exponential rates is the following: We divide the training set into \(\Theta (n/t^{\star })\)  batches and we get one classifier \(\widehat{y}^i_{t^{\star }}\)  for every batch. Afterwards, we output as classifier the multiclass majority vote among the classifiers.
Nevertheless, we can obtain this exponential convergence even without knowing \(t^\star \)  by computing an estimate for this quantity using samples. Essentially, we provide this estimator in lemma:general-estimate-time. For the proof, we refer to the proof:general-estimate-time.
