Fast convergence of extended Rademacher Complexity bounds

In this work we propose some new generalization bounds for binary classifiers, based on global Rademacher Complexity (RC), which exhibit fast convergence rates by combining state-of-the-art results by Talagrand on empirical processes and the exploitation of unlabeled patterns. In this framework, we are able to improve both the constants and the convergence rates of existing RC-based bounds. All the proposed bounds are based on empirical quantities, so that they can be easily computed in practice, and are provided both in implicit and explicit forms: the formers are the tightest ones, while the latter ones allow to get more insights about the impact of Talagrand's results and the exploitation of unlabeled patterns in the learning process. Finally, we verify the quality of the bounds, with respect to the theoretical limit, showing the room for further improvements in the common scenario of binary classification.