Research
Monotone Classification with Relative Approximations
arXiv:2506.10775v3 Announce Type: replace Abstract: In monotone classification, the input is a multi-set P of points in R^d, each associated with a hidden label from {-1, 1}. The goal is to identify a
arXiv:2506.10775v3 Announce Type: replace Abstract: In monotone classification, the input is a multi-set P of points in R^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 R^d to {-1, 1} with a small {em error}, measured as the number of points p in 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 + epsilon) dot k^* where epsilon ge 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 epsilon. All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.
Related
Source: arXiv cs.LG | 2026-08-19