{'fraction_non_alphanumeric': 0.0479361555943132, 'fraction_numerical': 0.01730881031657946, 'mean_word_length': 3.983932569471882, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Distributed Privacy-Preserving Learning Dynamics in General Social Networks

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.


INTRODUCTION
Given a set of options which yield unknown stochastic rewards/payoffs, learning the best option to maximize the expected reward gains is a commonly encountered issue in a wide spectrum including human society [1], robotics [2] and biology [3]. This problem can be casted as the following sequential decision problem: in each step, every individual (or agent) selects one of the options to adopt and obtains the reward yielded by the option; the goal is to let the agents make sequential selection decisions in an on-line manner, so as to identify the best option with the cumulative reward gains maximized even without the prior knowledge about the options' stochastic qualities.
In a social group, each agent can imitate the rational behaviors of the others through social interactions, to improve the efficiency of the above learning process. As shown in [4], the (iterative) social learning approach to the above problem consists of two stages: in each step, every agent takes an option sample according to the options' popularities, then decides whether or not to adopt the sampled option based on the latest observation on its stochastic reward signal. Although the above "sampling-and-adopting" social learning approach need not maintain any historical observations, it entails global information (i.e., all agents' latest adoptions) as input to calculate the options' popularities, while collecting the global information over the agents may result in considerable overhead in general social networks where the agents exchange information with each others through multi-hop communications. Moreover, agents in a social network usually are not forced to behave trustfully to each other; therefore, designing privacy-preserving mechanisms for protecting the agents' private data (e.g., their personal adoptions in our case) has been trending up in recent years [5], [6], [7]. Nevertheless, differential privacy has been extensively leveraged for data-centric off-line learning methods (e.g., federated learning [8], [9], [10], [11]), if it can be applied to the reinforced social learning process is still an open problem.
In this paper, we propose a privacy-preserving distributed social learning algorithm for general social networks. It proceeds iteratively and involves the following four stages in each iteration: • Perturbing: By leveraging the notion of Local Differential Privacy (LDP), each agent applies randomized perturbation to its latest adoptions for the purpose of privacy preservation.
• Disseminating: We propose a random walk-based information dissemination method, by which each agent disseminates its perturbed adoption over the (multi-hop) social network. • Adopting: Each agent finally decides whether or not to adopt the option (selected in the last stage) according to its most recent stochastic quality signal.
Although the above algorithm (technically) is applicable to the privacy-aware distributed learning in general social networks, some fundamental algorithmic questions are open: • According to our brief sketch on our proposed algorithm (especially the first two stages), the knowledge learnt by each agent from its peers is incomplete and perturbed. Hence, can our proposed four-staged social learning algorithm converge to the best option in this case? And if so, how efficient is it?
• It has been well known that perturbing a single (private) data may reduce its utility; therefore, given certain privacy budget, how much complexity (especially in communications) we have to pay for ensuring the utilities of the data collections for each agent in our social learning algorithm?
In this paper, we, for the first time, answer the above two open questions by solid theoretical analysis. We also perform extensive simulations to validate our theoretical analysis and to verify the efficacy of our algorithm.
The remainder of this paper is organized as follows. We survey related literature in Sec. 2. In Sec. 3, we give our system model and formulate our learning problem, before introducing some preliminaries which will be useful to our algorithm design and analysis. We then present the design of our four-staged privacy-preserving distributed social learning algorithm and the corresponding analysis in Sec. 4 and Sec. 5, respectively. The simulation results are reported in Sec. 6. We finally conclude our paper in Sec. 7.

Social Learning
Optimizing the decision-making process to maximize the expected reward is an essential problem for socialized individuals. Learning the best option for an isolated individual with time-invariant finite memory has been proved impossible in [12], [13]. Nevertheless, a common wisdom may suggest that interacting with each others to share the choices in the social group may contribute to the success of the learning process. Specifically, one can learn the experiences from its peers so as to avoid making similar mistakes in the decision-making process [14], [15]. Whereas the learning algorithms in early studies involve either sampling stage [16] or adopting stage [17], it is demonstrated in [18] that combining the two steps together could be a better learning strategy empirically. The two-staged learning strategy is then applied in sociology and economics [19], [20], [21], where the two stages are both crucial for the learning process. Our work is partially inspired by the recent work [4]. It investigates the dynamics of the two-staged learning strategy which entails global information as input, such that one in the social network can be aware of the choices of all the others. Unfortunately, single-hop social networks are not always available, whereas collecting the choices over the general (multi-hop) social network may induce considerable communication overhead. Hence, in this paper, one of our contributions is to study the learning dynamics in general social networks where the individuals interact with each other by multi-hop communications.

Privacy Preservation in Distributed Learning
The collaboration nature of the social learning entails data sharing among the learners (i.e., the agents in our case), whereas these data may implicate sensitive information of the learners. Therefore, privacy preservation becomes one of the main concerns for designing a feasible social learning mechanism. Nevertheless, most of existing proposals have their focus on investigating the privacy-preserving issue for data-intensive distributed learning frameworks, e.g., federated learning, where a central parameter server is deployed to update the target parameters of the learning model according to the gradients calculated by several distributed data servers based on their local data. One branch of these studies is to apply cryptography-based methods, e.g., secure multi-party computation [22], [23] and homomorphic encryption [24], [25]. However, the cryptographybased methods may induce considerable computation overhead. Therefore, another emerging branch (e.g., [8], [9], [10], [11]) relies on the notion of differential privacy, which is a state-of-the-art approach to address the privacy concerns in a wide range of topics including data release [26], [27], data mining [28], data collection [29], [30], etc. Unfortunately, whether or not it can be applied to address the privacy concern in our distributed social learning with no central infrastructure entailed is still an open problem.

MODELS AND PRELIMINARIES
In this section, we first introduce our system model in Sec. 3.1, and then formulate our problem of social learning dynamics in Sec. 3.2. We also introduce some preliminaries in Sec. 3.3, which will be useful in the sequent sections. Frequently used notations throughout this paper are summarized in Table 1.

System Model
We consider a social network represented by an undirected graph G = (N , E). N = {1, 2, · · · , N } denotes a set of N agents while E denotes the set of the edges between the agents. For ∀i, i ∈ N and i = i , we have an edge (i, i ) ∈ E if they can exchange messages with each other. Let N i = {i ∈ N | (i , i) ∈ E} denote the neighbors of agent i and N i be the size of N i (i.e., the degree of agent i in graph G). Assume each agent i initially is aware of N i . Without loss of generality, we suppose G is a connected and non-bipartite graph. We also assume that the network is well synchronized such that time can be divided into a set of disjoint rounds r = 1, 2, · · · , R, each of which consists of ∆ time slots. We adopt a relaxed CONGEST communication model, such that each agent is allowed to send only O(g(N )) messages of O(log N ) bits over each edge in a slot 1 . A social network consisting of agents N and edges E N i ⊆ N The set of the neighbors of agent i The random quality indicator of option j in round r η j ∈ [0, 1] Probability of Φ r j = 1 The adoption vector of agent i in round r where the binary random variable X r i,j (with j = 1, 2, · · · , m) indicating if agent i adopts option j in round r The perturbed adoption vector of agent i in round r where X r i,j is the random perturbation of X r−1 The set of the (replicated) perturbed adoption vectors disseminated in round r V r i ⊆ V r The set of the (replicated) perturbed adoption vectors sampled by agent i in round r V r = |V r | The number of the (replicated) perturbed adoption vectors disseminated in round r. V r i = |V r i | The number of the (replicated) perturbed adoption vectors sampled by agent i in round r. Q r j The popularity of option j in round r.
The set of agents selecting option j in the sampling stage of round r S r j = |S r j | The number of agents selecting option j in the sampling stage of round r The number of agents adopting option j in round r The number of agents with non-null adoption vectors in round r Suppose there are M options M = {1, · · · , M }. Each option j ∈ M is associated with a random quality indicator Φ r j ∈ {0, 1} in each round r 2 . Specifically, we have Φ r j = 1 if option j is "good" in round r such that the agents choosing it can gain reward; otherwise, Φ r j = 0. For ∀j ∈ M, Φ 1 j , Φ 2 j , · · · , Φ R j are drawn independently and identically from an unknown Bernoulli distribution parameterized by η j , i.e., Φ r j ∼ Bernoulli(η j ) for ∀j, such that Φ r j = 1, with probability η j ; 0, with probability 1 − η j .
Without loss of generality, we suppose that η 1 > η 2 ≥ · · · ≥ η M , such that the first option is the best one.

Social Learning Dynamics
As introduced in Sec. 1, the social learning algorithm proceeds iteratively in rounds r = 1, 2, · · · . Let X r i,j ∈ {0, 1} be a binary variable indicating if agent i adopts option j in round r. We assume that each agent i adopts at most one option in each round such that M j=1 X r i,j ≤ 1 for ∀r. Without prior knowledge on η j for ∀j ∈ M, the learning goal is to minimize the following average regret function where denotes the popularity of option j in round r, namely the fraction of the agents adopting option j in round r. Initially, we assume Q 0 j = 1 M for ∀j ∈ M 3 . The regret function measures the expected average difference between the optimal 2. As will be shown later, our algorithm is readily compatible to quality indicators varying randomly across slots.
3. Similar to [4], such an assumption of equal popularities is not crucial to our results. Our results hold with arbitrary initial conditions. off-line adoption policy (where every agent adopts the best option with prior knowledge about η j for ∀j ∈ M) and our on-line learning algorithm (with no prior knowledge about η j ) in reward gains up to R rounds.
We investigate a distributed social learning dynamics for general (multi-hop) social networks, such that the agents work collaboratively by exchanging information with each other through the general network so as to minimize the above regret function. Moreover, our another concern is the privacy preservation issue for the agents such that their information exchange will not result in privacy leakage.

Metropolis-Hasting Random Walk
In this paper, we leverage the notion of random walk such that each agent samples the distribution of the adoptions in the social network. In each step, a walk carries an information token from the current agent to a random neighbor or itself. Particularly, for a Metropolis-Hasting Random Walk (MHRW), in each step, i forwards the token to a randomly chosen neighbor (or itself) i according to probability Ψ(i, i ) The denote the probability that the walk initialized by agent i researches agent i after t steps. When the graph G is connected and non-bipartite, Ψ is a symmetric doubly stochastic matrix such that the random walk (initialized by i) has a unique uniform stationary distribution with q t i,i = 1 N for ∀i ∈ N when t → ∞. According to [31], the random walk achieves a α-nearly uniform distribution (such that 1 α steps, where Γ(Ψ) denotes the spectral gap of the transition matrix Ψ. In the following, to facilitate our algorithm analysis, we let α = 1 N 3 without sacrificing the generality and rationality of our analysis. Since Γ(Ψ) does not depend on N , it is said that a MHRW achieves a nearly uniform distribution in O(log N ) steps. In fact, α can be made as small as required at the expense of constant.

Local Differential Privacy
During the learning process, the agents need to communicate with each other for information exchanging, which entails a high demand on privacy preservation. In this paper, we leverage the notion of Local Differential Privacy (LDP) for the purpose of preserving privacy.
Definition 3.1 (Local Differential Privacy). Let ε be a positive real number and F be a randomized algorithm which takes a user's private data set D as input. Let imD be the image of the algorithm F. The algorithm F is said to be able to deliver ε-differential privacy, if for any pair of the user's possible private data x, x ∈ D and any subset K of imD, ε is the so-called privacy budget, which specifies the privacy loss which we can afford. Specifically, we have to allow more loss of privacy with a higher privacy budget. Especially, when = ∞, the randomized algorithm cannot offer any privacy preservation.

Basic Facts
We hereby introduce a few theorems and definitions which will be useful in our algorithm analysis.

Theorem 3.3 (Bernoulli Inequality).
Supposing z > −1 = 0 is a real number and n > 1 is an integer, we have Definition 3.2. Given real numbers Z 1 , Z 2 and c ≥ 0, the notation Z 1 c ∼ Z 2 denotes 1 c ≤ Z1 Z2 ≤ c. Definition 3.3. We leverage the notation g : N + → R to represent a function such that (i) For any real number > 0, there exists a positive integer (ii) For any real number > 0, there exists a positive integer where the first inequality is due to the Bernoulli Inequality (see Theorem 3.3). (6) can be obtained by rearranging the above inequality. Note that The inequality (7) follows the Bernoulli Inequality directly as follows:

ALGORITHM
In this section, we present our privacy-preserving social learning algorithm in a general graph. Our algorithm proceeds iteratively in rounds and each agent performs the following four stages in each round. In Stage 1, each agent perturbs the option it adopted in the last round, for the purpose of privacy preserving. Then, the agents disseminate their perturbed adoptions over the network through MHRWs in Stage 2. Thereafter, in Stage 3, each agent may receive a number of perturbed adoptions from its peers, according to which, the agent selects one option as a candidate. The candidate option is then considered to be adopted or not in Stage 4, based on the most recent observation on its stochastic quality. In the following, we present the details of the four stages, respectively.

Stage 1: Perturbing
If agent i does not adopt any option in round r − 1 such that X r−1 i,j = 0 for ∀j ∈ M, it does nothing to the adoption variables {X r−1 i,j } j∈M ; otherwise, i perturbs X r−1 i,j (for ∀j ∈ M) according to the following rule In another word, for any option j, each agent i "flips" , · · · , X r i,M be the perturbed adoption vector of node i in round r, the output of this stage is X r = { X r i } i∈N .

Stage 2: Disseminating
In this stage, we employ MHRWs to disseminate the perturbed adoption vectors over the network G. Each vector is associated with a length indicating the maximum times it is forwarded in a random walk. The vector and its length variable (as well as some prerequisite information specified by specific communication protocols) are encapsulated in a data token. A token is said to be feasible if it has a non-zero length variable. For any agent i adopting some option in round r − 1, it sets off hg(N ) MHRWs in parallel (where h = 16σ 1−β with σ ≥ 11). Each random walk has a length of O(log N ). The agent i uses a First-in-First-out (FIFO) queue to buffer the tokens (with non-zero length indicators) received to forward next. In each slot of round r, i pops the first (up to) hg(N ) feasible tokens out of the queue, and forwards each of the tokens to either one of its neighbors or itself according to the probability distribution Ψ(i, i ) (see Eq. (4)). The lengths of the tokens are decreased by one before the forwarding. A token (and thus a perturbed adoption vector) is said to be "sampled" by a agent if it reaches the agent with the associated length variable being zero. Let V r i denote the set of the perturbed adoption vectors sampled by agent i and V r i = |V r i | be the size of V r i . Note that, an agent may receive multiple perturbed adoption vectors from the same one.

Stage 3: Sampling
In this stage, each agent i selects an option to consider in the following adopting stage. Specifically, the agent i, with probability µ, selects an option j uniformly at random 4 ; with probability 1 − µ, i selects one of the options according to their normalized popularity estimates { Q r i,j } j∈M . In particular, agent i first estimates j's (unnormalized) popularity Q r i,j according to the sampled perturbed adoption vectors V r i in round r as such that Q r i,j ≥ 0 and m j=1 Q r i,j = 1.

Stage 4: Adopting
Let j * be the option sampled by agent i in the above stage. The agent i then decides whether or not to adopt the option j * according to the following rule: 4. We hereby use the probability µ to force the agents to "explore" the options, to prevent our algorithm from getting stuck in a local optimum. In practice, the parameter µ > 0 is usually small.
where β > 1/2 and is close to 1/2. In particular, if observing the most recent quality signal Φ r j * = 1, with probability β, the agent i adopts the option j * such that X r i,j * = 1 and X r i,j = 0 for ∀j = j * , while with probability 1 − β, i does not adopt any option such that X r i,j = 0 for ∀j. If Φ r j * = 0 is observed, i adopts j * with probability 1 − β or adopts none of the options with probability β.

ANALYSIS
In this section, we present the details of our analysis on the algorithm. We first analyze our algorithm from the perspective of communication complexity in Sec. 5.1. We then demonstrate how our algorithm has the regret function bounded in Sec. 5.2 and finally discuss the privacy preservation of our algorithm in Sec. 5.3.

Communication Complexity
It is demonstrated above that our algorithm entails very light-weight computations; therefore, we hereby focus on the communication complexity in each round, namely the number of slots in each round for disseminating the perturbed adoption vectors, while leaving the analysis on the number of rounds our algorithm takes to achieve convergence in Sec. 5.2.
As shown in Sec. 4.2, each agent launches hg(N ) MHRWs in each round in the disseminating stage, the question is, given that each MHRW entails O(log N ) steps to achieve a nearly uniform distribution, how many slots are demanded in our case to ensure all MHRWs approach the nearly uniform distributions. Although this question has been (partially) answered in a quite different context in our previous work [33], we hereby provide a sketch of our specialized answer in Lemma 5.1.
By applying the Chernoff bound (see Theorem 3.1), agent i receives at most 2h·g(N ) tokens in each slot with probability at least 1 − 1 N h/3 , when N is sufficiently large such that g(N ) > ln N . Furthermore, considering we employ a FIFO forwarding policy, the tokens agent i receives in some slot t can be delayed for at most t additional slots. As a token should be forwarded for O(log N ) times to achieve a nearly uniform distribution, we conclude that with probability at least 1 − N −h/3 , all MHRWs in round r approach a 1 N 3 -nearly uniform distribution in ∆ = O(log 2 N ) slots, according to what we have shown in Sec. 3.3.1.
Remarks 5.1. It follows Lemma 5.1 that, in our disseminating stage, each agent needs to send O(g(N ) log 2 N ) messages, each of which has O(log N ) bits 5 . Therefore, we conclude that our algorithm has a per-round communication complexity of O(g(N ) log 3 N ) for each agent. According to our definition of g(N ) in Definition 3.3, the complexity can be re-written (with a slight relaxation) as O (N log 3 N ).

Convergence
The challenges for verifying the convergence of our algorithm are two-fold: on one hand, although our MHRWbased disseminating stage entails very efficient communications, each agent gets only incomplete knowledge from its peers; on the other hand, the agents introduce random perturbations to their knowledge (i.e., their adoptions) for the purpose of privacy preserving, such that the knowledge each agent learns from their peers is noisy. As [4] has shown the convergence of the learning dynamics by assuming each agent in round r is aware of the actual popularities of all the options, i.e., {Q r−1 j } j∈M , our focus is at demonstrating that, for each agent i in round r, its estimate on Q r−1 j , namely Q r i,j , sufficiently approximates Q r−1 j for ∀j. In the following, we first present our main results on the convergence of the regret function and then give the detailed proof.

Main Result
Theorem 5.1. Assuming η 1 ≥ η 2 ≥ · · · ≥ η m . Let 1 2 < β < e e+1 and define δ = ln β 1−β (hence δ > 0 and δ → 0). Let ε > 0, 6µ ≤ δ 2 , h = 16σ 1−β (with σ ≥ 11) and Supposing N is sufficiently large such that Remarks 5.2. In the above theorem, we give the answers to the two questions proposed in Sec. 1. It is revealed by Theorem 5.1 that, when there are a sufficiently large number of agents engaged in the learning process, there exists a constant upper-bound on the regret of our four-staged algorithm. Furthermore, the quantitative trade-off between the number of the agents (thus the communication overhead as shown in Sec. 5.1) and the privacy budget is also revealed in Theorem 5.1.

5.
More precisely, the length of the message should be O(M + log N ) (in bits). Nevertheless, throughout our analysis, we focus on investigating how large N should be given fixed M . In this sense, we consider M is a constant.

Detailed Proof
As shown in Sec. 4.3, in round r, each agent i selects an option as a candidate in the sampling stage according to µ and { Q r i,j } j∈M . Assuming Y r i,j is a binary variable indicating if agent i selects option j in the sampling stage in round r, the probability of Y r i,j = 1 conditioned on Q r i,j can be defined as and we thus have Let S r j = {i ∈ N | Y r i,j = 1} denote the set of the agents that select option j in the sampling stage of round r and S r j = N i=1 Y r i,j be the size of S r j . We calculate the conditional expectation of S r j as follows where Q r j = 1 N N i=1 Q r i,j . Given Q r j , according to the Chernoff bound, the following lemma holds as a straightforward extension of Proposition 4.6 in [4].

Lemma 5.2.
In each round r, for each option j , with probability at least 1 − 2M where δ = 30M ln N µN ≤ 1 2 . Moreover, for ∀j ∈ M, with probability at least 1 − 2m N 10 . As shown in Sec. 4, the probability of X r i,j = 1 (conditioned on S r j and Φ r j ) can be defined as Supposing D r j = i∈S r j X r i,j denote the number of agents adopting option j in round r, it follows that Especially, due to our assumption β > 1 2 , β Φ r j (1 − β) 1−Φ r j ≥ (1 − β). It follows [4] again that Lemma 5.3. In any round r, for any option j, with probability at least 1 − 4M N 10 (conditioned on S r j , Φ r j ), where δ = 60M ln N µN ≤ 1 2 . Combining Lemma 5.2 and Lemma 5.3 together, we derive the relation between D r j and Q r j for ∀j in Lemma 5.4.

Lemma 5.4.
In any round r, for any option j, with probability at least 1 − 6M N 10 (conditioned on Φ r j and Q r j ), Proof. The proof follows directly from Lemma 6.1 and Lemma 6.2, by noticing that (1 + 2δ )(1 + 2δ ) ≤ 1 + 2δ + 2δ + 4δ δ ≤ 1 + 6δ as δ ≤ δ ≤ 1 2 . Let D r j = N i=1 X r i,j be the number of the agents adopting option j in round r, and D r = M j=1 D r j is thus the number of the agents with non-null adoptions. We derive the lower bounds for Q r j and D r as follows. Lemma 5.5. For any round r and option j, with probability at least 1 − 6M N 10 , Proof. According to Lemma 5.4, with probability at least 1 − 6M N 10 , we have by considering δ ≤ 1 2 and β > 1 2 . Moreover, as M j=1 D r j ≤ N , Q r j can be re-written as Similarly, with probability at least 1 − 6M N 10 , we deduce that where the equality in the last step is due to the fact that Let V r be the set of all perturbed adoption vectors disseminated in round r 6 and V r i ⊆ V r be a subset which agent i samples in round r. We also suppose V r = D r hg(N ) and V r i denotes the size of V r and the one of V r i , respectively. Lemma 5.6. For each agent i, when N is sufficiently large such that N ≥ 4 ln N , the number of the sampled perturbed adoption vectors in round r, i.e., V r i , satisfies with a probability at least 1 − 6M +3 N 10 . Proof. Assume Z r i,k ∈ {0, 1} is a Bernoulli random variable indicating if the k-th token in round r arrives 6. As shown in Sec. 4.2, V r is formed by replicating each agent's perturbed adoption vector for hg(N ) times. at agent i through the random walk. V r i then can be represented as V r To facilitate our presentation, we defined the following two events , and thus P[E 1 (i, r)] ≥ 1 − 1 N h/3 (see Lemma 5.1) and P[E 2 (r)] ≥ 1 − 6M N 10 (see Lemma 5.5). According to the Chernoff-Hoeffding bound (see Theorem 3.1), N σ where we have the second inequality when the two events both hold and the last inequality due to the fact that 1 − 1 N 2 ≥ 3 4 when N ≥ 4 ln N . Taking the union bound across i ∈ N , we get When N is sufficiently large such that g(N ) ≥ 4 ln N , can be re-written as the inequality (23), by considering the facts Given the 1 N 3 -nearly uniform distribution in round r (with probability at least 1 − 1 N h/3 ), the following inequality holds for ∀i ∈ N and ∀j ∈ M Proof. Considering the nearly uniform distribution (with probability at least 1 − 1 N h/3 ), conditioned on V r , the probability that agent i samples V r i = v r i tokens in round r, [ X] j denote the number of the perturbed adoption vectors sampled by agent i in round r with the j-th component being 1, we then have by considering the nearly uniform distribution resulting from the random walk-based dissemination again. Moreover, due to Lemma 5.8. Let N be sufficiently large such that g(N ) < N , We have the following two inequalities hold in any round r with probability at least 1 − 6M +3 N 10 , with probability at least 1 −

6M +3
N 10 (as shown in Lemma 5.6), we have where we have the third inequality by applying the inequality (6) (shown in Theorem 3.4), the forth one due to the fact that g(N ) < N , and the last one by applying the Bernoulli inequality (see Theorem 3.3). Furthermore, since Likewise, when V r i ≤ 15hg(N ) 8 holds, we deduce that where we have the last inequality due to the fact that 1 + 1 N N ≤ e holds for any positive integer N . Fur- Lemma 5.9. Conditioned on the adoptions X r−1 = {X r−1 i } i∈N in round r−1, for each option j ∈ M in round r, with probability at least 1 − 10M +3 N 10 , According to perturbation process shown in Sec. 4.1, the Bernoulli probability for any X ∈ X r−1 to have Furthermore, since each agent i does not carry out the perturbation in round r if it has no option adopted in round r − 1, we have Applying the Hoeffding's inequality (see Theorem 3.2) and the union bound, we have Similarly, supposing there exists c r i,j ∈ [ξ 0 , ξ 1 ] for ∀i, j according to Lemma 5.7 such that E Λ r i,j V r i , X r = c r i,j Λ r j , we can deduce that As we have shown in Lemma 5.6 that with probability at least 1 − 6M +3 N 10 , V r i ≥ 3(1−β) 32 hg(N ) such that for any agent i and option j, with probability at least 1− 8M +3 N 10 (conditioned on X r ), we have and hence, Since by combining (28) and (31). It then follows that exp(ε/2) + 1 exp(ε/2) − 1 with N being sufficiently large such that g(N ) ≤ N , since where the last inequality holds when M ζ ≤ 1/2 (which we will prove in Lemma 5.10). Hence, for ∀i, j, with probability at least 1 − 10M +3 N 10 (conditioned on X r−1 ), and thus Q r j − Q r−1 We finally complete the proof by substituting (33) into the above one. exp(ε/2)+1 exp(ε/2)−1 and δ = ln β 1−β . In any round r, with probability at least 1 − 10M +3 N 10 , we have for any option j, where δ Q = c ln N g(N ) . Proof. From Lemma 5.5 and Lemma 5.9, it is shown that

Remarks 5.3. As shown by Definition 3.3, we have
approach zero when N becomes infinity. Therefore, when N → ∞ given fixed c, in any round r, the average estimate on option j's popularity, i.e., Q r j , approaches the actual popularity of the option j, namely Q r−1 j , as closely as possible.
We now are ready to prove our main result Theorem 5.1 following the thread shown in [4]. In particular, we investigate the dynamics of our learning algorithm by coupling it with the Multiplicative Weights Update (MWU) method. The MWU method is a very powerful tool in a wide spectrum of learning and optimization problems. By defining a weight W r j for ∀j, r as follows As shown in the following lemma, for ∀j, r, Q r j approaches P r j as closely as possible, especially when there are a infinite number of agents. for all choices of Φ r j 's. Proof. The proof proceeds by the inducting on r. It is apparent that P 0 j = Q 0 j for ∀j ∈ M. We assume that the statement holds for ∀r ≥ 1, such that P r j 1+δr ∼ Q r j with probability at least 1 − (10M +3)r N 10 for each option j in round r. Since j Furthermore, according to Lemma 5.4 and Lemma 5.10, we deduce that with probability at least 1 − (10M +3)(r+1) . Assuming that δ r = 5 r δ Q ≤ 1, δ Q ≤ 1 27 and δ ≤ 1 6 δ Q , we have (1 + δ r ) 2 (1 + 6δ ) 2 (1 + 2δ Q ) 2 ≤ 1 + δ r+1 hold for ∀r ≥ 2. For r = 1 the bound can be checked by a direct calculation.
As shown in [4], let 1 2 < β ≤ e e+1 (and thus 0 < δ ≤ 1) and 6µ ≤ δ 2 . With infinite population (i.e., N = ∞) and uniform initialization P 0 j = 1 M for ∀j, for T ≥ ln M δ 2 , Especially, when P 0 j ≥ τ (for ∀j ∈ M) is non-uniform, the inequality (38) still holds for R ≥ ln(1/τ ) According to the (stochastic) coupling between P r j and Q r j shown in Lemma 5.10, we can deduce that Therefore, When R = ln M δ 2 , 5 R δ Q ≤ M ln 5 δ 2 c ln N g(N ) . Therefore, when N is sufficiently large such that we can deduce that (41) which partially completes the proof of Theorem 5.1 with R = ln M δ 2 . The above result can be extended to handle nonuniform initiation by letting N be sufficiently large such that ln N ≥ c(1/τ ) (instead of (41)). When T = ln(1/τ ) for ∀j with probability at least 1 − 6M N 10 . We can choose to let τ = µ(1−β) 4M , such that where we add the item RM N 10 by taking into the fact that the above inequality condition (i.e., Q r j ≥ µ(1−β) 4M ) may not be satisfied in some rounds such that the resulting regret for the corresponding epoch (involving the rounds) is at most 1. Hence, when ln(1/τ ) We finally complete the proof of Theorem 5.1 by concluding all the conditions on N as shown in the above lemmas.

Privacy Preservation
Theorem 5.2. In each round, our perturbation mechanism F achieves ε-LDP for each agent.
Proof. According to our perturbing process (shown in Sec. 4.1), for any adoption vectors X 1 , X 2 ∈ {0, 1} M and any perturbed adoption vector X ∈ {0, 1} M , we have where · 1 denotes 1 -norm. Then, for ∀ X ⊆ {0, 1} M , Base on the above result about per-round privacy loss, we can directly apply the composition rule of LDP to conclude that the total privacy loss over R rounds is at most Rε ≤ N 10 δ 6M ε.

SIMULATIONS
In this section, we perform numerical simulations to evaluate the performance of our distributed privacy-preserving social learning algorithm.

Learn More if Paying More
We first investigate the convergence of our algorithm with different network sizes and choices of g(N ). According to Theorem 5.1, we have to properly define g(N ) such that ln N < g(N ) < N for sufficiently large N . Hence, we hereby take two typical functions g(N ) = ln 2 N and g(N ) = N 1 2 as example. The privacy budget, ε, is set to be ln 2. Moreover, we apply our algorithm to two networks consisting of 10 3 and 10 4 agents respectively. In our simulations, we let β = 0.505, M = 10, and σ = 15 such that all conditions on N can be respected. The converging trajectories of the regret function are presented in Fig. 1. It is shown that, all the regrets are upper-bounded by 6δ after convergence under the different settings, which is consistent with Theorem 5.1. Moreover, since each agent launches hg(N ) random walks to disseminate its perturbed adoption, while larger g(N ) implies each agent is able to learn more from its peers (with fixed h), our algorithm could have lower regret (and thus higher learning efficacy) with larger g(N ). This inference is validated as illustrated in Fig. 1. We hereby evaluate the adaptability of our algorithm to different numbers of options. Since we get similar results with different choices of g(N ), we only report the results we obtained by letting g(N ) = ln 2 N , especially considering the limited space. We hereby fix N = 10 3 and other parameters remaining the same as mentioned in Sec. 6.1. As shown in Fig. 2, the learning process converges faster with less options, since there is less knowledge to learn for the agents in this case. Fortunately, we achieve almost the same regret with different numbers of options, which reveals the scalability of our algorithm to M . As mentioned in Sec. 3.3.2, we can tune the privacy budget ε to leverage the "strength" of the privacy preserving. When ε is larger, more privacy loss is allowed such that we do not have to introduce much perturbation to the adoption vectors. As illustrated in Fig. 3 where we perform our algorithm with different privacy budgets, smaller ε is meant to higher regrets and lower convergence rates, as the agents may be "confused" by the perturbation. Nevertheless, as shown in Sec. 5.3, we obtain better privacy preservation with smaller ε.

Privacy vs. Efficacy
Youming Tao is currently an undergraduate student in Taishan College, Shandong University, Shandong, China. He mainly focuses on fundamental problems in decentralized machine learning algorithm design, distributed computing, mechanism design and privacy-preserving data analytics.
Shuzhen Chen received the BSc degree in 2019 from the School of Computer Science and Technology, Shandong University. She is currently a postgraduate student in Department of Computer Science and Technology, Shandong University. Her research interests include distributed computing, wireless and mobile security.

Feng Li received his BS and MS degrees in
Computer Science from Shandong Normal University, China, in 2007, and Shandong University, China, in 2010, respectively. He got his PhD degree (also in Computer Science) from Nanyang Technological University, Singapore, in 2015. From 2014 to 2015, he worked as a research fellow in National University of Singapore, Singapore. He then joined School of Computer Science and Technology, Shandong University, China, where he is currently an associate professor. His research interests include distributed algorithms and systems, wireless networking, mobile computing, and Internet of Things.