Private Weighted Random Walk Stochastic Gradient Descent

• URL: http://arxiv.org/abs/2009.01790v2
• Date: Tue, 16 Mar 2021 10:10:25 GMT
• Title: Private Weighted Random Walk Stochastic Gradient Descent
• Authors: Ghadir Ayache and Salim El Rouayheb
• Abstract summary: We consider a decentralized learning setting in which data is distributed over nodes in a 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.
• Score: 21.23973736418492
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, since it has to wait for all the local models at all the nodes to converge. 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.

Related papers

• The Entrapment Problem in Random Walk Decentralized Learning [10.355835466049088]
  We investigate a decentralized SGD algorithm that utilizes a random walk to update a global model based on local data. Our focus is on designing the transition probability matrix to speed up convergence. We propose the Metropolis-Hastings with L'evy Jumps (MHLJ) algorithm, which incorporates random perturbations (jumps) to overcome entrapment.
  arXiv  Detail & Related papers  (2024-07-30T07:36:13Z)
• Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
  We propose a collaborative inverse propensity score estimator for causal inference with heterogeneous data. Our method shows significant improvements over the methods based on meta-analysis when heterogeneity increases.
  arXiv  Detail & Related papers  (2024-04-24T09:04:36Z)
• Differentially Private Decentralized Learning with Random Walks [15.862152253607496]
  We characterize the privacy guarantees of decentralized learning with random walk algorithms, where a model is updated by traveling from one node to another along the edges of a communication graph. Our results reveal that random walk algorithms tends to yield better privacy guarantees than gossip algorithms for nodes close from each other.
  arXiv  Detail & Related papers  (2024-02-12T08:16:58Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Clustering for directed graphs using parametrized random walk diffusion kernels [5.145741425164946]
  We introduce a new clustering framework, the Parametrized Random Walk Diffusion Kernel Clustering (P-RWDKC) Our framework is based on the diffusion geometry and the generalized spectral clustering framework. Experiments on $K$-NN graphs constructed from real-world datasets and real-world graphs show that our clustering approach performs well in all tested cases.
  arXiv  Detail & Related papers  (2022-10-01T16:13:40Z)
• Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data [17.978941229970886]
  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. We present an adaptive random walk learning algorithm.
  arXiv  Detail & Related papers  (2022-06-01T19:53:24Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  A computationally less intensive and node connectivity aware uniform sampling method is proposed. The advantages of the proposed algorithm become more enhanced when the algorithm is applied to large graphs.
  arXiv  Detail & Related papers  (2021-10-21T19:16:16Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  The distributionally robust optimization framework is considered for training a parametric model. The objective is to endow the trained model with robustness against adversarially manipulated input data. Proposed algorithms offer robustness with little overhead.
  arXiv  Detail & Related papers  (2020-07-07T18:25:25Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.