Communication Efficient Fair Federated Recommender System
Authors: KIRANDEEP KAUR
Sujit Gujar
Shweta Jain
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Recommender Systems
Bias and Fairness

Abstract: Federated Recommender Systems (FRSs) aim to provide recommendations to clients in a distributed manner with privacy preservation. FRSs suffer from high communication costs due to the communication between the server and many clients. Some past literature on federated supervised learning shows that sampling clients randomly improve communication efficiency without jeopardizing accuracy. However, each user is considered a separate client in FRS and clients communicate only item gradients. Thus, incorporating random sampling and determining the number of clients to be sampled in each communication round to retain the model's accuracy in FRS becomes challenging. This paper provides sample complexity bounds on the number of clients that must be sampled in an FRS to preserve accuracy. Next, we consider the issue of demographic bias in FRS, quantified as the difference in the average error rates across different groups. Supervised learning algorithms mitigate the group bias by adding the fairness constraint in the training loss, which requires sharing protected attributes with the server. This is prohibited in a federated setting to ensure clients' privacy. We design \ouralgo, a Random Sampling based Fair Federated Recommender System, which trains to achieve a fair global model. In addition, it also trains local clients towards a fair global model to reduce demographic bias at the client level without the need to share their protected attributes. We empirically demonstrate all our results across the two most popular real-world datasets (ML1M, ML100k) and different sensitive features (age and gender) to prove that RS-FairFRS helps reduce communication cost and demographic bias with improved model accuracy.


Under review as a conference paper at ICLR 2023
RS-FAIRERS: COMMUNICATION EFFICIENT
FAIR
FEDERATED RECOMMENDER SAIIERRSSSEEE SYSTEM
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Recommender Systems (FRSs) aim provide recommendations clients in distributed manner with privacy preservation. FRSs suffer from high communication costs due to the communication between the server and many clients. Some past literature on federated supervised learning shows that sam- pling clients randomly improve communication efficiency without jeopardizing accuracy. However, each user is considered a separate client in FRS and clients communicate only item gradients. Thus, incorporating random sampling and de- termining the number of clients to be sampled in each communication round retain the model's 's accuracy in FRS becomes challenging. This paper provides sample complexity bounds the number of clients that must be sampled in FRS to preserve accuracy. Next, we consider the issue of demographic bias in FRS, quantified as the difference in the average error rates across different groups. Supervised learning algorithms mitigate the group bias by adding the fairness con- straint the training loss, which requires sharing protected attributes with the server. This is prohibited in federated setting to ensure clients' privacy. We design RS- RS-FAIR Random Sampling based Fair Federated Recommender System, which trains to achieve a fair global model. In addition, it also trains local clients towards a fair global model to reduce demographic bias at the client level without the need to share their protected attributes. We empirically demonstrate across the two most popular real-world datasets (MLIM, ML100k) and different sensitive features (age and gender) that RS- AS-FAIRFRS helps reduce communica- tion cost and demographic bias with improved model accuracy.
INTRODUCTION
Recommender systems (RSs) have a wide variety of applications in online platforms like e-business, e-commerce, e-learning, e-tourism, music and movie recommendation engines (Lu et al. (2015) Traditional RSs require gathering clients' private information at the central server, leading to seri- privacy and security risks. ML models can train locally due to edge devices' increased storage and processing power. This has led to Federated learning (FL) (McMahan et al.) (2017)). which allows clients share their updates with the server without any data transfer. The server proposes a common model which is communicated with all clients. Using their data and the global model, clients train locally and communicate the updated model the server. FL has found many applica- tions in the past few years, e.g., Google keyboard query suggestion (Yang et al. (2018)), smartphone voice assistant, mobile edge computing, and visual object detection (Aledhari et al. (2020)). These applications face numerous challenges including communication efficiency (Smith et al. (0188) )
statistical heterogeneity (Smith et al. (2017)). systems heterogeneity (Bonawitz et al. (2019), pri- vacy, personalization, fairness (Kairouz et al. (202T)) and many more. This paper focuses on two primary issues: communication efficiency and demographic bias FRSs.
Unlike other applications of FL., where one client has data of many users. in FRS, each user acts as one client constituting a user's profile. FedRec (Lin et al. (202I)). an FRS, expects all the clients to train parallelly using matrix factorizaiion (MF). In each communication round, the server aggregates the model updates from a huge number of local clients to obtain a global model, and this global model is then sent back to all the clients. This whole procedure increases the communication cost. We show that random sampling of clients in each communication round reduces the communication cost even when only item gradients of sampled users communicated. Theoretically, we provide

---

Under review as a conference paper at ICLR 2023
bounds an ideal fraction of clients to be sampled to maintain the model's accuracy. Proving sample complexity bounds is non-trivial as the clients may possess non-lID data. To circumvent this issue, assume an underlying clustering structure on the clients such that clients within cluster share similar item vectors. The main novelty lies in proving that the random sampling will fetch enough representation from each cluster and the predicted ratings obtained after sampling small number of clients will not be far (with high probability) from that of predicted ratings obtained after communicating with all clients in all the rounds.
Fairness in FRSs is a critical yet under-investigated area. Empirically, we prove that FedRec offers better recommendations
particular group of clients. This unfair treatment can fortify the social stereotypes based on gender, race, or age. resulting in significant repercussions. So far, researchers have studied fairness in the domain of centralized RSs (Li al. (2022)). Many past works (Islam et al. (2019): Yao & Huang (2017); [Li et al. (2021); Yang et al. (2020a)) develop bias mitigation strategies in traditional RSs, which require sharing sensitive attributes with the server, causing pri-
vacy leakage in the federated setting. In FL framework, Yue et al. 2022 ; Kanaparthy et al. (202
Du et al. (020): Zhang et al. (2020) ameliorate bias in classification setting where each client pos- sesses data of many users and thus can train for fairness in each communication round. As opposed to this, in FRS, each user acts as one client that sends its item gradients to the server after updating the user vectors and item gradients locally. This makes it extremely difficult to train locally towards fairness. We propose a dual-fair vector update technique with two phases. In Phase 1, the server aggregates the received item vectors and trains them towards fairness on small fraction of data. Even if the global model is fair, local client updates may result in a heavily biased model. Thus in Phase 2, the clients minimize local error and learn item vectors closer to the globally fair vectors. In summary, our work aims at mitigating the issues of reducing the communication bottleneck and group bias in Federated Recommendation system (FedRec) (Yang et al. (2020b) for the first time. We list down our main contributions below:
1. We provide sample complexity bounds on the fraction of clients required for maintaining accuracy within the desirable limit Theorem4411 Our experiments prove that sampling these many clients improve communication costs in FRS without affecting accuracy even when the clients do not disclose their user vectors and share only updated item gradients.
2. We show the existence of group bias in FRS quantified by evaluating discrepancies in the average group losses for each sensitive attribute. To mitigate this issue, propose novel dual-fairness vector update technique that tackles the issue of group fairness at local as well as global level.
3. Combining the ideas of random-sampling and fuil-faireess vector update, propose RS- FAIRERS, a novel FRS model which provides communication efficiency and improved fairness as well as accuracy.
4. We show that RS- RS-FAIRERS mitigates demographic bias and improves accuracy via ex- tensive experimentation on the two most popular datasets of MLIM and ML100K, with different demographies (age and gender).
2 RELATED WORK
We divide the literature review into four sections: (i) federated recommender systems (FRS), (ii) client sampling in federated learning, (ii) fairness in centralized RSs, and (iv) fair federated learning models. We emphasize that there does not exist any work which targets fairesss in FRS.
Federated Recommender Systems (FRS): Federated Collaborative Filtering (FCF) (ud din (219)) is the first FRS to use implicit feedback for providing personalized recommendations. Lin et al. (02T)) identifies the need for an FRS that uses explicit ratings and proposes FedRec that deploys two techniques- Hybrid Filling (HF) and User Averaging (UA) for privacy preservation. Researchers have been actively exploring many areas of research in FRS like denoising (Liang el al.
(2021)) ), personalization (Jalalirad et al. (2019): Anelli et al. (202I)) privacy enhancement (Wang
et al. 2021 Hu et al. (2021) Ali et al. (2021) )) building robust FRS (Wu et al. (2022); Zhang
et al. 2022g Rong et al. (2022) 2.222igttttating cold-start issue (Wahab al. (2022)). and improving
accuracy of FRS (Perifanis
Efraimidis (2022). FedFast (Muhammad et al. (2020) speeds up
training in FRS by using an active sampling technique based the clustering of the user vectors.
2

---

Under review as a conference paper at ICLR 2023
However, Lin et al. (2021) argues that only item vectors of clients should be shared with the server to preserve clients' privacy. Further, [Saito et al. (2019) explaints that usage of implicit feedback leads to the positive-unlabeled problem. Thus, model. It uses explicit feedback, unlike the other existing models like FCF (ud din et al. (2019). NCF (Perifanis & Efraimidis (2022)) and Federank (Anelli al. (202T)) which either user implicit feedback or convert explicit ratings to implicit feedback. Moreover, none of the aforementioned works investigates fairness in federated recommendations. We identify two major challenges of high communication costs and demographic bias, which remain uninvestigated. Since client sampling methods can significantly reduce communication costs, we now discuss some existing papers that use random sampling in FL..
aim to analyze FedRec (Lin et al. (202I)) our base
Client Sampling in Federated Learning: Malinovsky et al. 2022) terms the selection of a batch of clients by the server for participation in the training process as partial participation and demonstrate that local steps can help to overcome the communication bottleneck. Charles et al. 2021 conducted extensive experiments to elicit significant challenges such as generalization issues, diminishing returns, training failures, and fairness concerns due to using large cohorts in FL models. Authors in (Balakrishnan et al.] (2022)) adopt greedy strategy to select clients to represent the overall population and provide convergence guarantees for the same. [Faaooni et al. (2021a) used clustered sampling for better client representation and reduced variance of stochastic aggregation weight, and[Chen et al. (2020) restricted the number of clients allowed to communicate their updates to the server. Finally, |Fraboni et al. (202Ib) studies the impact of client sampling on the convergence of models. While all the above methods assume unbiased client selection, another line of work by Cho et al. 2020) offers the first federated optimization convergence study for biased client selection techniques. Compared to classification settings, FRSs are different as out of the user, only item gradients are communicated
the server. None of the above papers provide bounds on the ideal number of samples required during communication even in federated learning setting. This paper, for the first time provides the sample complexity bounds with respect to FRSs.
Group Fairness in RSs: Xiao et al. (2017) study group fairness by maximizing the satisfaction of each group while minimizing the unfairness between them. Fu ct al. (2020) propose a fairness constrained approach via heuristic re-ranking to mitigate group bias in explainable RSs. Li et al. (2021) categorizes clients into advantaged and disadvantaged groups according to their activity level and provides re-ranking approach to debias the recommendations. Beutel et al. (209)) introduce novel metrics using pairwise comparisons to provide reasoning to bias and offer a regularizer to encourage improving the corresponding metric. Yao & Huang (017) formalizes four novel metrics to quantify demographic bias and introduce a regularizer term in the objective function to mitigate demographic bias; this approach is somewhat similar to Padala & Gujar (2020). All these methods require the availability of sensitive features of clients to get fair recommendations. leading to privacy leakage in federated settings. A few fair approaches like (Edizel el. (2020)] [Bobadilla et al. (0200) do not require sensitive attributes for mitigating bias but learn disparity from data while training to get unbiased recommendations for the clients whose demographics are unknown. However, FedRec only permits sharing item vector updates with the server, thus making these techniques inapplicable
to building fair FRS. Unlike all these approaches, our model RS-FAIRERS uses an in-processing method that neither disturbs the original data nor requires information leakage to the server.
Group Fairness in Federated Learning: Papadaki et al. (0022) provides an optimization al- gorithm to improve group fairness with similar performance guarantees to centralized ML models. Kanaparthy et al. (2021) proposes four heuristics by considering balanced and heterogeneous data cases separately for fair federated classification models. Yuu et al. (202I) propose GI-Fair tackle group and individual fairness in FLSS by using a regularization term to penalize the spread in the aggregated loss. Recent work by Hu et al. (2022) uses the concept of bounded group loss to pro- vide theoretical guarantees in group fairness. All these works were proposed to solve the issue of demographic fairness in a federated classification setting. They can not be applied FRS as FRS each user acts as one client, unlike classification, where one client can have data of many users. Unique from all other methods, RS-FAIRFRS is the first algorithm to provide dual-fairness vector updation in FRS by learning locally towards the global fair model for local fairness and achieving global fairness by training aggregated vectors towards fairness.
3

---

Under review as a conference paper at ICLR 2023
3 PRELIMINARIES
In a typical FRS with explicit feedback, we have n users (or clients), u E (1,2,3, ...........17 n) and items, rating given by a client to an item i. The true ratings given by the user and predicted ratings are denoted using Tui and fui. respectively. We assume that Tui 0 if the client has not rated an item. Pui E {0, 1} acts as an indicator variable for rated and unrated items. FedRec uses matrix factorization that identifies the latent structure behind the data to generate two matrices U E Rn*k and V E R in way that each client u is associated with vector U,, E R lxx called as user vector and each item i is associated with vector V, E R termed as item vector. The predicted rating of 1th item by uhhh user can be computed as fui = V..VV.. The goal of FedRec is then to learn the user vectors (locally) and item vectors globally to minimize the loss function:
RedRec:
2, ................................ m]. ........................ Each client has it's rating vector [rull that depicts the
CM = Σ Σ
Pus(rus U.. V,. V/2 11 + 11 U, 113)
(1)
ME(N] kE[m)
FedRec aims at predicting the rating of a client for each item i without sharing their rating be- haviors or records. For this, some unrated items are randomly sampled using sampling parameter and assigned virtual rating. Then, item gradients (u(,,)) i) for both truly as well as virtually rated items are shared with the server. The server than aggregates these gradients and sends back the aggregated item vectors all the clients. Additionally, each client also computes the user gradient VU,, locally and is not shared with the server. Next section proposes RS-FAIRFRS that solves the issue of communication inefficiency in FRS and mitigates demographic bias.
PROPOSED METHODOLOGY
To reduce the communication cost, randomly sample clients in each communication round who communicate (V, i) with the server. Randomly sampling the clients has been proposed in liter- ature under supervised federated learning (Charles al. (2021): Fraboni al. 2021 Cho et al.) ) However, since each client is a separate user in FRS and user only shares the item gradients with the server, it is not clear if random sampling will aid the recommender system to reduce com- munication cost without affecting its accuracy in federated setting. More importantly, the main question is that how many clients should we sample in each communication round. To answer this question, next section provides sample complexity bounds on the number of clients required to be sampled to obtained the desired accuracy.
4.1 RANDOM SAMPLING WITHOUT REPLACEMENT
Unlike FedRec (Ln et al. (2021) where the server aggregates item vectors after all the clients have sent their updates, in RS--RAFFR FRSR the server uniformly samples a fraction of n clients. It is well known that the users in FL. are non-IlI. However, users who provide ratings items tend to possess an underlying clustered structure. Various algorithms (Koren et al. (2009): Gupta et al. (2020)) work by identifying the latent patterns of users provide recommendations and within the cluster, users are IID. We aim to utilize this homogeneity within the same clusters without the knowledge of the K clusters and the users belonging to each cluster. For random sampling to work, it is important that the sampled set of clients C' must represent the entire population. In the first result, we show that when certain number of clients are sampled randomly at uniform, they represent each cluster equally to ensure that this sampled set is enough to represent the entire population.
Lemma 1 Suppose clients are uniformly distributed amongst K clusters. Then, subset S C [n]] sampled uniformly at random (without replacement) will contain an approximately equal number of clients from each cluster.
We use Hoeffding's 's bound (Sertling (1974)), which holds for sampling without replacement but provides very loose bound. Let X² E {0, denote the random variable taking the value 1 when 5th sample belong to cluster j and 0 othersise. Then using Hoeffding's bound, we get
2.2 [S] f. If we take |C=| = 2100, ie. 35% of the total number of clients (6000), then we get this probability to be roughly around 0.62, which is obtained at K 10.
X
K N < eexp
4

---

Under review as a conference paper at ICLR 2023
Hoeffding's inequality provides a very loose bound but actually this probability is very high which is evident from some basic experiments provided in the Appendix.
Lemma 2 Given clients during the training, T represents the fraction of clients sampled for each communication round. If V nr Eiegr Vú denote the average of item vectors over some C clients and V 1 - V represent the average of item vectors over total n clients. Then, E V. = E V!
Here, V.V. and V." denotes the predicted rating of any user when aggregated item vectors obtained only via the sampled users and all the clients in the training set respectively. This lemma holds inherently true if the underlying clients are homogeneous which is true in FL. Thus use the latent clustering assumption and Lemma to prove that the expected values of predicted ratings of sampled as well the entire population are equal. The detailed proof is provided in Appendix.
Now, we state our main theorem below:
Theorem 4.1 (Random Sampling of Clients) Given (U Fu=1s (V:).= > denote a Federated Recomnendation Model with predicted ratings ly- ing within a range la, b). If V. = az Eiecr Vi and V." = n Ei= V3 represent the average of item vectors over some fraction of clients and total n respectvvy then
rating matrix R, let
PO - - 2 5
2(b - a}
The above theorem can be proved using Hoeffding's bound and Lemma According the above theorem, if the ratings lie between [1, 5). then the probability that the error in predicted rating is more than 10% is less than 1% with just 35% clients from the pool of 6000 clients. Therefore, from our theorem if a dataset has around 6000 clients, we chose r = 0.35 in our experiments. important note that our main contribution lies in showing that while bounding the sample complexity, in general, is hard problem, clustering assumption on the underlying data makes it possible to provide the non non-trivial bounds. Without this assumption, straightforward use of Hoeffd- ing's ' inequality will give trivial bounds of 100% on the sample complexity, whereas we need only 30%. important to note that we assume the existence of clusters of item vectors with almost equal number of vectors in each cluster for theoretical analysis. We prove the same experimen- tally in Appendix. Furthermore, the clustering only aids in acquiring bound on ideal fraction of clients to be sampled. The fairesss of RS-FAIRFRSS out groups (age/gender). Since private clustering is an open challenge FL and forming clusters require sharing of sensitive attributes, RS-FAIRFRSensurr privacy to most of its users by hiding their demographics from the server.
independent of any clustering with with-
4.2 DUAL-FAIL FAIR UPDATE
This section firstly discusses the inability of existing fairness notions in RSs to be able measure group bias in federated setting. We then propose fairness metric which when added as a constraint in optimization function at server helps achieve fair global model. Furthermomre, we discuss two phase mechanism which helps in achieving global as well as local fairness.
Existing fairness notions in RS, namely value unfairness, absolute unfairness, and non-parity fair- ness (Yao & Huang (2017) consider the difference in average loss on a specific item i concerning users belonging to advantaged and disadvantaged groups. It is not feasible FL as each client is distinct and prohibited from sharing its ratings with the server and other clients. Moreover, Man- soury et al. (2020) mentions profile size as an important factor in group bias as more active clients receive better recommendations. We define user activeness the number of items rated by user, iee. a user is more active he or she has rated more items In out of all the items in the item set I. Thus, with assumption of a binary attribute, our metric accuracy parity (LeP) normalizes the sum of squared loss over all the items rated by client and is given as:
Σ (fui Twi)
Σ
Σ (fui -ra))² IEL
(2)
WEB
Iel.
WE
Here, g and -g denote the disadvantaged and advantaged groups, respectively. L, is the set of items rated by u and Pui Tui depict the predicted and true ratings, respectively. For models 0 and 0,
5

---

Under review as a conference paper at ICLR 2023
say that is demographically fairer model if (f) (O)( Designing fair FRS involves tackling three significant challenges which must be tackled. (i)Designing debiasing techniques for local clients becomes challenging if they are reluctant to share their sensitive attributes (Ezzeldin et al. (02T)) Considering the settings where each user is not one client, local fairness does not ensure global fairness in FI.. The non-Ill) data in FL makes it impossible for the entire distribution to be represented by one standard distribution, (ii) To achieve fairness, simple federated models usually do weighted aggregation; however, it becomes infeasible assign weights the updates sent to the server without knowing the group to which they belong. Dual-Fair Updation involves training towards fairness in two phases described below.
FairMF; We assume the availability of data of very few (20%) clients Dserver at the server for evaluating the fairness loss. This assumption was also considered by Kanaparthy et al. (2021) for building fair federated model for face classification. Previous works considered 5% of the overall data on the server. Choosing 5% of the overall data in RSs may lead to the privacy leakage of more users. Hence, instead of selecting 5% of the entire population, select data of only 20% of the users. This assumption helps achieve fairness without expecting clients to reveal their private sensitive attributes the server even during training. Therefore, unlike simple FRS, the server in RS-FAIRFRS not only aggregates but also helps achieve fairness. We denote each client at the server as 8 E {1, [],.....)) such that S << n,, i.e. the number of clients the server will always be much less than the number of local clients. FairMF trains the data at server Deerver for obtaining global fairness objective. The goal of FairMF is optimize the loss function defined as the combination of regularized MF (equation I and fairness penalty (equation 2) The final loss function is
min MF + C U.V
(3)
The hyperparameter A acts as a faimess penalizer. The update equations for client vector U, and item vector are obtained by taking derivatives of the fairness loss function with respect to client and item vectors respectively. Server runs FairMF for some iterations t, and obtains final U and Vjair. Finally, Vjair and mm (aggregated item vectors) are communicated to all the clients. We provide the exact procedure for FairMF in Algorithm
Fairness Oriented Client Batch ensures local fairness by learning locally towards fair global model. Each client downloads both Vfair and Vú from the server. While Vfair contributes towards fairness, communication of aggregated V3 provide each user with the benefit of other users' participation. Since in FL models global fairness does not ensure local fairness, it is important that each local client also trains towards the fair model. Then, each user vector is updated locally, followed by an updation in the Vi towards Vfair- Thus the local objective function changes
FO-ClientBatch:
min MF + Vlair Vill?) U.V
Clients keep
VU, below
with themselves and communicate only VV to the server. describes the detailed algorithm and communication details.
The section
Algorithm 2 ClientFilling( V
Algorithm FairMF (D (Derrver Utair: V)
1, 2, ...., my Un: u; ()
1: for Tg = 1, ..... to do for each (s. in D Deerver do
1: if strategy = HF then
2:
2:
for ltoca 1,2, ..... Tiocel do
3: rf.. of O, update U, and V; by cal- culating gradients by differentiating equa-
3:
Calculate the gradient VU, Un, t VVU
tion equation 3
4:
5:
end for
4: end for
5: end for
6:
Assign r.s to each item i E I, via HF
6: Ufair +- U.. Vjair + V₁
7:
else
7: return Fair, Vjair
8:
Assign r'm to each item E I, via UA
9:
end if
4.3 RS-FAIRERS
Algorithm describes RS- RS-FAIRERS in whole. With the assumption of the availability of small dataset (D (eerwer) corresponding to s users at the server, the procedure begins by initializing V =
[V]]e, and U [U,]i=ı which represent the item and user vectors respectively. Then, some

---

Under review as a conference paper at ICLR 2023
Algorithm 3 RS-FairFedRec Communication Efficient and Fairness Aware Federated Recom- mender System
Input: D Dserver, D Dirains T, T, M a, Output: Un, V33
1: Initialize V == [ and U [U_]
2: for t= 1.2, ......... do
3:
C + -Randdolly sub-sample T fraction of clients from all the users in Dirain }
4: Usair, Vfair < FairMF(D seruer. V (air)
5:
for each client E U in parallel do
6:
Sample L, from 1 Ve with |4ب| p|4ul 1, ...., m,; Uni u,
7:
ClientFilingg(
8:
Calculate the gradients VU, and (V, by differentiating equation Update Un via Ua + Un VVU
9:
10:
end for for -ari= I........ do
11:
12:
Calculate the aggregated gradient VV, for clients in C
13:
Update V, V1 VV,
14:
end for
15:
Decrease the learning rate 7 0.9r
16: end for
fraction of total clients present in the training dataset (Dtrain) are randomly sampled by the server denoted by C The assumption of D Dserver helps in obtaining fair item vectors Vfair which are communicated all the clients for local fairness. Alongwith these, V also sent to each client to retain the federated properties of FedRec and allow benefits of the participation of other clients. For initial round, the initialized item vectors are communicated, however as the training preoceeds, V gets updated by the aggregated item vectors. Further, the server aggregates item vectors sent by C" clients only. The fair item vectors V/air and aggregated item vectors communicated by the server are received by each client u and local training happen at all the clients. Similar to FedRec, using UA, every client will receive some (p) virtual ratings. In UA, some unrated items are sampled and then virtual rating rus is assigned to these items. In HF, after a certain amount of time Treedict the virtual rating is replaced by the predicted rating. To acquire predicted rating each client evaluates its user gradients and then updates its user vector. This procedure is called Client Filling (Lin et al. (202T)) explained in Algorithm The user and item gradients are evaluated simply by differentiating the equation 4 The proposed local objective minimizes the squared loss between the global item vectors and local ones. The updated item gradients are uploaded to the server train FairMF on the D Deerver and obtains Uaai and Vyoir. This procedure is repeated till convergence.
EXPERIMENTS
We empirically show that (i) random sub-sampling of clients reduces communication costs without any slump in accuracy of an FRS (ii) FedRec suffers heavily from demographic bias, and (iii) RS- FAIRFRS significantly reduces bias without any leakage of client's privacy and improves accuracy.
5.1 EXPERIMENTAL SET-UP
We use two benchmark datasets MI.IM and MI.10OK with explicit ratings ranging from to S. ML/M dataset consists of 1, 000, 209 ratings of 3, 706 movies by 6, 040 users and ML/00K consists of 943 users with 100, 000 ratings for 1, 682 items. MLIM has 4, 331 males and 1, 709 females; also, there are 5, 818 people with age 18 and 212 users with age < 18. Similarly, in ML.00K. users with age above 18 (889) are much more than ones with under 18 (54). Furthermore, ML100k has only 273 females as compared to 670 males. All our experiments use RMSE (Root Mean Square Error) as used by Lin et al. (2021) to provide a fair comparison of the accuracy of our model with

---

Under review as a conference paper at ICLR 2023
Tacket of wINCROE
(a) RMSE
(b) Time sec)
Figure 1:
Comparison plots for accuracy and average time per communication round on different values of in RS-FedRec on two datasets MLIM and ML100k
28
Calegrry
Sena thee A11
(a) MLIM
(b) ML100K
Figure 2: Difference in RMSE scores for different sensitive attributes by FedRec over two datasets.
the FedRec. We also provide analysis of Group Losses, calculated using the average of the RMSE score of all clients belonging to a certain group. Finally, we use L [equation 2 to evaluate demographic bias in all the experiments. We split each dataset randomly by keeping 20% of the data for the test set and the rest for training. Similar to Lin et al. (2021), we use A 20 latent features and set the value of sampling parameter to p = 2. We run all the models till convergence (T 20) and the FairMF procedure is executed to t. = 15 runs. We report all our results over an average of runs. The final tuned hyperparameter values and other details are provided in the Appendix. While it can be apparent that more data on the server will yield better performance, we run all our experiments on RS-FAIRFRSwin 100% and RS-FAIRERS with 20% data on the server to show that even with all the data on the server, RS-FAIRFRS with only 20% data provide much better accuracy as well as fairness. For exact numbers of the training and testing results, refer Appendix. Now we provide interesting results via various graphical representations.
5.2 EMPIRICAL EVALUATION
Random Sampling of Clients without Replacement: We randomly sample fraction of all the available clients. The model's accuracy is analyzed for wide range of values in Figure Ta Our model has very high error for small values. This indicates the failure converge and with around 35% of clients, the model performs nearly the same as with 100% clients. From Theorem it can be shown that the predicted rating of each client with sampled item vectors will be within 5% error with a probability of at least 0.96. In line with the findings of Charles et al. (021). increasing increases the training loss. Figure (rpresenss the average time taken (in sec) for one communication round by FedRec with different values of r. From these inferences, for all our experiments we select 7 35 as ideal value which provides reasonable accuracy in very less time.
To demonstrate the biased treat- ment FedRec towards certain sensitive groups, we compute average losses on each sensitive attribute. Figure 2 shows that the groups with more number of clients (advantaged groups) enjoy more accurate recommendations where as ones with lesser number of clients (disadvantaged groups) receive more erroneous recommendations, In both the datasets, clients with age > 18 enjoy recom- mendations with lesser RMSE as compared to the ones with age < 18. Similarly, females of both the datasets obtain recommendations with much higher RMSE compared to the males. This shows
Disparate treatment of FedRec for certain sensitive attributes:
8

---

Under review as a conference paper at ICLR 2023
225
0.2
0.55
Commurkcatinn 1u
Communcciion round
Communicaiion mund ET
communicaiio mund
(a) MLlM[Agel
(b) MLIM[Gender]
(c) Agel
(d) MLLOOk[[ender]
Figure 3: Lap on two datasets and two different demographics for different algorithms.
26223
E220 pccumtspon
0.04
C32
(3.70
0.123
5.100
0.90 use
2022 UAA
0A2
0.44
0.00
0.0
0.2
0.04
6.00
3.66
0.90
(a) ML.MM[Aee]
(h) MLIM[Gender]
(c) Agel
(d) |0.000[[Gender]
Figure 4: Fairness vs Accuracy plots
that the existing class imbalance affects the recommendations provided by FedRec which motivates us to develop a fair FedRec that trains towards mitigating this disparate treatment of FedRec.
Fairness of RS-FAIRFRS: To analyze fairness of RS-FAIRERS, we compare our results with FedRec, RS-FedRec (FedRec with sampling) and RS- RS-FAIRERS with (100%) data at the server. We also provide bias results on MF to show that FedRec amplifies the bias due to aggregation. In Figure show that only (20%) of client's data at the server helps in achieving better faimess than 100% because our model uses random sampling of clients in each round. The sampled clients make use of the server dataset to obtain fair results. 100% data on the server includes many outliers which worsens the fairness of sampled clients thus generating poor fairness as well as accuracy. Our results in Appendix show that even with only 25% and 50% of the items at the server, our model is able to reduce bias. Further, it is important to note that our model uses randomly initialized user and item vectors. Slowly as the training proceeds towards minima, the random vectors get trained and updated to obtain closest rating predictions. Thus, over period of time, the curve smoothens but the initial readings can be very fluctuating. is evident from all the four graphs in Figure 3 that RS-FAIRERS with 20% data the server manages acquire least bias on both the datasets for all the sensitive attributes. Thus, RS-FAIRERS (20%) manages to significantly reduce the bias in FedRec without leaking any sensitive information of most of the users during training.
Fairness vs Accuracy in RS-FAIRFRS: RS- FAIRFRS improves group bias and generates more accurate recommendations. We compute RMSE as well _e to depict the excellence of our model in both the aspects. Figure 4 shows that RS-FAIRR S (2%% provides more fair and accurate rec- ommendations the clients in both datasets for both the genders as well users with age above and under 18. It can be casily inferred that a lower value in both Demographic bias and RMSE accounts for better model. Users belonging both the age groups in ML100k dataset enjoy fair recommen- dations with RS- SS-FAIIFRS(20%) Though, MF performs slightly better in terms of accuracy as well as fairness for users in MLI for gender attribute due to the efficiency of centralized settings for smaller datasets, overall, RS- RS--AIRRRS (20%) outperforms all the existing federated algorithms.
6 CONCLUSION AND FUTURE WORK
We propose RS RS-FAIRERS which incorporates two key ideas (i) random sampling of clients to re- duce the communication cost, and (ii) dual-fair updation to mitigate group bias. We are first to theoretically bound the sample complexity on the fraction of clients to be sampled without affecting model's s accuracy. We empirically demonstrate our thcoretical results and provide extensive exper- iments to show that we can achieve much-reduced bias and improved model accuracy. Exploring various other types of biases in FRSs can be an interesting research direction. We would also like to extend our analysis provide theoretical fairness guarantees of RS- RS-FAIRFRS and explore the usage of dual-fair updation-like techniques in many other FL domains in future.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammed Aledhari, Rehma Razzak, Reza M. Parizi, and Fahad Saced. Federated learning: A survey on enabling technologies, protocols, and applications. IEEE Access, 14440699-140225. 2020. doi: 10. 11110///CCESSS2000.......
Waqar Ali, Rajesh Kumar, Zhiyi Deng, Yansong Wang, and Jie Shao. A federated learning approach for privacy protection in context-aware recommender systems. The Computer Journal, 64(7): 1016-1027, 2021.
Vito Walter Anelli, Yashar Deldjoo, Tommaso Di Noia, Antonio Ferrara, and Fedelucio Narducci. Federank: User controlled feedback with federated recommender systems. In European Confer- ence on Information Retrieval, pp. 32-47. Springer, 2021.
Ravikumar Balakrishnan, Tian Li. Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning via submodular maximization. In International Conference on Learning Representations, 2022. TRRLhttpss//pppereee/ Idd=nWKyFvaümm
net forum?
Alex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Li Wei, Yi Wu, Lukasz Heldt, Zhe Zhao, Lichan Hong, Ed H Chi, et al. Fairness in recommendation ranking through pairwise comparisons. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2212-2220, 2019.
Jesús Bobadilla, Raúl learning for improving fairness in recommender systems. arXiv preprint arXiv:2006.05255 2020.
Ángel González-Prieto, and Fernando Ortega. Deepfair: deep
Hans-Hermann Bock. Clustering methods: history of k-means algorithms. Selected contributions in data analysis and classification, pp. 161-172, 2007.
Keith Bonawitz, Hubert Eichner, Wolfgang Gricskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning at scale: System design. Proceedings of Machine Learning and Systems, 1: 374 388, 2019.
Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large- cohort training for federated learning. CoRR, abs/2106.07820, 2021. URL httpps:/://:
arg/abs/2100 07820
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. CoRR, abs/2010.13723, 2020. /RL./ttpss//ccxx..org//
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection federated learning: Convergence analysis and power-of-choice selection strategies. CoRR, abs/2010.01243, 2020. URL https:
01244
Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness-aware agnostic federated learning, 2020.
Bora Edizel, Francesco Bonchi, Sara Hajian, André Panisson, and Tamir Tassa. Fairecsys: mit- igating algorithmic bias in recommender systems. International Journal of Data Science and Analytics, 9(2):177-133 2020.
Yahya H Ezzeldin, Shen Yan, Chaoyang He, Emilio Ferrara, and Salman Avestimehr. Fairfed:
Enabling group fairness federated learning. arXiv preprint arXiv:2110.00857, 2021.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low- variance and improved representativity for clients selsection in federated learning. CoRR, abs/2105.05883, la. URL URLppttss://axxiitt org/ abs http:/bb/2200000 /200/ 05883
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. On the impact of client sampling on federated learning convergence. CoRR, abx/2107.12211. 2021b. URL https: : //arxiv.
org/abs/220 /107. 12211
10

---

Under review as a conference paper at ICLR 2023
Zuohui Fu, Yikun Xian, Ruoyuan Gao, Jieyu Zhao, Qiaoying Huang, Yingqiang Ge, Shuyuan Xu, Shijie Geng, Chirag Shah, Yongfeng Zhang. et al. Fairness-aware explainable recommendation over knowledge graphs. In Proceedings of the 43rd International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 69-78, 2020.
Meenu Gupta, Aditya Thakkar, Vishal Gupta, Dhruv Pratap Singh Rathore, al. Movie recom- mender system using collaborative filtering. In 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC), pp. 415 420. IEEE, 2020.
Nils Olof Hedman, Roine Johansson, and Urban Rosenqvist. Clustering and inertia: structural integration of home care swedish elderly care. International Journal of Integrated Care, 7, 2007.
Hongsheng Hu, Gillian Dobbie, Zoran Salcic, Meng Liu, Jianbing Zhang, Lingjuan Lyu, and Xuyun Zhang. Differentially private locality sensitive hashing based federated recommender system. Concurrency and Computation: Practice and Experience, pp. e6233, 2021.
Shengyuan Hu, Zhiwei Steven Wu, and Virginia Smith. Fair federated learning via bounded group loss, 2022. /ttpps:s:////xxi wttp:xivorrr/bb///222/ http://bb/220...0000
Rashidul Islam, Kamrun Naher Keya, Shimei Pan, and James Foulds. Mitigating demographic biases social media-based recommender systems. KDD (Social Impact Track). 2019.
Amir Jalalirad, Marco Scavuzzo, Catalin Capota, and Michael Sprague. A simple and efficient federated recommender system. In Proceedings of the 6th IEEF/ACM International Conference Big Data Computing, Applications and Technologies, BDCAT '19, pp. 53-58, New York, NY, USA, 2019. Association for Computing Machinery, ISBN 978 450370016. 3365 15.11099333888 /tt/httpss://.llorr//////// 110.0...14433300 335 09 001.55099.3338888 3368788
doi: 10.1145/
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Ad- vances and open problems in federated learning, Foundations and Trends@ in Machine Learning, 14(1-2):1-21) 2021.
Samhita Kanaparthy, Manisha Padala, Sankarshan Damle, and Sujit Gujar. Fair federated learning for heterogeneous face data, 2021.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Yunqi Li, Hanxiong Chen, Zuohui Fu, Yingqiang Ge, and Yongfeng Zhang. User-oriented fairness in recommendation. In Proceedings of the Web Conference 2021, pp. 624 632, 2021.
Yunqi Li, Hanxiong Chen, Shuyuan Xu, Yingqiang Ge, Juntao Tan, Shuchang Liu, and Yongfeng Zhang. Fairness in recommendation: A survey, 2022. URL httptt:///exxi.....tt
abs/
2205.1361
Feng Liang, Weike Pan, and Zhong Ming. Fedrec++: Lossless federated recommendation with explicit feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):2224 4231, May 2021. URL/ttps::// www.aai...iiinneeeeeeeeeeeeeeeee http:ppptpppptcclleeeeeeee 16546
Guanyu Lin, Feng Liang, Weike Pan, and Zhong Ming. Fedrec: Federated recommendation with ex- plicit feedback. IEEE Intelligent Systems, 36(5):21-30, 2021. doi: 10. 100//M/..2000033022222
Jie Lu, Dianshuang Wu, Mingsong Mao, Wei Wang, and Guangquan Zhang. Recommender system application developments: a survey. Decision Support Systems, 74:12-32, 2015.
Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sam-
pling without replacement provably help in federated optimization. CoRR, abss/200..110e 2022. URL hhttps://aaaet .rg. abs/ 2201 attp//1sss222.2...
11066
11

---

Under review as a conference paper at ICLR 2023
Masoud Mansoury, Himan Abdollahpouri. Jessie Smith, Anman Dehpanah, Mykola Pechenizkiy, and Bamshad Mobasher, Investigating potential factors associated with gender discrimination in collaborative recommender systems. In The Thirty- Third International Flairs Conference, 2020.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication--fficinnn learning of deep networks from decentralized data, 2017.
Khalil Muhammad, Qinqin Wang, Diarmuid O O'Reilly-Morgan, Elias Tragos, Barry Smyth, Neil Hurley, James Geraci, and Aonghus Lawlor. Fedfast: Going beyond average for faster training of federated recommender systems. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery Data Mining, pp. 1234 1242, 2020.
Manisha Padala and Sujit Gujar. Fone: Achieving fairness through neural networks. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (ICCA1-20) national Joint Conferences on Artificial Intelligence Organization, 2020.
(DCCiience,(UCAAA2200 Inter-
Afroditi Papadaki, Natalia Martinez, Martin Bertran, Guillermo Sapiro, and Miguel Rodrigues. Min- imax demographic group faimeess in federated learning, arXiv preprint
2022.
Vasilcios Perifanis and Pavlos Efraimidis. Federated neural collaborative filtering, Knowledge- Based Systems, 242:108441, 2022.
Dazhong Rong, Shuai Ye, Ruoyan Zhao, Hon Ning Yuen, Jianhai Chen, and Qimming He. Fedrecat- tack: Model poisoning attack to federated recommendation. arXiv preprint urXiv:2204.01499 2022.
Yuta Saito, Suguru Yaginuma, Yuta Nishino, Hayato Sakata, and Kazuhide Nakata. Unbiased recommender learning from missing-not-at-randoo implicit feedback, 2019. URL https: //arxiv. /99p. 03601
Robert Serfling. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, pp. 39 48, 1974.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. Advances in neural information processing systems, 30, 2017.
Virginia Smith, Simone Forte, Ma Chenxin, Martin Takáë, Michael Jordan, and Martin Jaggi. Cocoa: A general framework for communication-efficeen distributed optimization. Journal of Machine Learning Research, 18:230, 2018
Muhammad Ammad ud din, Elena Ivannikova, Suleiman A. Khan, Were Oyomno, Qiang Fu, Kuan Eeik Tan, and Adrian Flanagan. Federated collaborative filtering for privacy-preserving personalized recommendation system, 2019.
Omar Abdel Wahab, Gaith Rjoub, Jamal Bentahar, and Robin Cohen. Federated against the cold: A trust-based federated learning approach to counter the cold start problem in recommendation systems. Information Sciences, 2022.
Qinyong Wang, Hongzhi Yin, Tong Chen, Junliang Yu, Alexander Zhou, and Xiangliang Zhang. Fast-adapting and privacy-preserving federated recommender system. The VLDB Journal, pp. 1-20, 2021.
Chuhan Wu, Fangzhao Wu, Tao Qi. Yongfeng Huang, and Xing Xie. Fedattack: Effective and covert poisoning attack on federated recommendation via hard sampling. arXiv preprint arXiv:2202.04997. 2022.
Lin Xiao, Zhang Min, Zhang Yongfeng, Gu Zhaoquan, Liu Yiqun, and Ma Shaoping. Faimess-awaa aware group recommendation with pafeto-efficiency. Proceedings of the Eleventh ACM Conference Recommender Systems, pp. 107-115, 2017.
Ke Yang, Joshua R Loftus, and Julia Stoyanovich. Causal intersectionality for fair ranking. arXiv preprint arXiv:2006. 2008880006088888 2020a.
12

---

Under review as a conference paper at ICLR 2023
Liu Yang, Ben Tan, Vincent W Zheng, Kai Chen, and Qiang Yang. Federated recommendation systems. In Federated Learning, pp. 221-222--552 239. Springer, 2020b.
Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ra- mage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions, 2018.
Sirui Yao and Bert Huang. Beyond parity: Fairnsss objectives for collaborative filtering. Advances in neural information processing systems, 30, 2017.
Xubo Yue, Maher Nouiched. and Raed Al Kontar. Gifair-fl: An approach for group and individual fairnsss in federated learning, 2021.
Daniel Yue Zhang, Ziyi Kou, and Dong Wang. Fairfl: fair federated learning approach to reducing demographic bias in privacy-sensitive classification models. In 2020 IEEE International Confer- ence on Big Data (Big Data), pp. 1051-1066 2020. doi: 10. LLL.0//BBDD025002220000........9
Shijie Zhang, Hongzhi Yin, Tong Chen, Zi Huang, Quoe Viet Hung Nguyen, and Lizhen Cui. pattack: Poisoning federated recommender systems for manipulating item promotion. In Pro- ceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp- 1415-1423, 2022.
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 NOTATIONS
We list down all the important and frequently used notations in Table
Symbol
Meaning
Number of clients in training set
m
Number of items in training set
K
Number of Latent factors
R {1, .......5
Rating range
Tui
True rating
fui
Predicted rating
Tui
Virtual rating
Pui
Indiactor variable
u
client
item
I
Set of all items
U
Set of clients who rated item i
U
Set of all clients who rated an item i virtually
I
Set of items rated by
I
Set of items rated virtually by
U
client vectors matrix Item vectors matrix client vector for client Item vector for an item Item gradient for jth item which was rated by user a Rating Dataset Training set
U
V.
VV(u,
R
D Dtrain
D server
Dataset at server Disadvantaged Group
Advantaged Group
p
Sampling parameter
X"
Regularizer to prevent overfitting in FairMF
f
Fairness regularizer in FairMF Learning rate in FairMF
a
T
Fraction of clients sampled for one communication round Learning Rate for clients
7
Fairness Penalizer for clients
T
Number of communication rounds
T.
Number of epochs in FairMF
Tiocal
Number of iterations required to obtain prediction in Client Filling
Table 1: Notations and their meaning
A.2 EXPERIMENTAL PROOF FOR LEMMA
This section provides the experimental proof for Lemma [
FedRee generates item vectors at each communication round. We cluster these item vectors generated by FedRec by using K-means clus-
14

---

Under review as a conference paper at ICLR 2023
tering (Bock (2007)) Figure shows the elbow curve obtained after plotting clustering loss Inrtia (Hedman et al. (2007) corresponding to the number clusters. Inertia is one the most populair metrics to evaluated clustering results. It is calculated the sum of distances to each cluster center. high value of total distance implies that the points are far from each other which is a clear indica- tion that they less similar each other. It can be seen that for both the datasets get K 20
as the ideal number of clusters.
2202
3147
1750
2203
1500
um number of
203
number clusters
(a) MLIM
(b) ML.10Kk
Figure 5: Ideal number clusters for item vectors both datasets
Considering K 20 and asssuming that we have total number of clients = 6000, we randomly assign each client to one out of 20 clusters. Then, we randomly sample some of the clients and observe some interesting observations depicted in Figure G Figure [6a shows that after sampling some clients randomly uniform, the average number of clients from each cluster are almost same. Further, Figure 6bb clearly shows that the probability of getting 15% error in above experiment as small as 7.5% when averaged over 500 runs. Finally, Figure 66 demonstrattes that minimum number of samples in each cluster is also same. Thus all the three experiments support Lemma
2054
2043
(a)
(b)
(c)
Figure 6: Experimental Analysis of Random Sampling of Clients and Clustering
A.3 THEORETICAL ANALYSIS OF CLIENT SAMPLING
We first recall Lemma] and then provides its proof below:
Lemma 2 Given clients during the training, represents the fraction of clients sampled for each communication round. If V nr Σiecr V, denote the average of item vectors over some C clients and V.n = E V, represent the average of item vectors over total clients. Then, EIU V7l BIU V*'
Proof: Let Sj denote the set of clients in cluster j. and Cj denote the set of clients sampled from cluster j. Since in each cluster, the item vectors coming from identical distribution, have ELUT V.S. = E C.C.). Here, V.S. V.C. represent the average of item vectors Vi's from sets S; and C respectively. From Lemma [ if fraction of clients are selected from n clients uniformly at random without repetition, then we have C₁ R TS₁ with high probability. Then,
V
C
Σ/=1 IC.
15

---

Under review as a conference paper at ICLR 2023
S LE [E
j=1 T
S.|
E We now recall our main Theorem 4.1 and provide its detailed proof using above Lemma and Ho- effding's bound.
rating matrix R. let Yu=1 (Vi) > denote a Federated Recommendation Model with predicted ratings ly- ing within a range la, b]. If V, + Eiegr V; and V = = - V₁ represent the average of item vectors over some fraction of clients and total n respectvvs then
Theorem 4.1 (Random Sampling of Clients) Given
-nTc²
FQUIV - -U 2 S 2exp
2(b - a)2
Proof of Theorem 4.1 From Hoeffding 's inequality, we have,
P(UU
V
E VT] 2 e)
S 2 e
70- 2n
J. and
P(IU E
eexp
2nc (b-a)-
Thus with probability atleast
2nTr² expp
o5 }. we have,
E
EUT
- E V. B
E - - U V. EIU +
(From Lemma 2
V. - 22 < V. < U V." + 2e
Thus, we get VT - V 2 t) < expp 2(b-a)²
A.4 HYPERPARAMETER TUNING
We carefully tune all the hyper-parameters and list down the final tuned values in Table It is important to note that server in FedRec and RS-FedRec acts as an aggregator. Thus, the server does not require any tuning and the final tuned values for both the algorithms account for client side parameters. Opposite to this, server in RS-FAIRFRS(JOOSS as well as RS-FAJRFRS/220% require fairness oriented training. Therefore, server side. Since, regularizers at server as well as client side prevents overfitting, we use X" to denote them, but fairness regularizer at server A trains aggregated item vectors towards fairness using D. erever and fairness regularizer at client side trains local models towards globally fair item vectors. Experimentally, we observe that all the models converge well at = 20, thus we use T 20 in all our experiments. However, while executing FairMF at the server, we train FairMF for T, = 15 after each communication round. We obtain better fairness when we train FairMF for some epochs instead of letting it converge fully over each communication round which can be time consuming and it increases the load at server too. Thus FairMF executes for only 15 epochs and provides the updated item vectors to be communicated to all the local clients.
present separate hyper-parameter values for client side and
A.5 TRAINING AND TESTING RESULTS
We report the train as well as test results of all the four federated algorithms on two real-world datasets of MLIM and ML100k with two different sensitive attributes in Tables and It is noted that similar to training results, RS- RS-FAIRFFS[20%% performs the best in terms of accuracy as well as fairness. From the tables, evident that FedRec and RS-FedRec performs nearly the same which shows that random sampling retains the model accuracy. Then, SS-FAIFFRS(20% and RS- FAIRFIIRRSII (100%) provide an empirical proof to the claim we made in the main paper which states that do not need huge amount of data at the server. With minimal
results (rows for
16

---

Under review as a conference paper at ICLR 2023
Tuned Values
Algorithm
Hyper-parameter
MLIM
ML100k
Learning Rate (7)
0.1
0.08
FedRec
Regularizer (X")
0.02
0.01
Learning Rate (7)
0.1
0.08
RS-FedRec
Regularizer (X")
0.02
0.01
Learning Rate (a)
0.012
0.009
Server
Regularizer (A")
0.05
0.02
Fairness Regularizer (A)
1.5
1.25
RS-FairFRS[20%]
Learning Rate (?)
0.5
0.2
Clients
Regularizer (X")
0.01
0.02
Fairness Regularizer (1))
1.75
1.55
Learning Rate (a)
0.04
0.15
Server
Regularizer (A")
0.05
0.01
Fairness Regularizer (A²)
2.5
2.0
RS-FairFRS[100%]
Learning Rate (7)
0.65
0.22
Clients
Regularizer (A")
0.01
0.02
Fairness Regularizer (1)
1.75
1.55
Table Hyperparameter Values
Dinasets
Anribuse
Algorithms
RMSE
RMSE Advantiged Group
RMSE Disadvaniged Group
Demegraphic Bias
Fodiiee
0.89476
0,00006
Age
RS. FairRRS [20%]]
R5-FidRRee
0 8880K112
0.00165
0.86296
0,00411
0.30506
0,80364 0.00161
0.10244 0.00660
MLIM
FairFRR [100%]
0.90466 0.00800
L0008]
= 0008
0.00711 0.00985
397
0.00285
FedRte
U.39199 1 0.00221
0.91900 = DUUUUT
0.39112 0.0003
01ST1I6 U.01215
Gender
RS. FAS [20%)
RS FedRec
0,89422 0.00010
8.86655 0.00104
0,81883 0.00404
0,91923
0.00045
0,50365 0.00655
0.39134 0.0004
0.05418 0.00171
0.03354 0,00282
FairFRS [100%]
0,92200 0.0099
0.00079
Age
RS- FainFRR [20%]
RSS RS-Fedieec
0.87333 0.08316
0.8985 0.00144
0,90889 0.80422
0.95893 0.0475
0J87127 0.00321
0.88665 0.001 16
0J97833 0,08966
0.15483 0.00957
ML,10KK
RS Paint RS [100%]
Fedleee
0388881 0.00139
0,90292 4 0,00188
0,953335
0,93165
0.001
0.01394
0.39211 0.0000
0.50092 + 0,00199
0.11760 0.0025
0,8380 0,00300
Gender
RS-FaiFRS [20%essers]
Fedieed
0,8H224 0.00275
0.88885
0.00114
0,93532 0.00147
0.00510
0J8TU6N
0.39315- 0.000044
0.88889 D.0LEST
0
RS [100Susees]
0.90341 19.00179
0.93135-000031
039966200.002199
0079666-0000000
Table 3: Training results of 4 different algorithms on weal-wolld datasets.
Algorithms
Advanioged Group
on Disulvaniaged Group
Demographic
FedRec
1.29992 a 0.0009
1.34260 0.00050
1,26220= 0,00050
0.45860 0.00021
Age
RS-FairFRS [20%]
RS FedRoe
147941 9.00355
1.30870 0.00811
0.99014
1.40044 0.00085
0.00233
0,88700a 0.00220
1,289912 0,00122
0.47445 1 0.0031
0.20124 0.00876
MLIM
RS- FSS-Fii [100%]
50866
0.00549
Gender
RS-FairFR [20%]
RS-FedRoc
1.0121 0.00112
228888 0.00043
0.90144 a 0JW6S5
1,30001 0.00032
0.86652 a 0.00853
1.26101 a 0.00014
0.06164 a 0JJ0372
0.09518 0.00160
RS-FairFRS (100%)
144441 D.00022
1,29099 0.00999
1,23713 - 0.0069
0L08929 D.00221
0.00511
1J8331
Age
RS-FairRRS [20%]
RS-FolRec
1.12250 0.00113
1,32220 0.00450
(U98182 + 0J08661
1 0.00270
0.99973 = 0.IGESS
1.37877 0.00545
(.21 + 0J00601
0.30511 0.00568
RS FuirERS [100%)
1.38915 1 0.00087
1A3470 0.00995
1.3800L 2 0.00221
0.28823 0.00221
MI. 10KK
FouReee
1,323112 0.00229
1.37560 0.00899
1,31004 0.00022
0,10119 D.00233
RS-FotRee
1,329914 D.00654
369655
1.30809
0,11218
RS-Fair (20%)
1.01877
0.00190
RS. SSirFas (1004)
1,39592 0.00227
1,29280 0.00779
1.12118 = 0.00911
0 0.00901
Table 4: Testing Results of 4 different algorithms on real-world datasets
amount, we can acquire much better accuracy and demographic fairness too. Further, our results emphasize an important and interesting reasoning improved accuracy as RS-FAIRFRS/202 not only reduces the loss on advantaged group but also on the disadvantaged group. Our model is able to achieve this due to the uniqueness of the metric lap which when added to optimization function of MF, reduces loss as well as the difference between the loss on the various attributes over each stochastic gradient descent step.
17

---

Under review as a conference paper at ICLR 2023
Algeniltes
Pickac
Feeflee
0.20
(S-/unht5220% user 35% fanaal
wartinge ssess]
Ro rartrazeer Loors 23% dens)
Dentogigny SaniiL
RC RC-rerrddgas csers 25% herrs rear parringtens
01400
0.14
0.12
0.30
0.52
0.64
0.59
3:88
0.90
0.52
0.04
0.06
0.55
2.50
(a) MM]e[[ge]]
(b) MI.IM[Gender]
Algortthm
Algun thm
0.0625
0.13
0.19
Ri-nartiiaee uears & 55% mem
RS-remtts20% users kems))
Iis 200 50% iamm!
Iis Keeriinpttes snevn)
00015
200200
0.11
0.725
0once
0.22
00015
0.09
0.823
0.000
0.333
5.000
0.393
2.000
C.000
0.892
0.00
0.00)
6962 0.64
HM5E
(c) Agee
(d) MLI00k[(eederr
Figure 7: Fairness vs Accuracy plots
A.6 ADDITIONAL EXPERIMENTS
This section introduces some additional findings which validate the ability of our model to improve fairness when we further reduce the amount of data on the server. Initial experiments use entire rating data from 20% users. We use the data of 20% users which are enough to represent entire local population and belong to same platform. This is a reasonable proportion to assume as atleast these many users who already use the online platform might agree to share their sensitive attributes with the server. We further toughen this assumption by considering only few of the previously rated items by these 20% users. This is done by keeping a certain proportion of items on the server. We consider 25% and 50% items of the selected 20% users. Figure presents the final results obtained on these additional experiments. We plot Demographic bias vs RMSE to represent our results using scatter plot. We show the promising results of our algorithm on the server. The consistency of results on accuracy as well as fairness can be seen across all the datasets and sensitive attributes. Though intutive, our results suggest that having entire data of 20% users can be very conducive in obtaining a fairer as well as more accurate results. However, with only 25% of the item ratings, we are still able obtain much reduced bias and better accuracy for all the four datasets. Moving further, if we increase data on the server by considering 50% of the item ratings, then we results which are slight better than the previous consideration of 25%. And, the best outcomes are encountered with all the item ratings.
when dataset is further reduced
having small amount of user's data on the server, it is evident from the results that RS- FATRFRRRSSS Swith 100% data on the server performs the worst. This happens due to the consideration of outliers which participate when all the users happen to occur on the server. Whereas, only 30% of the users from local population participate in the aggregation at server. This result emphasizes that RS-FAIRFRSnee. not consider heavy fraction of users at the server. Client fraction minimal as 20% can help in improving faimess well accuracy of the model.
Since AS-FAIRFRSSPOmon
18


Reviews:
[{"review_id": "uzgy3MU47d", "reviewer": "Reviewer_r9UQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to improve the communication efficiency of the federated recommender system by incorporating random sampling. Specifically, the paper conducts a theoretical analysis to investigate how the reduced number of sampled clients will impact the model’s accuracy. Upon the above framework, the paper further proposes a de-biased recommender system by adding the fairness constraints in the training loss.\n", "summary_of_the_review": "The paper is a combination of two mechanisms: 1) random sampling for improving efficiency, and 2) regularization term for fairness. The proposed methods relies on two impractical assumptions. Moreover, the proposed method is reuse the existing technology without limited novelty. The experimental analysis needs to be strengthened to better support its claim.", "strength_and_weaknesses": "Strength:\n\n1. The targeting problem is an important branch of federated learning. \n2. The paper is well written.\n3. The proposed method is novel.\n\n\nWeaknesses:\n1. The proposed method relies on two assumptions: 1) clustering clients in the recommendation system, and 2) availability of 20% data at server. These two assumptions are too strong that limits the value of the proposed method. \n2. It is unclear how the clients will be clustered. Because the mentioned fairness is group-wise, the clustering result is very important to decide which client will contribute to the corresponding group. \n3. In Algorithm 1, there are two subfunctions, FairMF and ClientFilling,  that need to be cleary described.\n4. Some experiment results need to further analyzed. For exampmle, in Figure 3, why all curves are very unstable at the first server rounds, and the communication rounds is too few to demonstrated that the MF is converged. In Table 3, please analyse why RS-FairFRS(100%) performs worse than RS-FairFRS(20%).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ikzZJwuoim", "reviewer": "Reviewer_4W2j", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper propose a federated recommender system which guarantees fairness and communication efficiency while trying to minimize the accuracy drop.", "summary_of_the_review": "Overall this is a borderline paper. \n\nThe quality of the paper, including the motivation, the design of the protocol, the evaluation, is okay. The writing can be further improved as I pointed out in the weakness and clarity sections.\n\nThe novelty is low. Like I mentioned in the novelty section, the proposed protocol is composed of known techniques. The math for deriving sample complexity is ok but not very challenging.\n\n-----------------------------------------------------------------\nI would like to thank the authors for their answers to my question. I decide to keep the score after reading the rebuttal.", "strength_and_weaknesses": "Strength:\n1. The authors derive the first sample complexity for federated recommender, despite under strong assumptions.\n2. The authors evaluate the proposed the method on two real-world datasets and the experimental results seem promising.\n\nWeakness:\n1. Some of the assumptions in the paper are not validated. For example, in the first paragraph of 4.1, the authors make a pretty strong assumption that the distribution of the gradients are a mixture distribution by several homogeneous distributions. I would like to see this validated on a real-world dataset.\nAnother assumption worth validating is \": We assume the availability of data of very few (20%) clients Dserver at the server for evaluating the fairness loss.\" 20% is a non-negligible percentage. Could the author give a practical scenario where such a big portion of users' data are available?\n2. Algorithm 1 is too sketchy. It is understandable if the reader fully understand the context but as a pseudocode it is not self-contained.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "erjIdmuhbiV", "reviewer": "Reviewer_qZGd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a 3-part algorithm for an efficient and fair federated recommender system that preserves privacy. They promote privacy and efficiency by randomly sampling item gradients from only a fraction of clients. The authors present a theorem to give bounds on how the sampling rate affects accuracy. They then develop a global fair model by only using sensitive information about a client's group from a fraction of the population. The global model is then used to regularize item representations in local models to maintain fairness without exposing further sensitive information. The authors show this leads to increased model accuracy, reduced bias, and reduced communication on MovieLens datasets.", "summary_of_the_review": "I am marginally inclined to accept this paper. The authors address an important issue with an intuitive and well-explained algorithm. They demonstrate their technique on a real-world dataset and show improvements in efficiency, fairness, and accuracy. However, their solution still manages to violate privacy for 20% of the population while providing only incomplete fairness for the remaining users. Also the novlety of their technique is somewhat modest. The authors should use the feedback from reviews to strengthen the final version of the paper.", "strength_and_weaknesses": "Strengths:\n1. Maintaining fairness while protecting privacy is a challenging problem, and this paper shows good progress on a real-world dataset toward achieving this aim.\n2. Multi-part algorithm is intuitive and well presented.\n3. Proof of affect of sampling rate on federated accuracy fills a gap in existing literature.\n\nWeaknesses:\n1. The problem of maintaining fairness and privacy is incompletely solved as their solution requires a fraction (20%) of user's to sacrifice privacy. The remaining 80% of users only enjoy partial fairness as they are only regularized by a fair model without theoretical guarantees. The authors should explain how realistically they would violate 20% of users' privacy. Perhaps this fraction is comparable to the number of users who opt out / do not opt in to privacy permissions, though this group may not be a representative sample of users overall.\n2. The proof of the error bound when sampling clients is unsurprising and seems somewhat obvious. This section can perhaps be moved to an appendix. Furthermore, there is an assumption that users are uniformly distributed among clusters, but in general in fairness, groups tend to be of unequal size.\n3. Evaluation is performed on two different sized MovieLens datasets, so the paper is closer to validating on just a single problem domain. The authors should consider other recommender system benchmark datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-oSdOWdmvNK", "reviewer": "Reviewer_uaXN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors improve a recent federated recommendation method for rating prediction with explicit feedback, i.e., FedRec [Lin et al., 2021], by reducing the communication cost and improving the fairness.", "summary_of_the_review": "The proposed techniques are indeed novel for the specific problem, i.e., federated recommendation with explicit feedback, and are effective as shown by the empirical studies. However, the technical contribution is not very significant since the authors only focus on a very specific problem among various more important recommendation problems, e.g., matrix factorization for recommendation with implicit feedback. ", "strength_and_weaknesses": "Strength:\n1 The authors derive some complexity bound in client sampling for reducing the communication cost.\n2 The authors propose a dual-fair vector update technique for improving the fairness.\n\nWeakness:\n1 The authors focus on a very specific problem, i.e. rating prediction with explicit feedback, and a specific type of method, i.e., matrix factorization.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject