Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the Byzantine resilient optimization problem and proposes to use variance reduction and compression for improved convergence rates. More concretely, they propose a novel method, Byz-VR-MARINA, which integrates VR-MARINA and an unbiased gradient compressor together for Byzantine robustness. They show that Byz-VR-MARINA enjoys a better convergence rate under weaker assumptions when compared to previous works. The empirical evaluations also show that Byz-VR-MARINA has outstanding performances.
strength_and_weaknesses: Strength:
- The paper is well-written and covers a sufficient amount of related works.
- The idea of using variance reduction for Byzantine robustness is natural but it is straightforward to make the rate tight. This paper did a very good job of proving the rates under standard or weak assumptions.
- The gradient compression improves the communication efficiency but has little influence on the convergence rate.
- This paper additionally allows non-uniform sampling of stochastic gradient which is not seen in previous works.

Weakness / Possible improvement:
- What's the relation between b and m? For variance reduction techniques like SPIDER, the optimal choice of b is $b=\sqrt{m}$. If $m$ is significantly large than b, then in Table 1 (homogeneous + no compression + NC), Byz-VR-MARINA has a scaling of $c\delta\frac{m}{b} + 1/n$ which seems to be worse than BR-SGDm $c\delta + 1/n$.
- The probability p looks very interesting and can be further discussed. For example，
    - The p serves two goals in variance reduction and compression. If $b=\sqrt{m}$ for SPIDER, does it mean we may not simultaneously choose the best p for variance reduction and compression?
    - The lower bound term in (7) has a coefficient 1/p. Is it optimal?
    - Eq. (7) suggests that while variance reduction improves the convergence rate but at the same time makes the lower bound worse. Is there any way we can circumvent this? The overparameterization trick in (Karimireddy et al., 2021) seems not working as it increases the gradient size.


clarity,_quality,_novelty_and_reproducibility: The paper is quite clear with high quality and novelty. The steps to reproduce the experiment results are presented in the paper.
summary_of_the_review: I recommend accepting this paper as it gives good theoretical analysis and good empirical performance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The focus of this paper is on communication-efficient and Byzantine-robust distributed optimization. To this end, the authors propose an algorithm Byz-VR-MARINA that combines ideas from the Byzantine-robust distributed optimization work of Karimireddy et al., 2021 and communication-efficient distributed optimization work of Gorbunov et al., 2021b. The main contributions of the work include both theoretical guarantees for the proposed algorithm as well as numerical experiments that highlight the effectiveness of the proposed algorithm.
strength_and_weaknesses: **Strengths**

- This appears to be first work in the literature that focuses on communications efficiency in Byzantine-robust distributed optimization.
- The paper includes a rigorous set of theoretical guarantees for both the general nonconvex functions as well as functions that satisfy the PL condition. In addition, the analysis in the paper includes the case of heterogeneous data.

**Weaknesses** 

- In most works, the theory is presented for functions that are either strongly strongly convex or that satisfy the PL condition, but the experiments are then presented for nonconvex functions. It is strange that the experiments in this paper are only for strongly convex functions. Experiments with a total of five workers and just one of them being Byzantine are also not convincing.
- At some level, the paper appears to be a mash-up of ideas from two existing works. The authors could have done a better job of clarifying the challenges they have to face in terms of this.
clarity,_quality,_novelty_and_reproducibility: - The paper is well written and is definitely of high quality.
- The novelty of the paper is medium, because of it being a combination of existing ideas.
- The authors have provided a link to their code. But the code is simply a collection of files and the README file is barebones. It is therefore hard to judge the reproducibility power of this.
summary_of_the_review: Overall, it is a solid piece of work that primarily suffers from somewhat limited novelty and also lack of appropriate experimental results.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies Byzantine-robust variance reduced methods, and further combines them with gradient compression for communication efficiency. The paper takes a theoretical point of view, and numerical results on simple tasks such as logistic regression are provided.
strength_and_weaknesses:  **Strength:**

- S1. The theoretical perspective of proposed algorithms is studied thoroughly. 
- S2. The presentation is clear.


**Weakness:**
- W1. (Theory.) The proof of Byz-VR-MARINA seems to rely on different assumptions (see assumptions 2.3, 2.4) with other works in Table 2. Can the authors compare these assumptions, and is it possible to conclude which one is stronger? Another question is that for those convergence rates marked with x in Table 2, is it impossible to establish? Or the original paper did not report? For example, in the nonconvex setting, if combining the analysis to nonconvex SAGA and Byrd-SAGA, is it possible to get a rate? 

- W2. (Methodology.) This paper combines several techniques from existing works, such as VR-MARINA and robust aggregator. This makes the novelty boils down to applying existing works to the byzantine setting, which seems not sufficient for conferences like ICLR. 

- W3. (Experiments.) The numerical results can be improved in multiple aspects. **i)** No variance reduced method is compared. It is helpful to include the performance of e.g., VR-MARINA to verify how much the proposed algorithm is affected by byzantine workers. In addition, no alternatives from byzantine-tolerant VR methods are compared. Although Bryd-SAGA uses additional memory, but the datasets e.g., a9a, is small and such memory consumption is affordable. Even if Bryd-SAGA is not a good choice to compare with, the authors can compare to heuristics such as Bryd-SARAH / Bryd – SVRG.  **ii)** The numerical experiments do not reflect the influences of gradient compression. No runtime is compared. **iii)** Although claimed for nonconvex problems, most of tests are on logistic regression, which is convex. 

clarity,_quality,_novelty_and_reproducibility: Clarity: The presentation is clear.

Novelty: See W2

Reproducibility: Experimental details and codes are provided.

summary_of_the_review: This paper tackles Byzantine-robust distributed optimization mostly from a theoretical perspective. However, the comparison with related works seems difficult to carry out due to the different assumptions in analysis seems, hence its difficult to evaluate the theoretical contribution. In addition, the numerical results are relatively thin and cannot fully support the claimed merits.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a method for training a deep neural network in a federated fashion in the presence of malicious or misled workers who misreport their gradient contributions, aiming to reduce variance of the stochastic gradients during learning and compress. It illustrates that the reduction of variance, is, unsurprisingly, key to withstanding the activities of such workers and achieve robust learning. The paper contributes tighter guarantees than previous work in the area with fewer assumptions, as well as a method that can work under nonuniform gradient sampling.
strength_and_weaknesses: Strength
- Novel theoretical results, though mostly based on previous work on VR-Marina, a variance-reducing method.
- Interesting combination of robust aggregation and VR-Marina in a deviance setting.

Weakness
- Ambiguous and undefined terminology using a lexicographically documented ethnoreligious prejudice as a technical term.
- Use of language violating ACM guidelines on inclusiveness and non-discrimination.
- Confusing use of terminology, mixing a subset with a set.
- Lack of experimental comparison to alternative deviance-tolerant variance-reducing methods.
- Refusal to use the objective term "Deviant" instead of perpetuating an unscientific derogatory stereotype.
clarity,_quality,_novelty_and_reproducibility: Starting with the title, the paper uses an offensive term that the Association for Computing Machinery recommends be avoided in professional writing and presentations: https://www.acm.org/diversity-inclusion/words-matter

The authors made an effort to clarify their use of language and make it less ambiguous and offensive, They shortened the pejorative term to three letters, while refusing to use any of the objective alternatives suggested. They also refused to provide clear technical definitions that would not rely on a medieval prejudice in order to convey a technical scientific meaning in the 21st century.

Thereby, the authors insisted on using the essence of the pejorative term. The three-letter term offered (at times interchangeably with terms "bad" and "malicious") does not make things clearer. The kind of workers envisaged in the work are only described by reference to previous work, but their properties are not made clear and are not defined technically. The only definition given is the following on Page 1:

"there is a high risk that some participants deviate from the prescribed protocol either on purpose or not."

Thereafter, despite this formulation and disclaimer about the motives of the workers in question, the workers are still characterized interchangeably as "bad" and "malicious". The short definition given is scientifically insufficient and does include all the intended technical connotations of the term, as the authors also acknowledged. Nevertheless, even this definition, short and technically insufficient as it may be, lends itself to a neutral technical term. That is the term "deviant". The authors declined using such a technical term and insisted that the paper somehow required using a derogatory stereotype that ACM recommends avoiding, shortened to three letters.

Yet such terminology is technically unclear and ambiguous. Alluding to a pejorative dictionary definition of an ethnoreligious exonym, distorting even the way Lamport used it in 1982, does not make the term technically clearer. The claim that it does so is scientifically dubious. These authors seem to believe that science should use derogatory stereotypes presented as technical terms to move forward. This reviewer disagrees and recommends following the advice of ACM on the matter.
summary_of_the_review: The authors made some effort to improve the scientific clarity of the terms employed in the paper to properly identify the kind of workers envisaged in this context, however they fell short of providing clear technically worded definitions that would not rely on a prejudice dating back to the 15th century to convey the required scientific meaning. In fact, they even insisted that alluding to such a prejudice is necessary to convey the intended technical neaning

Therefore, unfortunately, the core definitions and terms employed remain wanting clarity and scientific precision, and there have not been solid rectification steps; the authors also bluntly refused using any of the alternative terms suggested and to provide the definitions requested by this reviewer.

In particular, the authors disputed that the use of language in their original submission, which violates ACM guidelines on the matter, was ambiguous and potentially offensive. They argued that using an ethnoreligous term with a derogatory meaning as scientific terminology is fine as long as it is abbreviated to its first three letters. They used as their main piece of evidence the fact that this term was not offensive to themselves. They declined to engage in further discussion and to respond to either the scientific or the ethical concerns raised. They expressed open disagreement regarding the ambiguity and lack of scientific clarity in the definitions employed and decided to do nothing more about it, contrary to ACM guidelines.

Nevertheless, I appreciate the dedicated scientific effort made by the authors to provide additional results comparing with alternative variance-reducing methods as they could. I also appreciate their willingness to rectify the terminological ambiguity and omit allusions to an enduring cultural prejudice of medieval origin that have no place in a peer-reviewed academic article, albeit only superficially. Therefore, I recommend acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a new Byzantine-tolerant distributed learning method called Byz-VR-MARINA, which adopts variance reduction to obtain a better convergence rate than existing methods. Meanwhile, communication compression is a bonus of the proposed method. The authors provide theoretical analysis of Byz-VR-MARINA for non-convex objective functions and the functions satisfying Polyak-Lojasiewicz inequality. Besides, empirical results of Byz-VR-MARINA and the baselines on binary classification tasks are provided.
strength_and_weaknesses: The main idea of variance reduction is well presented. I appreciate that theoretical analysis is provided for both non-convex objective functions and functions satisfying PL inequality. Meanwhile, there are also some concerns.

1. My major concern is about the proof details. The expectation notation $\mathbb{E}$ is used ambiguously in the proof details in the Appendix. Specifically, the randomness comes from both the stochastic mapping $\mathcal{Q}$ and the mini-batched estimator $\hat{\Delta}_i$. However, it is ambiguous which stochastic operator each expectation is with respect to. It increases the difficulty of checking the correctness of the proof details and would make readers confused.

2. It is claimed that communication compression is a bonus of the proposed method. However, there seems no theoretical analysis or empirical results about the communication efficiency in the paper.

3. The proposed method is very similar to VR-MARINA [1], which limits the novelty of this paper.

4. The experiments are conducted with the logistic regression model on a9a and w8a datasets. The scale of the problem is small given the current computing power and the background of distributed learning. Adding experiments on larger-scale problems would make this work more solid and convincing.

5. (minor) It seems that only the proofs for the generalized version of Theorem 2.1 and 2.2 are provided in the Appendix. It is suggested to add some details in the Appendix about how to obtain the final results when $B=0$ in Assumption E.1.

6. (minor) I am wondering why the hyperparameter setting for bucketing is presented in the paragraph that introduces the attack method IPM (page 9).

[1] Gorbunov, Eduard, et al. "MARINA: Faster non-convex distributed learning with compression." International Conference on Machine Learning. PMLR, 2021.
clarity,_quality,_novelty_and_reproducibility: Most parts of this paper are clearly written. However, the proof details are ambiguous. The novelty is limited. Please see the concerns above for details.
summary_of_the_review: Given the concerns above, this paper seems currently below the acceptance threshold to me. Meanwhile, I am willing to raise my rating if the authors could properly address the concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The work builds a distributed optimization framework that uses variance reduction as a main tool to cope with a training setting that has adversarial clients. The approach handles smooth non-convex losses, incorporates communication compression in its theoretical characterization, allows non-uniform sampling of stochastic gradients, and can deal with heterogeneous data. The approach also features a tight theoretical characterization when there is no adversarial worker (aka Byz-worker, as modified by the authors after the ethics discussions with one of the reviewers). 

The authors do a great job at explaining the background, highlighting the contributions, and summarizing the theoretical results. Numerical evidence shows that the resulting algorithm can attain better objective rates with their Byz modifications than the sota variance reduction algorithm or the distributed SGD. 
justification_for_why_not_higher_score: The numerical demonstration is somewhat stylistic with 5 workers with only one of them being 1 Byz-worker. 
justification_for_why_not_lower_score: The presentation is simply great with the proofs, contributions, and the ideas. The result is also quite solid.
Decision: Accept: poster