Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 
main_review: I am mostly concerned about the setup (line 64-line 74). 

“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?

“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?

line 72-73: the authors did not specify how each entry in a payoff vector is ordered.

It 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). 

I like it that Theorem 2 gives a bound on \zeta_t. But there are still some unclear things. 

how 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. 

What is $\Delta_{i,t}$?

The 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. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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:

1.	What’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. 
2.	Please 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?
3.	The 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. 
4.	In 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. 
5.	From 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? 
6.	Since 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. 
7.	The reviewer believes (24) admits a closed-form solution, and the computational complexity of (24) is the same as that of (6). Please check this. 

limitations_and_societal_impact: No negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Federated learning is a relevant problem in machine learning and I believe this work positively contributes to the existing literature. 
The 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: 

- 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).

- 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.
limitations_and_societal_impact: I don't see potential negative societal impact for this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Originality: The task is new. The problem formalization and the mechanism proposed are novel.

Quality: 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. 

Specifically, 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? 

Besides, 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?

Clarity: Some notations are unclear. It would be better if the paper has more explanation on the assumptions.

Significance: The problem studied by this paper is interesting and important.

Other comments:
1. What is $Q$ in Eq. (8)?
2. 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.
3. Typo: $Ray(\hat m_t, \Sigma_t)$ should be $Ray(\Sigma_t,\hat m_t)$.
limitations_and_societal_impact: No. The authors are recommended to add a discussion on the societal impact.
review_title: null

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