$\ell_{\infty}$ Vector Contraction for Rademacher Complexity
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})$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A vector-contraction inequality for Rademacher complexities using $p$-stable variables
Andreas Maurer in the paper "A vector-contraction inequality for Rademacher complexities" extended the contraction inequality for Rademacher averages to Lipschitz functions with vector-valued domains; He did it replacing…
A vector-contraction inequality for Rademacher complexities
The contraction inequality for Rademacher averages is extended to Lipschitz functions with vector-valued domains, and it is also shown that in the bounding expression the Rademacher variables can be replaced by arbitrary…
ClusteringRademacher Complexity for Adversarially Robust Generalization
Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with hig…
BIG-bench Machine LearningOn Rademacher Complexity-based Generalization Bounds for Deep Learning
We show that the Rademacher complexity-based approach can generate non-vacuous generalisation bounds on Convolutional Neural Networks (CNNs) for classifying a small number of classes of images. The development of new Tal…
Deep LearningGeneralization BoundsMajorizing Measures, Sequential Complexities, and Online Learning
We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dom…