本论文研究了学习具有相同未知有界协方差矩阵的分离高斯混合模型的复杂性,证明了该问题的任何统计查询算法至少需要 d 的阶次 1/ε 的复杂度,这为已知算法的最佳性提供了证据。
Jun, 2023
在截断设置下,通过统计查询 (SQ) 下界和超多项式的信息计算差,我们研究了估计截断恒等协方差高斯分布的均值问题。
Mar, 2024
本文提出了一种统计查询下限技术,用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题,并得出了样本复杂度和计算复杂度之间存在的超多项式差距,同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
Nov, 2016
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
该论文研究了在高斯边际下以不可知方式学习半空间和 ReLU 的基本问题,证明了这些问题的统计查询下限。
Jun, 2020
本文基于 Sum of Squares 方法,探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法,进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计,我们的方法多次突破优化算法的极限。
Nov, 2017
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法,并使用基于 Sum-of-Squares 证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020
该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题,给出了统计查询下限。通过梯度提升过程对之前的低界进行放大,对具体问题 ReLU 回归(等同于伪装学习 ReLU),我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询,从而阐述了与真实价值的学习问题不同的情况,我们的结果排除了一般(相对于关联)SQ 学习算法,这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型,即伪装学习和概率概念之间得到了最好的规约。
本论文提出了一种新的概念 "统计维数" 来刻画使用 SQ 算法求解样本复杂分布下的一般问题的复杂度,并且首次精确地表征出查询容差的必要性,具有在学习理论和算法优化方面的广泛应用。
Aug, 2016
在满足差分隐私的约束下,研究了估计混合高斯模型问题。通过使用新的框架,证明了高斯模型类的混合模型是可私密学习的,得到了估计混合高斯模型所需的样本数量的有界性,且不对 GMMs 作出任何结构性假设。
Sep, 2023