A Useful Definitions & Theorems,, X E[ X

Throughout this paper, we use the following standard Chernoff bounds. We say that H has the uniform convergence property w.r.t. We first define the quantities with respect to the distribution. For a given hypothesis h H, group U Γ and interval I Λ, we are interested in the subpoppulation which belongs to U and for which h prediction is in I, i.e., [x U, h(x) I]. We define a "bad" event B In order to do so, we would like to have a "large enough" induced sample in every interesting category.