Local Rademacher Complexity Bounds based on Covering Numbers
This paper provides a general result on controlling local Rademacher complexities, which captures in an elegant form to relate the complexities with constraint on the expected norm to the corresponding ones with constraint on the empirical norm. This result is convenient to apply in real applications and could yield refined local Rademacher complexity bounds for function classes satisfying general entropy conditions. We demonstrate the power of our complexity bounds by applying them to derive effective generalization error bounds.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sharper Generalization Bounds for Transformer
This paper studies generalization error bounds for Transformer models. Based on the offset Rademacher complexity, we derive sharper generalization bounds for different Transformer architectures, including single-layer si…
Adversarial Rademacher Complexity of Deep Neural Networks
Deep neural networks are vulnerable to adversarial attacks. Ideally, a robust model shall perform well on both the perturbed training data and the unseen perturbed test data. It is found empirically that fitting perturbe…
ARCApproximate Description Length, Covering Numbers, and VC Dimension
Recently, Daniely and Granot [arXiv:1910.05697] introduced a new notion of complexity called Approximate Description Length (ADL). They used it to derive novel generalization bounds for neural networks, that despite subs…
Generalization BoundsA Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
We study gapped scale-sensitive dimensions of a function class in both sequential and non-sequential settings. We demonstrate that covering numbers for any uniformly bounded class are controlled above by these gapped dim…
Generalization Analysis for Contrastive Representation Learning
Recently, contrastive learning has found impressive success in advancing the state of the art in solving various machine learning tasks. However, the existing generalization analysis is very limited or even not meaningfu…
Contrastive LearningGeneralization BoundsRepresentation Learning