Distributed Learning with Strategic Users: A Repeated Game Approach
Year: 2021

Abstract:
We consider a distributed learning setting where strategic users are incentivized, by 1 a cost-sensitive fusion center, to train a learning model based on local data. The 2 users are not obliged to provide their true gradient updates and the fusion center 3 is not capable of validating the authenticity of reported updates. Thus motivated, 4 we formulate the interactions between the fusion center and the users as repeated 5 games, manifesting an under-explored interplay between machine learning and 6 game theory. We then develop an incentive mechanism for the fusion center based 7 on a joint gradient estimation and user action classification scheme, and study its 8 impact on the convergence performance of distributed learning. Further, we devise 9 an adaptive zero-determinant (ZD) strategy, thereby generalizing the celebrated ZD 10 strategy to the repeated games with time-varying stochastic errors. Theoretical and 11 empirical analysis show that the fusion center can incentivize the strategic users to 12 cooperate and report informative gradient updates, thus ensuring the convergence. 13

We consider a distributed learning setting where strategic users are incentivized, by1 a cost-sensitive fusion center, to train a learning model based on local data. The2 users are not obliged to provide their true gradient updates and the fusion center3 is not capable of validating the authenticity of reported updates. Thus motivated,4 we formulate the interactions between the fusion center and the users as repeated5 games, manifesting an under-explored interplay between machine learning and6 game theory. We then develop an incentive mechanism for the fusion center based7 on a joint gradient estimation and user action classification scheme, and study its8 impact on the convergence performance of distributed learning. Further, we devise9 an adaptive zero-determinant (ZD) strategy, thereby generalizing the celebrated ZD10 strategy to the repeated games with time-varying stochastic errors. Theoretical and11 empirical analysis show that the fusion center can incentivize the strategic users to12 cooperate and report informative gradient updates, thus ensuring the convergence.13
1 Introduction14
Distributed machine learning is becoming increasingly important in large-scale problems with data-15 intensive applications [18, 21, 25, 37]. Notably, federated learning has emerged as an attractive16 distributed computing paradigm that aims to learn an accurate model without collecting data from the17 owners and storing it in the cloud: The training data is kept locally on the computing devices which18 participate in the model training and report gradient updates (or its variants) based on local data [19].19
In this work, we study a distributed learning scheme in which privacy-aware users train a global model20 with a fusion center. We consider the users to be rational, self-interested and risk-neutral. The users21 are not compelled to contribute their resources unconditionally, unless they are sufficiently rewarded,22 and the system may reach a noncooperative Nash equilibrium where the users do not participate in23 training. This departs from conventional distributed learning schemes where the agents directly follow24 the lead of the fusion center (FC)1 and send their gradients. Since the users are strategic, a paramount25 objective for the FC is to design an effective reward mechanism to incentivize self-interested users to26 provide informative gradient updates. The repeated game enriches the distributed learning framework27 with the idea of many agents interacting within a common uncertain environment, and this framework28 provides a new perspective to specify how agents can strategically choose the learning updates how29 the resulting changes impact the performance of the learning efforts.30
Challenges and Contributions. There are a number of challenges in distributed learning with31 strategic users. First, the users are not obliged to entirely dedicate their resources and they may not32 fulfill their roles in the training of the algorithm if it were not for their own interest. Secondly, the33 FC cannot directly validate data driven gradient updates due to their stochastic nature. The quality34
1We refer to the fusion center as “she" and a user as “he".
Submitted to 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Do not distribute.
of the updates can vary over time and across the users since each user can control his own dataset.35 The interactions among users and the FC are repeated, and each user is capable of devising intricate36 strategies based on the past interactions. From a game-theoretic perspective, the fusion center’s ability37 to reciprocate against non-cooperative user actions is significantly restricted since she cannot directly38 observe the user actions. Finally, the FC is not allowed to impose penalties on the users and positive39 rewards are the only options at her disposal to incentivize user participation. The work proposed here40 is, to the best of our knowledge, the first distributed learning framework to consider these challenges.41
In this study, we model the interactions (in terms of gradient reporting and reward) between the42 FC and the users as repeated games, which intertwine with the updates in distributed learning. We43 propose a reward mechanism for the fusion center, based on an adaptive zero-determinant strategy,44 thereby generalizing the celebrated ZD strategy to the repeated games with time-varying stochastic45 errors. To tackle the challenge that the FC cannot directly verify the received reported gradients,46 we devise a gradient estimation and user action classification. Our findings demonstrate that, by47 employing adaptive ZD strategies, the FC can incentivize the strategic users to cooperate and report48 informative gradient updates, thus ensuing the convergence of distributed learning.49
Detailed discussion on related work is relegated to Appendix A, due to space limitation.50
2 Distributed Learning with Strategic Users as Repeated Games51
We consider a distributed learning setting with K strategic users K = {1, . . . ,K} and a fusion center52 (FC), and the optimization problem is given as follows:53
min θ∈Rn
F (θ) := 1
K K∑ k=1 EZk∼D [ L(θ;Zk) ] , (1)
where L(·) is the loss function. In each iteration, each user gets a mini-batch of s i.i.d. sam-54 ples from an unknown distribution D, and computes the stochastic gradient signal as Xk,t :=55 1 s ∑s i=1∇θL ( θt; z i k,t ) , where zik,t is the i th sampled data of user k at time t.56
Stage Game Formulation: Actions and Payoffs. The action and the reported signal of user k in57 iteration t are denoted with Bk,t ∈ {c, d} and Yk,t, respectively. As depicted in Fig. 1, a user is58 cooperative (Bk,t=c) if he is sending the privacy-preserved version of his gradient Xk,t. Otherwise,59 the user is defective and sends a noise signal Υk,t ∼ N (0,Ξt) independent of Xk,t:60
Yk,t = { Xk,t +Nk,t, if Bk,t = c (cooperative); Υk,t, if Bk,t = d (defective).
(2)
Remark 1. Note thatNk,t is independent ofXk,t andNk,t ∼ N (~0, ν2t I). If ‖∇θL(θ; z)‖2 ≤ ` for all61 θ and z, then this privacy-preservation mechanism enjoys t-differential privacy, with t = `2 / s2ν2t62 for mini-batch size s. The details are provided in Appendix.63
The payoff structure of a single interplay between the fusion center and a user is depicted in Fig 1b.64 In iteration t, when a user cooperates, he provides an information gain R to the FC at his privacy65 cost VUR with 0<VU≤1. When a user defects, he does not provide any information gain and does66 not incur any privacy cost. The FC may distribute rewards at the end of each iteration to incentivize67 the users. We denote the action of the FC toward user k as Ak,t ∈{C,D}. The FC is cooperative68 (Ak,t=C) if she makes a payment r to the user at her cost rVFC with 0<VFC≤1. The FC is defective69 (Ak,t=D), if she does not make any payment to the user. The factor VFC captures the difference in the70 valuation of the reward between the FC and the user; for instance, the reward can be a coupon which71 may be redeemed in the future. Denote the FC’s payoff vector by SFC =[R−rVFC,−rVFC, R, 0]72 and that of the users by SU =[r−VUR, r,−VUR, 0]. In this paper, we only analyze the case where73 R>rVFC and r > VUR. Otherwise, the FC or users do not have any incentive to cooperate.74
The FC cannot observe the actions of the users and her realized payoffs. We assume that users do75 not communicate or collude with each other. They cannot observe the actions of other users and the76 actions of the FC toward other users. Next, we will discuss how to devise effective strategies for the77 FC to incentivize cooperative user action for the repeated game in a cost-effective manner.78
Repeated Games between Users and Fusion Center. A salient feature of 2 × 2 repeated games79 is that players with longer memories of the history of the game have no advantage over those with80 shorter ones when each stage game is identically repeated infinite times [31]. Thus, without loss of81 generality, we assume the user strategies only depend on the outcomes of the last round. Let q1, q2, q382 and q4 denote the probabilities of cooperation for the user conditioned on the joint action pair of83 the previous iteration, that is (Ak,t−1, Bk,t−1), in the order of (C, c), (C, d), (D, c) and (D, d). The84 user’s strategy vector is defined as q = [q1, q2, q3, q4].85
Analogous to the user strategies, let p1, p2, p3 and p4 denote the probabilities of cooperation for86 the FC conditioned on (Ak,t−1, Bk,t), in the order of (C, c), (C, d), (D, c) and (D, d). The fusion87 center’s strategy vector is defined as p = [p1, p2, p3, p4]. The joint action pair of the user and the88 FC is considered as the state of the game in iteration t: (Ak,t, Bk,t). The strategy vectors p and q89 imply a Markov state transition matrix as follows:90
Ω = q1p1 (1− q1)p2 q1(1− p1) (1− q1)(1− p2)q2p1 (1− q2)p2 q2(1− p1) (1− q2)(1− p2)q3p3 (1− q3)p4 q3(1− p3) (1− q3)(1− p4) q4p3 (1− q4)p4 q4(1− p3) (1− q4)(1− p4)  . (3) Let Λ∗ be the stationary vector of the transition matrix Ω, i.e., Λ∗ = Λ∗Ω. We can find the expected91 payoffs of the FC and the user in the stationary state as s∗FC = Λ ∗S>FC and s ∗ U = Λ
∗S>U . The FC sets92 her strategy p satisfying, for some real values ϕ0, ϕ1 and ϕ2, the equation93
[p1 − 1, p2 − 1, p3, p4] = ϕ0SFC + ϕ1SU + ϕ21. (4) This class of strategies are called zero-determinant (ZD) strategies, which enforce a linear relation94 between the expected payoffs, given by ϕ0s∗FC+ϕ1s ∗ U+ϕ2 =0, regardless of the user strategy [31].95 Remark 2. The ZD strategy is a powerful tool to incentivize the users cooperation for the FC96 because she can unilaterally set s∗U or establish an extortionate linear relation between s ∗ U and s ∗ FC.97 Against such an FC strategy, the user’s best response which maximizes his payoff is full cooperation,98 q∗ = [1 1 1 1]. The details are provided in Appendix C.99
Against the FC who is equipped with the ZD strategy, the user can increase his expected payoff only100 by cooperating more often, and consequently his best response is full cooperation. Assuming that101 there are sufficiently many participating users, the FC has the absolute leverage against any single102 user who tries to negotiate with her. Nevertheless, the FC cannot directly employ the ZD strategy103 since she cannot observe the true actions of the users. In the next section, we will study the use of ZD104 strategy can be extended in the scope of distributed learning.105
3 Distributed Stochastic Gradient Descent with Strategic Users106
For the ease of exposition, in this paper we focus on an interesting variant of the classical stochastic107 gradient descent algorithm using the gradient signals reported by strategic users (SGD-SU). In each108 iteration, the FC collects the reported gradients of the users and update the model as follows:109
θt = θt−1 − ηt · m̂t(Yt), (5)
Algorithm 1: Stochastic Gradient Descent with Strategic Users (SGD-SU) 1 for t = 1, 2, . . . , T − 1 do 2 Fusion Center: broadcast the current iterate θt−1 to all the users 3 forall k ∈ {1, 2, . . . ,K} do
4 User k: compute the gradient Xk,t and Yk,t ← { Xk,t +Nk,t cooperative action, Υk,t defective action, 5 Fusion Center: form the gradient estimate m̂t(Yt)← 1
K(Λ1Ωt−1)q>
∑K k=1 Yk,t
6 update model parameter θt ← θt−1 − ηtm̂t(Yt)
7 classify the users B̂k,t (m̂t, Yk,t)←
{ ĉ (cooperative) if Y >k,tm̂t>‖ 12m̂t‖ 2 2
d̂ (defective) else (7)
8 compute the detection and false alarm probabilities using (8) and (11) 9 compute the adaptive strategies (9) and distribute the rewards accordingly
where Yt =[Y1,t . . . YK,t], ηt is the step size and m̂t is the gradient estimator. The FC cannot directly110 observe user actions and verify the reported gradients. This gives rise to two coupled challenges:111
• The gradient estimator m̂t should be resilient against the uninformative reports of defective users.112 • Although the ZD strategies are powerful tools to incentivize user cooperation, the FC cannot113 directly employ a ZD strategy because she cannot observe the users’ actions.114
To tackle these difficulties, we will first introduce a gradient estimation and user classification scheme115 and discuss the impact of user action classification errors on the dynamics of repeated games. As116 outlined in Algorithm 1. we will develop adaptive FC strategies which generalize the classical ZD117 strategies to the repeated games with time-varying stochastic errors.118
3.1 Joint Gradient Estimation and User Action Classification119
The stochastic gradients can be decomposed as Xk,t = mt+Wk,t where mt := ∇θF (θt) is the120 population gradient and Wk,t is the zero-mean noise term [30]. The unknown parameter mt is the121 mean of the reported gradient Yk,t when the user is cooperative (Bk,t = c). The defective users122 send zero-mean random noise as their reported gradients. The FC needs to classify the reported123 gradients and obtain an estimate of mt for the SGD-SU update in (5). These two problems are124 coupled with each other, and the joint scheme is, therefore, comprised of a gradient estimator m̂t,125 and a classification rule B̂k,t. To tackle this difficult problem, we first investigate gradient estimation.126
Let Λ1 be the initial state distribution of the games between the users and the FC. A modified127 empirical mean based gradient estimator can be employed as follows:128
m̂t(Yt) := 1
K(Λ1Ωt−1)q> ∑K k=1 Yk,t. (6)
It is easy to verify that m̂t(·) is an unbiased estimator if the FC is able to employ her strategies p129 without any errors and the state distribution of the repeated games are governed by the state transition130 matrix Ω as in (3) without any perturbations.131
Using the gradient estimator m̂t(·), the FC can form the user action classification rule as132
B̂k,t (m̂t(Yt), Yk,t) =
{ ĉ if Y >k,tm̂t > 1
2 ‖m̂t‖2,
d̂ else; (7)
where d̂ (or ĉ) is the defective (or cooperative) label. The noise in the stochastic gradients, Wk,t,133 can be approximated as a zero mean Gaussian r.v. [17, 22, 26, 36]. Recall from (2) that cooperative134 users send the privacy-preserved versions of their gradient. This implies Yk,t∼N (mt,Σt), given135 Bk,t = c, where Σt := cov[Wk,t]+ν2t I. Thus, the detection and false alarm probabilities of the136 classifier, denoted by Φt and Ψt respectively, can be found as137
Φt = 1−Q
( m>t m̂t −
1 2 ‖m̂t‖2√
m̂>t Σtm̂t
) and Ψt = Q ( 1 2 ‖m̂t‖2√ m̂>t Ξtm̂t ) . (8)
Remark 3. The linear classifier (7) is an effective tool under the homoscedasticity assumption. If138 that is violated, the FC can employ different classifiers. The details are provided in Appendix for the139 Classifier Design.140
In the next subsection, we discuss how the FC can devise her strategies building on the joint gradient141 estimation and user action classification scheme.142
3.2 Adaptive Strategies for Fusion Center143
Although the ZD strategies, p, provide the FC an efficient and powerful mechanism to encourage144 the user’s cooperation; the FC cannot directly use p since they are conditioned on the user’s ac-145 tion, Bk,t, which is not observable to her. Alternatively, the FC can use the classification results146 after carefully adapting her strategies to mitigate the adverse effects of inevitable classification147 errors. Let πt,1, πt,2, πt,3 and πt,4 denote the probabilities of cooperation for the FC conditioned148 on (Ak,t−1, B̂k,t), in the order of (C, ĉ), (C, d̂), (D, ĉ) and (D, d̂). These are referred to as adaptive149 strategies and the FC sets these probabilities satisfying the following system of equations:150
p1 = πt,1Φt + πt,2(1− Φt), p2 = πt,1Ψt + πt,2(1−Ψt), p3 = πt,3Φt + πt,4(1− Φt), p4 = πt,3Ψt + πt,4(1−Ψt).
Suppose Φt Ψt ≥ p1 p2 and Φt Ψt ≥ p3 p4 . Then the unique solution to the system above is given by151
πt,1 = p1(1−Ψt)− p2(1− Φt)
Φt −Ψt , πt,2 = p2Φt − p1Ψt Φt −Ψt , (9a)
πt,3 = p3(1−Ψt)− p4(1− Φt)
Φt −Ψt , πt,4 = p4Φt − p3Ψt Φt −Ψt . (9b)
Remark 4. If the FC directly employed the ZD strategies without any adaptation, i.e., she cooperates152 with probability pi conditioned on classification output; the repeated games may not converge to153 the stationary state Λ∗ and a linear relation between the expected payoffs (4) may not be enforced154 because the classification errors yield an additive disturbance on the state transition matrix as follows155
156
Ω− (p1 − p2) { q>[1−Φt 0 1−Φt 0] + (1− q)>[0 Ψt 0 Ψt] } . (10)
Adaptive strategies (9) cancel out this adverse disturbance on the dynamics of the repeated games.157
In the absence of classification errors (Φt=1 and Ψt=0), the adaptive strategies reduce to the ZD158 strategies, i.e., πt = p. Classification errors force the FC to be more retaliatory than dictated by the159 ZD strategy p, i.e., πt,1>p1, πt,3>p3, πt,2<p2 and πt,4<p4. In general, detection and false alarm160 probabilities, Φt and Ψt, are time-varying; thus the adaptive strategies also change over time.161
3.3 The Impact of Estimation Errors on Repeated Game Dynamics162
The proposed adaptive strategies (9) requires the knowledge of detection probability, Φt. However,163 the FC cannot exactly compute Φt using (8) since she does not have the knowledge of mt. Instead,164 she can form her estimate Φ̂t using m̂t:165
Φ̂t = 1−Q ( 1 2 ‖m̂t‖2√ m̂>t Σtm̂t ) (11)
Due to the inevitable gradient estimation errors, in general, we have Φ̂t 6= Φt. As a result, the FC166 cannot exactly employ the adaptive FC strategies dictated by Eq. 9. With several steps of variable167 substitutions, this yields an additive perturbation on the state transition matrix as follows:168
Ω̃t = Ω + VtΩ ⊥ with Vt := Φ̂t − Φt Φ̂t −Ψt and Ω⊥ := (p1 − p2)q>[−1 0 1 0]. (12)
Let Λ̃t be the probability distribution over the state space of the games {Cc,Cd,Dc,Dd} at the start169 of iteration t. According to (12), the state distributions follow the transition rule such that170
Λ̃t+1 = Λ̃tΩ̃t = Λ̃t ( Ω + VtΩ ⊥) .
Note that Λt can be considered as the state distribution of the repeated games in the absence of171 perturbations on the state transition matrix. For the FC, Λt is the designed state distribution in which172 the ZD strategy dominates against any user strategy.173
Next, we study the time-varying perturbation terms. Using (8) and (11), Vt can be found as2:174
Vt= Φ̂t−Φt Φ̂t−Ψt =
Q ( m̂>t ( mt− 12 m̂t ) √ m̂>t Σtm̂t ) −Q ( 1 2 ‖m̂t‖2√ m̂>t Σtm̂t )
1−Q (
1 2 ‖m̂t‖2√ m̂>t Σtm̂t
) −Q ( 1 2 ‖m̂t‖2√ m̂>t Ξtm̂t
)= Q ( m̂t(mt−̂mt) ‖mt‖ + 1 2 ‖m̂t‖√ Ray(Σt, m̂t) ) −Q ( 1 2 ‖m̂t‖√ Ray(Σt, m̂t) ) 1−Q ( 1 2 ‖m̂t‖√
Ray(Σt, m̂t)
) −Q ( ‖mt‖√
Ray(Ξt, m̂t)
) .
In the presence of these perturbations, to establish stability guarantees on the dynamics of the repeated175 games, we impose the following assumption on the norm of the gradient estimator:176
Assumption 1. We assume that ‖m̂t‖≥max { 2 √ Ray(m̂t,Σt), 2 √ Ray(m̂t,Ξt), √ m̂>t (mt−m̂t) } .177
Note that these conditions are primarily associated to the accuracy of the linear classifier (7) which178 operates effectively when the mean vectors of the classes are sufficiently separated. The following179 result indicates that, due to the perturbations on the state transition matrix, the real state distribution180 Λ̃t is a noisy version of Λt.181
Lemma 1. Let Λ1 denote the initial state distributions of the games between the FC and the users.182 Under Assumption 1, we have that183
Λ̃t = Λt + Λ1 ∑t−1
i=1 ViΩ
i−1Ω⊥Ωt−1−i. (13)
This noise on the state distributions will manifest as a novel bias term in the gradient estimation. In184 the next subsection, we will provide the convergence analysis of SGD-SU which will mainly focus185 on the characterization of this bias term.186
3.4 Convergence Results187
In this section, we provide the convergence guarantee for SGD-SU (5). Let Ft denote the σ-algebra,188 generated by {θ1,Yi, i < t}. In particular, Ft should be interpreted as the history of SGD-SU up to189 iteration t, just before Yt is generated. Thus, conditioning on Ft can be thought of as conditioning190 on {θ1, Λ̃1,Y1, . . . , θt−1, Λ̃t−1,Yt−1, θt, Λ̃t}. For convenience, denote Et[·] := Et[·|Ft]. Observe191 that, we can decompose the gradient estimator m̂t as follows:192
m̂t(·) = mt(1 + ζt) + Et, (14)
where ζt is the estimation bias term due to the perturbations on the state transition matrix, given by193
ζt = 1
mt (Et[m̂t]−mt) =
∑K k=1 P(Bk,t = c|Ft)
K(Λtq>) − 1
and Et is the estimation noise term, given by Et=m̂t−Et[m̂t]. Conditioned on Ft, the probability of194 a user taking the cooperative action, in iteration t, is given by P(Bk,t=c|Ft)=Λ̃tq>. The bias term,195 ζt, can be found as follows:196
ζt = Λ̃tq>
Λtq> − 1. (15)
From Lemma 1 and (15), it is clear that the perturbations on the state transition matrix (12), directly197 translates into a bias in the gradient estimation rule.198
To establish convergence guarantees for the SGD-SU in (5), Λtq> and Λ̃tq> must meet the following199 criteria during the course of the algorithm:200
Assumption 2. We assume that Λtq> > 12 and Λ̃tq > > 0, for all t ∈ {1, 2, . . . , T}.201
2The Rayleigh’s quotient for a symmetric matrix M and nonzero vector x is defined as Ray(M,x) = x>Mx
x>x
The first condition Λtq> ≥ 0.5 is very mild in the sense that it merely requires that the probability202 of user cooperation dictated by the memory-1 strategies p and q (1 × 4 vectors), in the absence203 of perturbations, is larger than 0.5. The second condition Λ̃tq> > 0 states that, in the presence of204 perturbations, the probability of user cooperation is always positive3.205
By Assumption 2, there exists a positive constant HT such that206
0 < |ζt| < HT < 1, ∀t ∈ {1, . . . , T}. (16) Further, we have the following lemma characterizing the properties of estimation noise.207 Lemma 2. Conditioned on Ft, the estimation noise in iteration t, denoted Et, is a zero-mean random208 vector with the mean square error given by209
Et[‖Et‖2] = 1 K ( Λtq> ) ((ζt + 1)tr (Σt − Ξt) + 1Λtq> tr (Ξt)) . (17) By (16) and (17), we have that210
Et [ ‖Et‖2 ] ≤ ET
K with ET :=
1
Λtq>
[( HT + 1 ) tr(Σt − Ξt) + 1
Λtq> tr(Ξt)
] . (18)
We impose the following assumption on the objective function, which is standard for performance211 analysis of stochastic gradient-based methods [3, 28].212 Assumption 3. The objective function F and the SGD-SU satisfy the following:213
(i) F is L−smooth, that is, F is differentiable and its gradient is L−Lipschitz:214 ‖∇F (θ)−∇F (θ′)‖ ≤ L‖θ − θ‖, ∀θ, θ′ ∈ Rn.
(ii) The sequence of iterates {θt} is contained in an open set over which F is bounded below by215 a scalar Finf .216
Our next result describes the behavior of the sequence of gradients of F when fixed step sizes are217 employed.218 Theorem 1. Under Assumptions 2 and 3, suppose that the SGD-SU (5) is run for T iterations with a219 fixed stepsize β̄ satisfying220
0 < β̄ ≤ 1 L(1 +HT ) . (19)
Then, the SGD algorithm with strategic users satisfies that221 E [ 1
T ∑T t=1 ‖∇F (θt)‖2 ] ≤ LET K(1−HT ) + 2(F (θ1)− Finf) β̄T (1−HT ) .
Theorem 1 illustrates the impact of the perturbations on the state transition matrix (12) on the222 convergence rate of SGD-SU. When HT is close to 0, SGD-SU performs similar to the basic223 minibatch SGD. On the other hand, if HT is close to 1, the optimality gap may be large. Our next224 result will characterize the gradient estimation bias term ζt. First, we have the following assumption225 on the state transition matrix Ω.226 Assumption 4. The state transition matrix Ω can be diagonalized as Ω = ΓUΓ−1 with U has the227 eigenvalues of Ω in descending order of magnitude: 1≥|u2| ≥ |u3| ≥ |u4| ≥ 0.228
Denote the element of Γ−1 in the ith row and jth column as Γ−1ij . Denote the four rows of Γ −1 by229 ~γ1, . . . , ~γ4. Next, we define δ as230
δ := ( max
j∈{2,3,4} ∣∣Γ3j − Γ1j∣∣)( max j∈{2,3,4} ∣∣~γjq>∣∣2). Further, the first order Taylor approximation of the scalar variable Vt can be found as follows:231
Vt= m>t (m̂t−mt) ‖mt‖2 ht(mt) with ht(mt) :=
‖mt‖√ 2πRay(Σt,mt) exp
( − 1
8
‖mt‖2
Ray(Σt,mt)
)
1−Q (
‖mt‖ 2 √ Ray(Σt,mt)
) −Q ( ‖mt‖
2 √ Ray(Ξt,mt) ) . (20) 3A sufficient condition for this requirement is that user strategies are forgiving in nature, i.e., q1, q2, q3, q4 > 0.
Define hmaxt := maxi∈{1,...,t} hi(mi). Our next result indicates that, the estimation bias term ζt can232 be found in terms of the past gradient estimation errors.233 Theorem 2. Under Assumptions 1, 2 and 4, the gradient estimation bias term ζt, can be found as234
ζt = (p1 − p2) ∑t−1
i=1
Λiq > Λtq> m>i Ei ‖mi‖2 hi(mi)∆i,t (21a)
with235 |∆i,t| ≤ δ|u2|t−1−i + δ2hmaxt−1 |u2|t−2−i(t− i− 1). (21b)
Further, for some 0 < η < 1 we have236 P (|ζt| < η|α1, . . . , αt−1) > 1− ∑t−1 i=1 α 2 i
Kη2 (22a)
with237
α2i = 2
∣∣∣∣(ν2i − ξ2i ) + m>i Σimi‖mi‖2 ∣∣∣∣+ ξ2iΛiq>
‖mi‖2 ( Λiq> ) [Λiq> Λtq> ]2 h2i∆ 2 i,t. (22b)
Note that Eq. (21) indicates that, the estimation bias term ζt can be expanded in terms of past gradient238 estimation errors. We prove that the absolute values of the coefficients, |∆i,t|’s, are bounded as239
|∆i,t| ≤ δ|u2|t−1−i + δ2hmaxt−1 |u2|t−2−i(t− i− 1),
where u2 is the eigenvalue of Ω with the second highest absolute value. Since Ω is a row stochastic240 matrix, |u2| ≤ 1. When |u2| is strictly less than 1, ∆i,t’s decay fast as t− i grows. This can also be241 interpreted as the impact of past gradient estimation errors fade away quickly. Using this result, in242 Eq.(22), we derive a high probability upper bound on the estimation bias term ζt.243
4 Experiments244
In this section, we evaluate the performance of SGD-SU (5) using real-life datasets. All the results in245 the preceding section assert convergence for the SG method (5) under the assumption that the FC can246 access Σt and Ξt. In a real-life machine learning setting with strategic users, this information may247 not be available to the FC. For convenience, define K̂ct and K̂dt as the sets of users who are classified248 as cooperative (ĉ) and defective (d̂ ) at iteration t. Based on the user action classification, the FC can249 form her estimates for the covariance matrices under the cooperative and defective actions as follows:250
Σ̂t = 1
|K̂ct | ∑ k∈K̂ct ( Yk,t−Ȳ ct ) ( Yk,t−Ȳ ct )> and Ξ̂t = 1 |K̂dt | ∑ k∈K̂dt ( Yk,t − Ȳ dt )( Yk,t − Ȳ dt )> , (23)
where Ȳ ct = 1 |K̂ct | ∑ k∈K̂ct Yk,t and Ȳ dt = 1 |K̂dt | ∑ k∈K̂ct Yk,t.251
In our first set of experiments, we consider a binary logistic classification problem and use the KDD-252 Cup 04 dataset [6]. The goal of binary logistic classification experiments is to learn a classification253 rule that differentiates between two types of particles generated in high energy collider experiments254 based on 78 attributes [6]. In our second set of experiments, we consider a neural network trained on255 the MNIST dataset. The number of users is chosen as K = 50 and mini-batch size is s = 10. In the256 experiments, we have tested the performance of two different ZD strategies, namely equalizer and257 extortion[31].258
For the logistic classification problem, Fig. 4a and 4b, depict the optimality gap under four different259 user strategies: q = [0.9 0.15 0.9 0.15] (stubborn), q = [0.9 0.9 0.15 0.15] (tit-for-tat, ), q =260 [0.9 0.15 0.15 0.9] (win-stay-lose-switch) and q = [0.9 0.9 0.9 0.9] (full cooperation). For the full261 cooperation, coin toss, tit-for-tat and stubborn user strategies, SGSU converges quickly. For Pavlov262 user strategies, SGSU can eventually approach, albeit more slowly than other cases. Fig 4c and 4d263 illustrate the probability of user cooperation, Λ̃tq>, across different user strategies. The experimental264 results validate Lemma 1 and the empirical user cooperation probabilities match the theoretical except265 when the users are Pavlov. Unsurprisingly, when the users follow full cooperation (or coin toss)266 strategy, they cooperate with probability 0.9 (or 0.5) regardless of the actual states of the repeated267
games. For the cases with stubborn and tit-for-tat users, the games quickly converge to the steady268 state distribution. Interestingly, for the cases with Pavlov users, the probability of user cooperation269 decreases over time. This is associated to the performance of the linear classifier. For the image270 classification problem, Fig 4e-h depict the training loss and testing accuracy across iterations for271 different FC and user strategies. In all experiments, SGSU converges in the presence of strategic272 users. Further details regarding the Experimental results are relegated to Appendix.273
5 Future Directions274
In this work, we study a distributed learning framework where strategic users train a learning model275 with a fusion center. The main objective of the FC is to encourage users to be cooperative by276 distributing rewards. Based on this, we devise a reward mechanism for the FC based on the ZD-277 strategies. Further, we examine the performance of SGD algorithm in the presence of strategic users.278 Our findings reveal that the algorithm has provable convergence and our empirical results verify our279 theoretical analysis.280
We are also working on the development of robust estimation tools in distributed learning with281 strategic users. The geometric median is a reliable estimation technique when the collected data282 contain outliers of large magnitude [10, 14, 24, 27]:283
Med(Yt) := arg min y∈Rn ∑K k=1 ‖y − Yk,t‖2. (24)
The FC can use Med as a robust gradient estimator, especially when the variance of the uninformative284 signals, ξ2t , reported by the defective users, is very high. The geometric median (24) can be computed285 by the Weiszfeld’s algorithm [34, 35], which is a special case of iteratively reweighted least squares.286 In contrast, with the knowledge of q, the modified sample mean estimator (6) allows the FC to trade287 robustness for overall tractability of the algorithm with reduced computational complexity.288
The linear classifier is vulnerable to vanishing gradients as the stochastic gradient descent algorithm289 with strategic users (SGD-SU) converges to θ∗. This can be addressed by modifying the classifier290 to incorporate the information contained in the norm of the reported gradients. Furthermore, we291 discuss how to extend the convergence guarantee for SGSU to allow heterogeneous user strategies.292 The details are presented in Appendix.293
References294
[1] ALISTARH, D., ALLEN-ZHU, Z., AND LI, J. Byzantine stochastic gradient descent. In295 Advances in Neural Inform. Proc. Systems 31 (2018), NIPS’18, pp. 4613–4623.296
[2] BLANCHARD, P., EL MHAMDI, E. M., GUERRAOUI, R., AND STAINER, J. Machine learning297 with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Inform. Proc.298 Systems 30 (2017), NIPS’17, pp. 119–129.299
[3] BOTTOU, L., CURTIS, F. E., AND NOCEDAL, J. Optimization methods for large-scale machine300 learning. SIAM Review 60, 2 (2018), 223–311.301
[4] CAI, Y., DASKALAKIS, C., AND PAPADIMITRIOU, C. Optimum statistical estimation with302 strategic data sources. Journal of Machine Learning Research 40, 2015 (2015), 1–17.303
[5] CARAGIANNIS, I., PROCACCIA, A. D., AND SHAH, N. Truthful univariate estimators. 33rd304 International Conference on Machine Learning, ICML 2016 1 (2016), 200–210.305
[6] CARUANA, R., JOACHIMS, T., AND BACKSTROM, L. Kdd-cup 2004: Results and analysis.306 SIGKDD Explor. Newsl. 6, 2 (Dec. 2004), 95–108.307
[7] CHEN, Y., IMMORLICA, N., LUCIER, B., SYRGKANIS, V., AND ZIANI, J. Optimal data308 acquisition for statistical estimation. In Proceedings of the 2018 ACM Conference on Economics309 and Computation (New York, NY, USA, 2018), EC ’18, Association for Computing Machinery,310 p. 27–44.311
[8] CHEN, Y., PODIMATA, C., PROCACCIA, A. D., AND SHAH, N. Strategyproof Linear312 Regression in High Dimensions. In Proceedings of the 2018 ACM Conference on Economics313 and Computation (New York, NY, USA, jun 2018), vol. 76, ACM, pp. 9–26.314
[9] CHEN, Y., SU, L., AND XU, J. Distributed statistical machine learning in adversarial settings:315 Byzantine gradient descent. Proc. ACM Meas. Anal. Comput. Syst. 1, 2 (Dec. 2017).316
[10] COHEN, M. B., LEE, Y. T., MILLER, G., PACHOCKI, J., AND SIDFORD, A. Geometric317 median in nearly linear time. In Proc. ACM Symp. on Theory of Comp. (New York, NY, USA,318 2016), STOC ’16, ACM, p. 9–21.319
[11] CUMMINGS, R., IOANNIDIS, S., AND LIGETT, K. Truthful linear regression. Journal of320 Machine Learning Research 40, 2015 (2015), 1–36.321
[12] DEKEL, O., FISCHER, F., AND PROCACCIA, A. D. Incentive compatible regression learning.322 Journal of Computer and System Sciences 76, 8 (2010), 759–777.323
[13] DWORK, C. Differential privacy. In Proc. Int. Conf. Automata, Languages and Programming -324 Volume Part II (Berlin, Heidelberg, 2006), ICALP’06, Springer-Verlag, pp. 1–12.325
[14] FLETCHER, P. T., VENKATASUBRAMANIAN, S., AND JOSHI, S. Robust statistics on rieman-326 nian manifolds via the geometric median. In 2008 IEEE Conference on Computer Vision and327 Pattern Recognition (2008), pp. 1–8.328
[15] HAO, D., RONG, Z., AND ZHOU, T. Extortion under uncertainty: Zero-determinant strategies329 in noisy games. Phys. Rev. E 91 (May 2015), 052803.330
[16] HORN, R., HORN, R., AND JOHNSON, C. Matrix Analysis. Cambridge University Press, 1990.331
[17] JASTRZKEBSKI, S., KENTON, Z., ARPIT, D., BALLAS, N., FISCHER, A., BENGIO, Y., AND332 STORKEY, A. J. Three factors influencing minima in SGD. arXiv:1711.04623v3 [cs.LG] (Nov.333 2017).334
[18] JORDAN, M. I., LEE, J. D., AND YANG, Y. Communication-efficient distributed statistical335 inference. Journal of the American Statistical Association 114, 526 (2019), 668–681.336
[19] KONEČNÝ, J., MCMAHAN, H. B., RAMAGE, D., AND RICHTARIK, P. Federated optimization:337 Distributed machine learning for on-device intelligence. arXiv:1610.02527 [cs.LG] (Oct. 2016).338
[20] KONG, Y., SCHOENEBECK, G., TAO, B., AND YU, F.-Y. Information elicitation mechanisms339 for statistical estimation. Proceedings of the AAAI Conference on Artificial Intelligence 34, 02340 (Apr. 2020), 2095–2102.341
[21] LI, M., ANDERSEN, D. G., PARK, J. W., SMOLA, A. J., AHMED, A., JOSIFOVSKI, V., LONG,342 J., SHEKITA, E. J., AND SU, B.-Y. Scaling distributed machine learning with the parameter343 server. In Proc. of the 11th USENIX Conf. on Operating Systems Design and Implementation344 (USA, 2014), OSDI’14, USENIX Association, p. 583–598.345
[22] LIN, T., STICH, S. U., PATEL, K. K., AND JAGGI, M. Don’t use large mini-batches, use local346 sgd. In Int. Conf. Learning Representations (2020), ICLR’20.347
[23] LIU, Y., AND WEI, J. Incentives for Federated Learning: A Hypothesis Elicitation Approach.348 arXiv:2007.10596v1 [cs.LG] (July 2020).349
[24] LOPUHAA, H. P., AND ROUSSEEUW, P. J. Breakdown points of affine equivariant estimators350 of multivariate location and covariance matrices. Ann. Statist. 19, 1 (03 1991), 229–248.351
[25] LOW, Y., BICKSON, D., GONZALEZ, J., GUESTRIN, C., KYROLA, A., AND HELLERSTEIN,352 J. M. Distributed graphlab: A framework for machine learning and data mining in the cloud.353 Proc. VLDB Endow. 5, 8 (Apr. 2012), 716–727.354
[26] MANDT, S., HOFFMAN, M. D., AND BLEI, D. M. A variational analysis of stochastic gradient355 algorithms. In Proc. Int. Conf. Machine Learning (2016), vol. 48 of ICML’16, JMLR.org,356 p. 354–363.357
[27] MINSKER, S. Geometric median and robust estimation in banach spaces. Bernoulli 21, 4 (11358 2015), 2308–2335.359
[28] NEMIROVSKI, A., JUDITSKY, A., LAN, G., AND SHAPIRO, A. Robust stochastic approxima-360 tion approach to stochastic programming. SIAM J. on Optimization 19, 4 (2009), 1574–1609.361
[29] NG, K. L., CHEN, Z., LIU, Z., YU, H., LIU, Y., AND YANG, Q. A multi-player game for362 studying federated learning incentive schemes. In Proceedings of the Twenty-Ninth International363 Joint Conference on Artificial Intelligence, IJCAI-20 (7 2020), C. Bessiere, Ed., International364 Joint Conferences on Artificial Intelligence Organization, pp. 5279–5281.365
[30] POLYAK, B. T., AND JUDITSKY, A. B. Acceleration of stochastic approximation by averaging.366 SIAM Journal on Control and Optimization 30, 4 (1992), 838–855.367
[31] PRESS, W. H., AND DYSON, F. J. Iterated prisoner’s dilemma contains strategies that dominate368 any evolutionary opponent. Proc. Natl. Acad. Sci 109, 26 (2012), 10409–10413.369
[32] RICHARDSON, A., FILOS-RATSIKAS, A., AND FALTINGS, B. Budget-Bounded Incentives for370 Federated Learning. Springer International Publishing, Cham, 2020, pp. 176–188.371
[33] SU, L., AND XU, J. Securing distributed gradient descent in high dimensional statistical372 learning. SIGMETRICS Perform. Eval. Rev. 47, 1 (Dec. 2019), 83–84.373
[34] VARDI, Y., AND ZHANG, C.-H. The multivariate L1-median and associated data depth. Proc.374 Natl. Acad. Sci. 97, 4 (2000), 1423–1426.375
[35] WEISZFELD, E. Sur un probléme de minimum dans l’espace. Tohoku Math. J. 42 (1936),376 274–280.377
[36] XING, C., ARPIT, D., TSIRIGOTIS, C., AND BENGIO, Y. A Walk with SGD. arXiv:1802.08770378 [stat.ML] (Feb. 2018).379
[37] XING, E. P., HO, Q., XIE, P., AND WEI, D. Strategies and principles of distributed machine380 learning on big data. Engineering 2, 2 (2016), 179 – 195.381
Checklist382
1. For all authors...383 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s384 contributions and scope?385 (b) Did you describe the limitations of your work?386 (c) Did you discuss any potential negative societal impacts of your work?387 (d) Have you read the ethics review guidelines and ensured that your paper conforms to388 them?389 2. If you are including theoretical results...390
(a) Did you state the full set of assumptions of all theoretical results?391 (b) Did you include complete proofs of all theoretical results? Proofs are included in the392 Appendix.393 3. If you ran experiments...394
(a) Did you include the code, data, and instructions needed to reproduce the main experi-395 mental results (either in the supplemental material or as a URL)? The code is included396 in supplementary material complying to NeurIPS instructions with details on how to397 run the code.398
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they399 were chosen)?400
(c) Did you report error bars (e.g., with respect to the random seed after running experi-401 ments multiple times)?402
(d) Did you include the total amount of compute and the type of resources used (e.g., type403 of GPUs, internal cluster, or cloud provider)? The hardware used is described in the404 Appendix405
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...406 (a) If your work uses existing assets, did you cite the creators?407 (b) Did you mention the license of the assets?408 (c) Did you include any new assets either in the supplemental material or as a URL? Our409 code is included in the supplementary material.410 (d) Did you discuss whether and how consent was obtained from people whose data you’re411 using/curating?412 (e) Did you discuss whether the data you are using/curating contains personally identifiable413 information or offensive content?414 5. If you used crowdsourcing or conducted research with human subjects...415
(a) Did you include the full text of instructions given to participants and screenshots, if416 applicable?417
(b) Did you describe any potential participant risks, with links to Institutional Review418 Board (IRB) approvals, if applicable?419
(c) Did you include the estimated hourly wage paid to participants and the total amount420 spent on participant compensation?421

Review summaries:
The paper formulates the interaction between the fusion center (FC) and users in distributed learning (or federated learning) from the perspective of game theory. In order to encourage the users to provide effective information to the FC for model update, the FC adopt zero-determinant (ZD) strategy, associated with which there are some practical issues addressed by the authors. Theoretical analysis on the convergence of the proposed algorithm is presented. 

This paper proposed an incentive mechanism for a distributed learning setting. The users are encouraged but not obliged to provide the gradient. The results on convergence and an upper bound on the estimation bias of the gradient were shown. 

This paper studies the incentives in distributed learning, where the users can choose to join the cooperation or not. The paper formalizes this problem as a two-player game between the fusion center and the user, designs a strategy to learn and provides a convergence guarantee. The contributions include: 1. formalizing of a reward mechanism between FC and users; 2. proposing a strategy for the FC to make users join the cooperation, where FC cannot observe users' actions; 3. providing theoretical guarantee on the convergence rate.

The paper studies a federated learning scheme for training machine learning models using gradients provided by a set of strategic users. At each iteration, each user gets a mini-batch of samples, computes her gradient, and decides whether to report it to the fusion center (FC) or to report a random signal.  The authors propose a strategy for the FC which incentivizes users to truthfully report their gradients and ensure convergence guarantees. Results are validated experimentally on publicly available datasets.