Online vector balancing and geometric discrepancy
Online vector balancing and geometric discrepancy
复制标题
在线矢量平衡和几何差异
DOI：
10.1145/3357713.3384280
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Makrand Sinha
中科院分区：
文献类型：
--
作者：
N. Bansal;Haotian Jiang;Sahil Singla;Makrand Sinha
我们考虑一个在线向量平衡问题，其中T个向量从[-1，1] n上的任意分布中选择，一个接一个地到达，并且必须立即给出±符号。我们的目标是保持差异-任何有符号前缀和的范数-尽可能小。这个问题的一个具体例子是在线区间差异问题，其中T个点在单位区间[0，1]中一个接一个地均匀采样，目标是立即对它们进行±着色，使得每个子区间始终保持接近平衡。由于随机着色会导致Ω（T 1/2）差异，而最坏情况下的离线边界对于向量平衡是Θ（log（T/n）），对于区间平衡是1，一个自然的问题是是否可以（几乎）匹配这些问题的在线设置中的离线边界。必须利用随机性，因为在最坏的情况下，已知任何在线算法的差异都是Ω（T1/2）。在在线向量平衡的特殊情况下，Bansal和Spencer [BS 19]最近显示了当每个坐标独立选择时的O（lognlogT）界。当坐标之间存在依赖关系时，如在间隔差异问题中，该问题变得更具挑战性，正如Jiang，Kulkarni和Singla [JKS 19]最近的工作所证明的那样，该工作给出了在线间隔差异的非平凡O（T 1/loglogT）界。虽然这比随机着色好，但离离线边界还很远。在这项工作中，我们引入了一个新的框架，使我们能够处理在线矢量平衡，即使当输入分布具有跨坐标的依赖关系。特别是，这让我们得到一个poly（n，logT）界在线向量平衡任意输入分布下，和一个polylog（T）界在线间隔差异。我们的框架足够强大，可以捕获其他经过充分研究的几何差异问题;例如，我们得到了在线d维Tusnády问题的一个poly（log d（T））界。我们所有的边界都紧到多项式因子。在我们的工作中，一个关键的新技术成分是成对不相关随机变量之和的反集中不等式，这也可能是独立的利益。
We consider an online vector balancing question where T vectors, chosen from an arbitrary distribution over [−1,1] n , arrive one-by-one and must be immediately given a ± sign. The goal is to keep the discrepancy—the ℓ∞-norm of any signed prefix-sum—as small as possible. A concrete example of this question is the online interval discrepancy problem where T points are sampled one-by-one uniformly in the unit interval [0,1], and the goal is to immediately color them ± such that every sub-interval remains always nearly balanced. As random coloring incurs Ω(T 1/2) discrepancy, while the worst-case offline bounds are Θ(√n log(T/n)) for vector balancing and 1 for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is Ω(T 1/2) for any online algorithm. In a special case of online vector balancing, Bansal and Spencer [BS19] recently show an O(√nlogT) bound when each coordinate is independently chosen. When there are dependencies among the coordinates, as in the interval discrepancy problem, the problem becomes much more challenging, as evidenced by a recent work of Jiang, Kulkarni, and Singla [JKS19] that gives a non-trivial O(T 1/loglogT ) bound for online interval discrepancy. Although this beats random coloring, it is still far from the offline bound. In this work, we introduce a new framework that allows us to handle online vector balancing even when the input distribution has dependencies across coordinates. In particular, this lets us obtain a poly(n, logT) bound for online vector balancing under arbitrary input distributions, and a polylog (T) bound for online interval discrepancy. Our framework is powerful enough to capture other well-studied geometric discrepancy problems; e.g., we obtain a poly(log d (T)) bound for the online d-dimensional Tusnády’s problem. All our bounds are tight up to polynomial factors. A key new technical ingredient in our work is an anti-concentration inequality for sums of pairwise uncorrelated random variables, which might also be of independent interest.
DOI：
10.1145/3219166.3219179
发表时间：
2018-06
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
通讯作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas