A universally consistent learning rule with a universally monotone error
This solves a foundational theoretical problem in machine learning, providing a universally monotone learning rule as conjectured decades ago, which is incremental but addresses a long-standing open question.
The authors tackled the problem of constructing a universally consistent learning rule with a universally monotone error, proving its existence by presenting a deterministic, data-dependent partitioning rule that ensures expected error is non-increasing with sample size for all data distributions.
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örfi 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.