# Fast Agnostic Learners in the Plane

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 20 Oct 2025.

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

- [Computing Approximate Statistical Discrepancy](https://mlsanity.com/paper/1804.11287/) (2018)
- [Dynamic Planar Convex Hull](https://mlsanity.com/paper/1902.11169/) (2019)
- [Approximating the Distance to Monotonicity of Boolean Functions](https://mlsanity.com/paper/1911.06924/) (2019)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Computational Complexity in Property Testing](https://mlsanity.com/paper/2510.05927/) (2025)
- [Testing Connectedness of Images](https://mlsanity.com/paper/2312.03681/) (2023)

## Abstract (arXiv)

We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is well understood, its time complexity has received much less attention. We study the class of triangles and, more generally, the class of convex polygons with k vertices for small k, as well as the class of convex sets in a square. We present a proper agnostic learner for the class of triangles that has optimal sample complexity and runs in time tilde O(ε-6), improving on the algorithm of Dobkin and Gunopulos (COLT `95) that runs in time tilde O(ε-10). For 4-gons and 5-gons, we improve the running time from O(ε-12), achieved by Fischer and Kwek (eCOLT `96), to tilde O(ε-8) and tilde O(ε-10), respectively. We also design a proper agnostic learner for convex sets under the uniform distribution over a square with running time tilde O(ε-5), improving on the previous tilde O(ε-8) bound at the cost of slightly higher sample complexity. Notably, agnostic learning of convex sets in [0,1]2 under general distributions is impossible because this concept class has infinite VC-dimension. Our agnostic learners use data structures and algorithms from computational geometry and their analysis relies on tools from geometry and probabilistic combinatorics. Because our learners are proper, they yield tolerant property testers with matching running times. Our results raise a fundamental question of whether a gap between the sample and time complexity is inherent for agnostic learning of these and other natural concept classes.