${\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

References in corpus (3)

• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
• Structured Prediction Theory Based on Factor Graph Complexity

Cited by in corpus (5)

• Investigating the Role of Negatives in Contrastive Representation Learning
• New bounds for $k$-means and information $k$-means
• Nearly Optimal Clustering Risk Bounds for Kernel K-Means
• Estimating High-Dimensional Discrete Choice Model of Differentiated Products with Random Coefficients
• On Generalization Bounds for Projective Clustering