# Properly learning monotone functions via local reconstruction

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2022.

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

- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [On Exact Learning of d-Monotone Functions](https://mlsanity.com/paper/2502.01265/) (2025)
- [Monotone Classification with Relative Approximations](https://mlsanity.com/paper/2506.10775/) (2025)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## Abstract (arXiv)

We give a 2^tildeO(√n/ε)-time algorithm for properly learning monotone Boolean functions under the uniform distribution over 0,1n. Our algorithm is robust to adversarial label noise and has a running time nearly matching that of the state-of-the-art improper learning algorithm of Bshouty and Tamon (JACM '96) and an information-theoretic lower bound of Blais et al (RANDOM '15). Prior to this work, no proper learning algorithm with running time smaller than 2Omega(n) was known to exist. The core of our proper learner is a local computation algorithm for sorting binary labels on a poset. Our algorithm is built on a body of work on distributed greedy graph algorithms; specifically we rely on a recent work of Ghaffari (FOCS'22), which gives an efficient algorithm for computing maximal matchings in a graph in the LCA model of Rubinfeld et al and Alon et al (ICS'11, SODA'12). The applications of our local sorting algorithm extend beyond learning on the Boolean cube: we also give a tolerant tester for Boolean functions over general posets that distinguishes functions that are ε/3-close to monotone from those that are ε-far. Previous tolerant testers for the Boolean cube only distinguished between ε/Omega(√n)-close and ε-far.