Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical

We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system (X,mathcal S), the discrepancy of a two-coloring chi:X→-1,1 is defined as maxS ∈ mathcal S|chi(S)|, where chi(S)=sumlimitsx ∈ Schi(x). We propose a randomized algorithm which, for any d>0 and (X,mathcal S) with dual shatter function π^*(k)=O(kd), returns a coloring with expected discrepancy Oleft(√|X|1-1/dlog|mathcal S|right) (this bound is tight) in time tilde Oleft(|mathcal S|·|X|1/d+|X|2+1/dright), improving upon the previous-best time of Oleft(|mathcal S|·|X|3right) by at least a factor of |X|2-1/d when |mathcal S|≥|X|. This setup includes many geometric classes, families of bounded dual VC-dimension, and others. As an immediate consequence, we obtain an improved algorithm to construct varepsilon-approximations of sub-quadratic size. Our method uses primal-dual reweighing with an improved analysis of randomly updated weights and exploits the structural properties of the set system via matchings with low crossing number -- a fundamental structure in computational geometry. In particular, we get the same |X|2-1/d factor speed-up on the construction time of matchings with crossing number Oleft(|X|1-1/dright), which is the first improvement since the 1980s. The proposed algorithms are very simple, which makes it possible, for the first time, to compute colorings with near-optimal discrepancies and near-optimal sized approximations for abstract and geometric set systems in dimensions higher than 2.