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$-subgaussian...
Tallennettuna:
| Päätekijät: | , , |
|---|---|
| Aineistotyyppi: | Artikkeli |
| Julkaistu: |
2023
|
| Aiheet: | |
| Linkit: | https://arxiv.org/abs/2308.01406 http://arxiv.org/abs/2308.01406 |
| Tagit: |
Ei tageja, Lisää ensimmäinen tagi!
|