分布式随机加权梯度下降

吕净阁

摘要 针对如何进行分布式计算法，研究了一种基于梯度下降以及权重平衡的分布式随机加权次梯度下降算法。证明了在局部凸目标函数可微且利普希茨连续下，算法的收敛性。

【关键词】分布式优化 利普希茨连续 权重平衡

近年来，随着社会的进步、科技技术的发展，处理的数据不仅数量多而且维度高，对于那些简单的算法而言很难解决，因此分布式计算受到很多的关注。分布式计算通常是多个体系统中的每个节点与其邻居的局部信息交换来使全局损失函数最小。分布式凸优化问题有许多种解决方法：分布式次梯度算法（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.