Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper considers stochastic gradient descent convergence in a distributed setting with m workers, where up to α workers can be Byzantine, i.e. perform in an arbitrarily adversarial way. In this setting, they develop a variant of SGD which finds a second-order stationary point, prevents Byzantine workers from significantly affecting convergence, and achieves α^2 + 1/m speedup compared with the sequential case. The main idea of the algorithm is to measure deviations of gradient updates for a certain number of rounds and detect Byzantine machines which must have a significant deviation to noticeably affect the algorithm’s behavior.


If I’m correct, Lemma 3.1 allows a much simpler proof:
|\sum_{t=1}^{T-1} (ξ_0 + … + ξ_{t-1}) * Delta_t|
<= |\sum_{t=1}^{T-1} ξ_t| * |\sum_{t=1}^{T-1} Delta_t| + |\sum_{t=1}^{T-1} ξ_t * (Delta_1 + … + Delta_t)|
The first term is estimated as a sum of independent Guassians. The second term can be estimated using Azuma’s inequality (it’s a martingale since E[ξ_t] = 0 and ξ_t is independent on ξ_1, …, ξ_{t-1}, Delta_1, …, Delta_t). We can bound their norms of ξ_t by O(log (T/p)) with probability 1 - p/T.

Questions:
In Jin et al. (2019), dependence on d can be avoided when an additional assumption (Lipschitz stochastic gradient) is made. Can this work use this assumption? I believe that footnote 3 on page 4 talks about this assumption and argues that it may be too strong for practical applications, but I don’t see a reason to not get a result with this assumption. Are there technical obstacles?
Assumption 2.1, both items: the bounds are typically taken in expectation: E[||∇f(x_t) - ∇_ti ||^2] <= σ^2. Can this paper handle this kind of assumption? At the very least, one can’t immediately detect byzantine machines that deviate from the mean by more than σ.
Algorithm 1, line 11: it shouldn’t matter, but isn’t it more natural to take an average over good_{t+1}, not good_t?
Page 13, last equation: while the inequality seems to be true (since ξ_t are independent Gaussians), I don’t see how it follows from Lemma 4.2.
Page 14, Equation B.2: isn’t this way to bound the sum too loose? What’s the intuition behind this approach? Can we get a better bound with some other approach?

The following parts would benefit from an additional discussion:
While it’s clear that α^2 + 1/m comes from bounds on σ_t and Delta_t, the intuitive meaning behind the α^2 term is not clear. The reason why α=1/sqrt(m) is a threshold is also not clear.
While it may be clear from the algorithm (namely how the median behaves), I think it’s also worth explaining why the algorithm doesn’t significantly degrade when α is close to ½, unlike what one can expect.

I believe that the following places would benefit from the further expansion:
Page 13, bound on ||Delta_0 + … + Delta||^2: it’s better to explicitly write relation between B^t and Delta_t.
Page 15, “for some vector ||θ_t||”: I would explain the bound.
Page 15, “ψ_t is zero except in the first coordinate”: I would explain why.
Page 16, right after M is introduced: I would explain the first transition.

Minor issues:
While assuming that smoothness constants are 1 slightly simplifies the presentation, I believe that it makes some transitions harder to understand. E.g. bound on θ_t on page 15 would be more clear if the Hessian Lipshitz constant was in the equation.
nu should be an input/parameter of Algorithm 1
Page 13, proof of Claim B.2: it’s said that the proof is by induction, by I don’t think you use induction anywhere.
Page 13, Proof of Lemma 4.3: “Lipschitz smoothness” -> “smoothness”?

review_title: Good paper, accept

final_score: rating: 7: Good paper, accept
review_content: This paper studies distributed non-convex learning that is Byzantine resilient. The main contribution of the paper is an algorithm that is based on perturbed stochastic gradient descent, that is provably resilient to Byzantine failures, and that is guaranteed to reach near second-order stationary points of non-convex objective functions. Compared to similar works in the literature, this paper focuses on identifying Byzantine workers using a "concentration of gradients" argument that are then permanently removed from consideration for future iterations. The paper has a nice blend of algorithmic development, theoretical analysis, and detailed experiments. Overall, it is a good paper, worthy of publication in the proceedings. Before the final decision, however, I would like the authors to help address the following questions / comments of mine.

**Major Comments**

1. The permanent removal of workers from each iteration appears to be a risky strategy when one is dealing with workers' data that are not i.i.d. In particular, "RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets" is one such work that seems to be able to deal with non-i.i.d. datasets in Byzantine settings. It would be useful to see how does the proposed approach work in the presence of non-i.i.d. datasets and how does it compare to works such as the one referenced earlier.
   - A minor point, which is more of a curiosity: Is it possible for the Byzantine workers to play a colluding game where they force convergence **before** the algorithm had a chance to go through the two windows and eliminate the Byzantine workers?
2. While the paper refers to its strategy as "stochastic gradient descent", the method is really "perturbed stochastic gradient descent" that involves adding white Gaussian noise of variance $\nu^2$ to the iterates. This adds one more parameter to the problem and it is not clear how would one tune this parameter. Theorem 2.3 in the paper requires $\nu^2$ to be set according to knowledge of $\alpha$, the fraction of Byzantine workers. It is not clear from reading the paper as to how the authors set this parameter in their experiments.
3. Related to the above point, Theorem 2.3 only provides scaling guidelines for the different parameters (including the stepsize) in SafeguardSGD and even those scaling guidelines involve knowledge of $\alpha$. How does one fix these parameters and how were these parameters set for the experiments? In particular, one wonders why does the stepsize need to be a function of the fraction of Byzantine workers?
4. The statement of Theorem 2.3 needs a bit of clarification. First, it would be useful to specify the "high probability" part. What's the scaling of this high probability and it scales with which parameters? Second, what is the practical significance of "for at least constant fraction of the indices $t$"? Does this mean that the algorithm can, at the final stages of the algorithm, actually leave the neighborhood of the stationary point?
5. In Theorem C.1, part (c), the probability is lower bounded by 0.45. This does not seem like "high probability" at all. What are the implications of this assumption in Theorem C.1, part (c) on the overall results reported in the paper?
6. The experimental results are done for fixed numbers of Byzantine workers. It would have been useful to see how the performance scales with the increase in the number of Byzantine workers.
7. While this paper discusses distributed learning, Byzantine resilience in decentralized learning has also been investigated in recent works (see, e.g., Adversary-resilient distributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model). Are there any lessons for distributed Byzantine resilience from this paper that can be translated to decentralized Byzantine resilience?

**Minor Comments**

1. The range of $p \in (0,1)$ should be specified in Lemma 3.1 for complete rigor.

***Post-discussion period comments***

I am pleased with the revision the authors have posted during the discussion phase. I am also satisfied with the authors' response to my comments and to the comments of the other reviewers. I therefore recommend that this paper be accepted into proceedings of ICLR 2021.
review_title: A good paper on Byzantine-resilient distributed optimization; does need additional clarifications and discussion that *might* be doable in a revision.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
The authors present quite an interesting approach where they focus on the number of stochastic gradient evaluations rather than bounding the number of sampled stochastic functions. They converted other aggregation functions in their own formulation and then did a fair comparison. The results are in favor of the authors' method. The SafegaurdSGD algorithm is presented with several formal analysis and authors shows that why it is theoretically better to have two matrices (history record or safeguards) to mark the working machines good or bad/byzantine. The time complexity they present seems a bit difficult to understand and the argument they present for parallel speedup is also difficult to grasp as the machines are already running in a distributed environment how one can do parallel speedup? This should be presented in a clear way. The formal analysis is though rigorous but it requires a lot of time to understand as some of these notations are not defined and clearly mentioned and one has to assume some of the arguments presented to follow on.  The author presents that their method offers stronger bounds.  I appreciate the formal work and it clearly aligns with the results they have shown in the paper and in the supplementary part. The authors have studied the latest attacks introduced in literature and experimented other methods in their own introduced attack for a fair comparison which is great. Although there are several parameters that the authors do not discuss how they are chosen for the experiments they just show the experiment results for some selected values of parameters. 
The paper needs some format organization and need to define and clear something so it might become clear to other readers to understand and grasp concepts. 
The authors have already talked about the parallel speed in the introduction and instead of iterating in after Theorem 2.3, space can be used to fill with other detail or definition as it can be seen the authors are already short on space due to page limit. 
In the end, I want to say that please define notations before using them. It is quite an issue while reading the paper, you have to stop and have to find the definition. $\Omega(m^2d)$ in the introduction $d$ is not defined before. While mentioning the number of iteration required $x_0$ is not defined, $\Tilde O$ is not defined and is defined at section $2$. Lemma 3.2 $\Delta_t$ is used and then defined later. The spelling of Loewner is wrong. 
 
review_title: The paper has great formal analysis but is needs format organization and clarification

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors propose a new algorithm called SafeguardSGD, which solves the Byzantine detection problem, and tolerate less than half Byzantine workers with theoretical guarantees. Both theoretical and empirical results are provided. Compare to the baselines, the proposed algorithms show better performance on fixed Byzantine workers. In overall, I think this is a good paper.

However, there are some issues to be resolved:

1. The problem solved in this paper is actually not Byzantine tolerance, but Byzantine worker detection, which is a special case of Byzantine tolerance with stronger assumptions. The main difference is that, in this paper, the proposed method assumes that the malicious workers never change their roles (once Byzantine, always Byzantine), i.e., the indices of the Byzantine workers never change. Such assumption is not required by most of the previous works (Krum, median, Zeno), although it may not be emphasized in the previous work. With such assumption, the proposed algorithm could make the use of the historical info and remove the Byzantine worker permanently, which is why it could perform better than the baselines. I'm ok with the scenario (which is also used in [1]), but the authors should clearly state that the threat model in this paper is weaker than the previous work.

Why this assumption matters?  Note that it is unnecessary that the Byzantine workers always behaves maliciously.

Considering the following cases:

(1) The Byzantine workers behave as honest workers at the beginning, and start the attack at the middle of the training. I believe the proposed algorithm could handle this case, but it will be better if such experiments could be added.

(2) On some workers, there are some occasional and temporal hardware/software failures that produce results with huge error (flipped bits, large random noise), but such workers will recover later. In this case, it seems unreasonable to remove the failed workers from the list of good workers permanently.


2. It seems that the proposed algorithm is highly related and similar to [1]. However, the difference to [1] is not discussed in details in this paper. Furthermore, since [1] uses the same weakened threat model as this paper, it should be the most important baseline to compare to, which is not included in the experiments. I understand that there is not experiments in [1], so doing experiments for it may be difficult, but I'm not sure whether it's just difficult or totally infeasible. At least, the authors should explain why [1] is not included in the experiments.

[1] Alistarh, D., Allen-Zhu, Z., & Li, J. Byzantine stochastic gradient descent. NeurIPS 2018.
review_title: below acceptance threshold

Meta-review: The paper presents a new algorithm for byzantine resilient nonconvex distributed optimization. The presentation is clear, the motivation is solid, and the problem setting is interesting. The novelty of the present work is sufficient for publicaiton. The new scheme comes with some provable guarantees, improving the prior state of the art. Some of these guarantees are arguably not corresponding to strong operational robustness guarantees, however they compare well with convergence proofs of the related literature. Some concerns were raised with regards to comparison with some prior work, but the authors addressed it in the rebuttal.
Decision: Accept (Poster)