${\ell }_{\infty }$ Vector Contraction for Rademacher Complexity

Abstract

We show that the Rademacher complexity of any ${\mathbb{R}}^K$-valued function class composed with an ${\ell }_{\infty }$-Lipschitz function is bounded by the maximum Rademacher complexity of the restriction of the function class along each coordinate, times a factor of $\tilde{O}(\sqrt{K})$.

Technical note