Year: 2021

Abstract:
To study 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.

text: To study 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.

heading: 1 INTRODUCTION
text: Learning algorithms now typically leverage data generated by a large number of users (Smith et al., 2013; Wang et al., 2019a;b) to often learn a 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, 2021), conversational (Shum et al., 2018) and recommendation (Ie 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., 2021), these algorithms require a 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 as content recommendation, activists, companies, and politicians have strong incentives to promote certain views, products or ideologies (Hoang, 2020; Hoang et al., 2021). Remember for instance that, on YouTube, two views out of three result from algorithmic recommendations (Solsman, 2018). Perhaps unsurprisingly, this has led to vast amounts of fabricated activities to bias algorithms (Bradshaw & Howard, 2019; Neudert et al., 2019), like “fake reviews” (Wu et al., 2020). The scale of this phenomenon is well illustrated by the case of Facebook which, in 2019 alone, reported the removal of around 6 billion fake accounts from its platform (Fung & Garcia, 2019). This is particularly concerning in the era of “stochastic parrots” (Bender et al., 2021): climate denialists are incentivized to pollute textual datasets with claims like “climate change is a hoax”, as autocompletion, conversational and recommendation algorithms trained on such data will more likely spread these views (McGuffie & 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 deep fakes (Johnson & 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 learning algorithms arguably demands that they be trained solely on cryptographically signed data, that is, data that provably come from a 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 to behave strategically in order to promote certain views or products.
To address data poisoning, the Byzantine learning literature usually considers that each federated learning worker may behave arbitrarily (Blanchard et al., 2017; Mhamdi et al., 2018; El-Mhamdi et al., 2021). Recall that at each iteration of the federated learning stochastic gradient descent, each worker is given the updated model, and is asked to compute the gradient of the loss function with respect to (a batch of) its local data. Byzantine learning usually assumes that a malicious (Byzantine) worker may report any gradient; without having to justify whether such a 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., 2021), 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 practically compelling argument for the necessity to protect federated learning against gradient attacks.
Contributions. As a preamble of our main result, we formalize local PAC* learning1 (Valiant, 1984) for personalized learning, and prove that a simple and general solution to personalized federated linear regression and classification is indeed locally PAC* learning. Our proof leverages a new concept called gradient-PAC* learning, which is of independent interest. We prove that it is sufficient to 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 a 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 a simple but very general strategic gradient attack, called the counter-gradient attack (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 a 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., 2017; Mhamdi et al., 2018; Baruch et al., 2019; Xie et al., 2019), some of which apply almost straightforwardly to personalized federated learning (El-Mhamdi et al., 2020; 2021). Such results study the resilience against a minority of adversarial users. Our paper however focuses on a different kind of malicious users. Namely, like Suya et al. (2021), we study the resilience against strategic users, who aim to bias the learned models towards a specific target model.
The study of the resilience against strategic users is part of the research on strategyproof learning. Many special cases of strategyproofness have been tackled, including regression (Chen et al., 2018b; Dekel et al., 2010; Perote & Perote-Peña, 2004; Ben-Porat & Tennenholtz, 2017), classification (Meir et al., 2012; Chen et al., 2020; Meir et al., 2011; Hardt et al., 2016), statistical estimation (Cai et al., 2015), and clustering (Perote & Sevilla, 2003). However, none of these papers tackles a general personalized federated learning scheme. Typically, for linear regression, Chen et al. (2018b) and Perote & Perote-Peñ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 (e.g., due to ethical reasons), or they restrict the model to one dimension or a constant function in Rd. Conversely, Suya et al. (2021) show how to arbitrarily manipulate convex learning models through multiple data injections, in the case where a 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., 2020; Severi et al., 2021; Truong et al., 2020; Schwarzschild et al., 2021) or triggerless attacks (Biggio et al., 2012; Muñoz-González et al., 2017; Shafahi et al., 2018; Zhu et al., 2019;
1We omit complexity considerations for the sake of generality. We define PAC* to be PAC without such considerations.
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 a (bad) property.
Collaborative PAC learning was previously introduced by Blum et al. (2017), and then extensively studied (Chen et al., 2018a; Nguyen & Zakynthinou, 2018), sometimes with the presence of Byzantine collaborating users (Qiao, 2018; Jain & Orlitsky, 2020; 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 a general model of personalized learning, formalizes local PAC* learning and defines a general federated gradient descent algorithm. Section 3 proves the equivalence between data poisoning and gradient attacks, under local PAC* learning. Section 4 proves the local PAC* learning properties for federated linear regression and classification. Section 5 then describes a simple and general data poisoning attack, whose effectiveness against `22 is proved theoretically and empirically. Section 6 concludes.

heading: 2 A GENERAL PERSONALIZED FEDERATED LEARNING FRAMEWORK
text: We consider a set [N ] = {1, . . . , N} of users. Each user n ∈ [N ] has a local signed dataset Dn, and aims to learn a local model θn ∈ Rd. Users may collaborate to improve their models. Personalized learning must then input a tuple of users’ local datasets ~D , (D1, . . . ,DN ), and output a tuple of local models ~θ∗ , (θ∗1 , . . . , θ ∗ N ). Like many others, we assume that the users perform federated learning to do so, by leveraging the computation of a common global model ρ ∈ Rd. Intuitively, the global model is 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 Hanzely et al. (2020). Namely, we consider that the personalized learning algorithm outputs a global minimum (ρ∗, ~θ∗) of a global loss given by
LOSS(ρ, ~θ, ~D) , ∑ n∈[N ] Ln(θn,Dn) + ∑ n∈[N ] R(ρ, θn), (1)
whereR is a regularization, typically with a minimum at θn = ρ. For instance, Hanzely et al. (2020) and Dinh et al. (2020) define R(ρ, θn) , λ ‖ρ− θn‖22, which we shall call the `22 regularization. But other regularizations may be considered, like the `2 regularization R(ρ, θn) , λ ‖ρ− θn‖2, or
the smooth-`2 regularizationR(ρ, θn) , λ √
1 + ‖ρ− θn‖22. Note that, for all such regularizations, the limit λ →∞ essentially yields the classical non-personalized federated learning framework.

heading: 2.1 LOCAL PAC* LEARNING
text: In this paper, we focus on personalized learning algorithms that provably recover a user n’s preferred model θ†n, if the user provides a large enough honest dataset Dn, i.e. constructed with θ†n. Such honest datasets Dn could typically be obtained by repeatedly drawing random queries (or features), and by using the user’s preferred model θ†n 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 subsetH ⊂ [N ] of honest users, any preferred models ~θ†, any ε, δ > 0, and any datasets ~D−H from users n /∈ H , there exists I such that, if all users h ∈ H provide honest datasets Dh with at least |Dh| ≥ I data points, then, with probability at least 1− δ, we have ∥∥∥θ∗h ( ~D)− θ†h∥∥∥ 2 ≤ ε for all users h ∈ H .
Local PAC* learning is arguably a 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 4, we will show how local PAC* learning can be achieved in practice, by considering specific local loss functions Ln.

heading: 2.2 FEDERATED GRADIENT DESCENT
text: While the computation of ρ∗ and ~θ∗ could be done by a 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 ρt to the users. Each user n is then expected to update its local model given the global model ρt, either by solving θtn , arg minθn Ln(θn,Dn)+R(ρ
t, θn) (which is what we assume in the theory part, in the manner of Dinh et al. (2020)), or by making a (stochastic) gradient step from the previous local model θt−1n (which is what is done in our experiments, in the manner of Hanzely & Richtárik (2021)). User n is then expected to report the gradient gtn = ∇ρR(ρt, θtn) to the parameter server. The parameter server then updates the global model, using a gradient step, i.e. it computes ρt+1 , ρt − ηt ∑ n∈[N ] g t n. For simplicity, here, and since our goal is 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 El-Mhamdi et al. (2021).
We assume that the users are only allowed to send plausible gradient gradients. More precisely, we denote GRAD(ρ) , {∇ρR(ρ, θ) | θ ∈ Rd} the closure set of plausible (sub)gradients at ρ. If user n’s gradient gtn is not in the set GRAD(ρ
t), the parameter server can easily detect the malicious behavior and gtn will be ignored by the parameter server at iteration t. In the case of an ` 2 2 regularization, where R(ρ, θ) = λ ‖ρ− θ‖22, we clearly have GRAD(ρ) = Rd for all ρ ∈ Rd. It can be easily shown that, for `2 and smooth-`2 regularizations, GRAD(ρ) is the closed ball B(0, λ). Nevertheless, in this setting, a strategic user s ∈ [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 an honest dataset, s fabricates any strategically crafted dataset Ds, and then performs all other operations as expected.
Model attack: At each iteration t, s fixes θts , θ♠s , where θ♠s is any strategically crafted model. All other operations would then be executed as expected.
Gradient attack: At each iteration t, s sends any (plausible) strategically crafted gradient gts.
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 no clear ground truth, such as content moderation or language processing, the strategic user can always argue that their dataset is an “honest” dataset; not a 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.

heading: 3 THE EQUIVALENCE BETWEEN DATA POISONING AND GRADIENT ATTACKS
text: We now present our main result. The threat model we considered is closely related to “modeltargeted attacks”, studied in Suya et al. (2021). Recall also that, in this theory part, at each iteration, local models θtn are fully optimized, given ρ
t, in the manner of Dinh et al. (2020). Theorem 1 (Equivalence between gradient attacks and data poisoning). Assume local PAC* learning, and `22 or smooth-`2 regularization. Assume also that Ln is convex and L-smooth for all users
n ∈ [N ], and that the learning rate ηt is constant and small enough. Consider any datasets ~D−s provided by users n 6= s. Then, for any target model θ†s ∈ Rd, there exists a converging gradient attack of strategic user s (i.e. gts converges) such that ρ
t → θ†s, if and only if, for any ε > 0, there exists a dataset Ds such that ∥∥∥ρ∗( ~D)− θ†s∥∥∥ 2 ≤ ε.
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.

heading: 3.1 EQUIVALENCE BETWEEN DATA POISONING AND MODEL ATTACKS
text: In this section, we prove the equivalence between data poisoning and model attacks.
Lemma 1 (Reduction from model attack to data poisoning). Consider any data ~D and user s ∈ [N ]. Assume the global loss with datasets ~D has a global minimum (ρ∗, ~θ∗). Then (ρ∗, ~θ∗−s) is also a global minimum of the modified loss with datasets ~D−s and strategic reporting θ♠s , θ∗s( ~D).
Proof. The proof is almost straightforward. It is given in Appendix B.1.
Now, intuitively, by virtue of local PAC* learning, strategic user s can essentially guarantee that the personalized learning framework will be learning θ∗s ≈ θ♠s . But, a 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 θ∗s = θ ♠ s . In the sequel, we show that the answer is yes. Lemma 2 (Reduction from data poisoning to model attack). Assume `22, `2 or smooth-`2 regularization, and assume local PAC* learning. Consider any datasetsD−s and any attack model θ♠s such that the modified loss LOSSs has a unique minimum ρ∗(θ♠s , ~D−s), ~θ∗−s(θ♠s , ~D−s). Then, for any ε > 0, there exists a dataset Ds such that we have∥∥∥ρ∗( ~D)− ρ∗(θ♠s , ~D−s)∥∥∥
2 ≤ ε and ∀n 6= s, ∥∥∥θ∗n( ~D)− θ∗n(θ♠s , ~D−s)∥∥∥ 2 ≤ ε. (2)
Our proof in fact holds for all continuous regularizations R with R(ρ, θ) → ∞ as ‖ρ− θ‖2 → ∞. Moreover, note that the approximation guarantee holds for local models too.
Sketch of proof. Given local PAC* learning, for a large dataset Ds constructed from θ♠s , strategic user s can guarantee θ∗s( ~D) ≈ θ♠s . By carefully bounding the effect of the approximation on the loss using the Heine-Cantor theorem, we show that this implies ρ∗( ~D) ≈ ρ∗(θ♠s , ~D−s) and θ∗n( ~D) ≈ θ∗n(θ ♠ s , ~D−s) for all n 6= s too. The precise analysis, given in Appendix B.2, is nontrivial.

heading: 3.2 EQUIVALENCE BETWEEN MODEL ATTACKS AND GRADIENT ATTACKS
text: For the last few years, gradient attacks have been widely studied by the Byzantine learning literature. Recently, Shejwalkar et al. (2021) argued that they are not a realistic threat model. Below, we prove that, in our setting, they are actually as concerning as model attacks (and, thus, as data poisoning). Lemma 3 (Reduction from model attack to gradient attack). Assume that Ln is convex and Lsmooth for all nodes n ∈ [N ], and that we use `22 or smooth-`2 regularization. If gts converges and if ηt = η is a constant small enough, then ρt will converge too. Denote ρ∞ its limit. Then for any ε > 0, there is θ♠s ∈ Rd such that ∥∥∥ρ∞ − ρ∗(θ♠s , ~D−s)∥∥∥ 2 ≤ ε.
Sketch of proof. Denote g∞s the limit of g t s. Gradient descent then behaves as though it was minimizing the loss plus ρT g∞s (and ignoring R(ρ, θs)). Essentially, classical gradient descent theory then guarantees the convergence of ρt to ρ∞, though the precise proof is nontrivial. Then, since GRAD is closed and g∞s ∈ GRAD, we can construct θ♠s which approximately yields the gradient g∞s . The full proof (which also yields the necessary upper bound on η) is given in Appendix B.3.
Since any model attack can clearly be achieved by the corresponding honest gradient attack, we conclude that model attacks and gradient attacks are essentially equivalent. In light of our previous results, this implies that gradient attacks are essentially equivalent to data poisoning (Theorem 1).

heading: 4 EXAMPLES OF LOCALLY PAC* LEARNING SYSTEMS
text: 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.
Ln(θn,Dn) = ν ‖θn‖22 + ∑ x∈Dn `(θn, x), (3)
for some “loss per input” function ` and some weight ν > 0. Appendix C gives theoretical and empirical arguments are provided for using such a 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 `22, `2 or smooth-`2 regularization. Assume that, to generate a data xi, a user with preferred parameter θ† ∈ Rd first independently draws a random vector query Qi ∈ Rd from a sub-Gaussian query distribution Q̃, with parameter σQ and positive definite matrix Σ = E [ QiQTi ] . Assume that the user labels Qi with a real-valued answer Ai = QTi θ† + ξi, where ξi is a zero-mean sub-Gaussian random noise with parameter σξ , independent from Qi and other data points. Finally, assume that `(θ,Qi,Ai) = 12 (θ
TQi−Ai)2. Then the personalized learning algorithm is locally PAC* learning. Theorem 3 (Personalized logistic regression is locally PAC*-learning). Consider `22, `2 or smooth`2 regularization. Assume that, to generate a data xi, a user with preferred parameter θ† ∈ Rd first independently draws a random vector query Qi ∈ Rd from a query distribution Q̃, whose support SUPP(Q̃) is bounded and spans the full vector space Rd. Assume that the user then labels Qi with answer Ai = 1 with probability σ(QTi θ†), and labels it Ai = −1 otherwise, where σ(z) = (1+e−z)−1 is the sigmoid logistic function. Finally, assume that `(θ,Qi,Ai) = − ln(σ(AiθTQi)). Then the personalized learning algorithm is locally PAC* learning.

heading: 4.1 PROOF SKETCH
text: In this section, we outline the proofs of theorems 2 and 3, as 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, θ†, I, A,B, α) the event
∀θ ∈ Rd, ( θ − θ† )T ∇L (θ,D) ≥ AImin{∥∥θ − θ†∥∥ 2 , ∥∥θ − θ†∥∥2 2 } −BIα ∥∥θ − θ†∥∥ 2 . (4)
The loss ` is gradient-PAC* if, for any K > 0, there exist constants AK, BK > 0 and αK < 1, such that for any preferred model θ† ∈ Rd with ∥∥θ†∥∥ 2 ≤ K, assuming that the dataset D is obtained by honestly collecting and labeling I data points according to the preferred model θ†, the probability of the event E(D, θ†, I, AK, BK, αK) goes to 1 as I → ∞.
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 θ† will point away from θ†. In particular, gradient descent is then essentially guaranteed to draw θ closer to θ†. The right-hand side of equation 4 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 empirical and the expected loss functions depends only on a few key random variables, such as min SP ( 1 I ∑ QiQTi ) and ∑ ξiQi, which can be controlled by appropriate concentration bounds. Meanwhile, for logistic regression, for |b| ≤ K, we observe that (a − b)(σ(a) − σ(b)) ≥ cKmin(|a− b| , |a− b|2). Essentially, this proves that gradient-PAC* would hold if the empirical loss was replaced by the expected loss (times I). 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.
Now, under very mild assumptions on the regularizationR (not even convexity!), which are verified by the `22, `2 and smooth-`2 regularizations, we prove that the gradient-PAC* learnability through ` suffices to guarantee that personalized learning will be locally PAC* learning. Lemma 5. AssumeR is (sub)differentiable and nonnegative, andR(ρ, θ)→∞ as ‖ρ− θ‖2 →∞. If ` is gradient-PAC* and nonnegative, then personalized learning is locally PAC*-learning.
Sketch of proof. Once other users’ datasets are fixed, the learning of an honest user’s model has a fixed biased due toR. But as the user provides more data, by gradient-PAC*, the local loss becomes predominant, which guarantees local PAC*-learning. Appendix E provides a full proof.
Combining the two lemmas clearly yields theorems 2 and 3 as special cases. Note that our result actually applies to a more general set of regularizations and a more general set of local losses.

heading: 4.2 THE CASE OF NEURAL NETWORKS
text: Neural networks generally do not verify gradient PAC* learning. After all, because of symmetries like neuron swapping, different values of the parameters compute the same neural network function. Thus the notion of a “preferred model” θ† is arguably ill-defined for neural networks2. Nevertheless, we may consider a strategic user who only aims to bias the parameters of the last layer. In particular, assuming that all layers but the last one of a neural network are pretrained and fixed, then our theory may apply to the parameters of the last layer, if it performs classification or regression.

heading: 5 A PRACTICAL DATA POISONING ATTACK
text: We now construct a practical data poisoning attack. We do so by introducing a new effective gradient attack, and by then leveraging our equivalence to turn it into a data poisoning attack.

heading: 5.1 THE COUNTER-GRADIENT ATTACK
text: We now define a simple, general and practical gradient attack, which we call the counter-gradient attack (CGA). Intuitively, this attack estimates the sum g†,t−s of the gradients of other users based on its value at the previous iteration, which can be inferred from the way the global model ρt−1 was updated into ρt. More precisely, apart from initialization ĝ1−s , 0, CGA makes the estimation
ĝt−s , ρt−1 − ρt
ηt−1 − gt−1s = g †,t−1 −s . (5)
Strategic user s then reports the plausible gradient that moves the global model closest to the user’s target model θ†s, assuming others report ĝ t −s. In other words, at every iteration, CGA reports
gts ∈ arg min g∈GRAD(ρ) ∥∥ρt − ηt(ĝt−s + g)− θ†s∥∥2 . (6) Note that, to perform this attack, user s only needs to know the previous and current learning rates ηt−1 and ηt, the previous and current global models ρt−1 and ρt, and their target model θ†s.
Computation of CGA. Define hts , gt−1s + ρt−θ†s ηt − ρ t−1−ρt ηt−1
. For convex sets GRAD(ρt), it is straightforward to see that CGA boils down to computing the orthogonal projection of hts on GRAD(ρt). This yields very simple computations for `22, `2 and smooth-`2 regularizations. Proposition 1. For `22 regularization, CGA reports gts = hts. For `2 or smooth-`2 regularization, CGA reports gts = h t s min {1, λ/ ‖hts‖2}.
Proof. Equation (6) boils down to minimizing the distance between ρ t−θ†s ηt − ĝt−s and GRAD(ρ), which is the (convex) ball B(0, λ). This minimum is the orthogonal projection on B(0, λ). 2Evidently, our definition could be easily modified to give importance to the computed function, rather than to the parameters of the model.
Theoretical analysis. We now prove that CGA is perfectly successful against `22 regularization. To do so, we suppose that, at each iteration t and for each user n 6= s, the local models θn are fully optimized with respect to ρt, and the honest gradients of g†,tn are used for the gradient descent of ρ.
Theorem 4. Consider `22 regularization. Assume that ` is convex and L`-smooth, and that ηt = η is small enough. Then CGA is converging and optimal, as ρt → θ†s.
Sketch of proof. The main challenge is to guarantee that the other users’ gradients g†,tn for n 6= s 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 η, is given in Appendix F.
The analysis of the convergence against smooth-`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 ηt = η, then it either achieves perfect manipulation, or it is eventually partially honest, in the sense that the gradient by CGA correctly points towards θ†s.
Proof. Denote P the projection onto the closed ball B(0, λ). If CGA converges, then, by Proposition 1, P ( g∞s + ρ∞−θ†s η ) = g∞s . This implies in particular that ρ ∞ − θ†s and g∞s must be colinear. If perfect manipulation is not achieved (i.e. ρ∞ 6= θ†s), then we must have g∞s = λ ρ∞−θ†s ‖ρ∞−θ†s‖
2
.
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 0’s as 1’s, 1’s as 2’s, and so on, until 9’s that are labeled as 0’s. In particular, this target model has a nil accuracy. Figure 1 shows that such a user effectively hacks the `22 regularization against 10 honest users who each have 6,000 data points of MNIST, in the case where local models only undergo a single gradient step at each iteration, but fails to hack the `2 regularization. Further details on the experiment are given in Appendix G. We also ran a similar successful attack on the last layer of a deep neural network trained on cifar-10, which is detailed in Appendix J. The Appendix also discusses the extent to which the attack may be turned into data poisoning.
5.2 FROM GRADIENT ATTACK TO MODEL ATTACK AGAINST `22
We now show how to turn a gradient attack into model attack, against `22 regularization. Assume that we found a gradient g∞s such that ρ
∞ = θ†s. It is trivial to transform it into a model attack by setting θ♠s , θ † s − 12g ∞ s , as guaranteed by the following result, and as depicted by Figure 2.
Proposition 3. Consider the `22 regularization. Suppose that gts → g∞s and ρt → θ†s, with a constant learning rate ηt = η. Then, under the model attack θ♠s , θ † s − 12λ g ∞ s , the gradient at ρ = θ†s vanishes, i.e. ∇ρLOSS(θ†s, ~θ∗−s(θ†s, ~D−s), θ♠s ,D−s) = 0.
Proof. Given that the learning rate is constant, the convergence ρt → θ†s implies that the sum of honest users’ gradients at ρ = θ†s must equal −g∞s . Therefore, to achieve ρ∗ = θ†s with a model attack, it suffices to send a model θ♠s such that the gradient of λ ∥∥ρ− θ♠s ∥∥22 with respect to ρ at ρ = θ†s equals g ∞ s . Since the gradient is λ(θ † s − θ♠s ), θ♠s , θ†s − 12λ g ∞ s does the trick.
5.3 FROM MODEL ATTACK TO DATA POISONING AGAINST `22
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 `22 regularization and linear regression. For any dataD−s and any target value θ†s, there is a datapoint (Q,A) to be injected by user s such that ρ∗({(Q,A)} ,D−s) = θ†s.
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 θ♠s 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 ⊂ 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 a small noise, before probabilistically labeling the image with model θ♠s . Note that this leads us to consider images not in [0, 1]
d. Figure 3 shows the effectiveness of 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 are provided in Appendix I.

heading: 6 CONCLUDING REMARKS
text: We showed in this paper that, unlike what has been argued by, e.g., Shejwalkar et al. (2021), the gradient attack threat is not unrealistic. For personalized federated learning with local PAC* guarantees, gradient attacks are in fact just as 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 personalized 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 are urgently needed to make large-scale learning algorithms safe.

heading: ETHICS STATEMENT
text: The safety of algorithms is arguably a prerequisite to their ethics. After all, an arbitrarily manipulable 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 to promote non-certified products, e.g., by falsely pretending 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.

heading: REPRODUCIBILITY STATEMENT
text: 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.dropbox.com/sh/qdgmz9air24nhyr/AAAtycEkxc_ 1hGbvU5YG18z4a?dl=0
• The counter-gradient attack experiments can be run by executing this file: https://www.dropbox.com/sh/bycqkccgmk4muzn/ AACRD1yeTglLSHEd1OOAzmVqa?dl=0
• The data poisoning attack experiments can be run by executing this file: https://www.dropbox.com/sh/qodnl6ivzti8hch/ AADgX4EYuSOotiMCAHyTIiGMa?dl=0
• The cifar10 on VGG 13-BN experiments can be run by executing this file: https://www.dropbox.com/sh/5mw5c9dt25eiav7/AAC0jP3e2kuh_ zvLudWbmDl-a?dl=0
The experiments are seeded and the CuDNN backend is configured in deterministic mode in 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 of our Appendix. Our other figures can be obtained by adjusting the hyperparameters of our 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 additional results. The Appendix also contains the full proofs of our theorems.

heading: Appendices

heading: A CONVEXITY LEMMAS

heading: A.1 GENERAL LEMMAS
text: Definition 3. We say that f : Rd → R is locally strongly convex if, for any convex compact set C ⊂ Rd, there exists µ > 0 such that f is µ-strongly convex on C, i.e. for any x, y ∈ C and any λ ∈ [0, 1], we have
f(λx+ (1− λ)y) ≤ λf(x) + (1− λ)f(y)− µ 2 λ(1− λ) ‖x− y‖22 . (7)
It is well-known that if f is differentiable, this condition amounts to saying that ‖∇f(x)−∇f(y)‖2 ≥ µ ‖x− y‖2 for all x, y ∈ C. And if f is twice differentiable, then it amounts to saying∇2f(x) µI for all x ∈ C. Lemma 6. If f is locally strongly convex and g is convex, then f + g is locally strongly convex.
Proof. Indeed, (f + g)(λx+ (1− λ)y) ≤ λf(x) + (1− λ)f(y)− µ2λ(1− λ) ‖x− y‖ 2 2 + λg(x) + (1− λ)g(y) = λ(f + g)(x) + (1− λ)(f + g)(y)− µ2λ(1− λ) ‖x− y‖ 2 2.
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 x, y ∈ Rd,
‖∇f(x)−∇f(y)‖2 ≤ L ‖x− y‖2 . (8) Lemma 7. If f is Lf -smooth and g is Lg-smooth, then f + g is (Lf + Lg)-smooth.
Proof. Indeed, ‖∇(f + g)(x)−∇(f + g)(y)‖2 ≤ ‖∇f(x)−∇f(y)‖2 + ‖∇g(x)−∇g(y)‖2 ≤ Lf ‖x− y‖2 + Lg ‖x− y‖2 = (Lf + Lg) ‖x− y‖2 .
Lemma 8. Suppose that f : Rd × Rd′ 7→ R is locally strongly convex and L-smooth, and that, for any x ∈ X , whereX ⊂ Rd is a convex compact subset, the map y 7→ f(x, y) has a minimum y∗(x). Note that local strong convexity guarantees the uniqueness of this minimum. Then, there exists K such that the function y∗ is K-Lipschitz continuous on X .
Proof. The existence and uniqueness of y∗(x) hold by strong convexity. Fix x, x′. By optimality of y∗, we know that∇yf(x, y∗(x)) = ∇yf(x′, y∗(x′)) = 0. We then have the following bounds
µ ‖y∗(x)− y∗(x′)‖2 ≤ ‖∇yf(x, y ∗(x))−∇yf(x, y∗(x′))‖2 = ‖∇yf(x, y ∗(x′))‖2 (9) = ‖∇yf(x, y∗(x′))−∇yf(x′, y∗(x′))‖2 (10) ≤ ‖∇f(x, y∗(x′))−∇f(x′, y∗(x′))‖2 (11) ≤ L ‖(x− x′, y∗(x′)− y∗(x′))‖2 = L ‖x− x
′‖2 , (12) where we first used the local strong convexity assumption, then the fact that ∇yf(x, y∗(x)) = 0, then the fact that∇yf(x′, y∗(x′)) = 0, and then the L-smooth assumption.
Lemma 9. Suppose that f : Rd × Rd′ 7→ R is locally strongly convex and L-smooth, and that, for any x ∈ X , where X ⊂ Rd is a convex compact subset, the map y 7→ f(x, y) has a minimum y∗(x). Define g(x) , miny∈Y f(x, y). Then g is convex and differentiable on X and ∇g(x) = ∇xf(x, y∗(x)).
Proof. First we prove that g is convex. Let x1, x2 ∈ Rd, and λ1, λ2 ∈ [0, 1] with λ1 + λ2 = 1. For any y1, y2 ∈ Rd ′ , we have
g(λ1x1 + λ2x2) = min y∈Rd′ f(λ1x1 + λ2x2, y) (13)
≤ f(λ1x1 + λ2x2, λ1y1 + λ2y2) (14) ≤ λ1f(x1, y1) + λ2f(x2, y2). (15)
Taking the infimum of the right-hand side over y1 and y2 yields g(λ1x1 + λ2x2) ≤ λ1g(x1) + λ2g(x2), which proves the convexity of g.
Now denote h(x) = ∇xf(x, y∗(x)). We aim to show that∇g(x) = h(x). Let ε ∈ Rd small enough so that x+ ε ∈ X . Now note that we have
g(x+ ε) = min y∈Rd′
f(x+ ε, y) ≤ f(x+ ε, y∗(x)) (16)
= f(x, y∗(x)) + εT∇xf(x, y∗(x)) + o(‖ε‖2) (17) = g(x) + εTh(x) + o(‖ε‖2), (18)
which shows that h(x) is a superderivative of g at x. We now show that it is also a subderivative. To do so, first note that its value at x+ ε is approximately the same, i.e.
‖h(x+ ε)− h(x)‖2 ≤ ‖∇xf(x+ ε, y ∗(x+ ε))−∇xf(x, y∗(x+ ε))‖2
+ ‖∇xf(x, y∗(x+ ε))−∇xf(x, y∗(x))‖2 (19)
≤ L ‖ε‖2 + L ‖y ∗(x+ ε)− y∗(x)‖2 ≤
( L+ L2
µ
) ‖ε‖2 , (20)
where we used the L-smoothness of f and Lemma 8. Now notice that
g(x) = min y∈Rd′
f(x, y) ≤ f(x, y∗(x+ ε)) = f((x+ ε)− ε, y∗(x+ ε)) (21)
= f(x+ ε, y∗(x+ ε))− εT∇xf(x+ ε, y∗(x+ ε)) + o(‖ε‖2) (22) = g(x+ ε)− εTh(x)− εT (h(x+ ε)− h(x)) + o(‖ε‖2), (23)
But we know that ‖h(x+ ε)− h(x)‖2 = O(‖ε‖2). Rearranging the terms then yields
g(x+ ε) ≥ g(x) + εTh(x)− o(‖ε‖2), (24)
which shows that h(x) is also a subderivative. Therefore, we know that g(x+ε) = g(x)+εTh(x)+ o(‖ε‖2), which boils down to saying that g is differentiable in x ∈ X , and that ∇g(x) = h(x).
Lemma 10. Suppose that f : X × Rd′ → R is µ-strongly convex, where X ⊂ Rd is closed and convex. Then g : X → R, defined by g(x) = infy∈Y f(x, y), is well-defined and µ-strongly convex too.
Proof. The function y 7→ f(x, 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 ‖y‖2 → ∞. This proves that the infimum must be reached within a compact set, which implies the existence of a minimum. Thus g is well-defined. Moreover, for any x1, x2 ∈ X, y1, y2 ∈ Rd ′ , and λ1, λ2 ≥ 0 with λ1 + λ2 = 1, we have g(λ1x1 + λ2x2) = inf
y f(λ1x1 + λ2x2, y) (25)
≤ f(λ1x1 + λ2x2, λ1y1 + λ2y2) (26) ≤ λ1f(x1, y1) + λ2f(x2, y2)− µ
2 λ1λ2 ‖(x1 − x2, y1 − y2)‖22 (27)
≤ λ1f(x1, y1) + λ2f(x2, y2)− µ
2 λ1λ2 ‖x1 − x2‖22 , (28)
where we used the µ-strong convexity of f . Taking the infimum over y1, y2 implies the µ-strong convexity of g.

heading: A.2 APPLICATIONS TO LOSS
text: Now instead of proving our theorems for different cases separately, we make the following assumptions on the components of the global loss that encompasses both `22 and smooth-`2 regularization, a well as linear regression and logistic regression. Assumption 1. Assume that ` is convex and L`-smooth, and that R(ρ, θ) = R0(ρ − θ), where R0 : Rd → R is locally strongly convex (i.e. strongly convex on any convex compact set), LR0 - smooth and satisfyR0(z) = Ω(‖z‖2) as ‖z‖2 →∞.
Lemma 11. Under Assumption 1, LOSS is locally strongly convex and L-smooth.
Proof. All terms of LOSS are L0-smooth, for an appropriate value of L0. By Lemma 7, their sum is thus also L-smooth, for an appropriate value of L. Now, given Lemma 6, to prove that LOSS is locally strongly convex, it suffices to prove that ν ∑ ‖θn‖22 +R0(ρ− θ1) is locally strongly convex. Consider any convex compact set C ⊂ Rd×(1+N). Since R0 is locally strongly convex, we know that there exists µ > 0 such that∇2R0 µI . As a result,
(ρ, ~θ)T ( ∇2LOSS ) (ρ, ~θ) ≥ ν ∑ n∈[N ] ‖θn‖22 + µ ‖ρ− θ1‖ 2 2 (29)
= ν ‖θ1‖22 + µ ‖ρ‖ 2 2 + µ ‖θ1‖ 2 2 − 2µρ T θ1 + ν ∑ n 6=1 ‖θn‖22 . (30)
Now define α , √
2µ ν+2µ . Clearly, 0 < α < 1. Moreover, 0 ≤ ∥∥ 1 αθ1 − αρ ∥∥2 2 = 1α2 ‖θ1‖ 2 2 +
α2 ‖ρ‖22 − 2ρT θ1. Therefore 2ρT θ1 ≤ α2 ‖ρ‖ 2 2 + 1 α2 ‖θ1‖ 2 2, which thus implies (ρ, ~θ)T ( ∇2LOSS ) (ρ, ~θ) ≥ ( ν + µ ( 1− α−2 )) ‖θ1‖22 + µ ( 1− α2 ) ‖ρ‖22 + ν ∑ n6=1 ‖θn‖22 (31)
≥ ν 2 ‖θ1‖22 + 2νµ ν + 2µ ‖ρ‖22 + ν ∑ n 6=1 ‖θn‖22 ≥ min { ν 2 , 2νµ ν + 2µ }∥∥∥(ρ, ~θ)∥∥∥2 2 , (32)
which proves that∇2LOSS κI , with κ > 0. This shows that LOSS is locally strongly convex.
Lemma 12. Under Assumption 1, ρ 7→ ~θ∗(ρ, ~D) is Lipchitz continuous on any compact set. Proof. Define fn(ρ, θn) , ν ‖θn‖22 + ∑ x∈Dn `(θn, x) + λ ‖ρ− θn‖ 2 2. If ` is L-smooth, then fn is clearly (|Dn|L + ν + λ)-smooth. Moreover, if ` is convex, then for any ρ, the function θn 7→ fn(ρ, θn) is at least ν-strongly convex. Thus Lemma 8 applies, which guarantees that ρ 7→ ~θ∗(ρ, ~D) is Lipchitz.
Lemma 13. Under Assumption 1, ρ 7→ LOSS(ρ, ~θ∗(ρ, ~D), ~D) is L-smooth and locally strongly convex.
Proof. By Lemma 11, the global loss is known to be L-smooth, for some value of L and locally strongly convex. Denoting f : ρ 7→ LOSS(ρ, ~θ∗(ρ, ~D), ~D), we then have
‖∇f(ρ)−∇f(ρ′)‖2 ≤ ∥∥∥∇ρLOSS(ρ, ~θ∗(ρ, ~D), ~D)−∇ρLOSS(ρ′, ~θ∗(ρ′, ~D), ~D)∥∥∥
2 (33) ≤ L ∥∥∥(ρ, ~θ∗(ρ, ~D))− (ρ′, ~θ∗(ρ′, ~D))∥∥∥
2 (34)
≤ L ‖ρ− ρ′‖2 , (35) which proves that f is L-smooth.
For strong convexity, note that since the global loss function is locally strongly convex, for any compact convex set C, there exists µ such that LOSS(ρ, ~θ, ~D) is µ-strongly convex on C = (C1, C2) ⊂ (Rd,RN×d), therefore, by Lemma 10, f(ρ) will also be µ-strongly convex on C1 which means that f(ρ) is locally strongly convex.

heading: B PROOF OF THE EQUIVALENCE

heading: B.1 PROOF OF THE REDUCTION FROM MODEL ATTACK TO DATA POISONING
text: Proof of Lemma 1. We omit making the dependence of the optima on ~D explicit, and we consider any other models ρ and ~θ−s. We have the following inequalities:
LOSSs(ρ∗, ~θ∗−s, θ ♠ s , ~D) = LOSS(ρ∗, ~θ∗, ~D)− L(θ∗s ,Ds) (36)
≤ LOSS(ρ, (~θ−s, θ∗s), ~D)− L(θ∗s ,Ds) = LOSSs(ρ, ~θ−s, θ♠s , ~D), (37)
where we used the optimality of (ρ∗, ~θ∗) in the second line, and where we repeatedly used the fact that θ∗s = θ ♠ s . This proves that (ρ ∗, ~θ∗−s) is a global minimum of the modified loss.

heading: B.2 PROOF OF THE REDUCTION FROM DATA POISONING TO MODEL ATTACK
text: First, we define the following modified loss function:
LOSSs(ρ, ~θ−s, θ♠s , ~D−s) , LOSS(ρ, (θ♠s , ~θ−s), (∅, ~D−s)) (38)
where ~θ−s and ~D−s are variables and datasets for users n 6= s. We then define ρ∗(θ♠s , ~D−s) and ~θ∗−s(θ ♠ s , ~D−s) as a minimum of the modified loss function, and θ∗s(θ♠s , ~D−s) , θ♠s . We now prove a slightly more general version of Lemma 2, which applies to a larger class of regularizations. It also shows how to construct the strategic’s user data poisoning attack. Lemma 14 (Reduction from data poisoning to model attack). Assume local PAC* learning. Suppose also that R is continuous and that R(ρ, θ) → ∞ when ‖ρ− θ‖2 → ∞. Consider any datasets D−s and any attack model θ♠s such that the modified loss LOSSs has a unique minimum ρ∗(θ♠s , ~D−s), ~θ∗−s(θ♠s , ~D−s). Then, for any ε, δ > 0, there exists I such that if user s’s dataset Ds contains at least I inputs drawn from model θ♠s , then, with probability at least 1− δ, we have∥∥∥ρ∗( ~D)− ρ∗(θ♠s , ~D−s)∥∥∥
2 ≤ ε and ∀n 6= s, ∥∥∥θ∗n( ~D)− θ∗n(θ♠s , ~D−s)∥∥∥ 2 ≤ ε. (39)
Clearly, `22, `2 and smooth-`2 are continuous regularizations, and verify R(ρ, θ) → ∞ when ‖ρ− θ‖2 → ∞. Moreover, setting δ , 1/2 shows that the probability that the dataset Ds satisfies the inequalities of Lemma 14 is positive. This implies in particular that there must be a dataset Ds that satisfies these inequalities. ALl in all, this shows that Lemma 14 implies Lemma 2.
Proof of Lemma 14. Let ε, δ > 0 and θ♠s ∈ Rd. Denote ρ♠ , ρ∗(θ♠s , ~D−s) and ~θ♠ , ~θ∗(θ♠s , ~D−s) the result of strategic user s’s model attack. We define the compact set C by
C , { ρ, ~θ−s ∣∣∣ ∥∥ρ− ρ♠∥∥ 2 ≤ ε ∧ ∀n 6= s, ∥∥θn − θ♠n ∥∥2 ≤ ε} (40) We define D , Rd×N − C the closure of the complement of C. Clearly, ρ♠, ~θ♠−s /∈ D. We aim to show that, when strategic user s reveals a large dataset Ds whose answers are provided using the attack model θ♠s , then the same holds for any global minimum of the global loss ρ
∗( ~D), ~θ∗−s( ~D) ∈ C. Note that, to prove this, it suffices to prove that the modified loss takes too large values, even when θ♠s is replaced by θ ∗ s( ~D).
Let us now formalize this. Denote L♠ , LOSSs(ρ♠, ~θ♠−s, θ ♠ s , ~D−s). We define
η , inf ρ,~θ−s∈D
LOSSs(ρ, ~θ−s, θ♠s , ~D−s)− L♠. (41)
By a similar argument as that of Lemma 5, using the assumption R → ∞ at infinity, we know that the infimum is actually a minimum. Moreover, given that the minimum of the modified loss LOSSs is unique, we know that the value of the loss function at this minimum is different from its value at ρ♠, ~θ♠−s. As a result, we must have η > 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 θs satisfying ∥∥θs − θ♠s ∥∥2 ≤ κ, we have∣∣R(θs, ρ♠)−R(θ♠s , ρ♠)∣∣ ≤ η/3. (42) Now, Lemma 5 guarantees the existence of I such that, if user s provides a dataset Ds of least I answers with the model θ♠s , then with probability at least 1 − δ, we will have ∥∥∥θ∗s( ~D)− θ♠s ∥∥∥ 2 ≤ min(κ, ε). Under this event, we then have
LOSSs ( ρ♠, ~θ♠−s, θ ∗ s( ~D), ~D−s ) ≤ L♠ + η/3. (43)
Then
inf ρ,~θ−s∈D LOSSs(ρ, ~θ−s, θ∗s( ~D), ~D−s) ≥ inf ρ,~θ−s∈D LOSSs(ρ, ~θ−s, θ♠s , ~D−s)− η/3 (44)
≥ L♠ + η − η/3 ≥ L♠ + 2η/3 (45) > LOSSs ( ρ♠, ~θ♠−s, θ ∗ s( ~D), ~D−s ) . (46)
This shows that there is a high probability event under which the minimum of ρ, ~θ−s 7→ LOSSs ( ρ, ~θ−s, θ ∗ s( ~D), ~D−s ) cannot be reached in D. This is equivalent to what the theorem we
needed to prove states.

heading: B.3 PROOF OF REDUCTION FROM MODEL ATTACK TO GRADIENT ATTACK
text: In this section, we prove a slightly more general result than Lemma 3. Namely, instead of working with specific regularizations, we consider a more general class of regularizations, identified by Assumption 1. Lemma 15 (Reduction from model attack to gradient attack). Under Assumption 1, if gts converges and if ηt = η is a constant small enough, then ρt will converge too. Denote ρ∞ its limit. Then for any ε > 0, there is θ♠s ∈ Rd such that ∥∥∥ρ∞ − ρ∗(θ♠s , ~D−s)∥∥∥ 2 ≤ ε.
Note that since `22 and smooth-`2 regularizations satisfy Assumption 1, Lemma 15 clearly implies Lemma 3. We now introduce the key objects of the proof of Lemma 15.
Denote g∞s the limit of the attack gradients g t s. We now define
LOSS1s(ρ) , inf ~θ−s
{ LOSS(ρ, ~θ, ~D)− Ls(θs,Ds)−R(ρ, θs) } + ρT g∞s (47)
= inf ~θ−s ∑ n 6=s Ln(θn,Dn) + ∑ n 6=s R(ρ, θn) + ρT g∞s , (48) and prove that ρt will converge to the minimizer of LOSS1s(ρ). By Lemma 13, we show that LOSS1s(ρ) is both locally strongly convex and L-smooth.
Now define ζts , g t s − g∞s . We then know ζts → 0 and ∇LOSS1s(ρt) is the sum of all gradient vectors received from all users assuming the strategic user s sends the vector g∞s in all iterations. Thus, at iteration t of the optimization algorithm, we will take one step in the direction Gt , ∇LOSS1s(ρt) + ζts, i.e.,
ρt+1 = ρt − ηtGt. (49)
We now prove the following lemma that bounds the difference between the function value in two successive iterations. Lemma 16. If LOSS1s(ρ) is L-smooth and ηt ≤ 1/L, we have
LOSS1s(ρ t+1)− LOSS1s(ρt) ≤ − ηt 2 ∥∥Gt∥∥2 2 + ηtζ t s T Gt. (50)
Proof. Since LOSS1s is L-smooth, we have
LOSS1s(ρ t+1) ≤ LOSS1s(ρt) + (ρt+1 − ρt)T∇LOSS1s(ρt) +
L
2
∥∥ρt+1 − ρt∥∥2 2 . (51)
Now plugging ρt+1 − ρt = −ηtGt and ∇LOSS1s(ρt) = Gt − ζts into the inequality implies
LOSS1s(ρ t+1)− LOSS1s(ρt) ≤ ( −ηtGt )T ( Gt − ζts ) + L
2 ∥∥−ηtGt∥∥22 (52) ≤ −ηt
2
∥∥Gt∥∥2 2 + ηtζ t s T Gt, (53)
where we used the fact ηt ≤ 1/L.

heading: B.3.1 THE GLOBAL MODEL REMAINS BOUNDED
text: Lemma 17. There is M such that, for all t, LOSS1s(ρt) ≤M .
Proof. Consider the closed ball B(ρ∗, 1) centered on ρ∗ and of radius 1. By Lemma 13, we know that LOSS1s is locally strongly convex and thus there exists a µ1 > 0 such that LOSS 1 s is µ1-strongly convex on B(ρ∗, 1). Now consider a point ρ1 on the boundary of B(ρ∗, 1). By strong convexity we have ∥∥∇LOSS1s(ρ1)∥∥22 ≥ (ρ1 − ρ∗)T∇LOSS1s(ρ1) ≥ µ1 ‖ρ1 − ρ∗‖22 = µ1. (54) Now similarly, by the convexity of LOSS1s on Rd, for any ρ ∈ Rd − B(ρ∗, 1), we have∥∥∇LOSS1s(ρ1)∥∥2 ≥ √µ1. Now since ζts → 0, there exists an iteration T1 after which (t ≥ T1), we have ‖ζts‖2 ≤ 1 4 √ µ1, and thus ‖Gt‖2 ≥
∥∥∇LOSS1s(ρt)∥∥2 − ‖ζts‖2 ≥ 34√µ1. Thus, Lemma 16 implies that for t ≥ T1, if ‖ρt − ρ∗‖2 ≥ 1, then
LOSS1s(ρ t+1)− LOSS1s(ρt) ≤ −
η
2
∥∥Gt∥∥2 2 + ηζts T Gt (55)
≤ −η 2 ∥∥Gt∥∥2 2 + η ∥∥ζts∥∥2 ∥∥Gt∥∥2 (56) ≤ −η 2 ∥∥Gt∥∥ 2 (∥∥Gt∥∥ 2 − 2
∥∥ζts∥∥2) (57) ≤ −η
2
3
4
√ µ1
( 3
4
√ µ1 − 2
4
√ µ1 ) ≤ −3η
32 µ1 < 0. (58)
Thus, for ‖ρt − ρ∗‖2 ≥ 1, the loss cannot increase at the next iteration. Now consider the case ‖ρt − ρ∗‖2 < 1 for t ≥ T1. The smoothness of LOSS 1 s implies∥∥∇LOSS1s(ρt)∥∥2 < L. Therefore,∥∥ρt+1 − ρ∗∥∥ 2 = ∥∥ρt − η(∇LOSS1s(ρt) + ζts)− ρ∗∥∥2 (59)
≤ ∥∥ρt+1 − ρ∗∥∥
2 + η(L+
1
4
√ µ1) ≤ 1 + η(L+ 1
4
√ µ1). (60)
Now we define M1 , maxρ∈B(ρ∗,1+η(L+ 14 √ µ1)) LOSS 1 s(ρ), the maximum function value in the closed ball B ( ρ∗, 1 + η(L+ 14 √ µ1) ) . Therefore, we have LOSS1s(ρ
t+1) ≤ M1. So far we proved that for t ≥ T1, in each iteration of gradient descent either the function value will not increase or it will be upper-bounded by M1. This implies that for all t, the function value LOSS1s(ρ
t) is upper-bounded by
M , max { max t≤T1 { LOSS1s(ρ t) } ,M1 } . (61)
This concludes the proof.
Lemma 18. There is a compact set X such that, for all t, ρt ∈ X .
Proof. Now since LOSS1s is µ1-strongly convex in B(ρ∗, 1), for any point ρ ∈ Rd such that ‖ρ− ρt‖2 = 1, we have
LOSS1s(ρ) ≥ LOSS1s(ρ∗) + µ1 2 ‖ρ− ρ∗‖22 = LOSS 1 s(ρ ∗) + µ1 2 . (62)
But now by the convexity of LOSS1s in Rd, for any ρ such that ‖ρ− ρ∗‖2 ≥ 1, we have
LOSS1s(ρ) ≥ LOSS1s(ρ∗) + ‖ρ− ρ∗‖2 µ1 2 . (63)
This implies that if ‖ρt − ρ∗‖2 > 2 µ1 ( M2 − LOSS1s(ρ∗) ) , then LOSS1s(ρ
t) > M2. Therefore, we must have ‖ρt − ρ∗‖2 ≤ 2 µ1 ( M2 − LOSS1s(ρ∗) ) , for all t ≥ 0. This describes a closed ball, which is a compact set.

heading: B.3.2 CONVERGENCE OF THE GLOBAL MODEL UNDER CONVERGING GRADIENT ATTACK
text: Lemma 19. Suppose ut ≥ 0 verifies ut+1 ≤ αut + δt, with δt → 0. Then ut → 0.
Proof. We now show that for any ε > 0, there exists an iteration T (ε), such that for t ≥ T (ε), we have ut ≤ ε. For this, note that by induction, we observe that, for all t ≥ 0,
ut+1 ≤ u0αt+1 + t∑
τ=0
ατδt−τ . (64)
Since δt → 0, there exists an iteration T2(ε) such that for all t ≥ T2(ε), we have δt ≤ ε(1−α)2 . Therefore, for t ≥ T2(ε), we have
ut+1 ≤ u0αt+1 + t−T2(ε)∑ τ=0 ατδt−τ + t∑ τ=t−T2(ε)+1 ατδt−τ (65)
≤ u0αt+1 + ε(1− α)
2
t−T2(ε)∑ τ=0 ατ + T2(ε)−1∑ s=0 αt−sδs (66)
≤ u0 + T2(ε)−1∑ s=0 α−s−1δs αt+1 + ε(1− α) 2 ∞∑ τ=0 ατ . (67)
Denoting M0(ε) , ∑T2(ε)−1 s=0 α −s−1δs, we then have
ut+1 ≤ (u0 +M0(ε))αt+1 + ε
2 . (68)
Therefore, for t ≥ ln ε 2(u0+M0(ε))
lnα , we have
ut+1 ≤ ε 2 + ε 2 = ε. (69)
This proves that ut → 0.
We first prove the first part of Lemma 3.
Lemma 20. Under Assumption 1 and ηt = η ≤ 1/L, if gts converges, then so does ρt.
Proof. Define X based on Lemma 18. Since LOSS1s is locally strongly convex, there exists µ2 > 0 such that LOSS1s is µ2-strongly convex in a convex compact set X containing ρ
t for all t ≥ 0. By the strong convexity of LOSS1s(ρ), we have
LOSS1s(ρ t)− LOSS1s(ρ∗) ≤ (ρt − ρ∗)T∇LOSS1s(ρt)− µ2 2 ∥∥ρt − ρ∗∥∥2 2
(70) = (ρt − ρ∗)T ( Gt − ζts ) − µ2
2
∥∥ρt − ρ∗∥∥2 2 . (71)
Now, using the fact
(ρt − ρ∗)TGt = 1 η (ρt − ρ∗)T (ρt − ρt+1) (72)
= 1
2η
(∥∥ρt − ρ∗∥∥2 2 + ∥∥ρt − ρt+1∥∥2 2 − ∥∥ρt+1 − ρ∗∥∥2 2 ) (73)
= 1
2η
( η2 ∥∥Gt∥∥2 2 + ∥∥ρt − ρ∗∥∥2 2 − ∥∥ρt+1 − ρ∗∥∥2 2 ) (74)
= η
2
∥∥Gt∥∥2 2 + 1
2η
(∥∥ρt − ρ∗∥∥2 2 − ∥∥ρt+1 − ρ∗∥∥2 2 ) , (75)
we have LOSS1s(ρ
t)− LOSS1s(ρ∗) ≤ (76) η
2
∥∥Gt∥∥2 2 + 1
2η
(∥∥ρt − ρ∗∥∥2 2 − ∥∥ρt+1 − ρ∗∥∥2 2 ) − (ρt − ρ∗)T ζts − µ2 2 ∥∥ρt − ρ∗∥∥2 2 . (77)
But now note that LOSS1s(ρ t)−LOSS1s(ρ∗) ≥ LOSS1s(ρt)−LOSS1s(ρt+1). Thus, combining Equation (77) and Lemma 16 yields
− ηζts T Gt ≤ 1
2η
(∥∥ρt − ρ∗∥∥2 2 − ∥∥ρt+1 − ρ∗∥∥2 2 ) − (ρt − ρ∗)T ζts − µ2 2 ∥∥ρt − ρ∗∥∥2 2 . (78)
By rearranging the terms, we then have∥∥ρt+1 − ρ∗∥∥2 2 ≤ (1− µ2η) ∥∥ρt − ρ∗∥∥2 2 − η ( ρt+1 − ρ∗ )T ζts (79)
≤ (1− µ2η) ∥∥ρt − ρ∗∥∥2
2 + η ∥∥ρt+1 − ρ∗∥∥ 2 ∥∥ζts∥∥2 . (80) Now note that η ≤ 1/L < 1/µ2 and thus 0 < 1 − µ2η < 1. We now define two sequences ut , ‖ρt − ρ∗‖2 and δt = η ‖ζts‖2. We already know that δt → 0, and we want to show ut also converges to 0. By Equation (80), we have
u2t+1 ≤ (1− ηµ2)u2t + δtut+1, (81) which implies (
ut+1 − δt 2
)2 = u2t+1 − ut+1δt +
δ2t 4 ≤ (1− ηµ2)u2t + δ2t 4 , (82)
and thus ut+1 ≤ √
(1− ηµ2)u2t + δ2t 4 + δt 2 ≤ √ (1− ηµ2)u2t + δt 2 + δt 2 ≤ ( 1− ηµ2 2 ) ut + δt. (83)
Lemma 19 allows to conclude.

heading: B.3.3 REDUCTION FROM MODEL ATTACK TO CONVERGING GRADIENT ATTACK
text: 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 ε > 0, there exists θ♠s ∈ Rd such that ∥∥∥ρ∞ − ρ∗(θ♠s , ~D−s)∥∥∥
2 ≤ ε. We define
LOSS2s(ρ, θs) , inf ~θ−s
{ LOSS(ρ, ~θ, ~D)− Ls(θs,Ds) } (84)
= LOSS1s(ρ) +R(ρ, θs)− ρT g∞s , (85) and ρ∗(θs), its minimizer. Therefore, we have ∇ρLOSS2s(ρ, θs) = ∇ρLOSS1s(ρ) +∇ρR(ρ, θs)− g∞s . (86) By Lemma 13, we know that LOSS2s is locally strongly convex. Therefore, there exists µ3 > 0 such that LOSS2s(ρ) is µ3-strongly convex in {ρ| ‖ρ− ρ∗(θs)‖2 ≤ 1}. Therefore, for any 0 < ε < 1, if ‖ρ∞ − ρ∗(θs)‖2 > ε, we then have
ε ∥∥∇ρLOSS2s(ρ∞, θ♠s )∥∥2 ≥ (ρ∞ − ρ∗(θs))T∇ρLOSS2s(ρ∞, θ♠s ) (87)
≥ µ3 ‖ρ∞ − ρ∗(θs)‖22 = µ3 ≥ µ3ε 2, (88) and thus ∥∥∇ρLOSS2s(ρ∞, θ♠s )∥∥2 ≥ µ3ε.
Now since g∞s ∈ GRAD(ρ∞) there exists θ♠s ∈ Rd such that3 ∥∥∇ρR(ρ∞, θ♠s )− g∞s ∥∥2 ≤ µ3ε2
which yields ∥∥∇ρLOSS2s(ρ∞, θ♠s )∥∥2 = ∥∥∇ρLOSS1s(ρ∞) +∇ρR(ρ∞, θ♠s )− g∞s ∥∥2 (89) = ∥∥∇ρR(ρ∞, θ♠s )− g∞s ∥∥2 ≤ µ3ε2 , (90)
which is a contradiction. Therefore, we must have ∥∥∥ρ∞ − ρ∗(θ♠s , ~D−s)∥∥∥
2 ≤ ε.
3In fact, if g∞s belongs to the interior of GRAD(ρ∞), we can guarantee ∇ρR(ρ∞, θ♠s ) = g∞s .

heading: C SUM OVER EXPECTATIONS
text: In this section, we provide both theoretical and empirical results to argue for using a sum-based local loss over an expectation-based local loss.

heading: C.1 THEORETICAL ARGUMENTS
text: Indeed, intuitively, if one considers an expectation Ex∼Dn [`(θn, x)] rather than a sum, as is done by Hanzely et al. (2020), Dinh et al. (2020) and El-Mhamdi et al. (2021), then the weight of an honest active user’s local loss will not increase as a node provides more and more data, which will hinder the ability of θn 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 a much larger dataset Dn 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 a Bayesian negative log-posterior, given a prior exp ( − ∑ n∈[N ] ν ‖θn‖2 − ∑ n∈[N ]R(ρ, θn) ) on the local and global models, then the term that
fits local data should equal the negative log-likelihood of the data, given the models (ρ, ~θ). Assuming that the distribution of each data point x ∈ Dn is independent from all other data points, and depends only on the local model θn, this negative log-likelihood yields a sum over data points; not an expectation.

heading: C.2 EMPIRICAL RESULTS
text: We also empirically compared the performances of sum as opposed to the expectation. To do so, we 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(ρ, θ) , λ ‖ρ− θ‖22, λ = 1. We compared two different classifiers to which we refer as a “linear model” and “2-layers neural network”, both using CrossEntropy loss. The linear model has (784+1)×10 parameters. The neural network has 2 layers of 784 parameters with bias, with ReLU activation in between, adding up to ((784 + 1) × 784 + (784 + 1)× 10.
Note also that, in all our experiments, we did not consider any local regularization, i.e. we set ν , 0. All our experiments are seeded with seed 999.

heading: C.2.1 NOISY FASHIONMNIST
text: To see a strong difference between sum and average, we made the FashionMNIST dataset harder to learn, by randomly labeling 60% of the training set. Table 1 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.
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 1, 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.
In the case of learning FashionMNIST, given that the data is i.i.d., larger values of λ are 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 a common value of λ in both cases is slightly misleading, as using the sum intuitively decreases the comparative weight of the regularization term. To reduce this effect, for this experiment only, we 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 to robustly show that using the sum consistently outperforms the expectation, for both a linear classifier and a 2-layer neural network, for the problem of noisy FashionMNIST classification.

heading: C.2.2 FASHIONMNIST WITHOUT NOISE
text: Recall that we introduced noise into FashionMNIST to make the problem harder to learn and observe a clear difference between the average and the sum. In this section, we present results of our experiments when the noise is removed.
Even without noise, the difference between using the sum 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 in the absence of noise is weak is due to the fact that the FashionMNIST dataset is sufficiently linearly separable. Thus, we achieve a 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 of 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 it can catch the signal of the active node’s data and hence the average achieves weaker convergence performances than the sum.

heading: D LINEAR REGRESSION AND CLASSIFICATION ARE GRADIENT PAC*
text: Throughout this section, we use the following terminology.
Definition 5. Consider a parameterized event E(I). We say that the event E occurs with high probability if P [E(I)]→ 1 as I → ∞.

heading: D.1 PRELIMINARIES
text: Define ‖Σ‖2 , max‖x‖2 6=0(‖Σx‖2 / ‖x‖2) the `2 operator norm of the matrix Σ. For symmetric matrices Σ, this is also the largest eigenvalue in absolute value. Theorem 6 (Covariance concentration, Theorem 6.5 in Wainwright (2019)). Denote Σ = E [ QiQTi ] , where Qi ∈ Rd is from a σQ -sub-Gaussian random distribution Q̃. Then, there are universal constants c1, c2 and c3 such that, for any set {Qi}i∈[I] of i.i.d. samples from Q̃, and any δ > 0, the sample covariance Σ̂ = 1I ∑ QiQTi satisfies the bound
P
[ 1
σ2Q
∥∥∥Σ̂− Σ∥∥∥ 2 ≥ c1 (√ d I + d I ) + δ ] ≤ c2 exp ( −c3Imin(δ, δ2) ) . (91)
Theorem 7 (Weyl’s Theorem, Theorem 4.3.1 in Horn & Johnson (2012)). Let A and B be Hermitian4 and let the respective eigenvalues of A and B and A + B be {λi(A)}di=1, {λi(B)}di=1, and
4For real matrices, Hermitian is the same as symmetric.
{λi(A+B)}di=1, each increasingly ordered. Then λi(A+B) ≤ λi+j(A) + λd−j(B), j = 0, 1, ..., d− i, (92)
and λi+j(A) + λj+1(B) ≤ λi(A+B), j = 0, ..., i− 1, (93)
for each i = 1, ..., d. Lemma 21. Consider two symmetric definite positive matrices S and Σ. Denote ρmin and λmin their minimal eigenvalues. Then |ρmin − λmin| ≤ ‖S − Σ‖2.
Proof. This is a direct consequence of Theorem 7, for A = S, B = Σ− S, i = 1, and j = 0.
Corollary 1. There are universal constants c1, c2 and c3 such that, for any σQ -sub-Gaussian vector distribution Q̃ ∈ Rd and any δ > 0, the sample covariance Σ̂ = 1I ∑ QiQTi satisfies the bound
P
[ 1
σ2Q
∣∣∣min SP(Σ̂)−min SP(Σ)∣∣∣ ≥ c1(√ dI + dI ) + δ ] ≤ c2 exp ( −c3Imin(δ, δ2) ) , (94)
where min SP(Σ̂) and min SP(Σ) are the minimal eigenvalues of Σ̂ and Σ.
Proof. This follows from Theorem 6 and Lemma 21.
Lemma 22. With high probability, min SP(Σ̂) ≥ min SP(Σ)/2.
Proof. Denote λmin , min SP(Σ) and λ̂min , min SP(Σ̂). Since each Qi is drawn i.i.d. from a σQ -sub-Gaussian, we can apply Corollary 1. Namely, there are constants c1, c2 and c3, such that for any δ > 0, we have
P [∣∣∣λ̂min − λmin∣∣∣ ≥ c1σ2Q (√ d
I + d I
) + δσ2Q ] ≤ c2 exp (−c3Imin { δ, δ2 } ). (95)
We now set δ , λmin/(4σ2Q) and we consider I large enough so that c1 (√ d I + d I ) ≤
λmin/(4σ 2 Q). With high probability, we then have λ̂min ≥ λmin/2.

heading: D.2 LINEAR REGRESSION IS GRADIENT-PAC*
text: In this section, we prove the first part of Lemma 4. Namely, we prove that linear regression is gradient-PAC* learning.

heading: D.2.1 LEMMAS FOR LINEAR REGRESSION
text: Before moving to the main proof that linear regression is gradient-PAC*, we first prove a few useful lemmas. These lemmas will rest on the following well-known theorems. Theorem 8 (Lemma 2.7.7 in Vershynin (2018)). If X and Y are sub-Gaussian, then XY is subexponential. Theorem 9 (Equation 2.18 in Wainwright (2019)). IfX1, . . . , XI are iid sub-exponential variables, then there exist constants c4, c5 such that, for all I, we have
∀t ∈ [0, c4], P [|X − E [X]| ≥ tI] ≤ 2 exp ( −c5It2 ) . (96)
Lemma 23. For all j ∈ [d], the random variables Xi , ξiQi[j] are iid, sub-exponential and have zero mean.
Proof. The fact that these variables are iid follows straightforwardly from the fact that the noises ξi are iid, and the queries Qi are also iid. Moreover, both are sub-Gaussian, and by Theorem 8, the product of sub-Gaussian variables is sub-exponential. Finally, we have E [X] = E [ξQ[j]] = E [ξ]E [Q[j]] = 0, using the independence of the noise and the query, and the fact that noises have zero mean (E [ξ] = 0).
Lemma 24. There exists B such that ∥∥∑ i∈I ξiQi ∥∥ 2 ≤ BI3/4 with high probability.
Proof. By Lemma 23, the terms ξiQi[j] are iid, sub-exponential and have zero mean. Therefore, by Theorem 9, there exist constants c4 and c5 such that for any coordinate j ∈ [d] of ξiQi and for all 0 ≤ u ≤ c4, we have
P [∣∣∣∣∣∑ i∈I ξiQi[j] ∣∣∣∣∣ ≥ Iu ] ≤ 2 exp (−c5Iu2). (97)
Plugging u = vI(−1/4) into the inequality for some small enough constant v, and using union bound then yields
P ∥∥∥∥∥∑ i∈I ξiQi ∥∥∥∥∥ 2 ≥ I(3/4)v √ d  ≤ P ∥∥∥∥∥∑ i∈I ξiQi ∥∥∥∥∥ ∞ ≥ I(3/4)v  ≤ 2d exp (−c5√Iv2). (98) Defining B , v √ d yields the lemma.

heading: D.2.2 PROOF THAT LINEAR REGRESSION IS GRADIENT-PAC*
text: We now move on to proving that least square linear regression is gradient-PAC*.
Proof of Theorem 2. Note that∇θ`(θ,Q,A) = (θTQ −A)Q. Thus, on input i ∈ [I], we have
∇θ`(θ,Qi,A(Qi, θ†)) = ( (θ − θ†)TQi ) Qi − ξiQi. (99)
Moreover, we have (θ − θ†)T∇θ ( ν ‖θ‖22 ) = 2ν(θ − θ†)T θ = 2ν ∥∥θ − θ†∥∥2 2 + 2ν(θ − θ†)T θ†. (100)
As a result, we have
(θ − θ†)T∇θL(θ,D) = (101) I(θ − θ†)T Σ̂(θ − θ†)− (θ − θ†)T (∑ i∈I ξiQi ) + 2ν ∥∥θ − θ†∥∥2 2 + 2ν(θ − θ†)T θ†. (102)
But now, with high probability, we have (θ−θ†)T Σ̂(θ−θ†) ≥ (λmin/2) ∥∥θ − θ†∥∥2
2 (Lemma 22) and∥∥∑ i∈I ξiQi ∥∥ 2 ≤ BI(3/4) (Lemma 24). Using the fact that ∥∥θ†∥∥ 2 ≤ K and the Cauchy-Schwarz inequality, we have
(θ − θ†)T∇θL(θ,D) ≥ ( λmin
2 I + ν)
∥∥θ − θ†∥∥2 2 − (BI(3/4) + 2νK) ∥∥θ − θ†∥∥ 2 . (103)
Denoting AK , λmin2 and BK , B + 2νK and using the fact that I ≥ 1, we then have
(θ − θ†)T∇θL(θ,D) ≥ AKI ∥∥θ − θ†∥∥2
2 −BKI(3/4) ∥∥θ − θ†∥∥ 2
(104) ≥ AKImin {∥∥θ − θ†∥∥ 2 , ∥∥θ − θ†∥∥2 2 } −BKI(3/4) ∥∥θ − θ†∥∥ 2 , (105)
with high probability. This corresponds to saying Assumption 2 is satisfied for α = 3/4.

heading: D.3 LOGISTIC REGRESSION
text: In this section, we now prove the second part of Lemma 4. Namely, we prove that logistic regression is gradient-PAC* learning.

heading: D.3.1 LEMMAS ABOUT THE SIGMOID FUNCTION
text: We first prove two useful lemmas about the following logistic distance function.
Definition 6. We define the logistic distance function by ∆(a, b) , (a− b) (σ(a)− σ(b)). Lemma 25. If a, b ∈ R such that for some k > 0, |a| ≤ k and |b| ≤ k, then there exists some constant ck > 0 such that
∆(a, b) ≥ ck |a− b|2 . (106)
Proof. Note that the derivative of σ(z) is strictly positive, symmetric (σ′(z) = σ′(−z)) and monotonically decreasing for z ≥ 0. Therefore, for any z ∈ [−k, k], we know σ′(z) ≥ ck , σ′(k). Thus, by the mean value theorem, we have
σ(a)− σ(b) a− b ≥ ck. (107)
Multiplying both sides by (a− b)2 then yields the lemma.
Lemma 26. If b ∈ R, and |b| ≤ k, for some k > 0, then there exists a constant dk, such that for any a ∈ R, we have
∆(a, b) ≥ dk |a− b| − dk (108)
Proof. Assume |a− b| ≥ 1 and define dk , σ(k + 1) − σ(k). If b ≥ 0, since σ′(z) is decreasing for z ≥ 0, we have σ(b)− σ(b− 1) ≥ σ(b+ 1)− σ(b) ≥ dk, and by symmetry, a similar argument holds for b ≤ 0. Thus, we have
|σ(a)− σ(b)| ≥ min {σ(b)− σ(b− 1), σ(b+ 1)− σ(b)} ≥ dk. (109)
Therefore, (a− b) (σ(a)− σ(b)) ≥ dk |a− b| ≥ dk |a− b| − dk. (110)
For the case of |a− b| ≤ 1, we also have (a− b) (σ(a)− σ(b)) ≥ 0 ≥ dk |a− b| − dk.

heading: D.3.2 A UNIFORM LOWER BOUND
text: Definition 7. Denote Sd−1 , { u ∈ Rd ∣∣ ‖u‖2 = 1} the hypersphere in Rd. Lemma 27. Assume SUPP(Q̃) spans Rd. Then, for all u ∈ Sd−1, E
[∣∣QTu∣∣] > 0. Proof. Let u ∈ Sd−1. We know that there exists Q1, . . . ,Qd ∈ SUPP(Q̃) and α1, . . . , αd ∈ R such that u is colinear with ∑ αjQj . In particular, we then have uT ∑ αjQj = ∑ αj(QTj u) 6= 0.
Therefore, there must be a queryQ∗ ∈ SUPP(Q̃) such thatQT∗ u 6= 0, which implies a , ∣∣QT∗ u∣∣ > 0 By continuity of the scalar product, there must then also exist ε > 0 such that, for any Q ∈ B(Q∗, ε), we have
∣∣QTu∣∣ ≥ a/2, where B(Q∗, ε) is an Euclidean ball centered onQ∗ and of radius ε.
But now, by definition of the support, we know that p , P [Q ∈ B(Q∗, ε)] > 0. By the law of total expectation, we then have
E [∣∣QTu∣∣] = E [∣∣QTu∣∣ ∣∣Q ∈ B(Q∗, ε)]P [Q ∈ B(Q∗, ε)]
+ E [∣∣QTu∣∣ ∣∣Q /∈ B(Q∗, ε)]P [Q /∈ B(Q∗, ε)] (111)
≥ ap/2 + 0 > 0, (112)
which is the lemma. Lemma 28. Assume that, for all unit vectors u ∈ Sd−1, we have E [∣∣QTu∣∣] > 0, and that SUPP(Q̃) is bounded by MQ . Then there exists C > 0 such that, with high probability,
∀u ∈ Sd−1, ∑ i∈I ∣∣QTi u∣∣ ≥ CI. (113)
Proof. By continuity of the scalar product and the expectation operator, and by compactness of Sd−1, we know that
C0 , inf u∈Rd
E [∣∣QTu∣∣] > 0. (114)
Now define ε , C0/4MQ . Note that Sd−1 ⊂ ⋃
u∈Sd−1 B(u, ε). Thus we have a covering of the hypersphere by open sets. But since Sd−1 is compact, we know that we can extract a finite covering. In other words, there exists a finite subset S ⊂ Sd−1 such that Sd−1 ⊂ ⋃ u∈S B(u, ε). Put differently, for any v ∈ Sd−1, there exists u ∈ S such that ‖u − v‖2 ≤ ε.
Now consider u ∈ S. Given that SUPP(Q̃) is bounded, we know that ∣∣QTi u∣∣ ∈ [0,MQ ]. Moreover,
such variables ∣∣QTi u∣∣ are iid. By Hoeffding’s inequality, for any t > 0, we have
P [∣∣∣∣∣∑ i∈I ∣∣QTi u∣∣− IE [∣∣QT u∣∣] ∣∣∣∣∣ ≥ It ] ≤ 2 exp ( −2It2 MQ ) . (115)
Choosing t = C0/2 then yields
P [∑ i∈I ∣∣QTi u∣∣ ≤ C0I2 ] ≤ P [∣∣∣∣∣∑ i∈I ∣∣QTi uθ−θ†∣∣− IE [∣∣QT uθ−θ†∣∣] ∣∣∣∣∣ ≥ IC02 ] (116)
≤ 2 exp ( −IC02
2MQ
) . (117)
Taking a union bound for u ∈ S then guarantees
P [ ∀u ∈ S,
∑ i∈I ∣∣QTi u∣∣ ≥ C0I2 ] ≥ 1− 2 |S| exp ( −IC02 2MQ ) , (118)
which clearly goes to 1 as I → ∞. Thus ∀u ∈ S, ∑ i∈I ∣∣QTi u∣∣ ≥ C0I2 holds with high probability.
Now consider v ∈ Sd−1. We know that there exists u ∈ S such that ‖u − v‖2 ≤ ε. Then, we have∑ i∈[I] ∣∣QTi v∣∣ = ∑ i∈[I] ∣∣QTi u +QTi (v − u)∣∣ (119) ≥ ∑ i∈[I]
∣∣QTi u∣∣− IMQ ‖v − u‖2 (120) ≥ C0I
2 − IMQ C0 4MQ = C0I 4 , (121)
which proves the lemma.

heading: D.3.3 LOWER BOUND ON THE DISCREPANCY BETWEEN PREFERRED AND REPORTED ANSWERS
text: Lemma 29. Assume that Q̃ has a bounded support, whose interior contains the origin. Suppose also that ∥∥θ†∥∥ 2 ≤ K. Then there exists AK such that, with high probability, we have∑
i∈[I]
∆(QTi θ,QTi θ†) ≥ AKImin {∥∥θ − θ†∥∥ 2 , ∥∥θ − θ†∥∥2 2 } . (122)
Proof. Note that by Cauchy-Schwarz inequality we have∣∣QTi θ†∣∣ ≤ ‖Qi‖2 ∥∥θ†∥∥2 ≤MQK. (123) Thus, Lemma 26 implies the existence of a positive constant dK, such that for all θ ∈ Rd, we have∑
i∈I ∆ ( QTi θ,QTi θ† ) ≥ ∑ i∈I ( dK ∣∣QTi θ −QTi θ†∣∣− dK) (124)
= −dKI + dK ∥∥θ − θ†∥∥
2 ∑ i∈I ∣∣QTi uθ−θ† ∣∣ , (125)
where uθ−θ† , (θ − θ†)/ ∥∥θ − θ†∥∥ 2 is the unit vector in the direction of θ − θ†. Now, by Lemma 28, we know that, with high probability, for all unit vectors u ∈ Sd−1, we have∑∣∣QTi u∣∣ ≥ CI. Thus, for I sufficiently large, for any θ ∈ Rd, with high probability, we have ∑ i∈I ∆(QTi θ,QTi θ†) ≥ dKCmin 2 I ∥∥θ − θ†∥∥ 2 − dKI. (126)
Defining eK , dKCmin4 , and fK , 4 Cmin , for ∥∥θ − θ†∥∥ 2 > fK, we then have∑
i∈I ∆(QTi θ,QTi θ†) ≥ eKI
∥∥θ − θ†∥∥ 2 . (127)
We now focus on the case of ∥∥θ − θ†∥∥
2 ≤ fK. The triangle inequality yields ‖θ‖2 ≤ ∥∥θ − θ†∥∥ 2
+∥∥θ†∥∥ 2 ≤ fK +K. By Cauchy-Schwarz inequality, we then have ∣∣QTi θ∣∣ ≤ (fK +K)MQ , gK and∣∣QTi θ†∣∣ ≤ KMQ ≤ gK. Thus, by Lemma 25, we know there exists some constant cK such that∑ i∈I ( σ(QTi θ)− σ(QTi θ†) ) (QTi θ −QTi θ†) ≥ ∑ i∈I cK ∣∣QTi θ −QTi θ†∣∣2 (128)
= ∑ i∈I cK(θ − θ†)TQiQTi (θ − θ†) (129)
= cK(θ − θ†)T (∑ i∈I QiQTi ) (θ − θ†). (130)
Since distribution Q̃ is bounded (and thus sub-Gaussian), by Theorem 6, with high probability, we have
(θ − θ†)T (∑ i∈I QiQTi ) (θ − θ†) ≥ λmin 2 I ∥∥θ − θ†∥∥2 2 , (131)
where λmin is the smallest eigenvalue of E [ QiQTi ] . Thus, for ∥∥θ − θ†∥∥ 2 ≤ fK, we have
∑ i∈I ( σ(QTi θ)− σ(QTi θ†) ) (QTi θ −QTi θ†) ≥ λmincK 2 I ∥∥θ − θ†∥∥2 2 . (132)
Combining this with (127), and defining AK , min { λmincK 2 , eK } , we then obtain the lemma.

heading: D.3.4 PROOF THAT LOGISTIC REGRESSION IS GRADIENT-PAC*
text: Now we proceed with the proof that logistic regression is gradient-PAC*.
Proof of Theorem 3. Note that σ(−z) = e−zσ(z) = 1−σ(z) and σ′(z) = e−zσ2(z). We then have
∇θ`(θ,Q,A) = − σ′(AQT θ)AQ σ(AQT θ) = −e−AQ T θσ(AQT θ)AQ (133)
= −σ(−AQT θ)AQ = ( σ(QT θ)− 1 [A = 1] ) Q, (134)
where 1 [A = 1] is the indicator function that outputs 1 if A = 1, and 0 otherwise. As a result,
(θ − θ†)T∇θL(θ,D) = (135) (θ − θ†)T (∑ i∈I ( σ(QTi θ)− 1 [Ai = 1] ) Qi ) + 2ν(θ − θ†)T θ (136)
= (θ − θ†)T (∑ i∈I ( σ(QTi θ)− σ(QTi θ†) + σ(QTi θ†)− 1 [Ai = 1] ) Qi ) (137)
+ 2ν ∥∥θ − θ†∥∥2
2 + 2ν(θ − θ†)T θ† (138)
= ∑ i∈[I] ∆ ( QTi θ,QTi θ† ) + (θ − θ†)T (∑ i∈I ( σ(QTi θ†)− 1 [Ai = 1] ) Qi ) (139)
+ 2ν ∥∥θ − θ†∥∥2
2 + 2ν(θ − θ†)T θ†. (140)
By Lemma 29, with high probability, we have∑ i∈[I] ∆ ( QTi θ,QTi θ† ) ≥ AKImin {∥∥θ − θ†∥∥ 2 , ∥∥θ − θ†∥∥2 2 } . (141)
To control the second term of (139), note that the random vectors Zi , ( σ(QTi θ†)− 1 [Ai = 1] ) Qi are iid with norm at most MQ . Moreover, since E [1 [Ai = 1] |Qi] = σ(QTi θ†), by the tower rule, we have E [Zi] = E [E [Zi|Qi]] = 0. Therefore, by applying Hoeffding’s bound to every coordinate of Zi, and then taking a union bound, for any B > 0, we have
P ∥∥∥∥∥∑ i∈I Zi ∥∥∥∥∥ 2 ≥ BI3/4  ≤ 2d exp(−B2√I 2dM2Q ) . (142)
Applying now Cauchy-Schwarz inequality, with high probability, we have∣∣∣∣∣(θ − θ†)T (∑ i∈I ( σ(QTi θ†)− 1 [Ai = 1] ) Qi )∣∣∣∣∣ ≤ BI3/4 ∥∥θ − θ†∥∥2 . Combining this with (132) and using ∥∥θ†∥∥2 2 ≤ K, we then have
(θ − θ†)T∇θL(θ,D) (143) ≥ (AKI + ν) {∥∥θ − θ†∥∥ 2 , ∥∥θ − θ†∥∥2 2 } − (BI(3/4) + 2νK) ∥∥θ − θ†∥∥ 2 (144)
≥ AKI {∥∥θ − θ†∥∥ 2 , ∥∥θ − θ†∥∥2 2 } −BKI(3/4) ∥∥θ − θ†∥∥ 2 , (145)
where BK = B + 2νK. This shows that Assumption 2 is satisfied for logistic loss for α = 3/4, and AK and BK as previously defined.

heading: E PROOFS OF LOCAL PAC*-LEARNABILITY
text: Let us now prove Lemma 5. To do so, consider the preferred models ~θ† and a subset H ⊂ [N ] of honest users. Denote ~D−H the datasets provided by users n ∈ [N ] − H . Each honest user h ∈ H provides an honest dataset Dh of cardinality at least I ≥ 1. Consider the bound KH , maxh∈H ∥∥∥θ†h∥∥∥ 2 on the parameter norm of honest active users h ∈ H .

heading: E.1 BOUNDS ON THE OPTIMA
text: Before proving the theorem, we prove a useful lemma that bounds the set of possible values for the global model and honest local models.
Lemma 30. Assume that R and ` are nonnegative. For I large enough, if all honest active nodes h ∈ H provide at least I data, then, with high probability, ~θ∗H must lie in a compact subset of Rd×H that does not depend on I.
Proof. Denote L0 , LOSS(0, (~θ†H , 0−H), (∅, ~D−H)). Essentially, we will show that, if ~θ∗H is too far from ~θ†H , then the loss will take values strictly larger than L 0.
Assumption 2 implies the existence of an event E that occurs with probability at least P0 , P (KH , I)|H|, under which, for any θh ∈ Rd, we have( θh − θ†h )T ∇Lh (θh) ≥ AKHImin {∥∥∥θh − θ†h∥∥∥ 2 , ∥∥∥θh − θ†h∥∥∥2 2 } −BKHIα ∥∥∥θh − θ†h∥∥∥ 2 , (146)
which implies
uT (θh−θ†h)
∇Lh (θh) ≥ AKHImin { 1, ∥∥∥θh − θ†h∥∥∥
2
} −BKHIα. (147)
Note also that P0 → 1 as I → ∞. We now integrate both sides over the line segment from θ†h to θh. The fundamental theorem of calculus for line integrals then yields
Lh (θh)− Lh ( θ†h ) = ∥∥∥θh − θ†h∥∥∥
2 ∫ 1 t=0 uT (θh−θ†h) ∇L ( θ†h + t(θh − θ † h) ) dt (148)
≥ ∥∥∥θh − θ†h∥∥∥
2 ∫ 1 t=0 ( AKHImin { 1, t ∥∥∥θh − θ†h∥∥∥ 2 } −BKHIα ) dt (149)
= ∥∥∥θh − θ†h∥∥∥
2 ∫ 1 t=0 ( AKHImin { 1, t ∥∥∥θh − θ†h∥∥∥ 2 }) dt−BKHIα ∥∥∥θh − θ†h∥∥∥ 2 . (150)
Now, if ∥∥∥θh − θ†h∥∥∥
2 > 2, we then have
Lh (θh)− Lh ( θ†h ) ≥ ( AKHI
2 −BKHIα )∥∥∥θh − θ†h∥∥∥ 2
(151)
≥ AKHI − 2BKHIα. (152)
Now for I > I1 , max { 2L0/AKH , (4BKH/AKH ) 1 1−α } , we have
Lh (θh)− Lh ( θ†h ) > L0. (153)
This implies that if ∥∥∥θh − θ†h∥∥∥
2 > 2 for any h ∈ H , then we have
LOSS(0, (~θ†H , 0−H), ~D) < LOSS(ρ, (~θH , ~θ−H), ~D), (154)
regardless of ρ and θ−H . Therefore, we must have ∥∥∥θ†h − θ∗h∥∥∥
2 ≤ 2. Such inequalities describe a
bounded closed subset of Rd×H , which is thus compact. Lemma 31. Assume thatR(ρ, θ)→∞ as ‖ρ− θ‖2 →∞, and that ∥∥∥θ†h − θ∗h∥∥∥
2 ≤ 2 for all honest
users h ∈ H . Then ρ∗ must lie in a compact subset of Rd that does not depend on I.
Proof. Consider an honest user h′. Given our assumption on R → ∞, we know that there exists DKH such that if ‖ρ− θ∗h′‖2 ≥ DKH , thenR(ρ, θ ∗ h′) ≥ L0 + 1. Thus any global optimum ρ∗ must
satisfy ∥∥∥ρ∗ − θ†h′∥∥∥
2 ≤ ‖ρ∗ − θ∗h′‖2 + ∥∥∥θ∗h′ − θ†h′∥∥∥ 2 ≤ DKH + 2.

heading: E.2 PROOF OF LEMMA 5
text: Proof of Lemma 5. Fix ε, δ > 0. We want to show the existence of some value of I(ε, δ, ~D−H , ~θ†) that will guarantee (ε, δ)-locally PAC* learning for honest users.
By lemmas 30 and 31, we know that the set C of possible values for (ρ∗, ~θ∗H) is compact. Now, we define
EKH , max (ρ,θ)∈C ‖∇θR(ρ, θ)‖2 (155)
the maximum of the norm of achievable gradients at the optimum. We know this maximum exists since C is compact.
Using the optimality of (ρ∗, ~θ∗), for all h ∈ H , we have
0 ∈ (θ∗h − θ † h) T∇θhLOSS(ρ∗, ~θ∗) (156)
= (θ∗h − θ † h) T∇Lh(θ∗h) + (θ∗h − θ † h) T∇θhR(ρ∗, θ∗h) (157)
≥ (θ∗h − θ † h) T∇Lh(θ∗h)− ∥∥∥θ∗h − θ†h∥∥∥ 2 ‖∇θhR(ρ∗, θ∗h)‖2 (158)
≥ (θ∗h − θ † h) T∇Lh(θ∗h)− EKH ∥∥∥θ∗h − θ†h∥∥∥ 2 . (159)
We now apply assumption 2 for θ = θ∗h (for h ∈ H). Thus, there exists some other event E ′ with probability at least P0, under which, for all h ∈ H , we have
0 ≥ AKHImin {∥∥∥θ∗h − θ†h∥∥∥ 2 , ∥∥∥θ∗h − θ†h∥∥∥2 2 } −BKHIα ∥∥∥θ∗h − θ†h∥∥∥ 2 − EKH ∥∥∥θ∗h − θ†h∥∥∥ 2 . (160)
Now if I > I2 , max { 2EKH/AKH , (2BKH/AKH ) 1 1−α } this inequality cannot hold for∥∥∥θ∗h − θ†h∥∥∥
2 ≥ 1. Therefore, for I > I2, we have ∥∥∥θ∗h − θ†h∥∥∥ 2 < 1, and thus,
0 ≥ AKHI ∥∥∥θ∗h − θ†h∥∥∥2
2 −BKHIα ∥∥∥θ∗h − θ†h∥∥∥ 2 − EKH ∥∥∥θ∗h − θ†h∥∥∥ 2
(161)
and thus, ∥∥∥θ∗h − θ†h∥∥∥ 2 ≤ BKHI α + EKH AKHI . (162) Now note that P [E ∧ E ′] = 1 − P [¬E ∨ ¬E ′] ≥ 1 − P [¬E ] − P [¬E ′] = 2P0 − 1. It now suffices to consider I larger than I2 and large enough so that P (KH , I)|H| ≥ 1 − δ/2 (whose existence is guaranteed by Assumption 2, and which guarantees 2P0−1 ≥ 1− δ) and so that BKH I α+EKH
AKH I ≤ ε
to obtain the theorem.
F CONVERGENCE OF CGA AGAINST `22
To write our proof, we define LOSSρ−s : Rd → R by
LOSSρ−s(ρ) , inf ~θ
{ LOSS(ρ, ~θ, ~D)− Ls(θs,Ds)−R(ρ, θs) } (163)
= inf ~θ ∑ n 6=s L(θn,Dn) + λ ∑ n 6=s ‖ρ− θn‖22 . (164)
In other words, it is the loss when local models are optimized, and when the data of strategic user s are removed. Lemma 32. Assuming `22 regularization and convex loss-per-input functions `, for any datasets ~D, LOSS is strongly convex. As a result, so is LOSSρ−s. Proof. Note that the global loss can be written as a sum of convex function, and of ν ∑ ‖θn‖22 + ‖ρ− θ1‖22. 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 a straightforward application of Lemma 10.
We now move on to the proof of Theorem 4. Note that our statement of the proof was not fully explicit, especially about the upper bound on the constant learning rate η. Here, we prove that it holds for ηt = η ≤ 1/3L, where L is a constant such that LOSSρ−s is L-smooth. The existence of L is guaranteed by Lemma 13.
Proof of Theorem 4. Note that by Lemma 9, LOSSρ−s is convex, differentiable and L-smooth, and ∇LOSSρ−s(ρt) = g †,t −s. For ` 2 2 regularization, we have GRAD(ρ) = Rd for all ρ ∈ Rd. Then the minimum of equation 6 is zero, which is obtained when gts , ρt−θ†s η −ĝ t −s = g t−1 s + ρt−θ†s η + ρt−ρt−1 η . Note that
ρt+1 = ρt − ηg†,t−s − ηgts (165) = ρt − ηg†,t−s − (ρt − θ†s) + (ρt−1 − ρt)− ηgt−1s (166) = θ†s − ηt(g †,t −s + g t−1 s ) + η(g †,t−1 −s + g t−1 s ) (167)
= θ†s − η(g †,t −s − g †,t−1 −s ). (168)
Therefore, ρt+1 − ρt = η(g†,t−s − g †,t−1 −s )− η(g †,t−1 −s − g †,t−2 −s ). Then, using the L-smoothness of LOSSρ−s, and denoting ut , ∥∥ρt+1 − ρt∥∥ 2 , we have ut+1 ≤ Lηtut + Lηt−1ut−1. Now assume that η ≤ 1/3L. Then ut+1 ≤ 13 (ut + ut−1). We then know that ut+2 ≤ 13 (ut+1 + ut) ≤ 1 3 ( 1 3 (ut + ut−1) + ut) = 4 9ut + 1 9ut−1.
Now define vt , ut + ut−1. We then have vt+2 ≤ ut+2 + ut+1 ≤ 79ut + 4 9ut−1 ≤ 7 9 (ut + ut−1) ≤ 7 9vt. By induction, we know that vt ≤ (7/9)
(t−1)/2 max {v0, v1} ≤ ( √ 7/3)t ( ( √ 7/3) max {v0, v1} ) . Thus, defining α , √ 7/3 < 1, there exists C > 0 such that
ut ≤ vt ≤ Cαt. This implies that ∑∥∥ρt+1 − ρt∥∥ 2 ≤ ∑ Cαt < ∞. Thus ∑ (ρt+1 − ρt) converges, which implies the convergence of ρt to a limit ρ∞. By L-smoothness, we know that g†,t−s must converge too. Taking equation 168 to the limit then implies ρ∞ = θ†s. This shows that the strategic user achieves precisely what they want with CGA. It is thus optimal.

heading: G CGA ON MNIST
text: 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 a strategic user whose target model θ†s labels 0’s as 1’s, 1’s as 2’s, and so on, until 9’s as 0’s. We learn θ † s by relabeling the MNIST training dataset and learning from the relabeled data. We use λ = 1, Adam optimizer and a decreasing learning rate.

heading: H SINGLE DATA POISONING FOR LEAST SQUARE LINEAR REGRESSION
text: Proof of Theorem 5. We define the minimized loss with respect to ρ and without strategic user s by
LOSS∗−s(ρ, ~D−s) , min ~θ−s∈Rd×(N−1) ∑ n 6=s Ln(θn,Dn) + ∑ n 6=s λ ‖θn − ρ‖22  . (169) Now consider a subgradient g ∈ ∇ρLOSS∗−s(θ†s, ~D−s) of the minimized loss at θ†s. For x , −g 2λ ,
then have −g ∈ ∇ ( λ ‖x‖22 ) . We then define θ♠s , θ † s − x.
0 = g − g ∈ ∇ρLOSS∗−s(θ†s, ~D−s) +∇ρ ( λ ∥∥θ♠s − θ†s∥∥22) (170)
= ∇ρLOSSs(θ†s, ~θ∗−s(θ♠s , ~D−s), θ♠s , ~D−s), (171)
where LOSSs is defined by (38). Now consider the data point (Q,A) = (g, gT θ♠s − 1). For Ds = {(Q,A)}, we then have∇Ls(θ♠s ,Ds) = g, which implies
∇θsLOSS(θ†s, (θ♠s , ~θ∗−s(θ♠s , ~D−s), ~D) = 0. (172)
Combining it all together with the uniqueness of the solution then yields
arg min (ρ,~θ)
{ LOSS(ρ, ~θ, ~D) } = ( θ†s, ( θ♠s , ~θ∗−s(θ ♠ s , ~D−s) )) , (173)
which is what we wanted.

heading: I DATA POISONING AGAINST LINEAR CLASSIFICATION

heading: I.1 GENERATING EFFICIENT POISONING DATA
text: For every label a ∈ {1, . . . , 9}, we define ya , θ♠a − θ♠0 , and ca , −(θ ♠ a0 − θ ♠ 00) (where θ ♠ a0 is the bias of the linear classifier). The indifference subspace V is then the set of images Q ∈ Rd such that QT ya = ca for all a ∈ {1, . . . , 9}. To project any image X ∈ Rd on V , let us first construct an orthogonal basis of the vector space orthogonal to V , using the Gram-Schmidt algorithm. Namely, we first define z1 , y1. Then, for any answer a ∈ {1, . . . , 9}, we define
za , ya − ∑ b<a yTa zb zb ‖zb‖22 . (174)
It is easy to check that for b < a, we have zTa zb = 0. Moreover, if Q ∈ V , then
zTaQ = yTaQ − ∑ b<a (yTa zb)(z T b Q) ‖zb‖22 = ca − ∑ b<a (yTa zb)(z T b Q) ‖zb‖22 . (175)
By induction, we see that zTaQ is a constant independent from Q. Indeed, for a = 1, this is clear as zT1 Q = yT1 Q = c1. Moreover, for a > 1, then, in the computation of zTaQ, Q always appear as zTb Q for b < a. Moreover, denoting c′a the constant such that zTaQ = c′a for all a ∈ {1, . . . 9}, we see that these constants can be computed by
c′a = ca − ∑ b<a yTa zb ‖zb‖22 c′b. (176)
Finally, we can simply perform repeated projection onto the hyperplanes where a is equally probable as the answer 0. To do this, we first define the orthogonal projection P (X, y, c) of X ∈ Rd on the hyperplane xT y = c, which is given by
P (X, y, c) = X − (XT y − c) y ‖y‖22 . (177)
It is straightforward to verify that P (X, y, c)T y = c and that P (P (X, y, c), y, c) = P (X, y, c). We then canonically define repeated projection by induction, as
P (X, (y1, . . . , yk+1), (c1, . . . , ck+1)) , P (P (X, (y1, . . . , yk), (c1, . . . , ck)), yk+1, ck+1). (178)
Now consider any image X ∈ Rd. Its projection can be obtained by setting
Q , P (X, (z1, . . . , z9), (c′1, . . . c′9)) + ξ. (179) Note that to avoid being exactly on the boundary, and thus retrieve information about the scales of θ♠ and on which side of the boundary favors which label, we add a small noise ξ, to make sure Q does not lie 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]d, like the images of the MNIST dataset. In general, one could search for points Q ∈ V ∩ [0, 1]d. Note that in theory, by Theorem 3 (or a generalization of it), labeling random images in [0, 1]d should suffice. However, in the case where V ∩ [0, 1]d is empty (typically if no image in [0, 1] is argued by model θ♠s as realistically a 9), this procedure may require the labeling of significantly more images to be successful.

heading: I.2 A BRIEF THEORY OF DATA POISONING FOR LINEAR CLASSIFICATION
text: Using the efficient poisoning data fabrication, we thus have a set of images (Q, p(Q)), where pa(Q) is the probability assigned to image Q and label a. This defines the following local loss for the strategic node:
Ls(θs,Ds) = ∑
(Q,p(Q))∈Ds ∑ a∈{0,1,...,9} pa(Q) lnσa(θs,Q), (180)
where σa(θs,Q) = exp(θ T saQ+θsa0)∑
exp(θTsbQ+θsb0) is the probability that image Q has label a, according to the
model θs. We acknowledge that such labelings of queries is unusual. Evidently, in practice, an image may be labeled N times, and the number of labels Na it received can be set to be approximately Na ≈ Npa(Q). It is noteworthy that the gradient of the loss function is then given by(
θs − θ♠s )T ∇θsLs(θs,Ds) = ∑
Q∈Ds ∑ a∈{0,1,...,9} ( σa(θs,Q)− σa(θ♠s ,Q) ) ( θsa − θ♠sa )T Q+, (181)
where we defined Q+ , (1,Q) (which allows to factor in the bias of the model. This shows that ∇θsLs(θs,Ds) points systematically away from θ♠s , and thus that gradient descent will move towards θ♠s .
In fact, if the set of imagesQ cover all dimensions (which occurs if there are Ω(d) images, which is the case for 2,000 images, since d = 784), then gradient descent will always move the model in the direction of θ♠s , which will be the minimum. Moreover, by overweighting each data (Q, p(Q)) by a factor α (as though the image Q was labeled α times), we can guarantee gradient-PAC* learning, which means that we will have θ∗s ≈ θ♠s , 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 regularization R(ρ, θs) at ρ = θ†s and θs = θ♠s is equal to 2λ ∥∥θ†s − θ♠s ∥∥2. As the number N − 1 of other users grows, we should expect this distance to grow roughly proportionally to N . In order to make strategic user s robustly learn θ♠s , the norm of the gradient of the local loss Ls at θ†s must be vastly larger than 2λ
∥∥θ†s − θ♠s ∥∥2. This means that the value of α (or, equivalently, the number of data injected in Ds) must also grow proportionally to N .
I.3 INITIALIZATION OF THE LEARNING ALGORITHM
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 a poisoned model. To boost the convergence, we 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 we observe the convergence to this minimum.

heading: J CIFAR-10 ON VGG 13-BN EXPERIMENTS
text: We considered VGG 13-BN, which was pretrained on cifar-10 by Phan (2021). We now assume that 10 nodes are given part of the cifar-10 database, while a strategic node also joins to the personalized federated gradient descent algorithm. The strategic node’s goal is to bias the global model towards a target model, which misclassifies the cifar-10 data, by reclassifying 0 into 1, 1 into 2... and 9 into 0.

heading: J.1 COUNTER-GRADIENT ATTACK
text: We first show the result of performing counter-gradient attack on the last layer of the neural network. Essentially, images are now reduced to their vector embedding, and the last layer performs a simple linear classification akin to the case of MNIST (see Appendix G).

heading: J.2 RECONSTRUCTING A MODEL ATTACK
text: Reconstructing an attack model whose effect is equivalent to the counter-gradient attack is identical to what was done in the case of MNIST (see Section 5.2).

heading: J.3 RECONSTRUCTING DATA POISONING
text: This last step is however nontrivial. On one hand, we could simply use the attack model to label a large number of random images. However, this solution would likely require a large sample com-
plexity. For a more efficient data poisoning, we can construct vector embeddings on the indifference affine subspace V , as was done for MNIST in Section 5.3. This is what is shown below.
We acknowledge however that this does not quite correspond to data poisoning, as it requires reporting a vector embedding and its label, rather than an actual image and its label. The challenge is then to reconstruct an image that has a given vector embedding. We note that, while this is not a straightforward task in general, this has been shown to be at least somewhat possible for some neural networks, especially when they are designed to be interpretable (Zeiler & Fergus, 2014; Wang et al., 2019c; Mai et al., 2019).

Review summaries:
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.

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. 

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.

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.