# Optimal PAC Bounds Without Uniform Convergence arXiv: https://arxiv.org/abs/2304.09167 ยท HTML: https://mlsanity.com/paper/2304.09167/ ## Key facts - Cited by 33 papers in the map (data through 14 Oct 2026). - Builds on 14 of its 66 references that are in the map. - First posted on arXiv 18 Apr 2023. ## Builds on (most cited first, 14 of 14) - [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018) - [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015) - [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022) - [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014) - [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021) - [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020) - [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022) - [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020) - [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015) - [Martingale Methods for Sequential Estimation of Convex Functionals and Divergences](https://mlsanity.com/paper/2103.09267/) (2021) - [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022) - [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022) - [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022) - [Primal and Dual Combinatorial Dimensions](https://mlsanity.com/paper/2108.10037/) (2021) ## Built on by (most cited first, 30 of 33) - [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023) - [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024) - [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023) - [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023) - [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024) - [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026) - [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023) - [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025) - [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024) - [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024) - [On Agnostic PAC Learning in the Small Error Regime](https://mlsanity.com/paper/2502.09496/) (2025) - [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024) - [Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability](https://mlsanity.com/paper/2507.17316/) (2025) - [Majority-of-Three is Optimal](https://mlsanity.com/paper/2606.13614/) (2026) - [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024) - [Understanding Aggregations of Proper Learners in Multiclass Classification](https://mlsanity.com/paper/2410.22749/) (2024) - [Transductive Learning Is Compact](https://mlsanity.com/paper/2402.10360/) (2024) - [PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting](https://mlsanity.com/paper/2605.25678/) (2026) - [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026) - [PAC Learning is just Bipartite Matching (Sort of)](https://mlsanity.com/paper/2502.00607/) (2025) - [Universal rates of ERM for agnostic learning](https://mlsanity.com/paper/2506.14110/) (2025) - [The price of multi-group transductive learning](https://mlsanity.com/paper/2606.04423/) (2026) - [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026) - [Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation](https://mlsanity.com/paper/2603.02043/) (2026) - [Margin in Abstract Spaces](https://mlsanity.com/paper/2603.07221/) (2026) - [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026) - [A Fine-Grained Understanding of Uniform Convergence for Halfspaces](https://mlsanity.com/paper/2605.06004/) (2026) - [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026) - [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026) - [Optimistic Rates for Multiclass PAC Learning](https://mlsanity.com/paper/2608.10869/) (2026) ## Abstract (arXiv) In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classification. In this paper, we address this issue by providing optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. Our framework converts the leave-one-out error of permutation invariant predictors into high probability risk bounds. As an application, by adapting the one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth, we propose an algorithm that achieves an optimal PAC bound for binary classification. Specifically, our result shows that certain aggregations of one-inclusion graph algorithms are optimal, addressing a variant of a classic question posed by Warmuth. We further instantiate our framework in three settings where uniform convergence is provably suboptimal. For multiclass classification, we prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, addressing the suboptimality of the analysis of Daniely and Shalev-Shwartz. For partial hypothesis classification, we determine the optimal sample complexity bound, resolving a question posed by Alon, Hanneke, Holzman, and Moran. For realizable bounded regression with absolute loss, we derive an optimal risk bound that relies on a modified version of the scale-sensitive dimension, refining the results of Bartlett and Long. Our rates surpass standard uniform convergence-based results due to the smaller complexity measure in our risk bound.