Online balancing of vectors with small coordinates

Abstract

Let $v_1,\dots ,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\Vert v_t{\Vert }_{\infty }⩽d^{-1/2}$ for some $d⩾1$ and every $1⩽t⩽T$. There are absolute constants $L,C,c>0$ and a randomized online signing such that $$\mathbb{P}\left\{\underset{k⩽T}{\max }{\Vert \sum _{t=1}^k{\epsilon }_t{v}_t\Vert }_{\infty }>6L\right\}⩽CT\exp \left(-\frac{cd}{{\ln }^2(ed)}\right).$$ Consequently, constant prefix discrepancy holds with probability at least $1-\epsilon$ once $d$ is at least $C\ln \frac{3T}{\epsilon }{\left[\ln \left(e+\ln \frac{3T}{\epsilon }\right)\right]}^2$. In particular, every fixed sequence of vectors $a_t\in [-1,1{]}^m$ with at most $d$ nonzero coordinates admits an online signing with prefix discrepancy $O(\sqrt{d})$ and failure probability at most $CT\exp [-cd/{\ln }^2(ed)]$. We also prove a nonuniform version in which the failure probability depends on the individual parameters $d_t=\Vert v_t{\Vert }_{\infty }^{-2}$, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$. We identify the corresponding ${\ln }^{2}d$ barrier for the compact-potential method and extend the argument to general symmetric target bodies admitting a quadratic smoothness estimate.