通过 Ramsey 理论来测试多变量分布的紧密度

Nov, 2023

通过 Ramsey 理论来测试多变量分布的紧密度

Testing Closeness of Multivariate Distributions via Ramsey Theory

Ilias Diakonikolas, Daniel M. Kane, Sihan Liu

TL;DR我们研究了多维分布的相似性（或等价性）检测的统计任务，并提出了第一个解决这个问题的具有子学习样本复杂度的相似性检测器，其样本复杂度为$O((k^{6/7}/poly_d(ε))log^d(k))$，同时建立了近似匹配的样本复杂度下界$Ω(k^{6/7}/poly(ε))$，该问题在一维设置中的样本复杂度为$Θ(k^{4/5}/poly(ε))$。我们的研究结果还衍生出了对于共同未知分区上的$k$个直方图对和支持在$k$个未知不相交轴对齐矩形的均匀分布对的$d_{TV}$-相似性检测器，并且在算法和下界的构建中，我们都借助了Ramsey理论的工具。

Abstract

We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions $\mathbf p, \mathbf q$ on $\mathbb R^d$, we want to distinguish between the case that $\mathbf p=\mathbf q$ versu

发现论文，激发创造

双样本问题的核方法

提出一种基于重现核希尔伯特空间和大偏差界限的统计检验框架，可用于分析和比较分布，特别对于数据库属性匹配具有很好的性能表现。

May, 2008

离散分布相似度检测的最优算法

本文研究了对于两个离散分布的近似度检测问题，给出了一些用于信息理论最优的简单测试方法，并且在$n$和$\eps$的依赖关系上都达到了常数因子。

Aug, 2013

利用可变宽度直方图实现近线性时间的近似最优密度估计

本文提出了一种高效的基于变宽直方图的密度估计算法，通过使用该算法对来自 $p$ 的独立同分布采样，可以输出一个分段常数概率密度函数作为假设分布，并且在样本规模和运行时间上达到最优，其中总变差距离满足一定的误差限制。

Nov, 2014

使用不均等大小的样本进行接近度测试

考虑从一个未知分布$p$取$m_1$个样本，从另一个未知分布$q$取$m_2$个样本的情形，介绍了一种测试是否有$p=q$的快速算法，并分析了测试的样本复杂度，同时提出了估计马尔科夫链混合时间的算法及其初始样本个数的选择方法。测试算法主要依靠一种表现较为优异的统计量。