Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
复制标题
DOI：
10.1109/focs52979.2021.00116
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
David P. Woodruff;Samson Zhou
中科院分区：
文献类型：
--
作者：
David P. Woodruff;Samson Zhou
在对抗鲁棒流模型中，一系列元素被呈现给一个算法，并且允许其依赖于流过程中早期算法的输出。在经典的仅插入数据流模型中，本 - 埃利泽等人（PODS 2020，最佳论文奖）展示了如何将一个非鲁棒算法转换为一个具有大约$1/\varepsilon$因子开销的鲁棒算法。随后，哈西迪姆等人（NeurIPS 2020，口头报告）将其改进为具有$1/\sqrt{\varepsilon}$因子开销（忽略对数因子）。对于一般函数，根据卡普兰等人（CRYPTO 2021）的结果，后者已知是最优的。我们展示了如何通过为一大类流问题开发数据流算法来绕过这个不可能的结果，在近似因子上没有开销。我们的流问题类别包括研究最为深入的问题，例如$L_{2}$ - 重击者问题、$F_{p}$ - 矩估计以及经验熵估计。我们极大地改进了之前在这些问题上的所有工作，首次给出了对近似因子的最优依赖。与之前的工作一样，我们得到了一个通用的转换，它适用于任何非鲁棒流算法并且依赖于所谓的翻转数。然而，关键的技术创新在于我们将转换应用于我们所谓的流问题的差分估计器，而不是流问题本身的估计器。然后我们为一系列广泛的问题开发了第一个差分估计器。我们的差分估计器方法不仅适用于对抗鲁棒模型，还适用于数据的时间特性起核心作用的其他流模型。为了展示我们技术的通用性，我们另外为相关的数据流滑动窗口模型引入了一个通用框架，并解决了该模型中长期存在的开放性问题，将之前布拉弗曼和奥斯特罗夫斯基（FOCS，2007）对于$p\in[1,2]$以及整数$p > 2$的$F_{p}$ - 矩估计的$1/\varepsilon^{2 + p}$依赖关系大幅改进为最优的$1/\varepsilon^{2}$界限。我们还改进了之前对于$p\in[0,1)$的$1/\varepsilon^{3}$界限以及对于经验熵的之前的$1/-\varepsilon^{4}$界限，对于这两个问题也都得到了第一个最优的$1/\varepsilon^{2}$依赖关系。从性质上讲，我们的结果表明在近似因子方面，滑动窗口模型和标准数据流模型之间没有差异。
In the adversarially robust streaming model, a stream of elements is presented to an algorithm and is allowed to depend on the output of the algorithm at earlier times during the stream. In the classic insertion-only model of data streams, Ben-Eliezer et al. (PODS 2020, best paper award) show how to convert a non-robust algorithm into a robust one with a roughly $1/\varepsilon$ factor overhead. This was subsequently improved to a $1/\sqrt{\varepsilon}$ factor overhead by Hassidim et al. (NeurIPS 2020, oral presentation), suppressing logarithmic factors. For general functions the latter is known to be best-possible, by a result of Kaplan et al. (CRYPTO 2021). We show how to bypass this impossibility result by developing data stream algorithms for a large class of streaming problems, with no overhead in the approximation factor. Our class of streaming problems includes the most well-studied problems such as the $L_{2}$ -heavy hitters problem, $F_{p}$ -moment estimation, as well as empirical entropy estimation. We substantially improve upon all prior work on these problems, giving the first optimal dependence on the approximation factor. As in previous work, we obtain a general transformation that applies to any non-robust streaming algorithm and depends on the so-called flip number. However, the key technical innovation is that we apply the transformation to what we call a difference estimator for the streaming problem, rather than an estimator for the streaming prob-lem itself. We then develop the first difference estimators for a wide range of problems. Our difference estimator methodology is not only applicable to the adversarially ro-bust model, but to other streaming models where temporal properties of the data play a central role. To demonstrate the generality of our technique, we additionally introduce a general framework for the related sliding window model of data streams and resolve longstanding open questions in that model, obtaining a drastic improvement from the previous $1/\varepsilon^{2+p}$ dependence for $F_{p}$ -moment estimation for $p\in$ [1], [2] and integer $p > 2$ of Braverman and Ostrovsky (FOCS, 2007), to the optimal $1/\varepsilon^{2}$ bound. We also improve the prior $1/\varepsilon^{3}$ bound for $p\in[0,1)$, and the prior $1/-\varepsilon^{4}$ bound for empirical entropy, obtaining the first optimal $1/\varepsilon^{2}$ dependence for both of these problems as well. Qualitatively, our results show there is no separation between the sliding window model and the standard data stream model in terms of the approximation factor.