Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers the problems of communication efficiency, Byzantine robustness, and privacy in federated learning (FL). The paper focuses on sparsification for compression (in order to achieve communication efficiency), and analyzes what are conditions on sparsification to ensure that the expected pairwise l2-distance between client updates after sparsification remains bounded. Next, the paper proposes a sparsification technique -- consensus sparsification, which is a two-phase scheme that ensures that all clients agree on the same set of coordinates. The paper then combines it with a hierarchical scheme to enhance privacy, wherein sparsified updates from a subset of clients are first aggregated using secure aggregation, and then a robust aggregation is applied on top for Byzantine robustness. The paper analyzes the convergence rate for the proposed scheme.
strength_and_weaknesses: **Strengths:**
1. The paper considers a practically important and intellectually challenging problem of simultaneously achieving communication efficiency, Byzantine robustness, and privacy.

2. The analysis of sparsification schemes to ensure assumptions in Def. 1 ($(\delta, c)$-robust aggregator) is interesting. 

**Weaknesses:**
1. For privacy, the paper proposes a hierarchical approach where clients are randomly partitioned and then an aggregate update is computed for each partition using secure aggregation. This is essentially the bucketing approach from [Karimireddy et al. ICLR 2022] with additional secure aggregation. From the perspective of novelty, this is fairly limited. More importantly, this method would only enhance privacy, but there is no analysis about how much is the enhancement. (In fact, the authors acknowledge at the end of Sec. 3 that further study would require to quantify the privacy leakage.) On the other hand, the paper claims in the Abstract and Introduction (Table 1) that their method is privacy-preserving. This seems like a bit of over claiming. 

2. The analysis in Theorem 1 is to ensure the assumptions in Def. 1 ($(\delta, c)$-robust aggregator). The assumption of bounded pairwise distances is sufficient, but it is not discussed if it is necessary. Can there be another definition for a robust aggregator that does not need to assume bounded pairwise distances? There may be empirical robust aggregators that perform decently even without the assumption of bounded pairwise distances. It would be important to discuss this point. 

3. The $\epsilon$ parameter of DP in Theorem 2 seems to be quite large. In particular, it is of the order $O\left(\frac{\frac{K}{m}(d - \frac{K}{m})}{\alpha}\right)$, which seems to be at least $O(d)$. Since deep neural networks have large $d$, the value of $\epsilon$ may be too high for practice. It would be important to discuss this further.

clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality:** The presentation has a good level of clarity and technical quality seems good enough. 

**Novelty:** The novelty is a bit limited for the following reasons. 
* As mentioned in the previous section, while the sparsification scheme is interesting, the novelty of FedREP is quite limited. 
* The convergence analysis seems to follow directly from [Stich et al. 2018] and [Karimireddi et al. 2022]. It would be helpful if the authors can explicitly specify what are the new challenges in the analysis (if any). 
* Empirical results are restricted to CIFAR-10 and ResNet-20. It would be good to consider other datasets (e.g., some of the LEAF datasets) and model architectures. 

summary_of_the_review: My main concerns are mentioned in the section on Weaknesses. Due to these issues along with a limited novelty, it seems to me that the paper is not yet ready for publication. 

Additional suggestions and questions to improve the quality of the presentation are give below:

1. In Theorem 1, it is not clear why the conditions $\sum_{j\in[d]} \xi_{k,k’,j} =1$ and $\sum_{j\in[d]} \zeta_{k,j} =1$ will be satisfied. Is it assumed that update vectors are normalized? 

2. Footnote 3 mentions that random quantization can be adopted for “more privacy preservation”. What do the authors mean by “more privacy preservation”? Why would random quantization increase the level of privacy?

3. On page 2, it is mentioned that there are two ways to achieve privacy: differential privacy and secure aggregation. This is a bit misleading. Secure aggregation does not guarantee the privacy of training data, but only ensures the privacy of computation (i.e., aggregation operation). In other words, SecAgg ensures that the clients (and the server) observe only the aggregate model and cannot learn individual model updates. DP would be necessary to ensure input privacy. (For instance, in case of only 2 clients, even when secure aggregation is used, each client can compute the model update of the other client from the average.) It will be helpful to discuss this.

4. Before stating the main contributions, the paper claims that: “we theoretically analyze the tension among Byzantine robustness, communication efficiency and privacy preservation, and propose a novel FL framework called FedREP”. The paper analyzes the tension between sparsification and the condition required by $(\delta, c)$-robust aggregator. In other words, the tension between communication efficiency and Byzantine robustness. It is not cleat where the tension between the privacy and the other objectives is analyzed. It would be good to give a bit more details.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper propose the first federated learning system which supports privacy, communication efficiency and byzantine-robustness. Specifically, it designs a consensus sparsification protocol to compress the update and also keeps compatible with secure aggregation and robust aggregation.
strength_and_weaknesses: Strength:
1. Reconciling byzantine robustness, communication efficiency and privacy is an important topic in federated learning system design.
2. The evaluational results show reasonable trade-off between the three dimensions.


Weakness:
1. The authors did not discuss the potential malicious behavior during the consensus sparsification. What if some malicious client always upload misleading $I^t_k$? Will that affect the robustness or the privacy of the protocol?
clarity,_quality,_novelty_and_reproducibility: Clarity: The method is clear and correct.
Quality: The quality of the proposed method is good.
Novelty: The novelty of the proposed method is marginal.
Reproducibility: The authors provide the code for reproducibility. I do not have the chance to run it.
summary_of_the_review: The paper is a borderline one. I slightly tend towards acceptance but I am okay either way.

The biggest problem is that the authors do not discuss the influence of potential malicious attacks during the sparsification step. This makes the privacy guarantee questionable.

----------------------------------------------------------
Thank you for the rebuttal. I decide to keep the score after reading it.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors study the conditions that a communication compression method should satisfy to be compatible with existing Byzantine-robust methods and privacy-preserving methods. The core of their proposed method is consensus sparsification, which is a variant of top-$K$ sparsification with additional memory and a random selection component aiming at obscuring exact coordinates for sparsification. Their idea is that as long as the clients agree on non-zero coordinates, the dissimilarity among clients reduces, which is intuitive while they achieve communication saving through sparisification and preserve privacy by applying SecAgg off the shelf. 
strength_and_weaknesses: I think the paper is well-written. There are interesting algorithmic elements including the introduction of random variable $r_k^t$ with binomial distribution to improve privacy. The related work are sufficiently studied. I think ConSpar along with SecAgg is an interesting algorithm in terms of addressing communication costs and privacy risks. However, I am not sure it is much interesting in terms of  robustness. 

1- The main weakness of this paper is that the considered attacks are very simple and not designed for ConSpar, which will be elaborated in the following: 

- The type of attacks considered are mainly attacks effective against Krum and comed. What if an adversary constructs ${\cal I}_k^t$'s that target the **most informative coordinates of average update of honest clients** and make them zero. In that case, even if the server  perfectly detects all Byzantines, the server can only figure out the average of least informative coordinates of  good client, which does not help the server to learn an effective model. In particular, an attack, which tries to remove the most informative coordinates from the aggregate of good updates should be considered. I also checked the results in Appendix C.2. However, those experiments do not consider this attack. 

2- Regarding FoE attack. I am not sure why  the hyperparameter is set to 0.5. Xie et al., 2020a proposed to apply a number of $\epsilon$'s including 0.1 and 10 so I am curious why the authors selected 0.5? 

3- The idea is that sparsification makes the clients updates closer to each other. The smaller dissimilarity in Proposition 1 implies that it is easier fo find $\frac{1}{|{\cal G}|}\sum_{k=1}^{|{\cal G}|} \tilde g_k$. However, it does not guarantee anything about the quantity of interest $\frac{1}{|{\cal G}|}\sum_{k=1}^{|{\cal G}|} g_k$. Note that $\frac{1}{|{\cal G}|}\sum_{k=1}^{|{\cal G}|} \tilde g_k$ may be arbitrarily different from $\frac{1}{|{\cal G}|}\sum_{k=1}^{|{\cal G}|} g_k$. 

4- Definition 1: The upper bound $\rho$ for (Karimireddy et al., 2021) holds only for those good clients but Definition 1 includes a bound on all $m$ clients.

5- "As shown in previous works (Karimireddy et al., 2021), many widely-used aggregators, such as Krum (Blanchard et al., 2017), geoMed (Chen et al., 2017) and coordinate-wise median (Yin et al., 2018), satisfy Definition 1." 

- Could you specify where this is shown in (Karimireddy et al., 2021)? It is shown that Krum and coordinate-wise median are vulnerable to simple attacks (Fang et al., 2020; Xie et al., 2020). I am not sure how much Definition 1 is meaningful in terms of robustness in practical settings. 

Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to byzantine-robust federated learning. In Proc. USENIX Security Symposium, 2020.

Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantinetolerant SGD by inner product manipulation. In Proc. Uncertainty in Artificial Intelligence Conference, 2020.

6- Assumption 5 does not hold even for a quadratic loss function. Can the author clarify why Assumptions 3 and 4 are not sufficient to establish convergence guarantees?  

7- "Even with quantization, ... suffers from heavy communication cost."

- One advantage of unbiased quantization schemes is that the same test accuracy as the uncompressed baseline is achievable while achieving communication efficiency. It is unclear how much test accuracy is lost under same hyperparameters tuned for uncompressed baseline if someones uses consensus spartifications under no attack scenario?




clarity,_quality,_novelty_and_reproducibility: The paper is mainly clear. In terms of quality, it is OK, which has room for substantial improvement. To the best of my knowledge, the idea of ConSpar is novel. However, SecAgg, local memory, local updating, and bucketing are pretty standard. The experimental setup is sufficiently described.  
summary_of_the_review: The key idea of this paper is consensus sparsification, which is a variant of top-$K$ sparsification with additional memory and a random selection component to improve privacy. ConSpar along with SecAgg is an interesting algorithm in terms of addressing communication costs and privacy risks. The main weakness is w.r.t. robustness. The attacks considered are very simple and not designed for ConSpar. I think the smaller dissimilarity in Proposition 1 does not imply improved robustness.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This submission introduces a local sparsification scheme in the federated learning setting to reduce the data transmission burden. The scheme starts with sampling certain ratio of coordinates with largest magnitude, before adding in some randomly selected coordinates to meet the pre-designated sampling budget.

The authors intend to prove that the suggest sparsification scheme has differential-privacy property, and also shows the convergence of the resulted federated learning algorithm.
strength_and_weaknesses: Strength:

--> the structure of this submission is clear.

--> Proposition 2 about the contraction property of the proposed ConSpar algorithm is useful for the general community.

Weakness:

--> Some proof steps are problematic.

--> The writing should be overhauled.
clarity,_quality,_novelty_and_reproducibility: General comments:
1. Not including the algorithm in the main text does incur inconvenience for the reading experience.
2. Please state Theorem 2 clearly: what is the algorithm $\mathcal{M}$, what are input datasets $\mathcal{T}_{1,2}$, and what are corresponding possible output $\mathcal{S}$. So far the statement of theorem 2 is unclear and therefore the proof is impossible to follow.
3. I recommend that authors submit core code for experiments in the supplementary materials.
4. The statement for theorem 3 and 4 should be very explicit to distinguish their differences (wrt to difference optimization algorithms for local clients). I recommend the authors polish the narrative of the paper: be concise in textual description, and be clear and specific in theorem statement.

Specific comments:
1) On page 5, the update formula for $\mathbf{u}^{t+1}_k$ is  $\mathbf{u}^{t+1}_k= \mathbf{u}^{t}_k - \widetilde{\mathbf{g}}^t_k$. This is inconsistent with the expression for $\mathbf{u}^{t+1}_k$ on page 6.
2) What is $\Gamma$ in Figure 2 in Section 5?
3) Buffers $\mathbf{b}_l$ are used on the FedREP Server side. I do not see any involvement of buffer quantities in the optimization proof. It is okay to only include buffer as a practice hack. For theory statement, please be specific.
4) To make the proof more helpful to wider audience, I suggest authors to add some explanation about the motivation of considering $\widehat{\mathrm{w}}^{t+1}$ in equations (145) and (224) respectively. These two steps are decisive for setting up the entire optimization argument.
summary_of_the_review: The optimization proof did not include the buffer steps, which are stated in the main algorithm.

The writing of the paper needs major overhaul. The description of technical details should be direct to the point, specific and explicit, and the statement of theorems must be rigorous and detailed.

I recommend rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a technique for reducing communication in multi-silo FL. The technique is referred to as consensus sparsification and is a two-phase scheme that ensures that all clients agree on the same set of coordinates with additional randomization to ensure a level of differential privacy. The paper then combines it with a hierarchical scheme to enhance privacy and robust aggregation is applied on top for Byzantine robustness. The paper analyzes the convergence rate for the proposed scheme and empirically evaluates it against some other communication-efficient baselines.
Sparsification is a potentially useful way to reduce communication (although many more advanced techniques are known). The particular approach presented in this work is new and promising. However reviewers have found and detailed a significant number of issues with presentation and clarity of this work suggesting that it would benefit from a major revision.
justification_for_why_not_higher_score: Low scores from the most informed reviewers.
Decision: Reject