训练 ReLU 神经网络的复杂度
针对由修正线性单元(ReLU)组成的两层神经网络的训练的计算复杂度进行了探讨,发现该问题是 NP-hard 的,但在权重和样本都属于单位球时,可以通过特定算法在有限时间内得到令人满意的学习效果。
Oct, 2018
本文研究基于 ReLU 激活函数的深度 2 神经网络在训练上的困难性,并证明了最小化给定训练集的二次损失函数下的权重和差异生成问题、K 个 ReLU 加权求和问题在现实情况下均为 NP 难问题;同时还针对该问题提出算法时间下限并进行上界分析。
Nov, 2020
本文研究了使用修正线性单元(ReLU)训练简单神经网络的计算复杂度,并分析了训练数据维数对计算复杂度的影响。我们提供了参数化复杂度的结果,并且针对各种损失函数分析了两层 ReLU 网络的训练问题。
May, 2021
研究了带有权重衰减正则化的两层 ReLU 神经网络的训练复杂性,证明了近似 ReLU 网络的困难程度不仅与 Max-Cut 问题的复杂性相对应,而且在某些特殊情况下确切对应。具有多项式时间近似保证和近似困难性结果,以及对三种不同类型训练数据集的多项式时间近似分类。
Nov, 2023
本研究基于黑盒访问网络,提出第一个多项式时间算法以学习任意单隐藏层神经网络激活函数,并在高斯测量意义下实现对原神经网络的低二次误差,即使在最坏情况网络下,算法仍保证良好的效率。
Nov, 2021
我们提出了一个基于随机高阶矩张量收缩的多尺度算法,用于发现个别神经元。在学习由 $k$ 个 ReLU 激活的线性组合方面,该算法是首个在多项式时间内成功的,而且无需额外假设网络的正系数或隐藏权重向量的矩阵具有良好的条件数。
Apr, 2023
本文研究了使用不同激活函数定义的神经网络的训练问题的复杂性,证明了 sigmoid 激活函数导致的训练问题多项式时间可约化到存在性理论中,但是对于正弦激活函数的训练问题是不可判定的,并给出了限制条件下的训练问题的复杂性的上界。
May, 2023
本文研究使用带有 ReLU 的深度神经网络能够代表的函数家族,提供了一个训练一个 ReLU 深度神经网络的一种算法,同时提高了在将 ReLU 神经网络函数逼近为浅层 ReLU 网络时已知下限的上界,并证明了这些间隙定理。
Nov, 2016
本研究使用混合整数优化、多面体理论、热带几何等技术探究神经网络单隐藏层能否学习到所有函数的普适逼近定理,为可表示函数的类提供了数学支持。同时,解决了 Wang 和 Sun (2005) 关于分段线性函数的一项猜想,并提出了表示具有对数深度函数所需神经网络的上限。
May, 2021
使用一种称为过滤式 PCA 的新工具来解决学习具有 ReLu 激活函数的神经网络的问题,该算法可以快速,并且不需要权重具有良好的条件或正系数的假设。
Sep, 2020