NYU CG Seminar, 10/8/24.
Consider a geometric range space (X,S) for a point set X⊂R^d and geometrically defined ranges scriptS induced by containment in certain shapes such as disks, rectangles, or halfspaces. Let X be the union of two sets colored red R or blue B. The discrepancy maximization problem seeks to find shape S∈scriptS which maximizes the discrepancy ϕ(S)=|(|R∩S|/|R|)−(| B∩S|/|B|)|. We solve the ε-approximate version of this problem, where we seek some S-hat such that ϕ(S∗)−ϕ(S-hat)≤ε, where S∗ is the range achieving the maximum discrepancy.
Our solution is via a two-level coreset construction, where we approximate the space of ranges scriptS with one coreset, and the ground set X with another. We generalize this method towards an algorithm for approximately computing a class of distances between probability distributions (in this case point sets like R and B) referred to as Integral Probability Measures (IPMs). This leads to implications in spatial anomaly detection (as spatial scan statistics), machine learning (as linear classifiers), and statistics (in Kolmogorov-Smirnov distances), and more. In some cases the results are optimal given conditional hardness assumptions. Moreover, the algorithms might even be practical, scalable, and statistically powerful.