$\ell_{\infty}$ Vector Contraction for Rademacher Complexity
Dylan J. Foster, Alexander Rakhlin · arXiv (Cornell University) · 2019
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})$.