考虑从一个未知分布 $p$ 取 $m_1$ 个样本,从另一个未知分布 $q$ 取 $m_2$ 个样本的情形,介绍了一种测试是否有 $p=q$ 的快速算法,并分析了测试的样本复杂度,同时提出了估计马尔科夫链混合时间的算法及其初始样本个数的选择方法。测试算法主要依靠一种表现较为优异的统计量。
Apr, 2015
该研究提供了关于差分隐私下 k 个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界,同时通过构建精心选择的先验概率来证明隐私算法的下界。
Jul, 2017
研究了分布检测的样本测试的复杂度问题,提出了两种技术方法,一种是提供样本最优测试器,另一种是提供匹配样本下界。作者解决了大量重要的测试问题并证明了样本最优性,并且得到了第一个样本最优的对应测试器。
Jan, 2016
研究总变差距离下的离散分布测试问题,提出可用于样本较高概率区域的属性测试的算法,包括相应参数的样本复杂度与正确性保障。
Sep, 2020
本研究主要研究了如何在高置信度条件下,通过有限样本同时检验分布 $q$ 和 $p$ 是否相同,其结果给出了最优样本复杂度并表明了经验分布在均匀性检测中的高效性。
Aug, 2017
我们研究了多维分布的相似性(或等价性)检测的统计任务,并提出了第一个解决这个问题的具有子学习样本复杂度的相似性检测器,其样本复杂度为 $O ((k^{6/7}/poly_d (ε)) log^d (k))$,同时建立了近似匹配的样本复杂度下界 $Ω(k^{6/7}/poly (ε))$,该问题在一维设置中的样本复杂度为 $Θ(k^{4/5}/poly (ε))$。我们的研究结果还衍生出了对于共同未知分区上的 $k$ 个直方图对和支持在 $k$ 个未知不相交轴对齐矩形的均匀分布对的 $d_{TV}$- 相似性检测器,并且在算法和下界的构建中,我们都借助了 Ramsey 理论的工具。
Nov, 2023
研究如何通过样本来鉴别未知分布是否属于某个分布类,提出了一种可获得最优样本和计算效率的通用方法,并为分布的基本属性提供了测试方法。
Jul, 2015
研究了离散分布的条件独立性检验问题,并给出了样本复杂度的上下界,提出了第一种具有次线性样本复杂度的条件独立性测试器,用于对分布属性进行测试。
Nov, 2017
研究了对结构化分布的身份验证问题,提出了具有信息理论最优的样本复杂度的新型简单测试器,并应用于 t - 平面,t - 模态,对数凸,单调危险率(MHR)和它们的混合等广泛类别的结构化分布。
Oct, 2014
在非独立同分布的样本情况下,研究子线性样本属性测试和估计在哪些情形适用;给定一组分布,考虑学习或测试平均分布的属性,在某些情况下需要 $\Theta (k/\varepsilon^2)$ 样本;对于均匀性或相似性的测试,给定 $c=1$ 个样本,需要线性数量级的 $k$ 样本;$c \geq 2$ 时,恢复了独立同分布的亚线性样本测试,需要 $O (\sqrt {k}/\varepsilon^2 + 1/\varepsilon^4)$ 样本,且在 $c=2$ 的情况下,即使是线性数量级的 $\rho k$ 样本,也不能进行均匀性测试。