随机步长算法：快速全局优化方法

高晖

摘 要：提出了一種快速全局优化的随机步长算法（RSSA）。采用Adam算法分几步搜索局部最优解。根据收敛情况调整Adam的步长。当陷入局部最优时，估计步长的均值和方差，并将步长调整到局部最优范围之外，如均值加12～36倍方差。初始步长设置为一个较小的值，随着结果的收敛，步长逐渐减小。它保留了基于梯度的方法的优点，如内存少、数据运算稀疏、速度快。算例结果表明，该方法适用于大数据集和高维参数空间的快速全局优化问题。

关键词： 优化算法;随机步长;全局优化

一、介绍

超参数优化算法在深度学习中具有重要意义。随机梯度下降法（SGD）（Robbins&Monro，1951）广泛应用于科学和工程的许多领域。SGD利用梯度的一阶矩来解决目标函数的随机噪声问题，其效率和有效性在深度学习中得到了验证（Deng et al.，2013;Krizhevsky et al.，2012;Hinton&Salakhutdinov，2006;Hinton et al.，2012a;Graves et al.，2013）。Adam（Kingma&leiba，2015）是一种自适应矩估计优化算法，它在训练数据稀疏的情况下具有SGD的性能。Adam具有收敛速度快、内存消耗少、梯度对角缩放不变性等优点，适用于求解具有大规模数据和参数的优化问题（Wilson等，2017;Liangchen Luo等，2019）。

本文提出了一种基于Adam的随机步长调整方法，有效地解决了全局优化问题。采用Adam算法分几步搜索局部最优解。根据收敛情况调整Adam的步长。当陷入局部最优时，估计步长的均值和方差，并将步长调整到局部最优范围之外，如均值加12～36倍方差。初始步长设置为一个较小的值，随着结果的收敛，步长逐渐减小。

二、算法

实际目标函数不仅具有随机性，而且具有多重波动性，使得基于梯度的方法容易陷入局部最优。一种突破局部最优陷阱的方法是调整步长。通过移动平均计算，计算出陷入局部最优的步长的平均值和均方差，然后将步长设置得足够大，使其能够跳出陷阱。例如，将步长设置为平均值加上12-36倍均方差的范围，随机值取该范围。如果跳出局部陷阱，步长将取一个很小的值并逐渐减小。

在算法1中，f（αt） 是指使用Adam计算特定函数的响应，输入αt作为步长。对于不同的函数，应根据收敛到局部最优解的速度，在f（αt） 中设置不同的计算步骤。一般来说，步数不超过1000。

三、验证

为了实证评估所提出的方法，我们研究了不同的优化方法，包括协方差矩阵自适应进化策略（CMA-ES;Hansen和Ostermeier，2001），ADAM。比较结果表明，RSSA算法能有效地解决全局优化问题。

利用Rastrigin函数对该方法进行了评价。所有结果均在内存为8Gb的戴尔i7计算机上进行了模拟。利用RSSA求解Rastrigin问题的最大参数维数可达1亿。相比之下，CMA-ES的最大参数维数可以达到10000。

对于1000-D Rastrigin问题，种群规模设为101的CMA-ES在2100代时用1058秒得到适应值-1464.57，如图1所示，ADAM在几个步骤中落入陷阱。RSSA得到了百万D Rastrigin问题的适应值为0.0的全局最优解，如图2和图3所示。进行了10次运行，平均寻优时间为300.4秒，最快的一次用了11次迭代，耗时34秒，最慢的一次用了380次迭代，耗时1289秒。

四、结论

提出了一种基于Adam的随机步长调整优化算法。我们的方法是针对大数据集和高维参数空间的全局优化。该方法保留了Adam快速收敛到局部最优解的优点，具有快速找到全局最优解的特点。该方法实现简单，占用内存少。通过实验验证了全局最优收敛速度的分析。总之，我们发现RRAS是健壮的，非常适合人工智能优化。

参考文献：

[1]Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics， 22（3）：400–407， 1951.

[2]Deng， Li， Li， Jinyu， Huang， Jui-Ting， Yao， Kaisheng， Yu， Dong， Seide， Frank， Seltzer， Michael， Zweig， Geoff， He， Xiaodong， Williams， Jason， et al. Recent advances in deep learning for speech research at microsoft. ICASSP 2013， 2013.

[3]Krizhevsky， Alex， Sutskever， Ilya， and Hinton， Geoffrey E. Imagenet classifification with deep convolutional neural networks. In Advances in neural information processing systems， pp. 1097–1105， 2012.

[4]Hinton， G.E. and Salakhutdinov， R.R. Reducing the dimensionality of data with neural networks. Science， 313 （5786）：504–507， 2006.

[5]Hinton， Geoffrey， Deng， Li， Yu， Dong， Dahl， George E， Mohamed， Abdel-rahman， Jaitly， Navdeep， Senior， Andrew， Vanhoucke， Vincent， Nguyen， Patrick， Sainath， Tara N， et al. Deep neural networks for acoustic modeling in speech recognition： The shared views of four research groups. Signal Processing Magazine， IEEE， 29（6）：82–97， 2012a.

[6]Graves， Alex， Mohamed， Abdel-rahman， and Hinton， Geoffrey. Speech recognition with deep recurrent neural networks. In Acoustics， Speech and Signal Processing （ICASSP）， 2013 IEEE International Conference on，pp. 6645–6649. IEEE， 2013.

[7]Diederik P Kingma and Jimmy Lei Ba. Adam： A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations （ICLR）， 2015.

[8]Ashia C Wilson， Rebecca Roelofs， Mitchell Stern， Nati Srebro， and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems 30 （NIPS）， pp. 4148–4158， 2017.

[9]Liangchen Luo， Wenhao Huang， Qi Zeng， Zaiqing Nie， and Xu Sun. Learning personalized end-to-end goal-oriented dialog. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence （AAAI）， 2019.