# Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 31 references that are in the map.
- First posted on arXiv 21 Apr 2023.

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

- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [An Improved Uniform Convergence Bound with Fat-Shattering Dimension](https://mlsanity.com/paper/2307.06644/) (2023)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Uniform Laws of Large Numbers in Product Spaces](https://mlsanity.com/paper/2603.24493/) (2026)
- [Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale](https://mlsanity.com/paper/2605.13684/) (2026)
- [The price of multi-group transductive learning](https://mlsanity.com/paper/2606.04423/) (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)

## Abstract (arXiv)

We present a new general-purpose algorithm for learning classes of [0,1]-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of this algorithm in terms of a scale-sensitive generalization of the Vapnik dimension proposed by Alon, Ben-David, Cesa-Bianchi and Haussler. We give lower bounds implying that our upper bounds cannot be improved by more than a constant factor in general. We apply this result, together with techniques due to Haussler and to Benedek and Itai, to obtain new upper bounds on packing numbers in terms of this scale-sensitive notion of dimension. Using a different technique, we obtain new bounds on packing numbers in terms of Kearns and Schapire's fat-shattering function. We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of agnostic learning. For each ε > 0, we establish weaker sufficient and stronger necessary conditions for a class of [0,1]-valued functions to be agnostically learnable to within ε, and to be an ε-uniform Glivenko-Cantelli class. This is a manuscript that was accepted by JCSS, together with a correction.