Nov, 2016

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

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

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

    Apr, 2023

  • 通过梯度下降学习 ReLU

    本文研究学习呈现形式为 $max (0,<w,x>)$ 的修正线性单元（ReLUs）的问题，聚焦于高维场景下，权重向量的维数大于样本数的情形，针对实现可能性模型，展示了投影梯度下降算法在 0 处初始化的线性收敛率，这一结果对于深度架构的动态具有一定的参考价值。

    May, 2017

  • 面向 Relu 网络的快速计算认证鲁棒性

    本文提供了两种计算和证明最小失真非平凡下界的算法 Fast-Lin 和 Fast-Lip，可以用于解决具有 ReLU 结构的神经网络的鲁棒性问题。相比于现有的解决方法，这两种方法计算速度更快，下界的质量更高，同时作者还证明了除非 NP=P，否则无法用多项式时间算法求解最小的 l1 失真。

    Apr, 2018

  • 通过舒尔多项式高效学习一层 ReLU 网络

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

    Jul, 2023

  • 使用修正线性单元理解深度神经网络

    本文研究使用带有 ReLU 的深度神经网络能够代表的函数家族，提供了一个训练一个 ReLU 深度神经网络的一种算法，同时提高了在将 ReLU 神经网络函数逼近为浅层 ReLU 网络时已知下限的上界，并证明了这些间隙定理。

    Nov, 2016

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

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

    Jun, 2020

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

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

    Nov, 2018

  • 用多项式时间学习具有两个非线性层的神经网络

    提出了一种基于 Lipschitz 的单隐层神经网络的多项式时间学习算法，使用了 Alphatron 算法和核方法，这为布尔学习问题提供了新的方法。

    Sep, 2017

  • 线性可分数据上的 ReLU 网络学习：算法，最优性和泛化

    本文提出了一种新的随机梯度下降算法，利用随机噪声扰动，无需任何假设于数据分布、网络大小和训练集大小，就能够证明地达到单隐藏层 ReLU 网络的全局最优性，同时提出了一些一般的泛化保证，此外，数值测试结果也验证了算法和理论的实用性。

    Aug, 2018

  • 训练 ReLU 的计算复杂性

    针对由修正线性单元（ReLU）组成的两层神经网络的训练的计算复杂度进行了探讨，发现该问题是 NP-hard 的，但在权重和样本都属于单位球时，可以通过特定算法在有限时间内得到令人满意的学习效果。

    Oct, 2018