论文标题
对抗性稳定的流和滑动窗口的紧密界限通过差估计器
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
论文作者
论文摘要
在对抗性稳健的流模型中，将元素流提供给算法，并允许在流中的较早时间依靠算法的输出。在数据流的经典插入模型中，Ben-Eliezer等。 al。 （2020年PODS，最佳纸张奖）展示如何将非持续算法转换为强大的算法，其中大约$ 1/\ varepsilon $ factor factor Hephads开销。随后将其改进到Hassidim等人的$ 1/\ sqrt {\ varepsilon} $ factor Hepthin。 al。 （神经2020年，口服表现），抑制对数因素。对于一般函数，由于Kaplan等人的结果，后者是最有可能的。 al。 （加密2021）。我们通过为大量流媒体问题开发数据流算法来展示如何绕过这种不可能结果，而近似因素没有开销。我们的流媒体问题包括最有研究的问题，例如$ l_2 $ heeAvy的击球手问题，$ f_p $ - amoment估计以及经验熵估计。我们在这些问题上的所有先前工作都有很大的改进，从而使对近似因素的第一个最佳依赖性提供了最佳的依赖性。 与以前的工作一样，我们获得了适用于任何非体变流算法的一般转换，并取决于所谓的扭曲数。但是，关键的技术创新是，我们将转换应用于流媒体问题的差异估计器，而不是流媒体问题本身的估计器。然后，我们为各种问题开发了第一个差异估计器。我们的差异估计方法不仅适用于对抗性稳健模型，而且适用于数据的时间属性起着核心作用的其他流模型。 （抽象缩短以达到Arxiv限制。）
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 twist 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 problem 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 robust model, but to other streaming models where temporal properties of the data play a central role. (Abstract shortened to meet arXiv limit.)
