In large-scale federated and decentralized learning, communication efficiency
is one of the most challenging bottlenecks. While gossip communication -- where
agents can exchange information with their connected neighbors -- is more
cost-effective than communicating with the remote server, it often requires a
greater number of communication rounds, especially for large and sparse
networks. To tackle the trade-off, we examine the communication efficiency
under a semi-decentralized communication protocol, in which agents can perform
both agent-to-agent and agent-to-server communication in a probabilistic
manner. We design a tailored communication-efficient algorithm over
semi-decentralized networks, referred to as PISCO, which inherits the
robustness to data heterogeneity thanks to gradient tracking and allows
multiple local updates for saving communication. We establish the convergence
rate of PISCO for nonconvex problems and show that PISCO enjoys a linear
speedup in terms of the number of agents and local updates. Our numerical
results highlight the superior communication efficiency of PISCO and its
resilience to data heterogeneity and various network topologies.

在大规模联邦和分散式学习中，沟通效率是最具挑战性的瓶颈之一。为了解决这个折衷问题，我们在半分散式通信协议下研究了通信效率，设计了一种适应于半分散式网络的通信高效算法 PISCO，并证明了 PISCO 在非凸问题上具有收敛速度和线性加速效果，强调了 PISCO 在通信效率、数据异质性和各种网络拓扑上的优越性。