# Approximate Maximum Halfspace Discrepancy

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 41 references that are in the map.
- First posted on arXiv 25 Jun 2021.

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

- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Statistical Queries and Statistical Algorithms: Foundations and Applications](https://mlsanity.com/paper/2004.00557/) (2020)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2006.06467/) (2020)
- [Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability](https://mlsanity.com/paper/2006.04787/) (2020)
- [Tight Hardness Results for Maximum Weight Rectangles](https://mlsanity.com/paper/1602.05837/) (2016)
- [Computing Approximate Statistical Discrepancy](https://mlsanity.com/paper/1804.11287/) (2018)
- [Practical Low-Dimensional Halfspace Range Space Sampling](https://mlsanity.com/paper/1804.11307/) (2018)
- [Higher Lower Bounds from the 3SUM Conjecture](https://mlsanity.com/paper/1407.6756/) (2014)
- [Approximate Range Counting Revisited](https://mlsanity.com/paper/1512.01713/) (2015)

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

- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Fast Agnostic Learners in the Plane](https://mlsanity.com/paper/2510.18057/) (2025)

## Abstract (arXiv)

Consider the geometric range space (X, Hd) where X subset ℝd and Hd is the set of ranges defined by d-dimensional halfspaces. In this setting we consider that X is the disjoint union of a red and blue set. For each halfspace h ∈ Hd define a function Phi(h) that measures the "difference" between the fraction of red and fraction of blue points which fall in the range h. In this context the maximum discrepancy problem is to find the h^* = arg maxh ∈ (X, Hd) Phi(h). We aim to instead find an hath such that Phi(h^*) - Phi(hath) ≤ varepsilon. This is the central problem in linear classification for machine learning, in spatial scan statistics for spatial anomaly detection, and shows up in many other areas. We provide a solution for this problem in O(|X| + (1/varepsilond) log4 (1/varepsilon)) time, which improves polynomially over the previous best solutions. For d=2 we show that this is nearly tight through conditional lower bounds. For different classes of Phi we can either provide a Omega(|X|3/2 - o(1)) time lower bound for the exact solution with a reduction to APSP, or an Omega(|X| + 1/varepsilon2-o(1)) lower bound for the approximate solution with a reduction to 3SUM. A key technical result is a varepsilon-approximate halfspace range counting data structure of size O(1/varepsilond) with O(log (1/varepsilon)) query time, which we can build in O(|X| + (1/varepsilond) log4 (1/varepsilon)) time.