Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions

2013/10/22 by Corinna Cortes, Cortes, Corinna, Spencer Greenberg +3 · 1 citation
Computer Science · Decision Sciences · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Multi-Criteria Decision Making #cs.LG

paper · pdf · doi:10.48550/arxiv.1310.5796

openalex publication_date 2013/10/22 · arxiv created 2016/04/04 · arxiv updated 2016/04/06 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

We present an extensive analysis of relative deviation bounds, including detailed proofs of two-sided inequalities and their implications. We also give detailed proofs of two-sided generalization bounds that hold in the general case of unbounded loss functions, under the assumption that a moment of the loss is bounded. These bounds are useful in the analysis of importance weighting and other learning tasks such as unbounded regression.

Cited by

• Complexity Dependent Error Rates for Physics-informed Statistical Learning via the Small-ball Method

Related

• Relative Deviation Margin Bounds
• Uniform Deviation Bounds for Unbounded Loss Functions like k-Means
• Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation
• Generalization Bounds via Convex Analysis
• Distribution-dependent concentration inequalities for tighter generalization bounds