Press "Enter" to skip to content

ICML2019论文 | 炼丹?找到神经网络的全局最优解

训练好神经网络是个老大难问题。 其中一个难点,就在调参以使训练数据上的损失(loss)收敛。 领域中流传有各类调参技巧。 然而,很多技巧并无理论支持,时灵时不灵,以致调参被称为炼丹,是成不成全靠天的玄学。 这与凸优化算法保障找到凸优化问题的全局最优解之间形成强烈反差。 微软朱泽园在ICML2019上的一篇文章,则从理论层面证实,拥有充分多(大于某个多项式下界时)的神经元的神经网络,利用梯度下降或随机梯度下降算法,能够找到全局最优解。

 

在进入细节以前,读者应注意,朱泽园并未对他所得到的多项式下界进行优化,因此这一下界数目虽然随样本量多项式增长,但会非常庞大。最紧下界的数目仍是待解的问题。另外,即使通过构建满足假设条件的神经网络,并采用对应的优化方法得到0损失的网络权重参数,目前也并无理论保证该网络的泛化能力——除了在只有一个隐层时(详见参考文献)。

 

01

 

理论假设

 

该文仅基于如下两个假设。

 

第一,训练数据本身应是 非退化 的,即任何两个训练样本不能相同。 否则,若有两个训练样本相同,而它们的标签不同,容易得知,0损失永远不能达到。 更进一步,该工作假设任意两个训练样本是可分的,即任意两个样本x和样本y在欧式空间的距离大于某个小量。 考虑到实际应用样本总是离散而非连续的(比如图片数据像素点只取整数值),因而总是可分,这一假设合情合理。 下面就将这个小 量称为分辨率,记为\delta。

 

第二,模型本身是 过度参数化 的,即网络的隐层中拥有足够多的神经元。 这一假设是该工作的核心贡献所在。 该工作最终的结果指明,“足够多”这一足够,只需大于某个关于网络层数L和训练样本个数n的多项式函数即可。

 

02

 

理论结果

 

在陈述该文结果前,读者应注意,神经网络的优化有内在的随机性,如参数随机初始化、使用SGD优化器时样本的选择等等。因此,该文所有结果,均只保证在概率意义下成立。特别的,选择合适的参数,可以使这些理论结果以趋于1的概率成立。

 

神经网络的优化算法很多,该文的主要结果针对其中两个,分别是梯度下降算法(gradient descent,GD)和随机梯度下降算法(SGD)。对于梯度下降算法,该文证明,当神经网络的神经元个数m大于某个依赖于层数L、样本量n、分辨率\delta 和特征维度d的多项式函数时,从随机初始化开始——

 

以概率

 

 

和步长

 

 

GD能在多项式的运行时间 内

 

 

找到神经网络权重W使得

 

 

即离全局最优解之间仅差一个小量。

 

该文针对SGD算法证明了类似的结果,仅在步长和多项式的运行时间上有所不同(详情参看文章)。

 

03

 

证明思路

 

文章的主要结果来自于如下两个技术性定理。

 

第一个技术性定理联系了神经网络所表示的函数的梯度大小和函数值的大小。该文证明,概率意义下,当网络权重W距离随机初始参数很近时,梯度的范数有界,特别的,上下界均依赖于函数值。具体而言 ——

 

有上界如下

 

 

有下界如下

 

这一技术性定理说明,随机初始的参数周围不存在任意阶的驻点,从而梯度下降优化器总是能拿到非0的梯度进行梯度下降操作。除非目标函数值已经是0,此时实际上已找到全局最优。这一技术性定理经由实际验证如下图。图中可见梯度范数被目标函数值的常数倍控制住。

 

 

第二个技术性定理是有关神经网络的光滑性定理。对于二阶可导函数,其梯度值的变化被Lipscthiz条件控制住。从而沿梯度方向,总能找到依赖于当前梯度值的合适的步长使函数值确实在下降,并最终证明优化算法收敛。但对一个Relu网络而言,该函数本身不可导,因此需挖掘新的光滑性质,来保证在梯度下降过程中,函数本身是在减小的。在一定的假设条件下,该定理给出了一个类似光滑的性质如下

 

 

讨论:

 

必须说明,该文章仅是一篇关于优化的文章,丝毫不涉及泛化问题。即优化得到的模型在测试环境下的表现。值得一提的是,在另一篇文章Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers中,该文作者朱泽园已证明,层数为3时,过度参数化的网络模型有对应的泛化能力。

 

参考文献:

 

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song. A Convergence Theory for Deep Learning via Over-Parameterizatio. ICML2019.

 

Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. arXiv preprint arXiv:1811.04918, November 2018a.

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注