$\ell_{\infty}$ Vector Contraction for Rademacher Complexity
This provides a theoretical tool for analyzing generalization in high-dimensional machine learning settings, though it appears incremental as an extension of existing contraction principles.
The paper tackles the problem of bounding the Rademacher complexity for vector-valued function classes composed with Lipschitz functions, showing that it is bounded by the maximum coordinate-wise Rademacher complexity times a factor of approximately the square root of the dimension K.
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})$.