TCS+ Talk

Abstract: We consider an online vector balancing question where T vectors, chosen from an arbitrary distribution over [-1,1]^n, arrive one-by-one and must be immediately given a {+1,-1} sign. The goal is to keep the discrepancy---the \ell_{\infty}-norm of any signed prefix-sum---as small as possible. A concrete example of this question is the online interval discrepancy problem where T points are sampled one-by-one uniformly in the unit interval [0,1], and the goal is to immediately color them {+1,-1} such that every sub-interval remains always nearly balanced. As random coloring incurs \Omega(T^{1/2}) discrepancy, while the worst-case offline bounds are \Theta(\sqrt{n \log (T/n)}) for vector balancing and 1 for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is \Omega(T^{1/2}) for any online algorithm.

In this work, we introduce a new framework that allows us to handle online vector balancing even when the input distribution has dependencies across coordinates. In particular, this lets us obtain a \poly(n, \log T) bound for online vector balancing under arbitrary input distributions, and a \polylog (T) bound for online interval discrepancy. Our framework is powerful enough to capture other well-studied geometric discrepancy problems; e.g., we obtain a \poly(\log^d (T)) bound for the online d-dimensional Tusnády's problem. All our bounds are tight up to polynomial factors.

A key new technical ingredient in our work is an anti-concentration inequality for sums of pairwise uncorrelated random variables, which might also be of independent interest.

Based on joint works with Nikhil Bansal, Haotian Jiang, Janardhan Kulkarni, and Makrand Sinha. Part of this work appears in STOC 2020 and is available at https://arxiv.org/abs/1912.03350

To watch the talk:

• Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
• Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)