Online Banaszczyk conjecture for online vector balancing

From papers

Let v1,,vTRmv_1,\ldots,v_T\in\mathbb{R}^m be a sequence of vectors with Euclidean norm at most 11. In the oblivious adversarial online setting, the algorithm receives vtv_t at time tt and outputs a sign σt{±1}\sigma_t\in\{\pm1\}. Online Banaszczyk conjecture. There exists a randomized algorithm that, with high probability, achieves

maxt[T]s=1tσsvslog(mT).\max_{t\in[T]}\left\lVert\sum_{s=1}^t\sigma_s v_s\right\rVert_\infty\lesssim\sqrt{\log(mT)}.

This conjecture asks for an online analogue of Banaszczyk's discrepancy bound. The source attributes it to Alweiss, and presents it as an open conjecture concerning efficient online balancing against an oblivious adversary.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Sinho Chewi, Patrik Gerber, Philippe Rigollet and Paxton Turner, “Gaussian discrepancy: a probabilistic relaxation of vector balancing”, arXiv:2109.08280 (2022).

Solutions 0

No solutions have been posted yet.