An Equivalence Between Data Poisoning and Byzantine Gradient Attacks
Authors: Sadegh Farhadkhani
Rachid Guerraoui
Lê-Nguyên Hoang
Oscar Villemaud
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated learning
PAC learning
Byzantine attack
Data poisoning
Personalized  learning

Abstract: To address the resilience of distributed learning, the ``Byzantine" literature considers a strong threat model where workers can report arbitrary gradients to the parameter server. While this model helped generate several fundamental results, it has however sometimes been considered unrealistic, when the workers are mostly trustworthy machines. In this paper, we show a surprising equivalence between this model and data poisoning, a threat considered much more realistic. More specifically, we prove that any gradient attack can be reduced to data poisoning in a personalized federated learning system that provides PAC guarantees (which we show are both desirable and realistic in various personalized federated learning contexts such as linear regression and classification). Maybe most importantly, we derive a simple and practical attack that may be constructed against classical personalized federated learning models, and we show both theoretically and empirically the effectiveness of this attack.

Under review as a conference paper at ICLR 2022
AN EQUIVALENCE BETWEEN DATA POISONING AND BYZANTINE GRADIENT ATTACKS
Anonymous authors Paper under double-blind review
ABSTRACT
To study the resilience of distributed learning, the "Byzantine" literature consid- strong threat model where workers report arbitrary gradients the pa- rameter server. While this model helped generate several fundamental results, it has however sometimes been considered unrealistic, when the workers are mostly trustworthy machines. In this paper, we show a surprising equivalence between this model and data poisoning. a threat considered much more realistic. More specifically, we prove that any gradient attack can be reduced to data poisoning in a personalized federated learning system that provides PAC guarantees (which we show are both desirable and realistic in various personalized federated learning contexts such as linear regression and classification). Maybe most importantl, we derive simple and practical attack that may be constructed against classi- cal personalized federated learning models, and we show both theoretically and empirically the effectiveness of this attack.
INTRODUCTION
Learning algorithms now typically leverage data generated by a large number of users (Smith et al., 2013 Wang al. 2019a often learn common model that fits a large population (Konecny et al. 2015), but also sometimes to construct a personalized model for each individual (Ricci et al.) 2011. Autocompletion (Lehmann & Buschek] (202I) conversational (Shum et al., 2018) and rec- ommendation (Te et al. 2019) algorithms are examples of such algorithms deployed at scale. To be effective, besides huge amounts of (distributed) data (Brown et al., 2020 Fedus et al., 202T), these algorithms require high level of customization. This has motivated research into personalized
federated learning (Fallah et al. 2020 Hanzely et al. 2020 Dinh et al. 2020).
However, in applications such content recommendation, activists, companies, and politicians have strong incentives to promote certain views, products or ideologies (Hoang 2020 Hoang et al., 202T). Remember for instance that, on YouTube, two views out of three result from algorithmic recommen- dations (Solsman 2018). Perhaps unsurprisingly, this has led to vast amounts of fabricated activities bias algorithms (Bradshaw & Howard, 2019, Neudert et al. 2019). like "fake reviews" (Wu al., 2020). The scale of this phenomenon well illustrated by the case of Facebook which, in 2019 alone, reported the removal of around billion fake accounts from its platform (Fung & Garcia 2019). This is particularly concerning in the era of "stochastic parrots" (Bender et al. 2021): cli- mate denialists are incentivized pollute textual datasets with claims like "climate change is hoax", as autocompletion. conversational and recommendation algorithms trained on such data will more likely spread these views (McGuffte & Newhouse 2020)) This raises serious concerns about the vulnerability of personalized federated learning to such misleading data. Data poisoning attacks clearly constitute now a major machine learning security issue (Kumar et al. 2020).
Overall, in highly adversarial environments like social media, given the advent of fakes (John- son & Diakopoulos 2021), we should expect that most data are strategically crafted and labeled. In this context, the authentication of the data provider seems critical. In particular, the safety of learn- ing algorithms arguably demands that they be trained solely on cryptographically signed data, that is, data that provably come from known source. But even signed data cannot be wholeheartedly trusted since users usually have preferences over what ought to be recommended to others. They thus have incentives behave strategically in order to promote certain views products.

---

Under review as a conference paper at ICLR 2022
To address data poisoning, the Byzantine learning literature usually considers that each federated learning worker may behave urbitrarily (Blanchard et al. 2017 Mhamdi et al.) 2018 EI-Mhamdi et al. 202T). Recall that at each iteration of the federated learning stochastic gracient descent, each worker is given the updated model, and is asked to compute the gradient of the loss function with respect (a batch of) its local data. Byzantine learning usually assumes that malicious (Byzantine) worker may report any gradient; without having to justifyy whether such gradient could have been generated through data poisoning. In fact, the gradient attack threat model has sometimes been claimed to be unrealistic in practical federated learning (Shejwalkar et al. (021). especially when the workers are machines owned by trusted entities (cross-silo FL (Kairouz et al. 2021)).
We prove in this paper an equivalence between gradients attacks and fabricated data injection, in a general and desirable collaborative learning framework. Thereby, our paper provides the first prac- tically compelling argument for the necessity to protect federated learning against gradient attacks.
Contributions. As preamble of our main result, we formalize local PAC* learning VValiant 1984) for personalized learning, and prove that a simple and general solution to personalized fed- erated linear regression and classification is indeed locally PAC* learning. Our proof leverages new concept called gradient-PAC" learning, which is of independent interest. We prove that it is sufficient guarantee local PAC* learning, and that it is verified by basic learning algorithms, like linear and logistic regression. This is an important and highly nontrivial contribution of this paper.
Our main contribution is then to prove that local PAC* learning in personalized federated learning essentially implies an equivalence between data poisoning and gradient attacks. More precisely, we show how any (converging) gradient attack can be turned into data poisoning attack, with the same resulting harm. Given how easy it generally is to create fake accounts on web platforms and to inject data poisoning by generating fake activities, this result should arguably greatly increase the concerns over the vulnerabilities of federated learning with user-generated data.
Finally, we propose simple but very general strategic gradient attack, called the counter-grudient atlack (CGA), which any participant to federated learning can deploy to bias the global model towards any target model that better suits their interest. We prove the effectiveness of this attack under fairly general assumptions, which apply to many proposed personalized learning frameworks including Hanzely et al. (2020): Dinh et al. (2020). We then show empirically how this gradient attack can be turned into devastating data poisoning attack, with remarkably few data.
Related work. Byzantine learning has provided both negative and positive results in Byzantine resilience (Blanchard et al., 22017] Mhamdi et al. 20188] Baruch et al. 2019, Xie et al. 2019), some of which apply almost straightforwardly to personalized federated learning (El-Mhamdi al. 2020 2021). Such results study the resilience against a minority of adversarial users. Our paper how- ever focuses on a different kind of malicious users. Namely, like Suya et al. (202T), we study the resilience against strulegic users, who aim to bias the learned models towards a specific target model.
The study of the resilience against strategic users part of the research on strategyproof learning. Many special cases of gwrategyproffnes. have been tackled, including regression (Chen al. 2018h)
Dekel et al. 2010 Perote & Peñal 2004; Ben-Porat & Tennenholtz] 2017). classification
(Meir et al. 2012 Chen et al. [2000] Meir et al. 2011: Hardt et al.) (0166), statistical estimation
CCai et al. 2015), and clustering (Perote & Sevilla 2003). However, none of these papers tackles a
general personalized federated federaaed learning scheme. Typically, for linear regression, Chen et al. (2018b)
and Perote & Perote-Peña (2004) assume that each user can only provide a single data point. This greatly restricts the users" ability to contribute to the learning model. And while Dekel et al. (2010) allows multiple contributions, they either require payments, which might not be possible (c.g.. due to ethical reasons), or they restrict the model one dimension or a constant function in 12d Conversely, Suya et al. (202T) show how to arbitrarily manipulate convex learning models through multiple data injections, in the case where single model is learned from all data at once.
A large literature has focused on data poisoning, with either a focus on backdoor (Dai et al. 2019 Zhao et al. 20200 Severi et al. [20T]] Truong et al.) 20200; Schwarzschild et al. 2021) or triggerless
attacks (Biggio et al. 2012 MunozlGonzález et al. 2017 Shafahi et al. 2018 8 Zhu et al. 2019
We omit complexity considerations for the sake of generality. We define PAC* to be PAC without such considerations.
2

---

Under review as a conference paper at ICLR 2022
Huang et al., 2020 Barreno et al., 2006; Aghakhani et al. 2021 Geiping et al. 2021). However, most of this research analyzed data poisoning without signed data. One noteworthy exception is
Mahloujifar et al. (2019). whose universal attack amplifies the probability of (bad) property.
Collaborative PAC learning was previously introduced by Blum et al. (017)) and then extensively studied (Chen al. 2018a Nguyen & Zakynthinou 2018), sometimes with the presence of Byzan-
tine collaborating users (Qiao 2018 Jain & Orlitsky] [2200] Konstantinov et al.) 2020). We stress however that this line of work assumes that all honest users have the same labeling function. In other words, given any query, they agree on how the query should be answered. This is a very unrealistic assumption in many critical applications, like content moderation or language processing. In fact, in such applications, removing outliers can be argued to amount to ignoring minorities' views, which would be highly unethical. The very definition of PAC learning must then be adapted, which is what we do in this paper (also, we adapt it to parameterized models).
Structure of the paper. The rest of the paper is organized as follows. Section 2 presents general model of personalized learning, formalizes local PAC* learning and defines a general federated gradient descent algorithm. Section proves proves the equivalence between data poisoning and gradient attacks, under local PAC* learning. Section proves the local PAC* learning properties for federated linear regression and classification. Section S then describes simple and general data poisoning attack, whose effectiveness against Eg is proved theoretically and empirically. Section concludes.
2 A GENERAL PERSONALIZER FEDERATED LEARNING FRAMEWORK
We consider a set = = (I,..,, N} of users. Each user E [N] has local signed dataset D,,, and aims to learn a local model 0, E Rd. Users may collaborate to improve their models. Personalized learning must then input a tuple of users' local datasets D (Di...., DD)). and output a tuple of local models 0 A (Oi....,0% v.) Like many others, we assume that the users perform federated learning to do so, by leveraging the computation of common global model E R. Intuitively, the global model an aggregate of all users' local models, which users can leverage to improve their local models. The common global model will typically allow users with too few data to obtain an effective local model, while it may be mostly discarded by users whose local datasets are large.
More formally, we consider a very general personalized learning framework which generalizes the models proposed by Dinh et al. (2020) and HHanzely et al. (2020). Namely, we consider that the personalized learning algorithm outputs a global minimum (p",0" of a global loss given by
Loss(p, 0) a Σ (o, Dz)+ + Σ R(p,On),
(1)
NE[N]
nE(N]
Jestance,HHazzelyy and Dinh et al. (2000) define (p, & |l en 11 which we shall call the Eg regularization. But other regularizations may be considered, like the & regularization R(p, 0..) A X lp 0n or
where R is a regularization, typically with a minimum at ,,, = p. For instance, Hanzely et al. (2020)
the smooth-22 regularization R(p, 0,)) A X 1 + |le- - 0,, 1l Note that, for such regularizations, the limit À= + co essentially yields the classical non-personalized federated learning framework.
2.1 LOCAL PAC* LEARNING
In this paper, we focus on personalized learning algorithms that provably recover user n's preferred model of, if the user provides a large enough honest dataset D,,, i.e. constructed with 61, Such honest datasets D, could typically be obtained by repeatedly drawing random queries (or features), and by using the user's preferred model 0,, to provide (potentially noisy) answers (or labels). We refer to Section 4 for examples. The model recovery condition is then formalized as follows.
Definition 1. A personalized learning algorithm is locally PAC* learning if. for any subset H C [N] of honest users, any preferred models Øt, any E, > O, and any datasets D = from users
H. there exists I such that, if all users h E H provide honest datasets Dn with at least (Da) 2 I data
points, then, with probability at least 8, we have 00% (D) -0% 0%|1, S e for all users h E H.
3

---

Under review as a conference paper at ICLR 2022
Local PAC* learning is arguably very desirable property. Indeed, it guarantees that any honest active user will not be discouraged to participate in federated learning as they will eventually learn their preferred model by providing more and more data. In Section we will show how local PAC* learning can be achieved in practice, by considering specific local loss functions fen.
2.2 FEDERATED GRADIENT DESCENT
While the computation of p" and 8* could be done by single machine, which first collects the datasets D and then minimizes the global loss Loss, modern machine learning deployments often rather rely on federated (stochastic) gradient descent (or variants), with a central trusted parameter server. In this setting, each user n keeps their data Dn, locally. At each iteration t, the parameter server sends the latest global model p' to the users. Each user n is then expected to update its local model given the global model p". either by solving 6% _ arg ming L. (o.. Dx) ) + R(p', 6,,)) (which what we assume in the theory part, in the manner Dinh et al. (2020). or by making a (stochastic) gradient step from the previous local model 0f-1 (which is what is done in our experiments, in the manner of Hanzely & Richtárik (202I). User n is then expected to report the gradient 9f = V VpR(p', 0%) to the parameter server. The parameter server then updates the global model, using gradient step, i.e. it computes y²+ - p' T/e Ene(N) 9h- For simplicity, here, and since our goal to show the vulnerability of personalized federated learning even in good conditions, we assume that the network is synchronous and that no node can crash. Note also that our setting could be generalized to fully decentralized collaborative learning, as was done by EEI-Mhamdi et al. (202I).
We assume that the users are only allowed to send plausible gradient gradients. More precisely, we p. If user n's
denote GRAD(P) & {V, 0) 0 E I2d the closure set of plausible (sub)gradients gradient g is not in the set GRAD(Ø"), the parameter server can easily detect the malicious behavior and S will be ignored by the parameter server at iteration t. In the case of an Eg regularization, where R(p, 0) X llp 012- we clearly have GRAD(P) = Ted for all p E Rd. It can be easily shown that, for & and smooth-l2 regularizations, GRAD(P) is the closed ball (00, A).
Nevertheless, in this setting, strategic user E [N] can deviate from its expected behavior, to bias the global model in their favor. We identify in particular three sorts of attacks.
Data poisoning: Instead of collecting honest dataset, fabricates any strategically crafted dataset D., and then performs all other operations as expected.
Model attack: At each iteration f, s fixes 0 A where 0 is any strategically crafted model. All other operations would then be executed as expected.
Gradient attack: At each iteration f, 8 sends any (plausible) strategically crafted gradient g'-
Gradient attacks are intuitively the most harmful attacks, as the strategic user can then adapt their attack based on what they observe during the learning process. However, because of this, gradient attacks are more likely to be flagged as suspicious behaviors. At the other end of the spectrum, data poisoning is a much safer attack, as the strategic user can always report their entire dataset, and prove that they rigorously performed the expected computations. In fact, data poisoning can be executed, even if users directly provide the data to a (trusted) central authority, which is then tasked to execute (federated) gradient descent. This is typically what is done to construct recommendation algorithms on social medias, where users' data are their online activities (what they view, like and share). Crucially, especially in applications with clear ground truth, such as content moderation or language processing, the strategic user can always argue that their dataset is an "honest" dataset; not strategically crafted one. Ignoring the strategic user's data on the basis that it is an "outlier" may then be regarded as unethical, as it can be argued to amount to rejecting minorities' viewpoints.
3 THE EQUIVALENCE BETWEEN DATA POISONING AND GRADIENT ATTACKS
We now present our main result. The threat model we considered is closely related "model- targeted attacks", studied in Suya et al. (202I). Recall also that, in this theory part, at each iteration, local models f are fully optimized, given p., in the manner of Dinh et al. (2020).
Theorem (Equivalence between gradient attacks and data poisoning). Assume local PAC* learn- ing, and &3 or smooth-l2 regularization. Assume also that L.,, is convex and L-smooth for all users
4

---

Under review as a conference paper at ICLR 2022
[N), and that the learning rate qu is constant and small enough. Consider any datasets D=s provided by users n + s. Then, for any target model fJ E IR4, there exists a converging gradient attack of strategic user (i.e. I's converges) such that p² + 0%, if and onty if. for any 0, there exists dataset De such that | (D) 01 ||| S.
Note that smoothness is used as a sufficient condition to prove the convergence of federated gradient descent. We now present our proof, which goes through the intermediary step of model attacks.
3.1 EQUIVALENCE BETWEEN DATA POISONING AND MODEL ATTACKS
In this section, we prove the cquivalence between data poisoning and model attacks. Lemma (Reduction from model attack to data poisoning). Consider any data D and user s E [N]]
Assume the global loss with datasets DD has a global minimum (0", 00). Then (p" ,,0,) is also global minimum of the modified loss with datasets D_2 and strategic reporting 0 2 (D)
Proof. The proof is almost straightforward. It is given in Appendix B.1
Now, intuitively, by virtue of local PAC* learning, strategic user can essentially guarantee that the personalized learning framework will be learning 0; so 0 But, priori, it may seem unclear if this will imply a biasing of the global model essentially identical to the one obtained through the model attack that imposes 6% = 8.. In the sequel, show that the answer is yes.
Lemma 2 (Reduction from data poisoning to model attack). Assume Ey l2 or smooth-l2 regular- ization, and assume local PAC* learning. Consider any datasets D_ and any attack model 0 such
that the modified loss LOSS, has a unique minimum p" (8 D= (000 D_s). Then, for any e > O, there exists dataset Dr such that we have
0 (D) --0pppp (0 -=.) Se and Vn s (0)(D) (, D_,)) Se.
(2)
Our proof in fact holds for all continuous regularizations R with R(p 0) - oa as 1le 011 + co. Moreover, note that the approximation guarantee holds for local models too.
Sketch of proof. Given local PAC* learning, for a large dataset DD constructed from 0 strategic user can guarantee 8% (D) 0 By carefully bounding the effect of the approximation on the loss using the Heine-Canter theorem, show that this implies p (D) Re (0 D=s)) and (D)
( D_.) for all + too. The precise analysis, given in Appendix B.2 is nontrivial.
3.2 EQUIVALENCE BETWEEN MODEL ATTACKS AND GRADIENT ATTACKS
For the last few years, gradient attacks have been widely studied by the Byzantine learning literature. Recently, (hejwalkar al. (021) argued that they are not realistic threat model. Below, we prove that, in our setting, they are actually as concerning model attacks (and, thus, as data poisoning). Lemma 3 (Reduction from model attack gradient attack). Assume that Ln is convex and L- smooth for all nodes n. E [N), and that we use la or smooth-lz regularization. If g: converges and if T) 17 is a constant small enough, then p² will converge too. Denote 8 its limit. Then for any S.
> 0, there is 0 Rdd such that 100 p" p0 D
Sketch of proof. Denote g.ºd the limit of g¹ Gradient descent then behaves as though was minimiz- ing the loss plus pT 9 (and ignoring R(p,0,) Essentially, classical gradient descent theory then guarantees the convergence of p' ,00 though the precise proof nontrivial. Then, since GRAD is closed and S.ºh E GRAD, we can construct 0 which approximately yields the gradient gf The full proof (which also yields the necessary upper bound on 7)) is given in Appendix B.3
Li
Since any model attack clearly be achieved by the corresponding honest gradient attack, conclude that model attacks and gradient attacks are essentially equivalent. In light of our previous results, this implies that gradient attacks are essentially equivalent data poisoning (Theorem I.
5

---

Under review as a conference paper at ICLR 2022
4 EXAMPLES OF LOCALLY PAC* LEARNING SYSTEMS
To the best of our knowledge, though similar to collaborative PAC learning (Blum et al. 2017) local PAC* learnability is a new concept in the context of personalized federated learning. It is thus important to show that it is not meaningless. To achieve this, in this section, we provide sufficient conditions for a personalized learning model to be locally PAC* learnable. First, we construct local losses Ln as sums of losses per input, i.e.
(O,, =
= 110 + Σ DED
z),
(3)
for some "loss per input" function and some weight v > O. Appendix C gives theoretical and empirical arguments provided for using such sum (as opposed to an expectation). Remarkably, for linear or logistic regression, given such a loss, local PAC* learning can then be guaranteed.
Theorem 2 (Personalized least square linear regression is locally PAC* learning). Consider lz lg or smooth-l2 regularization. Assume that, to generate a data Tú, a user with preferred parameter Ot E 2dd first independently draws a random vector query Qi E R& from a sub-Gaussian query distribution 2, with parameter ag and positive definite matrix E E [2.2]] Assume that the user labels Qi with a real- val-valued answer A, = 2 gt + Eú, where &, is zero-mean nab-Gaussian random noise with parameter σg, independent from Qi and other data points. Finally, assume that ((, A:) (0= Q A.)². Then the personalized learning algorithm is locally PAC* learning.
Theorem 3 (Personalized logistic regression is locally PAC PAC*-learning). Consider Lg l or smooth- l2 regularization. Assume that, to generate a data Ii, a user with preferred parameter @i E Rdd first independently draws a random vector query Qi E Id from a query distribution ②, whose support SUPP( ②) bounded and spuns the full vector space IRd Assume that the user then labels 2 with answer A, = 1 with probability a ( 0t), and labels it A, = -1 otherwise, where a(z) = (1+--*)-1 is the sigmoid logistic function. Finally, assume that E(O, Qi, = In(0 Q.)). Then the personalized learning algorithm is locally PAC learning.
4.1
PROOF SKETCH
In this section, we outline the proofs of theorems 2 and 3 they are interesting in their own sake. The proofs both leverage the following notion, which intuitively means "robust PAC* learning". Definition 2 (Gradient-PAC*). Denote E(D, 0: I, A, a, the event
VO E Rdd (0- (0_ VL 2 AImin |00 - 00
ot [12] -I 0
07 12
(4)
The loss l is gradient-PAC' if. for any K> O. there exist constants Ak,, Bx: O and ar < 1, such that for any preferred model Qf E Rdd with ||0"]], S K. assuming that the dataset DD is obtained by honestly collecting and labeling I data points according to the preferred model 0¹, the probability of the event EDD 8*, I, Ak, BR, ax) goes to 1 as I - 30.
Intuitively, this definition asserts that, as we collect more data from an honest user, then, with high probability, the gradient of the loss at any point too far from Bt will point away from gt, In particular, gradient descent is then essentially guaranteed to draw 0 closer to 0t, The right-hand side of equation is subtly chosen to be strong enough to yield local PAC* learning guarantees, and weak enough to be verified by linear and logistic regression, as proved by the following lemma.
Lemma 4. Logistic and linear regression, defined in theorems 2 and 3
are gradient PAC* learning.
Sketch of proof. In the case of linear regression, remarkably, the discrepancy between the em- pirical and the expected loss functions depends only on a few key random variables, such as min SP (+E2,))
and Q. which can be controlled by appropriate concentration bounds. Meanwhile, for logistic regression, for |b] < K, we observe that (a - b)(a(a) - a(b)) > Cx. min((a - bl la b12). Essentially, this proves that gradient-PAC* would hold if the empiri- cal loss was replaced by the expected loss (times Σ). The actual proofs, however, are nontrivial, especially in the case of logistic regression, which leverages topological considerations to derive a critical uniform concentration bound. The full proofs are given in appendices D.2 and D.3

---

Under review as a conference paper at ICLR 2022
Now, under very mild assumptions the regularization R (not convexity!), which are verified by the Eg, lg and smooth-f2 regularizations, we prove that the gradient-PAG learnailiity through suffices to guarantec that personalized learning will be locally PAC* learning.
Lemma 5, Assume R is (sub saubddffereetiable and nonnegative, and R(p.0) - oc as 1p 0112 + cc. If é grudiem-PACC* and nonnegative, then personalized learning locally PeC*-ngg
Sketch of proof. Once other users' datasets fixed, the learning of an honest user's model has fixed biased due to R. But as the user provides more data, by gradient-PAC*, the local loss becomes predominant, which guarantees local PAC*-learning. Appendix E provides full proof.
Combining the two lemmas clearly yields theorems and 3 as special cases. Note that our result actually applies to more general set of regularizations and more general set local losses.
4.2 THE CASE OF NEURAL NETWORKS
Neural networks generally do not verify gradient PAC* learning. After all, because of symmetries like neuron swapping. different values the parameters compute the same neural network function. Thus the notion of "preferred model" Øf arguably ill-defined for neural networks Nevertheless, we may consider strategic user who only aims to bias the parameters of the last layer. In particular, assuming that all layers but the last one of neural network are pretrained and fixed, then our theory may apply to the parameters of the last layer, if it performs classification or regression.
5 A PRACTICAL DATA POISONING ATTACK
We now construct practical data poisoning attack. We do so by introducing a new effective gradient attack, and by then leveraging our equivalence to turn it into data poisoning attack.
5.1 THE COUNTER-GRADEEN ATTACK
We now define simple, general and practical gradient attack, which we call the counter-gradient attack (CGA). Intuitively, this attack estimates the sum وīا of the gradients of other users based on its value the previous iteration, which be inferred from the way the global model p² was updated into p². More precisely, apart from initialization g"_ & 0, CGA makes the estimation
g"_
(5)
T--1
Strategic user then reports the plausible gradient that moves the global model closest to the user's target model 0f. assuming others report مناو In other words, at every iteration, CGA reports
g. E arg min ||e' Tr(0". + +)) -01l2-
gEGRAn(p)
Note that, perform this attack, user only needs know the previous and current learning rates Mh-1 and nhe the previous and current global models p² and p¹, and their target model 0f.
p' -'o For convex sets GRAD(P'), Computation of CGA. Define hg -6-
straightforward to that CGA boils down to computing the orthogonal projection of hi on GRAD(p'). This yields very simple computations for E2, la and smooth-ly regularizations. Proposition For E, regularization, CGA reports gi = h For l2 or smooth-lz regularization, CGA reports g h² min (1, [11
Proof. Equation boils down minimizing the distance between d'-01 g", and GRAD(P), which is the (convex) ball B(0, A). This minimum is the orthogonal projection on B(,, A).
nt
FFvidently, our definition could be easily modified give importance to the computed function, rather than the parameters of the model.

---

Under review as a conference paper at ICLR 2022
Theoretical analysis. We now prove that CGA is perfectly successful against Eg regularization. To do so, we suppose that, at each iteration and for each user n o s, the local models 8, are fully optimized with respect to p', and the honest gradients of 9 are used for the gradient descent of p.
Theorem 4. Consider lg regularization. Assume that É is convex and sm-moh,th and that 7) n is small enough. Then CGA is converging and optimal, as p¹ + 0).
Sketch of proof. The main challenge is to guarantee that the other users' gradients gh: for n + remain sufficiently stable over time to guarantee convergence, which can be done by leveraging L-smoothness. The full proof, with the necessary upper-bound on 7), is given in Appendix
The analysis of the convergence against smooth-E, &2 is unfortunately significantly more challenging. Here, we simply make a remark about what CGA yields in this case, if it converges.
Proposition 2. If CGA against smooth-&2 regularization converges for Tjt n, then it either achieves perfect manipulation, or it is eventually partially honest, the sense that the gradient by CGA correctly points towards 0g.
Proof. Denote P the projection onto the closed ball A). If CGA converges, then, by Proposi- -8: = -2- This implies in particular that pD o and ge must be colinear.
tion P
If perfect manipulation is not achieved (i.e. ~Td * (i), then we must have g.º
Empirical evaluation of CGA. We deployed CGA to bias the federated learning of MNIST. We consider a strategic user whose target model is one that labels O's as I's, I's as 2's, and so on, until 9's that are labeled as O's. In particular, this target model has nil accuracy. Figure [ shows that such a user effectively hacks the & regularization against 10 honest users who each have 6,000 data points of MNIST, in the case where local mod- els only undergo single gradient step each iteration, but fails to hack the l regularization. Further details on the experiment given in Appendix G We also ran a similar successful attack on the last layer of deep neural network trained on cifar- 10, which detailed in Appendix ! The Appendix also discusses the extent to which the attack may be turned into data poisoning.
56
Epochs
Figure 1: Accuracy of the global model under attack by CGA.
5.2 FROM GRADIENT ATTACK TO MODEL ATTACK AGAINST &
We now show how to turn a gradient attack into model attack, against E regularization. Assume that we found a gradient ged such that ~ = 0z. It is trivial to transform into a model attack by setting 0
0! g as guaranteed by the following result, and as depicted by Figure
Model attack
Model atlack
25
nomm
12 dil target ddst
15-
0.2
5-
acc glob
50
150
0.0
Epochs
Epochs
(a) Distance between the global model p¹ and the target model 0f (target dist).
(b) Accuracy of p' according to o (which rela- bels + 1 + 2 + 0).
Figure 2: Successful model attack against E by combining CGA and Proposition 3
8

---

Under review as a conference paper at ICLR 2022
Proposition 3. Consider the lg regularization. Suppose that g' - gr and p' O with constant learning rate 1/t = 1/. Then, under the model attack 0 0 9% the gradient at p 0. vanishes, i.e. vpLoss(0 0- (0) D.i.D-Db0 -))), D_a) 0.
Given that the learning rate constant, the convergence p² + of implies that the sum of honest users' gradients at = 0 must equal - Therefore, to achieve n = of with model attack, it suffices to send a model 0 such that the gradient of ||e 0 l| with respect to p at g does the trick.
Proof.
0g equals 9." Since the gradient is A(0
5.3 FROM MODEL ATTACK TO DATA POISONING AGAINST E3
The case of linear regression. In linear regression, any model attack can be turned into a single data poisoning attack, as proved by the following theorem whose proof is given in Appendix H
Theorem 5. Consider the Eg regularization and linear regression. For any data D_ and any target value 0J, there is a datapoint (Q,A) to be injected by user s such that p ()((Q, D-,) = 0..
The case of linear classification. We now consider linear classification, with the case of MNIST. By Theorem 2 any model attack can be turned into data poisoning, provided sufficiently many (random) data points are labeled by the strategic user. However, this may require creating too many data labelings. especially if the norm of 8 is large (which is the case if s is alone against many active users), as suggested by Theorem 3
For efficient data poisoning. define the indifference affine subspace V C Rd as the set of images with equiprobable labels. Intuitively, labeling images close to V is very informative, as it informs us directly about the separating hyperplanes. To generate images, we first draw random images, which we then project orthogonally on V. We then add small noise, before probabilistically labeling the image with model 0 Note that this leads us consider images not in [0, 1jst Figure 3 shows the effectiveness the resulting data poisoning attack, with only 2,000 data points, as opposed to the other nodes' 6,000 data points. More details and explanations provided in Appendix [
Dala allack
Data attack
35-
25-
m2mm
20
dist
0.6
nomm
targel_dae dist
10-
glob
50
100
150
200
0.0
200
250
Epochs
(a) Distance between the global model p' and the target model 0J (target.dist).
(b) Accuracy of p' according to 81 (which rela- bels
+ ... + + 0).
Figure 3: Successful data attack against E by the efficient data generation scheme.
6 CONCLUDING REMARKS
We showed in this paper that, unlike what has been argued by, c.g., Shejwalkar et al. (2021) }. the gra- dient attack threat is not unrealistic. For personalized federated learning with local PAC* guarantees, gradient attacks are in fact just realistic and harmful as strategic data reporting. More generally, our work stresses how critical Byzantine learning research is. For instance, El-Mhamdi et al. (2021) proved lower bounds on what any collaborative learning algorithm can guarantee in heterogeneous environments, under Byzantine gradient attacks. Our work implies that, at least for certain person- alized federated learning problems, these lower bounds also hold for data poisoning attacks, which are known to be common for many high-risk applications. Arguably, a lot more security measures urgently needed to make large-scale learning algorithms safe.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
The safety of algorithms is arguably a prerequisite to their ethics. After all, an arbitrarily manip- ulable large-scale algorithm will unavoidably endanger the targets of the entities that successfully design such algorithms. Typically, unsafe large-scale recommendation algorithms may be hacked by health disinformation campaigns that aim promote non-certified products, e.g., by falsely pretend- ing that they cure COVID-19. Such algorithms must not be regarded as ethical, even if they were designed with the best intentions. We believe that our work helps understand the vulnerabilities of such algorithms, and will motivate further research in the ethics and security of machine learning.
REPRODUCIBILITY STATEMENT
All our experiments are run on the classical datasets MNIST and FashionMNIST. We provide all of the source codes to reproduce the experiments:
The sum versus expectation experiments can be run by executing this file:
https::/www.drpppttt wwwp/hhhggdmmm 9a1 http:///d...oaaaaaaaaaaaaaaa/aaa Incbv015YG1172277dd1
The couner--gradien attack experiments can run by executing this file:
https::/www.rrppppot http::/wwwppp...ccoc////cccccoc/
The data poisoning attack experiments be run by executing this file:
httpe://ww..rrgboo..com///////
vivzt.i 18chh/
The cifar10 VGG I3-BN experiments can be run by executing this file:
hetps://ww..dre
SyLuddWmbl1aaddl
The experiments are seeded and the CuDNN backend configured in deterministic mode order to reduce the sources of non-determinism. We also turn of the benchmark mode. Executing the codes will generate the figures and statistics of our main paper, and most of the figures our Appendix. Our other figures can be obtained by adjusting the hyperparameters of codes.
The full description of the architecture and optimisation algorithm used is described in Appendix C The experimental setup details of each experiment are provided in the Appendix, along with addi- tional results. The Appendix also contains the full proofs of our theorems.
REFERENCES
Hojjat Aghakhani. Dongyu Meng, Yu-Xiang Wang. Christopher Kruegel, and Giovanni Vigna. Bullseye polytope: A scalable clcan-label poisoning attack with improved transferability, 2021.
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph, and J. D. Tygar. Can machine learning secure? Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, ASIACCS '06, pp. 25,2,, New York, NY, USA, 2006. Association for Computing Machinery, ISBN 1595932720. doi: 10.1145/1128817112222 128824. URL http::
//doi. //doi.org/10/ 10. 1101111411222 17.181822
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bue, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL httlhttps: pttpppss/pppcceeeigs..... www.ppp...n....iiii............. ccc1c591e 4144 6cd1 Beard186bbboe 3obbbccfffsee311-4----222 htt.://cc..................pe//a
pdf
Omer Ben-Porat and Moshe Tennenholtz. Best response regression. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL /ttptt/ssssppppoocc...aerrro.c.a
pdf
10

---

Under review as a conference paper at ICLR 2022
Emily M. Bender, Timnit Gebru, Angelina McMillan- Major, and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Madeleine Clare Elish, William Isaac, and Richard S. Zemel (eds.), FAccT '21: 2021 ACM Conference Fairness, Accountabilityy and Transparency, Virtual Event / Toronto, Canada, March 3-10, 2021, pp. 610- doi: 10.1145/344218..22
623. ACM, 2021.
10 URL pttpps://dss 10. 1145/
3442188 3445922
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector ma- chines. In Proceedings of the 29th International Conference on Machine Learning. ICML 2012, Edinburgh, Scotland, UK, June 26- July 1, 2012. ieml.ee Omnipress, 2012. URL
http::/ wtt.cc/////c/eeeec. 880.. pdf
Peva Blanchard, EI Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Isabelle Guyon, Ul- rike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 30: An-
nual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 119-129, 2017. URL www.ee---byaanineeeeeeeettteeeee
6617-machine Teareeaaneeee -a--ing-wtt wit with- adversaries ie
ent desceeds.nn
Avrim Blum, Nika Haghtalab, Ariel D. Procaccia, and Mingda Qiao. Collaborative PAC learning. In
Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. Vish-
wanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 2392-2401, 2017. URL http::tttt//pppttttccttttt http:///ooccedddcoooooooo ngs. neur wwwerrpp... .c..cc/ .ht.raattttttm...... .tmll
Samantha Bradshaw and Philip Howard. The global disinformation order: 2019 global inventory of organised social media manipulation. Project Computational Propaganda, 2019.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam. Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, lya Sutskever, and Dario Amodei. Language models are few-shot learners. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Florina Balcan, and Hsuan-Tiee Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL htttps://prooceednggs neur ips wwtppppppe//////assit... 1457c0d6bfcb453 741 8ofboooooiio... 42 2o0006/6664484444aaaaaaaaa444460 Abst -ottt htmm
Yang Cai, Constantinos Daskalakis, and Christos H. Papadimitriou. Optimum statistical estimation with strategic data sources. In Peter Grünwald, Elad Hazan, and Satyen Kale (cds.), Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6. 2015, vol- ume 40 of JMLR Workshop and Conference Proceedings, pp. 280-296. JMIR.org, 2015. URL .m........... wwtpss//////aa//..ee
Jiecao Chen, Qin Zhang, and Yuan Zhou. Tight bounds for collaborative PAC learn- ing via multiplicative weights. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 3602-3611, 2018a. URL -aa Abst html
Yiling Chen, Chara Podimata, Ariel D. Procaccia, and Nisarg Shah. Strategyproof línear regres- sion in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Com- putation, EC 118, pp. 9-26, New York, NY. USA, 2018b. Association for Computing Machin- ery. ISBN 450355835.. doi: 1tt.5//221916..2211111 URL htthtt::: :/doi. orq/10. 1145/321 91 66 351
11

---

Under review as a conference paper at ICLR 2022
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15265-15276. Curran Asso- ciates, Inc., 2020. URL /tt/https:://proeeeiiin httprocceeddigs..eerriie.eee neurips ps. cc/ scc/paper/2220//11ee ae87a54e
pdf
Jiazhu Dai, Chuanshuai Chen, and Yufeng Li. A backdoor attack against lstm-based text classifi- cation systems. JEEE Access, 7:138872-13887,, 2019. doi: 10. N0.109/ACCESSSS21992241333
URL httt:p::/do..orgg///oo 101/.//A
Ofer Dekel, Felix Fischer, and Ariel D. Procaccia. Incentive compatible regression learning. Jour- nal of Computer and System Sciences, 76(8):759-777, 2010. ISSN 0022-0000. doi: https://doi.
0tg/100..006/i,.sss20000000
URL https: /ww::///wwwww. http::/wwwwwcciicciieeee..eee http://www...aaeeeaaaooooooooaaa wtt.:/eett..cccccennn/e///e
atticle//s1/5022000000003333
Canh Dinh, Nguyen H. Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Hugo Larochelle, Marc Aurelio Ranzato, Raia Hadsell, Maria-Florin Bal- can, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020,
neurips cc/ wttpsccapppp//////aaaas// .tml
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lê Nguyên Hoang, and Sébastien Rouault. Genuinely distributed byzantine machine learning. In Yuval Emek and Christian Cachin (eds.), PODC '20: ACM Symposium Principles of Distributed Computing, Virtual doi: 10.14553338733434055655 URL
Event, Italy, August 3-7, 2020, pp. 355 364. ACM, 2020.
https: /ww.i/oiii.o//// org 10 11w111155//0 338273382333 3405695
El-Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê Nguyên Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, heteroge- neous, asynchronous and nonconvex learning). In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, December 6- 14, 2021, 2021.
El-Mahdi El-Mhamdi, Rachid Guerraoui, and Sébastien Rouault. Distributed momentum for byzintine-resilientt stochastic gradient descent. 9th International Conference on Learning Representaatinss ICLR 2021, Vienna, Austria, May 4-8, 2021. OpenReview.net, 2021. URL
net/ wwt.://oooonn----BBBAaaaano H8UHahWG6A3
Alireza Fallah, Aryan Mokhtari, and Asuman E. Ozdaglar. Personalized federated learn- ing with theoretical guarantees: A model-agnostic meta-learning approach. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL Intpps:/pproeeddingg neurips cc/paper/2020/nas. Abs.:eccaddd-.tttttt...t..t. html
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion param- eter models with simple and efficient sparsity. CoRR, abs/2101.03961, 2021. URL https:
// /arriiv.org http//aaa///.../1/ 03961
Brian Fung and Ahiza Garcia. Facebook has shut down 5.4 billion fake accounts this year. CNN Business, 2019.
Jonas Geiping, Liam H Fowl, W. Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. In International Conference on Learning Representations, 2021. URL net nett/Eozum?id--lollnii
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models, 2021.
12

---

Under review as a conference paper at ICLR 2022
Filip Hanzely, Slavomír Hanzely, Samuel Horväth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. In Hugo Larochelle, Mare' Aurelio Ranzato. Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neu- ral Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, vir- tual, 2020. URL
neurips.. ww/papprr222//aaass..se S57aaff7922330 0t0.19988801111311112233838883
Abstract..ttmtt html
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Com- puter Science, ITCS 16, pp. 111-122, New York, NY. USA. 2016. Association for Com- puting Machinery. ISBN 9781450340571. doi: 10.1145/2840722888477.... URL https: //doi. 10. 1111///4440111 ST0.00777..288838
Le Nguyên Hoang. Science communication desperately needs more aligned recommendation algo- rithms. Frontiers in Communication, 5:115, 2020.
Lê Nguyên Hoang, Louis Faucon, and El-Mahdi El-Mhamdi. Recommendation algorithms, ne- glected opportunity for public health. Revue Médecine et Philosophie, 4(2):16-24, 2021.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2 edition, 2012. doi: 10.1017/977 01199788119024111
W. Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Mctapoi- son: Practical general-purpose clean-label data poisoning.
In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan -Tenn-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neu- ral Information Processing Systemy 2020, NeurlPS 2020, December 6-12, 2020, vir- Iual, 2020. URL httpps:/pproeeddingg wgweeeiiigggg...o neurips....pp... ips. httpp..cc/ccc... Soc//aaprr2222/haaeee Absttaaatttt.at.tttt.......aaa.. .hml
Eugene Ie, Vihan Jain, Jing Wang, Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Tushar Chandra, and Craig Boutilier. Slateq: tractable decomposition for reinforcement learning with recommendation sets. In Sarit Kraus (ed.), Proceedings of the Twenty-Eight International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 2599. ijcai.org. 2019. doi: 0224966//jaii22199333 URI. https: 10. 249.2/2943333 htt.///jjaaa..11336633 2019/360
Ayush Jain and Alon Orlitsky. A general method for robust learning from batches. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, viruual, 2020. URL f7882ce7er 6d968 7
new.ieerrio ccs/paper/222//hastt html
Deborah G. Johnson and Nicholas Diakopoulos. What to do about deepfakes. Commun. ACM, 64 (3):33-35, 2021. doi: 10. 145/3447255 /ttp 0ttp////111111/44775555
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafacl G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb. David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgüi,, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich. Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, 2021.
Jakub Konecný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed op- timization beyond the datacenter. CoRR, abs/151 1.03575, 2015. URL bttt:://axii... orq/ abs / 03575
13

---

Under review as a conference paper at ICLR 2022
Nikola Konstantinov, Elias Frantar, Dan Alistarh, and Christoph Lampert. On the sample complexity of adversarial multi-source PAC learning. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 5416 5416-5425. PMLR, 2020. URI.htpp: / httptttppp/pppceedinneeoeee vl wwwl119///nnttttteo invoe htmml
m p..prsssvlll
Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia. Adversarial machine learning-industry per- spectives. In 2020 IEEE Security and Privacy Workshops, SP Workshops, San Francisco, CA, USA, May 21, 2020, pp. 69 75. IEEE, 2020. doi: 010109/$P..0008220000000000 attpss://oft www.oo.g........o 1 109 www.//////600.... 2020. 00028
URL
Florian Lehmann and Daniel Buschek. Examining autocompletion as basic concept for interaction with generative AI. i-com, 19(3):251-200 2021. doi: 1011555/ccom222200000 URL https:
//doi. 10. 1515/icom
Saeed Mahloujifar, Mohammad Mahmoody, and Ameer Mohammed. Data poisoning attacks in multi-party learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceed- ings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Re- search, pp. 4274-4283. PMIR, 2019. URL http:://proceeeeee ngs. ml presss/997 maah far 9a 19thttml)
Guangean Mai, Kai Cao, Pong C. Yuen, and Anil K. Jain. On the reconstruction of face images from deep face templates. IEEE Trans. Pattern Anal. Mach. Intell,, 41(5): 188- 2019. doi: 10. 10.100/7AAM.20118887777777 2827389
URL httpp:://oi.orrrttteeet 111.11...1.11111
2018.
Kris McGuffie and Alex Newhouse. The radicalization risks of GPT-3 and advanced neural language models. CoRR, abs/2009.06800 2020. URL httptttss///xiii...ttta http::///raaxl..or///b////00000 06807
Reshef Meir, Shaull Almagor, Assaf Michaely, and Jeffrey Rosenschein. Tight bounds for strat- egyproof classification. In The 10th International Conference on Autonomous Agents and Multi- agent Systems Volume 1, AAMAS '11 pp. 319-326, Richland, SC, 2011. International Founda- tion for Autonomous Agents and Multiagent Systems. ISBN 0982657153.
Reshef Meir, Ariel D. Procaccia, and Jeffrey S. Rosenschein. Algorithms for strategyproof classifi- cation. Artificial Intelligence, 1886:1331553 2012. ISSN 0004-3702. doi: https://doi.org/10.0000 1016/ j.1t.it 0000000000...000.000000000 URL https: /twtt:::/www.... a www.::/wwwinneeddecc........ www. ccom//cceenc/arrticll
011/500437022200222
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of dis- tributed learning in byzantium. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICMI.201 Stockholmsmissaan, Stockholm, Sweden, July 10-15, 2018. volume 80 of Proceedings of Machine Learning Research, pp. 3518- 3527. PMLR, 2018. URw httt:::/ppocceec..ggg//////o//et mlr prwsssssssp....... / v80 wwt.m//ammiiii. html
Luis Muñoz-González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C. Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with mack-gradient optimization. Bhavani M. Thuraisingham, Battista Biggio, David Mandell Freeman, Brad Miller, and Arunesh Sinha (eds.), Proceedings of the 10th ACM Workshop on Artificial Intelli- gence and Security, AlSec CCS 2017, Dallas, TX, USA, November 3, 2017, pp. 27-38. ACM, 2017. doi: 10.1145/31285723314444 3140451
URL https:://o// https://doio.org/111/ 145 / 3128572. 111.//...1113318572222
Lisa-Maria Neudert, Philip Howard, and Bence Kollanyi. Sourcing and automation of polit- ical news and information during three european elections. Social Media+ Society, 5(3): 2056305119863147, 2019.
Huy L.
Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative PAC learning. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò
and
14

---

Under review as a conference paper at ICLR 2022
Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 7642-7650, 2018. URL
nwwrris........... cc/
paper/2018 Baw.//hhahhhhae 35 255.555f551111177743555555555523
Javier Perote and Juan Perote-Peña. prrategy-proof, estimators for simple regression. Math- ematical Social Sciences, 47(2):153-176, 2004. ISSN 0165-4896. doi: https///oo..or//10
1016/590665448660000008844444 URL httpt::///// //ws:///wwwt. sci encedi wtt.:iirrrrttcccccieeeeoooeeeeee cww.science//
Javier Perote and Olavide Sevilla. The impossibility of strategy-proof clustering. Economics Bul- letin, 2003.
Huy Phan. huymphaanpyxorrh.ccffrt January 2021. URL https:///ci.or//1000 Zenodo. 4431043
Mingda Qiao. Do outliers ruin collaboration? In Jennifer G. Dy and Andreas Krause (eds.), Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Re- search, pp. 4177-4184. PMLR, 2018. URL http::/pproceedingg www.mmrr...mm wwt.smmr....ssseeee press/vCC/ giaol Ba. html,
Francesco Ricci, Lior Rokach, and Bracha Shapira. Introduction to recommender systems hand- book. In Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor (eds.), Recom- mender Systems Handbook, pp. 1-35. Springer, 2011. 1. doi: 10. 100777978-0-338--5520--33 100110077990 978 0 387 85820-883333 3
URL,
attpps:/doo wtt.://ro......10.......
Avi Schwarzschild, Micah Goldblum, Arjun Gupta, John P Dickerson, and Tom Goldstein. Just how toxie data poisoning? a unified benchmark for backdoor and data poisoning at- tacks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Con- ference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9389 9398. PMLR, 18 24 Jul 2021. URL htttss::/ppooceeeeeee ngs. mlr. pttps//vss/////// schwarzsch ld21a.html
Giorgio Severi, Jim Meyer, Scott Coull, and Alina Oprea. Explanation- guided backdoor poi- soning attacks against malware classifiers. In Michael Bailey and Rachel Greenstadt (eds.), 30th USENIX Security Symposium, USENIX Security 2021, August /1-13, 2021, pp. 1487- 1504. USENIX Association, 2021. URL https: /wwww
http://wwwwwww.w.///////w//t www.us.eii.... org/ conference//e/////ooo/oo/oe
(sen1xxscuurrtt2///reeeeeata severi
Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianche and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 6106-6116, 2018 URL httphtttssoo http::::/prooceedinnggggo//////t neurips.eccpcc. Abbtt html
Virat Shejwalkar, Amir Houmansadr, Peter Kairouz, and Daniel Ramage. Back to the drawing board: A critical evaluation of poisoning attacks on federated learning. CoRR, 10s/2100..1221,
2021. httl::ttp//pxiiiiie org/ abs/ 102111111221111
Heung- Yeung Shum, Xiaodong He, and Di Li. From eliza to xiaoice: challenges and opportunities with social chatbots. Frontiers Inf. Technol. Electron. Eng., 19(1):10-26, 2018 doi: 10.1631/
FITEE.1700827 URL/https://dee www.:io.rgr...... 1ttp//11..1.11111 1 ITEE. 1700826
Jason R. Smith. Herve Saint-Amande Magdalena Plamada, Philipp Koehn, Chris Callison-Burre and Adam Lopez. Dirt cheap web-scale parallel text from the common crawl. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, ACL. 2013, 4-9 August 2013, Sofia, Bulgaria, Volume 1: Long Papers, pp. 1374-1383. The Association for Computer Linguisties, 2013. JRL //t::///wwwww wwww ac www.ww..b..... org/ anthology/PP1311111
Joan E. Solsman. Youtube's s ai is the puppet master over most of what you watch. CNET, 2018
15

---

Under review as a conference paper at ICLR 2022
Fnu Suya, Saeed Mahloujifar, Anshuman Suri, David Evans, and Yuan Tian. Model-targeted poi- soning attacks with provable convergence. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 10000-10010. PMLR, 2021. htt.httt://pcceeeeeee/
http//13/////// 39/paa22llaaaaaaaaa httml
Loc Truong, Chace Jones, Brian Hutchinson, Andrew August, Brenda Praggastis, Robert Jasper, Nicole Nichols, and Aaron Tuor. Systematic evaluation of backdoor data poison- ing attacks on image classifiers. In 2020 IEEF/CVF Conference on Computer Vision and Puttern Recognition, CVPR Workshops 2020, Seattle, WA, USA, June 14-19, 2020, pp. 3422- 3431. Computer Vision Foundation IEEE, 2020. doi: 10.1 (WW/C/PWWW0099.... 202000000000000222 URL
thecvf com/ cwom//tntett.../oo CVPRW 20tp/22mm///m227700000
Laannn__@sseeaai___alaaaaa on Image @ivee_Caasan www.saasssssesseeeceeaaaaaaaaaee CVVRW 2020 11220_ppper... html
Leslie G. Valiant. A theory of the learnale.. Commun. ACM, 27(1):1134-114) 1984. doi: 10.
1145/1968. 1972. URL / //doi. wtt.:o...///............
1972
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymplotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019, doi: 10.1017/
9781108627771.
Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. Superglue: A stickier benchmark for general-purpose language understanding systems. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.). Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3261 3275, 2019a. URL httppppss./ppp.cc..gg....ooeoe// hww.....eerppp.. ips. CC pttpppppppppppaaaaepp 7
html
Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding, In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019b. hRLLhttp:://ooo https:://opeeeeeiiiieeeee/ net fotummiidi
JJ4km2
Shurun Wang, Shiqi Wang, Xinfeng Zhang, Shanshe Wang, Siwei Ma, and Wen Gao. Scalable facial image compression with deep feature reconstruction. In 2019 IEEE International Confer- ence on Image Processing, ICIP 2019, Taipei, Taiwan, September 22-25, 2019, pp. 2691-2695 IEEE, 2019c. doi: 10. (0.1109/CCIP.209..coM 8803225.. dol.tttps//d...oo///..... 201 9. 8803255
Yuanyuan Wu, Eric W. T. Ngai, Pengkun Wu, and Chong Wu. Fake online reviews: Literature review, synthesis, and directions for future research. Decis. Support Syst. 132:1 13280, 2020. doi: 1.10016fj.sss.2050 13280. URL
wwt.e//......./...... das 2020. 113280
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant SGD by inner product manipulation. In Amir Globerson and Ricardo Silva (eds.), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 1 115 of Proceedings of Machine Learning Research, pp. 261-270. AUAI html
Press, 2019. URL http: htt.:::pppprrcceddnnge
mlr. wtt..//.wwww.../.eeeeeee/e
Matthew D. Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In David J. Fleet, Tomás Pajdla, Bernt Schiele, and Tinne Tuytelaars (eds.), Computer Vision ECCV
2014 13th European Conference, Zurich, Switzerland, September 12, 2014, Proceedings, Part
I. volume 8689 of Lecture Notes in Computer Science, pp. 818 833. Springer, 2014. doi: 10.1007/ 978-3-319 10590-17 1) 53. URL https: /oii org 53
--00--331111-11 10590-1 --1---3-111---111111111
16

---

Under review as a conference paper at ICLR 2022
Shihao Zhao, Xingjun Ma, Xiang Zheng, James Bailey, Jingjing Chen, and Yu- Jiang. Clean-
label backdoor attacks on video recognition models. In 2020 IEEE/CVF Conference on Computer
Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 14431- doi: 00110999CCP442220000000000000000
14440. Computer Vision Foundation IEEE, 2020.
thecvf. wetom/coneet_tcco CVPR 2020/htt1 Clean - Label Lackeoo Attacks Attacks on Video Recognition
URL httpp:://ppaaaceesseee
2020 paper. html
Chen Zhu, Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on deep neural nets. In Kamalika Chaudhuri and Rus- lan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learn- ing, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7614-7623. PMLR, 2019. URL http::/pproeeeingg.
mlr. mlz.press/v97/ 2ttp9////hhhl...e 9a. html
17

---

Under review as a conference paper at ICLR 2022
Appendices
A CONVEXITY LEMMAS
A.1 GENERAL LEMMAS
Definition 3. We say that f : .Rd - TR. is locally strongly convex if. for any convex compact
C C IR. there exists ps > such that f is p-strrongyy convex on C, Le. for any x, y E C and any
X [0, 1), we have
f(he + (1 (1-))8) S + (1- - A(1 - -
(7)
is well- that if f is differentiable, this condition amounts to saying that [[) - Vf(v))22 2 p. || - for all z, y E C. And if f is twice differentiable, then it amounts to saying f²)(()= žz2 pl for all x E C.
Lemma 6. If is locally strongly convex and g is convex, then f + g is locally strongly convex.
Proof. Indeed, (f + ()x + (1- (1)) - Xf(x) + (1 x)) (111 || - v112 + Ag(x) +
(1 ())(()) A(ʃ (x) +11 ()] + gv( x - A) 1
Definition 4. We say that f: : Rd + R is L-smooth if it is differentiable and if its gradient is L-Lipschitz continuous, i.e. for any I, Rdd
[[V - f(willa S L -
(8)
Lemma 7. If is Ly-smooth and g is smooth,, then f + g is (Lg + Lgy--mmothh
Proof. Indeed, |[V(f + g)(x) - (f + (y)ll I [Vf(()) ff())l2 + [Vg(z) - Vg(v)lla Tyf || vll2 + Tag | vll2 (L, I.g) 1 ull2-
Lemma 8. Suppose that f RRd x Rd' + TR is locally strongly convex and T-smooth, and that, for any x X, where X RRd is a convex compact subset, the map y >> f(x y) has minimum y (I:). Note that local strong convexity guarantees the uniqueness of this minimum. Then, there exists K such that the function y² is K KLLipschitz continuous on X.
Proof. The existence and uniqueness of y" (2: hold by strong convexity. Fix x, x'. By optimality of y", we know that fz y² (x)) = vyf(z', ,z') = O. We then have the following bounds
Mlly" (x) yd (2')l22 - (zf(z,)" vyf(z, = yf (x)
(9)
= g - y
(10)
< xz vf(2',
(11)
- T.
- 1 x',1"(x') - (+'))) = I. || 112
(12)
where we first used the local strong convexity assumption, then the fact that (xf (x))
0,
then the fact that V Vyf(a', y" (x')) = 0, and then the L-smooth assumption.
Lemma 9. Suppose that f Rdd Rd for any x E X, where X C Rdd is a convex compact subset, the map y + f(x, y) has a minimum y (2). Define g(z) mingey f(z v). Then is corvex and differentiable on X and V Vg(x)= = (z
I is locally strongly convex and L-smooth, and that,
Proof. First we prove that y is convex. Let 2e, E Rd, and λ1, A2 E [0, with A + d2 1. For any V1, 3/2 TRdd have
g(Aiz + )222)
= min f()zz + \2 vERd
(13)
< f(A + A2 A131 + )222)
(14)
A v1) + >ef( U2)-
(15)
18

---

Under review as a conference paper at ICLR 2022
Taking the infimum of the right-hand side over y1 and y2 yields g(\121 + x222) )1g(z1) + (22( which proves the convexity of g.
Now denote h(x) V vzf y (z)). We aim to show that Vg(x) = h(x). Let e Rd small enough so that r + E X. Now note that we have
g(x +) = min tx,) S fxxx,,
(16)
yER"
ff + + (=)) (1
(17)
= =g(z) + +="h<())>>>>> + (
(18)
which shows that h(x) is superderivative of g at r. We now show that it is also a subderivative. To do so, first note that its value E approximately the same, i.e.
|1(x + E) - h(2)112 S 1f + E, v +x) - y e))ll2
+ [1V=f(2.0 - yz
(19)
L3
L |||||| (1y (z)1l2 - L+
||
(20)
where we used the L-smoothness of f and Lemma
Now notice that
g(z)
min f(z, 3) S (1..v'( f(( -.y (x + +))
(21)
vER"
f(x E, v. (x+ Vv
o(1|=12)
(22)
= g(x + - h())) -
=" (h(x + 8) h(=)) + + =11)
(23)
But we know that [|[[ 8) - h(x))12 (11=112) Rearranging the terms then yields
g(x + e) 2 g(x) + M(c) o(leell)),
(24)
which shows that hxx) is also subderivative. Therefore, we know that g(x g(x)+++<((aa + o(]]=]1)) which boils down to saying that g is differentiable in x E X, and that Vg(x) = h(x). O
Lemma 10. Suppose that f X x Rd + u-strongly convex, where X C Rdd is closed and convex. Then g X R, defined by g(x) = infyev [xx 1), is well-defined and p-strongly convex too.
Proof. The function y fxx y) is still strongly convex, which means that it is at least equal to a quadratic approximation around 0, which is a function that goes to infinity in all directions as llv|2 0o. This proves that the infimum must be reached within a compact set, which implies the existence of minimum. Thus g is well-defined. Morcover, for any æ1, 22 E X, y1, 322 E Idd and X1, 0 with A + X2 1, we have
g(A101 + )2222) inf (A1 \2 v)
(25)
S f(Arz1 + 1222, A131 + A232)
(26)
1 >1 A1 |[21 - 32, 311 - -2)
< (x1, + (22,
(27)
S Aff(11.11) v1) - (2 (I2, (2)
X1 |æ| - 22112
(28)
2
where used the p-strong convexity of f. Taking the infimum over 3/ y/2 implies the p--tronn convexity of
A.2 APPLICATIONS TO LOss
Now instead of proving our theorems for different cases separately, we make the following assump- tions on the components of the global loss that encompasses both E and smooth-62 regularization, a well as linear regression and logistic regression.
Assumption 1. Assume that é is convex and Le-smooth, and that R(p,0) Rolp 8), where Ro Rd + R is locally strongly convex (i.e. strongly convex on any convex compact set), LRo" smooth and satisfy Ro(=) [[[[=]])) as ||=||| >> cc.
19

---

Under review as a conference paper at ICLR 2022
Lemma 11. Under Assumption 7 Loss is locally strongly convex and L-smooth.
Proof. All terms of LOss are sm-sth,th, for an appropriate value of Lg. By Lemma 7 their sum is thus also L-smooth, for appropriate value of L. Now, given Lemma 6 to prove that Loss is locally strongly convex, it suffices to prove that Σ ||0, 112 Ro(p- 01) is locally strongly convex. Consider any convex compact set C' C Iedx(I++)), Since Ro locally strongly convex, we know that there exists μ 0 such that Ro = pll As a result,
(p. 8) Loss) (p. 0) N V Σ
110.112 - 1 1lp 01112
(29)
nE[N]
= v =
+ 11l1 + / 1101112 - 2pp² 81 +v Σ 10.112
(30)
n
Now define a a² llel22 -2p" (0, (V*LOss) (p:0) (u + 1 (1 a 9) 110 1 + 1 (1 a²) |1e1
2p D422
Clearly, < a < 1. Moreover, 0 < 11 -
aplle = + 101112 +
Therefore 2p 01 S a² ||e| + + |00112. which thus implies
110,112
(31)
nø1
10:112 2/
1/ V + 2/
201
||ll2 + v
10 2 2 min
{ v
201
}
|| 0)
(32)
2
2/
12
which proves that L'LOSS ž kI, with K. > This shows that Loss is locally strongly convex.
Lemma 12. Under Assumption
+ (p. D) is Lipchitz continuous on any compact set.
Proof. Define (n 0.)) _ v 110 + ((On, + A llp 6, l12- If é is L-smooth, then fr is clearly ([Pn) E A)-smooth. Moreover, if l is convex, then for any p. the function On fn (p, 0%) is least v-strongly convex. Thus Lemma applies, which guarantees that p 0 (p. D is Lipchitz.
Lemma 13. Under Assumption convex.
p + (p is L-smooth and locally strongly
the global loss is known be L-smooth, for some value of L and locally strongly convex. Denoting f: p ~> Loss(p, 0¹ (p. D), D), we then have
Proof. By Lemma 11
[V)(()) vf(p')ll < v VpLoss(p (p, D). D) v,Loss(p', (d(.))
(33)
s L (p. 0- (2. D)) - (p) 0 (p'' (0'
(34)
L p 12
(35)
which proves that f is L-smooth.
For strong convexity, note that since the global loss function is locally strongly convex, for any com-
pact convex set C, there exists such that Loss(p, 0, D) is u-strongly convex on C' = (C1, C2) C
(Rd Nxd), therefore, by Lemma 10 f() will also be p-strongly convex on C₁ which means that
f()) is locally strongly convex.
B PROOF OF THE EQUIVALENCE
B. PROOF OF THE REDUCTION FROM MODEL ATTACK TO DATA POISONING
Proof of Lemma ! We omit making the dependence of the optima D explicit, and consider any other models p and 0_.. We have the following inequalities:
Loss,(p", T0.000 DDD = Loss(p", 0-, D) - C(B,, D.) S Loss(p, (0.., C(0,, D.) Loss, 0,,00
(36)
(37)
20

---

Under review as a conference paper at ICLR 2022
where we used the optimality of (p" 8*) in the second line, and where we repeatedly used the fact that 0 This proves that (p", 0²2)) is a global minimum of the modified loss.
B.2 PROOF OF THE REDUCTION FROM DATA POISONING TO MODEL ATTACK
First, we define the following modified loss function:
Loss. (p:00,00000000 . D_ A Loss(p, (0 0-,), (0, (.,D_
(38)
where 8_, and D_, are variables and datasets for users + We then define p" (0 D_.) and 0= (0. D_s) as a minimum of the modified loss function, and (0, DD_)) - 0 We now prove slightly more general version of Lemma 2 which applies to larger class of regularizations. It also shows how to construct the strategic's 's user data poisoning attack.
Lemma 14 (Reduction from data poisoning to model attack). Assume local PAC* learning. Sup- pose also that R. is continuous and that R(p,0) 0) + oc when 1lp 0|12 + co. Consider any datasets D-s and any attack model t such that the modified loss LOSS, has a unique minimum O² 00 D_ O- (0* D=s). Then, for any e, > O, there exists I such that if user s's dataset DD contains least I inputs drawn from model 6% then, with probability at least 1 5, have
p- -000)-0000 10.0 Se and Vn + 8, (x( -0, D_.)) S..
(39)
Clearly, By l2 and smooth-é2 are continuous regularizations, and verify R(p, 0) + oc when 1pp-01 0012 - 0c. Moreover, setting 8 - 1/2 shows that the probability that the dataset D, satis- fies the inequalities of Lemma i4 positive. This implies in particular that there must be a dataset DD that satisfies these inequalities. ALI in all, this shows that Lemma 14 implies Lemma
Proof of Lemma 14 Let 0 and 0 RRd Denote p
p" (0+ D_s) and 0 0 D_.) the result of strategic user s's model attack. We define the compact set C' C'by
C a
{ p. G_
p SEEAAA
00 1l _c
(40)
We define D A RdxN C the closure of the complement of C. Clearly, p* & D. We aim show that, when strategic user s reveals large dataset D, whose answers are provided using the attack model 0 then the same holds for any global minimum of the global loss p
e
C. Note that, to prove this, it suffices prove that the modified loss takes too large values, even when 0 is replaced by 0 (D))
Let us now formalize this. Denote Loss. , 00. (..)).. We define
inf Loss. 00 ,
(41)
P.E_ED
By a similar argument as that of Lemma 5 using the assumption R + oo at infinity, we know that the infimum is actually minimum. Moreover, given that the minimum of the modified loss LOss, is unique, we know that the value of the loss function at this minimum is different from its value at As result, must have 77 > 0.
Now, since the function R is differentiable, it must be continuous. By the Heine-Cantor theorem, it is thus uniformly continuous on all compact sets. Thus, there must exist >> 0 such that, for all models f₂ satisfying | 8 1|2 S K, we have
(((,.p=))
R(B p S n/3.
(42)
Now, Lemma 5 guarantees the existence of I such that, if user s provides dataset D, of least
answers with the model 0 then with probability at least 1 8, we will have |0:(D) 0 <
2
min(K,e). Under this event, we then have
LOSS, (p (
(1()), < L + n/33.
(43)
21

---

Under review as a conference paper at ICLR 2022
Then
inf Loss.((.__,, D-.)
) inf (p. 0, )--)-pp -n/3 (44)
P.B_.DD
L -1 1/n333 L +2/3
(45)
Loss,
(p 03 (D), D
(46)
This shows that there a high probability event under which the minimum of p. 0_ Loss, (p 07 D_s) cannot be reached in D. This is equivalent what the theorem needed to prove states.
B.3 PROOF OF REDUCTION FROM MODEL ATTACK TO GRADIENT ATTACK
In this section, we prove slightly more general result than Lemma 3 Namely, instead of work- ing with specific regularizations, we consider a more general class of regularizations, identified by Assumption T
Lemma 15 (Reduction from model attack to gradient attack), Under Assumption ! g' converges and if Th- = 17 is a constant small enough, then p¹ will converge too. Denote p its limit. Then for
any 0, there is A E Fd such that p - (8 D- SE.
Note that since tg and smooth-22 regularizations satisfy Assumption Lemma 3 We now introduce the key objects of the proof of Lemma 15
Lemma 15 clearly implies
Denote 92ºd the limit of the attack gradients g'.- We now define
(p) e inf (osss(p 0, 2 (.....D)) - R(p, R() +p= p=
(47)
8_,
inf Σ (on, (n) + > (m) nt
+ p" g2 pp0
(48)
and prove that p² will converge to the minimizer of Loss (p). By Lemma (p) is both locally strongly convex and L-smooth.
13 we show that
Now define & A d _. We then know ç and VLOss (o') is the sum of all gradient vectors received from all users assuming the strategic user sends the vector g.t in all iterations. Thus, at iteration & of the optimization algorithm, we will take one step in the direction G A (LOss!(p") + ç, i.e.,
D+ Gr.
(49)
We now prove the following lemma that bounds the difference between the function value in two successive iterations. Lemma 16. (p) is L-smooth and т). S L/L, we have
Loss) - Losss s 2
"t ||o*11 + + Gt.
(50)
Proof. Since Loss. is L-smooth, we have
VLOSs!(pp) + L 1|0 Now plugging et1 p² m and VLOSS! Gi-
(p < (p') + (0
(51)
Ç into the inequality implies
(ptt) Loss!(of) (-no²)² (G* - + + - 1
(52)
s - 11t | +
+ - !.= G*
(53)
where we used the fact f) T/T.
22

---

Under review as a conference paper at ICLR 2022
B.3.1
THE GLOBAL MODEL REMAINS BOUNDED
Lemma 17. There is M such that, for all t, Loss (0') S M.
Proof. Consider the closed ball B(p", 11 centered on p" and of radius 1. By Lemma 13 know that Loss, & is locally strongly convex and thus there exists a jn > 0 such that Loss, is -trsonyy convex on Bip 1). Now consider a point #1 on the boundary of B(p", 1). By strong convexity we have
(LLSs 2 (0r (pi-p")TVLOSS)" (O)S 2 MI Ull p -0'1 MI.
(54)
Now similarly, by the convexity of Loss (P))ss 2 v/1- Now since 5 + 0, there exists an iteration T1 after which (t Tı), we have ||<: I iv/ii and thus |G* l2 2 || (p - ll 2 /Va.. Thus, Lemma 16
Rd, for any P R B(p", 1), have
implies that for 2 Ti, if IIp' pall2 2 1, then
(o - (o') <
|G + ns. T G²
(55)
|| +n ||s/lla ||
(56)
/ ||'lll (1|6'l12 -2
"
(57)
n 3 3 VP -
2
3n
S 4 V/n
4 Vin
S
M1
< 0.
(58)
32
Thus, for l1oe p0112 2 1, the loss cannot increase at the next iteration.
Now consider the case 11p'-p0'l < for t 2 Ti. The smoothness of Loss implies [VLoss < L. Therefore,
|| pp-12 = 110l -11p' n(VLoss + +.- p²
(59)
1
< -1 + (L + 7 ( S 51+ + n + 4 /vM)
-
(60)
Now we define Mi A max maxxpEB(p" (+n(L+) Loss
the maximum function value in the
closed ball B (p", + r I tvrn) Therefore, we have Loss < Mi So far we proved that for & 2 Ti, in each iteration of gradient descent either the function value will not increase or it will be opper-bounded by M1. This implies that for all t, the function value Loss is
by
M A max
max (Loss M (S
(61)
This concludes the proof.
L
Lemma 18. There is a compact set X such that, all f, p² E X.
Proof. Now since Loss! is ft-strongly convex in B(p", for any point p e Rd such that lpp - p'll2 = 1, we have
Loss 2 (o's + M1 1 = Loss! (p") + M1
(62)
2
But now by the convexity of Loss! in Idd, for any P such that 11p - p²1l2 2 1, have
(p) > (o") + 11pp- - p 112 HI
(63)
2
This implies that 1|p² - p²112 > 2 (M₂ - Loss )) then Loss > M2. Therefore, we must have ||p' p0ll2 < 2 (M₂ (p")) for all 2 0. This describes closed ball, which is compact set.
23

---

Under review as a conference paper at ICLR 2022
B.3.2 CONVERGENCE THE GLOBAL MODEL UNDER CONVERGING GRADIENT ATTACK
Lemma 19. Suppose it 2 0 verifies 44+1 I au4 + 8G, with ót - Then ut O.
Proof. We now show that for any > O, there exists an iteration T(s), such that for 2 T(s), we have ue For this, note that by induction, we observe that, for all & 0,
ut+1 S uga ++ Σ d
(64)
==0
Since 6; - O, there exists an iteration T2(E) such that for all 2 T2(2), we have 8 v e(1-a)
2
Therefore, for t (2) we have
t- (c(e))
Ue+1 uoa 1+1
Σ a
Σ a
d
(65)
==0
r=t-Ta(E)+1
Tc))
Ta(6)-1
5(1
S uga +1
α
(66)
T=0
8=0
Ta(e)-1
s(1
Un +
Σ
1-8-88
c+1 +
a²
(67)
2
Denoting Mo(s) 2 2200 a x- 18. we then have
(1())-
u+11 S (no + Mo(E)) 1+1 + E a
(68)
2
Therefore, for 1 2 Mooo+Mo(t)
we have
In
U++1 S
(69)
2
This proves that de + O.
We first prove the first part of Lemma 3
Lemma 20, Under Assumption
7 and 17: = 17 S 1/L, g. converges, then so does p².
Since Loss is locally strongly convex, there exists μl such that Loss is p2-strongly convex in a convex compact set X containing o for all 0. By the strong convexity of (p), we have
Proof. Define X based on Lemma 18
- Loss s pp)) (p'ss
H2 ||l' p" 11
(70)
= =(p² 1 p²)= (G' -t)
112 1| p" $12
(71)
2
Now, using the fact
1
G''
(p' (T)=(p' - 1111)
(72)
1
1
(10' p²16 112 11ee 11 11 - p=112)
-p11-
(73)
2n
1
172
| 1| + Ilo' = - || -1|=0l 0² -²112)
(74)
2n
11
G
12+
(ll² p" 11 || م 10113)
(75)
2
2n
24

---

Under review as a conference paper at ICLR 2022
have
(0's - (0') 5
(76)
" 1 2n
(0' 1 (Il0* - -p=12 -1-11) - p²)
02133)
122
2 1 p 11.
(77)
But now note that (pt) (LOSsSs)) 2 (o's ( ( Thus, combining Equation and Lemma 16 yields
7C G S 27
(lo''-0'))
0011) -11 -1104t1-001 -pp' -:-)"
P2
l1ee
p= p=
(78)
2
2
By rearranging the terms, we then have
| - 1²112 = (1 - (277 |1p' - p011 - 17 -p"t1-p""" 52
(79)
1 (1 - 127) |10 - p= 112 + 1) 1100 -p" -2"112116:11
(80)
Now note that < 1/L- < 1/ U2 and thus 0 < - 1297 < 1. We now define two sequences
Ur A llp' p²ll p'll2 and 6e n 1 112- We already know that og + 0, and we want to show us also
converges to By Equation (80). we have
nhtu (1 - m22 + deu++1,
(81)
which implies
81
82 S (1 mu2)ut +
Ut41
u u141d
(82)
2
4
and thus
Ue+1 S V (1 ) +
87
8 2
S
(1
11/2
)3
8 +
6 < (1
77/2
Ut + 8c.
(83)
4
2 2
2
Lemma 19allows to conclude.
B.3.3 REDUCTION FROM MODEL ATTACK TO CONVERGING GRADIENT ATTACK
Proof of Lemma 15 Lemma
20 already provided the convergence part of Lemma 3 We now move
forward to proving the second part of the theorem, showing that for any > O, there exists 8 E Rd
such that
p000
p" ( D_.)
2 S c. We define
C.,,,, Loss (p.0e) 0.) e inf 0, - - Dz)
(84)
0_.
Loss (p) + R(p, 0.) p= 9,00
(85)
and p² its minimizer. Therefore, we have
(p vpLoss V Rpp(pp 0.) -06
(86)
By Lemma we know that Loss is locally strongly convex. Therefore, there exists μs > 0 such
that Loss? (p) is pa-strongly convex in {el [|p p² (0.)ll2 S 1). Therefore, for any 0 1, if
Ilpe0 p² (0.)ll > E, we then have
Lo lll 2 (0x0 p² (0.)) VV LOss 0,0))
(87)
2 ns 11 (0.) 12 = p3 2 2
(88)
and thus V 0 1|1 2 Mye.
Now since o.dh E GRAD(O there exists t E Rd such that Rp (000) 92 l1, S
M38
2
which yields
V Loss 0 1|2 V LOSS! ( 0
9: 1l2
(89)
V , 0:0111 S
M388
(00)
2
which is a contradiction. Therefore, we must have 1000 p² (0 D
S e.
In fact, if d.d belongs the interior of GRAD(P we can guarantee
V
0 = 9.
25

---

Under review as a conference paper at ICLR 2022
C SUM OVER EXPECTATIONS
In this section, we provide both theoretical and empirical results to argue for using sum-based local loss over an expectation-bes based local loss.
C.I THEORETICAL ARGUMENTS
Indeed, intuitively, if one considers expectation BgwD, [E(O,. x]] rather than sum, as is done by Hanzely et al. 2020). Dinh et al. (2020) and El-Mhamdi et al. (021), then the weight of an honest active user's local loss will not increase as node provides more and more data, which will hinder the ability of 8, to fit the user's local data. In fact, intuitively, using an expectation wrongly yields the same influence to any two nodes, even when one (honest) node provides much larger dataset Dr than the other, and should thus intuitively be regarded as "more reliable".
There is another theoretical argument for using the sum rather than the expectation. Namely, if the loss is regarded as Bayesian negative log pog-posterior, given a prior exp (-EnE(N) v 1|0nl22 - EnE(N) R(p, 0n)) on the local and global models, then term that fits local data should equal the negative log likelihood of the data, given the models (p. 0). Assum- ing that the distribution of each data point x E 'D, is independent from all other data points, and depends only on the local model On, this negative log-likelihood yields an expectation.
data points;
C.2 EMPIRICAL RESULTS
We also empirically compared the performances of as opposed to the expectation. To do so, constructed a setting where 10 "idle" users draw randomly 10 data points from the FashionMNIST dataset, while one "active" user has all of the FaSHionMNIST dataset (60,000 data points). We then learned local and global models, with R(p, 8) & > llp 0| different classifiers to which we refer as a "linear model" and "2-layers neural network", both using CrossEntropy loss. The linear model has 1784+1) 10 parameters. The neural network has 2 layers of 784 parameters with bias, with ReLU activation in between, adding up to ((784 + 1) x 784 + (784 + 1) x 10.
We compared two
Note also that, in all our experiments, we did not consider any local regularization, i.c. we set v P 0. All our experiments seeded with seed 999.
C.2.1 NOISY FASHIONMNIST
To see strong difference between sum and average, we made the FashionMNIST dataset harder learn, by randomly labeling 60% of the training set. Table reports the accuracy of local and global models in the different settings. Our results clearly and robustly indicate that the use of sums outperforms the use of expectations.
EL
ΣL
ENN
ΣNN
idle user's model
0.52
0.80
0.55
0.79
active user's model
0.58
0.80
0.56
0.79
global model
0.55
0.80
0.58
0.79
Table 1: Accuracy of trained models, depending on the use of expectation (denoted E) or sum (E), and on the use of linear classifier (L) or a 2-layer neural net (NN). Here, all users honest and an & regularization used, but there is a large heterogeneity in the amount of data per user.
On each of the following plots, we display the top-1 accuracy on the MNIST test dataset (10 000 images) for the active user, for the global model and for one of the idle users (in Table [ the mean accuracy for idle users is reported). as we vary the value of Intuitively, À models how much we want the local models to be similar.
26

---

Under review as a conference paper at ICLR 2022
In the case of learning FashionMNNIST, given that the data is ii.d., larger values of X more meaningful (though our experiments show that they may hinder convergence speed). However, in settings where users have different data distributions, e.g. because the labels depend on users' preferences, then smaller values of À may be more relevant.
Note that the use of common value of À in both cases is slightly misleading, using the intuitively decreases the comparative weight of the regularization term. To reduce this effect, for this experiment only, divide the local losses by the average of the number of data points per node for the sum version. This way, if the number of points is equal for all nodes, the two losses will be exactly the same. What's more, our experiments seem robustly show that using the sum consistently outperforms the expectation, for both linear classifier and 2-layer neural network, for the problem of noisy FNSHionMNIST classification.
1.0
1.-
0.8
0.9
0.2
3CC 3g
0.2
acc big
small
acC_slob
acc_glob
0.0
0.0
Epochs
Epochs
Using the average
(b) Using the
Figure 4: Linear model on noisy FashionMNIST, for 0.01.
acr_te
scc.mal
arc_5mall
0.8
glob
0.8
gleb
ACCURICy
0.6
2.6
0.0
0.0
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Epochs
Epechs
(a) Using the average
(b) Using sum
Figure 5: 2-layer neural network noisy FashionMNIST, for 0.01.
27

---

Under review as a conference paper at ICLR 2022
1.0
1.0
SCC 2ig
big
small
Aco/nxy
0.4
0.4
0.2
0.2
100
125
100
125
150
175
200
(a) Using the average
(b) Using the sum
Figure 6: Linear model on noisy FashionMNIST, for 0.1.
1.0
1.0
14g
big
acc_smal
acc_5mall
Accurics
0.6
0.6
0.4
0.2
25
50
75
100
125
150
175
200
25
75
100
125
150
175
200
Epochs
Epochs
(a) Using the average
(b) Using the sum
Figure 7: 2-layer neural network on noisy FashionMNIST, for À 0.1.
3CC_ smal
arc_5mall
0.8
glob
0.8
glob
ACCUMIT
0.6
0.6
0.0
0.0
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Epochs
Epachs
(a) Using the average
(b) Using sum
Figure 8: Linear model noisy FashionMNIST, for 1.
28

---

Under review as a conference paper at ICLR 2022
1.0
1.0
3CC 2ig
aic
small
Aco.
0.4
0.4
0.2
0.2
100
125
150
100
125
150
175
200
(a) Using the average
(b) Using the sum
Figure 9: 2-layer neural network on noisy FashionMNIST, for 1.
1.0
1.0
aCC 14g
acc big
acc_smal
act_smal
Accuric
0.6
0.6
0.4
0.2
25
50
75
100
125
150
175
200
25
75
100
125
150
175
200
Epochs
Epochs
(a) Using the average
(b) Using the sum
Figure 10: Linear model on noisy FashionMNIST, for 10.
bcgbig
3CC_ smal
sct_
0.8
glob
0.8
acc glob
AccUmO
0.6
2.8
0.0
0.0
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Epochs
Epechs
(a) Using the average
(b) Using sum
Figure 11: 2-layer neural network noisy FashionMNIST, for À 10.
29

---

Under review as a conference paper at ICLR 2022
1.0
1.0
SCC 2ig
SCC big smal
scc_glo
acc_glob
Aco/wey
ACo.rscy
0.4
0.4
0.2
0.2
100
125
100
150
175
200
(a) Using the average
(b) Using the
Figure 12: Linear model on noisy FashionMNIST, for = 100.
acc big
acc. small
acc small
acc_glob
Accrne
0.6
0.6
0.4
0.4
0.0
25
50
75
100 Epochs
125
150
175
200
25
75
100
125
150
175
200
Epochs
(a) Using the average
(b) Using the sum
Figure 13: 2-layer neural network on noisy FashionMNIST, for 100.
C.2.2 FASHIONMNIST WITHOUT NOISE
Recall that we introduced noise into MaSHionMNIST to make the problem harder to learn and ob- serve a clear difference between the average and the sum. In this section, we present results of our experiments when the noise is removed.
SCC_ smal
0.8
glob
0.8
ACCUMO
0.6
0.6
sct_smal
acc glob
0.0
0.0
200
400
600
800
1000
200
400
600
800
1000
Epochs
Epachs
(a) Using the average
(b) Using sum
Figure 14: Linear model FashionMNIST (without noise), for À 1.
30

---

Under review as a conference paper at ICLR 2022
1.0
1.0
SCC Dgg
smal
scc_glob
Aco/ney
0.4
0.4
0.2
0.2
3CC big
acc smal
1000
1250
1500
1750
1250
1500
1750
2000
(a) Using the average
(b) Using the sum
Figure 15: 2-layer neural network on FashionMNIST (without noise), for 1.
Even without noise, the difference between using the and using the expectation still seems important. We acknowledge, however, that the plots suggest that even though we ran this experiment for 10 times more (and 5 times more for the linear model) than other experiments, we might not have reached convergence yet, and that the use of the expectation might still eventually gets closer to the case of sum. We believe that the fact that the difference between sum and expectation the absence of noise is weak is due to the fact that the FashionMNIST dataset is sufficiently linearly separable. Thus, we achieve near-zero loss in both cases, which make the sum and the expectation close at optimum.
Even in this case, however, we observed that the sum clearly outperforms the expectation especially, in the first epochs. We argue that the reason for this is the following. By taking the average in local losses, the weights of the data of idle nodes are essentially blown out proportion. As a result, the optimizer will very quickly fit these data. However, the signal from the data of the active node will then be too weak, so that the optimizer has to first almost perfectly fit the idle nodes' data before catch the signal of the active node's 's data and hence the average achieves weaker convergence performances than the sum.
D LINEAR REGRESSION AND CLASSIFICATION ARE GRADIENT PAC*
Throughout this section, the following terminology.
Definition 5. Consider parameterized event E(I). We say that the event & occurs with high probability iP [E(I) + as - cc.
D. PRELIMINARIES
Define |E||, mal (I / / (|=]|]) the & operator norm of the matrix E. For symmetric matrices E. this also the largest eigenvalue in absolute value.
Theorem (Covariance concentration, Theorem 6.5 in Wainwright (2019).. Denote Σ OT where Q, E Rd from oo--su--Gause Gaussian random distribution Q. Then, there are universal constants C₁2 C2 and C3 such that, for any set (Qihiem of i...d. samples from ②, and any
8 > 0, the sample covariance = E O. satisfies the bound
1/d d
P
Σ
2 Ci
(
+
S c2 exp (-cgI moci6m
(91)
I
Theorem (Weyl's Theorem, Theorem 4.3.1 in Horn & Johnson 2012 ). Let A and B be Hermi-
tian and let the respective eigenvalues of and B and A be (A)A) (N,B)) and
Forr real matrices, Hermitian is the same as symmetric.
31

---

Under review as a conference paper at ICLR 2022
(A+(A B) each increasingly ordered. Then
A1 + B) S (A) + Aa- Aa-;(B), j= 0, 0,1,,.., ......-
(92)
and
(4+5(A) (B) S A B), j j= j=0,..,
(93)
for each -,....d d.
Lemma 21. Consider two symmetric definite positive matrices S and E. Denote Pmin and Amin their minimal eigenvalues. Then [Pmin >minn S || El12
Proof. This is direct consequence of Theorem 7 for A - S. B S, and j 0.
Corollary 1. There are universal constants Cı, C2 and e3 such that, for any Gaussian vector distribution 2 E Rd and any > O, the sample covariance E + satisfies the bound
min SP(E.) min min SP(E)) 2 ci (Vz
d
P 2
8 S exp (-c3Imin(,,88) (94)
where min SP(E) and min SP(E) are the minimal eigenvalues of E and E.
Proof. This follows from Theorem 6 and Lemma 21
Lemma 22. With high probability, min SP(..) 2 min Sp(F))/2
Proof. Denote Amin min SP(E) and Xyain A min SP(E). Since each Q₂ is drawn ii.d. from Namely, there are constants c₁, 02 and cz, such that for
a co-sub-Gaassiin we can apply Corollary [ any 8 > O, we have
(V d d
P [imin Amin 2 2002
do S 02 exp e-p min (6.62))
(95)
I
We now set A \min/(407) and we consider large enough so that e ( + S
Amia/ (402))(4)))) With high probability, we then have Amin 2 Amin/ /2.
D.2 LINEAR REGRESSION IS GRADIENT-PAC*
In this section, we prove the first part of Lemma gradient-PAC* learning.
Namely, we prove that linear regression is
D.2.1 LEMMAS FOR LINEAR REGRESSION
Before moving to the main proof that linear regression is gradient-PAre PAC* first prove few useful lemmas. These lemmas will rest on the following well-known theorems.
Theorem (Lemma 2.7.7 in Vershynin 2018 If X and are sub- Gaussiansnn then XY is sub- exponential.
Theorem (Equation 2.18 in Wainwright (2019). I are iid sub-exponential variables, then there exist constants c4. Cs such that, for all I. we have
E c0. P - E [X] t
< exxp (-ogIt²).
(96)
Lemma 23. For all j E [d]. the random variables X; zero mean.
E.1. are iid, sub- sabbexxooential and have
Proof. The fact that these variables are iid follows straightforwardly from the fact that the noises & are iid, and the queries Q₂ are also iid. Moreover, both are sub-Gaussian, and by Theorem g the product of sub-Guu sub-Gaussian variables is aub-exponential. Finally, we have E [X] E @il
[g] [Q[]] = 0, using the independence of the noise and the query, and the fact that noises have
zero mean (E [ 0).
32

---

Under review as a conference paper at ICLR 2022
Lemma 24. There exists B such that |EEEz E RiRil1 I BI3/4 with high probability.
Proof. By Lemma 23 the terms &, 111 are iid, sub-exponential and have zero mean. Therefore, by
Theorem 9 there exist constants сд and cs such that for any coordinate [d]] of Q,Q, and for all
S u S C1. we have
P
Σ iEZ
cQDI
2 Iu
S 2 exxp (-ezTu²).
(97)
Plugging cI(4) into the inequality for some small enough constant and using union bound then yields
P
Σ s. IET
I3//
SP
Σ Go.
7(3/2/
S (-exp(-evV (98)
RET
00
Defining B a v yields the lemma.
D.2.2 PROOF THAT LINEAR REGRESSION IS GRADIENT-PAC*
We now move on to proving that least square linear regression gradient-PAC*.
Proof of Theorem Note that Vol (0 A)Q. Thus, input i [Z], have
Vol(o, Q., A(2,))))))) ( Q.) Q -Q.
(99)
Moreover, we have
(0 (0-0'""V (111012) -2v(0 - 2 = 20110 0111 2v(0 -1)
(100)
As result, we have
(0 (0-0))VoC(()
(101)
I(e - O - 01) - -00 -0- 0i)T
Σ S. VET
+ 2v 22/10- --1122 2v aty
(102)
But now, with high probability, we have (0-0t) (0-0t)-T(0-0))) 0t) 2 (Amin 22) |10 at (Lemma 22 and EEizz 2i S BI(3/1) (Lemmaa 24 Using the fact that ||0t||, S K. and the Cauchy-Schward inequality, we have
- (o) 2
Amin I I+
0111 (BI(3/4) + 2v/C) l|0 01 8'112-
(103)
2
Denoting Ak A Amia and Bx B 2vK and using the fact that I > 1, we then have
0 (0-0)) D) > AxT 0 01 Bx I(34) |10 1101-1112
(104)
Ax min { {110- 0'112 110 -0'11²] (3/44 110 0il12-
(105)
with high probability. This corresponds to saying Assumption 2 is satisfied for a 3/4.
D.3 LOGISTIC REGRESSION
In this section, we now prove the second part of Lemma gradient-PACC learning.
Namely, we prove that logistic regression
33

---

Under review as a conference paper at ICLR 2022
D.3.1 LEMMAS ABOUT THE SIGMOID FUNCTION
We first prove two useful lemmas about the following logistic distance function.
Definition 6. We define the logistic distance function by aa, b) - (a - b) (a(a)-o - (b)).
Lemma 25. If a. b E IR such that for some k > 0, |a| I and [b = k, then there exists some
constant C O such that
(aa 2 Ck a b|
(106)
Proof. Note that the derivative of (z) is strictly positive, symmetric (o'(2) = -=((=)) and mono- tonically decreasing for 2 2 0. Therefore, for any 2 [-k; kt), we know d'(2) 2 C₁ - ok:).. Thus, by the mean value theorem, we have
(a) (b)
Ck.
(107)
b
Multiplying both sides by (a- b)2 then yields the lemma.
Lemma 26. b E IR, and (6| S k. some > O, then there exists a constant dy, such that for any E I, we have
A(a, b) 2 dg a - bl - dz
(108)
Proof. Assume Ja bl 2 and define da _ (k: + 1) -kk). If b 2 O, since d()) is decreasing alb + 1) o(b) de. and by symmetry, a similar argument
for z 2 0, we have (b)) abb-l) 1)
holds for b S 0. Thus, we have
(o(a) - (b)l 2 min (o(b) o(b - 1), + 1) -obb) 2 dR.
(109)
Therefore,
(a - b) (o - ob)) 2 du la - b/2 dx la 61 - dd.
(110)
For the case of la- - bl S 1, we also have (a b) (a(a) ab)) 2 0 N dx la - bl - dx.
D.3.2 A UNIFORM LOWER BOUND
Definition 7. Denote gd-1 A {u E Fdd ||u||== 1} the hypersphere in Rd.
Lemma 27. Assume SUPP(() spans Rd, Then, for all u E &dd-1, E I @ > 0.
Proof. Let E Sd-1 We know that there exists 2 21,..., Qa E SUPP(() and aj...., O.d R such that u is colinear with Σaz 2j. In particular, we then have u² Σ 2, = Σ (0 # Therefore, there must be query Q. E SUPP( ②) such that e u # O. which implies a - LTul O By continuity of the scalar product, there must then also exist & > 0 such that, for any Q E B(Q.,E), we have | u 2 a/2, where B(Q.,e) is an Euclidean ball centered on Q. and of radius
But now, by definition of the support, we know that p e p E B(Q..))) > 0. By the law of total expectation, we then have
E 51 E
[1 ul| | Q e| PI B(2.,
+ + e q0'llle Q & B(Q.. PlQ & B(Q..))
(111)
M 0p/2+0>0,
(112)
which is the lemma.
Lemma 28, Assume that for all unit vectors u E gd-1, we have E @ > 0, and that SUPP Q) bounded by Mo. Then there exists C such that, with high probability,
Vu E S0-1
Σ OT CZ.
CT.
(113)
34

---

Under review as a conference paper at ICLR 2022
Proof. By continuity of the scalar product and the expectation operator, and by compactness of gd-1, we know that
C - inf E 1 u| > 0.
(114)
uerd
Now define - Co/4M Note that s0-1 c U Uuega- e(, Thus have covering of the hypersphere by open sets. But since g compact, we know that we can extract a finite covering. In other words, there exists finite subset S C gd-1 such that Sd-1 c Uues B(u,s). Put
differently, for any g there exists u E 5 such that ||u vll2 S..
Now consider u E S. Given that SUPP( 2) is bounded, we know that 12" u E [0, Me]. Moreover,
such variables O u are iid. By Hoeffding's 's inequality, for any / > 0, we have
2I1
P
O u
IE O uI] 2 I1 S exxp
(115)
M
iEZ
Choosing t = Co/2 then yields
CoI
ICo
P
o
u
P
of Ug ot
- IE
up-0
un
2
(116)
2
LET
iET
-IC'²
S 2 exp
(117)
2M
Taking a union bound for u E S then guarantees
CoI
-ICo2
P VuES,
o
u
2 1 2|5| exp
(118)
2
2M
EEI
which clearly goes to 1 as I Thus Yu S, ΣiEr o
C. holds with high probability.
Now consider
gd-1 We know that there exists
S such that ||u vll2 S s. Then, have
Σ
o v
Σ
Q u + of (v u)l
(119)
iE
>
Σ
O u
IMe ||v u/l2
(120)
COI
Co
CoI
IMM
(121)
2
4Mc
4
which proves the lemma.
L
D.3.3 LOWER BOUND ON THE DISCREPANCY BETWEEN PREFERRED AND REPORTED ANSWERS
Lemma 29, Assume that Q has bounded support, whose interior contains the origin. Suppose also that ||0||| S K. Then there exists Ax such that, with high probability, we have
Esidfo oftt 2 AcI min {llo 11 - 11
(122)
Proof. Note that by Schwarz inequality we have | ot| < ||Qill 10t S MaK.
(123)
Thus, Lemma 26 implies the existence of a positive constant dx, such that for all 0 E Rd, we have
Σ rt > Σ
(dk O e. 0t - dc))
(124)
IET
iEI
= Ix + dx 110 011122 Σ
o up up-orl
(125)
1ET
35

---

Under review as a conference paper at ICLR 2022
where ot _ (0 (8-00) / ||0 10t1l1 is the unit vector in the direction of 8 ft.
Now, by Lemma 28 we know that, with high probability, for all unit vectors E s we have CT. Thus, for I sufficiently large, for any A E R with high probability, we have
Σ o u
dx dxCmin I
E 0 2 RET
0"| dxI.
(126)
Defining 6x A deCmin and JK
Cmin - for 100 0t Sk. then have
Σ EE
A 0 2 exI A 1
(127)
We now focus on the case of l|0 10110-0'1,, S fx. The triangle inequality yields ||0||2 S 1:0-00111 + |0'11 fi + K. By Cauchy-Schwarz inequality, we then have Q 0| (fic + M _ gk and
0f & KMo S gx. Thus, by Lemma 25
we know there exists some constant ex: such that
Σ (0 - - (2 0,0 2
Σ xx
(128)
i67
Σ
xx(0 01)² -000 2.0
01)
(129)
IEI
(x Qt1J
Σ 2.o (0 (0-01).
0t).
(130)
Since distribution Q is bounded (and thus sub-Gaussian), by Theorem with high probability, we have
(0 - 0t) Σ "OO0 (0 -0-00 -0- 2 Amin I 1
(131)
VET
where Aman is the smallest eigenvalue of EE [ Thus, for 110 110-0111 0011/ S SK. we have
Σ
(Q ot Amin
00
(132)
2
Combining this with (17), and defining Ax A min ( (Amiee ex we then obtain the lemma.
D.3.4 PROOF THAT LOGISTIC REGRESSION IS GRADIENT-PAC*
Now proceed with the proof that logistic regression is gradient-PAC*,
Proof of Theorem
Note that o = -
= 1- (z) and (())= = =x)))(x) We then have
(AA -A0 (A
- o(AQT0)
(133)
=-o(-A0"0)AQ = -000040=0000000) 1[== e
(134)
36

---

Under review as a conference paper at ICLR 2022
where 1 [A = 1] is the indicator function that outputs 1 if A 1, and 0 otherwise. As result,
(0 - ) (oL(0,
(135)
(0 (0- 00-0-)
Σ
(0(0 IA, = 11) =1)) 2. + +2(
(136)
VET
= -0- 01)
Σ (o(2 -(2 - 000 1 1]) 2.
(137)
+ 2v 110 11 + 2v(0 0f
(138)
Σ A (2 0, 2 + (0 - -01T
(o( - (A, = 2,
(139)
VEI
+ 2v 000 01 1|- 2v(0- T
(140)
By Lemma 29 with high probability, we have
Σ A 0, 0, 2
> AxImin {11o 0 11 -
0116)
(141)
To control the second term of 139 note that the random vectors Z; (o - [A, =14 2 iid with norm at most Me. Moreover, since E [1 [A, 1]] a ( ft). by the tower rule,
we have E [2:] = E [E| [ [ = O. Therefore, by applying Hoeffding 's bound to every coordinate
of Z. and then taking a union bound, for any B >> have
BI
P
Σ
2 iEI
2 BT3/1
S 2d exp
(142)
2dM3
Applying now Cauchy-Schwars Schwarz inequality, with high probability, we have
00 - 01) 01)z
(o( - 1 [A: = 11) 2, S BT 11001110000 0'112-
Combining this with 132) and using |0r|| K. we then have
(0 oty ( VoL(O,
(143)
2 (AKI v) { {11000000 0 0111 |10 00 [12] (BI(3/4) + + ||0 11112
(144)
2 AxI 110 0 112-110
e1
[12]]
Bx/(3/4) 110 81 81l12.
(145)
where Bx = B + 2vK.. This shows that Assumption Ax and Bx as previously defined.
2 is satisfied for logistic loss for a = 3/4, and
E PROOFS OF LOCAL PAC* -ECC-LLAAABBILITY
Let us now prove Lemma To do so, consider the preferred models 0 and subset H C [N] of honest users. Denote D_ the datasets provided by users E [N] H. Each honest user h H provides an honest dataset D), of cardinality at least I 1. Consider the bound K A on the parameter norm of honest active users h E H.
maxseH [0%]
E. BOUNDS ON THE OPTIMA
Before proving the theorem, we prove a useful lemma that bounds the set of possible values for the global model and honest local models.
37

---

Under review as a conference paper at ICLR 2022
Lemma 30. Assume that R and are nonnegative. For I large enough, if all honest active nodes h E H provide at least I data, then, with high probability, 64 must lie in compact subset of TR H that does not depend on I.
Proof. Denote L & Loss(o, (0.. 0-H), (0, Essentially, we will show that, if 0z is too far from Oz then the loss will take values strictly larger than L
Assumption
2 implies the existence of event & that occurs with probability at least Po -
P(K I) under which, for any 02 E IR, we have
T vhn (0n) 2 AK I Imin {11e, - 0%l13 11. -0-60 0/13]]
0 - 6% 0%11. (146)
BKy
which implies
T (6, (.)
Vn (0n) 2 A I min {I, 00. 08 0/ BKgI"
(147)
Note also that Po - 1 as I > cc. We now integrate both sides over the line segment from o). to 0,
The fundamental theorem of calculus for line integrals then yields
Ln (0h) = 1100 0/11
1- u(o. -0))o)) VL (oh + 110n ((0n-0%) 0%)) di
La (0%)
(148)
==0
0/
0% 11 2
1." (AknImin {1,2) On 1o%1-%) [b/1p} BK, )at.
1
(149)
0n 0%
(AkzI ( 1, (1.0|0n - 0/ di BK Ia 1100 -000 0%
(150)
1=
On 8% |
Now, if
2, then have
Ln (6h. Li (0%) 2 AknI I
|0hh - -82111
BBR In
(151)
2
2 AK I 2Bx
(152)
Now for I > Ii max 22k/AKu (4BKa/ (AKa) 1-m
) } we have
Ln (6%) - Ln (0%) > L.
(153)
This implies that if 00. 0%11 > 2 for any H, then we have
Loss(O, (0t, D) < Loss(p, (FH, 0-),
(154)
regardless of p and H. Therefore, we must have |0% - 07 S 2. Such inequalities describe bounded closed subset of Rdx H which is thus compact.
Lemma 31. Assume that R(p, 8) + do as ||p 0112 + oo, and that |10% 07 S 2 for all honest users & E H. Then p² must lie in a compact subset of RRdd that does not depend on I.
Proof. Consider an honest user h², Given our assumption on R + cc, we know that there exists
Dru such that if [|p - 0% ||2 2 Dr... then R(p, 07,) 2 67 + 1. Thus any global optimum p² must
satisfy |00 0f | 5 -1p= - 0% 212 + |0 0f
0%| ||
< D Kg +2.
38

---

Under review as a conference paper at ICLR 2022
E.2 PROOF OF LEMMA 5
Proof of Lemma that will guarantee (e, 8)-ooclll PAC* learning for honest users.
Fix E, > O. We want to show the existence of some value of Z(e, D 01)
By lemmas and 31 we know that the set C' of possible values for (0", 01) is compact. Now, we define
EKg
max (A,0)C
(155)
the maximum of the norm of achievable gradients the optimum. We know this maximum exists since C compact.
Using the optimality of (p", )²), for all E H. we have
E (0% 0f " Vo, Loss(p", 07) (0% VL)) + (0) (V.)²vo. R(p", ,0%
(156)
(157)
2 (0% VL) 10% 0:|12 Vo, R(p" 1l1
(158)
CN (0%) ER 10% 0%
2 (0%
(159)
We now apply assumption 2 for 0 = 0% (for h E H). Thus, there exists some other event El with probability least Po. under which, for all H. we have
2 Ak Imin min (105 - 07 1 [/]²]
- BKy I 0% - 0%111 EK* 100 0% (160)
Now if I Ie max 22KK AAKH (2B |AKx) 1 this inequality cannot hold for 0% 0% ||, > 1. Therefore, for I > Iz. we have
|0% 0%
and thus,
z AK 07 0/11
18 0%11
EKи 08% - 1oh--%//
BKn Ia
(161)
and thus,
10% 0/11_ 5 BR Ia + F.H
(162)
Akg I
Now note that P -1 -8- 2 1 - P [1=] - TP [P -P 1. now suffices
to consider larger than Zz and large enough so that P(KN, 1T,,,i 1 2 -8/2 (whose existence is guaranteed by Assumption and which guarantees 2P. to obtain the theorem.
1-5) and so that Bx I' ER
<
AxR I
F CONVERGENCE OF CGA AGAINST l
To write our proof, we define Loss IRd H8 by
Loss A inf Loss -)
Lo,, - RR(p,a)) 0,)
(163)
inf Σ L(On. D.)) + Σ 11 0n
(164)
In other words, it is the loss when local models are optimized, and when the data of strategic user are removed.
Lemma 32. Assuming Bs regularization and convex loss-per-input functions for any datasets D, Loss is strongly convex. As a result, so is Loss"..
Proof. Note that the global loss can be written as a sum of convex function, and of Σ 1100,11 + |lp - 8, 112. Using tricks similar to the proof of Lemma 11 we see that the loss is strongly convex. The latter part of the lemma is then straightforward application of Lemma T0
39

---

Under review as a conference paper at ICLR 2022
We to the proof of Theorem Note that statement of the proof not fully explicit, especially about the upper bound on the constant learning rate 17. Here, we prove that holds for 7/ = 1/3L, where L is constant such that Loss", is L-smooth. The existence of L guaranteed by Lemma T3
Proof of Theorem 4 Note that by Lemma Loss is convex, differentiable and L-smooth, and - For &g regularization, have GRAD(P) Ra for all p E I Then the
VLOss",
minimum of equation 6 is zero, which is obtained when 9 p'-0!
" - 9-_ 9 + p'
Note that
p²+l p²
119 1.3 ngs p'
(165)
119 1tt (0' - -8) + (p' -p') - 19.2
(166)
0
( (g + 92 1-11 + n1 71-1 9 9
(167)
0. (gg g= 1.111)..
(168)
Therefore, p²+1 p² = g n(ghi111 g
Then, using the L-smoothness Loss and denoting un - -|| -
-p' -/112. we have u++1 S (we + 1-1)). We then know that
LTp4 + 14--14-11. Now assume that S 1/3L. Then u++1 Uc-2 S ((1++1 un) s ( u1-1) + wn) f w
Now define 2t - ue + u1-1- We then have u++2 S u142 + u++1 S Juu + Ju-- (uu + up-1) I J.u. By induction, we know that i I (7/9) max foo. v1] S (V7/3)/ ((V7/3) max v1)). Thus, defining
V7/3 1, there exists C > such that Wr S Ve S Ca This implies that Σ Elpp't p²112 S Ca < oo. Thus E - p²) con- verges, which implies the convergence of p² to a limit p²) By L-smoothness, we know that وااو must converge too. Taking equation 168 to the limit then implies p 0¹. This shows that the strategic user achieves precisely what they want with CGA. is thus optimal.
G CGA ON MNIST
In this section, CGA is executed against 10 honest users, each one having 6,000 randomly and data points of MNIST, drawn randomly and independently. CGA is run by strategic whose target model 0* labels 0's as I's, I's as 2's, and so on, until 9's as O's. We learn 0! by relabeling the MNIST training dataset and learning from the relabeled data. We À Adam optimizer and decreasing learning rate.
35
35
30
25
25-
20
R_dist
2 norm
15
dist
15
2 dst
5-
0_
target
100
Epochs
Epochs
(a) Using 2
(b) Using &
Figure 16: Norm of global model, distance to initialisation and distance to target, under attack by CGA. In particular, we see that the attack against Eg successful, as the distance between the global model and the target model goes to zero.
40

---

Under review as a conference paper at ICLR 2022
H
SINGLE DATA POISONING FOR LEAST SQUARE LINEAR REGRESSION
Proof of T'hoormm 5 We define the minimized loss with respect to and without strategic user by
Loss" (p.
min
(o.... Da)
Σ>
110
pll
(169)
0 (R(x(N1))
Now consider subgradient E v .) of the minimized loss at OJ. For _ 2x
then have y v ||=11]) We then define 0 0!
9 g V LLLSS" (0), D V. (1 10 07 0%112)
(170)
vpLoss, (0. D D),,, 0_ D_s),
(171)
where L.sss, is defined by 38
Now consider the data point (Q,A) (g. of.
1). For
D. ((2,A)), we then have
(0 D.) = g. which implies
Lo.so (0." 0² (0 .). D) 0.
(172)
Combining all together with the uniqueness of the solution then yields
arg min (ooss(p, 0, D) (0), 0 0- (0 D D-))) (0.0)
(173)
which is what we wanted.
I DATA POISONING AGAINST LINEAR CLASSIFICATION
1.1 GENERATING EFFICIENT POISONING DATA
For every label E f1....,91 9}, we define yo - 0 60 and Co - (8 0%0 (where is the bias of the linear classifier). The indifference subspace V is then the set of images Q e Rd such that y C. for all E (9.....9..
20
To project any image orthogonal to V, using the Gram-Schmidt algorithm. Namely, we first define 21 A y1. Then, for any answer {1...., 99. define
IRd on V, let us first construct an orthogonal basis of the vector space
Σ bca
Na
2b |
(174)
is easy to check that for b < a, have z 2b 0. Moreover, if Q V, then
(v
2b (= Q)
(uā (1)
_ -/
Ca
(175)
|
1
By induction, we see that 2 ITQ Q is a constant independent from Q. Indeed, for 1, this is clear as z Q ví Q c₁ Moreover, for 1, then, the computation of 2 Q, Q always appear as =[ Q for b < Moreover, denoting e, the constant such that 2 = e₂ for all E (1,...9), we see that these constants can be computed by
dg = Ca
yo
2h
(176)
2b
2
Finally, we can simply perform repeated projection onto the hyperplanes where is equally probable as the answer O. To do this, we first define the orthogonal projection P(X, c) of X Rd on the hyperplane xf = e, which is given by
P(X.y.c) X (xf y
(177)
1 2
2
41

---

Under review as a conference paper at ICLR 2022
It is straightforward to verify that P(X, y, c) y= and that P, P(X, We then canonically define repeated projection by induction, as
P(X, (y1+...,9++1)) 1), (CI....,
,..11)) A P(P(X, (yI..... yk), (cI...,, yk+1, Cx+1). (178)
Now consider any image X E RR Its projection can be obtained by setting
Q P(X, (z1...., 20), (c..... 6)) + +
(179)
Note that to avoid being exactly on the boundary, and thus retrieve information about the scales of 8 and on which side of the boundary favors which label, we add small noise ç, to make sure Q does not exactly on V (which would lead to multiple solutions for the learning), but small enough so that the probabilities of the different label remain close to 0.1 (the equiprobable probability).
We acknowledge that images obtained this way may not be in [0. 1] like the images of the MNIST dataset. In general, one could search for points Q V n [0. 1j Note that in theory, by Theorem 3 (or a generalization of it), labeling random images in [0. 1] should suffice. However, in the case where V n [0, 1] is empty (typically if no image in [0, 1] is argued by model 6 as realistically 9), this procedure may require the labeling of significantly more images to be successful.
1.2 A BRIEF THEORY OF DATA POISONING FOR LINEAR CLASSIFICATION
Using the efficient poisoning data fabrication, we thus have set of images (Q, p( Q)), where pa (2) is the probability assigned to image Q and label a. This defines the following local loss for the strategic node:
D.) = Σ
E loo,0.))
(180)
(Q.D))) (E
explo" +0.00)) is the probability that image Q has label a, according to the
where To (0,, () Eexp(O @+0.a)
model oz. We acknowledge that such labelings of queries is unusual. Evidently, in practice, an image may be labeled N times, and the number of labels N₂ it received can be set to be approximately Na R (2).
It is noteworthy that the gradient of the loss function is then given by
(0. - 0. Vo, CO., D.) = Σ Σ
(aa(0., 2) - oa( 2)) (0.a - 0a)) et,
QED, (U.
(181)
where we defined Q+ A (1,2) (which allows to factor in the bias of the model. This shows that Ve, C, (0,, D&) points systematically away from 0 and thus that gradient descent will move towards 0.a
In fact, if the set of images Q cover all dimensions (which occurs if there are M(d) images, which is the case for 2,000 images, since d = 784), then gradient descent will always move the model the direction of 8th which will be the minimum. Moreover, by overweighting each data (Q, p Q)) by a factor a (as though the image Q was labeled a times), we can guarantee gradient-PACC learning, which means that will have 0r A 0 even in the personalized federated learning framework. This shows why data poisoning should work in theory, with relatively few data injections.
Note that the number of other users does make learning harder. Indeed, the gradient of the regu- larization R(p, 0.) at p 0 and 0, = 0 is equal to 2Λ |0]- 0 10 As the number N - 1 of other users grows, we should expect this distance grow roughly proportionally
N. In order to make strategic user s robustly learn 8 the norm of the gradient of the local loss L, at of must be vastly larger than 2A ||6] 8 2. This means that the value of a (or, equivalently, the number of data injected in D.) must also grow proportionally to N.
1.3 INITIALIZATION OF THE LEARNING ALGORITIIM
The convergence to the optimum is slow. But given that the problem is convex, we focus here mostly on showing that the minimum is indeed poisoned model. To boost the convergence, initialize our learning algorithm at a point close to what we expect to be the minimum. by taking this minimum and adding a Gaussian noise, and then observe the convergence this minimum.
42

---

Under review as a conference paper at ICLR 2022
J CIFAR-10 ON VGG 13-BN EXPERIMENTS
We considered VGG 13-BN, which was pretrained on cifar- 10 by Phan (202T). We now assume that 10 nodes given part of the cifar-10 database, while strategic node also joins the personalized federated gradient descent algorithm. The strategic node's s goal is to bias the global model towards target model, which misclassifies the cifar-10 data, by reclassifying 0 into 1, 1 into 2... and into O.
J.1 COUNTER-GRADIENT ATTACK
We first show the result of performing counter- counter-gradien gradient attack on the last layer of the neural network. Essentially, images are now reduced to their vector embedding, and the last layer performs simple linear classification akin to the case of MNIST (see Appendix G
Gradient attack
Gradient attack
1.0
40
honest dist
35
12_nom
target_dsst
30
attack, dist
Acorsey
0.6
20
0.4
15
10-
0.2
200
600
1000
200
600
1000
(a) Accuracy according to attacker's objective
(b) Distances
Figure 17: CGA on cifar- 10.
J.2 RECONSTRUCTING A MODEL ATTACK
Reconstructing an attack model whose effect is equivalent to the counter-gradient attack identical to what was done in the case of MNIST (see Section 5.2)
Model
1.0
40
honest dist
12_norm
0.8
target dis
30-
attack dist
25
Aconcyy
20-
0.2
0.0
Epochs
Epochs
Accuracy according to attacker's objective
(b) Distances
Figure 18: Model attack on cifar- 10.
J.3 RECONSTRUCTING DATA POISONING
This last step is however nontrivial. On one hand, we could simply use the attack model to label large number of random images. However, this solution would likely require large sample com-
43

---

Under review as a conference paper at ICLR 2022
plexity. For efficient data poisoning, construct vector embeddings on the indifference
affine subspace V, as was done for MNIST in Section 5.3
This is what is shown below.
1.0
40
honest_die dist
N_norm
0.8
....
target dist
attack clst
Accurny
0.6
25
20-
0.2
glob
0.0
800
Epochs
Epochs
Accuracy according to attacker's objective
Distances
Figure 19: Data poisoning on cifar-10.
We acknowledge however that this does not quite correspond data poisoning, as requires re- porting vector embedding and its label, rather than an actual image and its label. The challenge then to reconstruct an image that has given vector embedding. We note that, while this is not straightforward task in general, this has been shown to be at least somewhat possible for some neural networks, especially when they are designed be interpretable (Zeiler & Fergus 2014 Wang al., 2019c Mai et al. 2019).
44


Reviews:
[{"review_id": "uYFeJQBt9AT", "reviewer": "Reviewer_a13A", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 considered problem is of great contemporary importance in the deployment of large-scale machine learning systems. 1. The formalization of the PAC learnability is intuitive and concrete examples linear regression, logistic regression, are analyzed to illustrate this definition. 2. The equivalence between data poisoning, model attacks, and gradient attacks are carefully analyzed. 3. The proposed CGA attack has theoretical guarantee and demonstrates good empirical performance.\n\nIn general, I think the assumptions used in this paper are strong. 1. The sufficient condition proposed for PAC* learnability is not intuitive to me, is more like a sufficient condition for the two concrete examples analyzed, and lack intuitions for a wider class of functions. Like, does this condition or the PAC* learnability holds for any non-convex loss used in practice? 2. It might also help to have more detailed explanations for the considered data poisoning, model attacks and gradient attacks, like giving concrete examples to illustrate. The assumptions for theorem 6 to hold also seem strong to me, it is not clear to me how to interpret the assumed property of R, especially R(\\rho, \\theta) = R_0(\\rho - \\theta). It might be clearer to draw a diagram to show under which conditions the claimed equivalences hold, since the claim in the paper title and abstract is fairly strong. 3. I also would suggest giving proof outlines for main theorems for the paper. 4. Another question is how should we relate the proposed CGA with the previous sections, is there any motivations therein?\n", "summary_of_the_paper": "The paper formalizes the concept of PAC*-learnability for a generalized personalized federated learning model and provides a sufficient condition. Under this model, converging gradient attack is equivalent to data poisoning. The paper also proposes the counter-gradient attack that is effective and data-efficient.", "summary_of_the_review": "I would recommend that the paper is marginally below the acceptance threshold. Mainly because I don’t quite follow the intuitions of some assumptions. Refined analysis with weaker assumptions and clearer presentation would be appreciated.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lGLL93CmUm", "reviewer": "Reviewer_gjXp", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Model poisoning are generally perceived as stronger attacks (in terms of poisoning impact) than data poisoning attacks, simply because data poisoning only indirectly manipulates a client’s model update. Therefore, showing an equivalence as the paper argues would be very interesting. However, in my view, the paper is written in somewhat confusing manner, and lacks in details. Therefore, it is difficult to understand and assess the claims. (More detailed comments are given below.) Moreover, the paper does not compare the proposed Counter-Gradient attack with existing attacks. There are a large number of existing attacks and defenses, and it would be important to place the proposed attack in the larger context by comparing and contrasting with prior attacks and defenses.\n\nDetailed Comments:\n\n1. Definition 1 relies on ‘true models’ \\theta^{perp}. It will be good to give more details about what do the authors mean by true models. Propositions 1 and 2 on computing poisoned gradients also use true models. It is not clear how users will know about these true models? It will be important to elaborate this further. \n\n2. Is the difference between using sum vs. expectation in the loss not related to empirical vs. population risk? Also, computing the sum  of losses over the entire user dataset is essentially gradient descent, which is known to be computationally burdensome. It will be helpful to comment on these points.\n\n3. In Definition 2, a loss function is defined to be PAC-learnable. This is a bit confusing. PAC-learning is usually defined for a class of functions. It would be good to explicitly define the function class. \n\n4. In Theorem 2, how is \\tilde{Q} defined and how is the Supp() defined?\n\n5. Theorem 1 restricts the queries to be i.i.d. sub-Gaussian. This seems to be quite restrictive. It will be good to comment on this. \n\n6. Theorem 5 requires that a user’s dataset contains at least \\mathcal{I} inputs drawn from a certain model. This is quite confusing. What does it mean to draw inputs from a model?\n\n7. The paper says that [Shejwalkar et al. 2021] argued that model poisoning attacks are not realistic, and claims in the conclusion that their findings reverses this argument. It is not clear why an equivalence result would reverse the claim in [Shejwalkar et al. 2021]. This is because, as per my understanding, [Shejwalkar et al. 2021] also argue that data poisoning attacks are not very impactful (key lesson (2) on page 2). It would be important to give more details here. ", "summary_of_the_paper": "The paper studies data and model poisoning attacks in federated learning (FL). It argues that there is an equivalence between data poisoning and model poisoning attacks, by restricting attention to linear and logistic regression. The main technique is to leverage ideas from PAC-learning. Another key contribution is to propose a gradient poisoning attack.", "summary_of_the_review": "It would be interesting to show an equivalence between model and data poisoning attacks in FL. However, the paper is written in somewhat confusing manner and lacks in details, which makes it difficult to understand and assess the claims.", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "_VZLR2BtiG", "reviewer": "Reviewer_xXNa", "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": "Strengths:\n+ Reveals a new insight on the equivalence between Byzantine gradient and data poisoning attacks, which is an important and timely topic.\n+ A novel PAC framework for analyzing personalized federated learning performance.\n\nWeaknesses:\n- Gradient attack model is limited.\n- Experiments are limited to simple datasets.", "summary_of_the_paper": "This paper reveals the inherent equivalence between gradient and data poisoning attacks in personalized federated learning settings. The authors showed that any gradient attack can be transformed into data poisoning in a personalized federated learning system that provides PAC guarantees. This new insight challenges the view that (Byzantine) gradient attacks are unrealistic. The authors built this equivalence by constructing a model attack for personalized federated learning models. The authors showed the effectiveness of this attack both theoretically and empirically. ", "summary_of_the_review": "This paper reveals an equivalence between Byzantine gradient and data poisoning attacks in the context of personalized federated learning, which is an important and timely topic. This insight suggests that the claims in the existing literature that Byzantine gradient attacks are unrealistic is misleading. To my knowledge, this result is new and its contributions to the field are significant. However, this paper also has several issues, which are listed as follows:\n\n1. The attack model considered in this paper is somewhat simplistic in that the authors only considered the single-strategic-user case. Although it is understandable that this renders the problem more tractable for theoretical analysis, the results may not be very useful because Byzantine gradient attacks are not necessarily from a single malicious user. In fact, most works on Byzantine gradient attacks allow multiple Byzantine workers. It's unclear whether the results in this paper could be extended to multi-attacker scenarios.\n\n2. The authors proposed a PAC framework as a foundation to evaluate the performance of various Byzantine and data poisoning attacks. To my knowledge, this is also a new and interesting contribution. The authors demonstrated the relevance of this PAC framework by showing that linear regression and classifications are PAC learnable under this framework. But I wonder whether this PAC framework continues to be meaningful for more complex learning models than linear models. Having further discussions on this aspect would be very interesting.\n\n3. Most of the experiments in this paper are conducted on MNIST and Fashion-MNIST datasets, which are relatively simple. It would be more interesting to demonstrate the claimed equivalence between attacks on more sophisticated datasets. Also related to the previous comment, most of the experiments are based on linear models (a simple two-layer neural network is also used). I think this paper could benefit from more experiments with more sophisticated learning models.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "UudDZlYz36m", "reviewer": "Reviewer_oiiD", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The goal of this paper to compare two threat models in federated learning 1) data poisoning attacks that inject a number of poisoning examples to the training set 2) gradient attacks that change the update gradients sent during the federated learning operation by malicious agents. They specifically study the personalized federated learning setting where N machines collaborate to train N personalized models and a single global model. In this setting, the loss function is defined in a way that the global model and personalized models have dependencies to each other through an additive regularization that controls how far the personalized models can be from the global model.\n\nThe paper first defines two notions that they call PAC^* Learning and gradient PAC* learning for the personalized federated learning. The notion of PAC* learning is about finding a set of personalized models that are close to the set of true models with respect according to some metric. Note that this is different from PAC learning because they care about distance, rather than accuracy. They also define gradient-PAC*, which requires the gradients of the personalized models with respect to any global model \\rho to be close to that of true models.\n\nThen, they introduce a hypothetical threat model called a model attack, where they fix one of the personalized models to a specially crafted adversarial model. Then they show that, if the optimization of loss function has PAC* learning abilities, then the adversary can simulate the effect of the model attack using data poisoning attack, by poisoning all of the data for the machine, if the number of data-points provided by that machine is larger than some threshold. This result is expected, because as the number of data-points grow, the dependence between the personalized model and the global model decrease (because of the diminishing effect of the regularization). Then, by increasing the number of data points, because of PAC* learning, the adversary can change the personalized model to a adversarially crafted model, by using queries that are labeled accordingly. At the same time, the global model and other personalized models would not change much because of the diminish dependency of the global and personalized models.  \n\nNow the remaining step is to show that the gradient attack can be simulated by a model attack. In order to show this, they need some strong assumptions. For instance, they need the loss function to be strongly convex. They need the poisonous gradients to be valid gradients according to the global model. and also they require the poisonous gradients to converge. This step is technically interesting and novel, in my opinion. \n\nFinally, they design a data poisoning attacks that are inspired by the steps mentioned above. They empirically show that this attack is effective in linear regression.\n\n\nLimitations:\n\n- The final equivalence result of the paper only applies to simple settings with strongly convex loss functions and seems to only work for GD optimization.\n\n- The presentation of the work is not in publication stage. It is really hard to understand the main claims of the paper.\n\n- Some discussions about the implication of the results are missing\n\n\nComments/Questions to authors:\n\n1- I have read through the paper multiple times, but I still do not understand the exact threat model of gradient attack. I think you need to define this explicitly.\n\n2- The notions of PAC* learning are not defined properly. There are terms such as \"true model\"  and \"honest dataset\" that are not defined. These terms are not standard and must be defined. Also, there is a probability \\delta, what is this probability over? \n\n3- Section 3 seems to be completely out of context. Why do you need to justify the choice of loss function before describing the main results? I was really confused by this section. After reading the paper, I realize that you need to define the loss this way in order for Theorem 5 to hold? If this is correct, you need to explicitly mention it. I also find Table 1 confusing. \n\n4- Defining the loss function as a summation of the loss is fine, but your notion of PAC* learning talks about large number of data points. Wouldn't large number of data points make the dependence of global and personalized models weaker as more data is provided? How is it justified to keep the regularization the same as more data is provided?\n\n5- Again, section 4 seems to be out of place. It is a bit odd to see the main results of the paper in section 5. I would recommend to  change the order of sections 4 and 5.\n\n6- The equivalence between the model attacks and data poisoning attack depend on the number of data points. I think the paper needs discussion on this connection. Could the power of model attacks be significantly higher than data poisoning attacks when the number of data points provided by each party is a fixed and perhaps small number?\n\n7- Theorem 6 seems like the main theorem in the paper to me. But I cannot verify the proof. Specifically, I cannot verify equation (120) in page 33. Can you explain why this is the case? Aren't \\rho and \\theta_n getting optimized together. In your formulation it seems like \\theta_n is optimized until convergence for each intermediate \\rho. ", "summary_of_the_paper": "This paper shows an equivalence between data poisoning attacks and gradient attacks that attack gradient descent on personalized federated learning setting for certain convex loss functions. ", "summary_of_the_review": "I find the topic of this paper extremely interesting. Understanding the relation between gradient attacks and data poisoning attacks are very important. This paper takes an initial step in understanding the relation between these two attacks for simple models such as linear regression. However, as stated in my comments, I have serious concerns about the presentation of this work. The main ideas presented are not easy to comprehend. The exact threat models are not also clearly specified. I also have some concerns about the proofs (In particular about equation 120, page 33). I will be happy to increase my score if authors can provide sufficient response to my concerns.\n\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OD8QKqa4XXf", "reviewer": "Reviewer_bDXf", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Pros:\n\nThe paper studies an interesting problem, since both Byzantine attacks and data poisoning attacks have been extensive studied in the literature, but little is known about how these fields relate. The paper provides a substantial technical analysis, as well as a practical Byzantine attack.\n \n\n##########################################################################\n\nCons: \n\nUnfortunately, several concern prevent me from recommending acceptance. \n\n- Firstly, I find the comparison to related work very insufficient. \n\nFor the theoretical analysis a number of recent works, for example [1,2,3,4], have explored (robust) machine learning from multiple datasets from a PAC perspective. These essentially correspond to the notion of PAC* learnability presented here, with and without data poisoning. It is unexplained how these works compare to the current one. \n\nFor the gradient attack that is designed, there is no comparison to prior attacks as well. It is also unclear what this attack has to do with the rest of the paper - can the authors explain?\n\n- The paper is also slightly hard to follow, in particular the results of Theorem 4,5 and 6 are quite hard for me to interpret. Since there is no previously defined notions of success of for each of the attacks, it is hard to understand why the results imply any type of equivalence between the notions. Further discussion immediately after these results will therefore be helpful.\n\n#########################################################################\n\nReferences:\n\n[1] A. Blum, N. Haghtalab, A. D. Procaccia, M. Qiao: Collaborative PAC Learning, NIPS 2017\n[2] M. Qiao: Do outliers ruin collaboration?, ICML 2018\n[3] N. Konstantinov, E. Frantar, D. Alistarh, C.H. Lampert: On the Sample Complexity of Adversarial Multi-Source PAC Learning, ICML 2020\n[4] A. Jain and A. Orlitsky: A General Method for Robust Learning from Batches, NeurIPS 2020\n\n ", "summary_of_the_paper": "The paper studies the relationship between Byzantine gradient attacks in distributed optimization and data poisoning. Some theoretical evidence is presented about the equivalence of these. A new gradient-based Byzantine attack is also presented.", "summary_of_the_review": "While the studied topic and the proposed notions and results are interesting, I believe that the paper will benefit from substantial further comparison to existing work and also from further discussion of the results from Theorems 4,5,6.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an analysis showing the equivalence between gradient and data poisoning attacks in personalized federated learning settings. The paper contains an analysis of an attack that requires only a single corrupt learning agent, providing results in the setting of PAC learnable models.
The reviewers had several criticisms of the paper, some of which were addressed in the rebuttal.  The first is that the presentation of the paper was at times confusing, and the theoretical results were hard to interpret.  This has been addressed by several changes to the paper writing, including major changes to the layout.  The reviewers feel that other criticisms were not entirely addressed.  This includes the criticism that the experiments are in a fairly simplistic setting (GD on MNIST and Fashion MNIST), and that the theoretical results require strong assumptions and focus mostly on classical models that are learnable in convex frameworks.  While the reviewers agree there are interesting questions posed in this paper, the consensus seems to be that the experimental and theoretical results in this paper should be further revised, and that a future version of this paper will be a great candidate for publication.
Decision: Reject