Jun, 2020

一层 ReLU 网络的 PAC 学习算法和 SQ 下界

PDF
TL;DR本论文研究了具有 $k$ 个隐藏单元的一层 ReLU 网络在高斯边缘下学习的问题，并提出了适用于正系数情况的首个多项式时间算法，解决了此前在 $k≤3$ 情况下无多项式时间算法的开放性问题。然而，对于具有任意实系数的一层 ReLU 网络的 PAC 学习问题，则证明了一个统计查询下界，说明其难以在多项式时间内得到解决。
发现论文，激发创造
  • 通过舒尔多项式高效学习一层 ReLU 网络

    本研究旨在研究使用标准高斯分布下的 ReLU 激活函数的线性组合进行 PAC 学习的问题，并提出了一种具有高效样本和计算复杂度的算法，其复杂度接近于相关统计查询算法类中的最优复杂度。该算法使用张量分解识别出一个子空间，使其在正交方向上的所有 O (k) 阶矩都很小，并利用 Schur 多项式理论证明了当较低阶矩均很小时，较高阶矩误差张量也很小。

    Jul, 2023

  • 学习窄的一层 ReLU 网络

    我们提出了一个基于随机高阶矩张量收缩的多尺度算法，用于发现个别神经元。在学习由 $k$ 个 ReLU 激活的线性组合方面，该算法是首个在多项式时间内成功的，而且无需额外假设网络的正系数或隐藏权重向量的矩阵具有良好的条件数。

    Apr, 2023

  • 从查询中高效学习任何一个具有单个隐层 ReLU 的网络

    本研究基于黑盒访问网络，提出第一个多项式时间算法以学习任意单隐藏层神经网络激活函数，并在高斯测量意义下实现对原神经网络的低二次误差，即使在最坏情况网络下，算法仍保证良好的效率。

    Nov, 2021

  • 学习浅层网络的更快更简单算法

    我们研究了学习从标准的 d 维高斯度量中绘制的带有标签的示例的 k 个 ReLU 激活的线性组合的问题。我们发现了一个简化的一阶段版本的算法，其运行时间只有 (d/ε)^O (k^2)。

    Jul, 2023

  • 在多项式时间内可靠地学习 ReLU

    本研究提出了有效学习基于 ReLU 的常深度网络的算法，该算法运用了核方法、多项式逼近和凸优化的 “双损失” 方法，同时获得了解决 “凸分段线性拟合” 和 “在单位球上低权重多项式的噪音重构” 等其他应用。

    Nov, 2016

  • 高斯边缘下分别学习半空间和 ReLU 的近最优 SQ 下界

    该论文研究了在高斯边际下以不可知方式学习半空间和 ReLU 的基本问题，证明了这些问题的统计查询下限。

    Jun, 2020

  • 训练深度为 2 的 ReLU 网络的紧硬度结果

    本文研究基于 ReLU 激活函数的深度 2 神经网络在训练上的困难性，并证明了最小化给定训练集的二次损失函数下的权重和差异生成问题、K 个 ReLU 加权求和问题在现实情况下均为 NP 难问题；同时还针对该问题提出算法时间下限并进行上界分析。

    Nov, 2020

  • 在多项式时间内学习两层修正线性单元神经网络

    该研究提出了一种基于高斯分布假设的算法，可以在多项式时间内准确地恢复两层神经网络的权重矩阵，即使在存在噪声的情况下。

    Nov, 2018

  • 通过函数梯度计算统计查询下限

    该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题，给出了统计查询下限。通过梯度提升过程对之前的低界进行放大，对具体问题 ReLU 回归（等同于伪装学习 ReLU），我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询，从而阐述了与真实价值的学习问题不同的情况，我们的结果排除了一般（相对于关联）SQ 学习算法，这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型，即伪装学习和概率概念之间得到了最好的规约。

    Jun, 2020

  • 学习深度修正线性单元网络的固定参数可解性

    使用一种称为过滤式 PCA 的新工具来解决学习具有 ReLu 激活函数的神经网络的问题，该算法可以快速，并且不需要权重具有良好的条件或正系数的假设。

    Sep, 2020