隨機步長算法：快速全局優化方法

高暉

摘 要：提出了一種快速全局優化的隨機步長算法（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.