Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers a federated learning setting. The idea and novelty of the paper consist in taking fairness considerations into account. Namely, agents that contribute a lot of/little data or lower/higher quality data should not be treated the same way. 
strength_and_weaknesses: Strength: 
- the motivation of the paper is clear, and important. It is unfair to give the same outcomes and benefits to agents that barely contribute to the model learned by the federated learning algorithm and simply free-ride. Further, the presence of agents with low-quality data can further compromise the performance of agents with high-quality data. 
- the formal definition of fairness is an interesting proxy to address this issue, by looking at the excess risk of the model seen by population e compared to the best model population e could train on their own data. In turn, if this excess risk is low, it guarantees that a population with low-quality data sees a model $\theta_e$ that cannot be (much) better than the low-quality model they could have trained themselves. 
- the techniques are interesting, with a 2-step approach: i) clustering agents with similar data distribution together (so that agents with accurate/high-quality data are for example clustered together), then ii) give different weights to different agents as a function of their cluster in the loss minimization problem
- The authors provide theoretical statement showing that their algorithm performs well for a reasonable/common class of losses (linear + smooth and strongly convex)
- The authors provide convincing experiments showing that their approach leads to better fairness, but also overall model performance, than previous work. The results are especially good when the data is synthetically generated according to the assumptions of the paper, but the experiments also show that their approach does better than FedAvg and previous work even on real data. 

Weaknesses:
- I found the notations of the main theorem a bit confusing, with K being the number of rounds (which is what I think would typically be called T), and T the number of updates in each round. 
- Theorem 4 and the fairness analysis is a bit hard to understand in the case of smooth + strongly convex losses. It is also a bit weak in that i only looks at 2 clusters. However, this weakness is partially made up for through the experiments. 
- It is possible I missed this, but the authors seem to assume that M is known in advance, since it is provided as an input to the algorithm. How can one estimate/upper-bound the number of clusters? This seems that it would require to run the clustering first, before actually knowing M, and evaluating how close the data distributions are in each cluster. 
clarity,_quality,_novelty_and_reproducibility: The work and definition of fairness are original. Results are supported by theorem and proofs as well as experiments. 
summary_of_the_review: I think this is a good paper that studies an important problem and provides a comprehensive (both theoretically and practically) solution to said problem, and as such recommend acceptance into the program
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of training fair models in federated learning with heterogeneous agents. The authors proposed a new fairness metric which is the maximal difference of excess risks for any pair of agents. The authors then proposed an algorithm which is based on the Expectation-Maximization algorithm, that clusters the similar agents into groups and minimize the fairness-violation loss.

Theoretically the convergence guarantee for the proposed algorithm was provided for linear agents, and non-linear agents with smooth and strongly convex loss functions. Empirically the authors compared the proposed algorithm with FedAvg, q-FFL (Li et al., 2020b) and AFL (Mohri et al., 2019), showing that the proposed algorithm performs better under the proposed fairness criteria.
strength_and_weaknesses: Strength:
- Learning fair models in federated setting with heterogeneous agents is an important research problem. The proposed fairness criteria minimizes the maximal difference of excess risks for any pair of agents which is a natural criteria to use.
- The FOCUS is based on the Expectation-Maximization algorithm which is very intuitive.
- Both the theoretical convergence guarantees and experimental comparisons are studied carefully, and the experimental results demonstrate the effectiveness of the FOCUS algorithm in minimizing the proposed fairness loss.

Weakness:
- First concern is about the scalability of the proposed fairness criteria and algorithm. The proposed metric minimizes the maximal difference of excess risks for any pair of agents, whose evaluation requires looking at all the pairs of agents --which grows exponentially with the number of agents. It seems that even evaluating such a fairness criteria is computationally-expensive with a large number of agents.
- Following the scalability concern, the EM algorithm also tends to have a slow convergence.
- The experimental comparisons are comparing the proposed algorithm ---which is designed to minimize the proposed fairness loss ---to other methods which are not designed for that. I think a fair set of comparisons should include the performance of FedAvg if that is also using the clusters that FOCUS ends up using; and evaluating the results of FOCUS on the fairness criterion proposed in other works, e.g. the agnostic loss in AFL (Mohri et al., 2019). Moreover the runtime and computational costs should be compared as well. From the current evaluations, it is hard to conclude that FOCUS out-performs the existing methods. E.g. FedAvg is not using any clustering and outputs one single model; but FOCUS is allowed to return M models to the agents.

Typos:
- Equation (2), $\Epsilon$ missing the subscript $e_1$
clarity,_quality,_novelty_and_reproducibility: Overall the paper is written nicely and the structure was clear to follow. There was some concern on the comparisons and evaluations w.r.t. other baselines in the prior works. The implementation details and code are provided.
summary_of_the_review: Overall this paper studies an important problem ---FL with heterogeneous agents. The proposed fairness metric and algorithm are quite intuitive. The experimental comparisons are missing some necessary evaluations. I also have some concern on the scalability of the proposed approach.


---------
Post-rebuttal: I thank the authors for the detailed response to my questions and concerns! The additional clarifications and comparisons addressed my concerns on the scalability and computation cost of the proposed methods. Therefore I'd like to improve my score based on the author feedback.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies fairness in federated learning where clients have heterogeneous local data. In particular, the paper introduces a new fairness definition/measure to leverage the excess risk at each local client. Subsequently, the paper proposes an algorithm that provably outperforms FedAvg in terms of this new fairness definition under certain conditions. Empirical results on several real datasets against some baselines are provided.
strength_and_weaknesses: ### Strengths

- The exposition is generally clear in terms of setting, algorithm, theoretical results.

- Theoretical guarantees (both convergence and fairness analysis) are provided.

- Several real datasets are adopted in experiments.


### Weaknesses
- The motivation for fairness in federated learning can be strengthened. To elaborate, the abstract does not seem to motivate why fairness is important or necessary in FL. Similarly, the introduction does not seem to clearly motivate why fairness is important in FL.

- The specific design choice for fairness via agent-awareness (i.e., the equity among the difference between their excess losses) can be motivated better. To elaborate, why is equity in any form a good notion of fairness? What are the motivating use cases for this notion of fairness? 

- Related to the above point, in introduction it says
    > "we aim to define and enhance fairness by explicitly considering different contributions of heterogeneous agents" 
    
    But it seems the heterogeneity is indirectly defined through the distributions of datasets instead of _explicitly_ via some concrete quantity to measure the heterogeneity. Moreover, it does not seem to provide a clear/explicit definition for the contributions. Following this, how does this fairness relate different levels of contributions of the clients?

- The usage of Bayes optimal error can be elaborated better. For instance, how does Bayes optimal error affect the analysis, especially for regression-based analysis? What would happen if Bayes optimal error is not used? A subsequent question, how are high-quality and low-quality data defined?

- The formalization of the heterogeneity of data can be justified better. In particular, the features of the datasets are assumed to be generated from Gaussian distributions with different means but identical and isotropic covariances. And each dataset has a true underlying mean vector. Is there justification/motivation for this setting (e.g., real use-cases where data are generated in this way, or approximately)? Then, is clustering performed w.r.t. the full model parameters (treated as a high-dimensional vector)? If so, how will the clustering affect the FL performance in such high-dimensional space? 

- It seems some other related works (listed below) might also be relevant and can be empirically compared.

#### References

Tian Li et al, 2021, ICML, Ditto: Fair and Robust Federated Learning Through Personalization.

Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. Advances in Neural Information Processing Systems, 34:16104–16117, 2021. 

I believe the second reference is included in the paper
clarity,_quality,_novelty_and_reproducibility: ### Clarity and Quality

The paper is generally clearly and well-written.

### Novelty

There is some novelty in the new definition of the fairness.

### Reproducibility

The reproducibility is good.
summary_of_the_review: The motivation for the problem (i.e., fairness in FL) studied by this paper can be strengthened. There seems to be some mismatch between what is mentioned in the introduction and the main paper (e.g., contributions of agents are not explicitly/clearly defined). The approach (via Bayes optimal error) and setting (data heterogeneity) can be justified better. Overall, there is certainly merit to this paper, but in its current form, it is not ready to be published.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The main contribution of this work lies in proposing a fairness metric based on the difference between the maximal and minimal per-client excess risk for fair federated learning, which the reviewers have acknowledged to be novel.

After reviewing and responding to the authors' rebuttal, the reviewers have also raised the following main concerns:

(A) Theoretical analysis involves only 2 clusters.

(B) The number of clusters needs to be known in advance. The authors' further clarification to this issue was a rather simplistic experiment showing that if you pick more clusters, it wouldn't hurt. However, in a more realistic example, how can we know how many clusters would be enough? If we keep increasing the number of clusters, what does it compromise? 

(C) The lack of consideration of different fairness metrics in their empirical evaluation and explanations for the corresponding experimental results, for which we strongly encourage the authors to incorporate in their revised paper. Furthermore, I would encourage the authors to adopt a more appropriate perspective that no one fairness metric "rules": Being fair in one metric does not imply it is fair in another.

(D) There were some confusing claims in the paper and rebuttal that were eventually clarified. For example, the authors are referring to heterogeneity of data quality/contribution in terms of Bayes optimal loss, instead of heterogeneity of data distributions (as described in some parts of the paper). The authors are advised to revise to the former and avoid making references to the data distribution to eliminate confusion.
The authors' mention that each agent should "gain the same" from participating in federated learning added to the confusion. Fortunately, the discussion on absolute vs. relative performance perspective really helps us to understand the equity vs. fairness perspective of this work. We were initially confused by why the authors say "fairness is usually defined as the protection of a specific attribute", but it was later clarified that this does not refer to their work.

We encourage the authors to revise their work based on the reviewers' suggestions.
justification_for_why_not_higher_score: See the aforementioned main concerns (A), (B), and (C).
justification_for_why_not_lower_score: N/A.
Decision: Reject