Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The problem of fairness in federated learning (FL) is important given the popularity of the topic and its immediate impact on the society. Vanilla FL approaches may be subject to poor performance for clients whose data is under-represented across all participants. This paper proposes a new algorithm for federated learning to reduce variance in performance across clients. The inspiration for the algorithm comes from the problem of uniform  resource allocation in wireless networks.

While the problem and the motivation for the algorithm are interesting on the high level, I think this paper does not deliver the key ideas in sufficient detail and clarity.

On the algorithms side, I am still unclear on how the Lipschitz constant L is estimated on the first run with q=0. Are the results for q=0 in the experiments reported for this run or is it repeated with the learned L? Further, this procedure suggests that the number of communication rounds is at least doubled for the end-to-end training. Tuning q, which seems to be necessary, may require even more communication rounds.

While there are a lot of experiments in the paper (across main text and supplementary), none seem to be carried out sufficiently well. Understanding the complete experimental setup for at least one of them is also quite hard due to numerous supplementary references throughout the experiments section. I would recommend to focus on fewer experiments, but present more thorough results. Below are some suggestions.

The importance of resource allocation in FL appears to me to be directly related to the key FL aspects such as degree of data heterogeneity and number of clients. This submission is lacking experiments comparing FedAvg to the proposed method under these settings (which can be simulated using available datasets). To argue in favor of the proposed approach it is important to demonstrate failure modes of the existing algorithms under some realistic scenarios and present a solution using new algorithm.

Accuracies in Fashion MNIST and Shakespeare experiments seem quite poor suggesting some problems with the setup. FedAvg paper reports 54% on Shakespeare, whereas this paper reports 52%. It also appears that the number of considered "devices" on Shakespeare is significantly smaller than in the FedAvg paper (31 vs 1146) - what is the reason for this?
On Fashion MNIST, AFL paper reports 80%+ accuracy while achieving 90%+ on the combined dataset seems relative easy based on the results mentioned on the Github repository of the dataset. This paper reports 78% for the proposed method and AFL. Why is there a discrepancy with AFL paper and what is the performance of FedAvg on this dataset (assuming some suitable CNN architecture)? Is there a reason to believe that this dataset is much harder for federated learning than MNIST, where FedAvg roughly matches full data training?

This statement is ambiguous "uniform sampling is a static method and can easily overfit to devices with very few data points, whereas q-FFL has better generalization properties due to its dynamic nature." If there is a device with very few data points it is easy to overfit to it and q-FFL will essentially ignore that device since the loss on this device is very small. Why does this not lead to more severe overfitting behavior?
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: [Summary]
The authors propose a protocol to encourage a more fair distribution of the performance across devices in a federated setting. In contrast with previous work, which protects a specific attribute, this paper aims to achieve the uniformity of the accuracy distribution.

[Key Comments]
The paper is well-organized and clearly written. The claims are well-supported by theoretical analysis and experimental results. However, my main concern is that the paper offers an incremental improvement over the early work FedAvg (McMahan et al., 2017). It would be helpful for the authors to summarize their contributions if space permits.

[Details]
[Pro 1] This paper provides insights into fairness (a more uniform accuracy distribution) in federated learning, which appears to be well-motivated.

[Pro 2] This paper provides an instructive method to estimate the upper-bound of the Lipschitz constants for ??? the local objective function (the objective function with clients' data) ???. It is an interesting idea to choose dynamic step-size depending on the global Lipschitz constants and fairness parameter q.

[Pro 3] The evaluation fully considers various uniformity metrics, sampling strategies, and the chosen of q.

[Con 1] I am confused about the difference between the proposed method and Newton's method. It would be helpful for the authors to clarify the limitation of the objective function (for example, the objective function should be second-order derivable).

[Con 2] The authors note that "It is not straightforward to simply apply FedAvg to problem (2) when q>0, as the F_{k}^{q+1} term prevents the use of local SGD." I found it difficult for me to follow this argument. Is it relevant to the parameter q? Given the communication-efficiency improvement in Section 3.3, few explanations are provided for the main improvement over previous work. Is it because of the local updating? Otherwise, more details about the convergence rate will strengthen the submission.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors propose a new optimization objective for fair resource allocation. Furthermore, a new algorithm, q-FedAvg, based on the vanilla federated learning, is proposed to solve the new optimization in massive and heterogeneous networks. The paper is well written. Theoretical analysis is also provided to support the effectiveness of the proposed methods. The experiments show good performance.
In overall, I think this paper solves an important problem in federated learning, and I vote for acceptance.
However, since my knowledge in fairness is very limitted, I think my review is an educated guess. If the other reviews vote for rejection, I will not champion this paper.

I have question to the authors:

Is the proposed algorithm robust to the estimation of the Lipschitz constant? In my opinion, the proposed algorithm highly relies on $L_q(w)$. Thus, the estimation of L will be very essential. It will be better if the authors can show some results where different estimations of L  is used, and compare these results to show the sensitivity to the estimation of L.
review_title: Official Blind Review #1

Meta-review: This manuscript proposes and analyzes a federated learning procedure with more uniform performance across devices, motivated as resulting in a fairer performance distribution. The resulting algorithm is tunable in terms of the fairness-performance tradeoff and is evaluated on a variety of datasets.

The reviewers and AC agree that the problem studied is timely and interesting, as there is limited work on fairness in federated learning. However, this manuscript also received quite divergent reviews, resulting from differences in opinion about the novelty and clarity of the conceptual and empirical results. In reviews and discussion, the reviewers noted insufficient justification of the approach and results, particularly in terms of broad empirical evaluation, and sensitivity of the results to misestimation of various constants. In the opinion of the AC, while the paper can be much improved, it seems to be technically correct, and the results are of sufficiently broad interest to consider publication.
Decision: Accept (Poster)