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

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.

学术头条已建立微信交流群，想进群的同学请加学术君微信：AMiner308，记得备注：名字+单位/学校噢！

分享干货

AMiner迄今为止已发布18期AI系列研究报告，您可在后台回复 对应数字 获取报告。

推荐阅读 （点击查看↓）

✦  用户画像: 信息抽取方法概览

✦ Google Brain最新论文：标签平滑何时才是有用的？

✦ AI Time 第三期激辩|知识图谱的构建主要靠人工还是机器？

✦ CHI2019论文| 手势识别的2篇论文： BeamBand和Fine-grained hand activity

✦ CHI2019论文| 如何使用前置摄像头玩出手机交互新花样

✦ NeurIPS2018论文| 如何确定词向量嵌入表示的维数？ 斯坦福提出一种快速选择方法

✦ 基于嵌入表示的网络实体对齐方法进展概述

微信公众号菜单栏为大家设置了 “论文推荐” 和 “优质分享” 专栏，欢迎大家关注。

您的转发就是我们最大的动力

点击阅读原文 查看更多AMiner学术文章