# Agnostic proper learning of monotone functions: beyond the black-box correction barrier

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 59 references that are in the map.
- First posted on arXiv 5 Apr 2023.

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

- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Properly learning monotone functions via local reconstruction](https://mlsanity.com/paper/2204.11894/) (2022)
- [An Improved Distributed Algorithm for Maximal Independent Set](https://mlsanity.com/paper/1506.05093/) (2015)
- [Approximating the Distance to Monotonicity of Boolean Functions](https://mlsanity.com/paper/1911.06924/) (2019)
- [Local Computation Algorithms for Graphs of Non-Constant Degrees](https://mlsanity.com/paper/1502.04022/) (2015)
- [Testing k-Monotonicity](https://mlsanity.com/paper/1609.00265/) (2016)
- [A o(d) · polylog~n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d](https://mlsanity.com/paper/1710.10545/) (2017)
- [Local Algorithms for Sparse Spanning Graphs](https://mlsanity.com/paper/1402.3609/) (2014)
- [Best of Two Local Models: Local Centralized and Local Distributed Algorithms](https://mlsanity.com/paper/1402.3796/) (2014)
- [New Techniques and Tighter Bounds for Local Computation Algorithms](https://mlsanity.com/paper/1404.5398/) (2014)
- [A Polynomial Lower Bound for Testing Monotonicity](https://mlsanity.com/paper/1511.05053/) (2015)
- [Non-Local Probes Do Not Help with Graph Problems](https://mlsanity.com/paper/1512.05411/) (2015)
- [Sublinear Random Access Generators for Preferential Attachment Graphs](https://mlsanity.com/paper/1602.06159/) (2016)
- [Adaptive Boolean Monotonicity Testing in Total Influence Time](https://mlsanity.com/paper/1801.02816/) (2018)
- [Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation](https://mlsanity.com/paper/1807.06251/) (2018)
- [The Complexity of (Delta + 1)Coloring inCongested Clique, Massively Parallel Computation,and Centralized Local Computation](https://mlsanity.com/paper/1808.08419/) (2018)
- [Local Computation Algorithms for Spanners](https://mlsanity.com/paper/1902.08266/) (2019)
- [Testing Unateness Nearly Optimally](https://mlsanity.com/paper/1904.05309/) (2019)
- [Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics](https://mlsanity.com/paper/2103.14112/) (2021)
- [The randomized local computation complexity of the Lov'asz local lemma](https://mlsanity.com/paper/2103.16251/) (2021)
- [Local Computation of Maximal Independent Set](https://mlsanity.com/paper/2210.01104/) (2022)

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

- [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 the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given 2^tildeO(√n/varepsilon) uniformly random examples of an unknown function f:± 1n rightarrow ± 1, our algorithm outputs a hypothesis g:± 1n rightarrow ± 1 that is monotone and (opt + varepsilon)-close to f, where opt is the distance from f to the closest monotone function. The running time of the algorithm (and consequently the size and evaluation time of the hypothesis) is also 2^tildeO(√n/varepsilon), nearly matching the lower bound of Blais et al (RANDOM '15). We also give an algorithm for estimating up to additive error varepsilon the distance of an unknown function f to monotone using a run-time of 2^tildeO(√n/varepsilon). Previously, for both of these problems, sample-efficient algorithms were known, but these algorithms were not run-time efficient. Our work thus closes this gap in our knowledge between the run-time and sample complexity. This work builds upon the improper learning algorithm of Bshouty and Tamon (JACM '96) and the proper semiagnostic learning algorithm of Lange, Rubinfeld, and Vasilyan (FOCS '22), which obtains a non-monotone Boolean-valued hypothesis, then ``corrects'' it to monotone using query-efficient local computation algorithms on graphs. This black-box correction approach can achieve no error better than 2opt + varepsilon information-theoretically; we bypass this barrier by a) augmenting the improper learner with a convex optimization step, and b) learning and correcting a real-valued function before rounding its values to Boolean. Our real-valued correction algorithm solves the ``poset sorting'' problem of [LRV22] for functions over general posets with non-Boolean labels.