Distributed Learning with Strategic Users: A Repeated Game Approach
Authors: Abdullah Basar Akbay
Junshan Zhang
Venue: NeurIPS 2021 Submitted (2021)

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

20 In this work, we study distributed learning scheme in which privacy- aware users train global model with a fusion center. We consider the users be rational, self-interested and risk-neutral. The users 22 are not compelled to contribute their resources unconditionally. unless they are sufficiently rewarded, Distributed Learning with Strategic Users: A Repeated Game Approach
Anonymous Author(s)
Affiliation
Address email
Abstract
We consider a distributed learning setting where strategic users are incentivized, by cost-sensitive fusion center, to train learning model based on local data. The users are not obliged to provide their true gradient updates and the fusion center is not capable of validating the authenticity reported updates. Thus motivated, we formulate the interactions between the fusion center and the users repeated games, manifesting an under-explored interplay between machine learning and game theory. We then develop an incentive mechanism for the fusion center based on a joint gradient estimation and user action classification scheme, and study its impact on the convergence performance of distributed learning. Further, devise an adaptive zero-determinant (ZD) strategy, thereby generalizing the celebrated ZD strategy to the repeated games with time-varying stochastic errors. Theoretical and empirical analysis show that the fusion center can incentivize the strategic users to cooperate and report informative gradient updates, thus ensuring the convergence.
2
6
8
10
12
Introduction
14
15
Distributed machine learning is becoming increasingly important in large-scale problems with data- attractive
intensive applications [18, 21, 25, 37). Notably, federated learning has emerged distributed computing paradigm that aims to learn an accurate model without collecting data from the owners and storing it in the cloud: The training data is kept locally the computing devices which participate in the model training and report gradient updates (or variants) based on local data [19].
17
19
21
23 and the system may reach noncooperative Nash equilibrium where the users do not participate in
24 training. This departs from conventional distributed learning schemes where the agents directly follow
25 the lead of the fusion center (FC) and send their gradients. Since the users are strategic, paramount
25 objective for the FC is to design effective reward mechanism to incentivize self-interested users to provide informative gradient updates. The repeated game enriches the distributed learning framework
27
28 with the idea of many agents interacting within a common uncertain environment, and this framework provides a new perspective to specify how agents can strategically choose the learning updates how the resulting changes impact the performance of the learning efforts.
29
31 Challenges and Contributions. There are a number of challenges in distributed learning with
32 strategic users. First, the users are not obliged to entirely dedicate their resources and they may not
33 fulfill their roles in the training of the algorithm if were for their own interest. Secondly, the
34 FC cannot directly validate data driven gradient updates due to their stochastic nature. The quality
We refer the fusion center "she" and user as "he".
Submitted to 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Do not distribute.

---

Fusion Center
Current Model 0₁
C
d
Privacy
V
r
Fusion Center
Preserved
V
Fusion Center
Stochastic Gradient
Gradlents
Payments
^
Reported
R --rli Vice
Viee
Gradient
Vvu
YR,t
k
Arbitrary
Random Signal
1
Users (a)
K
User (c)
(b)
Figure/ 1: The fusion center (FC) trains the learning model with strategic users who are not obliged to report their gradients. (a) The objective of the FC is to incentivize users to cooperate by giving rewards as learn the model. (b) If the user is cooperative, he reports privacy-preserves version of his gradient signal. Otherwise, the user is defective and sends an arbitrary uninformative signal. (c) The FC and the user each choose cooperate or defect with respective payoffs shown.
35 of the updates can vary over time and across the users since each user can control his own dataset. The interactions among users and the FC are repeated, and each user is capable of devising intricate strategies based on the past interactions. From a gaee-theoretic perspective, the fusion center's 's ability 38 reciprocate against non-cooperative user actions significantly restricted since she cannot directly
36
37
39 observe the user actions. Finally, the FC is not allowed to impose penalties the users and positive
40 rewards are the only options at her disposal to incentivize user participation. The work proposed here is, to the best of our knowledge, the first distributed learning framework to consider these challenges.
42 In this study, we model the interactions (in terms of gradient reporting and reward) between the
43 FC and the users as repeated games, which intertwine with the updates in distributed learning. We
44 propose reward mechanism for the fusion center, based on an adaptive zero- prr-dettrmmnnat strategy,
45 thereby generalizing the celebrated ZD strategy to the repeated games with time-varying stochastic
46 errors. To tackle the challenge that the FC cannot directly verify the received reported gradients,
47 we devise a gradient estimation and user action classification. Our findings demonstrate that, by
48 employing adaptive ZD strategies, the FC can incentivize the strategic users to cooperate and report informative gradient updates, thus ensuing the convergence of distributed learning.
49
50
Detailed discussion on related work relegated to Appendix A, due space limitation.
2
Distributed Learning with Strategic Users as Repeated Games
52 We consider a distributed learning setting with K strategic users {l....,K] K} and fusion center (FC), and the optimization problem is given as follows:
min F(O) = Σ EzeD | [x0; DE
54 where [(-) is the loss function. In each iteration, each user gets a mini-batch of i.idd sam- ples from an unknown distribution D, and computes the stochastic gradient signal as X == Ei= (oL(0, = where 24,, , the 7th sampled data of user k at time t.
57
Stage Game Formulation: Actions and Payoffs. The action and the reported signal of user k in 58 iteration é are denoted with Вe, {c, d} and Yr,,, respectively. As depicted in Fig. 1, a user is cooperative (BR,= =c) if is sending the privacy-preserved version of his gradient XR,1- Otherwise,
59
80 the user defective and sends a noise signal TR, . (0, E,) independent of Xa.ti
[X NK.
if B (cooperative);
YE,t = T
(2)
if B = d (defective).
61 Remark Note that Nu. is independent of Xx,t and Nx.- ~ ~( V S ffor all 82 O and z, then this privacy-preservation mechanism enjoys e, e--differenttal privacy, with e = e 2/222 for mini-batch size The details are provided in Appendix.

---

64
The payoff structure of a single interplay between the fusion center and a user is depicted in Fig 1b. In iteration t, when user cooperates, he provides an information gain R to the FC at his privacy cost Vo R with 0 0< Vu I 1. When a user defects, he does not provide any information gain and does not incur any privacy cost. The FC may distribute rewards at the end of each iteration to incentivize the users. We denote the action of the FC toward user k as AR, E {C. D}. The FC is cooperative (= she makes a payment r to the user at her cost r VFC with 0 < VFC S 1. The FC is defective (AA, D), if she does not make any payment to the user. The factor VFc captures the difference in the valuation of the reward between the FC and the user; for instance, the reward can be a coupon which may be redeemed in the future. Denote the FC's payoff vector by Sec = [R-rVFc, -rVEC, R. OJ and that of the users by Sy= fu=(r- Vy R. 7. Vu R, 0J. In this paper, we only analyze the case where R VVFC and > V. Otherwise, the FC or users do not have any incentive to cooperate.
65
66
67
68
69
71
72
73
74
75
The FC cannot observe the actions of the users and her realized payoffs. We assume that users do not communicate or collude with each other. They cannot observe the actions of other users and the actions of the FC toward other users. Next, we will discuss how to devise effective strategies for the FC to incentivize cooperative user action for the repeated game in cost-effective manner.
76
77
78
79 Repeated Games between Users and Fusion Center. A salient feature of 2 repeated games
80 is that players with longer memories of the history of the game have no advantage over those with
81 shorter ones when each stage game is identically repeated infinite times [31]. Thus, without loss of
82 generality, we assume the user strategies only depend on the outcomes of the last round. Let Q1 42, Is
83 and q4 denote the probabilities of cooperation for the user conditioned on the joint action pair of
84 the previous iteration, that is (AR,t-1, 11,, in the order of (C, c), (C,d), (D, c) and (D, d). The
85 user's s strategy vector is defined as q = [41, 92, 93, q4).
86 Analogous to the user strategies, let pl, P2, P3 and denote the probabilities of cooperation for the FC conditioned on (As,t-1, Bx,c), in the order of (C, c), (C,d), (D,c) and (D, d). The fusion center's 's strategy vector is defined as p = [Pi, P2, p3. pa]. The joint action pair of the user and the 89 FC is considered as the state of the game in iteration t: (Ak,e, Bx,)). The strategy vectors p and q
87
88
90
imply Markov state transition matrix as follows:
hPP
(1 41)P2
a1 (1 P1)
(1 (1-00 [1-)((1 P2)
92P1
(1 q2)P2
92 P1)
(1-92)(1 10---121 P2)
Ω
43P3
(1 43)P4
Ps)
(1-gs)(1 -P1)
[qP3
(1 q1)p1
q1(1 Ps)
(1-9))(1 -P1)
i.e. 91 Let A be the stationary vector of the transition matrix i... A' = A We can find the expected
92 payoffs of the FC and the user in the stationary state as sèc = A AF and st = A The FC sets
98 her strategy p satisfying, for some real values yu, P01 and p2, the equation
[p1 1, P2
Ps. pal = SO + PuSu + 421.
(4)
This class of strategies are called zero- pero-determinant (ZD) strategies, which enforce linear relation between the expected payoffs, given by pu + +42= regardless of the user strategy [31].
95
Remark 2. The ZD strategy is a powerful tool incentivize the users cooperation for the FC because she can unilaterally set sy or establish an extortionate linear relation between sú and sec- Against such an FC strategy, the user's 's best response which maximizes his payoff is full cooperation,
97
98
q- = [1 1111 1). The details are provided in Appendix C.
39
100
Against the FC who is equipped with the ZD strategy, the user can increase his expected payoff only by cooperating more often, and consequently his best response is full cooperation. Assuming that there are sufficiently many participating users, the FC has the absolute leverage against any single user who tries to negotiate with her. Nevertheless, the FC cannot directly employ the ZD strategy since she cannot observe the true actions of the users. In the next section, we will study the use of ZD strategy can be extended in the scope of distributed learning.
101
102
103
105
Distributed Stochastic Gradient Descent with Strategic Users
106
107
For the ease of exposition, in this paper we focus on interesting variant of the classical stochastic gradient descent algorithm using the gradient signals reported by strategic users (SGD-SU). In each iteration, the FC collects the reported gradients of the users and update the model as follows:
108
0, P Th me (Y,) x)
(5)
3

---

Algorithm 1: Stochastic Gradient Descent with Strategic Users (SGD-SU)
1 for f == 1.2...., T do Fusion Center: broadcast the current iterate O--1 to all the users 3 forall k E , }} do
{ [k,t Nk.
cooperative action,
4
User compute the gradient Xs,t and Yk,t + (Tke
defective action,
5
Fusion Center: form the gradient estimate (Y,) - K(A1S!1-)q
1
Σx= K k= Yv.e
6
update model parameter 0r t 0,-1 M ())
(cooperative) if M 11 (7)
7 classify the users BR (me, Yk,e) d (defective) else
8 compute the detection and false alarm probabilities using (8) and (11) compute the adaptive strategies (9) and distribute the rewards accordingly
where Y. = [M YR,,), is the step size and m is the gradient estimator. The FC cannot directly observe user actions and verify the reported gradients. This gives rise to two coupled challenges: 111
112
The gradient estimator m, should be resilient against the uninformative reports of defective users. Although the ZD strategies are powerful tools incentivize user cooperation, the FC cannot directly employ a ZD strategy because she cannot observe the users' actions.
113
114
115
To tackle these difficulties, we will first introduce a gradient estimation and user classification scheme and discuss the impact of user action classification errors on the dynamies of repeated games. As outlined in Algorithm 1. we will develop adaptive FC strategies which generalize the classical ZD strategies to the repeated games with timevaryiig stochastic errors.
116
118
3.1
Joint Gradient Estimation and User Action Classification
The stochastic gradients can be decomposed as Xx.t = my + WE.: where mi == ((,) is the population gradient and We, is the zero-mean noise term [30]. The unknown parameter m, the mean of the reported gradient YR,: when the user is cooperative (BR, = c). The defective users send zero-mean random noise their reported gradients. The FC needs to classify the reported gradients and obtain an estimate of m, for the SGD-SU update in (5). These two problems are coupled with each other, and the joint scheme is, therefore, comprised of gradient estimator my and classification rule BR. To tackle this difficult problem, we first investigate gradient estimation.
120
122
123
124
125
126
127
Let Aj be the initial state distribution of the games between the users and the FC. A modified empirical mean based gradient estimator can be employed as follows:
128
my
Σx
k=1 Yu.I-
(6)
((Anf('-1)
It is easy to verify that m.)() is an unbiased estimator if the FC is able to employ her strategies without any errors and the state distribution of the repeated games are governed by the state transition
130
matrix Ωi as in (3) without any perturbations.
132 Using the gradient estimator fn)()), the FC can form the user action classification rule as
è if T, mm.
BA (fa (Y.). Yr.))
else;
where d (or è) is the defective (or cooperative) label. The noise in the stochastic gradients, WE.t- zero mean Gaussian r.v. [17, 22, 26, 36]. Recall from (2) that cooperative users send the prevacy-preserved versions of their gradient. This implies Yk, ~~ Ez), given 136 B where Σ; := cov + Thus, the detection and false alarm probabilities of the classifier, denoted by 4, and V, respectively, can be found as
133
134 can be approximated
137
my me 1|m,1
1 31
Φ 1-
and v, =
(8)
m, Eeme
M. Eeme

---

138
The linear classifier (7) is an effective tool under the homoscedasticity assumption. If that is violated, the FC can employ different classifiers. The details are provided in Appendix for the Classifier Design.
Remark 3.
139
140
141
In the next subsection, we discuss how the FC can devise her strategies building on the joint gradient estimation and user action classification scheme.
142
143
3.2 Adaptive Strategies for Fusion Center
Although the ZD strategies, P. provide the FC efficient and powerful mechanism to encourage the user's cooperation; the FC cannot directly use p since they are conditioned on the user's ac- tion, BR.r, which is not observable her. Alternatively, the FC can use the classification results after carefully adapting her strategies to mitigate the adverse effects of inevitable classification emrors. Let Ir, 22 Tr,3 and T denote the probabilities of cooperation for the FC conditioned
145
148
147
148
on (AR,e-1. Bx.e), in the order of (C, é). (C, d), (D, é) and (D, d). These are referred to as adaptive strategies and the FC sets these probabilities satisfying the following system of equations:
149
P1 = tt 1 + Tt -b),,
P2 = tt, V + 2 (1- - Ve),
Ps
Tr + Te,a &.), P1 te.3 v + t1,a Mp))
Suppose
41
P1
and
4
p3
Then the unique solution to the system above is given by
1/
p2
VE
P4
P1
v/ p2(1 (1- +b,)
p2
pı
V
Tt,
1t,2
(9a)
$ 1/
4 V
P3 (1 v, P1(1 22) 41,4
2, ps U
T1
(9b)
4, V
152
Remark 4. If the FC directly employed the ZD strategies without any adaptation, i.e., she cooperates with probability Pt conditioned on classification output; the repeated games may not converge to the stationary state A and linear relation between the expected payoffs (4) may not be enforced because the classification errors yield an additive disturbance on the state transition matrix as follows
153
154
155
156
Ω (pr - P2) {q T[[[1 [1-0, 0 1- 0] +]+ (1 (1- V. O Vt]}
(10)
Adaptive strategies (9) cancel out this adverse disturbance on the dynamics of the repeated games.
158
In the absence of classification errors (#, 1 and V 0), the adaptive strategies reduce to the ZD strategies, i.e., ne p. Classification errors force the FC to be more retaliatory than dictated by the ZD strategy p. i.c., NT. > P1, Tt,3 > P3. 22,2 < P2 and nt,4 < P1- In general, detection and false alarm probabilities, &, and V v, are time-varying; thus the adaptive strategies also change over time.
160
162
3.3
The Impact of Estimation Errors on Repeated Game Dynamics
163
The proposed adaptive strategies (9) requires the knowledge of detection probability, o.. However, the FC cannot exactly compute d using (8) since she does not have the knowledge of m, Instead, she can form her estimate 4, using m,;
184
1 | 11
(II)
m. Eames
186 Due to the inevitable gradient estimation errors, in general, we have T. * 4,, As a result, the FC cannot exactly employ the adaptive FC strategies dictated by Eq. 9. With several steps of variable substitutions, this yields an additive perturbation on the state transition matrix as follows:
167
188
T. tee and Ω = (p1 - p2)q
0 = Ω + V.2 with V, = a.
0).
(12)
Let Ag be the probability distribution over the state space of the games (Ce, Cd, De, Dd) at the start of iteration t. According to (12), the state distributions follow the transition rule such that
189
170
Á+t1 A, A. (22 + V.
5

---

Note that A, can be considered as the state distribution of the repeated games in the absence of 172 perturbations on the state transition matrix. For the FC, A, is the designed state distribution which the Z.D strategy dominates against any user strategy.
Next, we study the time-varying perturbation terms. Using (8) and (11), Vi can be found as
mi! (m+ Amme))
(1mm)) + f
-
4. 4
m Se
v (22,, mis)
v K'aay(Ze.ma
V
UI
3. 11
à | 12
1-Q
$ A
llre II (Ray ii))
Val Eefis
RRay(Ee, iix)
175
In the presence these perturbations, to establish stability guarantees on the dynamics of the repeated games, we impose the following assumption on the norm of the gradient estimator:
1ssumption 1. We assume that || 2 max (m,, Ez), 2 Ray (m,, E,), m. (m+ m.)
177
178
Note that these conditions are primarily associated to the accuracy of the linear classifier (7) which operates effectively when the mean vectors of the classes sufficiently separated. The following
179
180
result indicates that, due to the perturbations on the state transition matrix, the real state distribution
181
A is a noisy version of A4-
182
Lemma 1. Let A₁ denote the initial state distributions of the games between the FC and the users. Under Assumption we have that
183
A = A. + A Σ 12-
(13)
184
This noise on the state distributions will manifest as a novel bias term in the gradient estimation. In the next subsection, we will provide the convergence analysis of SGD-SU which will mainly focus on the characterization of this bias term.
185
186
187
3.4
Convergence Results
In this section, we provide the convergence guarantee for SGD-SU (5). Let F. denote the o-algebra, generated by (0,, Y,, < l). In particular, F, should be interpreted as the history of SGD-SU up to
189
190
iteration f, just before Y, is generated. Thus, conditioning on F, can be thought of as conditioning
on (01, A1, Y..... - A4-1, Y,-1, 0G, A. For convenience, denote E&[1] == [-FF]. Observe that, we can decompose the gradient estimator m, as follows:
192
(.)-) = m, (1 + ()) + &
(14)
where So is the estimation bias term due to the perturbations on the state transition matrix, given by
1 [E, m.) Σk= P(B c(5) my
S.
K(Aiq
194 and & the estimation noise term, given by & -
Conditioned on F. the probability of 195 a user taking the cooperative action, in iteration i, is given by P(B,, =)) A.q" T. The bias term,
E, [mr).
Sr. can be found follows:
Zrq T
G.
1.
(15)
Auq
197 From Lemma and (15), is clear that the perturbations on the state transition matrix (12), directly translates into a bias in the gradient estimation rule.
To establish convergence guarantees for the SGD-SU in (5), T and d must meet the following criteria during the course of the algorithm:
200
Assumption
2. We assume that T > 1/2 and T.qT 0, for all L (1,2,.... ... T).
The Rayleigh's quotient for symmetric matrix M and nonzero vector is defined as (M) a.
27

---

202
The first condition A,q" 2 0.5 is very mild in the sense that it merely requires that the probability of user cooperation dictated by the memory-1 strategies p and q (1 vectors), in the absence of perturbations, is larger than 0.5. The second condition bry > 0 states that, in the presence of perturbations, the probability of user cooperation is always positive'.
203
204
206
By Assumption there exists positive constant Hr such that
[Sal < HT < Vi E (T)...,T).
(16)
Further, have the following lemma characterizing the properties of estimation noise.
208
Lemma 2. Conditioned on Ft, the estimation noise in iteration t, denoted &g, a zero-mean random vector with the mean square error given by
B₁ [1| (AiqT)
((G (Ge+1)Ie 1)tr (Et (E--E()
1 Aeq (r(i))
(17)
Drq
210
By (16) and (17), we have that
E. [|E <
Fr K
with ET ~iq- (Hy + 1)tr(2, - -,)) + x
(18)
Teq
211
We impose the following assumption on the objective function, which standard for performance analysis of stochastic gradient-based methods [3, 28).
213
Assumption 3. The objective function F and the SGD-SU satisfy the following:
214
(i) F is L smooth, that is, F is differentiable and its gradient is L-Lipschitz:
VVF()) - VF((') < L|l A1I, v0,0 6 E RR.
215
(ii) The sequence of iterates { is contained in an open set over which bounded below by a scalar Fint.
216
Our next result describes the behavior of the sequence of gradients of F when fixed step sizes are employed.
218
Theorem 1. Under Assumptions 2 and 3, suppose that the SGD-SU (5) is run for T iterations with fixed stepsize 3 satisfying
220
0 0 M(1 Hr) Then, the SGD algorithm with strategic users satisfies that
(19)
221
1 + --1 IVF()))1
LET
2(F(O)) Fint)
E
<
K(1-H) HT) BT(1 Hr)
222
Theorem illustrates the impact of the perturbations on the state transition matrix (12) on the convergence rate of SGD-SU. When Hy is close to O, SGD-SU performs similar to the basic minibatch SGD. On the other hand, if Hr is close to I, the optimality gap may be large. Our next result will characterize the gradient estimation bias term First, we have the following assumption on the state transition matrix Ω.
224
226
Assumption 4. The state transition matrix Q can be diagonalized Ω rur with U has the
228
eigenvalues of Q2 in descending order of magnitude: 12 |u2 2 Ual Z |ug 2 0.
Denote the element of 1' in the 7th row and jth column T. 74. Next, define as
Denote the four rows of 1 by
229
230
7
[aj (
7 T T))
max (E(2.3.4)
max (E(33,44)
Further, the first order Taylor approximation of the scalar variable Vir can be found follows:
[meell
V. mi (me mz), he (m) with hm(m))) == 2/2 EE, me)
exp
Ray Ray me)
(20)
||m
lime
|
2
2 Ray m.)
2 Ray(EE, m.)
A sufficient condition for this requirement is that user strategies forgiving in nature, i.e., 91, 92, 43, 49,
7

---

232
Define h = ( (l.....) h& (m:). Our next result indicates that, the estimation bias term G can be found in terms of the past gradient estimation errors.
233
Theorem 2. Under Assumptions 1, 2 and 4, the gradient estimation bias term St- can be found
(-1 A,q
m & hi hi(ms)))s
G = (pi -p2) Σ
(21a)
|m;||
235
with
| S 8/u011-111
"-1-i 5² n max uz2
1--2- i 1))
(21b)
Further, for some 0 17
have
Di=1 a
P
(((e) < m//a...... at-1) >
(22a)
K1
with
(v
(
m
E.m;
<?
2
[|m
A;9
A.q
(22b)
||mm]]
(A.q*)
Arq
238
Note that Eq. (21) indicates that, the estimation bias term Sa can be expanded in terms of past gradient estimation errors. We prove that the absolute values of the coefficients, | 's, are bounded
r 8|ug|"-1-i 1111-i 5² " 1
1);
240
where U2 is the eigenvalue of Q with the second highest absolute value. Since Q is row stochastic matrix, |u2| S 1. When juz] strictly less than A., 's decay fast as grows. This can also be interpreted as the impact of past gradient estimation errors fade away quickly. Using this result, in (22), we derive a high probability upper bound on the estimation bias term G..
241
243
Experiments
244
245
In this section, we evaluate the performance of SGD-SU (5) using real-life datasets. All the results in the preceding section assert convergence for the SG method (5) under the assumption that the FC can access Mn and E. In real-life machine learning setting with strategic users, this information may be available the FC. For convenience, define &द and K as the sets of users who are classified as cooperative (c) and defective (d) at iteration t. Based on the user action classification, the FC can form her estimates for the covariance matrices under the cooperative and defective actions as follows:
247
248
249
250
E.
Σ (Yx, Vi) (Y PP) and E KER;
Σ kERd
(YE, - Fr)) T (23)
(Kel
where Y [NCP] EKERG Ys, and Y
[K21] EKERG Yk..-
251
252
In our first set of experiments, we consider binary logistic classification problem and use the KDD- Cup 04 dataset [6]. The goal of binary logistic classification experiments is to learn a classification rule that differentiates between two types of particles generated in high energy collider experiments based on 78 attributes [6]. In our second of experiments, we consider neural network trained on
253
254
255
256
the MNIST dataset. The number of users is chosen as K = 50 and mini-batch size is s = 10. In the experiments, we have tested the performance of two different ZD strategies, namely equalizer and extortion[31].
257
258
For the logistic classification problem, Fig. 4a and 4b, depict the optimality gap under four different user strategies: q = [0.9 0.15 0.9 0.15] (stubborn), q = [0.9 0.9 0.15 0.15] (tit-for-tat, ). = (..9 0.15 0.15 0.9] (win-stay-lose-swithh and q = 0.9 0.9 0.9 0.9) (full cooperation). For the full cooperation, coin toss, tit-for-tat and stubborn user strategies, SGSU converges quickly. For Pavlov user strategies, SGSU can eventually approach, albeit more slowly than other cases. Fig 4c and 4d illustrate the probability of user cooperation, Λ.q across different user strategies. The experimental results validate Lemma I and the empirical user cooperation probabilities match the theoretical except when the users are Pavlov. Unsurprisingly, when the users follow full cooperation (or coin toss) strategy, they cooperate with probability 0.9 (or 0.5) regardless of the actual states of the repeated
260
282
263
254
286

---

300
100
(a) Equalizer
(h) Extortion
(c) Equalizer
(d) Extortion
Col
Buk
7950
(c) Equalizer
(f) Extortion
Equalizer
(h) Extortion
Figure 2: Stochastic Descent Algorithm with Strategic Users
288
games. For the cases with stubborn and tit-for-tat users, the games quickly converge to the steady state distribution. Interestingly, for the cases with Pavlov users, the probability of user cooperation decreases over time. This is associated to the performance of the linear classifier. For the image classification problem, Fig 4e-h depict the training loss and testing accuracy across iterations for different FC and user strategies. In all experiments, SGSU converges in the presence of strategic users. Further details regarding the Experimental results are relegated to Appendix.
270
272
273
Future Directions
274
In this work, study distributed learning framework where strategic users train learning model with a fusion center. The main objective the FC is to encourage users to be cooperative by distributing rewards. Based this, devise reward mechanism for the FC based on the ZD- strategies. Further, we examine the performance of SGD algorithm in the presence of strategic users. Our findings reveal that the algorithm has provable convergence and empirical results verify theoretical analysis.
276
278
280
We are also working the development of robust estimation tools in distributed learning with strategic users. The geometric median a reliable estimation technique when the collected data
282
contain outliers of large magnitude [10, 14, 24, 27]:
Med(Y.) == arg min
Σ ll Yi,
(24)
yER"
The FC can use Med robust gradient estimator, especially when the variance of the uninformative signals, E? reported by the defective users, is very high. The geometric median (24) can be computed by the Weiszfeld's 's algorithm [34, 35], which special case of iteratively reweighted least squares. In contrast, with the knowledge of the modified sample mean estimator (6) allows the FC to trade robustness for overall tractability of the algorithm with reduced computational complexity.
285
286
287
288
289
The linear classifier vulnerable to vanishing gradients as the stochastic gradient descent algorithm with strategic users (SGD-SU) converges 6* This be addressed by modifying the classifier
281
to incorporate the information contained in the norm of the reported gradients. Furthermore, we discuss how extend the convergence guarantee for SGSU to allow heterogeneous user strategies. The details are presented in Appendix.
292
283
References
295
[1] ALISTARH, D., ALLEN-ZHU, Z.,, AND LI, J. Byzantine stochastic gradient descent. In Advances in Neural Inform. Proc. Systems 31 (2018), NIPS' 18, pp. 4613-4623.

---

297
[2] BLANCHARD. P., EL MHAMDI, E. M., GUERRAOUI, R., AND STAINER, J. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Inform. Proc. Systems 30 (2017), NIPS 17, pp. 119-129.
296
[3] BOTTOU, L.., CURTIS, F. F.,, AND NOCEDAL, J. Optimization methods for large-scale machine learning. SIAM Review 60, (2018), 223-311.
301
302
[4] CAT, Y., DASKALAKIS, C., AND PAPADIMITRIOU, C. Optimum statistical estimation with strategic data sources. Journal of Machine Learning Research 40, 2015 (2015), 1-17.
[5] CARAGIANNIS, I., PROCACCIA, A. D., AND SHAH, N. Truthful univariate estimators. 33rd
305
International Conference on Machine Learning, ICML 2016 I (2016), 200-210.
306
[6] CARUANA, R., JOACHIMS, T., AND BACKSTROM, L. Kdd-cup 2004: Results and analysis. SIGKDD Explor. Newsl. 6, 2 (Dec. 2004), 95-108.
[7] CHEN, Y., IMMORLICA, N., LUCIER, B., SYRGKANIS. V., AND ZIANI, J. Optimal data the acquisition for statistical estimation. In Proceedings of the 2018 ACM Conference on Economics and Computation (New York, NY, USA, 2018), EC '1, Association for Computing Machinery,
309
311
p. 27.4-4..
312
[8] CHEN, Y., PODIMATA, C., PROCACCIA, A. D., AND SHAH, N. Strategyproof Linear
313
Regression in High Dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation (New York, NY, USA, jun 2018), vol. 76, ACM, pp. 9-26.
314
315
[9] CHEN, Y., Su. L., AND XU, J. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proc. ACM Meas. Anal. Comput. Syst. 2 (Dec. 2017).
316
317
[10] COHEN, M. B., LEE. Y. T., MILLER, G., PACHOCKI, J., AND SIDFORD, A. Geometric median in nearly linear time. In Proc. ACM Symp. on Theory of Comp. (New York, NY, USA, 2016), STOC '1, ACM, p. 9-21.
318
319
320
[1I] CUMMINGS, R., IOANNIDIS, S., AND LIGETT, K. Truthful linear regression. Journal of Machine Learning Research 40, 2015 (2015), 1-36.
322
[12] DEKEL, O., FISCHER, F., AND PROCACCIA, A. D. Incentive compatible regression learning.
323
Journal of Computer and System Sciences 76, 8 (2010), 759-777.
324
[13] DWORK, C. Differential privacy. In Proc. Int. Conf. Automata, Languages and Programming Volume Part II (Berlin, Heidelberg, 2006), ICALP' 06, Springer-Verlag, pp. 1-12.
[14] FLETCHER, P. T., VENKATASUBRAMAANNN S., AND JOSIII, S. Robust statistics rieman- nian manifolds via the geometric median. In 2008 IEEE Conference on Computer Vision and Pattern Recognition (2008), pp. 1-8.
327
[15] HAO, D., RONG, Z., AND ZHOU, T. Extortion under uncertainty: Zero-determinant strategies in noisy games. Phys. Rev. E 91 (May 2015), 052803.
330
331
[16] HORN, R., HORN, R., AND JOHNSON, C. Matrix Analysis. Cambridge University Press, 1990.
332
[17] JASTRZKERSKI, S., KENTON, Z., ARPIT, D., BALLAS, N., FISCHER, A., BENGIO, Y., AND STORKEY, A. J. Three factors inftuencing minima in SGD. 1.Xiv:7711.0462331 [cs.LG] (Nov. 2017).
338
334
335
[18] JORDAN, M. I., LEE, J. D., AND YANG, Y. Communication-efficieeen distributed statistical
336
inference. Journal of the American Statistical Association 114, 526 (2019), 668 668-681.
337
[19] KONEČNÝ, J., MCMAHAN, H. B., RAMAGE, D., AND RiCHTARIK, Federated optimization: Distributed machine learning for on-device intelligence. arXiv:1610.02527 [cs.LG] (Oct. 2016).
338
339
[20] KONG, Y., SCHOENEBECK, G., TAO, B., AND YU, F.-Y. Information elicitation mechanisms for statistical estimation. Proceedings of the AAAI Conference on Artificial Intelligence 34, 02 (Apr. 2020), 2095-2102
340
342 [21] LI, M., ANDERSEN, D. G., PARK, J. W., SMOLA, J. AHMED, A., JOSIFOVSKI, V., LONG, J., SHEKITA, E. J., AND SU, B.-Y. Scaling distributed machine learning with the parameter server. In Proc. the 11th USENIX Conf. on Operating Systems Design and Implementation (USA, 2014), OSDI' 14, USENIX Association, p. 588-598.
343
345
346
[22] LIN, T., STICH, S. U., PATRI,, K. K., AND JAGGI, M. Don't use large mini-batches, use local sgd. In Int. Conf. Learning Representations (2020), ICLR 20.
10

---

348
[23]
LIU, Y., AND WEI, J. Incentives for Federated Learning: A Hypothesis Elicitation Approach. arXiv:2007. 10596v1 [cs.LG) (July 2020).
349
350
[44]
LOPUHAA, H. P., AND ROUSSBEUW, P. J. Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. Ann. Statist. 19, 1 (03 1991), 229-248.
351
352
[25]
LOW, Y., BICKSON, D.. GONZALEZ, J., GUESTRIN, C., KYROLA, A., AND HELLERSTEIN,
J. M. Distributed graphlab: A framework for machine learning and data mining in the cloud.
354
Proc. VLDB Endow. 5, 8 (Apr. 2012), 716-727.
355
[26] MANDT, S., HOFFMAN, M. D., AND BLEI, D. M. variational analysis of stochastic gradient
algorithms. In Proc. Int. Conf. Machine Learning (2016), vol. 48 of ICMI' 16, JoLR.org. p. 1.34-333.
357
[27]
MINSKER, S. Geometric median and robust estimation in banach spaces. Bernoulli 21, 4 (11 2015), 2308-2335.
359
380
NEMIROVSKI, A., JUDITSKY, A., LAN, G., AND SHAPIRO, A. Robust stochastic approxima- [28]
tion approach to stochastic programming. SIAM J. Optimization 19, 4 (2009). 1574-1609.
[29] NG. K. L.., CHEN, 7., LIU, Z., YU, H., LIU, Y., AND YANG, Q. A multi-player game for studying federated learning incentive schemes. In Proceedings of the Twenty-Ninth International
363
Joint Conference on Artificial Intelligence, IJCAI-20 (7 2020), C. Bessiere, Ed., International Joint Conferences on Artificial Intelligence Organization, pp. 5279-5281.
365
388
[30]
POLYAK, B. T., AND JUDITSKY, A. B. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization 30, 4 (1992), 838-855.
387
368
[31]
PRESS, W. H., AND DYSON, J. Iterated prisoner's s dilemma contains strategies that dominate any evolutionary opponent. Proc. Natl. Acad. Sci 109, 26 (2012), 10409-10413.
[32] RICHARDSON, A., FIL.OS- ATSIKAS, A., AND FAITINGS, B. Budget- Buugge--Bunded Incentives for Federated Learning. Springer International Publishing. Cham, 2020, pp. 176-188.
371
372
[33] SU. L., AND Xu, J. Securing distributed gradient descent high dimensional statistical learning. SIGMETRICS Perform. Eval. Rev. 47, (Dec. 2019), 83-84.
373
374
[34] VARDI, Y., AND ZHANG, C.-H. The multivariate m.e-mn and associated data depth. Proc. Natl. Acad. Sci. 97, 4 (2000), 1423-1426.
[35] WEISZFELD, E. Sur un probléme de minimum dans l'espace. Tohoku Math. J. 42 (1936).
377
274-280.
378
[36] XING, C., ARPIT, D., TSIRIGOTIS, C., AND BENGIO, Y. A Walk with SGD. [stat.ML] (Feb. 2018).
379
380
[37] XING, E. P., HO, Q-, XIE, P., AND WEI, D. Strategies and principles of distributed machine learning big data. Engineering 2, 2 (2016), 179 - 195.

---

Checklist
382
383
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
385
contributions and scope?
386
(b) Did you descrihe the limitations of your work?
387
(c) Did you discuss any potential negative societal impacts of your work?
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
389
380
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results?
392
(b) Did you include complete proofs of all theoretical results? Proofs are included in the Appendix.
383
394
3. If you ran experiments..
395
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? The code is included in supplementary material complying to NeurlPS instructions with details on how to run the code.
397
399
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)?
400
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)?
402
403
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? The hardware used is described in the Appendix
405
406
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
407
(a) If your work uses existing assets, did you eite the creators?
408
(b) Did you mention the license of the assets?
409
(c) Did you include any new assets either in the supplemental material or as a URL? Our code is included in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating?
412
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?
414
415
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable?
417
418
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable?
419
420
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation?
12


Reviews:
[{"review_id": "r-J8wCtr5e5", "reviewer": "Reviewer_mQAc", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The task is new. The problem formalization and the mechanism proposed are novel.\n\nQuality: The submission is technically sound. But the assumptions are somewhat unreasonable to me and I would like to know if these assumptions are necessary and non-vacuous. \n\nSpecifically, for Assumption 1, it might be uncommon to make assumptions over the gradient estimate, which is a r.v. dependent on the objective function and the noise distributions. I am curious if the assumption could be made directly over the objective function and the distributions instead of the gradient estimate. For Assumption 2, $\\tilde{\\Lambda}_t$ depends on $\\Lambda_t$, the objective function and the noise distributions. Similar to Assumption 1, it looks quite strange to make direct assumptions over $\\tilde{\\Lambda}_t$.  Also, before Assumption 2, the authors state that ``\" $\\Lambda_t q^\\top$ and $\\tilde{\\Lambda}_t q^\\top$ must meet the following criteria ...\". Is Assumption 2 a necessary condition? \n\nBesides, the gradient estimator $\\hat m_t$ depends on $q$. It is unclear to me what $q$ is.  Is it the user's initial strategy? Is it deterministic?\n\nClarity: Some notations are unclear. It would be better if the paper has more explanation on the assumptions.\n\nSignificance: The problem studied by this paper is interesting and important.\n\nOther comments:\n1. What is $Q$ in Eq. (8)?\n2. Is $\\hat {m}_t^\\top (m_t - \\hat m_t)$ in Assumption 1 always positive? If not, $\\sqrt{\\hat m_t^\\top (m_t - \\hat m_t)}$  is not well-defined.\n3. Typo: $Ray(\\hat m_t, \\Sigma_t)$ should be $Ray(\\Sigma_t,\\hat m_t)$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. The authors are recommended to add a discussion on the societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "N9VSRVToRfG", "reviewer": "Reviewer_VAjM", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. The formulation and the results are interesting; however, there are some concerns from the reviewer:\n\n1.\tWhat’s the motivation of the users submitting random noninformative signal to the FC instead of just submitting nothing when they decide not to cooperate. Submitting random noninformative signal does not benefit the users but harms the FC. \n2.\tPlease explain the state transition matrix $\\Omega$ in eq. (3), why it is constructed as it is and why the states are supposed to evolve according to it. Just below eq. (3), the authors use \\bar{\\Omega} to denote the transition matrix, what is the difference between $\\Omega$ and $\\bar{\\Omega}$, or it is just a typo?\n3.\tThe authors are expected to clearly state the goal of users in playing the game, namely, in each iteration, the users maximize what, the expected long-term reward, or the reward of this iteration. Based on the objective of the users, the author shall show that the users’ best response is q* = [1, 1, 1, 1]^T given that the FC adopts ZD strategy. \n4.\tIn the Experiments section, the figure referred is Fig 2 rather than Fig 4. SGSU is SGD-SU, typo? Does Pavlov mean the win-stay-lose-switch? If it does, please just use one of these two phrases throughout the paper. \n5.\tFrom Figure 2(a) and (b), it is shown that the optimality gap is the smallest when the users take tit-for-tat strategy. Does this mean the FC prefers tit-for-tat instead of full-cooperation in order to obtain a favorable solution to optimization problem (1)? This is not consistent with the game, where the FC prefers full-cooperation? \n6.\tSince the problem is formulated as a repeated game, the experiments shall show whether the strategy of the users converges exactly to q* starting from any initial state and action. \n7.\tThe reviewer believes (24) admits a closed-form solution, and the computational complexity of (24) is the same as that of (6). Please check this. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "M-2j-nDmJ2L", "reviewer": "Reviewer_UwUw", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Federated learning is a relevant problem in machine learning and I believe this work positively contributes to the existing literature. \nThe work adds both novel theoretical contributions and experimental results. Moreover, it is clearly written. Hence, my acceptance score.  However, I have a few comments for the authors: \n\n- It would be nice to have related works discussed in the main paper, clearly highlighting the differences in terms of set-ups and assumptions considered. I believe the problem of federated learning can be tackled from a lot of different perspectives and it would be nice to have this clear from the first sections. A lot of technical definitions and details could be moved to the Appendix instead (e.g., Equation 20).\n\n- In the experiments, only a static strategy vector is considered for the users. However, it would be natural to consider users who adapt their strategy online. Is there a particular reason why this was not considered? This would test whether the FC algorithm actually steers the agents to collaborate in the long run.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see potential negative societal impact for this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Bel7NM-cSKL", "reviewer": "Reviewer_AUVR", "summary": "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am mostly concerned about the setup (line 64-line 74). \n\n“In iteration t, when a user cooperates, he provides an information gain R to the FC at his privacy cost VUR with 0”. It is unclear to me how the authors quantifies the privacy cost and why it is related to the information gain R via a factor V_U between 0 and 1. It seems to me that the information gain R was not used in Algorithm 1. Would the authors explain how R is used? Moreover, the information gain R should vary every time. Is it the case in the paper’s setup?\n\n“The FC is cooperative (Ak,t=C) if she makes a payment r to the user at her cost rVFC with 0”. Why is the cost of the FC rV_{FC} related to V_{FC} via a factor V_FC between 0 and 1? Would the authors explain the intuition behind this?\n\nline 72-73: the authors did not specify how each entry in a payoff vector is ordered.\n\nIt would be beneficial to discuss when Phi_t/Psi_t>=p1/p2, Phi_t/Psi_t>=p3/p4 are satisfied and if they are always satisfied (line 151). \n\nI like it that Theorem 2 gives a bound on \\zeta_t. But there are still some unclear things. \n\nhow large is $\\sum_{i=1}^{t-1} \\alpha_i^2$ compared to $\\eta^2$? The authors should establish that the bound (22a) would not be vacuous. Recall in line 61 that the norm of the gradient is <= \\ell. This bound is vacuous if the upper bound is just close to \\ell. The authors may want to compute the expected value of \\zeta_t and then check if the bound is vacuous. \n\nWhat is $\\Delta_{i,t}$?\n\nThe current form looks pretty complicated. The authors may want to do some asymptotic analysis and present the asymptotic order of each term so that the presentation of the results can also be simplified. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary:

The paper considers a setting motivated by federated learning, where a fusion center (FC) seeks to minimize some loss function over k users, but has to rely on stochastic gradients reported by the users. This is set up as a repeated game in which users can either cooperate (and send the true stochastic gradient) or defect and send a noisy signal.

The main result is a stochastic gradient descent-strategic users (SGD-SU) algorithm, which builds on ideas of the zero-determinant strategy for repeated 2x2 games (Press and Dyson, PNAS, 2012). 
The paper presents theoretical results on the effectivity of their algorithm (Theorem 1 and Theorem 2), as well as experimental results (on the KDD Cup 04 dataset and the MNIST dataset).

Recommendation:

All reviewers were a bit lukewarm on this paper. They generally liked the basic question/problem, but also expressed a variety of concerns regarding the concrete modelling assumptions.
My evaluation is closest to that of reviewer mQAc, which felt that the assumptions (Assumption 1 and Assumption 2) are a bit artificial, and that it's a bit unclear what information is gained from the theoretical bounds.  
Overall, I don't see enough enthusiasm here to recommend the paper for acceptance.


Decision: Reject