Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper presents a scheme for federated learning (FL) called FedVote. In FedVote, clients use binary neural networks where a latent restricted range weight vector $\boldsymbol{h}$ is learned, and stochastic rounding is applied to obtain quantized weights $\in$ {$-1,+1$}. The communication cost to the server (up-link) is reduced by using quantized weights. The server aggregates weights by summing over all the weights of the clients at each round of training and applying a sign function. This mechanism is referred to as plurality voting (ties are broken randomly). However, the paper also proposes to use soft voting, which normalizes the number of ones (cf. hard sign function) to get probability values. These probabilities are then quantized with a clipping mechanism to restricted maximum and minimum values, using predefined thresholds, and broadcasted to the clients (down-link). The latent weights of the client models are updated using the soft voting results. The paper also adapts work on reputation-based voting (Bendahmane et al. 2014) to deal with adversarial FL in the form of Byzantine attacks. The paper presents convergence analysis for FedVote under the independent and identically distributed data setting. Empirical evaluations is conducted on two datasets ,Fashion-MNIST and CIFAR-10, and applied to two models, LeNet-5 and VGG-7, respectively.

main_review: Mainly, the paper has the following weaknesses:

- The main proposed method (FedVote) is incremental at best, and the proposal on the adversarial aspect (Byzantine-FedVote) is limited. The normalization mechanism potentially requires careful tuning. Binary weights reduce uplink communication, but downlink savings depend on probability quantization scheme.

- Confined to using binary neural networks

- It is not clear how the quantization of probability values for soft voting are set (i.e., predefined thresholds) and the effects on performance.

- It is not clear how the predefined coefficients ($\beta$) are set as it relates to reputation-based voting, and the effects on performance.

- Empirical evaluations is limited:
  - Several other machine learning models/benchmarks are not evaluated on (e.g., [LEAF: A Benchmark for Federated Settings, Caldas et al. 2019]).
  - For test accuracy experiments, the number of clients used and the number sampled each round is not given.
  - For communication efficiency experiment, the number of clients used ($M$=31) is quite small (e.g., [Hsu et al. 2019] uses 100 clients). Down-link GB not accounted for.

- Preliminaries should be provided on adversarial FL/Byzantine attack.

- Information on measuring energy usage (Table 4) not provided.

Are Figure 4 (a) and (b) correctly labeled? 

summary_of_the_review: The contributions in the paper are limited and not well-focused. Overall, I do not think the paper is at a level for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to reduce the communication cost for federated learning while ensuring that the aggregation method at the server is tolerant to the presence of Byzantine clients. Towards this instead of communicating the local update/gradients or their quantized version, this paper proposes to communicate the quantized model weights to the server. The server performs the aggregation in the quantized space and communicates the aggregate value back to the clients. To enable faithful quantization of the weights during the communication with the server, each client learns normalized weights (by applying a coordinate-wise normalization function to the latent weights). 

The paper also proposes a weighted aggregation mechanism at the server that takes the reputations of different clients into account.  

The paper analyzes the impact of the weight quantization on the convergence of the underlying federated learning algorithm in an i.i.d. setting. Empirical evaluations on Fashion-MNIST and CIFAR-10 show that the proposed method outperforms existing local update/gradient compression-based schemes. 

main_review: Strengths:

1) The paper presents a novel communication efficient federated learning algorithm that quantizes local model weights as opposed to quantizing the local gradients. The paper employs the existing approach of quantizing normalized versions of latent weights to achieve this objective.
2) The paper address the issue of Byzantine clients and proposes a weighted aggregation method to counter such Byzantines.
3) Theoretical and empirical results in the paper showcase the utility of the proposed algorithm. 

Weaknesses:

1) What purpose does Lemma 1 (one-shot FedVote) serve? The assumption that all the error events are i.i.d. would most like not to hold in a multi-round setting. Even in a single round, would one need independent initializations at different clients for the analysis to hold? Also, why can the probabilities $epsilon_{m, i}$ not be arbitrarily close to 1.

2) Section 4.3 states that (without weighted aggregation) the proposed method is going to be vulnerable to the presence of Byzantines as (on average) it behaves as the FedAvg (Lemma 2). Is this conclusion correct even when one is ensuring weight normalization at the clients?

3) In Section 6, what is the underlying quantization rule when sending ternary weights to the server.

4) Please make the plot colors consistent across Fig 1(a) - 1(c).

5) In the introduction the authors claim that "However, directly quantizing the gradient vector does not provide the optimal trade-off between communication efficiency and model accuracy."  Is there any prior work that supports this blanket statement?
summary_of_the_review: The studies an important problem in the context of federated learning, namely designing communication efficient learning algorithms in the presence of Byzantine clients. The paper presents an interesting weight quantization-based algorithm and analyzes its convergence in an i.i.d. setting. The authors also demonstrate the superiority of the proposed algorithm on existing communication efficient federated learning algorithms in the literature on two standard image classification benchmarks. 

That said, there are some questions that remain about the claims made in the paper (see weaknesses above).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper provides a voting-based quantized model averaging method for federated learning. The convergence is proved and the experimental results on Fashion-MNIST and CIFAR-10 show that the proposed scheme outperforms existing schemes.

main_review: I like the topic of this paper, but I have some concerns as below.

1. Explanation on the huge gap between FedVote and SignSGD with majority vote [Bernstein’18]. 
    1. It seems like the basic concept of FedVote is from [Bernstein’18]. I’m bit curious why FedVote has some gap compared with [Bernstein’18]. Is it because of the weighted voting strategy of FedVote? Can we do some ablation study to check what made FedVote such powerful, compared with [Bernstein’18]?
2. Comparison with other Byzantine-tolerant schemes
    1. There have been many previous works on Byzantine-tolerant schemes, e.g., using coding scheme to defend Byzantine attacks, DRACO[Chen’18], DETOX[Rajput’19], Election coding [Sohn’20], SignGuard[Xu’21], ByzShield [Konstantinidis’21]. Especially, the last four works focus on the voting-based model/gradient averaging. I think this paper should at least mention these works, and also compare the performance. 
    2. There have been naive methods of using median or mean of median schemes for tolerating Byzantines, starting from 2017, e.g., KRUM, multi-KRUM. I guess this paper didn’t compare with these naive methods also. 
    3. After the [Bernstein’18], there have been upcoming works [Karimireddy’19] suggesting that error feedback fixes the issue of SignSGD. I’m not sure whether the authors compared their work with this scheme. 
    4. So in general, I thought that the literature search and comparison is bit weak. SignSGD is 3-year old paper, and there have been many other papers using voting-based aggregation for Byzantine tolerance. 

[Bernstein’18] https://arxiv.org/abs/1802.04434
[Chen’18] https://arxiv.org/abs/1803.09877
[Karimireddy’19] http://proceedings.mlr.press/v97/karimireddy19a/karimireddy19a.pdf
[Rajput’19] https://proceedings.neurips.cc/paper/2019/hash/415185ea244ea2b2bedeb0449b926802-Abstract.html
[Sohn’20] https://proceedings.neurips.cc/paper/2020/hash/a7f0d2b95c60161b3f3c82f764b1d1c9-Abstract.html
[Xu’21] https://arxiv.org/pdf/2109.05872.pdf
[Konstantinidis’21] https://arxiv.org/abs/2010.04902
summary_of_the_review: This is an interesting paper, but the idea is quite similar to SignSGD paper, and has no thorough comparison with existing works. Better comparison & ablation are needed to better understand why FedVote works better than existing schemes.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The author(s) proposed a new algorithm based on plurality voting for federated learning with quantized gradients. Convergence theory is developed and experiments on both iid and non-iid datasets are conducted to evaluate the proposed method.
main_review: **Pros**:
- The paper is well-written and related works are well-address to my knowledge.
- Has a nice introduction on quantized neural networks, which is good for readers that are not familiar with the topic.

**My Questions**: I have some questions on the theory side of the paper.

- The author(s) described the convergence of FedVote in terms of $|| f(\tilde{w}^{(k)}) ||^2$, which is a valid measure of stationarity for continuous problems. I wonder what is the conclusion to the discrete problem? For example, we have a stationary point $w^*$ such that $|| f( \tilde{w}^* ) || = 0$. Then what conclusion can we obtain for the following problem
$$ 
	\min_{w \in \mathbb{D}^2_n} f(w).
$$
Can we say that we are at a global minimum in the convex case?

- In Lemma 1, the author(s) define $s_i =\frac{2}{M} \sum_{i=1}^M \epsilon_{m,  i}$. From the definition we know $s_i \in (0,  2)$. Why the author(s) conclude that $s_i \in (0, 1)$?

-  Theorem 1 describes the convergence of FedVote for $\eta$ that satisfies the assumption. I wonder why the author(s) do not give a Corollary on the convergence rate for a particular choice of $\eta$ (which is usually done in the literature, e.g., see the analysis in [1])? It is not straightforward for readers to see the convergence (or non-convergence) without a concrete choice of $\eta$.

- In Remark 2, the author(s) mention that the variance of quantization error will impede the convergence, which also holds for FedPAQ. However, I do not see any non-convergence issue of FedPAQ from [Theorem 2, 1]. Could the author(s) explain more on the non-convergence of FedPAQ?

- On the theory side, could the author(s) elaborate the advantages of the proposed method over FedPAQ?

[1] Reisizadeh et al. FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization. AISTATS 2020.
summary_of_the_review: I have some questions about the theoretical analysis of this paper. I hope that the author(s) could kindly elaborate.
review_title: null

Meta-review: Reviewers raised several valid concerns about novelty of quantization idea and lack of discussions related to prior art (AISTATS 2020 paper). The rebuttal did not convince the reviewers to raise their score. We hope the authors will benefit from the feedback and improve the paper for future submission.
Decision: Reject