Optimal Online Discrepancy Minimization in Linear Time
We provide an online algorithm with the following guarantee: for any fixed sequence of vectors $v_1,\dots,v_T \in \mathbf{R}^d$ with $\|v_i\|_2\le 1$, the algorithm assigns each arriving vector $v_t$ a random sign $\varepsilon_t$ such that every prefix sum $\sum_{i=1}^t \varepsilon_i v_i $ can be wr...
-д хадгалсан:
| Үндсэн зохиолч: | |
|---|---|
| Формат: | Өгүүллэг |
| Хэвлэсэн: |
2026
|
| Нөхцлүүд: | |
| Онлайн хандалт: | https://arxiv.org/abs/2607.04388 http://arxiv.org/abs/2607.04388 |
| Шошгууд: |
Шошго байхгүй, Энэхүү баримтыг шошголох эхний хүн болох!
|