Published on Sun Nov 15 2020

A Distributed Privacy-Preserving Learning Dynamics in General Social Networks

Youming Tao, Shuzhen Chen, Feng Li, Dongxiao Yu, Jiguo Yu, Hao Sheng
0
0
0
Abstract

In this paper, we study a distributed privacy-preserving learning problem in general social networks. Specifically, we consider a very general problem setting where the agents in a given multi-hop social network are required to make sequential decisions to choose among a set of options featured by unknown stochastic quality signals. Each agent is allowed to interact with its peers through multi-hop communications but with its privacy preserved. To serve the above goals, we propose a four-staged distributed social learning algorithm. In a nutshell, our algorithm proceeds iteratively, and in every round, each agent i) randomly perturbs its adoption for privacy-preserving purpose, ii) disseminates the perturbed adoption over the social network in a nearly uniform manner through random walking, iii) selects an option by referring to its peers' perturbed latest adoptions, and iv) decides whether or not to adopt the selected option according to its latest quality signal. By our solid theoretical analysis, we provide answers to two fundamental algorithmic questions about the performance of our four-staged algorithm: on one hand, we illustrate the convergence of our algorithm when there are a sufficient number of agents in the social network, each of which are with incomplete and perturbed knowledge as input; on the other hand, we reveal the quantitative trade-off between the privacy loss and the communication overhead towards the convergence. We also perform extensive simulations to validate our theoretical analysis and to verify the efficacy of our algorithm.

Mon Mar 27 2017
Machine Learning
Private Learning on Networks: Part II
This paper considers a distributed multi-agent optimization problem. We present two randomized iterative algorithms for distributed optimization. We prove deterministic correctness (in every execution) of the proposed algorithms.
0
0
0
Mon Jul 01 2013
Machine Learning
Online discrete optimization in social networks in the presence of Knightian uncertainty
We study a model of collective real-time decision-making in a social network operating in an uncertain environment. The environment's impact on the agents in the network is seen through a sequence of cost functions. We construct a decentralized strategy, wherein each agent selects its action based only on the costs directly
0
0
0
Tue Oct 01 2013
Machine Learning
Online Learning of Dynamic Parameters in Social Networks
This paper addresses the problem of online learning in a dynamic setting. We consider a social network in which each individual observes a private signal about the underlying state of the world. We establish a tight bound on the rate of change of the state.
0
0
0
Mon Jun 21 2010
Artificial Intelligence
Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties
Online learning has become increasingly popular on handling massive data. The autonomous learners update local parameters based on local data sources. They periodically exchange information with a small subset of neighbors in a communication network.
0
0
0
Mon Aug 29 2011
Machine Learning
Strategic Learning and Robust Protocol Design for Online Communities with Selfish Users
This paper focuses on analyzing the free-riding behavior of self-interested users in online communities. Traditional optimization methods for communities composed of compliant users such as network utility maximization cannot be applied here.
0
0
0
Thu Sep 03 2020
Machine Learning
Private Weighted Random Walk Stochastic Gradient Descent
0
0
0