Summary
The paper considers a federated learning setting with strategic data resources. The authors assume that the entities taking part in the learning process are selfish players incentivized to get the best model but benefit if their competitors receive inaccurate models. This selfish behavior pushes players to lie to the central learning mechanism in their reports.
The authors consider two cases: Mean estimation and a multi-round SGD on strongly convex objectives. They model the players' strategies as multiplicative/additive factors that could be added to the players' actual local computations. The authors show that even in the straightforward case of mean estimation, a PNE does not exist. They offer two remedies: Monetary payments (via peer-prediction techniques) and punishments (noisy model updates by the central mechanism). Then, they show that a PNE exists and characterize the form of payments/punishments required.
Finally, they conduct an experimental analysis demonstrating that their remedies positively affect the learning procedure.
Strengths
1. The paper deals with a practical issue that is somewhat under-explored.
2. Despite the abundance of notations, the authors have done an excellent job in making the paper read smoothly.
Weaknesses
1. The paper adopts a game theoretic approach, but many modeling assumptions seem cumbersome and unjustified (see questions below).
2. It is hard to assess this paper's technical contribution. Particularly, the novelty of the peer prediction-based mechanisms are well-studied ideas. The authors did not explain whether this paper adopts these ideas in a plug-and-play manner or presents new non-trivial derivations. The "our contribution" part addresses the paper's content but not its marginal contribution to the line of research, making the technical contribution hard to assess.
Questions
1. Strategy spaces: The assumption that players report their updates along with $\alpha^i \xi^i$, where $\alpha^i$ is player $ i$'s strategy and $\xi^i$ is a random variable seems completely arbitrary and unjustified. Typically, one makes assumptions about what players aim to do (e.g., maximize their payoff) and what they can do (e.g., bounded computation or memory, acting myopically, etc.). Explicit assumptions about players' strategies without proper grounding and reasoning are cumbersome and inconvenient. Could the authors justify what real-world scenarios the strategy spaces in Eq. (3) models? Could the authors present assumptions about player rationality\behavior that would recover their modeling?
2. The assumption about $b^i$ in Eq. (4): What is the justification for this? Indeed, it facilitates the analysis but seems entirely out of context.
3. Multi-round: The authors assume that in the multi-round case, players pick their strategies only once initially. What is the rationale for this modeling? Allowing players to change their strategies throughout the execution will be harder to analyze, but this compromise does not make much sense.
4. Corollary 2: The authors show that a pure Nash equilibrium does not exist, concluding that "without modifications to the protocol, no player can benefit from collaborative learning." While this might be true, I do not see how the inexistence of Nash equilibrium implies collaboration is useless. To reach this conclusion, the authors must show that players are better off (i.e., their estimates are more accurate) without the protocol. Where is this analysis located in the paper? Further, I suspect that a mixed Nash equilibrium does exist, so arguing about whether players can benefit from collaboration should at least consider their payoff under some form of a solution concept (be it mixed equilibrium, sink equilibrium, or otherwise). My question: Could the authors describe why the inexistence of PNE suggests that collaboration is useless?
5. The methods the authors adopt, e.g., scoring rules, seem to treat the most general case where players can report whatever they want, beyond limiting the structure of their message (Eq. (3) for the mean estimation case). This is at least true in the mean estimation case. The same thing applies to the payment case. What does this paper benefit from making the limiting (and, as I argued before, the highly unjustified) assumption of the structured strategy spaces?
6. What is the technical modification of peer-prediction\noise communication required for this paper? How novel is the derivation needed for this paper, and how does it differ from previous papers? Answers to this question could facilitate the assessment of this paper's contribution.
Minor:
• Why are the super scripts m and w needed in lines 198 and 211 (they also appear later in the paper)?
• 173: clients->players
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.