We next have to convert this algorithm which guarantees an expected error bounded by \(\mathrm {Ndim}(\mathcal {H}) \Theta (\log (k))/(n+1)\)  into an algorithm
that guarantees a bound on the error with probability at least \(1-\delta \) . In order to boost the algorithm, we use a standard boosting algorithm by decomposing the dataset into \(\log (1/\delta )\)  parts and using Chernoff bounds. For the details we refer to the boosting trick of [1]} and the proof of Theorem 34.(i) of [2]}.
