Monotone Classification with Relative Approximations
Not on the map. Why?
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.
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
13 of 55 references.
References · 13
- 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
- 2018On Coresets for Logistic Regressioncited by 67
- 2016Coresets and Sketchescited by 63
- 2014Minimax Analysis of Active Learningcited by 61
- 2021Coresets for Classification -- Simplified and Strengthenedcited by 28
- 2020A Comprehensive Benchmark Framework for Active Learning Methods in Entity Matchingcited by 17
- 2018Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and morecited by 14
- 2022Properly learning monotone functions via local reconstructioncited by 6
- 2019Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curvescited by 5
- 2023Agnostic proper learning of monotone functions: beyond the black-box correction barriercited by 4
- 2024No Dimensional Sampling Coresets for Classificationcited by 4
- 2013An optimal lower bound for monotonicity testing over hypergridscited by 2
1 more
- 2024Relative-error monotonicity testingcited by 1
Built on by
Not cited yet.