Approximate Maximum Halfspace Discrepancy

Consider the geometric range space $(X,{\mathcal{H}}_d)$ where $X \subset $\mathbb{R}$^d$and$$\mathcal{H}$d$isthesetofrangesdefinedby$d$-dimensionalhalfspaces\mathrm{.}Inthissettingweconsiderthat$X$ is the disjoint union of a red and blue set. For each halfspace $h\in {\mathcal{H}}_d$ define a function $\mathrm{\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 \max{h \in (X, $\mathcal{H}$_d)} \Phi(h)$\mathrm{.}Weaimtoinsteadfindan$\hat{h}$suchthat$\Phi(h^*) - \Phi(\hat{h}) \le \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/\varepsilon^d) \log^4 (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 $\mathrm{\Phi }$ we can either provide a $\mathrm{\Omega }(\mathrm{\mid }X{\mathrm{\mid }}^{3\mathrm{/}2-o(1)})$ time lower bound for the exact solution with a reduction to APSP, or an $\mathrm{\Omega }(\mathrm{\mid }X\mathrm{\mid }+1\mathrm{/}{\epsilon }^{2-o(1)})$ lower bound for the approximate solution with a reduction to 3SUM. A key technical result is a $\epsilon$-approximate halfspace range counting data structure of size $O(1\mathrm{/}{\epsilon }^d)$ with $O(\log (1/\varepsilon))$querytime,whichwecanbuildin$O(|X| + (1/\varepsilon^d) \log^4 (1/\varepsilon))$ time.