Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers gradient compression in federated/distributed learning with two additional requirements: robustness against Byzantine clients and differential privacy (DP). The paper proposes a sign-based gradient compression method, called $\beta$-stochastic signSGD, which applies clipping and a stochastic sign operator to gradients (Definition 3) for compression. SignSGD, which simply applies a sign operator to gradients was proposed in [Bernstein et al., 2019], and its stochastic version was proposed in [Jin et al., 2020]. The method proposed in the paper reduces to that in [Jin et al., 2020] for $\beta = 0$. The paper presents convergence result and DP guarantees, along with experimental results. 
strength_and_weaknesses: **Strengths:** 

1. The family of sign-based compressors is practically appealing, and the paper proposes an interesting variant of stochastic signSGD. 

**Weaknesses:**

1. The paper does not cover all details and the technical presentation leaves open several questions. For instance, the paper does not discuss any upper bound on the number of Byzantine clients $\tau(t)$ in an FL iteration. It is well-known in Byzantine robustness literature that, when the fraction of Byzantine clients is greater than 1/2, then it is not feasible to achieve robustness. Remark 1 discusses the case of sufficiently large $\tau(t)$, which is quite confusing. (Other comments and suggestions are mentioned later). 

2. The paper does not give details on whether DP guarantees are for client-level or item-level privacy. There are also no empirical comparisons with DP-SGD and/or local-DP algorithms with the proposed method. 

3. The $\epsilon$ of DP for the proposed method is $O(d)$, where $d$ is the number of parameters of ML model (i.e., the length of gradients). This is going to be significantly large for several ML models such as deep neural networks. Would such a high epsilon be practical in terms of DP?

clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality:** The presentation can be significantly improved. There are several questions that need more details:

1. What is an upper bound on the number of Byzantine clients that the method can tolerate? The second part of Theorem 5 only considers a lower bound on $\tau(t)$. What is the upper bound on $\tau(t)$ up to which equation (6) holds? As mentioned under ‘Weaknesses’, when the fraction of Byzantine clients is greater than 1/2, then it is not feasible to achieve robustness. Without such an upper bound on $\tau(t)$, it is not possible to assess the correctness of the result, and it is critical to add details.

2. Is there any upper bound on $\beta$? The $\epsilon$ value of the DP guarantee is $d \log\left(\frac{2B + \beta}{\beta}\right)$, and larger values of $\beta$ may be able to lower $\epsilon$. However, the paper does not discuss details about how large can $\beta$ be.

**Novelty:** Considering [Jin et al., 2020], the novelty of the method is fairly limited. The main novelty is in terms of analysis. I did not go through the detailed proofs.  

1. The result of Theorem 1 is quite straightforward.

2. For adaptive adversaries, the method can support the following upper bound on the number of Byzantine clients: $\tau(t) \leq \frac{2}{p^2} \log\frac{6}{c}$, where $p$ is a probability with which a client participates in a FL round and $c$ is a positive constant. When $p = O(1)$, then the $\tau(t)$ seems to be a constant, and it would not increase with the number of clients. In contrast, several prior works on Byzantine robust FL can tolerate a constant fraction of Byzantine clients (as opposed to a constant number of Byzantine clients). 

3. Empirical results only consider a multi-layer perceptron (MLP) model. It would be helpful to understand how the proposed method performs on more sophisticated models such as CNNs and deeper networks such as ResNet.
summary_of_the_review: The proposed method of $\beta$-stochastic signSGD and the analysis are interesting. However, there are several questions that need to be addressed before the paper becomes ready for publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides the first algorithm based on sign SGD, which achieves Byzantine resilience and differential privacy.
strength_and_weaknesses: 1)Author motivates the subject from a theoretical and practical point of view. 
2)In the introduction, the author reviewed the previous works carefully. 
3)the author successfully addressed the issue and recommended the algorithms.
4)The authors successfully provide simulation results for their algorithm.
5)The proof is mathematically correct.


clarity,_quality,_novelty_and_reproducibility: 
1)Author motivates the subject from a theoretical and practical point of view. 
2)In the introduction, the author reviewed the previous works carefully. 
3)the author successfully addressed the issue and recommended the algorithms.
4)The authors successfully provide simulation results for their algorithm.
5)The proof is mathematically correct.

summary_of_the_review: I think this is a good paper and should get accepted. But, the writing should improve.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes an optimization algorithm $\beta$-stochastic sign SGD. The authors proves that $\beta$-stochastic sign SGD is differentially private in the case of $\beta > 0$. The authors also show that $\beta$-stochastic sign SGD achieves Byzantine resilience under some problem assumptions.
strength_and_weaknesses: Strength: 
1. The paper shows that $\beta$-stochastic sign SGD achieves communication efficiency, differential privacy, and Byzantine resilience simultaneously.
2. The proposed algorithm is very practical, easy to implement, and have good performance in MNIST and CIFAR-10 datasets in experiments. 

Weakness:
1. The technical contribution in proving differential privacy of $\beta$-stochastic sign SGD is not that significant. 
2. The assumptions for bounded gradients and sub-Gaussian element-wise gradient noise are kind of strong for federated learning or requires more justification, and these two assumptions again make the technical contributions less significant. 
3. More discussions with existing works such as [1] are needed for comparing the final error bounds for Byzantine resilience.
4. Basically, the reviewer gets the idea that $\beta$-stochastic sign SGD achieves two-fold benefits, but wants to see some comparisons with existing works in each dimension, so that the paper is more persuasive in that $\beta$-stochastic sign SGD achieves performances matching the state of the art of at least comparable, and the technical challenges therein is non-trivial given that the algorithm itself is not that novel. 
5. In the experiments, it seems that the authors tune the algorithm to find good parameters $B$, which makes the algorithm less practical since it means that this algorithm needs to be run several times to achieve good performance (this will contradict to the target benefits of the algorithm), so a good estimate of a favorable $B$ would be helpful. 
6. Can the authors add some experiments to compare the performance of $\beta$-stochastic sign SGD with other existing algorithms either designed for DP or Byzantine resilience?


[1] Karimireddy, S. P., He, L., & Jaggi, M. (2021, September). Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing. In International Conference on Learning Representations.
clarity,_quality,_novelty_and_reproducibility: 1. The reviewer does not quite follow why Theorem 1 is a standalone result, it seems to me it is an intermediate lemma for proving convergence, can the authors provide more explanations?
2. The definition of sub-Gaussian has a typo that one side should be $-t$.
summary_of_the_review: This paper has a very interesting finding that $\beta$-stochastic sign SGD achieves Byzantine resilience and differential privacy simultaneously. It will help the reviewer to understand the contributions of this paper better if there were more performance comparisons of $\beta$-stochastic sign SGD with existing methods designed for DP or Byzantine resilience only, whether they are comparable theoretically or in experiments in each dimension, and maybe some more explanations on the significance of the presented results.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors propose a new communication compression method called $\beta$-stochastic sign SGD, which is Byzantine-resilient and differentially private. The authors provide theoretical results about differential privacy and convergence. Besides, the proposed method is empirically compared with SignSGD and FedAvg.
strength_and_weaknesses: **Strength**: The main idea of randomly flipping the sign is easy to understand and makes sense. The proposed method is not hard to implement.

---
**Weaknesses**: 
1. The novelty of this work is limited since the proposed method seems to be a combination of stochastic sign SGD and random flipping.
2. The $L_1$ norm of gradients can be directly bounded by $\sum_{i\in[d]}B_i$ according to Assumption 3. It seems that the constant terms in the right-hand side of (5) and (6) are very likely to be not smaller than the trivial upper bound $\sum_{i\in[d]}B_i$. Could the authors compare the results in Theorem 5 with this? 
3. The empirical results are not solid enough. The proposed method is only compared with SignSGD and FedAvg. Comparing $\beta$-stochastic sign SGD with more Byzantine-resilient methods is required.
4. This paper is not well-written.
  - $\beta$ is frequently used before being formally defined in the abstract and the introduction. Besides, $d$ appears in the statement of contributions (page 2) without any definition.
  - It is ambiguous what the notation $\nabla F_i(\cdot)$ means. Does it mean the partial derivative w.r.t. the $i$-th variable (i.e., the $i$-coordinate in the gradient)? If so, it is highly suggested to use $\nabla_i F(\cdot)$ or $(\nabla F(\cdot))_i$ since the original notation is very likely to be confused with $\nabla f_m(\cdot)$, which denotes the gradient of function $f_m(\cdot)$.
  - It is highly suggested to explicitly clarify which norm the notation $||\cdot||$ in Assumption 2 denotes.

clarity,_quality,_novelty_and_reproducibility: - This paper is not well-written. 
- Several claims are not well-supported. 
- The novelty of this paper is limited. 
- There are almost no concerns about reproducibility.
summary_of_the_review: Although the proposed method is easy to implement, given the concerns about novelty, quality, and readability, this work is currently below the bar of ICLR.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposed a new optimizer for federated learning, generalizing upon a stochastic version of signSGD due to (Jin et al. 2020), that enjoys byzantine robustness and differential privacy.  Reviewers liked the simplicity of the algorithm and the promising set of experiments (though mostly on toy-scale datasets), but find the theoretical results incremental or not quite informative (e.g., with large epsilon parameters for DP than typically considered a meaningful DP guarantee).   Several reviewers also found the paper hard to read.

Some of these issues were clarified in the rebuttal, but it does not change the overall level of excitement among reviewers.
justification_for_why_not_higher_score: Due to the weaknesses above.
Decision: Reject