# Computing Approximate Statistical Discrepancy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2018.

## Built on by (most cited first, 5 of 5)

- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)
- [Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance](https://mlsanity.com/paper/2504.11299/) (2025)
- [Fast Agnostic Learners in the Plane](https://mlsanity.com/paper/2510.18057/) (2025)

## Abstract (arXiv)

Consider a geometric range space (X,cA) where each data point x ∈ X has two or more values (say r(x) and b(x)). Also consider a function Phi(A) defined on any subset A ∈ (X,cA) on the sum of values in that range e.g., rA = sumx ∈ A r(x) and bA = sumx ∈ A b(x). The Phi-maximum range is A^* = arg max_A ∈ (X,cA) Phi(A). Our goal is to find some hatA such that |Phi(hatA) - Phi(A^*)| ≤ varepsilon. We develop algorithms for this problem for range spaces with bounded VC-dimension, as well as significant improvements for those defined by balls, halfspaces, and axis-aligned rectangles. This problem has many applications in many areas including discrepancy evaluation, classification, and spatial scan statistics.