精确的一阶分布式算法：Extra

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了精确的一阶分布式算法：Extra，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1942字，纯文字阅读大概需要3分钟。

内容图文

简介：避免数据融合中心（a data fusion center）或是远程通信(a long distance communication)又或是提供更好的负载平衡（better load balance），即一般的分布式计算的背景。

特点:
exact：准确收敛
constant stepsize：固定步长

假设条件1: (图拓扑或matrix假设)

Decentralized Property：\(\omega_{ij}=\tilde{\omega}_{ij}=0\)（如果不存在通信或连接）

Symmetry：\(W=W^T\), \(\tilde{W}=\tilde{W}^T\)(注意这里并没有要求平衡图，因此是无向不平衡)

Null Space Property: null {\(W-\tilde{W}\)}=span {\(1\)}

Spectral Property: \(\tilde{W}\succ 0\), \(\frac{I+W}{2}\succeq\tilde{W}\succeq{W}\)

关于转移矩阵的四种形式:

对称双随机(对称双随机转移矩阵是最理想的分布式优化条件)
- 基于Laplace常数的边权矩阵(Laplacian-based constant edge weight matrix)
$$W=I-\frac{L}{\tau}$$
其中\(L\)是图的拉普拉斯矩阵，\(\tau >\frac{1}{2}\lambda_{\max}(L)\)是一个标量，如果找不到\(\lambda\),可以设置节点最大度+\(\epsilon\)，例如1
- 序列常数边权矩阵(Metropolis constant edge weight matrix)
对称最快线形平均矩阵(FDLA)

Extra方法使用任意的matrix都是可以的。

具体算法:

$$\begin{align}x^1= Wx^0-\alpha\nabla f(x^0)\\
x^{k+2}=(I+W)x^{k+1}-Wx^{k}-\alpha[\nabla f(x^{k+1})-\nabla f(x^k)]\end{align}$$

假设条件2 (目标函数假设)

所有的函数都是 proper closed convex且Lipschitz continuous。即，符合利普希茨连续的闭凸函数。

假设条件3 (存在性假设)

最优解集是存在的。

修正过程:

根据算法容易得出
$x^1=Wx^0-\alpha\nabla f(x^0)$
$x^2= (I+W)x^1-\tilde{W}x^0-\alpha \nabla f(x^1)+\alpha\nabla f(x^0)$
$\cdots$
依次递推后相加，得到
$$x^{k+1}=Wx^k-\alpha \nabla f(x^k)+\sum^{k-1}_{t=0}(W-\tilde{W})x^t,k=0,1,\cdots(1)$$

多项式前面部分就是传统的DGD方案，最后一项就是修正项。

关于这个递推式，可以两边做变形，凑出$W$和$\tilde{W}$的关系。
已知$\tilde{W}=\frac{I+W}{2}$,那么
变形(1)得到$$(I+W-2\tilde{W})x^{k+1}+\tilde{W}(x^{k+1}-x^k)=-(\tilde{W}-W)^{1/2}\sum^{k+1}_{t=0}(\tilde{W}-W)^{1/2}x^t-\alpha \nabla f(x^k)$$

只要证明$-(\tilde{W}-W)^{1/2}\sum^{k+1}_{t=0}(\tilde{W}-W)^{1/2}x^t-\alpha \nabla f(x^k)$等于0即可证明表达式最终收敛。

内容总结

以上是互联网集市为您收集整理的精确的一阶分布式算法：Extra全部内容，希望文章能够帮你解决精确的一阶分布式算法：Extra所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---