# Exact Lower Bounds for the Agnostic Probably-Approximately-Correct (PAC) Machine Learning Model

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2016.

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

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation](https://mlsanity.com/paper/2301.11509/) (2023)
- [Assessing Fairness in the Presence of Missing Data](https://mlsanity.com/paper/2112.04899/) (2021)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Sharp bounds on aggregate expert error](https://mlsanity.com/paper/2407.16642/) (2024)
- [The Empirical Mean is Minimax Optimal for Local Glivenko-Cantelli](https://mlsanity.com/paper/2410.02835/) (2024)
- [Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion](https://mlsanity.com/paper/2111.00062/) (2021)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)

## Abstract (arXiv)

We provide an exact non-asymptotic lower bound on the minimax expected excess risk (EER) in the agnostic probably-ap-proximately-correct (PAC) machine learning classification model and identify minimax learning algorithms as certain maximally symmetric and minimally randomized "voting" procedures. Based on this result, an exact asymptotic lower bound on the minimax EER is provided. This bound is of the simple form c_∞/√nu as nu→∞, where c_∞=0.16997dots is a universal constant, nu=m/d, m is the size of the training sample, and d is the Vapnik--Chervonenkis dimension of the hypothesis class. It is shown that the differences between these asymptotic and non-asymptotic bounds, as well as the differences between these two bounds and the maximum EER of any learning algorithms that minimize the empirical risk, are asymptotically negligible, and all these differences are due to ties in the mentioned "voting" procedures. A few easy to compute non-asymptotic lower bounds on the minimax EER are also obtained, which are shown to be close to the exact asymptotic lower bound c_∞/√nu even for rather small values of the ratio nu=m/d. As an application of these results, we substantially improve existing lower bounds on the tail probability of the excess risk. Among the tools used are Bayes estimation and apparently new identities and inequalities for binomial distributions.