本文探讨如何在高斯分布下计算最适合的 ReLU 模型,证明了学习受高斯边缘影响下的 ReLU 模型的难点,并提出了一种利用噪声半空间学习算法的近似最优解法。
Nov, 2019
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题,给出了统计查询下限。通过梯度提升过程对之前的低界进行放大,对具体问题 ReLU 回归(等同于伪装学习 ReLU),我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询,从而阐述了与真实价值的学习问题不同的情况,我们的结果排除了一般(相对于关联)SQ 学习算法,这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型,即伪装学习和概率概念之间得到了最好的规约。
Jun, 2020
学习高斯协变量下的线性分类器混合问题,主要结果是一个统计查询(SQ)下界暗示已知算法对于该问题基本上是最佳的,甚至对于均匀混合的特殊情况。
Oct, 2023
在截断设置下,通过统计查询 (SQ) 下界和超多项式的信息计算差,我们研究了估计截断恒等协方差高斯分布的均值问题。
Mar, 2024
本文提出了一种统计查询下限技术,用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题,并得出了样本复杂度和计算复杂度之间存在的超多项式差距,同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
Nov, 2016
本论文研究了学习具有相同未知有界协方差矩阵的分离高斯混合模型的复杂性,证明了该问题的任何统计查询算法至少需要 d 的阶次 1/ε 的复杂度,这为已知算法的最佳性提供了证据。
Jun, 2023
本论文研究了具有 $k$ 个隐藏单元的一层 ReLU 网络在高斯边缘下学习的问题,并提出了适用于正系数情况的首个多项式时间算法,解决了此前在 $k≤3$ 情况下无多项式时间算法的开放性问题。然而,对于具有任意实系数的一层 ReLU 网络的 PAC 学习问题,则证明了一个统计查询下界,说明其难以在多项式时间内得到解决。
研究学习理论中使用的统计查询模型在学习含有 Massart 噪声的 Halfspaces 时的有效性,并证明了已知的算法与最优界的差距,解决了一个学习理论中长期存在的难题。
Dec, 2020
研究了高维线性回归在对抗性污染下的稳健模型问题,并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。
May, 2018