Private Weighted Random Walk Stochastic Gradient Descent
Private Weighted Random Walk Stochastic Gradient Descent
复制标题
DOI：
10.1109/jsait.2021.3052975
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Ghadir Ayache;S. E. Rouayheb
中科院分区：
文献类型：
--
作者：
Ghadir Ayache;S. E. Rouayheb
我们考虑一个分散的学习环境，其中数据分布在图中的节点上。我们的目标是在分布式数据上学习一个全局模型，而不涉及任何需要信任的中央实体。虽然基于流言的随机梯度下降（SGD）可以用来实现这一学习目标，但它会产生很高的通信和计算成本。为了加快收敛速度，我们建议研究基于随机游走的SGD，其中全局模型基于图上的随机游走进行更新。我们提出了两种算法的基础上实现，在一个分散的方式，均匀采样和重要性采样的数据的两种类型的随机游走。我们提供了一个非渐近分析的收敛速度，考虑到常数相关的数据和图形。数值结果表明，基于加权随机游走的算法对高方差数据具有更好的性能。此外，我们提出了一个隐私保护的随机游走算法，实现局部差分隐私的基础上，我们提出的伽马噪声机制。我们还给出了数值结果，该算法的收敛性，并表明它优于添加剂拉普拉斯为基础的隐私机制。
We consider a decentralized learning setting in which data is distributed over nodes in a graph. The goal is to learn a global model on the distributed data without involving any central entity that needs to be trusted. While gossip-based stochastic gradient descent (SGD) can be used to achieve this learning objective, it incurs high communication and computation costs. To speed up the convergence, we propose instead to study random walk based SGD in which a global model is updated based on a random walk on the graph. We propose two algorithms based on two types of random walks that achieve, in a decentralized way, uniform sampling and importance sampling of the data. We provide a non-asymptotic analysis on the rate of convergence, taking into account the constants related to the data and the graph. Our numerical results show that the weighted random walk based algorithm has a better performance for high-variance data. Moreover, we propose a privacy-preserving random walk algorithm that achieves local differential privacy based on a Gamma noise mechanism that we propose. We also give numerical results on the convergence of this algorithm and show that it outperforms additive Laplace-based privacy mechanisms.