# Monotone Learning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 10 Feb 2022.

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

- [The Shape of Learning Curves: a Review](https://mlsanity.com/paper/2103.10948/) (2021)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Risk-Monotonicity in Statistical Learning](https://mlsanity.com/paper/2011.14126/) (2020)
- [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, 9 of 9)

- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Delegated Classification](https://mlsanity.com/paper/2306.11475/) (2023)
- [Evaluating Self-Supervised Learning via Risk Decomposition](https://mlsanity.com/paper/2302.03068/) (2023)
- [Weight-Space Linear Recurrent Neural Networks](https://mlsanity.com/paper/2506.01153/) (2025)
- [On Learning-Curve Monotonicity for Maximum Likelihood Estimators](https://mlsanity.com/paper/2512.10220/) (2025)
- [A Survey of Learning Curves with Bad Behavior: or How More Data Need Not Lead to Better Performance](https://mlsanity.com/paper/2211.14061/) (2022)
- [Reevaluating Meta-Learning Optimization Algorithms Through Contextual Self-Modulation](https://mlsanity.com/paper/2410.01655/) (2024)
- [Monotonic Learning in the PAC Framework: A New Perspective](https://mlsanity.com/paper/2501.05493/) (2025)
- [Risk reversal for least squares estimators under nested convex constraints](https://mlsanity.com/paper/2601.16041/) (2026)

## Abstract (arXiv)

The amount of training-data is one of the key factors which determines the generalization capacity of learning algorithms. Intuitively, one expects the error rate to decrease as the amount of training-data increases. Perhaps surprisingly, natural attempts to formalize this intuition give rise to interesting and challenging mathematical questions. For example, in their classical book on pattern recognition, Devroye, Gyorfi, and Lugosi (1996) ask whether there exists a {monotone} Bayes-consistent algorithm. This question remained open for over 25 years, until recently Pestov (2021) resolved it for binary classification, using an intricate construction of a monotone Bayes-consistent algorithm. We derive a general result in multiclass classification, showing that every learning algorithm A can be transformed to a monotone one with similar performance. Further, the transformation is efficient and only uses a black-box oracle access to A. This demonstrates that one can provably avoid non-monotonic behaviour without compromising performance, thus answering questions asked by Devroye et al (1996), Viering, Mey, and Loog (2019), Viering and Loog (2021), and by Mhammedi (2021). Our transformation readily implies monotone learners in a variety of contexts: for example it extends Pestov's result to classification tasks with an arbitrary number of labels. This is in contrast with Pestov's work which is tailored to binary classification. In addition, we provide uniform bounds on the error of the monotone algorithm. This makes our transformation applicable in distribution-free settings. For example, in PAC learning it implies that every learnable class admits a monotone PAC learner. This resolves questions by Viering, Mey, and Loog (2019); Viering and Loog (2021); Mhammedi (2021).