# Refined Error Bounds for Several Learning Algorithms

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

## Key facts

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

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

- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)
- [Fast Rate Information-theoretic Bounds on Generalization Errors](https://mlsanity.com/paper/2303.14658/) (2023)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participation](https://mlsanity.com/paper/2405.02745/) (2024)
- [Universal Rates of Empirical Risk Minimization](https://mlsanity.com/paper/2412.02810/) (2024)
- [Learning in an Echo Chamber: Online Learning with Replay Adversary](https://mlsanity.com/paper/2509.25135/) (2025)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)
- [On the ERM Principle in Meta-Learning](https://mlsanity.com/paper/2411.17898/) (2024)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [The price of multi-group transductive learning](https://mlsanity.com/paper/2606.04423/) (2026)
- [Strategic PAC Learnability via Geometric Definability](https://mlsanity.com/paper/2605.13426/) (2026)
- [Surprises in Proper Positive-Only Learning](https://mlsanity.com/paper/2606.28309/) (2026)
- [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026)
- [When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory](https://mlsanity.com/paper/2608.14020/) (2026)
- [Learning Distributions from Samples and Qualities](https://mlsanity.com/paper/2610.17956/) (2026)

## Abstract (arXiv)

This article studies the achievable guarantees on the error rates of certain learning algorithms, with particular focus on refining logarithmic factors. Many of the results are based on a general technique for obtaining bounds on the error rates of sample-consistent classifiers with monotonic error regions, in the realizable case. We prove bounds of this type expressed in terms of either the VC dimension or the sample compression size. This general technique also enables us to derive several new bounds on the error rates of general sample-consistent learning algorithms, as well as refined bounds on the label complexity of the CAL active learning algorithm. Additionally, we establish a simple necessary and sufficient condition for the existence of a distribution-free bound on the error rates of all sample-consistent learning rules, converging at a rate inversely proportional to the sample size. We also study learning in the presence of classification noise, deriving a new excess error rate guarantee for general VC classes under Tsybakov's noise condition, and establishing a simple and general necessary and sufficient condition for the minimax excess risk under bounded noise to converge at a rate inversely proportional to the sample size.