Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the natural class of algorithms, namely *Aggregators with Gaussian noise* for distributed SGD with differential privacy (DP) and Byzantine resilience (BR). Previous results shows VN $\Rightarrow$ BR $\Rightarrow$ convergence of SGD.
The authors first show that aggregators with Gaussian noise algorithms satisfy DP but violates VN necessarily, so approximate VN is proposed. Theorem 2 shows approximate VN $\Rightarrow$ convergence. Proposition 2 shows the above algorithms satisfies approximate VN with certain parameters. With the combined bound Corollary 1, the authors observe (and then verify by experiments) that larger batch size is beneficial and in particular more beneficial than when DP or BR is enforced alone.

main_review: The paper is clearly written and provides a reasonable solution to this very interesting question. However, I do have several comments.
1. I wonder if there is any difference between the Byzantine model in the paper and the adversarial contamination model in the robust statistics community (see papers cited below). In my opinion they are the same as in both models a fraction of data are allowed to be arbitrarily changed. In particular, the interesting part of Byzantine seems to be lost since the aggregator is always trust-worthy.
2. If they are the same, then I would like to see a modular solution based on, for example, the following
    > Aggregating the gradient accurately implies SGD convergence

    Starting from here, features like robustness(=BR assuming the answer to my Q1) and/or DP can be added to the aggregator. There are robust and accurate aggregators with much nicer theoretical guarantee, e.g. [this paper](https://epubs.siam.org/doi/abs/10.1137/17M1126680). There's actually a big line of work.
    There is also [accurate robust + DP aggregators](https://arxiv.org/abs/2102.09159).
    Based on what is presented in the paper, I don't see a necessary interplay between robustness=BR and SGD convergence, so I think a modular solution is possible and better, potentially encouraging deeper observation for practice.
    In particular, the aggregators used in the paper seem to be variants of geometric medians and other versions of medians, which is one of the central objects of robust statistics. The adaptation seems to be rooted in the VN condition, which doesn't seem "widely used" as claimed in the paper. Almost all references of it are written by roughly the same group of authors. The notion of $(\alpha,f)$-BR also seems to be restricted to the same group. Following this line of work may not be the best approach and I highly recommend the authors to explore the connections and make use of existing powerful results, rather than re-inventing sub-optimal wheels.
    Of course all these comments rely on the answer to my Q1, which I might have misunderstood. I would love to hear the reply and change my rating correspondingly.
3. It's unclear to me why RHS of the bound in Corollary 1 is decreasing in $b$. The relevant part in this bound looks like $\ln(b)(C+1/b)^2$. I tested with a few different $C$ and some make it increasing while others make it decreasing. It is important to justify this point since it is one of the most important practical implications of the theory in this paper.
summary_of_the_review: Not recommended as its current form since it seems to have missed a deeper connection and hence a much nicer solution. The batch size observation also doesn't seem to be firmly supported. However, the question is interesting so I look forward to its future form.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper combined differential privacy and byzantine resilience in the distributed SGD algorithm.  The authors provide a simultaneous theoretical guarantee of DP and BR by re-tuning the algorithm. Both theoretical results and numerical experiments are conducted to show the effectiveness.
main_review: Strengths: This paper is well organized and easy to follow. The targeted problem is interesting and important. The theoretical contribution of this paper is providing the interplay between DP and BR.

Weakness:  
1. In assumptions 1-3, it requires the empirical loss function Q to be differentiable. Is that possible to extend current results for non-smooth loss? Say, the absolute derivation loss.
2. As it has been claimed in the abstract, "by carefully re-tunning the learning algorithm", how to choose the learning rate $\gamma_1,\dots,\gamma_T$? Is the proposed method robust with a certain range of learning rates?
summary_of_the_review: 1. In assumptions 1-3, it requires the empirical loss function Q to be differentiable. Is that possible to extend current results for non-smooth loss? Say, the absolute derivation loss.
2. As it has been claimed in the abstract, "by carefully re-tunning the learning algorithm", how to choose the learning rate $\gamma_1,\dots,\gamma_T$? Is the proposed method robust with a certain range of learning rates?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 
The paper studies a federated learning setting combining differential privacy (DP) and byzantine robustness (BR).  The paper shows that the "variance norm" condition for byzantine resilience needs to be relaxed as we can expect when DP is added, and then shows an adapted theorem which allows for both DP and BR.  The paper also presents a number of preliminary experiments and some interesting open questions.

main_review: 
The paper is well-written and understandable.
The result is novel, but not very surprising.
I didn't check every detail but at a high level the results seem correct.


Detail:

In Algorithm 1, please explain the meaning (what?) and importance (why?) of "without replacement" in the sampling?  Depending on the distribution D this concept may be easier or more complicated to interpret.


summary_of_the_review: 
The paper is mostly sound and brings a contribution (even if not very surprising).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of distributed learning via SGD when a fraction of workers are Byzantine and the rest want their data to be kept private. The authors consider a generic/naiive combination of Byzantine resilience (BR) and differentially privacy (DP) in Algorithm 1. They show that the VN condition is incompatible with Gaussian noised SGD, but propose an approximate VN conidtion that can be realized by noisy SGD. They then establish a convergence guarantee for the algorithm and conduct numerical experiments.
main_review: Strengths: 

-Proposition 1 and (especially) Proposition 2 are interesting 

-The problem is interesting 

Weaknesses: 

General points: 

-Measuring privacy loss in terms of privacy loss per iteration is not meaningful. Privacy loss accumulates, so it is very unusual and not informative to measure the loss of each step; instead epsilon should capture the privacy loss of the full algorithm (T rounds) to quantify the risk of inference attacks on the model  

-The significance of the VN condition is not adequately explained. How exactly is this condition relevant to BR? 

-The convergence results are not very interpretable, seem to have incorrect units 

-Writing needs a lot of work 

Specifics: 
0. Abstract

-"...rendered invalid when workers enforce DP" is not accurate for two reasons: you only show this for a particular DP protocol, namely the Gaussian mechanism; showing it fundamentally for any DP mechanism would be much more interesting. Also, what you show is in terms of the VN condition, which is not explicitly connected to BR. 

1. Introduction

-"trusted server" and "honest but curious server" are both used to describe the set up, which is confusing. Usually "trusted server" means honest and not curious (i.e. not a privacy threat). 

-"Byzantine" should be informally defined or briefly described early on before it is used many times 

-Dwork et al (2014) is a strange choice for citation for a sentence about private ML. There are many other more relevant works from 2014 to present. Also, "especially when considering neural networks" does not seem to add anything and I'm not sure I agree that neural nets are special in this sense. 

-Abadi et al (2016) is the wrong/incomplete citation for DP SGD: Bassily et al (2014) and Song et al (2013) considered DP SGD earlier. 

-Theorem (Informal): should state conditions on loss; need to define (or informally explain, at the very least) "approximated VN" before using it in a theorem; paragraph following Theorem is too much detail for not having defined VN

-"parameters have very little impact in most settings when considering DP or BR separately" is not clear 

-Figure 1. Is the number of iterations fixed? 

2. Problem Settign 

-"common dataset" what does this mean? Are the m points divided/partitioned among n workers or all workers have access to D? 

-"*By far, the most widely used* approach....is *the* differentially private version...": strong claim made without any evidence; also, there are many ways to provide DP besides Gaussian noise, so there is no single "the" DP version of SGD. 

-**"we are mainly interested in...per-step...privacy": Why?! This is not nearly as meaningful. If T goes to infinity then essentially the algorithm provides no privacy at all but your epsilon might still be small, which is very misleading.**

-Def 2: explain intuition; provide an example of a BR GAR

Section 3: 

-Algorithm 1: clarify the presentation. When you loop through "honest" and "Byzantine" workers, it seems as if the analyst/curator who is implementing the algorithm knows which workers are honest and not, which is clearly not the case

-Contextualize Theorem 1. the privacy properties of Gaussian mechanism and subsampling are well-known, so this theorem is not at all novel; this should be stated. Also the log term in the denominator can be tightened; can take $s^2 \approx C^2 log(1/\delta)/\epsilon^2 m^2$ 

-**What's the significance of VN condition?** How does it relate to BR?

-"when $\epsilon$ and $\delta$ are non-zero...": strange sentence because $s$ increases as $\epsilon$ and $\delta$ decrease. 

-Theorem 2: why doesn't $\kappa$ appear? Units appear to be wrong. Should provide comparison to Aliastarh, Allen-Zhu, Li (2018) and the references therein. Also should compare to DP optimization rates 

-Corollary 1: misleading because $\epsilon$ is not the actual privacy budget of full T-round algorithm, so first term should also scale with T. This remark applies to experiments too. 
summary_of_the_review: The paper makes some good progress towards an understanding of DP and BR in SGD via Proposition 1 and 2. However, the convergence results are not very clean and not properly contextualized. The writing is rather poor and the $\epsilon$ issue is a big one. I cannot recommend acceptance in the current form.
review_title: null

Meta-review: The paper considers the natural class of algorithms, namely Aggregators with Gaussian noise for distributed SGD with differential privacy (DP) and Byzantine resilience (BR). Previous results shows VN->BR-> convergence of SGD. The authors first show that aggregators with Gaussian noise algorithms satisfy DP but violates VN necessarily, so approximate VN is proposed. Theorem 2 shows approximate VN->convergence. Proposition 2 shows the above algorithms satisfies approximate VN with certain parameters. With the combined bound Corollary 1, the authors observe (and then verify by experiments) that larger batch size is beneficial and in particular more beneficial than when DP or BR is enforced alone. In the formulation, an important baseline of robust mean aggregation [Diakonikolas,Kamath,Kane,Li,Moitra,,Stewart'2016] and even more relevant baseline of robust and DP mean aggregation[Liu,kong,Kakade,Oh,'21] are somehow missing. One would assume that directly applying these well-known techniques might give the desired DP and robust SGD. The field at the intersection of differential privacy and robustness has evolved quite a bit recently and tremendous technical innovations are happening. Given the relveance of the proposed problem to this line of work, one should make the connections precise and explain the differences.
Decision: Reject