# FedRec+: Enhancing Privacy and Addressing Heterogeneity in Federated
Recommendation Systems

Lin Wang, Zhichao Wang, Xi Leng, Xiaoying Tang The authors are with the School
of Science and Engineering, The Chinese University of Hong Kong (Shenzhen),
Shenzhen 518172, China (email: linwang1,zhichaowang<EMAIL_ADDRESS>tangxiaoying@cuhk.edu.cn).

###### Abstract

Preserving privacy and reducing communication costs for edge users pose
significant challenges in recommendation systems. Although federated learning
has proven effective in protecting privacy by avoiding data exchange between
clients and servers, it has been shown that the server can infer user ratings
based on updated non-zero gradients obtained from two consecutive rounds of
user-uploaded gradients. Moreover, federated recommendation systems (FRS) face
the challenge of heterogeneity, leading to decreased recommendation
performance. In this paper, we propose FedRec+, an ensemble framework for FRS
that enhances privacy while addressing the heterogeneity challenge. FedRec+
employs optimal subset selection based on feature similarity to generate near-
optimal virtual ratings for pseudo items, utilizing only the user’s local
information. This approach reduces noise without incurring additional
communication costs. Furthermore, we utilize the Wasserstein distance to
estimate the heterogeneity and contribution of each client, and derive optimal
aggregation weights by solving a defined optimization problem. Experimental
results demonstrate the state-of-the-art performance of FedRec+ across various
reference datasets.

##  I Introduction

Recommender systems have experienced significant advancements in recent years,
enabling personalized recommendations for users [28]. However, traditional
centralized recommender systems raise concerns about privacy leakage and data
integration limitations, as they rely on a central server to store user data
[21; 17]. On the other hand, federated learning (FL) is a distributed learning
scheme that ensures privacy preservation by allowing participants to
collaboratively train a machine learning model without sharing data [14]. The
combination of federated learning and recommendation systems gives rise to
federated recommendation systems (FRS), offering a promising solution for
privacy-preserving recommendations [22].

FRS addresses privacy and data security concerns by decentralizing the
recommendation process. User data remains localized on individual devices or
servers, and models are trained locally without sharing data. This
decentralized approach enhances user privacy and fosters trust. Various
approaches, such as federated matrix factorization [1; 12], federated
collaborative filtering [4; 5], and federated deep learning [15], distribute
the training process across each local parity and aggregate gradients on a
central server.

However, privacy preservation remains a major challenge in FRS. Although data
decentralization reduces privacy risks compared to conventional data-center
training, transmitted gradients between parties can still leak user privacy
[26]. To address this, various privacy protection mechanisms, including pseudo
items [10], homomorphic encryption [2; 11], secret sharing [11], and
differential privacy [4; 26], have been incorporated into FRS. Pseudo-item
method, in particular, has gained attention due to its low computation and
communication costs. By uploading gradients of both interacted and randomly
sampled unrated items, Pseudo items prevent the server from inferring user
interactions, as shown in Figure 2. However, existing pseudo-item methods
suffer from limitations such as introducing significant noise or imposing high
communication burdens [10; 9].

Another challenge in FRS is the heterogeneity across local datasets and
models, which complicates the aggregation of local recommendations into a
coherent global recommendation [6].

Therefore, in this work, we are primarily interested in addressing two
challenges in FRS: _(1) Design an effective pseudo items method that is low
noise as well as low communication cost. (2) Design an aggregation algorithm
to address the heterogeneity challenge in FRS._ To effectively address these
challenges, we propose an innovative framework called FedRec+, which includes
an improved pseudo items method that uses feature similarity to select a
subset for virtual rate assignment and an optimal aggregation strategy based
on the Wasserstein Distance, as illustrated in Figure 1. FedRec+ effectively
preserves client privacy with low computation and communication costs and
alleviates the heterogeneity problem in FRS. FedRec+ guarantees convergence
with a controllable noise term.

Figure 1: Framework of FedRec+. FedRec+ consists of a privacy-preserving
component and a dynamic aggregation component. Specifically, (1) it
incorporates an enhanced pseudo-items method to safeguard the privacy of
interacted items, and (2) it employs an optimal aggregation strategy to
address the heterogeneity challenge.

The contributions of this paper are summarized as follows:

  * •

We propose FedRec+, a privacy-enhancing FRS algorithm with explicit feedback.
FedRec+ utilizes feature similarity to generate low-noise pseudo items and
incorporates an optimal aggregation strategy derived from the Wasserstein
distance between the global and local models to address the statistical
heterogeneity problem.

  * •

We provide a convergence analysis of FedRec+, demonstrating a convergence rate
of $\mathcal{O}(\frac{1}{\sqrt{T}}+\frac{1}{T})$. This analysis explicitly
highlights the impact of the pseudo-item method and the Wasserstein Distance
based aggregation method on the convergence results.

  * •

We evaluate FedRec+’s performance using public datasets and find that it
excels in recommendation performance. Additionally, our ablation study
explores the impact of the number of pseudo items.

###  I-A Related Work

Several works have explored the use of federated learning in the context of
recommendation systems. [1] propose a federated collaborative filtering method
for recommendation systems. Other works that follow this line of research
include [4; 15; 5]. Additionally, deep learning-based FedRS models have been
proposed to leverage user data while ensuring privacy compliance [26].

#### FRS with Pseudo Items

To address privacy concerns in FRS, the use of pseudo items has been proposed.
[10] Introduce the concept of pseudo items to protect users’ interacted
information. However, the vanilla approach of randomly selecting unrated items
as pseudo items introduces significant noise. [9] Divide clients into
different groups, where one group records the gradients of unrated items
uploaded by another group, effectively reducing the noise caused by unrated
items. However, this approach requires additional communication and storage
costs between users, which can lead to privacy leakage issues [13]. [11]
Combine secret sharing and pseudo items mechanisms to provide stronger privacy
guarantees, while [26] combine pseudo items and Local Differential Privacy
(LDP) mechanisms to protect user interaction behaviors and ratings in FRS.
However, none of these methods effectively address the challenge of large
noise from pseudo items while maintaining a low communication cost. In this
paper, we propose FedRec+ that leverages each client’s own data information to
select optimal unrated items, minimizing noise without requiring communication
between users.

#### FRS with Aggregation

While aggregation algorithms for federated learning (FL) have been extensively
studied for various purposes such as convergence acceleration [24; 3],
fairness enhancement [25], and robustness improvement [19], limited research
has been conducted on aggregation algorithms specifically tailored for FRS.
[18] Propose FedFast, a federated recommendation model with improved
aggregation and update policies. However, there has been no dedicated work
addressing the heterogeneity problem in FRS from an aggregation perspective.
In this paper, we propose an aggregation algorithm for FRS that utilizes
Wasserstein Distance to constrain the objective, effectively tackling the
heterogeneity challenge.

##  II SYSTEM MODEL and ALGORITHM

In this section, we first state the problem setup (Sec II-A), and after
explaining the FedRec+ algorithm 1 (Sec II-B and Sec II-C), we present our
theoretical result along with the underlying assumptions (Sec III).

Notations: Following the commonly used notations in probabilistic matrix
factorization [7], the rating of a user $u$ to an item $i$ is calculated as
the inner product of their latent feature vectors, i.e.,
$\hat{r}_{ui}=\textbf{U}_{u}\textbf{V}_{i}^{\top}$, where
$\textbf{U}_{u}\in\mathbb{R}^{1\times d}$ and
$\textbf{V}_{i}\in\mathbb{R}^{1\times d}$ are the latent feature vectors of
user $u$ and item $i$, respectively. The ground-truth rating of item $i$ by
user $u$ is denoted as $r_{ui}$. The sets of rated and unrated items for user
$u$ are represented as $\mathcal{I}_{u}$ and $\mathcal{I}_{u}^{\prime}$,
respectively. The local and global learning rates are denoted as $\eta_{L}$
and $\eta$, respectively. $b\in[0,B]$ and $k\in[0,K]$ are local batch and
local epoch respectively. Boldface characters are used to represent vectors.

###  II-A Problem Setup

Figure 2: Illustration of pseudo-item method. To maintain privacy during
rating data gradient uploads, the gradients of rated and unrated items are
mixed to prevent privacy leaks, safeguarding sensitive information and
ensuring privacy protection.

Before presenting our approach, we provide an overview of the federated matrix
factorization (FedMF) algorithm.

In a recommender system, the goal is to fill in missing values of a rating
matrix $\boldsymbol{R}\in\mathbb{R}^{n\times m}$. Matrix factorization (MF) is
a widely used approach that decomposes the matrix into two low-rank matrices.
The rating $r_{ui}$ that user $u$ gives to item $i$ can be approximated as:

$\displaystyle\hat{r}_{ui}=\boldsymbol{U}_{u}\boldsymbol{V}_{i}^{\top},$ (1)

where $\boldsymbol{V}_{i}$ represents the latent factors of item $i$, and
$\boldsymbol{U}_{u}$ represents the latent factors of user $u$. The latent
factors are learned by minimizing a loss function that incorporates the known
ratings and regularization terms:

$\displaystyle\min_{\boldsymbol{V}_{i},\boldsymbol{U}_{u}}\frac{1}{2}\sum_{(u,i)\in\mathcal{I}_{u,i}}\left(r_{ui}-\boldsymbol{U}_{u}\boldsymbol{V}_{i}^{\top}\right)^{2}+\lambda\left(\left\|\boldsymbol{V}_{i}\right\|_{2}^{2}+\left\|\boldsymbol{U}_{u}\right\|_{2}^{2}\right)\,,$
(2)

where $\mathcal{I}_{u,i}$ represents the set of user-item pairs with known
ratings, and $\lambda$ is the regularization coefficient. Stochastic gradient
descent is utilized to update each parameter:

$\displaystyle\boldsymbol{V}_{i}\leftarrow\boldsymbol{V}_{i}-\eta_{L}\cdot\left(\lambda\cdot\boldsymbol{V}_{i}-e_{ui}\cdot\boldsymbol{U}_{u}\right)\,,$
(3)

$\displaystyle\boldsymbol{U}_{u}\leftarrow\boldsymbol{U}_{u}-\eta_{L}\cdot\left(\lambda\cdot\boldsymbol{U}_{u}-e_{ui}\cdot\boldsymbol{V}_{i}\right)\,,$
(4)

where $e_{ui}=r_{ui}-\boldsymbol{U}_{u}\boldsymbol{V}_{i}^{\top}$ is the
prediction error, and $\eta_{L}$ is the local learning rate.

The vanilla FedMF algorithm [1] extends MF to a federated setting. In FedMF,
the item latent factors
$\left\\{\boldsymbol{V}_{i}\right\\}_{i\in\mathcal{I}}$ are stored on the
central server, while each user’s latent factors $\boldsymbol{U}_{u}$ are kept
on the local party. The training process consists of the following steps,
which are repeated until the convergence of model parameters: (1) The local
party downloads item $i$’s latent factors $\boldsymbol{V}_{i}$ from the
server. (2) The local party updates the user’s latent factors
$\boldsymbol{U}_{u}$ using its private local data $\boldsymbol{r}_{u}$. (3)
The local party computes the gradients of each item’s latent factors
$\boldsymbol{g}_{ui}=\lambda\cdot\boldsymbol{V}_{i}-e_{ui}\cdot\boldsymbol{U}_{u}$
with $\boldsymbol{r}_{u}$ and the updated $\boldsymbol{U}_{u}$. (4) The local
party sends $\boldsymbol{g}_{ui}$ to the server. (5) The server aggregates the
gradients $\sum_{u\in\mathcal{U}}\boldsymbol{g}_{ui}$ and updates
$\boldsymbol{V}_{i}$.

However, the vanilla FedMF algorithm suffers from privacy leakage due to the
transmitted gradients. The server continuously receives the gradients of the
item $i$’s latent vector from user $u$ at step $t-1$ and step $t$:

$\displaystyle\boldsymbol{g}_{u,i}^{t-1}=\lambda\cdot\boldsymbol{V}_{i}^{t-1}-e_{ui}^{t-1}\cdot\boldsymbol{U}_{u}^{t-1}\,,$
(5)

$\displaystyle\boldsymbol{g}_{u,i}^{t}=\lambda\cdot\boldsymbol{V}_{i}^{t}-e_{ui}^{t}\cdot\boldsymbol{U}_{u}^{t}\,,$
(6)

where $\boldsymbol{V}_{i}^{t-1}$ and $\boldsymbol{V}_{i}^{t}$ represent the
item $i$’s latent factors at step $t-1$ and step $t$ respectively, and
$\boldsymbol{U}_{u}^{t-1}$ and $\boldsymbol{U}_{u}^{t}$ represent the user
$u$’s latent factors at step $t-1$ and step $t$ respectively. The server also
knows the update rule for the user’s latent factors:

$\displaystyle\boldsymbol{U}_{u}^{t}=\boldsymbol{U}_{u}^{t-1}+\gamma\cdot\sum_{i\in\mathcal{I}_{u}}\left(\lambda\cdot\boldsymbol{U}_{u}^{t-1}-e_{ui}^{t}\cdot\boldsymbol{V}_{i}^{t}\right)\,,$
(7)

where $\mathcal{I}_{u}$ represents the set of items that user $u$ has rated.
Combining these equations, the server can solve for the unknown variables,
revealing private raw ratings of each user [8].

To address the gradient leakage problem of vanilla FedMF, several secure FedMF
algorithms have been proposed. One such algorithm is FedRec [10], which
introduces a hybrid filling (HF) strategy to randomly sample unrated items and
mix them with rated items. The stochastic gradient descent of FedRec is as
follows:

$\displaystyle\nabla
V^{\mathrm{HF}}(u,i)=\left\\{\begin{array}[]{l}\left(U_{u}\cdot
V_{i}^{T}-r_{ui}\right)U_{u}+\lambda V_{i},y_{ui}=1,\\\ \left(U_{u}\cdot
V_{i}^{T}-r_{ui}^{\prime}\right)U_{u}+\lambda
V_{i},y_{ui}=0.\end{array}\right.$ (8)

where $r_{ui}$ and $r_{ui}^{\prime}$ are the true observed rating and the
virtual rating of user $u$ to item $i$, respectively.

While FedRec ensures privacy protection in rating prediction, the random
sampling of items in the hybrid filling strategy introduces noise to the
recommendation model, leading to potential performance impacts. This serves as
the motivation to develop a lossless version of FedRec, which is crucial for
practical deployment in real-world applications.

###  II-B Feature similarity for pseudo items

While FedRec ensures privacy protection in rating prediction, the hybrid
filling strategy, which involves randomly sampling items, introduces noise
that impacts performance. To address this, we aim to design a low-noise scheme
for assigning rates to unrated items.

Inspired by feature selection techniques utilizing feature similarity [16], we
aim to select items with characteristics most similar to the rated items for
assigning virtual rates. Feature similarity enables the exploration of hidden
relationships in the feature space among recommended items [20]. For instance,
assuming that some unrated items in the dataset share similar features with
rated items having a specific score, the virtual scores of these similar
unrated items would be close to that specific score. To reduce noise while
maintaining privacy protection, we selectively choose pseudo items that
closely align with a user’s existing ratings for hybrid filling.

To learn user and item features, we employ an encoder. For instance, let
$E_{r}=Encoder(V_{i}^{r})$ represent the feature of a rated item and
$E_{un}=Encoder(V_{i}^{un})$ represent the feature of an unrated item. We
calculate the cosine similarity between these features. Considering
$E_{r}=[x_{1},x_{2},\ldots,x_{n}]$ and $E_{un}=[y_{1},y_{2},\ldots,y_{n}]$,
the cosine similarity $\theta$ measures the angle between the two vectors and
is defined as follows:

$\displaystyle\text{Sim}(E_{r},E_{un})=\cos\theta=\frac{\sum_{i=1}^{n}(x_{i}\cdot
y_{i})}{\sqrt{\sum_{i=1}^{n}x_{i}^{2}\cdot\sum_{i=1}^{n}y_{i}^{2}}}.$ (9)

By selecting the top-k unrated items with the most similar features to the
scored items, we obtain low-noise pseudo items. These virtual rates, based on
latent relationships in the item feature space, introduce less noise compared
to randomly assigned scores or randomly averaged virtual scores.

Algorithm 1 FedRec+

1:Initialize the model parameters $\boldsymbol{V}_{i}$, $\boldsymbol{U}_{u}$,
global and local learning rate $\eta$ and $\eta_{l}$, number of training
rounds $T$.

2:Trained model $\boldsymbol{V}_{i}$ and $\boldsymbol{U}_{u}$

3:0for $t=1,\ldots,T$ do

4:-1Each client $u\in U$,in parallel

5:-2Sample top-k unrated items $\mathcal{I}_{u}^{\prime}$ based on feature
similarity (9) and assign them virtual rates.

6:-3$k=0,\cdots,K-1$

7:-4Update the user’s latent factors $\boldsymbol{U}_{u}$ using (4), average
on both rated and unrated items.

8:-5Get gradients $\boldsymbol{g}_{u,i}^{t,k}$ (6) from both the selected
unrated and rated items $i\in\mathcal{I}\cup\mathcal{I}^{\prime}$.

9:-6Local
update:$\boldsymbol{V}_{u}^{t,k+1}=\boldsymbol{V}_{i}^{t,k}-\eta_{L}\boldsymbol{g}_{u,i}^{t,k}$.

10:-7

11:-8Send
$\boldsymbol{\Delta}_{t}^{i}=\boldsymbol{V}_{i}^{t,K}-\boldsymbol{V}_{i}^{t,0}=-\eta_{L}\sum_{k=0}^{K-1}\boldsymbol{g}_{u,i}^{t,k}$
to server

12:-9

13:-10Server

14:-11Server updates $\boldsymbol{V}_{i}$ and sends to clients:

15:-12$\boldsymbol{V}_{i}^{t+1}=\boldsymbol{V}_{i}^{t}+\eta\sum_{u\in
U}p_{u}\boldsymbol{\Delta}_{t}^{i}$, where $p_{u}$ is based on (23).

16:-13

17:-14

###  II-C Wasserstein Distance for Aggregation

Figure 3: Illustration of aggregation weights under heterogeneous data. The
aggregation weight is determined inversely proportional to the Wasserstein
distance. As the distributions of the local model and global model become
closer, the aggregation weight increases accordingly.

In this section, we present the derivation of aggregation weights based on
Wasserstein distance to address the challenge of statistical heterogeneity in
FRS, as depicted in Figure 3.

Wasserstein distance [23] is a metric on probability distributions inspired by
the problem of optimal transport. It is particularly suitable for measuring
high-dimensional distributions, even in the absence of overlap. It quantifies
the dissimilarity between local models and the global model. Wasserstein
distance of two distribution $\boldsymbol{\mu}$ and $\boldsymbol{\nu}$ is
defined as:

$\displaystyle\boldsymbol{W}_{p}(\boldsymbol{\mu},\boldsymbol{\nu})=\inf_{\boldsymbol{\gamma}\in\boldsymbol{\Gamma}(\boldsymbol{\mu},\boldsymbol{\nu})}\mathbb{E}_{(\boldsymbol{x},\boldsymbol{y})\sim\gamma}\left[\|\boldsymbol{x}-\boldsymbol{y}\|_{p}\right]\,,$
(10)

which generally lacks a closed-form solution. However, if we consider the
L2-norm as the geometric metric and simplify the problem to a Gaussian
distribution, an analytic solution for the distance can be obtained:

$\displaystyle
d^{2}=\left\|\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\right\|_{2}^{2}+\operatorname{tr}\left(\left(\boldsymbol{\Sigma}_{1}^{\frac{1}{2}}-\boldsymbol{\Sigma}_{2}^{\frac{1}{2}}\right)^{2}\right)\,.$
(11)

Here, $\boldsymbol{\mu}_{1}$, $\boldsymbol{\Sigma}_{1}$ represent the mean and
variance of the first distribution, while $\boldsymbol{\mu}_{2}$,
$\boldsymbol{\Sigma}_{2}$ represent the mean and variance of the second
distribution.

Assuming that each client’s aggregation weight is denoted by $p_{u}$, the
server aggregates local models
$\boldsymbol{w}_{t+1}^{1},\cdots,\boldsymbol{w}_{t+1}^{|U|}$ to compute the
global model using the following equation:

$\displaystyle\overline{\boldsymbol{w}}=\sum_{u=1}^{m}p_{u}\boldsymbol{w}_{t+1}^{u}\,.$
(12)

where $|U|=m$ represents the number of users in FRS.

The distance between the aggregated model and the true global model can be
formalized as:

$\displaystyle
D=\boldsymbol{W}_{2}\left(p_{\overline{\boldsymbol{w}}}(\boldsymbol{w}),p_{\boldsymbol{w}_{g}}(\boldsymbol{w})\right)\,,$
(13)

where $\boldsymbol{w}_{g}$ represents the optimal model parameters based on
the global distribution, i.e., the distribution of data gathered from all
participants. We derive an upper bound for equation (13):

$\displaystyle D$
$\displaystyle=\boldsymbol{W}_{2}\left(p_{\overline{\boldsymbol{w}}}(\boldsymbol{w}),p_{\boldsymbol{w}_{g}}(\boldsymbol{w})\right)$
$\displaystyle=\inf_{\boldsymbol{\gamma}\in\boldsymbol{\Gamma}\left(p_{\overline{\boldsymbol{w}}},p_{\boldsymbol{w}_{g}}\right)}\mathbb{E}_{(\boldsymbol{x},\boldsymbol{y})\sim\gamma}\left[\|\boldsymbol{x}-\boldsymbol{y}\|_{2}\right]$
$\displaystyle\leq
m\sum_{u=1}^{m}p_{u}^{2}\inf_{\gamma_{u}\in\boldsymbol{\Gamma}\left(p_{\boldsymbol{w}_{K}^{u}},p_{\boldsymbol{w}_{g}}\right)}\mathbb{E}_{(\boldsymbol{x}_{u},\boldsymbol{y}_{u})\sim\gamma_{u}}\left[\|\boldsymbol{x}_{u}-\boldsymbol{y}_{u}\|_{2}\right]\,.$
(14)

In the above equation, we split $\|\boldsymbol{x}-\boldsymbol{y}\|_{2}$ as
$\left\|\sum_{u=1}^{m}p_{k}\left(\boldsymbol{x}_{k}-\boldsymbol{y}_{k}\right)\right\|_{2}$,
where each pair $\left(\boldsymbol{x}_{k},\boldsymbol{y}_{k}\right)$ is
supported on
$\boldsymbol{\Gamma}\left(p_{\boldsymbol{w}_{K}^{u}},p_{\boldsymbol{w}_{g}}\right)$.
The inequality relies on the Cauchy-Schwarz inequality and the independence of
$\boldsymbol{w}_{K}^{u}$. By bounding the distance, we establish an upper
bound for the gap between the aggregated model and the true global model.
Consequently, minimizing the above upper bound effectively approximates the
objective of minimizing equation (13).

######  Lemma II.1.

Let $\xi_{u,k}$ be a sample from a local dataset uniformly at random. For a
sufficiently large batch size $B$, the finite-dimensional vector
$g={g_{1},g_{2},\cdots,g_{K}}$ converges to a joint distribution approximately
according to the Central Limit Theorem, where
$g_{k}=\frac{1}{B}\sum_{b=1}^{B}\nabla_{w}F(w_{k},\xi_{k,b})$ for
$k\in\\{1,2,\cdots,K\\}$. This implies that, with mini-batch stochastic
gradient descent, the sum of all local updates converges to a Gaussian
distribution.

###### Proof.

For any constant of the local epoch $K$, we can rewrite gradient vector
$\boldsymbol{g}$ as

$\displaystyle\boldsymbol{g}=\frac{1}{B}\sum_{b=1}^{B}\left(\nabla_{\boldsymbol{w}}F\left(\boldsymbol{w}_{1},\boldsymbol{\xi}_{1,b}\right),\cdots,\nabla_{\boldsymbol{w}}F\left(\boldsymbol{w}_{K},\boldsymbol{\xi}_{K,b}\right)\right)\,,$
(15)

let
$\tilde{\boldsymbol{g}}_{b}=\left(\nabla_{\boldsymbol{w}}F\left(\boldsymbol{w}_{1},\boldsymbol{\xi}_{1,b}\right),\cdots,\nabla_{\boldsymbol{w}}F\left(\boldsymbol{w}_{K},\boldsymbol{\xi}_{K,b}\right)\right)$,
then we have:

$\displaystyle\boldsymbol{g}=\frac{1}{B}\sum_{k=1}^{B}\tilde{\boldsymbol{g}}_{b}\,.$
(16)

As long as the gradient norm is upper bounded and $K$ is finite,
$\tilde{\boldsymbol{g}}_{b}$ follows some complex distribution with bounded
covariance matrix. Since $\boldsymbol{\xi}_{k,b}$ is sampled independently
from the same distribution, $\boldsymbol{g}$ is the mean vector of
$\tilde{\boldsymbol{g}}_{1},\cdots,\tilde{\boldsymbol{g}}_{B}$, which are
independent and identically distributed (i.i.d.) random vectors. Therefore,
according to the Central Limit Theorem, $\boldsymbol{g}$ converges to
$\mathcal{N}(\boldsymbol{\mu},\boldsymbol{\Sigma})$ in distribution. ∎

Lemma II.1 implies that, with mini-batch stochastic gradient descent, the sum
of all local updates converges to a Gaussian distribution, i.e.:

$\displaystyle\overline{\boldsymbol{g}}=\boldsymbol{w}_{K}-\boldsymbol{w}_{1}=\sum_{k=1}^{K}\boldsymbol{g}_{k}=\mathbf{1}^{T}\boldsymbol{g}\,,$
(17)

where $\overline{\boldsymbol{g}}$ is a linear transformation of a joint
Gaussian vector, thus it conforms to a Gaussian distribution. As the Gaussian
distribution is determined by the mean vector and the covariance matrix, our
next goal is to estimate these variables.

Based on (17), we know that the total gradient distribution is approximated by
the sum of independent random vectors, i.e.
$\overline{\boldsymbol{g}}=\boldsymbol{w}_{K}-\boldsymbol{w}_{1}=\sum_{k=1}^{K}\eta\boldsymbol{g}_{k}=\eta_{L}\mathbf{1}^{T}\boldsymbol{g}$,
where $\eta_{L}$ is the local learning rate. Therefore, the corresponding
parameters can be estimated as
$\boldsymbol{\mu}=\eta_{L}\sum_{k=1}^{K}\mathbb{E}\left[\boldsymbol{g}_{k}\right]\doteq
K\eta_{L}\mathbb{E}\left[\boldsymbol{g}_{1}\right]$ and
$\boldsymbol{\Sigma}=\eta_{L}^{2}\sum_{k=1}^{K}\boldsymbol{\Sigma}_{k}\doteq
K\eta_{L}^{2}\boldsymbol{\Sigma}_{1}$. Here, index 1 represents a random user,
and $E[\boldsymbol{g}_{1}]$ and $\boldsymbol{\Sigma}_{1}$ represent the
average gradients and average variance of client 1. In particular, based on
the relationship between the covariance matrix, correlation matrix, and the
mean vector, we can obtain
$\Sigma_{k}={\mathbb{E}}[g_{k}g_{k}^{T}]-{\mathbb{E}}[g_{k}]{\mathbb{E}}[g_{k}^{T}]$,
where $g_{k}=\frac{1}{B}\sum_{b=1}^{B}\nabla F(x,\xi_{k,b})$.

Furthermore, implied by Lemma II.1, the global gradient distribution converges
to $\mathcal{N}(\boldsymbol{\mu}_{g},\frac{\boldsymbol{\Sigma}_{g}}{B})$.
Therefore, to minimize the distance between the aggregated model and the
global model, we can formulate an optimization problem as follows:

$\displaystyle\min_{p_{k}}$ $\displaystyle
D=\sum_{u=1}^{m}p_{u}^{2}\left(\left\|\eta\boldsymbol{\mu}_{g}-\eta_{L}K\boldsymbol{\mu}_{u}\right\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)\right)$
(18) s.t.
$\displaystyle\boldsymbol{M}=\left(\frac{\eta^{2}\boldsymbol{\Sigma}_{g}}{B}\right)^{\frac{1}{2}}-\left(\frac{K^{2}\eta_{L}^{2}\boldsymbol{\Sigma}_{u}}{B}\right)^{\frac{1}{2}},\sum_{u=1}^{m}p_{u}=1,p_{u}\geq
0\,.$

######  Proposition II.2.

The optimal server aggregation weights that minimize the distribution distance
between the aggregated model and the ideal global model, using Wasserstein
Distance, are given by:

$\displaystyle
p_{u}^{*}=\frac{\frac{1}{\|K\eta_{L}\boldsymbol{\mu}_{u}-\eta\boldsymbol{\mu}_{g}\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)}}{\sum_{u=1}^{m}\frac{1}{\|K\eta_{L}\boldsymbol{\mu}_{u}-\eta\boldsymbol{\mu}_{g}\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)}}.$
(19)

###### Proof.

It can be seen that (18) is a convex optimization problem, which we use the
Karush–Kuhn–Tucker (KKT) conditions to solve. Introducing Lagrange multipliers
$\lambda_{u}\in\mathbb{R}$ for the inequality constraints $p_{u}\geq 0$, and a
multiplier $\nu\in\mathbb{R}$ for the equality constraint $\sum_{u}p_{u}=1$,
we have

$\displaystyle\lambda_{u}\geq 0,\lambda_{u}p_{u}=0,\sum_{u\in[m]}p_{u}=1,\quad
p_{u}\geq 0,$ $\displaystyle
2\left(\left\|\eta\boldsymbol{\mu}_{g}-\eta_{L}K\boldsymbol{\mu}_{u}\right\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)\right)p_{u}-\lambda_{u}+\nu=0.$
(20)

Since $\sum_{u\in[m]}p_{u}=1$, there exists $u_{0}$ such that $p_{u_{0}}>0$.
Thus we have $\lambda_{u_{0}}=0$, which yields
$\nu=-2\left(\left\|\eta\boldsymbol{\mu}_{g}-\eta_{L}K\boldsymbol{\mu}_{u}\right\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)\right)p_{u_{0}}<0$.
Therefore, $p_{u}>0$ always holds because if $p_{u}=0$, it leads to
$2\left(\left\|\eta\boldsymbol{\mu}_{g}-\eta_{L}K\boldsymbol{\mu}_{u}\right\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)\right)p_{u}-\lambda_{u}+\nu<0$
which violates the condition in (II-C). As a result, we have
$\lambda_{u}=0,\forall u\in[m]$. Furthermore,

$\displaystyle
p_{u}=-\frac{\nu}{2\left(\left\|\eta\boldsymbol{\mu}_{g}-\eta_{L}K\boldsymbol{\mu}_{u}\right\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)\right)},\quad\forall
u\in[m].$ (21)

By plugging (21) into $\sum_{u\in[m]}p_{u}=1$, we have

$\displaystyle\nu=-\frac{2}{\sum_{u}1/\left(\left\|\eta\boldsymbol{\mu}_{g}-\eta
K\boldsymbol{\mu}_{u}\right\|^{2}+\operatorname{tr}\left(\boldsymbol{M}^{2}\right)\right)}.$
(22)

Plugging (22) back into (21) completes the proof. ∎

However, considering the increased communication traffic and computational
complexity introduced by the covariance matrix, we need to simplify the
procedure. Note that

$\displaystyle\lim_{B\rightarrow+\infty}p^{*}_{u}=\frac{\frac{1}{\|K\eta_{L}\boldsymbol{\mu}_{u}-\eta\boldsymbol{\mu}_{g}\|^{2}}}{\sum_{u}\frac{1}{\|K\eta_{L}\boldsymbol{\mu}_{u}-\eta\boldsymbol{\mu}_{g}\|^{2}}}\,.$
(23)

Hence, with a sufficiently large batch size, we can use (23) to estimate the
optimal aggregation probability. Thus, we have derived an optimal aggregation
strategy using the Wasserstein distance to address the challenge of
heterogeneity in FRS.

##  III Theoretical analysis

In this section, to ease the theoretical analysis, we redefine some notations:
the parameter of the model is $\boldsymbol{x}$ instead of $\boldsymbol{U}$ and
$\boldsymbol{V}$, and use index $i\in[1,\cdots,m],k\in[1,K],t\in[0,T]$ to
indicate user, local epoch, and communication round. The optimization
objective of FRS is formulated as follows:

$\displaystyle\min_{\boldsymbol{x}\in\mathbb{R}^{d}}f(\boldsymbol{x})={\mathbb{E}}_{i\sim\mathcal{P}}\left[F_{i}(\boldsymbol{x})\right]\,,$
(24)

where $F_{i}(\boldsymbol{x})\triangleq{\mathbb{E}}_{\xi\sim
P_{i}}[F_{i}(\boldsymbol{x},\xi)]$. Here, $\mathcal{P}$ represents the overall
data distribution of entire client distribution,
$\boldsymbol{x}\in\mathbb{R}^{d}$ is the model parameter,
$F_{i}(\boldsymbol{x})$ represents the local loss function at client $i$ and
$P_{i}$ is the underlying distribution of local dataset at client $i$. In
general, $P_{i}\neq P_{j}$ if $i\neq j$ due to data heterogeneity. However,
the loss function $F(\boldsymbol{x})$ or full gradient $\nabla
F(\boldsymbol{x})$ can not be directly computed as the exact distribution of
data is unknown in general. Hence, one often consider the following empirical
risk minimization (ERM) problem in the form of finite-sum instead:

$\displaystyle\min_{\boldsymbol{x}\in\mathbb{R}^{d}}f(\boldsymbol{x})=\sum_{i\in
S_{t}}p_{i}F_{i}(\boldsymbol{x})\,,$ (25)

where $F_{i}(\boldsymbol{x})=\frac{1}{|D_{i}|}\sum_{\xi\in
D_{i}}F_{i}(\boldsymbol{x},\xi)$. Here, $S_{t}$ is the selected client set in
each round and $p_{i}$ is the aggregation weights of clients.

To ease the theoretical analysis of our work, we use the following widely used
assumptions:

######  Assumption 1 (L-Smooth).

There exists a constant $L>0$, such that $\left\lVert\nabla F_{i}(x)-\nabla
F_{i}(y)\right\rVert\leq L\left\lVert x-y\right\rVert,\forall
x,y\in\mathbb{R}^{d}$, and $i={1,2,\ldots,m}$.

######  Assumption 2 (Unbiased Local Gradient Estimator and Local Variance).

Let $\xi_{t}^{i}$ be a random local data sample in the round $t$ at client
$i$: ${\mathbb{E}}\left[\nabla
F_{i}(\boldsymbol{x}_{t},\xi_{t}^{i})\right]=\nabla
F_{i}(\boldsymbol{x}_{t}),\forall i\in[m]$. There exists a constant bound
$\sigma_{L}>0$, satisfying ${\mathbb{E}}\left[\left\lVert\nabla
F_{i}(\boldsymbol{x}_{t},\xi_{t}^{i})-\nabla
F_{i}(\boldsymbol{x}_{t})\right\rVert^{2}\right]\leq\sigma_{L}^{2}$.

######  Assumption 3 (Bound Gradient Dissimilarity).

For any set of weights $\left\\{w_{i}\geq 0\right\\}_{i=1}^{m}$ with
$\sum_{i=1}^{m}w_{i}=1$, there exist constants $\sigma_{G}^{2}\geq 0$ and
$A\geq 0$ such that $\sum_{i=1}^{m}w_{i}\left\|\nabla
F_{i}(\boldsymbol{x})\right\|^{2}\leq(A^{2}+1)\left\|\sum_{i=1}^{m}w_{i}\nabla
F_{i}(\boldsymbol{x})\right\|^{2}+\sigma_{G}^{2}$.

The above three assumptions are commonly used in both non-convex optimization
and FL literature, see e.g. [6; 27]. For Assumption 3, if all local loss
functions are identical, then we have $A=0$ and $\sigma_{G}=0$.

Since there are both rated items and pseudo items, $\nabla
F_{i}(\boldsymbol{x}_{t,k}^{i})=\frac{1}{B}\sum_{b\in B}\nabla
F(\boldsymbol{x}_{t,k}^{i},\xi_{b})=\alpha\frac{1}{B^{r}}\sum_{b^{r}\in
B^{r}}\nabla
F(\boldsymbol{x}_{t,k}^{i},\xi_{b^{r}})+(1-\alpha)\frac{1}{B^{u}}\sum_{b^{u}\in
B^{u}}\nabla
F(\boldsymbol{x}_{t,k}^{i},\xi_{b^{u}})=\alpha\nabla\overline{F}(\boldsymbol{x}_{t,k}^{i})+(1-\alpha)\tilde{F}(\boldsymbol{x}_{t,k}^{i})$,
where $B^{r}$ and $B^{u}$ represent the rated items and unrated items,
respectively. $B=B^{r}\cup B^{u}$ represents total items.
$\alpha=\frac{B^{r}}{B}$ is the relative ratio of rated items in all user’s
items.

######  Assumption 4 (Gradient Difference Bound).

In each round, we assume that the gradient of the pseudo item is denoted as
$\nabla\tilde{F}(\boldsymbol{x}_{t,k}^{i})$, while its true gradient is
denoted as $\nabla\overline{F}(\boldsymbol{x}_{t,k}^{i})$. The gap of the
approximation satisfies the following conditions:
${\mathbb{E}}\|\nabla\overline{F}(\boldsymbol{x}_{t,k}^{i})-\nabla\tilde{F}(\boldsymbol{x}_{t,k}^{i})\|^{2}\leq\rho^{2}$,
$\forall i,t,k$.

######  Theorem III.1 (Convergence rate).

Under Assumption 1\- 4, and let constant local and global learning rate
$\eta_{L}$ and $\eta$ be chosen such that
$\eta_{L}<min\left(1/(8LK),C\right)$, where $C$ is obtained from the condition
that
$\frac{1}{2}-10L^{2}\frac{1}{m}\sum_{i-1}^{m}K^{2}\eta_{L}^{2}(A^{2}+1)(\chi_{p\|w}^{2}A^{2}+1)\textgreater
C\textgreater 0$, and $\eta\leq 1/(\eta_{L}L)$. The expected gradient norm of
FedRec+ is bounded as follows:

$\displaystyle\mathop{min}\limits_{t\in[T]}{\mathbb{E}}\|\nabla
f(\boldsymbol{x}_{t})\|^{2}\leq
2\left[\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}A^{2}+1\right](\frac{f_{0}-f_{*}}{c\eta\eta_{L}KT}+\Phi)$
$\displaystyle+2\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\sigma_{G}^{2}\,,$
(26)

where $f_{0}=f(x_{0})$, $f_{*}=f(x_{*})$, and

$\displaystyle\Phi=\frac{1}{c}\left[\frac{5\eta_{L}^{2}KL^{2}}{2}(\sigma_{L}^{2}+6K\sigma_{G}^{2}+6K(1-\alpha)^{2}\rho^{2})\right.$
$\displaystyle\left.+\frac{\eta\eta_{L}L}{2}(\sigma_{L}^{2}+(1-\alpha)^{2}\rho^{2})+20L^{2}K^{2}(A^{2}+1)\eta_{L}^{2}\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\sigma_{G}^{2}\right]\,.$

where
$\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}=\sum_{i=1}^{m}\left(w_{i}-p_{i}\right)^{2}/p_{i}$
represents the chi-square divergence between vectors
$\boldsymbol{w}=\left[\frac{1}{m},\ldots,\frac{1}{m}\right]$ and
$\boldsymbol{p}=\left[p_{1},\ldots,p_{m}\right]$. Observe that when all
clients have uniform data distribution, we have
$\boldsymbol{p}=\boldsymbol{w}$ such that $\chi^{2}=0$.

######  Corollary III.2.

Suppose $\eta_{L}$ and $\eta$ are
$\eta_{L}=\mathcal{O}\left(\frac{1}{\sqrt{T}KL}\right)$ and
$\eta=\mathcal{O}\left(\sqrt{Km}\right)$ such that the conditions mentioned
above are satisfied. Then for sufficiently large T, the iterates of FedRec+
satisfy:

$\displaystyle\min_{t\in[T]}\left\|\nabla
f\left(\boldsymbol{x}_{t}\right)\right\|^{2}\leq\mathcal{O}\left(\frac{(f^{0}-f^{*})}{\sqrt{mKT}}\right)$
$\displaystyle+\mathcal{O}\left(\frac{\sqrt{m}(\sigma_{L}^{2}+(1-\alpha)^{2}\rho^{2})}{2\sqrt{KT}}\right)+\mathcal{O}\left(\frac{20(A^{2}+1)\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\sigma_{G}^{2}}{T}\right)$
$\displaystyle+\mathcal{O}\left(\frac{5(\sigma_{L}^{2}+6K\sigma_{G}^{2}+6K(1-\alpha)^{2}\rho^{2})}{2KT}\right)+2\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\sigma_{G}^{2}\,.$
(27)

######  Remark III.3 (Effects of pseudo items and reweight aggregation).

The noise error introduced by pseudo items is denoted by $\rho$. It is
observed that a larger value of $1-\alpha$ corresponds to a larger noise,
implying that using more pseudo items leads to increased noise. The non-
vanishing term $\chi_{\boldsymbol{w}|\boldsymbol{p}}^{2}\sigma_{G}^{2}$
represents the aggregation error arising from an unbiased aggregation
distribution. In other words, there is always an error term present in the
convergence rate as long as the aggregation algorithm exhibits bias.

_Proof Sketch:_ Using the following two lemmas, we can finish the proof. In
particular, based on the Lemma III.4, we bound the gradient norm of $\nabla
f(\boldsymbol{x}_{t})$ by the norm of $\nabla\tilde{f}(\boldsymbol{x}_{t})$,
and then utilize Lemma III.5 we derive the upper bound for
$\nabla\tilde{f}(\boldsymbol{x}_{t})$.

######  Lemma III.4 (Gradient distance between pseudo items and rated items.).

For any model parameter $\boldsymbol{x}$, the difference between the gradients
of $f(\boldsymbol{x})$ and $\tilde{f}(\boldsymbol{x})$ can be bounded as
follows:

$\displaystyle\|\nabla
f(\boldsymbol{x})-\nabla\tilde{f}(\boldsymbol{x})\|^{2}\leq\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\left[A^{2}\|\nabla\tilde{f}(\boldsymbol{x})\|^{2}+\kappa^{2}\right]\,,$
(28)

$f(x)$ is the true objective with $f(x)=\sum_{i=1}^{m}w_{i}f_{i}(x)$ where
$\boldsymbol{w}$ is usually average of all clients, i.e.,
$\boldsymbol{w}=\frac{1}{m}$. $\tilde{f}(x)=\sum_{i=1}^{m}p_{i}f_{i}(x)$ is
the surrogate objective with the reweight aggregation probability
$\boldsymbol{p}$.

###### Proof.

$\displaystyle\nabla
f(\boldsymbol{x})-\nabla\tilde{f}(\boldsymbol{x})=\sum_{i=1}^{m}\frac{w_{i}-p_{i}}{\sqrt{p}_{i}}\cdot\sqrt{p}_{i}\left(\nabla
f_{i}(\boldsymbol{x})-\nabla\tilde{f}(\boldsymbol{x})\right)\,.$ (29)

Applying Cauchy-Schwarz inequality, it follows that

$\displaystyle\|\nabla
f(\boldsymbol{x})-\nabla\tilde{f}(\boldsymbol{x})\|^{2}$ (30)
$\displaystyle\leq\left[\sum_{i=1}^{m}\frac{\left(w_{i}-p_{i}\right)^{2}}{p_{i}}\right]\left[\sum_{i=1}^{m}p_{i}\left\|\nabla
F_{i}(x)-\nabla\tilde{f}(\boldsymbol{x})\right\|^{2}\right]$
$\displaystyle\leq\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\left[A^{2}\|\nabla\tilde{f}(\boldsymbol{x})\|^{2}+\sigma_{G}^{2}\right]\,,$

where the last inequality uses Assumption 3. Note that

$\displaystyle\|\nabla f(\boldsymbol{x})\|^{2}\leq 2\|\nabla
f(\boldsymbol{x})-\nabla\tilde{f}(\boldsymbol{x})\|^{2}+2\|\nabla\tilde{f}(\boldsymbol{x})\|^{2}$
(31) $\displaystyle\leq
2\left[\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}A^{2}+1\right]\|\nabla\tilde{f}(\boldsymbol{x})\|^{2}+2\chi_{\boldsymbol{p}\|\boldsymbol{w}^{2}}^{2}\sigma_{G}^{2}\,.$

As a result, we obtain:

$\displaystyle\min_{t\in[T]}$ $\displaystyle\left\|\nabla
f\left(\boldsymbol{x}_{t}\right)\right\|^{2}\leq\frac{1}{\tau}\sum_{t=0}^{T-1}\left\|\nabla
f\left(\boldsymbol{x}_{t}\right)\right\|^{2}$ $\displaystyle\leq
2\left[\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}A^{2}+1\right]\frac{1}{\tau}\sum_{t=0}^{T-1}\left\|\nabla\tilde{f}\left(\boldsymbol{x}_{t}\right)\right\|^{2}+2\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\sigma_{G}^{2}$
$\displaystyle\leq
2\left[\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}A^{2}+1\right]\epsilon_{\mathrm{opt}}+2\chi_{\boldsymbol{w}\|\boldsymbol{p}}^{2}\sigma_{G}^{2}\,,$
(32)

where $\epsilon_{\mathrm{opt}}$ denotes the optimization error. ∎

######  Lemma III.5 (Local updates bound.).

For any step-size satisfying $\eta_{L}\leq\frac{1}{8LK}$, we can have the
following results:

$\displaystyle{\mathbb{E}}\|x_{t,k}^{i}-x_{t}\|^{2}\leq
5K\left(\eta_{L}^{2}\sigma_{L}^{2}+6K\eta_{L}^{2}(1-\alpha)^{2}\rho^{2}+6K\eta_{L}^{2}\sigma_{G}^{2}\right)$
$\displaystyle+30K^{2}(A^{2}+1)\eta_{L}^{2}\|\nabla f(x_{t})\|^{2}\,.$

###### Proof.

$\displaystyle{\mathbb{E}}_{t}\|x_{t,k}^{i}-x_{t}\|^{2}$
$\displaystyle{\mathbb{E}}_{t}\|x_{t,k-1}^{i}-x_{t}-\eta_{L}((1-\alpha)\nabla
F(x_{t,k-1}^{i};\xi_{b^{u}})$ $\displaystyle+\alpha\nabla
F(x_{t,k-1}^{i};\xi_{b^{r}})-(1-\alpha)\nabla\overline{F}_{i}(x_{t,k-1}^{i})-\alpha\nabla\overline{F}_{i}(x_{t,k-1}^{i})$
$\displaystyle+(1-\alpha)\nabla\tilde{F}_{i}(x_{t,k-1}^{i})-(1-\alpha)\nabla\tilde{F}_{i}(x_{t,k-1}^{i})+\nabla
F_{i}(x_{t,k-1}^{i})$ $\displaystyle-\nabla F_{i}(x_{t})+\nabla
F_{i}(x_{t}))\|^{2}$
$\displaystyle\leq(1+\frac{1}{2K-1}){\mathbb{E}}_{t}\|x_{t,k-1}^{i}-x_{t}\|^{2}$
$\displaystyle+(1-\alpha)^{2}\eta_{L}^{2}{\mathbb{E}}\|\nabla
F(x_{t,k-1}^{i};\xi_{b^{u}})-\nabla\tilde{F}_{i}(x_{t,k-1}^{i})\|^{2}$
$\displaystyle+\alpha^{2}\eta_{L}^{2}{\mathbb{E}}\|\nabla
F(x_{t,k-1}^{i};\xi_{b^{r}})-\nabla\overline{F}_{i}(x_{t,k-1}^{i})\|^{2}$
$\displaystyle+6K(1-\alpha)^{2}\eta_{L}^{2}{\mathbb{E}}\|\nabla\tilde{F}_{i}(x_{t,k-1}^{i})-\overline{F}_{i}(x_{t,k-1}^{i})\|^{2}$
$\displaystyle+6K\eta_{L}^{2}{\mathbb{E}}\|\nabla F_{i}(x_{t,k-1}^{i})-\nabla
F_{i}(x_{t})\|^{2}+6K\eta_{L}^{2}{\mathbb{E}}\|\nabla F_{i}(x_{t})\|^{2}$
$\displaystyle\leq(1+\frac{1}{K-1}){\mathbb{E}}_{t}\|x_{t,k-1}^{i}-x_{t}\|^{2}+\eta_{L}^{2}\sigma_{L}^{2}+6K\eta_{L}^{2}(1-\alpha)^{2}\rho^{2}$
$\displaystyle+6K\eta_{L}^{2}\sigma_{G}^{2}+6K\eta_{L}^{2}(A^{2}+1)\|\nabla
f(x_{t})\|^{2}\,.$ (33)

Unrolling the recursion, we obtain:

$\displaystyle{\mathbb{E}}_{t}\|x_{t,k}^{i}-x_{t}\|^{2}\leq\sum_{p=0}^{k-1}(1+\frac{1}{K-1})^{p}\left[\eta_{L}^{2}\sigma_{L}^{2}+6K\eta_{L}^{2}(1-\alpha)^{2}\rho^{2}\right.$
$\displaystyle\left.+6K\eta_{L}^{2}\sigma_{G}^{2}+6K(A^{2}+1)\|\eta_{L}\nabla
f(x_{t})\|^{2}\right]$
$\displaystyle\leq(K-1)\left[(1+\frac{1}{K-1})^{K}-1\right]\left[\eta_{L}^{2}\sigma_{L}^{2}\right.$
$\displaystyle\left.+6K\eta_{L}^{2}(1-\alpha)^{2}\rho^{2}+6K\eta_{L}^{2}\sigma_{G}^{2}+6K(A^{2}+1)\|\eta_{L}\nabla
f(x_{t})\|^{2}\right]$ $\displaystyle\leq
5K(\eta_{L}^{2}\sigma_{L}^{2}+6K\eta_{L}^{2}(1-\alpha)^{2}\rho^{2}+6K\eta_{L}^{2}\sigma_{G}^{2})$
$\displaystyle+30K^{2}(A^{2}+1)\eta_{L}^{2}\|\nabla f(x_{t})\|^{2}\,.$ (34)

∎

##  IV Numerical results

In this section, we present simulation results to validate the performance of
the FedRec+ and compare it with the vanilla pseudo method (FedRec). We use two
widely used benchmark datasets for recommendation including ML-100K and ML-1M.
ML100K contains 100, 000 ratings of 1, 682 movies from 943 users; ML1M
contains 1, 000, 209 ratings of 3, 952 movies from 6, 040 users, while both
have rating levels of $[1,2,\cdots,5]$. We process each dataset follows the
setting in [9]: (i) randomly dividing the dataset into five equal parts, (ii)
using four parts for training and one part for testing, (iii) repeating this
process four times to obtain five distinct sets of training and test data. Our
experimental analysis is based on these five datasets, and we report the
average performance across all five.

In our experiment, we use the PMF [17] as the backbone model and we use three
commonly used evaluation metrics, i.e., MAE, RMSE, and NMSE, for performance
evaluation.

Table I demonstrates the superior performance of FedRec+ over FedRec across
all three recommendation metrics. This indicates our proposed algorithm is
effective.

TABLE I: Recommendation performance of FedRec and FedRec+ in ML1M and ML100K.

Data | Algorithm | MAE | RMSE | NMSE
---|---|---|---|---
ML-1M | FedRec | 0.8962  ±0.0002 | 1.1178  ±0.0003 | 0.0893  ±0.0005
FedRec+ | 0.8929  ±0.0002 | 1.1014  ±0.0003 | 0.0879  ±0.0009
ML-100K | FedRec | 1.0120  ±0.0002 | 1.3179  ±0.0021 | 0.1236  ±0.0009
FedRec+ | 0.9109  ±0.0021 | 1.1713  ±0.0022 | 0.1006  ±0.0008

Figure 4: Performance of FedRec+ under different numbers of pseudo items.

Figure 4 illustrates the impact of varying numbers of pseudo items on ML1M. It
indicates that higher numbers of pseudo items result in increased noise and
consequently worse performance, aligning with our theoretical analysis.

##  V Conclusion and future works

This paper focuses on the problem of privacy-aware federated recommendation
with explicit feedback. We propose FedRec+, a privacy-preserving framework
that addresses this issue. FedRec+ utilizes feature similarity to generate
low-noise pseudo items without client communication. Furthermore, we employ
the Wasserstein Distance to optimize the aggregation probability, which helps
handle the heterogeneity of the federated recommendation system. Convergence
analysis is conducted to demonstrate the impact of pseudo items and
aggregation probability. FedRec+ is a versatile solution that can be combined
with other privacy-aware recommendation methods, such as differential privacy
[4]. Our experimental results, based on public datasets, validate the
effectiveness of FedRec+.

##  VI ACKNOWLEDGEMENTS

This work is supported in part by the National Natural Science Foundation of
China under Grant No. 62001412, in part by the funding from Shenzhen Institute
of Artificial Intelligence and Robotics for Society, in part by the Shenzhen
Key Lab of Crowd Intelligence Empowered Low-Carbon Energy Network (Grant No.
ZDSYS20220606100601002), and in part by the Guangdong Provincial Key
Laboratory of Future Networks of Intelligence (Grant No. 2022B1212010001).

## References

  * [1] 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.  arXiv preprint arXiv:1901.09888, 2019.
  * [2] Di Chai, Leye Wang, Kai Chen, and Qiang Yang.  Secure federated matrix factorization.  IEEE Intelligent Systems, 36(5):11–20, 2020.
  * [3] Shengbo Chen, Cong Shen, Lanxue Zhang, and Yuanmin Tang.  Dynamic aggregation for heterogeneous quantization in federated learning.  IEEE Transactions on Wireless Communications, 20(10):6804–6819, 2021.
  * [4] Koustabh Dolui, Illapha Cuba Gyllensten, Dietwig Lowet, Sam Michiels, Hans Hallez, and Danny Hughes.  Towards privacy-preserving mobile applications with federated learning: The case of matrix factorization (poster).  In Proceedings of the 17th Annual International Conference on Mobile Systems, Applications, and Services, pages 624–625, 2019.
  * [5] Hongsheng Hu, Gillian Dobbie, Zoran Salcic, Meng Liu, Jianbing Zhang, and Xuyun Zhang.  A locality sensitive hashing based approach for federated recommender system.  In 2020 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID), pages 836–842. IEEE, 2020.
  * [6] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  Scaffold: Stochastic controlled averaging for federated learning.  In International Conference on Machine Learning, pages 5132–5143. PMLR, 2020.
  * [7] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  Computer, 42(8):30–37, 2009.
  * [8] Daniel Lazard.  Thirty years of polynomial system solving, and now?  Journal of symbolic computation, 44(3):222–231, 2009.
  * [9] Feng Liang, Weike Pan, and Zhong Ming.  Fedrec++: Lossless federated recommendation with explicit feedback.  In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 4224–4231, 2021.
  * [10] Guanyu Lin, Feng Liang, Weike Pan, and Zhong Ming.  Fedrec: Federated recommendation with explicit feedback.  IEEE Intelligent Systems, 36(5):21–30, 2020.
  * [11] Zhaohao Lin, Weike Pan, and Zhong Ming.  Fr-fmss: Federated recommendation via fake marks and secret sharing.  In Proceedings of the 15th ACM Conference on Recommender Systems, pages 668–673, 2021.
  * [12] Shuchang Liu, Shuyuan Xu, Wenhui Yu, Zuohui Fu, Yongfeng Zhang, and Amelie Marian.  Fedct: Federated collaborative transfer for recommendation.  In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pages 716–725, 2021.
  * [13] Xiaoyuan Liu, Hongwei Li, Guowen Xu, Zongqi Chen, Xiaoming Huang, and Rongxing Lu.  Privacy-enhanced federated learning against poisoning adversaries.  IEEE Transactions on Information Forensics and Security, 16:4574–4588, 2021.
  * [14] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [15] Lorenzo Minto, Moritz Haller, Benjamin Livshits, and Hamed Haddadi.  Stronger privacy for federated collaborative filtering with implicit feedback.  In Fifteenth ACM Conference on Recommender Systems, pages 342–350, 2021.
  * [16] Pabitra Mitra, CA Murthy, and Sankar K. Pal.  Unsupervised feature selection using feature similarity.  IEEE transactions on pattern analysis and machine intelligence, 24(3):301–312, 2002.
  * [17] Andriy Mnih and Russ R Salakhutdinov.  Probabilistic matrix factorization.  Advances in neural information processing systems, 20, 2007.
  * [18] Khalil Muhammad, Qinqin Wang, Diarmuid 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 on Knowledge Discovery & Data Mining, pages 1234–1242, 2020.
  * [19] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui.  Robust aggregation for federated learning.  IEEE Transactions on Signal Processing, 70:1142–1154, 2022.
  * [20] Wenbin Qian, Yinsong Xiong, Jun Yang, and Wenhao Shu.  Feature selection for label distribution learning via feature similarity and label correlation.  Information Sciences, 582:38–59, 2022.
  * [21] Steffen Rendle.  Factorization machines with libfm.  ACM Transactions on Intelligent Systems and Technology (TIST), 3(3):1–22, 2012.
  * [22] Zehua Sun, Yonghui Xu, Yong Liu, Wei He, Yali Jiang, Fangzhao Wu, and Lizhen Cui.  A survey on federated recommendation systems.  arXiv preprint arXiv:2301.00767, 2022.
  * [23] Cédric Villani et al.  Optimal transport: old and new, volume 338.  Springer, 2009.
  * [24] Lin Wang, Yongxin Guo, Tao Lin, and Xiaoying Tang.  Delta: Diverse client sampling for fasting federated learning.  2022\.
  * [25] Lin Wang, Zhichao Wang, and Xiaoying Tang.  Fedeba+: Towards fair and effective federated learning via entropy-based model.  arXiv preprint arXiv:2301.12407, 2023.
  * [26] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie.  Fedgnn: Federated graph neural network for privacy-preserving recommendation.  arXiv preprint arXiv:2102.04925, 2021.
  * [27] Haibo Yang, Minghong Fang, and Jia Liu.  Achieving linear speedup with partial worker participation in non-iid federated learning.  arXiv preprint arXiv:2101.11203, 2021.
  * [28] Liu Yang, Ben Tan, Vincent W Zheng, Kai Chen, and Qiang Yang.  Federated recommendation systems.  Federated Learning: Privacy and Incentive, pages 225–239, 2020.