# Relative Deviation Margin Bounds

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2020.

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

- [Improved Balanced Classification with Theoretically Grounded Loss Functions](https://mlsanity.com/paper/2512.23947/) (2025)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [The Price of Implicit Bias in Adversarially Robust Generalization](https://mlsanity.com/paper/2406.04981/) (2024)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Margin theory for the scenario-based approach to robust optimization in high dimension](https://mlsanity.com/paper/2303.03891/) (2023)
- [Uniform Risk Bounds for Learning with Dependent Data Sequences](https://mlsanity.com/paper/2303.11650/) (2023)
- [Compression Implies Generalization](https://mlsanity.com/paper/2106.07989/) (2021)

## Abstract (arXiv)

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.