Distribution-Dependent Weighted Union Bound †

In this paper, we deal with the classical Statistical Learning Theory’s problem of bounding, with high probability, the true risk [Formula: see text] of a hypothesis h chosen from a set [Formula: see text] of m hypotheses. The Union Bound (UB) allows one to state that [Formula: see text] where [Formula: see text] is the empirical errors, if it is possible to prove that [Formula: see text] and [Formula: see text] , when h, [Formula: see text] , and [Formula: see text] are chosen before seeing the data such that [Formula: see text] and [Formula: see text]. If no a priori information is available [Formula: see text] and [Formula: see text] are set to [Formula: see text] , namely equally distributed. This approach gives poor results since, as a matter of fact, a learning procedure targets just particular hypotheses, namely hypotheses with small empirical error, disregarding the others. In this work we set the [Formula: see text] and [Formula: see text] in a distribution-dependent way increasing the probability of being chosen to function with small true risk. We will call this proposal Distribution-Dependent Weighted UB (DDWUB) and we will retrieve the sufficient conditions on the choice of [Formula: see text] and [Formula: see text] that state that DDWUB outperforms or, in the worst case, degenerates into UB. Furthermore, theoretical and numerical results will show the applicability, the validity, and the potentiality of DDWUB.