提出跳跃式随机游走算法,解决去中心化学习中模型陷入局部区域的问题。
Decentralized Learning via Random Walk with Jumps

- 引入莱维跳跃机制打破随机游走的局部陷阱
- 理论证明收敛速率受数据异质性与网络结构影响
- 适合大规模异构网络下的分布式机器学习场景
我们研究无中心协调器的网络上分布式数据的去中心化学习。随机游走学习是一种基于令牌的方法,单个模型在遍历各节点时使用本地数据更新,通信和计算开销低。加权随机游走学习通过设计转移矩阵实现期望的采样分布,在数据异质情况下加速收敛。我们发现,采用马尔可夫-哈斯蒂恩斯算法实现加权采样可能导致一种此前未被揭示的现象——陷落:随机游走可能被困在网络的小区域内,导致更新高度相关,严重损害收敛性能。为解决此问题,我们提出马尔可夫-哈斯蒂恩斯带莱维跳跃(MHLJ)算法,通过引入偶尔的长程跳转恢复探索能力,同时遵守局部信息约束。我们建立了显式刻画数据异质性、网络谱间隙和跳跃概率作用的收敛率,并通过实验验证MHLJ能有效消除陷落现象,显著加速去中心化学习。
原文摘要 · Abstract (English)
We study decentralized learning over networks where data are distributed across nodes without a central coordinator. Random walk learning is a token-based approach in which a single model is propagated across the network and updated at each visited node using local data, thereby incurring low communication and computational overheads. In weighted random-walk learning, the transition matrix is designed to achieve a desired sampling distribution, thereby speeding up convergence under data heterogeneity. We show that implementing weighted sampling via the Metropolis-Hastings algorithm can lead to a previously unexplored phenomenon we term entrapment. The random walk may become trapped in a small region of the network, resulting in highly correlated updates and severely degraded convergence. To address this issue, we propose Metropolis-Hastings with Levy jumps, which introduces occasional long-range transitions to restore exploration while respecting local information constraints. We establish a convergence rate that explicitly characterizes the roles of data heterogeneity, network spectral gap, and jump probability, and demonstrate through experiments that MHLJ effectively eliminates entrapment and significantly speeds up decentralized learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。