江抱石作者

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.

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论神经网络ICML 2019
3
相关数据
微软机构

微软是美国一家跨国计算机科技公司,以研发、制造、授权和提供广泛的计算机软件服务为主。总部位于美国华盛顿州的雷德蒙德,最为著名和畅销的产品为Microsoft Windows操作系统和Microsoft Office办公室软件,以及Xbox的游戏业务。微软是美国《财富》杂志2015年评选的世界500强企业排行榜中的第95名。

https://www.microsoft.com/en-us/about
范数技术

范数(norm),是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,是一个函数,其为向量空间内的所有向量赋予非零的正长度或大小。半范数反而可以为非零的向量赋予零长度。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

随机梯度下降技术

梯度下降(Gradient Descent)是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知,使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中,我们可以利用随机梯度下降的方法来最小化训练模型中的误差,即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例,就对其作出预测,并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

神经元技术

(人工)神经元是一个类比于生物神经元的数学计算模型,是神经网络的基本组成单元。 对于生物神经网络,每个神经元与其他神经元相连,当它“兴奋”时会向相连的神经元发送化学物质,从而改变这些神经元的电位;神经元的“兴奋”由其电位决定,当它的电位超过一个“阈值”(threshold)便会被激活,亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中,神经元通过带权重的连接接处理来自n个其他神经元的输入信号,其总输入值将与神经元的阈值进行比较,最后通过“激活函数”(activation function)产生神经元的输出。

优化器技术

优化器基类提供了计算梯度loss的方法,并可以将梯度应用于变量。优化器里包含了实现了经典的优化算法,如梯度下降和Adagrad。 优化器是提供了一个可以使用各种优化算法的接口,可以让用户直接调用一些经典的优化算法,如梯度下降法等等。优化器(optimizers)类的基类。这个类定义了在训练模型的时候添加一个操作的API。用户基本上不会直接使用这个类,但是你会用到他的子类比如GradientDescentOptimizer, AdagradOptimizer, MomentumOptimizer(tensorflow下的优化器包)等等这些算法。

推荐文章
暂无评论
暂无评论~