Chain rules for Rademacher complexity

Abstract

Two preliminary estimates are obtained for expected suprema of Bernoulli processes indexed by an image of a bounded Euclidean subset through a class of Lipschitz functions. If that bounded subset is given by the projection of a bounded function class onto a sample vector, the result can be considered as a control over empirical Rademacher complexity of a composite function class. Such an estimate can be applied to learning problems where the hypotheses have composite structure or where more than one function is needed to determine the empirical loss.