2023-09-13
The set discrepancy problem's solution is a basic tool for data approximation and optimization. Work by Lovett and Meka and its deterministic counterpart developed by Levy et al. solve this problem for general set systems. Building on these work, we provide random algorithms computing optimal discrepancy for set systems of VC-dimension \(\le d\) by using properties of the packings and coverings of such set systems. We give a generic algorithm with expected runtime \(\tilde{O}(md^2n^{1/d}+n^3\log^{3d}(n))\) where \(n\) is the number of elements and \(m\) the number of sets of the set system. This improves on \(\tilde{O}\left((n+m)^3\right)\) and \(\tilde{O}(n^4m)\) from respectively Lovett and Meka and Levy et al.. We obtain this result via the use of \(\delta\)-coverings which we provide algorithms to compute. Our main algorithm computes near-minimal \(\delta\)-coverings in time \(\tilde{O}\left(\frac{mnd^2}{\delta} + \left(\frac{nd}{\delta}\right)^{2d+2}\log\left(\frac{nd}{\delta}\right)\right)\). We also give a faster algorithms for geometric sets systems such as thy spanned by halfspaces or balls.
Undergoing revisions