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,๐ฎ), the discrepancy of a two-coloring ฯ:Xโ{-1,1} is defined as max_S โ๐ฎ|ฯ(S)|, where ฯ(S)=โ_x โ Sฯ(x). We propose a randomized algorithm which, for any d>0 and (X,๐ฎ) with dual shatter function ฯ^*(k)=O(k^d), returns a coloring with expected discrepancy O(โ(|X|^1-1/dlog|๐ฎ|)) (this bound is tight) in time ร(|๐ฎ|ยท|X|^1/d+|X|^2+1/d), improving upon the previous-best time of O(|๐ฎ|ยท|X|^3) by at least a factor of |X|^2-1/d when |๐ฎ|โฅ|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 ฮต-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 O(|X|^1-1/d), 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.
READ FULL TEXT