Combining Differential Privacy and Byzantine Resilience in Distributed SGD
Authors: Rachid Guerraoui
Nirupam Gupta
Rafael Pinot
Sébastien Rouault
John Stephan
Venue: ICLR 2022 Submitted (2022)
Keywords: Distributed SGD
Byzantine resilience

Abstract: Privacy and Byzantine resilience (BR) are two crucial requirements of modern-day distributed machine learning. The two concepts have been extensively studied individually but the question of how to combine them effectively remains unanswered. This paper contributes to addressing this question by studying the extent to which the distributed SGD algorithm, in the standard parameter-server architecture, can learn an accurate model despite (a) a fraction of the workers being malicious (Byzantine), and (b) the other fraction, whilst being honest, providing noisy information to the server to ensure differential privacy (DP). We first observe that the integration of standard practices in DP and BR is not straightforward. In fact, we show that many existing results on the convergence of distributed SGD under Byzantine faults, especially those relying on $(\alpha,f)$-Byzantine resilience, are rendered invalid when honest workers enforce DP. To circumvent this shortcoming, we revisit the theory of $(\alpha,f)$-BR to obtain an approximate convergence guarantee. Our analysis provides key insights on how to improve this guarantee through hyperparameter optimization. Essentially, our theoretical and empirical results show that (1) an imprudent combination of standard approaches to DP and BR might be fruitless, but (2) by carefully re-tuning the learning algorithm, we can obtain reasonable learning accuracy while simultaneously guaranteeing DP and BR. 

Under review as a conference paper at ICLR 2022
COMBINING DIFFERENTIAL PRIVACY AND BYZANTINE RESILIENCE IN DISTRIBUTED SGD
Anonymous authors Paper under double-blind review
ABSTRACT
Privacy and Byzantine resilience (BR) are two crucial requirements of modern-day distributed machine learning. The two concepts have been extensively studied individually but the question of how to combine them effectively remains unan- swered. This paper contributes to addressing this question by studying the extent to which the distributed SGD algorithm, in the standard parameter-server archi- tecture, can learn an accurate model despite (a) fraction of the workers being malicious (Byzantine), and (b) the other fraction, whilst being honest, providing noisy information to the server to ensure differential privacy (DP). We first observe that the integration of standard practices in DP and BR is not straightforward. In fact, we show that many existing results on the convergence of distributed SGD under Byzantine faults, especially those relying rendered invalid when honest workers enforce DP. To circumvent this shortcoming, we revisit the theory of (a, f)R to obtain an approximate convergence guarantee. Our analysis provides key insights on how to improve this guarantee through hy- perparameter optimization. Essentially, our theoretical and empirical results show that (1) an imprudent combination of standard approaches to DP and BR might be fruitless, but (2) by carefully re-tuning the learning algorithm, we can obtain reasonable learning accuracy while simultancously guaranteeing DP and BR.
(a., f)-Bznantine resilience, are
INTRODUCTION
Distributed machine learning (MI.) has received significant attention in recent years due to the growing complexity of ML models and the increasing computational resources required to train them (Dean et al. 2012 Srivastava et al. 2015). One of the most popular distributed ML settings is the parameter server architecture, wherein multiple machines (called workers) jointly learn single large model on their collective dataset with the help of a trusted server running the stochastic gradiens descent (SGD) algorithm (Bottou) 2010). In this scheme, the server maintains estimate of the model parameters, which is iteratively updated using stochastic gradients computed by the workers.
Compared to its centralized counterpart, distributed SGD is more susceptible to security threats. One of them is related to the violation data privacy by an honest-but-curiee buttiioottuiuss server (Zhu et al. (211)). Another one the malfunctioning due (what is called) Byzantine behavior of workers (Lamport et al. 1982: Blanchard et al., 2017). In the past, significant progress has been made in addressing these issues separately. In the former case, (e, d)-differenttal privacy (DP) has become dominant standard for preserving privacy in ML, especially when considering neural networks (Dwork et al. 2014 Abadi al. 2016). In the latter case, f Byzznninne resilience has emerged as the principal notion for demonstrating the Byzantine resilience (BR) of distributed SGD (B (Blanchard et al.) 2017 El Mhamdi et al. 2018). Since DP and BR are two crucial pillars of distributed machine learning, practitioners will inevitably have to build systems satisfying both these requirements. It is thus natural to ask the following question: Can we simultaneously ensure DP and BR in distributed ML?
In this paper, we take a first step towards positive answer to this question by studying the resilience of the renowned DP-SGD algorithm (Abadi et al. 2016) against Byzantine workers. More precisely. we consider distributed SGD where, in each learning step, the honest workers inject Gaussian noise to their gradients to ensure (c, 6DDD,, while the server updates the parameters by applying an (a, BB aggregation rule on the received gradients (to protect against. Byzantine workers). Upon analyzing

---

Under review as a conference paper at ICLR 2022
the convergence of this algorithm, show that DP and BR can indeed be combined, however, doing so is non- non-trivial. Our key contributions are summarized below.
1. Inapplicability of existing results from the BR literature. We start by highlighting inherent incompatibility between the supporting theory (a, f)R and the Gaussian mechanism used in DP-SGD. Specifically, show (in Section 3.2 that the variance-to-Pe guarantee (a, f)BR, cannot be satisfied when honest workers enforce (c, 8)-DP via Gaussian noise injection. Hence, existing results on the resilience of distributed SGD Byzantine workers not applicable when considering DP-SGD. More generally, this highlights limitations of many existing Byzantine resilient techniques in settings where the stochasticity of the gradients is non-trivial.
(VN) condition, critical to
2. Adapting the theory of BR to account for DP. To overcome the aforementioned shortcoming, we introduce relaxation of the VN condition (in Section (.3) namely the n-approximated VN condition. By doing we (1) generalize existing results from the BR literature and (2) demonstrate approximate convergence of DP-SGD under Byzantine faults. Our convergence result can be roughly as follows.
Theorem (Informal). Let Q be the loss function of the learning model, and O, be the parameter vector obtained after I steps of our algorithm. If the n-approximated VN condition holds true, then
min E [[Q(0))1 S max {1p TE(T]
log VT
where [7] (1...., 7), and ||-|| denotes the Euclidean norm.
As the aforementioned result suggests, a smaller 1) ensures better convergence. To quantify this convergence guarantee, present (in Section 3.4) necessary and sufficient conditions for the ry- approximated VN condition to hold. Specifically, we show that the condition holds only if 11² E Ω (ddm(11/8)/mm) where d, 6, and m denote the model size, batch size, and dataset size respectively. This showcases an important interplay between DP and BR, e.g., larger and ó leads to stronger resilience to Byzantine workers at the expense of weaker privacy.
3. From theoretical insights to practical convergence.
Importantly, our result (in Section 3.4 pro-
vides key insights on how to better integrate standard approaches to DP and BR using hy- perparameter optimization (HPO), e.g., by in- creasing the batch size or choosing an ap- propriate aggregation rule. The improvement illustrated by a snippet of our experimental results in Figure D This finding is particularly interesting as these parameters have very little impact in most settings when considering DP or BR separately. We validate our theoretical insights in Section 4 through exhaustive set of experiments on MNIST and Fashion- MNIST using neural networks.
0.8
Max cross-accuaacy
0.7
0.6
MDA
Krum
0.5
Median
Bulyan
0.4
25
150
300
500
750
1000
1250
1500
Batch size
Figure 1: Impact of the batch size and aggregation rule on the cross-accuracy of DP-SGD against the little (Baruch al. 2019) attack Fashion-MNIST.
CLOSELY RELATED PRIOR WORKS
There has been long line of research on the interplay between DP and other notions of robustness in ML (Dwork& & Lei 2009 Ma et al. 2019] Song et al. 2019b a Sun et al.) [0199] Lécuyer et al.) 2019 Pinot et al.) 2019) However, previous approaches do not apply to our setting for two main reasons; (1) they do not address the privacy of the dataset against an honest-bur buteett-bt-curoous server, and (2) their underlying notion of robustness are either weaker than or orthogonal to BR. Furthermore, recent works on the combination of privacy and BR in distributed learning either study weaker privacy model than DP or provide only elementary analyses (Chen et al.) 2018 He et al., [0200] So et al. 2020; Guerraoui et al.) 202I). We refer the interested reader to Appendix A for in depth discussion of prior works. In short, we believe the present paper to be the first to provide an in-depth analysis with practical relevance the integration of DP and BR in distributed learning.
2

---

Under review as a conference paper at ICLR 2022
2 PROBLEM SETTING AND BACKGROUND
Let X' be the space of data points. We consider the parameter server architecture with n workers {W....., 3,, owning common dataset D E X of m points. The workers seek to collaboratively compute a parameter vector E IR' that minimizes the empirical loss function Q defined as follows:
- Σ q0, x) v0 E 1R m
Q(0)
(I)
ZED
where q is a point wise loss function. We assume that function Q is differentiable and admits non-trivial local minimum. other words, VQ admits a critical point, but it is not null everywhere.
We also make the following standard assumptions.
Assumption (Bounded norm). There exists a finite real C < oo such that all 0 E Rd and x E D,
[Vq(0, x))l S C.
Assumption 2 (Bounded variance). There exists real value v < co such that for all 0 E Rd,
Σ -VV s u² ZED
Assumption 3 (Smoothness). There exists real value L such that for all 8, 0' R
(Q())) s L LI10- 0'|l
Assumptions 2 and are classical to most optimization problems in machine learning (Bottou et al.) 2018). Assumption I is merely used to avoid unnecessary technicalities, especially when studying difterential privacy. In practice, can be easily enforced by gradient clipping (Abadi et al,, 2016).
In an ideal setting, when all the workers are honest (i.e., non-Byzantine) and data privacy is not an issue, a standard approach to solving the above learning problem is the distributed implementation of the stochastic gradient descent (SGD) method. In this algorithm, the server maintains an estimate of the parameter vector which is updated iteratively by using the average of the gradient estimates sent by the workers. However, this algorithm is vulnerable to both privacy and security threats.
Threat model. We consider the server to be honest-but-currin but-curious, and that some of the workers are Byzantine. An coneestbuutcurriou server follows the prescribed algorithm correctly, but may infer sensitive information about workers' data using their gradients and any other additional information that can be gathered during the learning as demonstrated by Zhu al. (2019). On the other hand, Byzantine workers need not follow the prescribed algorithm correctly and can send arbitrary gradients. For instance, they may either crash or even send adversarial gradients to prevent convergence of the algorithm (Blanchard et al., 2017).
2.1 DISTRIBUTED SGD WITH DIFFERENTIALLY PRIVACY
Over the last decade, differential privacy (DP) has become a gold standard privacy-preserving data analysis (Dwork et al., 2014). Intuitively, a randomized algorithm is said to preserve DP if its executions on two adjacent datasets are indistinguishable. More formally, two datasets and D' are said to be adjacent if they differ by at most one sample. Then, (e, 8DD is defined as follows.
Definition 1 ((e, ()-))) Let
0, E [0, 1] and O an arbitrary output space. A randomized algorithmm M xm - O is (c, 8) -differrettillly private if for any two adjacent datasets D, D', and any possible set of outputs C O.
P(M((D) E E s e (M('' E c +
By far, the most widely used approach to ensure DP in machine learning is to use the differentially private version of SGD, called DP-SGD (Song et al. 2013 Bassily et al. 2014 Abadi et al.) (016). The distributed implementation of this scheme against honest-but-curious server consists, at every step, in making the honest workers add Gaussian noise with variance s² to their stochastic gradients before sending them to the server. When is chosen appropriately (e.g., see Theorem I each learning step satisfies (c, 6DD at the worker level. Finally, the privacy guarantee of the overall learning procedure is obtained by using the composition properry of DP (Kairouz et al. 2015 Abadi ct al. 2016, Wang et al. 2019). However, we are mainly interested in studying the impact of per-step and per-worker privacy budget (c, d) on the resilience of the algorithm to Byzantine workers.
3

---

Under review as a conference paper at ICLR 2022
2.2 BYZANTINE RESILIENCE OF DISTRIBUTED SGD
In the presence of Byzantine workers, the server can no longer rely on the average of workers' gradients to update the model parameters. Instead, it
gradient aggregation rule (GAR) F RRdxn + I2 that is resilient to incorrect gradients that may be sent by at most f Byzantine workers. A standard notion for defining this resilience is (a, By-zaanie resilience stated below. which was originally proposed by Blanchard et al. (2017).
Definition 2 ((a,) f resilience). Let 0 S x/2, and 0
Consider random are ii.d. from common distribution G. Let
vectors g......, g( among which at least G ~ G be a random vector characterizing this distribution. A GAR is said to be (or, f'-Byzantinee resilient for G if its outpu R = F(g g(")) satisfies the following two properties:
I. E R E (G]) 2 (1 sin a) || [G]] > O, and
2. for any r E (2. 3, 4}. E [[[2e]1"] is upper bounded by a linear combination of E ][ ..... E [ where Eisist
This condition has been shown critical to ensure convergence of the distributed SGD algorithm in the presence of up Byzantine workers (Blanchard et al. 2017 El Mhamdi et al. 2018). Thus, it serves as an excellent starting point for studying the Byzantine resilience of distributed DP-SGD, Consequently, we consider the algorithm where the server implements Byzantine robust GAR while the honest workers follow instructions prescribed in DP-SGD.
3 COMBINING DIFFERENTIAL PRIVACY AND BYZANTINE RESILIENCE
Algorithm [ described below, combines the standard techniques to DP and BR in distributed SGD. Given a GAR F and noise injection parameter 8, Algorithm| [ computes T steps of distributed DP-SGD with F as an aggregation rule at the server guarantee BR.
Algorithm 1: Distributed DP-SGD with Byzantine resilience
The server chooses arbitrary initial parameter vector 0, R learning rates ........ mr a deterministic GAR F. Honest workers have a fixed batch size and noise injection parameter s. for L 1...., T.....Tou do
Sctup:
The server broadcasts 02 to all workers.
foreach honest worker w, do
1. w; builds B, by sampling points random without replacement from D) and computes noisy gradient estimate with noise injection parameter i.c., it computes
11
Σ
Vg (0t,
(00)
v vt N'O, aa)
(2)
B
2. wy sends the resulting noisy gradient to the server.
end
foreach Byzantine worker w; de
w. sends to the server a (possibly arbitrary) vector (4) its "gradient". end
server computes the aggregate R& received gradients using F. iee. it computes
R₂ F
(3)
The server updates the parameter vector using the learning rate y follows
0 0, Re-
(4)
end
Note that when s = 0, i.e., when no noise is injected, Algorithm Tenithhhmeeeuceee reduces to a classical Byzantine resilient distributed SGD algorithm presented in prior works such as Blanchard et al. (2017) and El Mhamdi et al. (2018). Furthermore, when f = and F the average function, it reduces to distributed implementation of the well-known DP-SGD scheme, e.g., from Abadi et al. (006))
4

---

Under review as a conference paper at ICLR 2022
3.1 DIFFERENTIAL PRIVACY GUARANTEE
Intuitively, Algorithm T should inherit the privacy guarantees of DP-SGD. Indeed, the privacy preserving scheme applied at the worker level the same and will not by altered by the GAR thanks to the poot-prcessingg property of DP (Dwork et al. 2014). Then, owing to previous works, can easily show that Algorithm 1 satisfies (c, 6)-DP at each step and for each honest worker when = 20/be/ 2 In (1.25/8). Furthermore, as shown in Theorem I we can obtain a much tighter analysis using advanced analytical tools such as privacy amplification via sampling (Balle et al. 2018).
Theorem 1. Suppose that Assumption
holds true.
Let b E [m] and (e, 6) E (0, 1) Consider Then, each honest worker satisfies (c, 6)-DP at mé
Algorithm with bln((e--1) +1)
2C
2 In
1.256
every step 8 [T] of the procedure.
Henceforth, whenever we refer Algorithm I with per-step and per-worker privacy budget (e, 8), will consider as defined in Theorem aboov..
3.2 INAPPLICABILIT OF EXISTING RESULTS FROM THE BR LITERATURE
As discussed in Section 2 prior works on BR can demonstrate the convergence of Algorithm ! the GAR F is (a., f) - BByzantinn resilient during the entire learning process. However, verifying the validity of (ae, J)R is nearly impossible as the condition depends upon the gradients of the Byzantine workers that can be arbitrary (Blanchard et al. 2017). The only verifiable condition known in the literature to guarantee (a, /)-BR is the variance-to-norm (VN) condition, which is defined as follows (E) Mhamdi et al. 2018).
Definition 3 (VN Condition). For a parameter vector 0 E Rd let G(O) denote the random vector characterizing the gradients sent by the honest workers to the server at 0. GAR F satisfies the VN condition for any 0 such that G(O) has non-zero mean,
KF(n, f) (IC(O)-E(G(OO)
-
< [B]]1
where Kr(n, J) > 0 is the multiplicative constant of GAR F that depends n and |
This condition means that for GAR F to guarantee convergence for the procedure, the distribution of the gradient estimates at parameter 0 must be "well-hehaved". For instance, if the norm of the expected stochastic gradients converges to 0 then should the variance. Note that in the case of Algorithm from (2) we obtain that for any 0 E Rd,
1 b
G(f)
Σ ZEB
Vg (0, 2)
(5)
where B is set data points sampled randomly without replacement from D, and y ~ N la). Thus, the VN condition can longer be satisfied whenever >> 0, i.e., workers follow instructions prescribed in SGD We show this formally in Proposition bello..
Proposition 1. Let b E [m]. Consider Algorithm | with > 0. If Assumption 3 hholds true, then there exists no GAR that satisfies the VN condition.
Note that when c and are non-zero, we will have > O as explained in Section 3.1 Accordingly, Proposition D means that prior results the convergence of existing Byzantine resilient GARs, including the works by [lanchard et al. (2017) and El Mhamdi et al. ()018), are no longer valid when enforcing any non-zero level of DP. Although the VN condition only sufficient one, due the lack of necessary conditions in the literature, it is the most widely used tools for proving BR, e.g., see BBlanchard et al. (2017): ): EI Mhamdi al. (2018); Xie al. (018b); El-Mhamdi et al. (2200): Boussetta et al. (2021). Hence, Proposition [highlights an inherent limitation of the theory of BR, especially when simultaneously enforcing DP via noise injection.
Precise values of Ky (n, f) for most popular GARs he found in Appendix
5

---

Under review as a conference paper at ICLR 2022
3.3 ADAPTING THE THEORY OF BR TO ACCOUNT FOR DP
To circumvent the aforementioned limitation, we propose relaxation of the theory of (a, J)-BR by relaxing the original VN condition to the 1-aaproximated VN condition defined below.
Definition 4 (17 in-approximated VN condition). Let G(t) denote the random vector characterizing the gradients sent by the honest workers to the server at parameter vector B. For rj 2 0, a GAR F satisfies the n-approximated VN condition for all 0 E IR such that [| [G(())]] > 4bb
kr(n, f)2 [IG[0]) - [ [G(O)]] < [B|G()]]
where Kr f) > 0 is the multiplicative constant of GAR F that depends n and f.
Definition relaxes the initial VN condition by allowing a subset of (possible) parameter vectors 0 to violate the inequality in Definition 3 In particular, E [G([)] = VQ(Ø). when the gradients are sufficiently close to a local minimum, or [ S y). the inequality need not be satisfied. While the 7-approximated VN condition is a natural extension of Definition
enables us study cases where the distribution of the gradients at & is non-tri non-trivial, c.g., the variance of G(Ø) need not vanish when VQ(@) approaches O. Consequently, we can utilize this new criterion to analyze the convergence of Algorithm| condition, we show Theorem P the approximate convergence of Algorithm
| for different GARs and levels of privacy. Assuming 1-approximated VN
0, CAR F satisfying the 1-approximated VN condition, and " = -1/ for all t E [T). If Assumptions
Theorem 2. Let rj 2 and b [m)]. Consider Algorithm 2 with
7 and 3 hold true,
then there exists a E [0, 222 and μ E [0, oo) such that for any 2 1,
min E [[Q(0)11 S max 172 ( (1 - sin (x) EE(T]
Q(0,) -0"
1 VT
2
1+InT In
1
+
2(1 - ((1-sin ax)
VT
where Q" is the minimum value of Q, i.e. Q min Q(0), and a = v0 + ds² + C DERd
According to Theorem 2 Algorithm 1 can compute a parameter 0 for which [IQ( S 1) in
expectation with rate of OInT/vT) In other words, when the loss function Q is regularized (see, e.g.. Bottou et al. 2018). ). it finds an approximate local minimum with an error proportional to n Note that, when 7 0 (i.e., when DP is not enforced), the above result encapsulates the existing convergence results from the BR literature, e.g.. Blanchard et al. (2017) El Mhamdi et al. (2018).
Remark 1. For generality, we do not provide the exact values for parameters a and μ Theorem These two constants depend on the learning scheme that is applied, in particular the resilience properties of the GAR used. However, since these parameters are constant throughout the learning procedure, keeping them to be generic does not affect our conclusions on the asymptotic error.
3.4 STUDYING THE INTERPLAY BETWEEN DP AND BR
The value of 7 is intrinsically linked to the amount of noise that workers inject to the procedure. In a way, it represents the impact of per-worke worker DP on the resilience of Algorithm to Byzantine workers. To quantify this impact, we present in Proposition sufffiiiin and necessary conditions for a GAR F to satisfy the 7-approximated VN condition in the context of Algorithm [
Proposition 2. Let b [m). d) E (0, 1)². Consider Algorithm I with privacy budget (c, 8) and GAR F with multiplicative constant (n, f) > Then, the following assertions hold true.
1. Under Assumptions andd the n-approximated VN condition can hold true only if
1.256
1
n 4n S)
md
bii(e= - 1)
Additionally under Assumption 2 if
12 2 (n. (n, f)
80
1.250
mife 1) bb) + x²
1
+
1) 1)2
mo
then F satisfies the n-approximated VN condition.

---

Under review as a conference paper at ICLR 2022
The above result, in conjunction with Theorem presents convergence guarantee that can be obtained by distributed DP-SGD under Byzantine faults. In particular, we have the following corollary of Theorem and Proposition
Corollary 1. Lei b E [ml, (c,6) E (0, 1)a. Consider Algorithm 7 with privacy budget (e, 6) and GAR F, and = 1/vi all t E [T]. If Assumpttins and 3 are satisfied, then for any T 2 1,
min R [[VQ()))1]] max kr(n, f)² 8C NE(T]
1.256 m2
1 b + 02
In VT
mm(=
Corollary 1 quantiffes the impact of different parameters on the convergence of the algorithm. For instance, we observe that larger values of and 6, i.e., weaker DP guarantees, imply smaller worst- case convergence error and therefore, better guarantee of learning. But importantly, it also shows how the convergence guarantee of the algorithm depends upon other hyperparameters, namely the batch size b, the number of parameters d, and the multiplicative constant KF(n, f) of the GAR. Let us for example take the case of the batch size below.
Impact of batch size. We consider the specific GAR of Minimum -Dimmmter Averaging (MDA) for which KMDA
we obtain that //8/nns (EI Mhamdi et al. 2018). Then, from Corollary
min E [ [QQ()) max { CE(T]
852 (n f)²
1.25b mo
1
In T
mie- + 22
From above, we note that when parameters e and are in the interval (0, 1) and f 0, i.c. both DP and BR are enforced, then increasing the batch size b indeed reduces the asymptotic convergence error of the algorithm. However, this is not the case when we consider DP and BR separately. When all workers are honest, f = O, which implies 1) 0. The algorithm then asymptotically converges to a local minimum regardless of the batch size used. On the other hand, when the workers do not obfuscate their gradients (s 0), the 17aapprxxmmated VN condition holds true for Then, the asymptotic convergence error of the algorithm is again independent of the batch size. To conclude, the batch size plays crucial role in improving the learning accuracy when enforcing DP and BR simultaneously, but it should have little influence when considering them individually.
(v8f/n-5) v.
Remark 2. Although Corollary 7 provides some useful insights on improving the accuracy of the learning algorithm combining DP and BR, it need not be tight as it only provides upper bound relying on a sufficient condition; the 1-approximated VN condition. turns out that providing a non-trivial lower bound for distributed SGI) in the presence of Byzantine faults remains open problem, even without DP. In spite of this, we show the practical relevance of the insights obtained from Corollary 7 through an exhaustive set of experiments in the subsequent section.
NUMERICAL EXPERIMENTS
The goal of our experiments is to investigate whether theoretical insights actually applicable in practice and whether hyperparameter optimization (HPO) can improve the integration of DP and BR. Accordingly, we assess the impact of varying different hyperparameters the training losses and top-1 cross-accuracies of neural network under (c, O-DP and attacks from Byzantine workers over a maximum of 300 learning steps.
Reproducibility. All our experiments (training + graphs) are reproducible in one command. Please see code/ README. md in the supplementary material. Additional graphs are available in plots/.
4.1 EXPERIMENTAL SETUP
Datasets. We use MNIST (LeCun & Cortes, 2010) and Fashion-MNIST (Xiao et al. 2017). The datasets are pre-processed before training. MNIST receives an input image normalization with mean 0.1307 and standard deviation 0.3081. Fashion- MNNIS is expanded with horizontally flipped images. Due to space limitations, we only showcase here results on the Pashion-MNIS, dataset.
Architecture and fixed hyperparmaters. We consider a feed-forward neural network composed of two fully-connectoo linear layers of respectively 784 and 100 inputs (for a total of 79 510 parameters) and terminated by sofimax layer of 10 dimensions. ReL.U is used between the two
7

---

Under review as a conference paper at ICLR 2022
linear layers. We use the Cross Entropy loss, total number of workers 15. Polyak's momentum of 0.99 at the workers, a constant learning rate of 0.5, and a clipping parameter C = We also add an &g -e-rgularization factor of 10 Note that some of these constants reused from the literature on BR, especially from Baruch et al. (2019) Xie et al. (019); EI-Mhamdi et al. (2021).
vary the batch size b within (25, 50, 150, 300, 500, 750, 1000, 1250, 1500), the per-step and per- per-worker privacy parame- ter in {0.2, 0.1, 0.05) (6 is fixed to 10 00, the number of Byzantine workers f in {3, 6) well as the attack they implement (litle from Baruch et al. (2019) and empire from Xie et al. (2019)). We also vary the Byzantine resilient GAR F {MDA, Krum, Median, Bulyan). Note that due its large computational cost, we only use the Bulyan aggregation rule when f =
Varying hyperparameters for HPO. For both datasets,
Each of the 432 possible combinations of these hyperparameters run times using seeds from to (for reproducibility purposes), totalling in 2160 runs. Each run satisfies (c. 6D- at every step under attacks from Byzantine workers. To assess the impact of the privacy noise alone, we also run the experiments specified above with the averaging GAR and without Byzantine workers (denoted by "No attack"). These experiments account for another 27 combinations, totalling in 135 additional runs. Overall, we performed comprehensive set of 2295 runs for which we provide brief summary below. More details on the experimental setup and results can be found in Appendices D and
4.2
EXPERIMENTAL RESULTS
0.8
Max cross-accuracy
Max cross-accuracy
0.7
0.4
0.5
0.2
25
150
300
500
750
1000
1250
1500
25
150
300
500
750
1000
1250
1500
Batch size
Batch size
Max cross-accuracy
0.8
Max cross-accuracy
0.8
No attack
0.6
0.6
MDA
Krum
Median
Bulyan
0.4
0.4
750 Batch size
1500
25
300
750
1500
Batch size
Figure 2: Maximum top-1 cross accsracc reached on Fashion-MNIST when only varying the batch size 5 for diffferent threat scenarios and different GARs. The first and second rows show the little and empire attacks respectively. The first and second columns display f 6, = 0.05 and f= = 3, < = 0.2 respectively. All reported metrics include standard deviation obtained with the 5 consecutive As a reference, note that the maximal top-1 cross-accuracy achieved by the tested model in the vanilla setting (i.e., with neither DP nor Byzantine faults) around 84-85% for Fashion-MNIST.
6,
In Figure 2 we give a snapshot of our results by showcasing 4 characteristic outcomes encountered. Below, we present further characterization them. Besides validating our theoretical insights on the impact of the batch size and the GAR selection on the convergence of Algorithm | these plots also showcase the threat scenarios which hyperparameter optimization (HPO) has the most impact. Note that the little attack more damaging than empire in experiments; hence in our discussion below, we consider little to stronger threat than empire, ceteris paribus.
1. Strongest threat scenario (top left). We consider little with f = 6 and = 0.05, i.e., the strongest level of attack and privacy implemented. In this stringent scenario, the algorithm fails to deliver good learning accuracy under Byzantine attacks. Although increasing the batch size helps improve the convergence, the accuracy remains quite poor (well below 0.6, even when b 1500).
8

---

Under review as a conference paper at ICLR 2022
2. Relaxed threat scenario (bottom left). Here, keep f = 6 and 0.05, but trade the attack for a weaker one (empire). This scenario validates our intuition on the advantage of increasing the batch size, but it mostly highlights the impact of GAR selection. Different GARs differ significantly in their maximum cross accuracies, while MDA performs the best.
3. Mild threat scenario (top right): We now consider e 0.2 and f 3, i... a weaker privacy guarantee and a fewer number of Byzantine workers. However, we revert back to little attack. We see that, for all GARs, increasing the batch size significantly improves the maximum cross- accuracy. The choice of GAR also impacts the performance, with Bulyan being the best.
4. Weakest threat scenario (bottom right): We consider empire with f f= 3 and = 0.2. The threat is weak that all GARs perform almost the same. Although HPO still helps obtain better accuracy, it is not critical in this setting.
Main Takeaway. Our empirical results show that training feed-forward neural network under both DP and BR is possible but expensive in some settings. Indeed, in the non-trivial threat scenarios, to achieve the same maximum aross-accuracy as DP-SGD with b 50, we need per-worker batch size 2 1000, i.c., 20 times larger than the Byzantine-free free setting. Moreover. depending upon the setting, the selection of the GAR might be more influential than the batch size. Finally, note that in the Byzantine-free setting, the DP-SGD algorithm obtains reasonable cross-accuracies (close to 0.8) for most batch sizes considered. This validates our theoretical findings (discussed Section (3.4) that the batch size has more significant impact when combining DP and BR compared to when enforcing DP alone. Similar observations on the negligible impact of the batch size the privacy-free setting (but under Byzantine attacks) can be found in Appendix
CONCLUSION & OPEN PROBLEMS
In this paper, we have studied the integration of standard approaches DP and BR, namely the distributed implementation of the popular DP-SGD protocol in conjunction with (a, J)-BR GARs. Upon highlighting the limitations of the existing theory of BR when applied this algorithm, we have proposed generalization of this theory. By doing so, we have (1) quantified the impact of DP on BR, and (2) proposed an HPO scheme to effectively combine DP and BR. Our results have shown that DP and BR can be combined but at the expense of computational cost in some settings.
Our generalization of the theory of (a, BB is also of independent interest. Specifically, we have proposed relaxation of the VN condition 77apppoxettted VN condition. Although the VN condition is quite stringent and only sufficient, it is consistently relied upon to design and study different Byzantine resilient GARs (Blanchard al.] 2017 El Mhamdi al., 2018 EI-Mhamdi 2020 2021 1 Boussetta et al. 2021). Hence, our convergence result, obtained using the relaxed
eet al. 1/aapproximated VN condition, supersedes many existing results in the literature of BR.
Interestingly, we have observed through our experiments (see Appendix E.2 that even when the relaxed 7/aapproximated VN condition violated, the algorithm obtains reasonable learning accuracy. This observation opens two interesting problems expounded below.
1. A theoretical problem: The VN condition (either approximated or not) is not tight enough to fully characterize BR. That is, in some cases, GAR may be (a, f)RBR without satisfying the VN condition. Furthermore, the theory of BR focuses on "worst-case" attacks that, for now, might not be achievable in practice. Hence, the question the tightness of the VN condition for any specific attack, even without DP, remains open.
2. An empirical problem: The practice of BR focuses on state-of-ther thrt realizable attacks. These attacks are arguably sub-optimal explaining why we can obtain reasonable learning accuracy despite the violation of the VN condition. This also calls for designing better (or stronger) attacks.
Finally, while we have focused adapting the theory of BR to make it more compatible with the standard DP-SGD algorithm, an alternate future direction could be to investigate other DP mechanisms that may comply better with classical approaches to BR, while preserving DP guarantees.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, pp. 308-318, 2016.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 6280-6290, Red Hook, NY, USA, 2018.
Curran Associates Inc.
Moran Baruch, Gilad Baruch, and Yoav Goldberg. A little is enough: Cireumventing defenses for distributed learning. In Advances Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, 8-14 December 2019. Long Beach, CA. USA, 2019.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473, 2014.
doi: 10. 10.1000FFCS.2214.555
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolernnt gradient descent. In Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 119-129. Curran Asso- ciates, Inc., 2017. URL [ttpps://proceeaing intrrrcreddnnnsneeeiiisps neurips wwt.rriss.cccpaeee cttpppppee//////ELL...
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Yves Lechevallier and Gilbert Saporta (eds.), Proceedings of COMPSTAT pp. 177-186, Heidelberg, 2010. Physica-Verte HD. ISBN 77783-77908-204-33
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3111 211, 2018.
Amine Boussetta, El-Mahdi El-Mhamdi, Rachid Guerraoui, Alexandre Maurer, and Sébastien Rouault. Aksel: Fast byzantine sgd. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Schloss Dagstuhl-Leibnizz Leibnni-ZZeetumm für Informatik, 2021.
X. Chen, J. Ji, C. Luo, W. Liao, and P. Li. When machine learning meets blockchain: A decentralized, privacy-preservin and secure design. In 2018 IEEE International Conference on Big Data (Big 2018.
Data), pp.
Georgios Damaskinos, Celestine Mendler-Dünner, Rachid Guerraoui, Nikolaos Papandreou, and Thomas Parnell. Differentially private stochastic coordinate descent. Proceedings of the AAAI Conference on Artificial Intelligence, 3578):7176-7184, May 2021. URL Jtttps::: aaai
org/index
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' au- relio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc Le, and Andrew Ng. Large scale distributed deep networks. In F. Percira, C. J. C. Burges, L. Bottou, and K. Q. Wein- berger (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Asso- ciates, Inc., 2012. URL https: httpttt /ttp::::///ccceeedeeooo www.:ediiiiinnnnnnnnooeeeo 1aca970000001112222228888888 Pawpee661112263--pprr..... http://.....nnaaaaa..eeeeeee/eee cctppppp///1//////////p/ 2/file/
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the Forty-First Anmual ACM Symposium on Theory of Computing, STOC '09, pp. 371-380 New York, NY, USA, 2009, Association for Computing Machinery. ISBN 9781605585062. doi:
11555//36414.15566666 URL /tt.:ttss://oo..orr
1145/113641111 1536466
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 93-44:2111440) 2014.
10

---

Under review as a conference paper at ICLR 2022
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in Byzantium. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference
Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 3521-3530. PMIR, 10-15 Jul 2018. URL wwt.ttttpss.............p....stt httt:p::/pproceedd ings www.pres//wb//mee mhammd 18a.dii11aa... 18..hmml
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lê Nguyên Hoang, and Sébastien Rouault. Genuinely distributed byzantine machine learning. In Proceedings of the 39th Symposium on
Principles of Distributed Computing. PODC '20, pp. 355-364 New York, NY, USA, 2020. doi: 011145/3382234444056653
Association for Computing Machinery. ISBN 9781450375825.
URL
111.///33.11113322111 3405695
El-Mahdi El-Mhamdi, Rachid Guerraoui, and Sébastien Rouault. Distributed momentum for resiliett stochastic gradient descent. In 9th International Conference Learning Representations, ICLR 2021, Vienna, Austria. May 4-8, 2021. OpenReview.net, 2021. URL
https:://pennret
net m
Shripad Gade and Nitin H. Vaidya. gradients. In 2018 IEEE Conference on Decision and Control (CDC), pp. 184-191, 2018. doi: 10.11009CDC22011..661199
distributed learning via obfuscated stochastic
Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, Séhastien Rouault, and John Stephan. Differential privacy and byzantine resilience in sgd: Do they add up? In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC pp. 391 391-401, New York, NY. USA, doi: 10.1145/3465084,
2021. Association for Computing Machinery. ISBN 9781450385480. 3467919. URL http:::tt/ 11w.////...../4........... 44444///445084444799991 3467919
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Secure byzantine-robust machine learning, 2020.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1376-1385 Lille, France, 07-09 Jul 2015. PMLR. URL http: http::/prooceeddnggg wtt.ssss.....pp..s//e.. www.ss/v3333
kairouz15.html
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst, 43)):822401, July 1982. ISSN 0164-0925. doi: 10. 15/15577777733357766
URL mattps:://oi.. .rrg 10. 00111115337777 45/357172.3577772
Yann LeCun and Corinna Cortes.
MNIST handwritten digit database.
http://awwneeuue.oo///////////im 2010. URL /aann. lecun com wxeb http///bbbmmmi///////m
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 20/9 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pp. 656-672. IEEE, 2019. doi: 10. N0.11099/P.20190000
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially-priinn learners: Attacks and defenses. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 4732-4738. International Joint Conferences on Artificial Intelligence Organization, 2019. doi: 10.24963/ijcai.2019966 URL httphtttp////ooorooo org/
10. NV.22963/1jcca1 2019/2511166
M. Naseri, J. Hayes, and Emiliano De Cristofaro. Toward robustness and privacy in federated learning: Experimenting with local and central differential privacy. ArXiv, 0bs/2009.0356/) 2020.
Opacus. Opacus PyTorch library. Available from cammoopccs..t ail 2021.
Rafael Pinot, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif. A unified view on differential privacy and robustness to adversarial examples. arXiv preprint 1xxiv:/906..79990 2019.
11

---

Under review as a conference paper at ICLR 2022
R. Shokri and V. Shmatikov. Privacy-preserving deep learning. In 2015 53rd Anmual Allerton Conference on Communication, Control, and Compuring (Allerton), pp. 909-910, 2015. doi: 10.1 10.110/AAEERTON220........
Jinhyun So, Basak Guler, and A. Salman Avestimehr. Byzantine-resilient secure federated learning, 2020.
Liwei Song, Reza Shokri, and Prateek Mittal. Membership inference attacks against adversarially robust deep learning models. In 2019 IEEE Security and Privacy Workshops, SP Workshops 2019, San Francisco, CA, USA, May 19-23, 2019, pp. 50-56. IEEE, 2019a. doi: 10.1 109/SPW.2019. 00021.
Liwei Song, Reza Shokri, and Prateek Mittal, Privacy risks of securing machine learning models against adversarial examples. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS '19, pp. 241-257, New York, NY. USA, 2019b. Association for Computing Machinery. ISBN 978145036744 doi: 10.1 10.1145/3195555333422
Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. 2013. doi: 00.119//GobbuSSP22013666663
Rupesh K Srivastava, Klaus Greff, and Jürgen Schmidhuber. Training very deep networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Asso- ciates, Inc., 2015. URL httpps://rroeeeiing 211a7la12
http://nss..uurps...c.epppaaaaep /eeerr/ps.cccppppr/////////e Paper. ppff
Ziteng Sun, Peter Kairouz,, Ananda Theertha Suresh, and H. Brendan McMahan, Can you really backdoor federated learning? CoRR, abs/1911.07963, 2019. URL http://///ax wrg.vbbrrr//a/a
1911. 07963
Fengyi Tang, Wei Wu, Jian Liu, and Ming Xian. Privacy-preserving distributed deep learning via homomorphie re-encryption. Electronics, 8:411, 04 2019. doi: 10.3390/eletromicc8044411
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy yong Sohn, Kangwook Lee, and Dimitris S. Papailiopoulos. Attack of the tails: Yes, you really can back- door federated learning. In NeurlPS, 2020. URL https:
neurips. cc/
0apprr/220/hash/BBBEEB oeeer//0000.aaaaaaaeeeeeeeeeeeee 72te:/33e222211222-22222222
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled renyi differential privacy and analytical moments accountant. Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the livety-Seconel International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Muchine Learning Research, pp. 1226-1233 PMLR, 16-18 Apr 2019. URL http::ttp///pttt
ngs ml www.spprssssem
wang 2b.html
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion- a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd, 2018a.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Phocas: dimensional byzantine-
stochastic gradient descent, 2018b.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant SGD by inner product manipulation. In Proceedings of the Thirty-Fifit Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25. 2019, pp. 83, 2019.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantinerrobust distributed learning: Towards optimal statistical rates. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5650-560 5659. PMLR, 10-15 Jul 2018. URL http:/ttttpp/oeeeeeeee http::////cceeeiiggppee m mlr. wtr.press/v80.. 8a html
12

---

Under review as a conference paper at ICLR 2022
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Bus E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 14774-14784. Curran Associates, Inc., 2019. URLhttp: papers ni nips. w wwtpc/cppppp..1110//..
eakage f from wratinggadiientt.....
13

---

Under review as a conference paper at ICLR 2022
A RELATED WORK
Privacy. In the past, significant attention has been given to protecting data privacy for both central- ized (Song et al. 2013 Damaskinos et al.) [021] Abadi et al., 2016) and distributed SGD (Shokri & Shmatikov 2015 Naseri al. (2020). Although several techniques for data protection exist such as the encryption Tang et al. 2019) or obfuscation (Gade & Vaidya 2018) of gradients, the most standard approach consists in adding DP noise to the gradients computed by the workers (Abadi et al. 2016; Song et al. 2013 Shokri & Shmatikov [015 Naseri et al., 2020), which is what we consider. However, these works only consider a fault-free setting where all workers are assumed to be honest.
Byzantine resilience. In a separate line of research, several other works have designed Byzantine resilient schemes for distributed SGD in the parameter-serve server architecture (Blanchard et al., 201 7, El Mhamdi et al. [2018] Yin et al., 2018: Xie et al., 200 8a b) EI- El-Mhamdi et al., (0200 Boussetta et al., 2021). Nevertheless, in these papers, the training data is not protected, meaning that their methods do not consider the privacy threat associated with sharing unencrypted gradients with the server.
Combining privacy and BR. Although scarce, there has been some work on tackling the problem of combining privacy and BR. For instance, He et al. (2020) consider this problem for different framework that includes two honest-but-curious non-colludig servers, a strong assumption that does not always hold in practice. Furthermore, their additive secret sharing scheme is rendered ineffective in our setting where there is a single conest-but-curion server that obtains information from all the workers. In the context of privacy, the single-server setting generalizes the multi-server setting with colluding servers. Another related work, the BREA framework, proposes the use of verifiable secret sharing amongst workers (So et al. 2020). However, the presented privacy scheme scales more poorly than DP mechanisms. and is infeasible in most distributed ML settings with no inter-worker communication. Chen al. (2018) propose the LearningChain framework that is claimed combine DP and BR. However, LearningChain is an experimental method, and Chen et al. do not provide any formal guarantees either on the resilience or on the convergence of the proposed algorithm.
Recently, Guerraoui et al. (202T) studied the problem of satisfying both DP and BR in single- server distributed SGD framework. While they demonstrate the computational hardness of this problem in practice, we go beyond by showing an inherent incompatibility between the supporting theory of ()-BR and the Gaussian mechanism from DP. Moreover, our approximate convergence result generalizes the prior works on BR. This generalization is critical to quantifying the interplay between DP and BR. Importantly, while Guerraoui et al. (202T) only give elementary analysis explaining the difficulty of the problem, show that a careful analysis can help combine DP and BR.
DeceetlyyGGerraoui
Studying the interplay between DP and other notions of robustness. There has been a long line of work studying the interplay and mutual benefits of DP and robustness to data corruption in the centralized learning setting (Dwork& & Lei, 2009: Ma et al. 2019). However, these works do not server, and they not applicable to our setting. Furthermore, data corruption is actually a weaker threat than BR as the adversary cannot select its gradients online to disrupt the learning process.
consider the problem of distributed scenario with an conest-but-curionn
Recently, there have been some work on the interplay between DP and robustness to evasion attacks (a.k.a. adversarial examples). Interestingly, some findings in that line of research are similar ours. DP and robustness to adversarial examples have been demonstrated to be very close from a high-level theoretical point of view even if their semantics are very different (Lécuyer et al., 2019 Pinot et al., 2019). However, some recent works have pointed out that these two notions might be conflicting in some settings (Song et al. 2019a|9 b). is however worth noting that BR and robustness to adversarial examples are two orthogonal concepts. In particular, the robustness of model (at testing time) to evasion attacks does not provide any guarantee on the robustness (at training time) to Byzantine behaviors. Similarly, as BR focuses on the training (optimization) procedure, models using& a Byzantine resilient aggregation rule but without obtaining robustness to evasion attacks. The connection between these two notions of robustness remains an open problem.
always train
Finally, Sun et al. (2019) suggested that in the context of federated learning, differential privacy could help defend against backdoor attacks. However, this hypothesis got challenged by Wang et al. (2020).
14

---

Under review as a conference paper at ICLR 2022
B STANDARD GARS WITH ASSOCIATED MULTIPLICATIVE CONSTANTS
In this section, we present the different GARs used in our experiments, along with their associated VN conditions (Definition 3) and multiplicative constants ky f).
B.1 KRUM
Krum is an aggregation rule introduced under the assumption that n 2 2f + 3. consists in selecting the gradient which has the smallest mean squared distance, where the mean is computed over its - 2 closest gradients (Blanchard al. 2017). Formally, let (8) ,..... g(..) be the gradients
received by the parameter server. For any E {1,2, ..., n and o i, we denote by + j the fact that (كو is amongst the n f closest vectors (in distance) to g(+و) within the submitted gradients.
Krum assigns to each (+)) a score
=
Σ 3:1-3
|000 |000000
-1000003
(6)
and outputs the gradient with the lowest score. Blanchard et al. 2017) prove that Krum is f)- Byzantine resilient, assuming that the following VN condition is satisfied:
2 n - f(n 2) 2) f2 1 [IG(()= - [[CCO)))(CC))) < [B[G())]
(7)
n 2 2
Therefore, the multiplicative constant for Krum is
KKrum (n, f) f)=f))//) /2 ( f+ f f f2 11
(8)
n - 2f
B.2 MOIMMUM-DAMMEERR AVERAGING (MDA)
MDA is an aggregation rule introduced under the assumption that n > 2f + 1. It outputs the average of the most clumped gradients among the received ones (El Mhamdi et al. 2018 El-Mhamdi al. 2020). Formally, let Q = (g()), g ..... (")} be the set of gradients received by the parameter server and let T = (VIV C Q | n f} be the set all subsets Q of cardinality n - f. MDA chooses the set
g000) -066)
S arg min
VET
(gt9 eg
and outputs the average of the vectors in S. El Mhamdi et al. (011)) prove that MDA is (a, Byzantine resilient, assuming that the following VN condition holds true:
2
V&f
[IG - [G())]]] < [E
n-
Therefore, the multiplicative constant for MDA is
V8f (MDA(n, f) n
(10)
B.3 MEDIAN
Yin et al. (2018) introduce the Median aggregation rule under the assumption that n > + 1. When using Median, the parameter server outputs the coordinate-wise median of the submitted gradients. We recall that every submitted gradient g()) Rdd, where d is the number of parameters of the model. Formally, Median is defined as follows
median (1)) (1).g(2111
(m)
median (g 22, g (2) [2] ..., (2)
Median (()), g(2) (((),...gg())
(II)
median
(g (d). (2) (d. ((.
15

---

Under review as a conference paper at ICLR 2022
where []] is the j'th coordinate of g and median is the real-valued median. In other words,
median (I), 32, 22,,.., = arg min ZER
x|
where 21, 22 22,,..,, En E IR. The VN condition for Median is the following:
(n - f) [IG(0) < | [[
Therefore, the multiplicative constant for Median is
MMedian (n, f) = V - f.
(12)
B.4 BULYAN
Bulyan an aggregation rule defined under the assumption that n 2 4f + 3. is actually not an aggregation rule in the conventional sense, but rather iterative method that repetitively existing GAR (El Mhamdi et al. 2018). In this paper, we use Bulyan on top of Krum defined above. Formally, Bulyan uses Krum n 2 times iteratively, each time discarding the highest-scoring gradient. After that, the parameter server is left with a set P of the n 2 2 "lowest-scoring gradients selected by Krum, as mentioned in Appendix B.I] Bulyan then outputs the average of the 4f 2 closest gradients to the coordinate-wiss median of the - 2 2 (selected) gradients E P.
The VN condition for Bulyan is the same as that of Krum (i.e., equation tive constant for Bulyan is
Therefore, the multiplica-
12 n I f(n 2) + f2 1)
Bulgan (n,
(13)
2f
16

---

Under review as a conference paper at ICLR 2022
C PROOFS OMITTED FROM THE MAIN PAPER
C.I TECHNICAL BACKGROUND ON PRIVACY
Before demonstrating Theorem [ we recall some classical tools from the DP literature. Below, we recall the definition of sensitivity, the privacy guarantee of the Gaussian noise injection, and the notion notion of privacy amplification by sub-sampling.
Definition (Sensitivity). Let f X RR.. The sensitivity of f. denoted by A(f), the maximum norm of the difference between the outcomes of f when applied any two adjacent datasets, i.e.
A(f)= == sup D-D'
((D))=(D')ll.
where D' denote the adjacency between the databases D and D' from X
demonstrate that the Gaussian noise injection scheme (a.k.a. the Gaussian mechanism) satisfies (c, 6)-DP for well chosen noise injection parameter 8.
Using this notion of sensitivity,
Lemma Dwork et al. (2014). Let f x + RR, (e, E 1)2, and s > The scheme that takes D X as input, and outputs
M(D) = I(D) + where ~ (0,
satisfies (e,8)-DP A()
21 (1.25/8).
Finally, let us introduce the concept privacy amplification by sub-sampling. Here, we study sub-sampling without replacement defined follows.
Definition 6. (Sub-sampling) Given dataset D E xm and constant b E [m], the procedure SUB-SAMPLEFm-B Xm X selects points at random and without replacement from D.
This sub- sub-sampling procedure has been widely studied in the privacy preserving literature and is known to provide privacy amplification. In particular, Balle et al. 2018) demonstrated that it satisfies the following privacy amplification lemma.
Lemma 2 (Balle et al. (2018). Let e 0, E (0,1), [m], and O be an arbitrary output space. Let M X - O be an Oe, algorithm and M' Xmm + O defined as M' == M o SUB-SAMPLE,
Then M' is (e', D'D-,, with = In (1 h [e 1)) and 8' h8
C.2 PROOF OF THEOREM 1
Theorem 1. Suppose that Assumption
holds true.
Let b E [m] and (c, E 1)?. Consider mn Then, each honest worker satisfies (c, 6DD at
Algorithum with bin((e--1) 13
2C
2 In
1.256
every step & [T] of the procedure.
Proof. Let [T] be arbitrary step of Algorithm and 0, the parameter step 4. Let consider an arbitrary honest worker wy, Note that the batch on which w/ computes its gradient estimate constituted of b points randomly sampled without replacement from D. Hence we can write B, = SUB-SAMPLEM (D). We now denote by f X + Rd the function that evaluates the mean gradient at 6, using B,. Specifically.
1 Σ Vq z), for any batch B, x zEB,
f
(14)
We denote by M X dd the noise injection scheme. i.c., for any B, xbb
M M = (B,) Ms yt N La))
(15)
Following the above notation, at step f, the honest worker w; computes the noisy gradient estimate
gi .M SUUB-AMPLEE.-Bl/ Hence, suffices to show that M SUB-SAMBE SA-PL-AMLE.---- satisfies
(e, DDP to conclude the proof.
17

---

Under review as a conference paper at ICLR 2022
Since two adjacent datasets only differ on row, using Assumption 1
have that A(f)
<
2C
In particular, this implies that 2 A(A)
1) 2l
1,25)
Then, according to Lemma
M
mi
is (c', 6.6) 6DDP with c' d In ((ee 1) m +1). Finally, it suffices to use Lemma M SUB-SAMPLE is (e, -iffferrennl private.
to conclude that
C.3 PROOF OF PROPOSITION
Proposition 1. Let be E [m)] Consider Algorithm with 0. Assumption holds true, then there exists no GAR that satisfies the VN condition.
Proof. Let consider arbitrary GAR F with multiplicative constant (n f) > 0. We denote
the set of critical points of Q by è := {0 E R VQ(@) = 0}. While considering Algorithm the random variable that characterizes the gradients sent by the honest workers given parameter vector is defined as follows, for all E Rdd
G( = Σ (0, SEB
where set of points randomly sampled without replacement from (denoted D R) and y ~ (NO, s²aa). To show that the VN condition (in Definition 3) does not hold true, we show that there exists E gd such that
(n(n, f) E -[G()) 2 [[(())
For doing so, we first observe that for any 0 E Rd. G(0) is an unbiased estimator of VQ(0), i.e., [G(()] (Q()). Furthermore, note that the injected noise y is independent from the stochasticity
( Σ Vq (0, x)) Hence, for all 0 E Rd.
of gradient estimate
ZEB
(E
E R~ B~DiEn Divn
Σ Vq x) (0) + +Ey-V(0,e1a) [|B|I]]
[|wmP]] TT((s (a(s ds².
2 E Ey-
(16)
As Q admits non-trivial minima, we know that O- * Rd. Accordingly, there exists 0* O* and 8' E ( Without loss of generality, can always take 0- and 6' such that
110' 0 S KF(n, f)vds
where L is the constant defined in Assumption 3 Thus, using Assumption we get
[[Q((')) - ((') - VQ(0")I
L 8*1l s kx <n f)
(17)
Furthermore, thanks (16 we know that
K (n, 2 - 2 kr(n, d)dds
(18)
Finally, using 17) and 18 we obtain that
kF f) E [|G(0') - -E 2 xF(n, f)²d²² [VQ(1)1 |E
The above concludes the proof.
18

---

Under review as a conference paper at ICLR 2022
C.4 PROOF OF THEOREM! 2
Before we prove the theorem, we note the following implication of Assumption Lemma 3. Under Assumption for a given parameter 0,
E
2) (0 VQ())
JEB
where recall that B a batch of b data points chosen randomly from dataset D
Proof. Consider an arbitrary B. Then,
Σ -
-)) VQ(()
Vg (0, (V)
b
FEB
ZEB
By triangle inequality, and the fact that (-)2 is convex function, obtain that
Σ
x) x))
VV (0, x) -VQ(0))
#EB
BEB
V
VQ x) -
SEB
Recall that B is set of points randomly sampled without replacement from D, which we denote by B ~ DWR Thus, given 0,
E
Σ (V. x) VQ())) #EB
E EB
Σ x) 2)-
Therefore, from above we obtain that
E
Σ
(0,
VQ(0))
S
R
B-DDiR
Σ
(0, v
(19)
b
b
.EB
LEEB
Note that
(m-1)
BBnDiyn
Σ
V (0, VQ(0)12
Vg x) VQ(0))1
LEEB
b Σ (0, -Q
m RED
Finally, substituting above from Assumption
we obtain that
E Ba
Σ (V, 2
bv².
Substitution from above in 19 concludes the proof.
We now present the proof of Theorem 2 which is re-stated below for convenience.
Theorem 2. Let rj 2 and b E [m]. Consider Algorithm 7 with
0, a GAR F satisfying the and hold true,
"rapproximated VN condition, and 7tt = 1/vl for all t E [T). If Assumptions then there exists E [0, 2/2) and E [0, oo) such that for any T 2 1,
< max {1P: Q(0,)-1 - -Q"
2 L
1 In
min E (E(T]
|QQ())1
(1 sin ox)
2(1 - a)
where Q" is the minimum value of Q, i.e., Q min Q(0), and BER
V02
ds² +
19

---

Under review as a conference paper at ICLR 2022
Proof. Recall from (4) in Algorithm that, for all
0+11 = 02 7/ Rs
where R = F' (
..... .....)))) ) Thus, under Assumption 3
we obtain that for all t,
Q(0++1) s -x (vQ(0) R₂) + I2
|Rlll
(20)
2
We denote by E, [.] the conditional expectation given the history P. = {0,,...,
0,3 Ru....
R
By taking the conditional expectation E, both sides in 20
we obtain that
S E. [) Q(0,) Y (VQ().) E. (R,))
+
2e L
Es
[|
(21)
2
Recall from
5 that, for all 6,
G(O,) = 1 Σ (0 x) REB,
where B, of points randomly sampled without replacement from D and y/2 WO0 sa By Definition of the 7-approximated VN condition, when |[,, [G(O))]] > 1,
(n, f), [|G(e) - E, [G())]II] < ||E [G(e,)]|I*
(22)
Now, consider an arbitrary integer T 1. We can partition set [T] {l..... T} into two sets ST and ST such that
=- [ E [GOO) S n and ST [T] \ ST. First, we consider the case when Sy * 0. In this case, 36" [T] such that ||E,- [G(0,-)]II S 1/. As E [G()] = VQ(@) for any given 0, this implies that (Q )l S 17. Thus,
(23)
[QQ(0)11 s. n TE
min
Thus, the theorem is trivially true in this case. Next, consider the when Sy 0, i.c., ST = (7). Thus, in this case,
E, G((,)]] 7. Vt E [T].
This implies that 22 holds true for all E [T]. Thus, from prior results in Blanchard et al. (2117);
El Mhamdi et al.
2018 8) obtain that GAR
(a, f)-Byzantine resilient with respect to G(O,)
for each E [7)
Thereforee by Definition 2 there exists a E [0, m/2) and < oo such that (recall
that EE [G(B)] VQ(0) for any given 0)
(VQ(0,), E,, [R,) (1 sin a:) IQ and E, [[]||]] WB, [IC Vt [T].
Substituting from above in 21 we obtain that, for all f [T].
E, [Q(0+41)] s Q(0,) - mx(1 - -in [IQ())) + 2H E, [IG(OO)] Under Assumptions
(24)
2
andd] from Lemma we obtain that, for all t E [T].
12 [|G()))]] R2 [I)((.) - [G(O))11)] + +IVQ(0)) s (v² + ds²) + C2.
Recall that x² 0² 2 + ds² C Substituting from above in (4) we obtain that
E, [Q(0.41)] Q0,, (x sin [[Q(())) o² Lu 2
7 E
As E 11 E, [... E, [:] .]., from above obtain that
o²LI
E [[Q(0 < (Q(0,) 7e sin a) E [[Q00)11
2 761
1I E [T).
20

---

Under review as a conference paper at ICLR 2022
Thus, by taking summation on both sides over all t [T], obtain that
[(((+++)) - E (Q())) (1 sin a) Σ Yt E
[Q(0))1
Σ
7
2
As 0g is a priori fixed, E [Q((,)] Q(0,). Upon subtracting Q on both sides, and noting that E [[((]) 2 Q" for all 8, we obtain that
T²I. T
[Q(0. Q = Q(0,) Q (1- sin Σ " E
[IQ(0,11
Σ
By re-arranging,
T
d²L
T Σ
(1 sin a) Y E Σ
[Q(()))
=ER(I)))
1t
2
1=1
Upon substituting n 1/v1, obtain that
Σ E
[VQ(0)11
T T²I.u
(ins
=E - Q- +
VT
2 t
Note that Et=l S In
Thus, by multiplying both sides by 1/VT, we obtain that
sin 1= E
[Q(0))1
Q(0,) Q"
o²
11)
In T +1)
T
VT
2
VT
Hence, as min E
[Q(0,) 12] < (+) E
| |IQQ()))1.
[|Q(0))1 Q(9)) Q"
o²Lu
In T +1
(1 (i-sin ai min E [E[T]
VT
2
VT
Hence, the proof.
C.5 PROOF PROPOSITION
Proposition 2. Let b [m], (E, E (0, 1)a. Consider Algorithm with privacy budget (e, 8) and GAR with multiplicative constant (F, f) > Then the following assertions hold true.
1. Under Assumptions
7 Maadd 3 the ap- approoxiiatted VN condition holds true only
1.25b
1
n² z f)
m8
bmiee - 1)
2. Additionally under Assumption 2 if
n 2 (n,
dl
1.25b mo
)
mm(er- b) t
2
then F satisfies the n-approximated VN condition.
Proof. Let us consider an arbitrary GAR F with multiplicative constant p /) > O. We denote the set of points that do not satisfy the constraint on the gradient of Q by O, == {0 E Rd | s 7). While considering Algorithm]] ] the random variable that characterizes the gradients sent by the honest workers is defined as follows:
G(Ø)
Σ Vi (0, x)
40 E Rd
Edd
21

---

Under review as a conference paper at ICLR 2022
where B is set of b points randomly sampled without replacement from D (denoted B ~ Div and
(00, s² Ta). As in the proof of Proposition [ we note that for all 0 E RRd G(0) is unbiased
estimate of VQ( hence we also have that θ == {0 RR || [G())]] - 7). Furthermore, the injected noise is independent of the stochasticity of gradients. Hence for all 0 E R4,
E
[[G(0) E [())) E BBDDiv
Vg (0, V VQ
+ ds²
(25)
FEB
We now demonstrate necessary condition for to satisfy the 17-approximated VN condition under Assumptions [ and 3 To do so, we first show reductio ad absurdum that the 7-approximated VN condition holds true only if
8C2 In 1.256 mn.
2 f)dd
62 In ((e - 1) 1)
Let us assume that there exists 17 > 0 such that
8C In 1.256 mé
2 < (n
(26)
8 In ((et - 1) 1)2
and such that the y-approximated VN condition holds. That is, for all 0 E (
kF 2
(3 |GG())-E(G(O)])) [G(O))] ||[G(()]]
(27)
Let us first note that from have for any 0 E Rd
25 replacing s according to the privacy budget from Theorem
| we
802 In
1256 mB
d
SE - - B
(28)
6 In ((e
1) m
1)²²
Hence, combining 27 and 28
get that for all 0 R
8C2
1.256 mB
(n
< [E((()
(29)
2 In ((e 1) +1)
Recall that Q admits a local minima, hence there exists 8* such that /[Q( = 0. Furthermore, under Assumption
we know that (.)(( is continuous on Rd; hence its range on R includes (.256) m3
SC
the interval 0, KF (F, f)
particular, there exist H' E Rdd such that
62 1))
8C2 In
1.25b
(n, f)dd
126
(30)
b2 (le - 1) m + 1)2
On the one hand, assuming that 6' O,,, leads to a contradiction with (26). On the other hand, assuming that 6' E O,, leads another contradiction with (29 hence also with (26). Finally, we obtain reductio ad absurdum that the 17 n-approximated VN condition holds only if
SC2 In 1.256
2 (n
(31)
In ((et - 1) +
we further note that for any x E R2o, In(x 1) s 2 we have
80 In
1.25b md
C In
(1.256
Ry (n, 2d
4k
m5
(32)
82 In ((e m +1)
be(e" 1)
Finally, combining 31 and 32 proves the necessary condition.
22

---

Under review as a conference paper at ICLR 2022
2. We now show the sufficient condition for F to satisfy the 1-approximated VN condition by further supposing that Assumption 2 holds true. Let us consider
1.256 md
(m(e-1)
1 2 8
2p 2 k)( 8C2din
mle= - 1)
+ 02
(33)
Note that for any x E Ryo,
1 - 1
S.Shm In(x)) Accordingly, have
x
1
1
1
In (e - 1) 11)+
m
m(e< 1) +
1
2 b
(34)
b
(e - +1+
b
By combining (33 and 34 we get
(d(0
(
8C In 1.256
n² pxpp(n f)²
v²
(35)
62 (In ((e 1) 1) 1))
Furthermore, by Lemma under Assumption 2 we have that
8C2 In 1.256
-[GO))) v² +
1 (In ((e - 1) + 1))
Thus,
8C In (1.256
xr(n, [IC(0) - [G((]]]]]] s mF²
02 of
1/3 (1)
Finally, by using 35). for any R O, we have
Kr(n, f)² ||G(0 B [G(O))]] s [[(G)))
The above concludes the proof.
C.6 PROOF OF COROLLARY
Corollary 1. Let E [m]) (c,8) E (0, 1)2. Consider Algorithm GAR F, and 7t = for all t [T]. If Assumptions and are satisfied, then for any 2 1,
1 with privacy budget (e, 6) and
min [IVQ()))) & max 5)² k
8
1.256
m5
mie= 1)
b
1 + +0?
0
In T
Proof. Under the stated assumptions, we note from Proposition 2 that GAR F satisfies the 77- approximated VN condition when
(8C'dl
1.255
(mld 1
+ 1 m(e- 1) b
n 2 kr(n
2
md
Thus, Theorem 2 implies that there exist a E [0, π T/2) and E [0, oo) such that for any T 2 1,
min E [[[QQ()) TE
max
[)²
dd
1.255 md
rafe= - 1)
2 ) + +0²)
Q(0i) Q'
(1 sin a))
(1)
/T
+
2(1 - sin
no
(-
(1+ In
VT
Finally, note that
Q(01) -2
1
1 + In
In
E E
(1 (1-sing a:)
/T
2(1 si
VT
vT
Hence, the proof.
23

---

Under review as a conference paper at ICLR 2022
D ADDITIONAL INFORMATION ON THE EXPERIMENTAL SETUP
D.1 MOMENTUM SGD
While the wish for simplicity of presentation has led us to focus on SGD in the paper, our use of momentum in the experiments is motivated by the following two main observations.
1. El-Mhamdi et al. (202)) recently demonstrated empirically that momentum at the workers can improve the resilience of the system Byzantine workers.
2. Momentum has been demonstrated to improve the convergence rate of SGD by reducing the variance of stochastic gradients. In the context of Algorithm [ momentum can be shown to reduce the variance of the noise injected by the workers, while preserving the privaey budget.
D.2 PRIVACY BUDGET AND NUMBER TRAINING STEPS
The values of step and worker privacy budget E {0.2, 0.05) and 8 = 10 that consider Section 4. yield, respectively, an overall privacy budget of E {7.58, 4.77, 3.46) and J = 1.2 x 10- for every batch size considered, after running the algorithm for T steps. Since (ž. ö) directly depends the batch size well as the total number of learning steps T, adapt the value of T for every run in order to obtain the same (E, 8) in all experiments (regardless of the batch size used). The maximum value
considered 300 steps for the smallest batch size = 25. Larger batch sizes have T < 300 Finally, given fixed batch size and number of steps, evaluate the overall privacy budgets using the Py Porchh package Opacus that is based on the moments accountant algorithm (Abadi et al. 2016), well as the advanced composition theorem (Kairouz et al. 2015
D.3 STUDIED ATTACKS
In the experiments of this paper, we use two state-of-the-art attacks that we refer to as little and empire. Both attacks rely on the same core idea. Let Ç fixed non-negative real number and let ae be the attack vector at time step 1. At every time step 1, all Byzantine workers send + Ça, to the server, where St is an approximation of the real gradient G(O+) at step The specific details each attack are mentioned below.
Little is Enough (Baruch al. 2019). In this attack, a, - where og is the opposite vector of the coordinate- wise standard deviation of G(0,). In experiments, set for little.
Fall of Empires (Xie et al., 2019). In this attack, ag = - All Byzantine workers thus send (1- step In our experiments, we set Ç = 1.1 for empire, corresponding to 0.1 in the notation of the original paper.
E ADDITIONAL EXPERIMENTAL RESULTS
We remind the reader that all experiments are reproducible in one command (refer to code/ Cede/REACME,.. md). All plots can be found in plots/ in the supplementary folder. Due to space limitations, plots/ / only includes the plots for the Fashion-MNIST dataset. The plots corresponding to MNIST can also be generated by running the code.
E. SANITY CHECKS
Impact of Batch Size in Non-Private Setting, Hereafter, we provide some additional results the impact of the batch size in the settings where DP is not enforced. These results validate our claim on the mild impact of the batch size and the GAR selection when noise is injected at the worker level.
In Figure 3 we study the impact of the batch size on the learning accuracy in non non-private setting where the workers do not about leaking private information and thus share their gradients in the clear without adding noise to them. Unlike in Figure 2 from Section 4.2 all curves in all four
Note that to avoid technical difficulties, actually run 300 learning steps for all experiments. However, we report the maximum cross-cccuracies the end of T < 300 steps, where 7 is defined as above.
24

---

Under review as a conference paper at ICLR 2022
1.0
Max cross-accurae
Max cross-accurace
No attack
No attack
MDA
0.4
MDA
0.4
Krum
0.2
Krum
0.2
Median
Median
Bulyan
0.05
25
150
300
500
750
1000
1250
1500
0.9
25
150
300
500
750
1000
1250
1500
Batch-size
Batch-size
1.0
1.0
Max croEs-accuracy
Max cross-accuracy
No attack
No attack
MDA
0.4
MDA
0.4
Krum
0.2
Krum
0.2
Median
Median
Bulyon
0.0
0.0
300
750
1500
300
1500
Batch-size
Batch-size
Figure 3: Impact of the batch size on the cross-accuracy of the learning on Fashion- MNNIST in the non-private scenario. The first and second rows show the little and empire attacks respectively. The first and second columns correspond to and f = 3 Byzantine nodes respectively.
threat scenarios mostly flat. This indicates that the batch size and the GAR indeed become crucial factors in the HPO process whenever DP and BR are combined, and has a negligible impact when only one of these notions is enforced (refer to Figure R
and the No attack curves in Figure 2
Impact of c with and without Byzantine workers. We also provide below some results studying the impact of varying the privacy parameter alone under different attack scenarios. As shown in Figure in the non-Byzantine setting (No attack), increasing (i.e., weakening the privacy guarantees) does increase the maximum cross-accuracy encountered in the learning, but negligible rate. All No attack curves only show mild improvement in the cross- cros-acccuaacy compared to the GARs under attacks. This means that the standard privacy-aceuracy trade-off in DP quite mild in our experiments. However, when there are Byzantine workers in the system executing mate-of-tthe-ar attacks, the impact of on the learning accuracy is more important, especially in the case of little (first row of Figure 4.. In some instances where the executed attack might not be strong (e.g., empire and f = 3). the impact of e mild even in the Byzantine setting.
1.0
Max cross cross-acuur accuracy
No attack
0.8
MDA
0.8
attack
Median
MDA
0.4
0.4
Krum
Max
Median
Bulyan
88.05
88.05
0.10
Epsilon
Epsilon
1.0
1.0
Max closs accureyy
0.6
Max croSs cross-accurao
0.8
0.6
0.6
No attack
MDA
0.4
MDA
0.4
Krum
Median
Median
Bulyan
0.0
0.0
$0.05
Epsllon
Epsilon
Figure 4: Impact of on the cross-accuracy of the learning on Rashion-MNIS for b 1000. The first and second rows show the little and empire attacks respectively. The first and second columns correspond to f = 6 and f = Byzantine nodes respectively.
25

---

Under review as a conference paper at ICLR 2022
E.2 SATISHIABILITY OF THE VN CONDITION IN PRACTICE
Verifying whether the VN condition (or the n-approximated VN condition) holds is actually impossi- ble in practice as we do not have access to the real gradient distribution of the honest workers G-.). Instead we estimate statisties on G() by using the gradient estimates of the honest workers every step of the learning. Furthermore, to facilitate the visualization, we actually compute the VN ratio defined below.
VN Ratio: We re-arrange the terms of the 7-approximated VN condition as follows:
(n f)²
[I((0) E [G(O))I < | [G(O)]I
(36)
(OG())-E(G(O)])
(37)
B [GOOI
kg(n, f)
ratio
In the following, we refer to the left hand side of 37) as the VN ratio. This is the ratio of the standard deviation of the honest gradients to the norm the expected honest gradient, which has already been discussed by EI Mhamdi et al. (2018). In simulations, the VN ratio can be measured during the training along the parameter trajectory by estimating the variance and the expectation of the gradients sent by the honest workers. For GAR F for which the constant Kr(n, J) is known (e.g., see Appendix B), we can measure the VN ratio get insights on the satisfiability of the a-approximated VN condition.
VN Ratio Our Experiments: Takeaways. In Figure we show the measured VN ratios along the parameter trajectory (01..... 300). for both the gradients sampled by each honest worker and the gradients submitted to the GAR. The sampled honest gradients are the gradients computed by the honest workers using the data batches sampled in each step of the training. The submitted honest gradients are the gradients submitted by the honest workers to the parameter server, after having corrupted them using additive Gaussian noise and having applied momentum.
10.0
10.0
5.0
5.0
2.5
"sample" MDA "submit'
'sample" MDA "submit"
0.0
100
200
250
300
0.0
50
100
150
250
300
Step number
Step number
MDA "sample"
10.0
10.0
7.5
5.0
5.0
MDA 'sample'
MDA "submit"
0.0
100
200
0.0
50
250
Step number
Step number
Figure 5: VN ratios for MDA and b 1000, under the same settings (and layout) as in Figure "Sample" corresponds to the VN ratio of the sampled gradients, i.e., gr for the honest worker i. "Submit" corresponds the VN ratio observed by the GAR. The latter significantly differs from the former mostly due to the added Gaussian noise for DP.
Figure 5 summarizes the value the VN ratio we encountered during the learning under the same settings (and layout) as in Figure 2 We observe that the VN ratio of sampled gradient can be extremely small compared to the VN ratio its corresponding submitted gradient. Our first takeaway regarding the submitted gradient is that its VN ratio is "nearly" constant. As the VN ratio of the privacy
26

---

Under review as a conference paper at ICLR 2022
noise is constan 2 the aforementioned observation suggests that the privacy noise is substantially larger than the sampled gradients; hence dominating the VN ratio of the submitted gradients.
Recalling that KMDA (n, f) vBf/mn-),, f), Figure shows that if (in our experiments) KMDA where to be smaller than 0.08, the 7-approximated VN condition would have been satisfied during the entire training. This is not the case in setting where
15. This brings us our second takeaway, discussed as follows. For MDA, there exists extreme (but arguably reasonable) settings for which the VN condition can actually be satisfied, for at least several hundred training steps. However, did not have to use such extreme settings in our experiments to observe convergence.
TThe VN ratio can be treated a property of a generic random vector, e.g., stochastic gradient or privacy noise. As the distribution of the privacy noise does not change during training, its VN ratio constant.
27


Reviews:
[{"review_id": "xwRsD8fIe7K", "reviewer": "Reviewer_Vukg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly written and provides a reasonable solution to this very interesting question. However, I do have several comments.\n1. 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.\n2. If they are the same, then I would like to see a modular solution based on, for example, the following\n    > Aggregating the gradient accurately implies SGD convergence\n\n    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.\n    There is also [accurate robust + DP aggregators](https://arxiv.org/abs/2102.09159).\n    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.\n    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.\n    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.\n3. 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_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.\nThe 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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ncowQ208CYo", "reviewer": "Reviewer_NXde", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\n-Proposition 1 and (especially) Proposition 2 are interesting \n\n-The problem is interesting \n\nWeaknesses: \n\nGeneral points: \n\n-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  \n\n-The significance of the VN condition is not adequately explained. How exactly is this condition relevant to BR? \n\n-The convergence results are not very interpretable, seem to have incorrect units \n\n-Writing needs a lot of work \n\nSpecifics: \n0. Abstract\n\n-\"...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. \n\n1. Introduction\n\n-\"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). \n\n-\"Byzantine\" should be informally defined or briefly described early on before it is used many times \n\n-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. \n\n-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. \n\n-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\n\n-\"parameters have very little impact in most settings when considering DP or BR separately\" is not clear \n\n-Figure 1. Is the number of iterations fixed? \n\n2. Problem Settign \n\n-\"common dataset\" what does this mean? Are the m points divided/partitioned among n workers or all workers have access to D? \n\n-\"*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. \n\n-**\"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.**\n\n-Def 2: explain intuition; provide an example of a BR GAR\n\nSection 3: \n\n-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\n\n-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$ \n\n-**What's the significance of VN condition?** How does it relate to BR?\n\n-\"when $\\epsilon$ and $\\delta$ are non-zero...\": strange sentence because $s$ increases as $\\epsilon$ and $\\delta$ decrease. \n\n-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 \n\n-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_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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ecc5OwLhydU", "reviewer": "Reviewer_tyNc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nWeakness:  \n1. 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.\n2. 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_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.", "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.\n2. 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?", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-eDiFKApzv3", "reviewer": "Reviewer_RoTT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper is well-written and understandable.\nThe result is novel, but not very surprising.\nI didn't check every detail but at a high level the results seem correct.\n\n\nDetail:\n\nIn 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.\n\n", "summary_of_the_paper": "\nThe 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.\n", "summary_of_the_review": "\nThe paper is mostly sound and brings a contribution (even if not very surprising).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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