Constructive Discrepancy Minimization with Hereditary L2 Guarantees

In discrepancy minimization problems, we are given a family of sets $\mathcal{S}=\{S_1,\dots ,S_m\}$, with each $S_i\in \mathcal{S}$ a subset of some universe $U=\{u_1,\dots ,u_n\}$ of $n$ elements. The goal is to find a coloring $\chi :U\to \{-1,+1\}$ of the elements of $U$ such that each set $S \in $\mathcal{S}$$ is colored as evenly as possible. Two classic measures of discrepancy are ${\mathrm{\ell }}_{\mathrm{\infty }}$-discrepancy defined as $$\text{disc}$\infty($\mathcal{S}$,\chi):=\max{S \in $\mathcal{S}$} | \sum_{u_i \in S} \chi(u_i) |$and$\ell_2$-discrepancydefinedas$$\text{disc}$2($\mathcal{S}$,\chi):=\sqrt{(1/|$\mathcal{S}$|)\sum{S \in $\mathcal{S}$} \left(\sum_{u_i \in S}\chi(u_i)\right)^2}$. Breakthrough work by Bansal gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring $\chi$ such that $$\text{disc}$\infty($\mathcal{S}$,\chi) = O(\lg n \cdot $\text{herdisc}$\infty($\mathcal{S}$))$where$$\text{herdisc}$\infty($\mathcal{S}$)$isthehereditary$\ell\infty$-discrepancyof$$\mathcal{S}$$. We complement his work by giving a simple $O((m+n)n^2)$ time algorithm for finding a coloring $\chi$ such $$\text{disc}$_2($\mathcal{S}$,\chi) = O(\sqrt{\lg n} \cdot $\text{herdisc}$_2($\mathcal{S}$))$where$$\text{herdisc}$_2($\mathcal{S}$)$ is the hereditary ${\mathrm{\ell }}_2$-discrepancy of $\mathcal{S}$. Interestingly, our algorithm avoids solving an SDP and instead relies on computing eigendecompositions of matrices. Moreover, we use our ideas to speed up the Edge-Walk algorithm by Lovett and Meka [SICOMP’15]. To prove that our algorithm has the claimed guarantees, we show new inequalities relating ${\text{herdisc}}_{\mathrm{\infty }}$ and ${\text{herdisc}}_2$ to the eigenvalues of the matrix corresponding to $\mathcal{S}$. Our inequalities improve over previous work by Chazelle and Lvov, and by Matousek et al. Finally, we also implement our algorithm and show that it far outperforms random sampling.