测试分布支撑集大小比学习直方图更高效，样本量大幅减少。
Testing Support Size More Efficiently Than Learning Histograms
- 用切比雪夫多项式分析法设计新测试算法
- 仅需 $O( frac{n}{ε/log n} /log(1/ε))$ 样本，逼近最优下界
- 适用于需要快速估计支撑集下界的场景
考虑两个关于未知概率分布 $p$ 的问题：1. 需要多少样本才能判断 $p$ 是否支持在最多 $n$ 个元素上？即给定 $p$ 的样本，判断其是否在总变差距离上与支持大小为 $n$ 的分布 $ε$-远。2. 给定 $m$ 个 $p$ 的样本，能给出的支撑集大小最大下界是多少？现有最优方法通过学习直方图，需 $Θ( frac{n}{ε^2 /log n})$ 样本。本文提出更优算法，仅需 $O( frac{n}{ε/log n} /log(1/ε))$ 样本，接近已知下界 $Ω( frac{n}{ε/log n})$。该算法同时改进了第二个问题的下界估计。证明依赖于对切比雪夫多项式在非设计区间外的近似行为分析，文章旨在以可读方式呈现该方法。
原文摘要 · Abstract (English)
Consider two problems about an unknown probability distribution $p$: 1. How many samples from $p$ are required to test if $p$ is supported on $n$ elements or not? Specifically, given samples from $p$, determine whether it is supported on at most $n$ elements, or it is "$ε$-far" (in total variation distance) from being supported on $n$ elements. 2. Given $m$ samples from $p$, what is the largest lower bound on its support size that we can produce? The best known upper bound for problem (1) uses a general algorithm for learning the histogram of the distribution $p$, which requires $Θ(\tfrac{n}{ε^2 \log n})$ samples. We show that testing can be done more efficiently than learning the histogram, using only $O(\tfrac{n}{ε\log n} \log(1/ε))$ samples, nearly matching the best known lower bound of $Ω(\tfrac{n}{ε\log n})$. This algorithm also provides a better solution to problem (2), producing larger lower bounds on support size than what follows from previous work. The proof relies on an analysis of Chebyshev polynomial approximations outside the range where they are designed to be good approximations, and the paper is intended as an accessible self-contained exposition of the Chebyshev polynomial method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。