异构网络环境下最大化谱间距的拓扑设计
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家重点研发计划 (2020YFA0711400); 国家自然科学基金 (61831018, U21A20452)


Topological Design for Maximizing Spectral Gap in Heterogeneous Network Environment
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    分布式平均共识和去中心化机器学习是具有广泛应用的去中心化计算方法. 两种方法的收敛率主要由拓扑的谱间距所决定. 节点网络环境的异构性包括节点带宽和节点间连接可用性的不同. 异构网络环境对去中心化计算的效率提出了挑战. 本文研究异构网络环境下最大化谱间距的拓扑设计问题, 推导了谱间距针对拓扑任一条边的梯度, 并设计了基于该梯度的增删边算法来构建目标拓扑. 构建的拓扑具有更大谱间距, 且各节点的数据通信时间相近. 拓扑构建算法的性能在不同程度的异构网络环境下能够保持稳定, 且生成的拓扑在分布式共识中以更快的收敛率和更短的时间达到收敛. 基于该算法, 本文进一步验证了最新发现的谱间距与去中心化机器学习收敛率的弱相关性.

    Abstract:

    Distributed average consensus and decentralized machine learning are widely employed decentralized computing methods. The convergence rates of the two methods are mainly determined by the spectral gap of the topology. The heterogeneity of the network environment among nodes includes the difference in node bandwidth and inter-node connection availability. The heterogeneous network environment poses a challenge to decentralized computation efficiency. This work studies the topology design of maximizing the spectral gap under a heterogeneous network environment. The gradient of the spectral gap for any edge of the topology is derived and an edge-addition and deletion algorithm is designed based on this gradient to construct the target topology. The generated topology has larger spectral gaps and similar data communication time of each node. The performance of this algorithm remains stable under different levels of heterogeneous network environments. The generated topology achieves convergence with a faster convergence rate and shorter time in distributed consensus. Based on this algorithm, this paper further verifies the recently discovered weak relationship between the spectral gap and convergence rate of decentralized machine learning.

    参考文献
    相似文献
    引证文献
引用本文

缪一航,徐跃东,吴俊.异构网络环境下最大化谱间距的拓扑设计.计算机系统应用,2023,32(9):248-256

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-02-24
  • 最后修改日期:2023-03-30
  • 录用日期:
  • 在线发布日期: 2023-06-30
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号