# Monotonic Learning in the PAC Framework: A New Perspective

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 9 Jan 2025.

## Builds on (most cited first, 10 of 10)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [The Shape of Learning Curves: a Review](https://mlsanity.com/paper/2103.10948/) (2021)
- [Introducing Geometry in Active Learning for Image Segmentation](https://mlsanity.com/paper/1508.04955/) (2015)
- [Minimizers of the Empirical Risk and Risk Monotonicity](https://mlsanity.com/paper/1907.05476/) (2019)
- [Risk-Monotonicity in Statistical Learning](https://mlsanity.com/paper/2011.14126/) (2020)
- [Monotone Learning](https://mlsanity.com/paper/2202.05246/) (2022)
- [Making Learners (More) Monotone](https://mlsanity.com/paper/1911.11030/) (2019)
- [A universally consistent learning rule with a universally monotone error](https://mlsanity.com/paper/2108.09733/) (2021)

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

- [Monotone and Separable Set Functions: Characterizations and Neural Models](https://mlsanity.com/paper/2510.23634/) (2025)

## Abstract (arXiv)

Monotone learning describes learning processes in which expected performance consistently improves as the amount of training data increases. However, recent studies challenge this conventional wisdom, revealing significant gaps in the understanding of generalization in machine learning. Addressing these gaps is crucial for advancing the theoretical foundations of the field. In this work, we utilize Probably Approximately Correct (PAC) learning theory to construct a theoretical risk distribution that approximates a learning algorithm's actual performance. We rigorously prove that this theoretical distribution exhibits monotonicity as sample sizes increase. We identify two scenarios under which deterministic algorithms based on Empirical Risk Minimization (ERM) are monotone: (1) the hypothesis space is finite, or (2) the hypothesis space has finite VC-dimension. Experiments on two classical learning problems validate our findings by demonstrating that the monotonicity of the algorithms' generalization error is guaranteed, as its theoretical risk upper bound monotonically converges to 0.