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

Jane Lange, Arsen Vasilyan

Introduction

In the study of Boolean functions, monotonicity is a fundamental property: a function $f: \{-1, 1\}^n \to \{-1, 1\}$ is monotone if flipping an input bit from -1 to 1 never decreases the output value. Learning these functions is a cornerstone of computational learning theory, yet achieving "proper" learning—where the hypothesis produced is itself monotone—has historically faced significant theoretical hurdles.

This paper addresses the challenge of agnostic proper learning. In the agnostic setting, we are given examples of an arbitrary function $f$ and must find a monotone hypothesis $g$ that is nearly as close to $f$ as the best possible monotone function. Specifically, if $opt$ is the distance between $f$ and the closest monotone function, we seek a hypothesis with an error rate of $opt + \epsilon$. While "improper" learners (which can output non-monotone functions) have long been efficient, proper learners were previously stuck at a "black-box correction barrier," limiting their error to $2 \cdot opt + \epsilon$. This work provides the first efficient algorithm to break this barrier, achieving the gold standard of $opt + \epsilon$.

The Black-Box Correction Barrier

Traditional approaches to proper learning often followed a "learn then correct" pipeline. An algorithm would first learn a non-monotone hypothesis and then apply a black-box correction procedure to force monotonicity. However, information-theoretic limits on Boolean labels meant that any such correction could, at best, guarantee an error of $2 \cdot opt$. To surpass this, the authors propose a fundamental shift: performing the correction process on real-valued functions rather than Boolean labels.

Methodology

The authors introduce a three-stage framework that operates primarily in the real-valued domain $[-1, 1]$ to preserve information that is typically lost during early rounding.

1. Convex Optimization via the Ellipsoid Method

The problem of finding a suitable predictor is framed as a convex feasibility problem. The algorithm searches for a low-degree, real-valued polynomial $P$ that is simultaneously close to the target function $f$ and close to some monotone function. To navigate this search space efficiently, the authors designed a separation oracle. This oracle utilizes a "high-weight matching" of violated pairs—points in the hypercube where the monotonicity constraint is failed—to generate hyperplanes that guide the Ellipsoid Method toward a valid solution.

2. Real-Valued Monotonicity Correction

Once a candidate polynomial $P$ is found, it must be made strictly monotone. The authors developed a new Local Computation Algorithm (LCA) for real-valued functions. This extends previous "poset sorting" techniques, which were restricted to Boolean values. By correcting the function bit-by-bit (from most significant to least significant) while updating the underlying partial order (poset), the LCA can evaluate the corrected function $P_{CORRECTED}$ at any point $x$ without needing to compute the entire truth table, which would be exponentially large ($2^n$).

3. Monotone Rounding

The final step involves rounding the corrected real-valued function back to the Boolean domain $\{-1, 1\}$. The authors employ a specific rounding procedure designed to preserve the monotonicity established in the previous step, ensuring the final hypothesis is both proper and accurate.

Theoretical Results

The algorithm achieves a distance of $opt + O(\epsilon)$ from the target function, matching the best possible theoretical performance for agnostic learning.

Efficiency and Complexity: * Sample Complexity: $2^{\tilde{O}(\sqrt{n}/\epsilon)}$ * Runtime: $2^{\tilde{O}(\sqrt{n}/\epsilon)}$

This represents a massive improvement over previous proper learners that required $2^{\Omega(n)}$ time. Furthermore, the runtime nearly matches the known lower bound of $2^{\tilde{\Omega}(\sqrt{n})}$, suggesting that the algorithm is near-optimal in its efficiency. Additionally, the paper provides a distance estimator that can approximate how far an unknown function is from being monotone within an additive error $\epsilon$ in the same time complexity.

Conclusion and Future Work

By moving the monotonicity correction process into the real-valued domain, this work successfully bypasses the $2 \cdot opt$ barrier that has limited proper learning for years. While the $2^{\sqrt{n}}$ complexity is a landmark result in Boolean function analysis, it remains computationally intensive for high-dimensional practical applications.

Future research may focus on extending these "proper" guarantees beyond the uniform distribution to more general product distributions. Additionally, while the main learning result uses random samples, parts of the distance estimation still require query access; reducing this dependency remains an open challenge in the field.

Summary updated

Abstract

We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given $2^{\tilde{O}(\sqrt{n}/\varepsilon)}$ uniformly random examples of an unknown function $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$, our algorithm outputs a hypothesis $g:\{\pm 1\}^n \rightarrow \{\pm 1\}$ that is monotone and $(\mathrm{opt} + \varepsilon)$-close to $f$, where $\mathrm{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^{\tilde{O}(\sqrt{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^{\tilde{O}(\sqrt{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 $2\mathrm{opt} + \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.
BibTeX
@article{lange2026agnostic,
  author = {Jane Lange and Arsen Vasilyan},
  title = {{Agnostic proper learning of monotone functions: beyond the black-box correction barrier}},
  journal = {SIAM Journal on Computing},
  year = {2026},
  doi = {10.1137/24m1630463},
}

Loading related content...

Figure