分布式隨機加權(quán)梯度下降

呂凈閣

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

【關(guān)鍵詞】分布式優(yōu)化 利普希茨連續(xù) 權(quán)重平衡

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

1 問題描述

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

2 分布式隨機加權(quán)次梯度下降

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

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

4 結(jié)論

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

參考文獻

[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]，數(shù)學雜志，2012，32 （01）： 74-78.