# Monotone Classification with Relative Approximations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 55 references that are in the map.
- First posted on arXiv 12 Jun 2025.

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

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [A Comprehensive Benchmark Framework for Active Learning Methods in Entity Matching](https://mlsanity.com/paper/2003.13114/) (2020)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [Properly learning monotone functions via local reconstruction](https://mlsanity.com/paper/2204.11894/) (2022)
- [Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curves](https://mlsanity.com/paper/1907.06969/) (2019)
- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [An optimal lower bound for monotonicity testing over hypergrids](https://mlsanity.com/paper/1304.5264/) (2013)
- [Relative-error monotonicity testing](https://mlsanity.com/paper/2410.09235/) (2024)

## Abstract (arXiv)

In monotone classification, the input is a multi-set P of points in ℝd, each associated with a hidden label from -1, 1. The goal is to identify a monotone function h, which acts as a classifier, mapping from ℝd to -1, 1 with a small em error, measured as the number of points p ∈ P whose labels differ from the function values h(p). The cost of an algorithm is defined as the number of points having their labels revealed. This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most (1 + ε) · k^* where ε ≥ 0 and k^* is the minimum error achieved by an optimal monotone classifier -- in other words, the error is allowed to exceed the optimal by at most a relative factor. Nearly matching upper and lower bounds are presented for the full range of ε. All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.