分布式隨機加權梯度下降

呂凈閣

摘要 針對如何進行分布式計算法，研究了一種基于梯度下降以及權重平衡的分布式隨機加權次梯度下降算法。證明了在局部凸目標函數可微且利普希茨連續下，算法的收斂性。

【關鍵詞】分布式優化 利普希茨連續 權重平衡

近年來，隨著社會的進步、科技技術的發展，處理的數據不僅數量多而且維度高，對于那些簡單的算法而言很難解決，因此分布式計算受到很多的關注。分布式計算通常是多個體系統中的每個節點與其鄰居的局部信息交換來使全局損失函數最小。分布式凸優化問題有許多種解決方法：分布式次梯度算法（DG）;分布式ADMM算法。文獻[3]在梯度下降算法的基礎上介紹了一種隨機梯度下降法，并證明了算法的一些重要性質。

1 問題描述

本文考慮一個由n個節點構成的有向連通網絡圖Gt（V，Et）表示，其中V代表節點集合，Et代表邊集。如果在第t時刻節點i和節點j有信息交流，則（i，j）∈Et;Nout（t）={j∈V|（i，j）∈Et}，dout（t）=|Nout（t）表示節點i在第t時刻的出度鄰居和出度。本文考慮以下分布式凸優化問題：

2 分布式隨機加權次梯度下降

為解決分布式隨機算法，本文通過對狀態添加獨立同分布的隨機擾動，提出具有分布式隨機加權次梯度下降算法：令xi（t）∈Rd為節點i的本地估計，每個節點i進行（3）：∈3 算法的收斂性分析

令x*為算法的最優點。為方便分析算法的收斂性，定義

4 結論

本文在時變有向強連通網絡拓撲下研究了分布式隨機加權次梯度下降算法，通過理論分析證明了算法的收斂性。

參考文獻

[1]A. Nedic and A.Ozdaglar. Distributedsubgradient methods for multi-agentoptimization [J]. IEEE Transactions onAutomat ic Control， 2009， 54 （01）： 48-61.

[2]王慧慧.分布式交替方向乘子法研究[D].南京大學，2017.

[3]汪寶彬，戴濟能，隨機梯度下降法的收斂速度[J]，數學雜志，2012，32 （01）： 74-78.