本文提出了一种统计查询下限技术,用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题,并得出了样本复杂度和计算复杂度之间存在的超多项式差距,同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
Nov, 2016
本论文研究了学习具有相同未知有界协方差矩阵的分离高斯混合模型的复杂性,证明了该问题的任何统计查询算法至少需要 d 的阶次 1/ε 的复杂度,这为已知算法的最佳性提供了证据。
Jun, 2023
学习高斯协变量下的线性分类器混合问题,主要结果是一个统计查询(SQ)下界暗示已知算法对于该问题基本上是最佳的,甚至对于均匀混合的特殊情况。
Oct, 2023
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
该论文研究了在高斯边际下以不可知方式学习半空间和 ReLU 的基本问题,证明了这些问题的统计查询下限。
Jun, 2020
该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题,给出了统计查询下限。通过梯度提升过程对之前的低界进行放大,对具体问题 ReLU 回归(等同于伪装学习 ReLU),我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询,从而阐述了与真实价值的学习问题不同的情况,我们的结果排除了一般(相对于关联)SQ 学习算法,这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型,即伪装学习和概率概念之间得到了最好的规约。
研究了高维线性回归在对抗性污染下的稳健模型问题,并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。
May, 2018
该研究提出了一种高效的算法,利用截断样本可以无限精确地估计多元正态分布的参数,前提是拥有样本集的访问权,并且该样本集存在具有非微不足道的测度。
Sep, 2018
本文针对高维高斯分布参数学习问题进行了研究,提出了鲁棒估计算法,在拥有少量恶意样本的情况下实现了 $O (ε)$ 精度的估计,同时也证明了算法的多项式时间复杂度和多项式数量样本要求。
Apr, 2017
本文介绍了一种基于矩估计的计算方法,并应用新颖且简单的降维技术将上界推广到任意维数 $d>1$,同时发现了一些样本复杂度较小的特殊情况,同时我们的结果也适用于在总变异距离上学习混合物的每个组件,其中我们的算法显著提高了样本复杂度。
Apr, 2014