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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:February 24,2023
  • Revised:March 30,2023
  • Adopted:
  • Online: June 30,2023
  • Published:
Article QR Code
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063