## Abstract

In the stochastic online vector balancing problem, vectors v1, v2,..., v_{T} chosen independently from an arbitrary distribution in R^{n} arrive one-by-one and must be immediately given a ± sign. The goal is to keep the norm of the discrepancy vector, i.e., the signed prefix-sum, as small as possible for a given target norm. We consider some of the most well-known problems in discrepancy theory in the above online stochastic setting, and give algorithms that match the known offline bounds up to polylog(nT) factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC' 20). In particular, for the Komlós problem where kvtk2 ≤ 1 for each t, our algorithm achieves O^{e}(1) discrepancy with high probability, improving upon the previous O^{e}(n^{3}/^{2}) bound. For Tusnády's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an O(log^{d}^{+4} T) bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker O(log^{2}d^{+1} T) bound. We also consider the Banaszczyk setting, where given a symmetric convex body K with Gaussian measure at least 1/2, our algorithm achieves O^{e}(1) discrepancy with respect to the norm given by K for input distributions with sub-exponential tails. Our results are based on a new potential function approach. Previous techniques consider a potential that penalizes large discrepancy, and greedily chooses the next color to minimize the increase in potential. Our key idea is to introduce a potential that also enforces constraints on how the discrepancy vector evolves, allowing us to maintain certain anti-concentration properties. We believe that our techniques to control the evolution of states could find other applications in stochastic processes and online algorithms. For the Banaszczyk setting, we further enhance this potential by combining it with ideas from generic chaining. Finally, we also extend these results to the setting of online multicolor discrepancy.

Original language | English |
---|---|

Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |

Editors | Daniel Marx |

Publisher | Association for Computing Machinery, Inc |

Pages | 2842-2861 |

Number of pages | 20 |

ISBN (Electronic) | 9781611976465 |

Publication status | Published - 2021 |

Event | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States Duration: 10 Jan 2021 → 13 Jan 2021 |

### Conference

Conference | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
---|---|

Country/Territory | United States |

City | Alexandria, Virtual |

Period | 10/01/21 → 13/01/21 |

### Bibliographical note

Publisher Copyright:© 2021 by SIAM