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

09/02/2022
โˆ™
by   Monika Csikos, et al.
โˆ™
0
โˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset