2025/06/12 by Yufei Tao, Tao, Yufei
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2506.10775
openalex publication_date 2025/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.