Walk for Learning: A Random Walk Approach for Federated Learning From Heterogeneous Data
Walk for Learning: A Random Walk Approach for Federated Learning From Heterogeneous Data
复制标题
DOI：
10.1109/jsac.2023.3244250
复制
发表时间：
2022-06
影响因子：
16.4
通讯作者：
Ghadir Ayache;Venkat Dassari;S. E. Rouayheb
中科院分区：
文献类型：
--
作者：
Ghadir Ayache;Venkat Dassari;S. E. Rouayheb
我们考虑一个参数服务器（PS）的问题，它希望学习一个模型来拟合分布在图节点上的数据。我们把联邦学习（FL）作为一个规范的应用程序来关注。FL的主要挑战之一是节点与参数服务器之间的通信瓶颈。文献中一个流行的解决方案是允许每个节点在每次迭代中将模型发送回PS之前对模型进行多次本地更新。虽然这缓解了通信瓶颈，但不同节点拥有的数据的统计异质性已被证明会延迟收敛并使模型产生偏差。在这项工作中，我们研究了随机漫步（RW）学习算法来解决通信和数据异构问题。主要思想是利用节点之间可用的直接连接，这通常比与PS的通信“便宜”。在随机漫步中，模型被认为是一个“接力棒”，在每次迭代中更新后，从一个节点传递给它的一个邻居。设计RW的挑战在于数据的异构性和数据分布的不确定性。理想情况下，我们希望更频繁地访问包含更多信息数据的节点。我们将该问题视为一个沉睡的多臂强盗（MAB），设计了接近最优的节点采样策略，该策略实现了方差减少的梯度估计，并接近亚线性的最优采样策略。在此框架下，我们提出了一种自适应随机行走学习算法。对其收敛性提供了理论保证。我们的数值结果验证了我们的理论发现，并表明我们的算法优于现有的随机漫步算法。
We consider the problem of a Parameter Server (PS) that wishes to learn a model that fits data distributed on the nodes of a graph. We focus on Federated Learning (FL) as a canonical application. One of the main challenges of FL is the communication bottleneck between the nodes and the parameter server. A popular solution in the literature is to allow each node to do several local updates on the model in each iteration before sending it back to the PS. While this mitigates the communication bottleneck, the statistical heterogeneity of the data owned by the different nodes has proven to delay convergence and bias the model. In this work, we study random walk (RW) learning algorithms for tackling the communication and data heterogeneity problems. The main idea is to leverage available direct connections among the nodes themselves, which are typically “cheaper” than the communication to the PS. In a random walk, the model is thought of as a “baton” that is passed from a node to one of its neighbors after being updated in each iteration. The challenge in designing the RW is the data hetErogeneity and the uncertainty about the data distributions. Ideally, we would want to visit more often nodes that hold more informative data. We cast this problem as a sleeping multi-armed bandit (MAB) to design near-optimal node sampling strategy that achieves a variance reduced gradient estimates and approaches sub-linearly the optimal sampling strategy. Based on this framework, we present an adaptive random walk learning algorithm. We provide theoretical guarantees on its convergence. Our numerical results validate our theoretical findings and show that our algorithm outperforms existing random walk algorithms.