{'fraction_non_alphanumeric': 0.044928124014240005, 'fraction_numerical': 0.013541525843810553, 'mean_word_length': 4.017295952973095, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Federated Recommendation System

Federated recommendation systems can provide good performance without collecting users' private data, making them attractive. However, they are susceptible to low-cost poisoning attacks that can degrade their performance. In this paper, we develop a novel federated recommendation technique that is robust against the poisoning attack where Byzantine clients prevail. We argue that the key to Byzantine detection is monitoring of gradients of the model parameters of clients. We then propose a robust learning strategy where instead of using model parameters, the central server computes and utilizes the gradients to filter out Byzantine clients. Theoretically, we justify our robust learning strategy by our proposed definition of Byzantine resilience. Empirically, we confirm the efficacy of our robust learning strategy employing four datasets in a federated recommendation system.


Introduction
Recommendation systems (RS), which are machine learning models that try to predict the user (client) preferences, are increasingly being deployed commercially [22; 4; 26; 37; 32; 35]. Learning a conventional RS requires centralized storage of clients' data, which raises privacy concerns [6]. In order to make RS compliant with privacy regulation while preserving the quality of recommendation service, federated recommendation system (FRS) has attracted recent attention [1; 10; 29]. An FRS is able to learn a quality recommendation model without holding clients' data centrally.
However, due to the decentralized data storage, FRS is susceptible to low-cost poisoning attacks [40; 7; 13; 23; 20; 36]. An unscrupulous competitor can easily create a small number of malicious clients, i.e., Byzantine clients, to bias the recommendations [3; 2; 40; 36]. Consequently, a non-robust federated recommendation system with irrelevant recommendations will soon lose its reputation and trust. Therefore, developing a federated recommendation system that is robust against poisoning attacks is necessary.
It appears that learning a robust FRS can directly employ existing defense strategies, i.e., utilize the model parameters among clients to detect Byzantine clients [7; 11; 23; 41; 21]. The tacit assumption of the existing defense strategies is that the clients optimize their local models with (stochastic) gradient descent (SGD), where the update of the model parameter is identical to the gradient (of the model parameter). However, in learning FRS, SGD often leads to poor performance due to the problem of vanishing gradients, slow convergence, and its inability to handle sparse data [43; 42]. Consequently, it is common for clients to employ momentum-based optimizers such as Adam [19] and SGD with momentum [30] to optimize their local models [1; 17; 9]. Our experimental findings in Appendix H.2 also substantiate this. Naturally, the following question arises: Byzantine clients (orange triangles) federally use Adam to jointly optimize a matrix factorization model [1]. We extract model parameters (left panel) and gradients (right panel) from all 90 clients at the 24-th training round and use principal components analysis (PCA) to project them into 2-D dimension for visualization.
Can we simply employ the model parameters of clients to detect Byzantine clients when momentum-based optimizers are used to learn the federated recommendation system?
We argue that the answer to the above question is negative. We further propose that we should utilize gradients rather than model parameters to detect Byzantine clients. For example, when a client uses Adam to optimize its local model, the update to the model parameter is not identical to the gradient of the local model [19]. Actually, the model parameter is adaptively updated based on the current gradient and gradients in the previous rounds. If the client is Byzantine, its model gradient could largely deviate from that of benign clients (e.g., Byzantine clients perform gradient ascent while benign clients perform gradient descent [40]). However, the model parameter of the Byzantine client could be similar to that of the benign client due to the fact that the model parameter accumulates gradients (including other benign gradients) of the previous training rounds. As a result, Byzantine model parameters are less distinguishable from benign ones compared to Byzantine gradients. To illustrate this fact, in Figure 1, we trained a simple federated recommendation system with 58 benign clients (blue dots) and 32 Byzantine clients (orange triangles) using Adam optimizer. We plotted the clients' model parameters (left panel) and the clients' gradients (right panel) at a randomly selected training round. From Figure 1, model parameters from Byzantine and benign clients are less distinguishable than the gradients. This issue affects all momentum-based optimizers including Adam, and we will elaborate in Section 4.
To learn a robust federated recommendation system, rather than using clients' model parameters, we propose to utilize gradients to detect Byzantine clients. Our main contributions are: 1. We first employ factored item similarity model (FISM) [18] in learning a federated recommendation system (FRS), which achieves state-of-the-art performance. Our method is able to handle real-time personalization and sparse client feedback [16] better than the existing methods [1; 10; 29].
2. To the best of our knowledge, we are the first to develop a robust federated recommendation system against the poisoning attack. We show that when clients use momentum-based optimizers such as Adam, Byzantine clients are able to camouflage their model parameters and launch effective attacks. However if we employ gradients for detection, it can effectively thwart Byzantine clients. We propose a new definition of Byzantine resilience catering to momentum-based optimized FRS, and we provide a theoretically guarantee that our robust learning strategy (gradient-based detection) is Byzantine resilient. Empirically, we conduct extensive experiments on real-world datasets verifying the efficacy of our robust learning strategy against poisoning attacks. Besides momentum-based optimizers, we further show that our robust learning strategy can be easily adapted to other well-known optimizers such as AdaGrad [12] and RMSProp [31] and still preserves the theoretical guarantee of Byzantine resilience.

Background and notations
In this section, we review factored item similarity model (FISM) and Adam optimizer used in federated recommendation system (FRS).
Notations. We use bold lower-case letters such as m to represent vectors, lower-case letters such as m to represent scalars, and upper-case curlicue letters such as S to represent sets. Aggregated vectors are denoted by a line over vectors such as m. Byzantine vectors are denoted by a tilde over vectors such as m. m denotes the Euclidean norm of m. |S| is the cardinality of set S. denotes element-wise multiplication (Hadamard product). All operations between vectors are element-wise operations in this paper (except inner products of vectors).
Factored item similarity model (FISM). In online services (e.g., YouTube, Amazon, etc.), clients constantly update their preference data [5]. It is imperative for recommendation systems to handle real-time personalization [14]. Moreover, many clients' activities are not frequent, i.e., the client-item rating matrix is sparse [25]. To deal with real-time personalization and sparse data, factored item similarity model (FISM) was proposed [18]. FISM utilizes the average embedding vector of items that have been rated by client i to represent client i's feature and then uses the inner product of client i's and item j's embedding vectors to calculate the prediction score of client i on item j. Formally, the predictive model is: (1) y ij is the prediction score of client i on item j. S i+ is the set of client i's rated items. γ is a hyperparameter controlling the normalization effect. p j , q k ∈ R d are the trainable embedding vectors for item j and k respectively. d is the dimension of the embedding vectors. Each item j has two embedding vectors p j and q j : p j represents the item feature for prediction, while q j is a historical interaction used for representing client feature. For clarity, we use θ to represent trainable embedding vectors p j and q j for all items j.
When client i interacts with a new item j, we just need to add item j to S i+ , i.e., S i+ = S i+ ∪ {j}, and do not need to retrain the model. On the other hand, even if a client has less activity, it can be represented by an average embedding vector of items, which prevents overfitting of the model. Adam optimizer. Adam optimizer has been widely used in learning FRS, due to its fast convergence property and its ability to handle sparse gradients [1]. Different from SGD that directly uses gradients to update model parameters, Adam updates the model parameters using estimates of first and second moments of the gradients. At round t, client i uses Adam optimizer to update its model parameter θ ti according to: where g ti , m ti , v ti , u ti and θ ti are gradient, first moment, second moment, update and model parameter of the i-th client at t-th (communication) round. m t−1 , v t−1 and θ t−1 that are the inputs at round t respectively represent aggregated first moment, aggregated second moment and aggregated model parameter at (t − 1)-th round. β 1 and β 2 are hyperparameters related to first and second moment vectors. η is the learning rate. m 0 , v 0 are initialized to 0. θ 0 is initialized with random values sampled from a standard Gaussian distribution. is a small constant for numerical stability.

Algorithm 1 Adam-based (Robust) Federated Recommendation System -A-(R)FRS
Input: Client set S, number of training rounds T , and fraction of training clients per round e Output: Trained model parameter θ T (Represents the trainable parameter of Eq. (1)) procedure SERVER AGGREGATION Initialize m 0 , v 0 , and θ 0 for each round t = 1, 2, ..., T do Use Eq. (2) for Byzantine clients detection. end for Option I: F t ← S t Non-robust FRS. Ignore the computed g ti . Option II: Robust FRS. Use the computed g ti . N t = i∈Ft n i n i is the number of training data of client i.
Algorithm 2 Client update using Adam optimizer Input: Aggregated first moment m t−1 , aggregated second moment v t−1 and aggregated model parameter θ t−1 at round (t − 1) from the server Output: First moment m ti , second moment v ti and model parameter θ ti of client i at round t procedure CLIENT UPDATE Run on the i-th client.
Conventional federated recommendation systems based on matrix factorization (MF) [1; 10; 29] fail to deal with real-time personalization and sparse data [18; 27; 17]. To solve this problem, we propose Adam-based federated recommendation system (A-FRS), which extends FISM to be a FRS. A-FRS inherits the advantages of FISM [18]. It can handle real-time personalization and deal with sparse data with the ability to learn a quality recommendation model without collecting clients' data.
The learning of A-FRS is shown in Algorithm 1 (Option I). In Algorithm 1, A-FRS consists of two parts: a server and |S| clients. The server distributes first moment, second moment, and model parameters to the clients for training and aggregates those trained by all clients.
Clients optimize their local recommendation model based on the ranking loss [28] defined as follows: where S is the client set. σ(·) is the sigmoid function. θ denotes trainable model parameter. λ controls the strength of L 2 regularization to prevent overfitting. S i+ and S i− are sets of client i's rated items and unrated items respectively.ŷ ij andŷ ik can be calculated with Eq. (1). Similar to other federated recommendation methods [1], clients utilize Adam to optimize model parameters. Compared with SGD, two additional terms (the first moment m and the second moment v) are introduced in Adam. Thus, clients also need to transfer these two terms to the server for aggregation.

Robust federated recommendation system
In this section, we first show that Byzantine clients can camouflage the model parameters and launch effective attacks. Then, we propose our robust learning strategy in Adam-based FRS and theoretically prove that our strategy is Byzantine resilient. Besides, in Appendix C, D, and E, we show that our robust learning strategy is also suitable in FRS based on other well-known optimizers (e.g., SGD with momentum, AdaGrad, and RMSProp) with theoretical guarantees.

Motivation -Byzantine clients can camouflage model parameters
We demonstrate that when clients use momentum-based optimizers such as Adam, the Byzantine clients can camouflage their model parameters while launching an effective poisoning attack 2 . Thus, the existing defense methods [7; 11; 23] catering to SGD optimizer can not be simply applied, because they detect Byzantine clients based on the model parameters.
In the left panel of Figure 2, the i-th client at the round t uses Adam to optimize the local model. We plot the parameter θ ti -gradient g ti relationship. For simplicity, let θ ti and g ti be scalars. Suppose point A is the benign point with benign θ ti and g ti , the Byzantine client can choose Byzantine point B which has the same θ ti but completely different g ti that is calculated by The detailed derivation is provided in Appendix F. Eq. (8) is the case for one dimension. It can be easily generalized into higher-dimensional model parameters due to element-wise operations of Eq. (2-6). In particular, when the dimension of the model parameter θ ti is large, the number of such Byzantine gradients g ti is exponential, because the Byzantine client can craft each component of the Byzantine gradients g ti . Thus, the Byzantine client can easily choose a g ti that can effectively poison the global model.
In the right panel of Figure 2, we conduct an experiment showing the efficacy of the camouflage attack (red line). The blue line represents Precision@K [38] of A-FRS (Option I in Algorithm 1) without any attack. The red line represents the Precision@K with 40% Byzantine clients. The Byzantine clients maintain the same model parameters for update but calculate the Byzantine g ti that has the largest Euclidean distance from the benign correspondence g ti . Consequently, from the right panel of Figure 2, the red line is lower than the blue line. It shows that the camouflage attack can effectively degrade the global model.
It is worth noting that not all model parameters can be camouflaged. For example, in the left panel of Figure 2, point C has a unique mapping from θ ti to g ti . Thus, the Byzantine client has a certain chance of failing to camouflage the model parameter. However, this chance is afflicted with the curse of dimensionality. As the dimensionality of model parameters is typically very large, the Byzantine client can confidently camouflage the model parameter and launch effective attacks.
Motivated by the above observations, rather than using model parameters, we propose to use gradients of the models to detect Byzantine clients in the following sections.

Byzantine resilience
The current defense methods employ the existing definitions of Byzantine resilience [7; 23; 39]. However, these definitions only provide restrictions to the model parameters of clients. For example, if a client's model parameter is very distinct from those of others, this client is deemed to be Byzantine. These restrictions do not apply to first moment and second moment in Algorithm 2. As a result, Byzantine clients can camouflage the model parameters but change the gradient along with first and second moments to be very different (shown in Section 4.1). Thus, existing definitions have this serious limitation, which can lead to a security breach.
To solve this, we give a new definition, Adam-Byzantine resilience to evaluate defense methods when Adam is used in FRS. Other types of Byzantine resilience definitions catering to other optimizers such as SGD with momentum, AdaGrad, and RMSProp can be found in Appendix C, D, and E.
Suppose n out of n clients are Byzantine. Let G t = {g ti |i ∈ {1, ..., n − n}} be the gradient set of n − n benign clients at round t. Let G t = { g ti |i ∈ {1, ..., n}} be the gradient set of n Byzantine clients at round t. Let F t be the set of selected clients for aggregation. LetĜ t = {ĝ ti |client i ∈ F t } be the gradient set of clients in F t . We define Adam-Byzantine resilience as follows: Definition 1 Adam-Byzantine Resilience. For any client i in F t at training round t, we denote its first moment, second moment and model parameter asm ti ,v ti andθ ti . For any benign client j at training round t, we denote its first moment, second moment, and model parameter as m tj , v tj and θ tj . A defense method is Adam-Byzantine resilient, if for the round T there exist positive constant numbers C m , C v and C θ , such that The definition of Adam-Byzantine resilience provides constraints on first moments, second moments, and model parameters. If a defense method is Adam-Byzantine resilient, no matter how Byzantine clients attack the server (e.g., by using gradient ascent [7] or by adding random noise [21]), the attack will have little influence on the global model, which guarantees the efficacy of the defense method. In comparison, the existing definitions of Byzantine resilience [7; 11; 23] can provide no guarantees on condition 1 and condition 2.

Adam-based robust federated recommendation system (A-RFRS)
When clients federally learn a recommendation system using Adam optimizer, we propose Adambased robust federated recommendation system (A-RFRS) (Option II in Algorithm 1). In A-RFRS, g ti are used to detect Byzantine clients, since m ti , v ti , and θ ti are computed by g ti of client i at round t. Compared with non-robust A-FRS (Option I), our robust version A-RFRS performs a filtering operation before the aggregation of updates from clients. The filtering function F (·) is flexible. In our paper, we utilize the strategy of Krum [7] to filter out Byzantine clients based on the computed gradients.
To theoretically justify our proposed A-RFRS, we prove that A-RFRS is Adam-Byzantine resilient.
Assumption 1. For any gradient g, its norm is upper bounded by a positive constant number g max . Formally, g ≤ g max with g ∈ G t ∪ G t , t ∈ N * . Theorem 1. A-RFRS is Adam-Byzantine resilient, if Assumption 1 and Assumption 2 hold, and for any client i in F t with gradientĝ ti ∈Ĝ t , for any benign client j with gradient g tj ∈ G t , and for training round T ∈ N * , there exist a positive constant number C g , such that T t=1 client i∈Ft benign client j ĝ ti − g tj ≤ C g .
The proof of Theorem 1 is in Appendix B. Theorem 1 claims that, if our gradient-based filter algorithm (e.g., gradient-based Krum) guarantees thatĝ ti is close to any benign gradient g tj , then the first momentm ti , second momentv ti and model parameterθ ti will also be close to the benign m tj , v tj and θ tj . This indicates that our defense method is robust to Byzantine attacks. This further shows that our learning strategy, which utilizes gradients to filter out Byzantine clients, is effective when Adam optimizer is used.
We also show that our proposed robust learning strategy that utilizes gradients to detect Byzantine clients, can be adapted to other well-known optimizers such as SGD with momentum, AdaGrad, and RMSProp with theoretical guarantees. Those results and the proofs are in Appendix C, D, and E, respectively. We also conduct experiments comparing our robust learning strategy with existing defense methods on FRS based on SGD with momentum and AdaGrad in Appendix H.3.

Experiments
In this section, we evaluate the performance of our proposed A-FRS (Option I in Algorithm 1) and A-RFRS (Option II in Algorithm 1) on 4 real-world datasets from various domains (i.e., Last. with the ranking position K ranges from 1 to 5. The detailed description of datasets and training configurations are in Appendix G. Federated recommendation system. In the first part of our experiments, we compare our A-FRS (Option I in Algorithm 1) with existing federated matrix factorization (FMF) [1], which employs matrix factorization in FRS. For each client, we randomly select 80% of its local data as the training set and evaluate the global model with the remaining 20%. Figure 3 shows Precision@K of FRSs on different datasets where the ranking position K ranges from 1 to 5. We also report Recall@K [22] in Appendix H.1. The results demonstrate that our proposed A-FRS (red line) outperforms FMF (blue line) on all datasets. Recommendation datasets are often sparse, and our A-FRS employs factored item similarity model that is capable of dealing with sparse data.  In our setting, the Byzantine clients employ the gradient ascent attack [7]. The Byzantine clients firstly use their own data to compute the gradient g normally, but use −g to calculate m, v and θ and send them back to the server. We have also tried additive noise attack [21], where Byzantine clients add Gaussian noise to their model parameters, but the additive noise attack has minor poisoning effects on the global model. Thus, we do not consider the additive noise attack. In addition, we also do not consider the camouflage attack (detailed in Section 4.1) in this section since the existing defense methods only examine the model parameters, therefore they cannot defend camouflage attack at all.
In Figure 4, we set the number of Byzantine clients n = 0.2n, 0.3n, 0.4n, and evaluate and compare our A-RFRS with RFA, Trmean, Krum and No defense model (our non-robust A-FRS) on four different datasets. For each client, we randomly select 80% of the local data as the training set, but we evaluate the global model with the remaining 20% data of benign clients. We run our experiment with five repeated trials and report the average Precision@K (the ranking position K ranges from 1 to 5) and its standard deviation. We also report the average Recall@K and its standard deviation in Appendix H.1.

Conclusion
This paper proposes a novel robust learning strategy to defend poisoning attacks in momentum-based federated recommendation system. We first show that Byzantine clients can camouflage the model parameters and elude existing defense methods by launching an effective camouflage attack. To solve this problem, we propose to use gradients (instead of model parameters) to filter out Byzantine clients in momentum-based federated recommendation system. We theoretically proved that our proposed robust learning strategy is Byzantine resilient and empirically verified its efficacy. A promising future direction is extending the current work to defend targeted poisoning attacks.
[3] Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Advances in Neural Information Processing Systems, pages 8632-8642, 2019.
[4] Omer Ben-Porat and Moshe Tennenholtz. A game-theoretic approach to recommendation systems with strategic content providers. In Advances in Neural Information Processing Systems, pages 1110-1120, 2018.
[  Aggregated first moment at round t − 1 v t−1

A Notations
Aggregated second moment at round t − 1 r t−1 Aggregated squared gradient at round t − 1 θ Gradient of i-th benign client at round t m ti First moment of i-th benign client at round t v ti Second moment of i-th benign client at round t r ti Squared gradient of i-th benign client at round t θ ti Model parameter of i-th benign client at round t g ti Gradient of i-th Byzantine client at round t m ti First moment of i-th Byzantine client at round t v ti Second moment of i-th Byzantine client at round t r ti Squared gradient of i-th benign Byzantine at round t θ ti Model parameter of i-th benign Byzantine at round t β 1 Hyperparameter of Adam, 0 < β 1 < 1 β 2 Hyperparameter of Adam, 0 < β 2 < 1 β 3 Hyperparameter of SGD with momentum, 0 < β 3 < 1 β 4 Hyperparameter of RMSProp, 0 < β 4 < 1 Element-wise multiplication B Proof of Theorem 1 In this section, we show the proof of Theorem 1.
Suppose n out of n clients are Byzantine. Let G t = {g ti |i ∈ {1, ..., n − n}} be the gradient set of n − n benign clients at round t. Let G t = { g ti |i ∈ {1, ..., n}} be the gradient set of n Byzantine clients at round t. Let F t be the set of selected clients for aggregation. LetĜ t = {ĝ ti |client i ∈ F t } be the gradient set of clients in F t . We define Adam-Byzantine resilience as follows: Definition 1 Adam-Byzantine Resilience. For client i in F t at training round t, we denote its first moment, second moment and model parameter asm ti ,v ti andθ ti . For any benign client j at training round t, we denote its first moment, second moment, and model parameter as m tj , v tj and θ tj . A defense method is Adam-Byzantine resilient, if for the round T there exist positive constant numbers C m , C v and C θ , such that Assumption 1. For any gradient g, its norm is upper bounded by a positive constant number g max . Formally, g ≤ g max with g ∈ G t ∪ G t , t ∈ N * .
Assumption 2. After T rounds of training, each component of v t−1 is lower bounded by a positive constant number v min . Formally, for any round t with t > T , v t−1 Lemma 2. If Assumption 1 holds, then for any client i with first moment m ti at round t, the norm of its first moment is upper bound by g max . Formally, m ti ≤ g max .
Proof. We prove the lemma by mathematical induction.
When t = 1, since m t−1 = m 0 = 0 and according to Assumption 1, The first equality is due to the definition of first moment. The first inequality is due to Assumption 1. Thus, m 1i ≤ g max holds.
Suppose when t = k, m ti = m ki ≤ g max holds.
When t = k + 1, firstly, we focus on m k . Recall that the aggregation rule is weighted aggregation of all clients in F k . Formally, where λ i is the weight for the i-th first moment m ki . When t = k, m ki ≤ g max holds. Thus, The second equality is due to absolutely homogeneous of matrix norm. Now we draw our attention to m (k+1)i : The first inequality is due to triangle inequality and the second inequality is due to Eq. (12) and Assumption 1. Thus, when t = k + 1, m ti = m (k+1)i ≤ g max holds.
Therefore, for any t ∈ N * , m ti ≤ g max holds.
Theorem 1. A-RFRS is Adam-Byzantine resilient, if Assumption 1 and Assumption 2 hold, and for any client i in F t with gradientĝ ti ∈Ĝ t , for any benign client j with gradient g tj ∈ G t , and for training round T ∈ N * , there exist a positive constant number C g , such that T t=1 client i∈Ft benign client j ĝ ti − g tj ≤ C g .
Proof. Intuitively, sinceĝ ti is not far from g tj ,m ti ,v ti andθ ti should also be close to m tj , v tj and θ tj . We will prove them step by step below.
The first step is to provem ti is close to m tj .
According to the definition of first moment, The second equality is due to absolutely homogeneous of matrix norm. By adding round 1 to round T , all clients in F t and all benign clients together, The first equlity is due to Eq. (14). The inequality is due to the assumption of Theorem 1. Let C m = (1 − β 1 )C g . Then C m is a positive constant number, and T t=1 client i∈Ft benign client j Thus, condition 1 of Adam-Byzantine resilience holds.
The second step is to provev ti is close to The first equality is due to the definition of second moment. The second equality is due to absolutely homogeneous of matrix norm. The third equality follows from square of the difference formula. The first inequality is due to submultiplicativity of matrix norm. The second inequality is due to triangle inequality. By adding round 1 to round T , all clients in F t and all benign clients together, The first inequality is due to Eq. (17). The second inequality follows from Assumption 1. The third inequality is due to the assumption of Theorem 1 and Lemma 1.
Therefore, condition 2 of Adam-Byzantine resilience holds.
The third step is to proveθ ti is close to θ tj . According to the definition,θ Recall thatv ti The second inequality is due to Assumption 2. By combining Eq. (20) with Eq. (21), We combine all the components together: By adding round 1 to round T , all clients in F t and all benign clients together, when T > T , The first inequality is due to Eq. (23). The second inequality is due to Eq. (19).
β2vmin . Then C v is a positive constant number, and T t=1 client i∈Ft benign client j The second inequality is due to Assumption 2. By combining Eq. (27) with Eq. (28), We combine all the components together: By adding round 1 to round T , all clients in F t and all benign clients together, when T > T , T t=1 client i∈Ft benign client j 1 √v The first inequality is due to Eq. (30). The second inequality is due to Eq. (25).
When T ≤ T , T t=1 client i∈Ft benign client j 1 √v 1 The second equality is due to the definition of 1 √ v tj k . The second inequality is due to Assumption 2.
By combining Eq. (34) with Eq. (35), We combine all the components together: The first inequality is due to Eq. (37). The second inequality follows from (16)) and T t=T +1 client i∈Ft benign client j 1 √v The first inequality is due to Eq. (38). The second inequality follows from Eq. (39). The third inequality is due to Eq. (16) and Eq. (32). Let C θ = T t=1 client i∈Ft benign client j Then C θ is a positive constant number, and T t=1 client i∈Ft benign client j When T ≤ T , Thus Eq. (41) still holds.
The fourth part is to proveθ ti is close to θ tj . According to the definition ofθ ti and θ tj , The inequality follows from Eq. (41). Therefore, condition 3 of Adam-Byzantine resilience holds.
Since condition 1,2 and 3 of Adam-Byzantine resilience all hold, A-RFRS is Adam-Byzantine resilient.

C FRS based on SGD with momentum
In this section, we propose the definition of SGD with momentum-Byzantine resilience and show that our robust learning strategy is suitable in FRS based on SGD with momentum optimizer [30] with theoretical guarantee.
The algorithm of SGD with momentum of client i at round t is: where g ti , m ti and θ ti are gradient, momentum and model parameter of client i at round t. η is the learning rate. β 3 is a hyperparameter controlling the weight of momentum. m t−1 and θ t−1 represent aggregated momentum and aggregated model parameter at round (t − 1).
Suppose n out of n clients are Byzantine. Let G t = {g ti |i ∈ {1, ..., n − n}} be the gradient set of n − n benign clients at round t. Let G t = { g ti |i ∈ {1, ..., n}} be the gradient set of n Byzantine clients at round t. Let F t be the set of selected clients for aggregation. LetĜ t = {ĝ ti |client i ∈ F t } be the gradient set of clients in F t . We define SGD with momentum-Byzantine resilience as follows: Definition 2 SGD with momentum-Byzantine Resilience. For any client i in F t , we denote its momentum and model parameter asm ti andθ ti . For any benign client j, we denote its momentum and model parameter as m tj and θ tj . A defense method is SGD with momentum-Byzantine resilient, if for the round T there exists positive constant numbers C m and C θ , such that: We propose SGD with momentum-based robust federated recommendation system (S-RFRS), which utilize gradients to detect Byzantine clients in FRS based on SGD with momentum optimizer. The algorithm of S-RFRS is the same to A-RFRS except the former uses SGD with momentum to learn the model while the latter uses Adam to learn the model.
Theorem 2. S-RFRS is SGD with momentum-Byzantine resilient, if for any client i in F t with gradientĝ ti ∈Ĝ t , for any benign client j with gradient g tj ∈ G t , and for the round T , there exist a positive constant number C g , such that T t=1 client i∈Ft benign client j ĝ ti − g tj ≤ C g .
Proof. Intuitively, sinceĝ ti is not far from g tj ,m ti andθ ti should also be close to m tj and θ tj . We will prove them step by step below.
The first step is to provem ti is close to m tj .
According to the definition of momentum, By adding round 1 to round T , all clients in F t and all benign clients together, The first equlity is due to Eq. (45). The inequality is due to the assumption of Theorem 2. Let C m = C g . Then C m is a positive constant number, and T t=1 client i∈Ft benign client j Thus, condition 1 of SGD with momentum-Byzantine resilience holds.
The second step is to proveθ ti is close to θ tj .
According to the definition of model parameter (for simplicity, we omit the learning rate), The inequality is due to Eq. (47). Let C θ = C m . Then C θ is a positive constant number, and T t=1 client i∈Ft benign client j Thus, condition 2 of SGD with momentum-Byzantine resilience holds.
Since condition 1 and 2 of SGD with momentum-Byzantine resilience all hold, S-RFRS is SGD with momentum-Byzantine resilient.

D FRS based on AdaGrad
In this section, we propose the definition of AdaGrad-Byzantine resilience and show that our robust learning strategy is suitable in FRS based on AdaGrad optimizer [12] with theoretical guarantee.
The algorithm of AdaGrad of client i at round t is: where g ti , r ti , u ti and θ ti are gradient, squared gradient, update, and model parameter of client i at round t. η is the learning rate. r t−1 and θ t−1 represent aggregated squared gradient and aggregated model parameter at round (t − 1). is a small constant for numerical stability.
Suppose n out of n clients are Byzantine. Let G t = {g ti |i ∈ {1, ..., n − n}} be the gradient set of n − n benign clients at round t. Let G t = { g ti |i ∈ {1, ..., n}} be the gradient set of n Byzantine clients at round t. Let F t be the set of selected clients for aggregation. LetĜ t = {ĝ ti |client i ∈ F t } be the gradient set of clients in F t . We define AdaGrad-Byzantine resilience as follows: Definition 3 AdaGrad-Byzantine Resilience. For any client i in F t , we denote its squared gradient and model parameter asr ti andθ ti . For any benign client j, we denote its squared gradient and model parameter as r tj and θ tj . A defense method is AdaGrad-Byzantine resilient, if for the round T there exists positive constant numbers C r and C θ , such that: We propose AdaGrad-based robust federated recommendation system (AG-RFRS), which utilize gradients to detect Byzantine clients. The algorithm of AG-RFRS is the same to A-RFRS except the former uses AdaGrad to learn the model while the latter uses Adam to learn the model.
Assumption 3. For any gradient g, its norm is upper bounded by a positive constant number g max . Theorem 3. AG-RFRS is AdaGrad-Byzantine resilient, if Assumption 3 and Assumption 4 hold, and for any client i in F t with gradientĝ ti ∈Ĝ t , for any benign client j with gradient g tj ∈ G t , and for the round T , there exist a positive constant number C g , such that T t=1 client i∈Ft benign client j ĝ ti − g tj ≤ C g .
Proof. Intuitively, sinceĝ ti is not far from g tj ,r ti andθ ti should also be close to r tj and θ tj . We will prove them step by step below.
The first step is to prover ti is close to r tj .
The first equality is due to the definition of squared gradient. The third equality follows from square of the difference formula. The first inequality is due to submultiplicativity of matrix norm. The second inequality is due to triangle inequality. By adding round 1 to round T , all clients in F t and all benign clients together, T t=1 client i∈Ft benign client j r ti − r tj ≤ T t=1 client i∈Ft benign client j ĝ ti − g tj 2 + 2 ĝ ti − g tj g tj ≤ T t=1 client i∈Ft benign client j ĝ ti − g tj 2 + 2 T t=1 client i∈Ft benign client j ĝ ti − g tj g max The first inequality is due to Eq. (51). The second inequality follows from Assumption 3. The third inequality is due to the assumption of Theorem 3 and Lemma 1. Let C r = C 2 g + 2g max C g . Then, C r is a positive constant number, and T t=1 client i∈Ft benign client j Therefore, condition 1 of AdaGrad-Byzantine resilience holds.
The second step is to proveθ ti is close to θ tj . According to the definition,θ r tj (for simplicity, we omit the learning rate). We can decompose the proof into four parts: 1.
The first part is to prove √r ti is close to √ r tj . We focus on one component of √r ti and √ r tj . For any vector r, let r k denote the k-th component of r.
Recall thatr ti k = r t−1 k + (ĝ ti k ) 2 and r tj k = r t−1 k + (g tj k ) 2 . When t > T , The second inequality is due to Assumption 4. By combining Eq. (54) with Eq. (55), We combine all the components together: T t=1 client i∈Ft benign client j The first inequality is due to Eq. (57). The second inequality is due to Eq. (53). Let C r = T t=1 client i∈Ft benign client j √r ti − √ r tj + Cr 2 √ rmin . Then C r is a positive constant number, and T t=1 client i∈Ft benign client j When T ≤ T , Recall that r ti k = r t−1 k + (ĝ ti k ) 2 and r tj k = r t−1 k + (g tj k ) 2 . When t > T , The second inequality is due to Assumption 4. By combining Eq. (61) with Eq. (62), We combine all the components together: By adding round 1 to round T , all clients in F t and all benign clients together, when T > T , The first inequality is due to Eq. (64). The second inequality is due to Eq. (59). Let C r = T t=1 client i∈Ft benign client j 1 √r rmin . Then C r is a positive constant number, and T t=1 client i∈Ft benign client j 1 √r When T ≤ T , T t=1 client i∈Ft benign client j 1 √r When t > T , The second equality is due to the definition of 1 √ r tj k . The second inequality is due to Assumption 4.
By combining Eq. (68) with Eq. (69), We combine all the components together: T t=1 client i∈Ft benign client j ĝ ti √r The first inequality is due to Eq. (71). The second inequality is due to Assumption 3. Since T t=T +1 client i∈Ft benign client j ĝ ti − g tj ≤ C g (assumption of Theorem 3) and T t=T +1 client i∈Ft benign client j 1 √r T t=1 client i∈Ft benign client j ĝ ti √r The first inequality is due to Eq. (72). The second inequality follows from Eq. (73). The third inequality is due to Eq. (66) and the assumption of Theorem 3. Let C θ = T t=1 client i∈Ft benign client j ĝ ti √r Then C θ is a positive constant number, and T t=1 client i∈Ft benign client j ĝ ti √r When T ≤ T , T t=1 client i∈Ft benign client j ĝ ti √r Thus Eq. (75) still holds.
The fourth part is to proveθ ti is close to θ tj . According to the definition ofθ ti and θ tj (for simplicity, we omit the learning rate), The inequality follows from Eq. (75). Therefore, condition 2 of AdaGrad-Byzantine resilience holds.

E FRS based on RMSProp
In this section, we propose the definition of RMSProp-Byzantine resilience and show that our robust learning strategy is suitable in FRS based on RMSProp optimizer [31] with theoretical guarantee.
The algorithm of RMSProp of client i at round t is: where g ti , r ti , u ti and θ ti are gradient, squared gradient, update, and model parameter of client i at round t. η is the learning rate. β 4 is a hyperparameter controlling the weight of squared gradient. r t−1 and θ t−1 represent aggregated squared gradient and aggregated model parameter at round (t − 1).
is a small constant for numerical stability.
Suppose n out of n clients are Byzantine. Let G t = {g ti |i ∈ {1, ..., n − n}} be the gradient set of n − n benign clients at round t. Let G t = { g ti |i ∈ {1, ..., n}} be the gradient set of n Byzantine clients at round t. Let F t be the set of selected clients for aggregation. LetĜ t = {ĝ ti |client i ∈ F t } be the gradient set of clients in F t . We define RMSProp-Byzantine resilience as follows: Definition 4 RMSProp-Byzantine Resilience. For any client i in F t , we denote its squared gradient and model parameter asr ti andθ ti . For any benign client j, we denote its squared gradient and model parameter as r tj and θ tj . A defense method is RMSProp-Byzantine resilient, if for the round T there exists positive constant numbers C r and C θ , such that:

1.
T t=1 client i∈Ft benign client j r ti − r tj ≤ C r ;
We propose RMSProp-based robust federated recommendation system (R-RFRS), which utilize gradients to detect Byzantine clients. The algorithm of R-RFRS is the same to A-RFRS except the former uses RMSProp to learn the model while the latter uses Adam to learn the model.
Assumption 5. For any gradient g, its norm is upper bounded by a positive constant number g max . Formally, g ≤ g max with g ∈ G t ∪ G t , t ∈ N * . Theorem 4. R-RFRS is RMSProp-Byzantine resilient, if Assumption 5 and Assumption 6 hold, and for any client i in F t with gradientĝ ti ∈Ĝ t , for any benign client j with gradient g tj ∈ G t , and for the round T , there exist a positive constant number C g , such that T t=1 client i∈Ft benign client j ĝ ti − g tj ≤ C g .
Proof. Intuitively, sinceĝ ti is not far from g tj ,r ti andθ ti should also be close to r tj and θ tj . We will prove them step by step below.
The first step is to prover ti is close to r tj .
The first equality is due to the definition of squared gradient. The second equality is due to absolutely homogeneous of matrix norm. The third equality follows from square of the difference formula. The first inequality is due to submultiplicativity of matrix norm. The second inequality is due to triangle inequality. By adding round 1 to round T , all clients in F t and all benign clients together, T t=1 client i∈Ft benign client j The first inequality is due to Eq. (79). The second inequality follows from Assumption 5. The third inequality is due to the assumption of Theorem 4 and Lemma 1. Let C r = (1 − β 4 )C 2 g + 2(1 − β 4 )g max C g . Then, C r is a positive constant number, and T t=1 client i∈Ft benign client j r ti − r tj ≤ C r .
The second step is to proveθ ti is close to θ tj . According to the definition,θ Recall that r ti k = β 4 r t−1 The second inequality is due to Assumption 6. By combining Eq. (89) with Eq. (90), We combine all the components together: The fourth part is to proveθ ti is close to θ tj . According to the definition ofθ ti and θ tj (for simplicity, we omit the learning rate), T t=1 client i∈Ft benign client j The inequality follows from Eq. (103). Therefore, condition 2 of RMSProp-Byzantine resilience holds.
Since condition 1 and condition 2 of RMSProp-Byzantine resilience all hold, R-RFRS is RMSProp-Byzantine resilient. The relation between the model parameter θ ti and the gradient g ti of client i at round t. Suppose point A is the benign point with benign θ ti and g ti , point B is a Byzantine point with the same θ ti but different g ti . point C has a unique mapping from θ ti from g ti , and thus cannot be camouflaged.
In this section, we demonstrate the derivation of Byzantine gradient in camouflage attack.
As shown in Figure 5, suppose point A is the benign point with benign θ ti and g ti , the Byzantine client can choose Byzantine point B which has the same θ ti but completely different g ti . According to Adam update rule, the model parameter of point A and point B are computed by Since they have the same update, we can obtain By removing the fractions and square roots, By removing the parentheses, (108) By deleting the same items, Since g ti does not equal to g ti , we can divide the equation by (g ti − g ti ), Thus, we can get Then, we can obtain g ti : It is worth noting that not all θ ti can be camouflaged. For example, in Figure 5, point C has a unique mapping from θ ti to g ti . In this case, if we compute g ti by Eq. (113), the Byzantine update of model parameter will equal to negative benign update of model parameter (i.e., β1m t−1 +(1−β1)g ti √ β2v t−1 +(1−β2)(g ti ) 2 = − β1m t−1 +(1−β1) g ti √ β2v t−1 +(1−β2)( g ti ) 2 ). Thus, Eq. (107-113) hold but Eq. (106) does not hold.

G Datasets, baselines and configuration of experiments
In this section, we show the details of datasets, baselines and configuration of experiments. We set the dimension of p j , q j (embedding vectors of item j) d = 64, learning rate η = 10 −3 , client ratio e = 10 −2 , hyperparameter γ = 1, hyperparameter of Adam β 1 = 0.9, β 2 = 0.999, and the regularization coefficient λ = 10 −4 . All hyperparameter of baseline methods that are not mentioned above are set to their default value. All experiments are run on the same machine with i7-5820K CPU, 64GB RAM, and three GeForce GTX TITAN X GPU.

H Additional experiments
In this section, we show the results of three additional experiments. Section H.