用极低空间实现高效分布身份检验，突破传统限制
Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
- 提出仅需O(log⁴ ε⁻¹)空间的流式算法
- 样本复杂度达到理论最优O(1/ε²)
- 适用于连续分布检验，对离散分布不适用
给定一个分布D的样本，需检验其是否等于固定分布D*。当分布为连续时，基于Kolmogorov距离的检验已知可使用最优的O(1/ε²)个样本，但传统方法需O(1/ε²)空间，先前工作已优化至O(1/ε)。本文首次实现仅用O(log⁴ ε⁻¹)空间的流式算法，同时保持渐近最优的样本复杂度。该结果与离散分布上的总变差距离形成鲜明对比——后者已被证明无法实现类似空间压缩。最后，论文提出9个相关开放问题，以激发进一步研究。
原文摘要 · Abstract (English)
Suppose we have a sample from a distribution $D$ and we want to test whether $D = D^*$ for a fixed distribution $D^*$. Specifically, we want to reject with constant probability, if the distance of $D$ from $D^*$ is $\geq \varepsilon$ in a given metric. In the case of continuous distributions, this has been studied thoroughly in the statistics literature. Namely, for the well-studied Kolmogorov metric a test is known that uses the optimal $O(1/\varepsilon^2)$ samples. However, this test naively uses also space $O(1/\varepsilon^2)$, and previous work improved this to $O(1/\varepsilon)$. In this paper, we show that much less space suffices -- we give an algorithm that uses space $O(\log^4 \varepsilon^{-1})$ in the streaming setting while also using an asymptotically optimal number of samples. This is in contrast with the standard total variation distance on discrete distributions for which such space reduction is known to be impossible. Finally, we state 9 related open problems that we hope will spark interest in this and related problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。