Global Rademacher Complexity Bounds: From Slow to Fast Convergence Rates

Previousworksinliteratureshowedthatperformanceestimationsoflearningpro- cedures can be characterized by a convergence rate ranging between O(n^(−1)) (fast rate) and O(n^(−1/2)) (slow rate). In order to derive such result, some assumptions on the prob- lem are required; moreover, even when convergence is fast, the constants characterizing the bounds are often quite loose. In this work, we prove new Rademacher complexity (RC) based bounds, which do not require any additional assumptions for achieving a fast convergence rate O(n^(−1)) in the optimistic case and a slow rate O(n^(−1/2)) in the general case. At the same time, they are characterized by smaller constants with respect to other state-of-the-art RC fast converging alternatives in literature. The results proposed in this work are obtained by exploiting the fundamental work of Talagrand on concentration inequalities for product mea- sures and empirical processes. As a further issue, we also provide the extension of the results to the semi-supervised learning framework, showing how additional unlabeled samples allow improving the tightness of the derived bound.