# A universally consistent learning rule with a universally monotone error

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 15 references that are in the map.
- First posted on arXiv 22 Aug 2021.

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

- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)

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

- [Monotone Learning](https://mlsanity.com/paper/2202.05246/) (2022)
- [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)
- [Monotonic Learning in the PAC Framework: A New Perspective](https://mlsanity.com/paper/2501.05493/) (2025)

## Abstract (arXiv)

We present a universally consistent learning rule whose expected error is monotone non-increasing with the sample size under every data distribution. The question of existence of such rules was brought up in 1996 by Devroye, Gy"orfi and Lugosi (who called them "smart"). Our rule is fully deterministic, a data-dependent partitioning rule constructed in an arbitrary domain (a standard Borel space) using a cyclic order. The central idea is to only partition at each step those cyclic intervals that exhibit a sufficient empirical diversity of labels, thus avoiding a region where the error function is convex.