Optimal Online Discrepancy Minimization

We prove that there exists an online algorithm that for any sequence of vectors \(v_1,\ldots,v_T \in \mathbb{R}^n\) with \(\|v_i\|_2 \leq 1\), arriving one at a time, decides random signs \(x_1,\ldots,x_T \in \{ -1,1\}\) so that for every \(t \le T\), the prefix sum \(\sum_{i=1}^t x_iv_i\) is \(10\)...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-08
Main Authors: Kulkarni, Janardhan, Reis, Victor, Rothvoss, Thomas
Format: Article
Language:English
Subjects:
Algorithms
Cloning
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that there exists an online algorithm that for any sequence of vectors \(v_1,\ldots,v_T \in \mathbb{R}^n\) with \(\|v_i\|_2 \leq 1\), arriving one at a time, decides random signs \(x_1,\ldots,x_T \in \{ -1,1\}\) so that for every \(t \le T\), the prefix sum \(\sum_{i=1}^t x_iv_i\) is \(10\)-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums \(O(\sqrt{\log (nT)})\)-subgaussian, and gives a \(O(\sqrt{\log T})\) bound on the discrepancy \(\max_{t \in T} \|\sum_{i=1}^t x_i v_i\|_\infty\). Our proof combines a generalization of Banaszczyk's prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching \(\Omega(\sqrt{\log T})\) strategy for an oblivious adversary.
ISSN:2331-8422