Online Banaszczyk conjecture for online vector balancing

About 5 years old · traced to

Let v1,…,vT∈Rmv_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

max⁡t∈[T]∥∑s=1tσsvs∥∞≲log⁡(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.