Jul, 2023

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

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

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

    Jun, 2020

  • 学习窄的一层 ReLU 网络

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

    Apr, 2023

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

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

    Jul, 2023

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

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

    Nov, 2016

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

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

    Nov, 2021

  • 关于学习 ReLU 及高斯边缘的时间 / 准确性权衡

    本文探讨如何在高斯分布下计算最适合的 ReLU 模型，证明了学习受高斯边缘影响下的 ReLU 模型的难点，并提出了一种利用噪声半空间学习算法的近似最优解法。

    Nov, 2019

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

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

    Sep, 2020

  • ReLU$^k$ 激活的深度神经网络的表达能力和逼近特性

    通过使用 ReLU $^k$ 激活函数的深度神经网络，我们研究了其表达能力和逼近特性。我们的研究发现，深度 ReLU$^k$ 网络不仅有效逼近多项式，还能准确表示高次多项式。我们提供了全面而有建设性的证明，证明了深度 ReLU$^k$ 网络可以表示多项式。借此，我们得出了网络参数的上界，并证明了 Sobolev 空间和解析函数的子优逼近率。此外，通过研究深度 ReLU$^k$ 网络对浅层网络的表达能力，我们发现深度 ReLU$^k$ 网络能逼近多种变差空间中的函数，甚至超越了仅由 ReLU$^k$ 激活函数生成的变差空间。这一发现表明了深度 ReLU$^k$ 网络在逼近各种变差空间中的函数时的适应性。

    Dec, 2023

  • 基于 ReLU 的回归近似方案

    本文提出一种基于分布函数采样数据的 ReLU 回归算法并给出了第一个可行的常数近似算法，同时该算法适用于所有对数凸分布。通过更加复杂的技术，我们还能够获得任何次高斯分布的多项式时间逼近方案。

    May, 2020

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

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

    Nov, 2018