# Local Rademacher Complexity Bounds based on Covering Numbers

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2015.

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

- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [The Minority Matters: A Diversity-Promoting Collaborative Metric Learning Algorithm](https://mlsanity.com/paper/2209.15292/) (2022)
- [Improved Diversity-Promoting Collaborative Metric Learning for Recommendation](https://mlsanity.com/paper/2409.01012/) (2024)
- [Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks](https://mlsanity.com/paper/2103.06671/) (2021)
- [Fitted value iteration methods for bicausal optimal transport](https://mlsanity.com/paper/2306.12658/) (2023)
- [Does Order Matter : Connecting The Law of Robustness to Robust Generalization](https://mlsanity.com/paper/2602.20971/) (2026)
- [Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations](https://mlsanity.com/paper/2512.01213/) (2025)
- [Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees](https://mlsanity.com/paper/2606.29331/) (2026)
- [Optimal Allocation of Embedding Dimensions under Finite-Sample Constraints](https://mlsanity.com/paper/2608.24592/) (2026)

## Abstract (arXiv)

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.