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

呂凈閣

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

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

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

1 問題描述

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

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

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

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

4 結(jié)論

本文在時變有向強(qiáng)連通網(wǎng)絡(luò)拓?fù)湎卵芯苛朔植际诫S機(jī)加權(quán)次梯度下降算法，通過理論分析證明了算法的收斂性。

參考文獻(xià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].南京大學(xué)，2017.

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