# Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions

arXiv: https://arxiv.org/abs/1310.5796 · HTML: https://mlsanity.com/paper/1310.5796/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2013.

## Built on by (most cited first, 15 of 15)

- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [Information-Theoretic Analysis of Unsupervised Domain Adaptation](https://mlsanity.com/paper/2210.00706/) (2022)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [Best-Effort Adaptation](https://mlsanity.com/paper/2305.05816/) (2023)
- [Generalization and Robustness of the Tilted Empirical Risk](https://mlsanity.com/paper/2409.19431/) (2024)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)
- [Some Hoeffding- and Bernstein-type Concentration Inequalities](https://mlsanity.com/paper/2102.06304/) (2021)
- [Conditional Linear Regression for Heterogeneous Covariances](https://mlsanity.com/paper/2111.07834/) (2021)
- [Distribution-free Deviation Bounds and The Role of Domain Knowledge in Learning via Model Selection with Cross-validation Risk Estimation](https://mlsanity.com/paper/2303.08777/) (2023)
- [Uniform Risk Bounds for Learning with Dependent Data Sequences](https://mlsanity.com/paper/2303.11650/) (2023)
- [Complexity Dependent Error Rates for Physics-informed Statistical Learning via the Small-ball Method](https://mlsanity.com/paper/2510.23149/) (2025)
- [Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget](https://mlsanity.com/paper/2602.17894/) (2026)
- [Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion](https://mlsanity.com/paper/2111.00062/) (2021)

## Abstract (arXiv)

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.