Unravelling in Collaborative Learning

Summary

The paper models the collaborative learning problem using a statistical model. In this model, since each agent has its own utility with respect to the risk and the cost of sampling, they may not converge to the Nash equilibrium of optimal general risk. More precisely, the process may undergo a phenomenon known as unraveling, wherein it contracts to the point that it becomes empty or consists solely of the worst agent. The paper designs a mechanism to avoid this phenomenon and provides a practical implementation for the transfer-free mechanism.

Strengths

- The paper models the collaborative learning problem in a manner that is both strict and easy to understand. - The paper identifies the "unraveling" problem during the process of collaborative learning and provides a solution. This seems like a very important issue for making collaborative learning work. - The paper clearly lists the hypotheses used in every theorem, making it easy to understand the conditions under which the theorems apply.

Weaknesses

- The paper does not show empirically when the "unraveling" problem occurs or whether the mechanism in section 4.2 makes a difference. It is not clear whether the problem is common in practice. - The empirical implementation of the mechanism in section 4.2 requires hypothesis 7, which may not be feasible in practice if the aggregator does not know $P_0$ exactly or the number of samples is relatively small, i.e., less than $q'$. - The notation is confused, i.e., $\underline{n}$ is used to denote an expression of $\arg\max_{n}\cdots$.

Questions

- Hypothesis 4 appears to be a bound on the number of agents. Could you provide an example of the number of agents required in practice? - As mentioned in the weaknesses section, could you demonstrate the "unraveling" problem and the mechanism to address this issue in practice? How common is this problem? - Is the selection of $\eta_{\delta}$ in proposition 3 optimal?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

I do not foresee any negative societal impact from this paper. For other limitations, please see the questions and weaknesses sections.

Summary

There can be strategic learners and collaborations for collaborative learning is not trivial. When data qualities are private, coalitions may undergo unravelling wherein only worst agents will be left in the coalition. Authors propose a probabilistic verification-based mechanism to make optimal collaboration as Nash Equilibrium with high probability.

Strengths

Authors consider the formation of coalitions and consider strategic agents with distribution of different quality. Authors also propose that optimal coalition occurs at NE as per their mechanism with high probability and back it up with rigorous theoretical proofs.

Weaknesses

The authors don’t show that if the agents report the type profile of the agents truthfully. They rather consider that the aggregator to approximate it based on their probability distribution. Also, experimental verification isn’t provided.

Questions

As the aggregator is estimating the types of contributor's types, they need to have access to the probability distribution from which they are sampling data. How practical is this scenario?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

As authors proposed by the authors, it would have been better if agents learned their types themselves in an online fashion.

Summary

Adverse selection is a phenomenon studied in economics in which information asymmetry may have a negative effect in the market equilibrium. The paper considers a federated learning setting when the agents are strategic, and the authors formalize the concept of ``adverse selection'', and analyze it in several directions. The question they ask is the following: assume that different agents are able to collect samples with different quality and share it with other agents. In this case agents with high quality sample may benefit little from sharing their information. This may have a spiral effect so that none would be happy to share their samples. The authors formalize this problem and analyze it trough a series of results: (1) they model the above mechanism in which each agent i can sample data points with quality \theta_i (2) they show how a benevolent social planner can maximize the overall utility for all agents if she knows all \theta_is (3) they formalize the strategic setting in two cases and ask whether unraveling may occur: - They that indeed this may occur if the social planner is unaware of the quality of samples. Assuming that agents are able to statically share the value of \theta_i they show that in this case the Nash equilibrium is when the lowest quality agent or no agent shares their samples. - Motivated by this negative result the authors consider a different scenario in which the agents do not share the value of the quality of their samples but they share a fixed number samples if they want to participate in the aggregation process, using these samples the planner estimates the quality of their data and asked for more samples if needed. In this case, agents will all reveal the true value of the quality of their samples, and the social planner can maximize the overall utility function so that unravelling will not occur. I find the results interesting and solid (although I didn't check the proofs). The presentation is a bit hard to follows but I don't see an easier way of presenting all of these theoretical results.

Strengths

- solid mathematical modeling and analysis - interesting result: extending an interesting concept called unravelling to federated learning

Weaknesses

- hard to follow all details

Questions

I didn't understand the subsection about VCG mechanism. What is it and why it is not available in your framework?

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have discussed the future directions in the conclusion.

Summary

The paper studies adverse selection in federated learning, due to varying levels of data quality among the clients. In particular, a phenomenon of unravelling, in which the collaboration is essentially destroyed due to insufficient incentives for participation for the agents with high quality data, is identified and studied. Within a specific model for the incentives of the clients and the server objective, the authors first derive optimal protocols under full information. Then they prove the emergence of the unravelling effect under hidden information and suggest a mechanism that avoids this effect by estimating the clients' dataset qualities from data.

Strengths

- The paper studies a very relevant topic, namely participation incentives in FL. It also provide a new model for such incentives in the presence of varying data qualities and demonstrates and studies the effect of unravelling, which is, to my awareness, also a novelty in the context of FL. - The paper is well-written and the model design choices are well-justified. - Related work is covered well. - The paper shows how to incentivize participation by estimating the clients' data qualities by an initial sampling phase. In this way, more data can be collected from the clients with high-quality distributions. I think this approach is valuable, since it does not require any payments/penalties, but instead incentivize collaboration purely by changing the learning algorithm.

Weaknesses

- In the proposed frameworks, the utilities of the clients are evaluated based on upper bounds on the loss and therefore on the type of guarantees on the model that can be obtained. One might expect that clients would instead reason about the expected loss (and hence utility) that they will get from the FL protocol, under the decisions they take (and over the randomness of the sampled data). It will be nice to see a discussion about why clients may chose to reason via statistical guarantees as compared to expected rewards; as well as a discussion of whether the techniques in the paper can be extended to the case where expected reward is considered. - If I interpret equation (8) correctly, currently the problem that the server solves requires that agents who are not included in the collaboration also would benefit from joining. Intuitively, this feels unfair/undesirable, since these agents will be "left out" of the collaboration. Of course, that won't be a problem if the grand coalition is chosen, but how about the remaining cases?

Questions

- For H1, it will be nice if the authors can clarify what $alpha$, $beta$ and $gamma$ can depend on in their framework. Are they absolute constants, can they depend of $\mathcal{H}$, the distribution $P$, etc? - In H3, does the lower bound on $\theta_j$ need to be larger than $0$? - Could the authors clarify how Lemma 1 and Proposition 3 relate to classic results from domain adaptation about the generalization of classifiers learned on multi-source data and about estimating the discrepancy distance from finite samples?

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

It will be nice to see a discussion about possible notions of optimality of mechanisms that incentivize participation in this context.