BGTplanner: Maximizing Training Accuracy for Differentially Private Federated Recommenders via Strategic Privacy Budget Allocation

Training recommender models often relies on sensitive data, such as users’ historical interactions with items. To protect origin data from leaking to malicious attackers, FR, a distributed learning framework [18] has been widely adopted for training recommender models [3, 6]. Nevertheless, revealing training parameters rather than raw data has proven inadequate for ensuring privacy protection [8, 9, 10], leading to the development of DPFR. To safeguard data privacy, DPFRs incorporate DP mechanisms [11], which enhance privacy by injecting noises to distort exposed training parameters. This approach has emerged as a key consideration in privacy-preserving recommenders [19], despite that its adoption in practice is still hindered by lowered recommendation accuracy.

The privacy budget is a non-recoverable resource, which must be split into multiple small portions to restrict the privacy loss per training round [14, 15]. It has been reported in [19] that DP noises generated by a small privacy budget per round can severely impair model accuracy. Existing studies have initially attempted to address the influence of noise on DPFR. For example, [20] explored dynamic techniques for adjusting the learning rate, batch size, noise magnitude, and gradient clipping to improve DPFR accuracy. Yet, this work does not account for dynamic factors in the recommender training process, such as online interactive ratings and randomly generated noises [3]. The dynamic strategy introduced by [17] focused on privacy budget allocation in a heuristic-based method. However, when applied to DPFR, it confronts the limitation that a heuristically designed strategy can be far from the optimal privacy budget allocation.

CMBA is an online decision-making scheme applicable in complex dynamic environments [21]. [22] applied CMBA to improve personalized FL. [23, 21] applied CMBA to improve client selection for FL framework by overcoming dynamic training environments. Because of the dynamic nature of user interactions with recommenders, we are among the first to utilize CMAB for optimizing the allocation of the privacy budget in DPFR.

Differential privacy (DP) [24, 12] is a mechanism designed to limit an attacker’s ability to gain additional knowledge about individuals in a dataset. A typical approach to achieve DP is by introducing randomness into computations, which conceals the details of individual data records. Formally, DP is characterized by $\epsilon$, which defines the upper bound on the difference between two neighboring inputs, and $\delta$, which represents the residual probability. The formal definition of classic ($\epsilon,\delta$)-DP is provided in Definition 1.

In the DP mechanism, revisiting the same dataset increases the risk of privacy leakage compared to a single access [25]. The composition theorem [26] states that the privacy budget per query should decrease as the number of accesses to the dataset grows. The most fundamental form of this is the sequential composition theorem, presented in Theorem 1.

Following this, in federated learning [18, 27], clients can securely update the recommender models using private datasets and upload the noisy gradients to the server for global aggregation in each training round. Specifically, a client $u$ in the differentially private federated recommender (DPFR) framework updates the gradients for the local item embedding $\nabla\bm{\iota}_{u}^{t}$, the local user embedding $\nabla\bm{\nu}_{u}^{t}$, and other recommender parameters $\nabla\bm{\omega}^{t}_{u}$, respectively [3, 28]. Before uploading these local recommender models to the server, the client distorts the local gradients by adding noise: $\nabla\tilde{\bm{\omega}}^{t}_{u}=\nabla\bm{\omega}^{t}_{u}+\bm{n}_{\omega}$ and $\nabla\tilde{\bm{\iota}}_{u}^{t}=\nabla\bm{\iota}_{u}^{t}+\bm{n}_{\iota}$, where $\bm{n}_{u}=[\bm{n}_{\omega},\bm{n}_{\iota}]$ represents the DP noise generated by a specific DP noise mechanism (e.g., Gaussian [14] or Laplace [15]) based on the allocated privacy budget $(\epsilon_{u}^{t},\delta_{u}^{t})$. ¹¹1The user embedding is generally stored locally after being updated, and therefore does not require noise addition.

The foundational concept of the Contextual Multi-Armed Bandit (CMAB) algorithm is essential for addressing decision-making challenges that involve balancing exploration and exploitation. Analogous to rows of slot machines (one-armed bandits), the CMAB algorithm deals with selecting actions over successive rounds to maximize cumulative rewards. Let $A$ denote the number of arms (or actions), and $t$ represent discrete time steps. At each time step $t\in\{1,\dots,T\}$, the algorithm selects an action $a^{t}$ from the space of action $\mathcal{A}=\{1,2,\dots,A\}$ based on observed environmental information (e.g., any context vector matrix $\mathbf{X}^{t}$). The reward $r^{t}$ corresponding to the chosen action is then observed. The goal of the algorithm is to iteratively refine its action-selection strategy to maximize the expected cumulative reward over time, which can be expressed as:

In Fig. 1, we present the workflow of a typical DPFR system. There are two main components: the server and clients. The server plays two functions: aggregating model parameters of the recommender and allocating the privacy budget to each client to determine the noise scale [29, 30]. Clients are responsible for conducting local model updates with private datasets. Before uploading local recommender models to the server, a DP noise adder will generate noises according to the allocated privacy budget to distort local models [3, 19, 6].

In the system, there are $U$ clients, denoted by the set $\mathcal{U}=\{1,\cdots,U\}$. The DPFR can conduct the maximum $T$ rounds of model training. The total privacy loss of each client is constrained by a fixed total privacy budget $(\epsilon_{u}^{total},\delta_{u}^{total}),\forall u\in\mathcal{U}$ to be consumed throughout the entire training. During the training process, clients and the server need to exchange information multiple times via the following five steps.

In Step ①, all clients upload ID numbers of item samples used for the local training. The server can reform the ID information as the context matrix denoted by $\bm{\mathrm{X}}^{t}=[\mathrm{X}_{u,i}^{t}]^{U\times I}$. Here, $I$ represents the total number of items, and $\mathrm{X}_{u,i}^{t}\in\{0,1\}$. $\mathrm{X}_{u,i}^{t}=1$ indicates that item $i$ is used for training on client $u$ in this round, while $\mathrm{X}_{u,i}^{t}=0$ signifies that the item is not used. Note that $\bm{\mathrm{X}}^{t}$ is commonly uploaded together with updated parameters in Step ④ for aggregating item embeddings in related works [3]. It makes no difference in uploading $\bm{\mathrm{X}}^{t}$ in either step²²2It is worth mentioning that $\bm{\mathrm{X}}^{t}$ before uploading can be obfuscated by clients with pseudo records to enhance privacy. Since our focus is not on how to obfuscate $\bm{\mathrm{X}}^{t}$, we simply assume that existing obfuscation methods  [3] will be applied..

In Step ②, the server allocates $(\epsilon_{u}^{t},\delta_{u}^{t})$ privacy budget to client $u\in\mathcal{U}$ in round $t$. If a client exhausts its privacy budget, it quits the training process. Besides, the server can verify the noise scale [29, 30] and account cumulative privacy budget consumption using privacy accounting methods for different DP mechanisms, such as native composition for Laplace noises [14] and Moments Accountant for Gaussian noises [31].

In Step ③ and ④, client $u$ updates the recommender model via Local Trainer using the latest user-item interactions in local data. Local updating yields gradients of the local item embedding $\nabla\bm{\iota}_{u}^{t}$, the local user embedding $\nabla\bm{\nu}_{u}^{t}$ and other recommender parameters $\nabla\bm{\omega}^{t}_{u}$, respectively [3]. After local training, client $u$ uploads $\nabla\tilde{\bm{\omega}}^{t}_{u}=\nabla\bm{\omega}^{t}_{u}+\bm{n}_{\omega}$ and $\nabla\tilde{\bm{\iota}}_{u}^{t}=\nabla\bm{\iota}_{u}^{t}+\bm{n}_{\iota}$ where $\bm{n}_{u}=[\bm{n}_{\omega},\bm{n}_{\iota}]$ represents DP noises generated by DP Noise Adder according to the allocated privacy budget $(\epsilon_{u}^{t},\delta_{u}^{t})$.

In Step ⑤, Model Aggregator deployed at the server aggregates recommender parameters and item embedding vectors based on $\bm{\mathrm{X}}^{t}$. For more details, please refer to [3]. Then, the server broadcasts aggregated parameters and item embedding vectors to all clients.

Our study primarily focuses on designing a more advanced BGTplanner. In our design, we suppose that the server can select an action $a^{t}\in\mathcal{A}$ for privacy budget allocation, where $\mathcal{A}=\{1,2,\ldots,A\}$ represents $A$ different levels of privacy budgets. The action $a^{t}$ corresponds to the privacy budget $(\epsilon_{u}^{t},\delta_{u}^{t})$, denoted by $(\epsilon_{u}^{t},\delta_{u}^{t})=C_{u}(a^{t})$, for generating DP noises on client $u$. Our objective is to maximize the final recommendation accuracy, gauged by reward $\sum_{t=1}^{T}r^{t}$. Here, $r^{t}$ denotes the reward of round $t$, which can be defined as the change of training loss or recommender accuracy between round $t$ and $t-1$. The FL training performance is highly dependent on data quality. Thus, $r^{t}$ should be related to the privacy budget allocated to round $t$ and training records contributed by clients. According to the process in Fig. 1, training records are represented by $\bm{\mathrm{X}}^{t}$. Thus, we define the objective as $\mathbb{E}\left[r^{t}\mid a^{t},\bm{\mathrm{X}}^{t}\right]$. Given the limited total privacy budget, our problem can be formulated as follows:

There are two challenges for solving $\mathbb{P}1$. First, we need to specify the expression of $\mathbb{E}\left[r^{t}\mid a^{t},\bm{\mathrm{X}}^{t}\right]$. To our best knowledge, the exact expression is unavailable in existing works. Second, it cannot be maximized by a greedy algorithm. If we only consider $\mathbb{E}\left[r^{t}\mid a^{t},\bm{\mathrm{X}}^{t}\right]$ for round $t$, we should allocate all budget to $t$ such that $\mathbb{E}\left[r^{t}\mid a^{t},\bm{\mathrm{X}}^{t}\right]$ is maximized, which unfortunately depletes the privacy budget for other training rounds, resulting in poor final recommendation accuracy.

In our problem, accurate prediction of rewards serves as a cornerstone for BGTplanner. Given an action $a$, we employ GPR to model the relationship between the context input, i.e., $\bm{\mathrm{X}}^{t}$, and the corresponding reward.

In a typical recommender, $\bm{\mathrm{X}}^{t}$ is a high-dimensional matrix, making it impossible to directly apply GPR. To reduce the dimension of $\bm{\mathrm{X}}^{t}$, we conduct the Singular Value Decomposition (SVD) operation to obtain $\bm{\mathrm{X}}^{t}=\bm{\mathrm{U}}\Sigma\bm{\mathrm{V}}^{*}$. Then, we rank diagonal elements in $\Sigma$ by a descending order to only reserve top $d$ elements, where $d$ is a tuneable hyper-parameter. Let $\bm{x}^{t}$ denote the vector containing reserved $d$ elements. Unless otherwise specified, we use $\bm{x}^{t}$ to denote the context vector hereafter.

With a much lower dimension, GPR can predict $\mathbb{E}\left[r^{t}\mid a,\bm{x}^{t}\right],\forall a\in\mathcal{A}$ based on historical information. To distinguish with $\mathbb{E}\left[r^{t}\mid a,\bm{x}^{t}\right]$, let $\hat{r}(a,\bm{x}^{t})$ denote the predicted reward. According to [32], $\hat{r}(a,\bm{x}^{t})$ can be modelled as a random variable sampling value from the distribution of the Gaussian Process $\text{GP}\left(\mu_{0}(\bm{z}^{t}),k(\bm{z}^{t},\bm{z}^{\prime})\right)$, where $\mu_{0}(\bm{z}^{t})$ denotes the mean function³³3For simplicity and practicability, $\mu_{0}(\bm{z})$ is assumed to be zero [32]. and $k(\bm{z}^{t},\bm{z}^{\prime})$ is the covariance (or kernel) function for input vector $\bm{z}^{t}$ and the historical input vector $\bm{z}^{\prime}$. To simplify our notation, we can concatenate any action $a\in\mathcal{A}$ (or a historical action $a^{t^{\prime}}\in\mathcal{A},\forall t^{\prime}<t$) with the context $\bm{x}^{t}$ (or $\bm{x}^{t^{\prime}}$) to form the vector $\bm{z}^{t}=[a,\bm{x}^{t}]$ (or $\bm{z}^{\prime}=[a^{t^{\prime}},\bm{x}^{t^{\prime}}]$). ⁴⁴4 Note that $a^{t^{\prime}}$ is already fixed in round $t^{\prime}$ for $t^{\prime}<t$.

To adapt the GPR to model the temporal dynamics of observations (i.e., inputs $\bm{z}$), we construct a composite kernel that incorporates both the squared exponential kernel function and the Ornstein-Uhlenbeck temporal covariance function [33], yielding

where $\mathcal{Z}^{t-1}=\{\bm{z}^{1},...,\bm{z}^{t-1}\}$ is the set of historical inputs until the round $t-1$, $|t-t^{\prime}|$ represents the temporal difference between $\bm{z}^{t}$ and historical input $\bm{z}^{\prime}$, and $\alpha$ is a hyper-parameter tuning the weight assigned to temporal correlations. The hyper-parameter $s>0$ represents the length scale for determining the influence of one input on another. Hence, a larger $k(\bm{z}^{t},\bm{z}^{\prime})$ indicates a stronger correlation between $\bm{z}^{t}$ and $\bm{z}^{\prime}$, implying the effectiveness of the historical observation with input $\bm{z}^{\prime}$ in predicting the reward with input $\bm{z}^{t}$.

Until round $t$, we can collect the input set $\mathcal{Z}^{t-1}$ and the reward vector $\bm{r}^{t-1}=[r^{1},...,r^{t-1}]^{\top}$ including $t-1$ observed rewards. Thus, we can establish a GPR with $t-1$ variables to predict the $r^{t}$ distribution. The detailed joint distribution of GPR is presented in Appendix B. Using the joint distribution of GPR and Bayes’ theorem, we can predict $\hat{r}(a,\bm{x}^{t})$ for any action $a\in\mathcal{A}$ with context $\bm{x}^{t}$ by the conditional distribution $\mathcal{N}({\mu}(\bm{z}^{t}),\sigma(\bm{z}^{t}))$ parameterized by the mean function ${\mu}(\bm{z}^{t})$ in Eq. (5) and variance function $\sigma(\bm{z}^{t})$,⁵⁵5Due to the limited space, the expression of variance function $\sigma(\bm{z}^{t})$ is presented in Appendix B. where $\bm{z}^{t}=[a,\bm{x}^{t}]$.

Here, $\mathbf{k}^{t-1}(\bm{z}^{t})=[k(\bm{z}^{t},\bm{z}^{1}),k(\bm{z}^{t},\bm{z}^{2}),\dots,k(\bm{z}^{t},\bm{z}^{t-1})]$ is the kernel vector between historical inputs and the current input, $\mathbf{K}^{t-1}=[k(\bm{z},\bm{z}^{\prime})]_{\forall\bm{z},\bm{z}^{\prime}\in\mathcal{Z}^{t-1}}$ represents the kernel matrix among historical inputs, and $\mathbf{I}$ denotes an identity matrix. Additionally, $\sigma_{\mu}$ is a variance parameter of distribution $\mathcal{N}_{\mu}(0,\sigma_{\mu}^{2})$, representing the deviation of the zero-mean random noise between the observed reward $r$ and the estimated reward $\hat{r}(a,\bm{x}^{t})$ [34].

For a given $a$, it can be concatenated with the context $\bm{x}^{t}$ to form the input $\bm{z}^{t}$. By leveraging Eq. (5), we can estimate the expected reward $\hat{r}(a,\bm{x}^{t})$. By enumerating $a\in\mathcal{A}$, we can predict the reward for choosing different actions. Note that our Predictor design is not based on a fixed $\bm{x}^{t}$. It can process dynamic contexts for predicting rewards with the evolving dynamics of user-item interactions over time.

We next discuss the design of the long-term privacy budget constrainer in BGTplanner.

In $\mathbb{P}1$, the privacy budget is constrained in the entire training process by (3b). To solve it, we decouple the time-dependent privacy budget constraint with an online queue optimization method [35, 36] so that we can consider budget allocation round by round in $\mathbb{P}1$. For training round $\tau$, considering that the inequality $\sum_{t=1}^{\tau}\epsilon_{u}^{t}\leq\sum_{t=1}^{T}\epsilon_{u}^{t}$ always holds when $\tau\leq T$, we can relax the constraint in Eq. (3b) as $\sum_{t=1}^{T}\epsilon_{u}^{t}\leq\epsilon_{u}^{total},\forall u$. $\delta_{u}^{t}$ can be constrained in a similar way. For saving space, we simply use $\epsilon_{u}^{t}$ to denote the privacy budget hereafter.

The problem enforcing long-term privacy budget constraints can be transformed into queue recursion optimization with Lagrange multipliers $\bm{\lambda}^{t}={[\lambda_{u}^{t}]^{U}}^{\top},\forall t.$ Therefore, the Lagrange function of reward in Eq. (3a) can be written as: $L(\bm{a},\bm{\lambda})=\sum_{t=1}^{T}L^{t}(a^{t},\bm{\lambda}^{t}),$ where

Here, $\bm{\epsilon}^{total}=[\epsilon^{total}_{u}]^{U}$ is the total privacy budget vector, $\bm{\epsilon}^{t}=[\epsilon^{t}_{u}]^{U}$ is the per-round privacy consumption vector for all clients and $\epsilon^{t}_{u}=C_{u}(a^{t})$ is the function mapping actions and privacy budgets. Additionally, $\langle\cdot,\cdot\rangle$ represents the inner product of two vectors. The problem $\mathbb{P}1$ is converted to maximizing the reward with the constraint punishment by solving $\min_{\bm{a},\tau}\max_{\bm{\lambda}}L(\bm{a},\bm{\lambda})\;\text{s.t.}\;\eqref{EQ:c2},\eqref{EQ:c3}.$ By penalizing the privacy budget consumption per training round, we can simplify the problem by only considering how to optimize $L^{t}(\,a^{t},\bm{\lambda}^{t})$ for a particular round $t$.

By resorting to the online mirror descent (OMD) algorithm [37, 38], we can tackle the Lagrangian dual problem in every round $t$, formulated as $\min_{\bm{\lambda}^{t}\in\mathcal{V}}D^{t}(\bm{\lambda}^{t})$, where

Here, $\mathcal{V}=\left\{\bm{\lambda}\in\mathbb{R}^{N}:\bm{\lambda}\geq 0,\,\|\bm{\lambda}\|_{1}\leq\Lambda\right\}$ is the space of the dual variable $\bm{\lambda}$, and $\Lambda>0$ is the $l_{1}$-radius of $\mathcal{V}$.

With the determined space set $\mathcal{V}$, Constrainer can update $\bm{\lambda}^{t+1}$ in the rest training rounds with the following rule:

where $B(\cdot,\cdot)$ is the Bregman divergence of the generating function and $\eta_{t}$ is the step factor of the OMD algorithm. Here, we select the generating function as the negative entropy function, the same as that in [36].

To sum up, Constrainer enables the integration of long-term privacy budget constraints into instant reward maximization and focuses on dynamically tuning $\bm{\lambda}^{t}$ to penalize the privacy budget consumption properly.

The last component in BGTplanner is designed by leveraging contextual Multi-Armed Bandit (CMAB) to make final budget allocation decisions. Briefly speaking, there are two phases in BGTplanner, i.e., the initial stage and the exploration-exploitation stage, which are described as below.

We provide a detailed description of the BGTplanner algorithm in Alg. 3. The algorithm operates in two stages: an initial stage, described in Alg. 1, and a subsequent exploration-exploitation stage, which includes three main steps in each round. In each training round of the second stage, BGTplanner predicts the scores for all actions, selects the optimal action and adjusts the dual variables based on observed rewards and the remaining privacy budgets. With the chosen budget allocation action, the server and all clients execute one round of DPFR training, as detailed in Alg. 2, to update the model and embedding parameters. This process navigates a dynamic training environment, where the privacy budget is strategically allocated to maximize model performance while adhering to privacy constraints. The iterative process continues until the privacy budget is exhausted or the desired training performance is achieved.

Given $(\epsilon^{total}_{u},\delta^{total}_{u})$, each client can allocate its budget as follows. If the Laplace mechanism is adopted, $\delta^{t}_{u}=0$ and each client can employ the native composition rule [14] to accumulate the total privacy loss $\epsilon^{total}_{u}$ during the multiple rounds. Otherwise, if the Gaussian mechanism is adopted, clients can convert the budget to the RDP (Rényi Differential Privacy) budget, which can then be simply split into multiple training rounds [15]. In this case, Eq. (3b) should be updated by the RDP budget. It has been proved in [14, 15] that if clients follow these methods to accumulate their privacy loss, $(\epsilon^{total}_{u},\delta^{total}_{u})$-DP is satisfied on client $u$.

BGTplanner incurs additional computation and memory overhead for making budget allocation decisions. Through analysis, we show that the overhead cost is lightweight and affordable for the server. For Predictor, the complexity for calculating the Gaussian Kernel is $\mathrm{O}(A\cdot d\cdot t)$, with $d$ dimension of the input vector. The computational complexity for estimating the reward $\mu(\bm{z}^{t})$ in Eq. (5) is $\mathrm{O}(A\cdot d\cdot t^{2})$. Calculating the score vector $\beta^{t}(a)$ by Eq. (11) incurs a complexity of $\mathrm{O}(A\cdot U)$, and computing the probability vector $\bm{p}^{(t)}$ via Eq. (12)-Eq. (13) has a complexity of $\mathrm{O}(A)$. To conclude, the total computation complexity per round is $\mathrm{O}(A\cdot(t^{2}\cdot d+U))$. According to [37], the computational complexity of Constrainer is also small by using the MOD algorithm.

Additionally, the memory complexity is $\mathrm{O}(A\cdot t^{2}+U)$, primarily because of the storage requirements for 1) the GP kernels, 2) estimated means, scores and probabilities for all actions, and 3) client budgets and penalties information.

We then discuss the regret performance of BGTplanner. We define the optimal expected reward for one round while ensuring resource utilization remains within a predefined budget as OPT [36], i.e.,

With Definition 2, let $T\cdot\text{OPT}$ denote the upper bound of the optimal reward in online scenarios [39], we can minimize the regret between the OPT and the actual reward obtained by BGTplanner online algorithm as:

We first give the error guarantee of the estimation of $\ell_{1}$-radius $\Lambda$.

Here, when $\epsilon^{total}_{min}=\mathrm{O}(T\cdot M(T_{0}))$, we can donate $\Lambda\lesssim\frac{T\cdot\text{OPT}}{\epsilon^{total}_{min}}+1$, where the notation ‘$\lesssim$’ denotes a represents multiple that is less than. The comprehensive proof of Lemma 1 can be found in Lemma 4.1 in [36] . With the estimation error guarantee of $\Lambda$ in Lemma 1, the OMD to update $\bm{\lambda}$ achieves optimal regret bounds $\mathrm{O}(\sqrt{T})$ (Lemma 2.2 in [36]). Therefore, we can obtain the following regret guarantee of Alg. 3 and we rewrite the theorem as follows: