Relative Deviation Margin Bounds

2020/06/26 by Corinna Cortes, Mehryar Mohri, Cortes, Corinna +3
Computer Science · Engineering · #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2006.14950

openalex publication_date 2020/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a series of new and more favorable margin-based learning guarantees that depend on the empirical margin loss of a predictor. We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity or the empirical ℓ_∞ covering number of the hypothesis set used. Furthermore, using our relative deviation margin bounds, we derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment. We also briefly highlight several applications of these bounds and discuss their connection with existing results.

Citations

• A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Near-Tight Margin-Based Generalization Bounds for Support Vector\n Machines

Related

• Relative Deviation Learning Bounds and Generalization with Unbounded\n Loss Functions
• Uniform Deviation Bounds for Unbounded Loss Functions like k-Means
• On the Optimization of Margin Distribution
• On the Consistency of Max-Margin Losses
• Multiclass learning with margin: exponential rates with no bias-variance trade-off