Nov, 2020

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

PDF
TL;DR本文研究基于 ReLU 激活函数的深度 2 神经网络在训练上的困难性，并证明了最小化给定训练集的二次损失函数下的权重和差异生成问题、K 个 ReLU 加权求和问题在现实情况下均为 NP 难问题；同时还针对该问题提出算法时间下限并进行上界分析。
relu activation functiondepth-2 neural networknp-hardnesslower boundsproper learning algorithm
发现论文，激发创造
  • 训练 ReLU 的计算复杂性

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

    Oct, 2018

  • 训练 ReLU 神经网络的复杂度

    本文探讨了采用 ReLU 激活函数训练神经网络的复杂度问题，研究表明在神经元构架固定的情况下，两层 ReLU 神经网络的训练是 NP - 难问题，但在第一隐藏层提供足够的超参数时，可以通过多项式时间算法找到合适的权重。

    Sep, 2018

  • ReLU 门深度神经网络在布尔输入上的下界

    该研究借助 ReLU 挖掘深度学习的奥秘，以布尔函数为背景，考察了 ReLU 网络深度对模型大小的影响，并提出一种随机限制的方法来验证 LTF-OF-RELU 电路的最优性以及 ReLU 深度网络的难以压缩性，并展示出一种 Sum-of-ReLU-of-ReLU 函数实现的不可能性。

    Nov, 2017

  • ReLU 网络训练的多项式时间解决方案：基于最大割和 zonotopes 的复杂性分类

    研究了带有权重衰减正则化的两层 ReLU 神经网络的训练复杂性，证明了近似 ReLU 网络的困难程度不仅与 Max-Cut 问题的复杂性相对应，而且在某些特殊情况下确切对应。具有多项式时间近似保证和近似困难性结果，以及对三种不同类型训练数据集的多项式时间近似分类。

    Nov, 2023

  • 由数据维度参数化的 ReLU 网络训练的计算复杂度

    本文研究了使用修正线性单元（ReLU）训练简单神经网络的计算复杂度，并分析了训练数据维数对计算复杂度的影响。我们提供了参数化复杂度的结果，并且针对各种损失函数分析了两层 ReLU 网络的训练问题。

    May, 2021

  • 关于 ReLU 神经网络的深度下界

    本研究使用混合整数优化、多面体理论、热带几何等技术探究神经网络单隐藏层能否学习到所有函数的普适逼近定理，为可表示函数的类提供了数学支持。同时，解决了 Wang 和 Sun (2005) 关于分段线性函数的一项猜想，并提出了表示具有对数深度函数所需神经网络的上限。

    May, 2021

  • 使用深度 ReLU 神经网络对分段光滑函数进行最优逼近

    研究了在 $L^2$ 意义下逼近分类器函数所需的 ReLU 神经网络的深度和权重数量，构造了一类具有固定层数的人工神经网络，使用 ReLU 激活函数逼近可允许不连续的分段 $C^β$ 函数，权重数量为 $O (ε^{-(2 (d-1))/β})$，并证明这是最优的。此外，为了实现最优逼近率，需要具有一定深度的 ReLU 网络。最后，分析了在高维空间中使用特征映射和分类器函数逼近的情况。

    Sep, 2017

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

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

    Nov, 2016

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

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

    Nov, 2016

  • 关于 ReLU 网络的样本复杂度的大小无关性研究

    本文研究了从推广的角度学习 ReLU 神经网络的样本复杂性，并结合权重矩阵上的范数限制，给出了与网络规模无关的上界，其中 Frobenius norms 为主要研究方向。

    Jun, 2023