Towards User-level Private Reinforcement Learning with Human Feedback
Authors: Jiaming Zhang
Mingxi Lei
Meng Ding
Mengdi Li
Zihang Xiang
Difei Xu
Jinhui Xu
Di Wang
Venue: COLM 2025 (2025)
Keywords: Differential Privacy
RLHF
LLM alignment
TL;DR: We propose AUP-RLHF, a user-level label DP framework that improves privacy-utility trade-offs in RLHF for better model alignment.

Abstract: Reinforcement Learning with Human Feedback (RLHF) has emerged as an influential technique, enabling the alignment of large language models (LLMs) with human preferences. However, how to protect user preference privacy has become a crucial issue, as LLMs tend to remember users' preferences. Most previous work has focused on using  differential privacy (DP) to protect the privacy of individual data. However, they have concentrated primarily on item-level privacy protection and have unsatisfactory performance for user-level privacy, which is more common in RLHF. This study proposes a novel framework, AUP-RLHF, which integrates user-level label DP into RLHF. We first show that the classical random response algorithm, which achieves an acceptable performance in item-level privacy, leads to suboptimal utility when in the user-level settings. We then establish a lower bound for the user-level label DP-RLHF and develop the AUP-RLHF algorithm, which guarantees $(\varepsilon, \delta)$ user-level privacy and achieves an improved estimation error. Experimental results show that AUP-RLHF outperforms existing baseline methods in sentiment generation and summarization tasks, achieving a better privacy-utility trade-off.

Published as a conference paper at COLM 2025
Towards User-level Private Reinforcement Learning with Hu- man Feedback
Jiaming Zhang" 1 Mingxi Lei"; Meng Ding Mengdi Li ZZihang Xiang? Difei Xu Jinhui Xu , Di Wang2.
RRemmin University of China, Provable Responsible AI and Data Analytics (PRADA) Lab, SKing Abdullah University of Science and Technology, *State University of New York at Buffalo Correspondence: di. wangekaust. edu.
Abstract
Reinforcement Learning with Human Feedback (RLHF) has emerged as an influential technique, enabling the alignment of large language models (LLMs) with human preferences. However, how to protect user preference privacy has become crucial issue, as LLMs tend to remember users' pref- erences. Most previous work has focused on using differential privacy (DP) to protect the privacy of individual data. However, they have concentrated primarily on item-level privacy protection and have unsatisfactory perfor- mance for user-level privacy, which is more common in RLHE. This study proposes a novel framework, AUP-RLHF, which integrates user-level label DP into RLHE. We first show that the classical random response algorithm, which achieves an acceptable performance in item-level privacy, leads to suboptimal utility when in the user-level settings. We then establish lower bound for the user-level label DP-RLHF and develop the AUP-RLHF algo- rithm, which guarantees (e, user-level privacy and achieves an improved estimation error. Experimental results show that AUP-RLHF outperforms existing baseline methods in sentiment generation and summarization tasks, achieving better privacy-utility trade-off.
1 Introduction
The advent of large language models (LLMs) has significantly transformed the field of artifi- cial intelligence, leading to widespread adoption and application in diverse domains(Hong et al., 2024; Yang et al.; Cheng et al.; Zhang et al., 2024), such as legal (Chalkidis & Ke- mentchedjhieva, 2023; Wu et al., 2023b), medical (Thirunavukarasu et al., 2023; García- Ferrero et al., 2024; Yuan et al., 2024), and coding assistant (Ross et al., 2023; Nam et al., 2024; Kazemitabaar et al., 2024). A notable advancement in this area is the incorporation of Reinforcement Learning from Human Feedback (RLHF), paradigm that improves the performance and alignment of language models by integrating human preferences and feedback into the training process (Ouyang et al., 2022).
However, since RLHF relies on collecting human feedback, it inevitably raises privacy concerns, particularly regarding the identity and sensitive information of human annota- tors. For example, in the financial domain, investment advisors can annotate and provide feedback on -LM-geeerteed investment recommendations. These preference labels may encompass sensitive information such as individual investment strategies, risk preferences, and financial objectives. In addition, LLMs have the potential to infer individual user pref- erences, interests, or personal attributes by analyzing queries and interactions posed. Such inferences may lead the generation of targeted advertisements, personalized suggestions, or other customized content, which in turn could inadvertently expose sensitive aspects of the user's 's private life (Yan et al., 2024; Lyu et al., 2023; Harte al., 2023; Hu al., 2024; Huang et al., 2024).
Eqqul contributions.

---

Published as a conference paper at COLM 2025
To address the aforementioned privacy concerns, Differential Privacy (DP) (Dwork et al., 2006), which quantifies privacy protection by adding noise to ensure the anonymity of individual data in statistical analysis, has become a common approach, effectively protecting user privacy. Recently, there have been an increasing number of studies focusing on DP- RLHF (Chowdhury et al., 2024b; Chua et al., 2024; Wu et al., 2023a; Teku et al., 2025), demonstrating the feasibility of DP to RLHF. However, traditional DP' algorithms in RLHF focus on item-level privacy, where they ensure that the inclusion or exclusion of any single data point does not significantly affect the model's 's output. In practical scenarios, user typically contributes multiple pieces of data, rendering item-level privacy insufficient. Specifically, existing methods offer privacy guarantees that deteriorate as user participation increases or blindly introduce excessive noise, leveraging the group property of differential privacy, which severely impacts the performance of the model in deployment (Lev et al., 2021). For example, in Section 4, we will show that the Randomized Response mechanism, which is the canonical way of protecting label privacy and achieves the nearly optimal rate in the item-level case (Chowdhury et al., 2024b), will significantly degrade its utility in the user-level privacy scenario. Thus, there is a pressing need for developing user-level label DP-RLHF with better privacy-utility tradeoff.
To tackle the challenges outlined above, motivated by the current developments of user-level DP supervised learning (Geyer et al., 2017; Bassily & Sun, 2023a; Levy et al., 2021; Liu & Asi, 2024a; Ghazi et al., 2024; Zhao et al., 2024), we propose a novel framework, namely AUP- RLHF, which satisfies user-level label DP and achieves a smaller estimation error. The key intuition the use of the average gradient of the loss with respect to each user's 's preferences for parameter updates in the DP-SGD algorithm (Abadi et al., 2016; Su et al., 2024; Shen et al., 2023; Xiao et al., 2023; Hu et al., 2022). However, unlike the existing DP-SGD designed for item level, we leverage outlier removal and adaptive sampling processes to handle the high sensitivity ensure that the gradient exhibits concentrated properties. Then, at each step of the SGD update, we add noise, which is significantly small, related to the concentrated parameters only to ensure privacy. Our contributions are as follows:
1. We first demonstrate that under canonical assumptions, the classical randomized re- sponse method, which performs well in the item-level setting, exhibits large estimation error O dymm m in the user-level setting. Specifically, when the contribution for each user Viee
is large, randomized response sacrifices utility to provide uniform privacy protection in the privacy-utility trade-off, rendering the algorithm unsuitable. We also establish
lower bound Ω
d=
Vd for user-level DP-RLHE.
Vnmi
V/nn
We are the first to conduct a theoretical analysis user-level differential privacy in RLHE To close the gap between the upper and lower bounds, we develop AUP-RLHF
that satisfies (E, 5) usser-levl label privacy, with an upper bound of O estimation error. Additionally, we extend the algorithm to the K-wise case, where the Klavā
dvā
for the
upper bound of the estimation error remains O
VINI
3. We empirically validate AUP-RLHF through experiments on commonly studied tasks. We conducted controlled sentiment generation and summarization experiments. We show that, across base models of varying sizes and different privacy parameter configurations, AUP-RLHF consistently outperforms the other user-level DP baselines.
2 Related Work
User-level DP learning. User-level DP has garnered increasing attention due to its privacy protection, which aligns more closely with real-world scenarios. Several studies have explored various tasks of user-level DP, such mean estimation (Levy et al., 2021), empirical risk minimization (Levy et al., 2021), and stochastic convex optimization (Bassily & Sun, 2023b; Liu & Asi, 2024b). Levy et al. (2021) first introduced user-level DP, providing stricter privacy protection by safeguarding the entire contribution of users, based on novel private mean estimation algorithm. Bassily & Sun (2023b) further investigated how
2

---

Published as a conference paper at COLM 2025
carefully selected first-order optimization methods can achieve optimal utility under local DP conditions. Liu & Asi (2024b), on the other hand, ensured query concentration through above-threshold and adaptive sampling techniques, thereby releasing the minimal number of user assumptions while still achieving optimal utility. However, none of them has considered RLHF. In this paper, build the first theoretical results user-level (label) DP-RLHF.
Privacy-preserving in RLHE Zhu et al. (2023) provided a theoretical framework for RLHF under clean data conditions, demonstrating the properties of MLE and pessimistic MLE. However, due privacy leakage issues (Li al., 2023), MLE cannot be applied directly. Building on this, Chowdhury et al. (2024b) introduced theoretical framework for incorpo- rating DP into RLHF, designing an unbiased loss function based on random responses to achieve DP. Teku et al. (2025) proposed novel multi-stage mechanism that privately aligns the model with labels from previous stages combined with random responses. However, as we will show later, random responses cannot be easily extended to more practical user- level settings, which results in poor utility. Meanwhile, Wu et al. (2023a) utilized DP-SGD across the three stages of RLHF- Supervised Fine-Tunings Reward Model Learning, and Alignment with PPO ensure privacy preservation. Chua et al. (2024) explored the application of Group Privacy and User-wise DP- to achieve user-level DP in RLHE However, they provide only experimental results and lack rigorous theoretical guarantees. Our experiments will show that our proposal method has better performance than these methods.
Preliminaries
3.1 RLHF
In the RLHF process, the data structure used is quadruple (s,a",at aa,,at, where represents the prompt provided by the user to the LLM, a and a are the two responses generated by the LLM, and y E {0, indicates the human preference between the two responses. We follow the notion of Chowdhury et al. (2024b); Ouyang et al. (2022); Zhu et al. (2023), where preferences are modeled as Bradley-Terry-Luce (BTL) model:
rre- (s,a')
exp
Pg- y = s, s, aaaaaa))
exp (ra- (s, a))) + exp (rg- (s,a²) o(ro- (s, rg- (s, (s)
where, S x A + (0,1} denotes the ground-truth reward model parameterized by l and (z) = 1 refers to the sigmoid function. And we assume reward model linear function: rp- (s,a) (s, 0', where Φ S x A + R2 is some known and fixed feature map, constructed by removing the last layer of pre-trained language model in LLM, and in that case, 0* corresponds to the weights of the last layer. Let = ((s,at) +ss a²) denote the differential feature of actions at and a at state s.
3.2 Differential Privacy
We use the notation Z; = (Sij, G.. atp Mit) represent user i's contributions, and
2; == (Si,, afy ii Vi,)) represent user i's jth contributions. We use capital Z denote one user and z to denote one item. We consider user-level DP, which protects all of a user's 's contributions, meaning that the output of an algorithm M operating on a dataset with users (thus, mn samples in total) D (2,) 'indistinguishable when single user's contributions in D are altered. A formal definition is provided below.
Definition 1. (User-Level Differential Privacy). A mechanism M (Z"I"" - Rd is (e, user-level differentially private, if for any neighboring datasets D,D' (Z" that differ in one user, and for any event O in the range of M, we have
Pr(M(D) O] < Pr(M(D') 0] +
3

---

Published as a conference paper at COLM 2025
The original definition of DP (Dwork et al., 2006) assumes that the whole dataset is private, which is quite strong for many scenarios in RLHF. As in RLHF, a user's preferences are only associated with the label of the prrompt,respoosst label) tuple, while the prompt itself is not sensitive, as it is sampled from pre-collected datasets that are already considered public knowledge (Chowdhury et al., 2024b; Teku et al., 2025). Thus, in this paper, we consider the label DP (Ghazi et al., 2021). We assume that (s, 5, a²) is publicly accessible, while user preference data y E {0, } are private. Therefore, the focus is on protecting the user's 's preference information y. The definition of label DP at the user level is provided below.
Definition 2. (User-Level Label Differential Privacy). A mechanism : (2"h R R is (e, user-level label differentially private, if for any neighboring datasets D, D,D' E (Z"")" that differ in the labels of one user, and for any event in the range of M, we have
Pr[M(D) E O] S ef Pr[M(D') E O] +
Note that item-level label differential privacy is specific case of this definition with m
4 Sub-optimality of Random Response
To achieve label-level DP, natural approach is to employ the random response (RR) (Warner, 1965) mechanism to each label, which achieves privacy by randomly flipping labels. fact, such simple idea has been shown to achieve satisfactory performance in the item-level DP-RLHF both theoretically and practically (Teku et al., 2025; Chowdhury et al., 2024b). However, the theoretical behavior of RR in the user-level setting remains unclear. In the following, we first investigate the theoretical behavior of RR in the user-level setting. We will then show how the upper bound of the estimation error degrades when each user contributes a large amount of data m..
4.1 User-level Random Response
Let 2 0, m be the sample numbers of a single user, and y & {0,1} the group privacy property, extend the classical RR to the user level, we need to flip each label to make it satisfy m: <-DP. In detail, the outputs of the RR mechanism ý follow the following probability distribution
1 be the true label. By
ct/m
P y y]
1 pc/m ee/m o(emm)
Pl =1 o(e/m).
It is easy to show that User-level RR is e-user-level label DP. Then, we consider the following loss the perturbed data, which is unbiased to the original loss in (non-private) RLHE We will present the design of this loss function in Appendix B.3.
" --00= log Pl, +1 (Tu) =0) -
TD.
= log P
(1)
where the predicted scores of each randomized label Vijj given Xi,j are defined as:
(xT.0)
o(e/m)
(1 (xT.0)
cle/m)
Ply
Ph
(1
x
(1-e(e/m))
Thus, our private model is defined
yRr E T
(2)
where ŌRR satisfies e-user-level label DP due RR and the post-processing property of DP. To get the estimation error of 0RR, we make the following assumption, which is standard in the existing literature (Shah et al., 2016; Shin et al., 2023; Chowdhury et al., 2024b).

---

Published as a conference paper at COLM 2025
Assumption (Boundedness). (a) 8 lies in the set θ = = R$ (1,0) 0, | < cB}
with some constant Here the condition (1, 8) 0 ensures identifiability of 0" (b) Features are bounded, i.e, for all (s,a) we have || a) S L for some constant L.
- T x1 denote the sample covariance matrix of differential features Let Ep == 1
mi
x = (5 ( ( a.))
Theorem 1. For any > O, the private model ÖRR is s-DP. Moreover, under Assumption for any O, with probability least a, we have
c/m 1 d log(1/a)
@ōrR 0*1 - 00
Ami (ED) c//m
HM
where = 2IB 22LB. Amin (Ep) is the minimum eigenvalue of ED.
Note that, the bound non-trivial only when the sample covariance matrix positive definite. However, this assumption is too strong due to the high dimensionality of the feature vector. We can relax by imposing that the population covariance matrix is positive definite by imposing a coverage assumption on the state-action feature space, which is commonly encountered offline bandit and reinforcement learning settings (Yin et al., 2022).
Assumption 2 (Coverage of feature space). Defining the differential state-action features & (s, & as, and population covariance matrix I EE (dP [xx T].
We assume that Amin (Σ) 2 x for some K >
Corollary 1. Under the same assumption in Theorem and Assumption 2, with probability least 1 a, we have
|oRR 0" 50
1 c m
log(1/a)
Yx c
111
Remark The estimation error in Corollary is influenced by the convergence parameter which implicitly depends on the dimensionality d (Wang et al., 2020). Since ||x||| S L,
it follows that 2 O 12 by Assumption 1. Thus, to implement user label level DP,
When m = 1, iee, when in the item-level case, our bound matches the nearly-optimal rate shown in Chowdhury et al. (2024b). However, when m is large, & becomes a vanishingly small quantity. Consequently, m
the estimation error of estimator ōRR is O ((
the estimation comes to O Pm estimator inefficient.
which can be large magnitude, rendering the
4.2 Lower Bound of User-level DP-RLHF
On the other hand, we introduce the lower bound of estimation error for user-level DP- RLHF, which characterizes the worst-case performance of any user-level DP algorithms. A detailed discussion is deferred to the Appendix B.5.
Theorem 2 (Informal Statement). For any (e, -userreleeeel DP algorithm with output Oprior there exists an instance of the BTL model with the underlying parameter O* such that
d
Vd
El|Oprio 0'112 2 5
(3)
nm
V Vmnn
Main Method
In the previous section, we have shown that although the RR-based mechanism for DP- RLHF in the user-level setting simple, there are several issues. First, when the contribution

---

Published as a conference paper at COLM 2025
Algorithm 1 AUP-RLHF
Input: Dataset D (Zi...., 7n) (Z" privacy parameters (e, initial point d
2: Based on users, partition D into disjoint datasets {Di)ie(k) where Dj is of size
N n/22+11i
3: for = l.....,,k do
4: Run Algorithm 2 with (0; Dú n4 Tú M/, E, E, 7,) and get its output t,.
5: end for
6: Output: 0
Algorithm 2 AdapUserPrrv-SGD
1: Input: Initial model weights 8,, training set D of users and records, batch size ii, learning rate ',, iterations T, privacy parameters (e, concentration threshold т b Compute noise multiplier
2: <- PrivacyAccount( 2,
2, n, 7)
3: for 1,,,..., T do
4:
Randomly draw U, batch of users
>> Subsampling
5: for Ut do
6: Sr,i < d [je(m] Ve((),2))
Compute user-averaged gradient
7:
end for
8:
of + 1 Lireu 1(18 8ir $ T)
n if AboveThresholld e/,, 4n/5) = in Alg. 3 then Run
Compute concentration scores with sf
9:
Set B, 0
11:
Set fr. + Ep 1(1grr 1(1 gull < 2T)
Add ith user to Bi with probabiiyy Pt. where
Remove the outliers
0
if fúi < R/2 if fúi 2 2n/3 otherwise
Pr
1
fu-R//2
R/6
Aggregate and add noise for the remaining users:
14:
Let Ei = | LieR, 8t,i B, is not empty, and 0 otherwise
gi + gi + Vt, where 1/ ~ N(,, 8r3
log(e
15:
4a
16:
0 + 0: - 18:
> Update model
else
18:
Halt. end if
Halt the algorithm if it does not pass.
19:
20:
end for
21:
return - E
of each user mn is large, we can see the privacy-utility trade-off in Corollary is bad. This is because, intuitively, larger indicates have more data, the estimation error should be lower. However, a larger m will introduce larger error for the RR mechanism, which contradicts our expectations. Second, we can there is a large gap between the lower bound and upper bound. Thus, natural question is whether we can further fill in the gap. Finally, the private model +RR needs to be the exact minimizer of the loss in (2), which is impossible to get in practice due to the non-convexity of the loss. Thus, a practical and efficient DP² algorithm is needed.
In this section, we propose our AUP-RLHE method, which is based on DP-SGD (Abadi et al., 2016; Wang et al., 2017; Wang & Xu, 2019; Wang et al., 2019). Instead of flipping labels, here we consider the original loss function in the BTL model with linear reward:
((0,z) [1 log 1 0) log P2.0],
where P=,1 or (x T). Pz, (1- (xTo))

---

Published as a conference paper at COLM 2025
In AUP-RLHF (Algorithm 1), we first partition the data into several disjoint sets, and for each set, we will use a DP-SGD-based update, namely AdapUserPriv-SGD (Algorithm 2). In detail, during each iteration of parameter updates, the framework operates in three stages. First, a subset of users is selected via user-wise sampling, and the average gradient of the selected subset is computed user-level private mean estimation oracle, which outputs a gradient satisfying user-level DP (Step 9-15). Third, the gradient obtained from the previous step is used to perform gradient descent for parameter updates.
query (Step 4-8). Second, the query is passed through
The main difference between AUP-RLHF and DP-SGD is the private mean estimation oracle for aggregated gradients. If we directly extend DP-SGD to the user-level (Appendix Algorithm 4) (Chua al., 2024). for each user's data, we may aggregate their gradient and perform a clipping with some threshold C (Step 9). In this case, the sensitivity of the average of clipped gradients is O(2), with ñ as the number of subsampled users. However, such a method does not leverage information on each user's data, leading to unsatisfactory performance. In this work, leverage the user-level private mean estimation oracle proposed by Liu & Asi (2024b), which is an adaptive sampling procedure to remove outliers to let the aggregated user-level gradients add less noise. To achieve adaptive mean estimation for concentrated samples, we first introduce the concept of concentration.
Definition 3. A set of random samples {ei)ie(m) is cconceetneee if there exists point
x E Rd such that with probability at least
max
|X - x S T. ic(n]
After adaptive sampling (Step 8-14), we can obtain a T-concentrated subset users, with user-averaged gradients (gu,)ieu, as the random samples. Due to the concentration property, the sensitivity of the aggregated gradients will be bounded (TT). Thus, there is no need to do clipping and it allows the added noise to scale proportionally to (which is Ö vm rather than the constant clipping radius C, resulting in significantly smaller noise and achieving improved utility.
Specifically, to get such a concentrated subset, the algorithm first employs an AboveThreshold mechanism (Algorithm 3) compute concentration score, which determines whether the average gradient of users is predominantly concentrated (Step 9). This ensures that the input dataset is approximately z-concentrated. Subsequently, outlier detection performed by assigning each sample a score that quantifies its likelihood of being an outlier, i.e., not concentrated gradient. Each sample is then retained with a probability proportional to its score, effectively removing low-score outliers and yielding high-quality, concentrated subset of data (Step 10-12).
Given the total number of users, batch size of users, number of iterations, and privacy budget, this subroutine can determine the noise ç we need add in Step 16 of Algorithm ensure the algorithm satisfies (e,5) DP. We adopt the Poisson subsampling, common practice the privacy accounting of DP-SGD, in Step 4. Thus, theoretically, we can show that ç = Ó en
can make the algorithm achieve (c, SDDP (3). However, in practice,
vTT
we always use various open source libraries to give more accurate calculations on such noise, such as DP Accounting !
Theorem 3. For any <,, 1, 1, Ō VTi((1/8) Algorithm is (E,8) user-level (label)
DP. Here, the Big-O notation omits other logarithmic terms.
In the following, we will show that it is possible to get an improved upper bound of estimation error with some specific hyper-parameters.
7

---

Published as a conference paper at COLM 2025
Theorem 4. Under Assumption and 2 and the condition in Theorem 3, for any 0 S 10
and
x 6 1, in Algoritium set k [log log mn], 8g ii ni, 1ii II.
min
Tiv (mm,d/8) T//44 I; S aLlog(n,dme and Ti O (m? + mn:Va) The v
/mn,e
mm
4L
output @ satisfies the following if n;
log (gg(ddn)) (og(mdn,//)
vd Vnne
E|lê - 12 - Ō
+
Vmn
The Big-Ô notation omits other logarithmic terms.
Remark 2. We discuss the case under the same condition as in Remark 1 when x = 0 ( As we mentioned, when m is a large quantity, the estimation error of the RR estimator is 002 dm), while the upper bound of AUP-RLHF is Ö dv We can see it improves
v MIC
factor of O my Vá
)- The factor of O (/))) is because SGD algorithm adds noise to each
dimension of the parameter 8. When m /n exceeds vd, our algorithm exhibits better utility than the RR algorithm, which is also commonly observed in practical scenarios.
In the previous section, we considered the case where the label is binary. In fact, our method can be directly extended to the general K-wise case. See Appendix B.4 for details.
Experiments
6.1 Experimental Setup
Tasks and Datasets. We evaluate our AUP-RLHF method on two different datasets with three different tasks. The IMDb dataset (Maas et al., 2011) is widely used movie review dataset containing both positive and negative reviews. We perform a controlled sentiment generation task on this dataset. The TL;DR dataset (Völske et al., 2017) is summarization dataset containing posts from Reddit along with their corresponding titles, on which we conduct summarization task.
Base models. For each dataset and task, we use the pre-trained Gemma-2-2B (Team et al., 2024) and LLaMA-2-7B (Touvron et al., 2023) our base models.
Baselines. We compare our algorithm with three baselines, which all are user-level DP- based RLHF algorithms: Random Response (Section 4), User-wise DP-SGD (Chua et al., 2024), and Group Privacy (Chua et al., 2024). Additionally, we compare our results with those obtained from RLHF under non-private settings.
Evaluation. In the controlled sentiment generation task, we use the reward score as the evaluation metric. Additional details are provided in Appendix A.1. For the summarization task, we assess our AUP-RLHF algorithm by comparing its win rate against each baseline strategy. Following previous work RLHF (Rafailov et al., 2024), we adopt GPT-4 as proxy for human evaluation.
Settings. We set each user's contributions at mı 10, with и set to 2500 for the sentiment generation task, and = 50, = 1800 for the summarization task. We set privacy budgets = or ε = 8, with 8 fixed at 10-5 Due to the slower training speed of the SGD-based optimizer compared to Adam, we set the number of sub-datasets
and the number of training epochs for the reward model to 5 instead of 1. Other hyperparameter details are provided in Appendix A Table 3 and Table The experiments are carried out on machines with one Nvidia A100 GPU card, 14-core Intel Xeon Gold 6348 CPUs, and 100GB of RAM.
8

---

compared when 3. (3) Published as a conference paper at COLM 2025
Win
Loss
037
Reward
Userrttse
56%
44%
1.0
Userwise DPSGD
Rondom Response
5.%%
Resgonse Group Privacy
Group
0.5
Rivacy
0
3
60
80
100
Divergence
Win Rate
Figure IMDb Sentiment Generation (Llama-2-7b, 8).
Figure 2: Win Rate Against the SFT Model for TL;DR Summarization (Gemma-2-2b, 8).
6.2 Experimental Results
IMDb Sentiment. For the sentiment generation task, make the following observations based on the experimental results depicted in Figure 1, 3, and 4: (1) We observe that, under the same KL divergence, our AUP-RLHE outperforms other baselines in terms of the reward metric, demonstrating the superiority of our model. (2) Consistent with the theoretical analysis of differential privacy, relaxing the privacy budget leads to an improvement in the reward score metric. Specifically, we find that, for the same KL divergence, the reward values of AUP-RLHF and all baselines are higher when By comparing the experimental results of Gemma-2-2B and Llama-2-7B, we observe that at E = 3, the larger model yields improved performance, which is consistent with most DP fine-tuning papers (Yu et al., 2021; Wu et al., 2023a). However, at = 8, the performance improvement in the larger model is less significant, possibly due to the lack of sufficiently exhaustive hyperparameter search to find the optimal model performance.
TL;DR Summarization. Similar to the findings in the sentiment generation task, in Figure and 5 we observe that AUP-RLHF outperforms other baselines in terms of the win rate metric, across both model sizes and varying privacy budgets. Furthermore, when the privacy budget is set to e 3, the performance of all algorithms is suboptimal, with winrates below 50%. However, when the privacy budget relaxed of all algorithms improve. Meanwhile, our AUP-RIHF achieves significant increase in winrate, rising from 39% 63% on the Gemma-2 2-2BB model.
8, the win rates
I1
10
20
50
5
10
20
50
6
0.366
0.586
1.051
2.429
6 c=
1
1.101
1.284
1.631
2.402
C
0.139
0.175
0.246
0.461
3
0.726
0.809
0.928
1.182
0.086
0.102
0.128
0.189
8
0.531
0.578
0.639
0.750
Table 1: Effective noise of AUP-RLHF on TL;DR dataset.
Table 2:
Effective noise of User-wise
DPSGD on TL;DR dataset.
Analyzing AUP-RLHE. As observed in Table 1, as the number of user records m increases, the noise added to AUP-RLHF increases accordingly. This is because, based our theory, the variance of the noise is Ō (11 ). Thus, when the total size mn and iteration number T larger.
are fixed, mn- = .Mt is fixed, increasing reduces n, making the noise Ó +
Additionally, we find that, under the same and the noise in AUP-RLHF is smaller than that in User-wise DP-SGD. This due to the fact that our algorithm, based on the user-concentrated nature, requires the noise scale to be proportional to the concentration parameter rather than the clipping radius C. This reduction noise allows our algorithm to converge more quickly.

---

Published as a conference paper at COLM 2025
7 Conclusion
In this work, we study RLHF with user-level privacy. We first demonstrate the sub- optimality of the RR method, followed by presenting the lower bound for user-level DP-RLHF. Then, we propose the AUP-RLHF algorithm, which ensures that the output satisfies user-label DP while achieving better utility. In our experiments, we validate the superiority of our algorithm across two commonly used datasets.
Although we present an innovative approach, there are some limitations to our method that motivate future research directions. First, our upper bound (Theorem 4) relies strong assumption that the loss function is both strongly convex and Lipschitz continuous. Second, this upper bound we prove is suboptimal, which has additional factor of d compared to lower bound. This originates from our coverage assumption. Furthermore, when extending our analytical framework to DPO, non-linear assumption is required (Chowdhury al., 2024a; Zhu et al., 2023), making it difficult to unify the semi-norm
I| with the lo-oomm
Acknowledgements
Di Wang and Zihang Xiang are supported in part by the funding BAS/1/1689-01-01 from KAUST, and funding from KAUST Center of Excellence for Generative AI, under award number 5940.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Πlya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Raef Bassily and Ziteng Sun. User-level private stochastic convex optimization with optimal rates. In International Conference on Machine Learning, pp. 1838-1851. PMLR, 2023a.
Raef Bassily and Ziteng Sun. User-level private stochastic convex optimization with optimal rates. In International Conference on Machine Learning, pp. 1838-1851. PMLR, 2023b.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Amos Beimel, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. In Theory of Cryptography Conference, pp. 437-454. Springer, 2010.
Ilias Chalkidis and Yova Kementchedjhieva. tion. Xiviv preprint ar Xivi::200 130088, 2023.
Retrieval-augmented multi-label text classifica-
Keyuan Cheng, Gang Lin, Haoyang Fei, Yuxuan Zhai, Lu Yu, Muhammad Asif Ali, Lijie Hu, and Di Wang. Multi-hop question answering under temporal knowledge editing. In First Conference on Language Modeling.
Sayak Ray Chowdhury, Anush Kini, and Nagarajan Natarajan. Provably robust dpo: Aligning language models with noisy feedback. In arxiv preprint arXiv:2403.00400 2024a.
Sayak Ray Chowdhury, Xingyu Zhou, and Nagarajan Natarajan. Differentially private reward estimation with preference feedback. In International Conference on Artificial Intelligence and Statistics, pp. 4843-4851. PMLR, 2024b.
Lynn Chua, Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Daogao Liu, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Mind the privacy unit! user-level differential privacy for language model fine-tuning. arXiv preprint ar (rx::2246..4433 2024.
10

---

Published as a conference paper at COLM 2025
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-40) 2014.
Iker Carcia-Ferrero, Rodrigo Agerri, Aitziber Atutxa Salazar, Elena Cabrio, Iker de la Iglesia, Alberto Lavelli, Bernardo Magnini, Benjamin Molinet, Johana Rigau, et al. Medical mt5: an open-source multilingual text-to-text 1lm for the medical domain. ar arx preprint ar XrXi:2404.006113 2024.
German
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arviv preprint ar Xix::712..05557, 2017.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. Advances in neural information processing systems, 34:27131-27144 2021.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang. User-level differential privacy with few examples per user. Advances in Neural Information Processing Systems, 36, 2024.
Jesse Harte, Wouter Zorgdrager, Panos Louridas, Asterios Katsifodimos, Dietmar Jannach, and Marios Fragkoulis. Leveraging large language models for sequential recommendation. In Proceedings of the 17th ACM Conference Recommender Systems, 2023.
Yihuai Hong, Yuelin Zou, Lijie Hu, Ziqian Zeng, Di Wang, and Haiqin Yang. Dissecting fine-tuning unlearning in large language models. In Proceedings of the 2024 Conference on Empirical Methods Natural Language Processing, pp. 1933-3941, 2024.
Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. 2012.
Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM SIGMOD- SIGACT-SIGAL Symposium on Principles of Database Systems, pp. 227-236, 2022.
Lijie Hu, Ivan Habernal, Lei Shen, and Di Wang. Differentially private natural language mod- els: Recent advances and future directions. In Findings of the Association for Computational Linguistics: EACL 2024, pp. 478-499, 2024.
Tianhao Huang. Tao Yang, Ivan Habernal, Lijie Hu, and Di Wang. Private language models via truncated laplacian mechanism. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 3980-3993, 2024.
Majeed Kazemitabaar, Runlong Ye, Xiaoning Wang, Austin Zachary Henley, Paul Denny, Michelle Craig, and Tovi Grossman. Codeaid: Evaluating classroom deployment of an Ilmebased programming assistant that balances student and educator needs. In Proceedings of the CHI Conference on Human Factors in Computing Systems, pp. 1-20, 2024.
Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. Advances in Neural Information Processing Systems, 34:12466-12479, 2021.
Haoran Li, Dadi Guo, Wei Fan, Mingshi Xu, Jie Huang, Fanpu Meng, and Yangqiu Song. Multi-step jailbreaking privacy attacks on chatgpt. ar preprint ar arXto:2304.05197 2023.
Daogao Liu and Hilal Asi. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates. In International Conference on Artificial Intelligence and Statistics, pp. 4240 4248. PMLR, 2024a.
11

---

Published as a conference paper at COLM 2025
Daogao Liu and Hilal Asi. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates. In International Conference on Artificial Intelligence and Statistics, pp. 1240-4245 PMLR, 2024b.
R Duncan Luce. Individual choice behavior, volume 4. Wiley New York, 1959.
Hanjia Lyu, Song Jiang, Hanqing Zeng, Yinglong Xia, Qifan Wang, Si Zhang, Ren Chen, Christopher Leung, Jiajie Tang, and Jiebo Luo. LIm-rec: Personalized recommendation via prompting large language models. arviv preprint ar ar 15780, 2023.
Andrew Maas, Raymond E Daly, Peter Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguisfics: Human languag technologies, pp- 142-150, 2011.
Daye Nam, Andrew Macvean, Vincent Hellendoorn, Bogdan Vasilescu, and Brad Myers. Using an Ilm to help with code understanding. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, pp- 1-13, 2024.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 00127730-277442 2022.
Robin L Plackett. The analysis of permutations, Journal of the Royal Statistical Society Series C: Applied Statistics, 24(2):193-22 202, 1975.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
Steven Ross, Fernando Martinez, Stephanie Houde, Michael Muller, and Justin Weisz.
The programmer's 's assistant: Conversational interaction with large language model for software development. In Proceedings of the 28th International Conference on Intelligent User Interfaces, Pp. 491-514, 2023.
Nihar B Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramch, Martin Wainwright, et al. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. Journal of Machine Learning Research, 17(58):1-47, 2016.
Hanpu Shen, Cheng-Long Wang, Zihang Xiang, Yiming Ying, and Di Wang. Differ- entially private non-convex learning for multi-layer neural networks. arXiv preprint a<Xiv:2310.08425, 2023.
Daniel Shin, Anca D Dragan, and Daniel S Brown. Benchmarks and algorithms for offline preference-based reward learning. arXiv preprint arXiv:2301.01332 2023.
Jinyan Su, Lijie Hu, and Di Wang. Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research, 25 2024. 2024.
Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Álexandre Ramé, et al. Gemma 2: Improving open language models at a practical size, 2024. URL htllps//aaxxi.. org/abs/2408.00111 001188 1(3), 2024.
Noel Teku, Fengwei Tian, Payel Bhattacharjee, Souradip Chakraborty, Amrit Singh Bedi, and Ravi Tandon. Aligning large language models with preference privacy. 2025. URL https://openreviers net/ dfmmmmi@ffnmmmIJ....
Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature medicine, 29(3):1930-194) 2023.
12

---

Published as a conference paper at COLM 2025
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajiwal Bhargava, Shruti Bhosale, et Llama Open foundation and fine-tuned chat models. arXiv preprint (XXi::2077009288. 2023.
Michael Völske, Martin Potthast, Shahbaz Syed, and Benno Stein. TI; dr: Mining reddit to learn automatic summarization. In Proceedings of the Workshop on New Frontiers in Summmarization, pp. 59 59-63, 2017.
Di Wang and Jinhui Xu. Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1182-1189, 2019.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp. 6526- 6535. PMLR, 2019.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline Il with linear function approximation? arXiv preprint #rXio:2010.11895, 2020.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American stalistical association, 60(309):63-69) 1965.
Fan Wu, Huseyin Inan, Arturs Backurs, Varun Chandrasekaran, Janardhan Kulkarni, and Robert Sim. Privately aligning language models with reinforcement learning. ar Xiv preprint ar drXio:2310.16966 2023a.
Yiquan Wu, Siying Zhou, Yifei Liu, Weiming Lu, Xiaozhong Liu, Yating Zhang, Changlong Sun, Fei Wu, and Kun Kuang. Precedent-enhanced legal judgment prediction with Ilm and domain-model collaboration. arviv preprint ar Xrxo::2310.02211, 2023b.
Hanshen Xiao, Zihang Xiang, Di Wang, and Srinivas Devadas. A theory to instruct differentially--rivaal learning via clipping bias reduction. In 2023 IEEE Symposium Security and Privacy (SP), pp. 2170-2189. IEEE, 2023.
Biwei Yan, Kun Li, Minghui Xu, Yueyan Dong, Yue Zhang, Zhaochun Ren, and Xiuzhen Cheng. On protecting the data privacy of large language models (Ilms): A survey. ar Xiv preprint Xix:2403.000 05156, 2024.
Shu Yang, Muhammad Asif Ali, Lu Yu, Lijie Hu, and Di Wang. Model autophagy analysis to explicate self-consumption within human-ai interactions. In First Conference on Language Modeling.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline rein- forcement learning with linear representation: Leveraging variance information with pessimism. arx preprint ar xxXi::2003.05804, 2022.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. ar Xie preprint ar arXic:2110.06500, 2021.
Dong Yuan, Eti Rastogi, Gautam Naik, Sree Prasanna Rajagopal, Sagar Goyal, Fen Zhao, Bharath Chintagunta, and Jeff Ward. A continued pretrained Ilm approach for automatic medical note generation. Xiv preprint wrXim:2403.09057 2024.
Zhuoran Zhang, Yongxiang Li, Zijian Kan, Keyuan Cheng, Lijie Hu, and Di Wang. Locate-then-ediit for multi-hop factual recall under knowledge editing. Xiv preprint ar arXit:2410.06331, 2024.
13

---

Published as a conference paper at COLM 2025
Puning Zhao, Lifeng Lai, Li Shen, Qingming Li, Jiafei Wu, and Zhe Liu. A huber loss minimization approach to mean estimation under user-level differential privacy. arXio preprint ar 3tt::2405.134555 2024.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In International Conference on Machine Learning. PMLR, 2023.
A Additional Experiment Details
*: Ad--ua
Divergence
furden hazenz minas miaey
Reward
Reward
1.4
12-
LEP pe.e in Group Insaaty
20
KL Divergence
timestep
timestep
K.P sue Orag Frvets
235
KL Divergence
200
2.50
Reward
Reward
ALMII not GrEup Francy
Group Prascy
KL Divergence
timestep
timestep
(b) 8
Figure 3: IMDb Sentiment Generation (Llama-2-7)).
Ru Uss vis D7S00 doeg Rivssy
Usar de DPSCD Grea hhbry
KL Divergence
Reward
1.-
Reward
22-
DEeriiE DEFCD
20
KL Divergence
timestep
timestep
(a)
AUH-U tsaee la
KL Divergence
Beathher
Reward
Reward
2.
56
KL Divergence
timestep
timestep
(b)
Figure 4: IMDb Sentiment Generation (Gemma-2-2b).
14

---

Published as a conference paper at COLM 2025
A.1 IMDb Sentiment Experiment Details
follow the setup in Rafailov et al. (2024), where prefix prompts are sampled between 2 to 8 tokens. For reward model training, we cardi /t settt-bas-seettmeeeeeee a backbone model trained on Twitter data, which is further fine-tuned on IMDb sen- timent analysis by updating the last layer only. Llama-2-7b and Gemma-2-2b serve as the base models. While each method fine-tunes the base models using its respec- tive reward model, test performance is evaluated using a ground-truth reward model, siebert/
laaerta-lrreeeennliiis english, ensuring fair comparison. On every 10 steps until convergence, we report the rewards and KL-divergence over a set of test prompts, shown in Fig and Fig 4.
Parameter
Gemma-2-2B
Llama-2-7B
Batch Size
4
Learning Rate
1e-4
1e-4
Warmup Ratios
0.1
0.1
Learning Rate Scheduler
Cosine
Cosine
Optimizer
AdamW
AdamW
Training Epochs
1
LoRA Rank
LoRA Alpha
32
32
Table 3: Parameter settings for Supervised Fine-Tuning (SFT) on Gemma-2-2B and Llama-2- 7B.
Parameter
Gemma-2B
Llama-2-7B
Batch Size
64
Mini-batch Size
64
64
Learning Rate
le-5
1e-5
Optimizer
RMSProp
RMSProp
KL Penalty Coefficient
0.15
0.15
LoRA Rank
16
16
LoRA Alpha
32
32
Table 4: PPO parameter settings for Gemma-2-2B and Llama-2-7B.
Parameter
AUP-RLHF
User-wise DPSGD
Group Privacy
Random Response
User Batch Size
50
50
N/A
N/A A
Per-user Sample Size
10
10
N/A
N/A A
Sample Batch Size
N/A
N/A
500
500
Learning Rate
1e-3
1e-3
le-3
1e-3
Warmup Ratios
0.2
0.2
0.2
0.2
Learning Rate Scheduler Epochs
Cosine
Cosine
Cosine
Cosine
5
5
5
5
Table 5: Reward model parameter settings for Gemma-2-2B and Llama-2-7B.
A.2 TL;DR Summarization
For reward model training, trained on Natural Language Inference, which further fine-tuned on summarization preference by updating the last layer only.
backbone model
15

---

Published as a conference paper at COLM 2025
AUT KLhF
38%
61%
AUP RUF
63%
37%
35%
65%
Auecodoee
56%
44%
Tandom
32%
6.76
fansor Sapeste:
43%
Noguise
Group
Group
47%
53%
96
100
20
40
(a)
(b) e
Figure 5: Win Rate Against the SFT Model for TL;DR Summarization (Gemma-2-22
Mn
Loss
Win
Loss
AUP-HLHI
AUP-RUHI
User wisa
92%
58%
User
30%
45%
DPSCD
DPSGD
Random
41%
59%
Random Response
49%
51%
Response
frivac
41%
59%
Mivac
52%
48%
20
60
100
20
40
80
100
% Win Rate
% Win Rate
(a) =
(b) E 8
Figure 6: Win Rate Against the SFT Model for TL,DR Summarization (Llama-2-7)).
A.3
Computational overhead
The main overhead of group privacy training methods introduced by the per-example gradient clipping and noise addition. For the user-wise DP-SGD and AUP-RLHE, the main overhead is from the user-wise data sampling(line in Algorithm 2), per-user gradient clipping(line 9 in Algorithm 4) or concentration scores computing(line 8 in Algorithm 2) and noise addition(line 15 Algorithm 2)
We report the average per-step training time (in seconds) for training the reward model using different methods, averaged over 100 steps 100 steps with batch size of 500 on the IMDb Sentiment Generation task.
Random Response
Group Privacy
User-wise DPSGD
AUP
Training Time
2.78
4.29
4.32
4.54
Table 6: Training time per step (seconds)
From the Table 6, we observe that AUP-RLHE incurs only little computational overhead compared to Group Privacy and User-wise DP-SGD. The relatively short training time of Random Response is due the absence of gradient clipping and noise addition.
A.4 Number of contributions per user
According to Theorem 5, when the number of users is fixed, larger results in smaller upper bound on the estimation error, leading to better utility.
To provide more quantitative analysis, present the following table showcasing the effect of varying. We conduct experiments on IMDb Sentiment Generation using Gemma-2 2B, following the same settings in Tables 3, and 5.
16

---

Published as a conference paper at COLM 2025
10
100
500
Reward KL divergence
0.6402
0.8582
0.8539
1.2671
0.6960
0.9071
0.7434
0.8800
Reward / KL divergence
0.9198
0.9461
1.1486
1.4399
Table 7: Effect of contribution number
As shown in the Table 7, We observe that as the user contribution m increases, the reward- to-KL divergence ratio improves at convergence, indicating that the model achieves better utility.
B
Other Details
B.1
Notions
Parameter
Meaning
Parameter
Meaning
Number of users
Contributions per
0
Reward model parameter
f
Ground-truth reward model parameter
d
Dimension of 0
Privacy budget
5
Failure probability
K
Number of candidate responses
Sigmoid function
Ty
Reward function parameterized by
Feature map
Differential feature vector
y
Human preference label
Randomized label
Σ
Covariance matrix
Ain
Minimum eigenvalue
Strong convexity parameter
Lipschitz constant
Bound on [|]
Coverage parameter Gradient clipping bound
Concentration threshold
C
Probability bound
Learning rate
T
Number of iterations
Batch size of users Distribution family
D
Dataset
P
S
Noise multiplier
A
Parameter difference
Table 8: Key notions in this paper
B.2 Algorithm
Algorithm AboveThresholdd
1: Input: Dataset D =(Z,...,22 ,.),, threshold A E R, privacy parameter e
2: Let Å = A - Lap (2)
3: for = to do
4: Receive new query 9: Z + IR
5: Sample v Lap
6:
if q: (D) + 14 < Â then
7:
Output: a; = 1
8:
Halt
9:
else
10:
Output: a; T
11:
end if
12: end for
17

---

Published as a conference paper at COLM 2025
Algorithm 4 User-wise DP-SGD
Input: Initial model weights tb, training set D of users and records, learning rate !/, iterations T, user batch size A, privacy budget e, number of records per user {
gradient norm bound C
2: < PRIVACYCOUNTING(e.,
T)
b> Compute noise multiplier > Prepare the dataset
3: (User-wise DP-SGD directly uses D)
4: for aar=11..... do
5: Randomly draw Ur batch of î users
6: for ,, do
7:
Sample 2, {
j Mj je(ss] k; records for the ith user in Ut
8:
81,1 - & Lje(s] V ((,
Compute user-averaged gradient
8ti - St.i/ max(1, (
9:
> Clip gradient
10:
end for
11:
81 < π Lic(n] 81,5 (2
b Aggregate and add noise Model update
12: 0r11 +- 01 18:
end for
B.3 De-biased loss function
We start with the BCE loss under randomized labels. Next, we discuss their drawback, which help us get intuition for a de-biased loss. For any R the predicted probabilities of randomized label Vi, given x as
Pl, = o(e)o (x1,0) + (1- o(e)) (1- - (xT,0)
P = (()) (1 (1-0 (z]] + (1-111 o(E))o (x,,0)
After applying random response to the dataset, it becomes D (i)) The MLE ÊLeE computed on this dataset satisfies user-level privacy and can be obtained by minimizing the BCE loss (the negative log- likelihoohhh)
m (0) ΣΣ
1 (ūr
1) log Pl, + ( 0) log pt
The drawback BCE loss with randomized labels is that it introduces bias in loss compared with clear-text loss E (8) , (f)] At the same time, this leads to discrepancy in the log-odds between the randomized dataset and the clear dataset, introducing bias in the preferences for a and n (Chowdhury et al., 2024b). This motivates us to design de-bias loss function that ensures the log-odds are identical between the randomized and clear datasets. The following loss achieves this:
(T) Σ
Σ
(ūi,
1) log pl, +1 (Vi, = 0) log pl,]
where we define, for any 0 Rd, the predicted scores of each randomized label Ji given x1 as
σ (x,,0) ((e)
(1 - (1-0 (x1, o(e)
(1-0 (((e)
(1-o(e))
(1- o [x]
(xTT
Although pl, and ph, are not probabilities, they satisfy our desired property:
18

---

Published as a conference paper at COLM 2025
P
logit (pt))
log
log
P.j - 0
x x
Hence, the loss function (0) essentially de-biases the effect of randomization.
B.4 Extension to K-wise
y) be the data structure of K-wise RLHF, where each sample has a state e S (e.g., prompt given to language model), K actions al ,..,, A (e.g., K responses from the language model), and label (1,2, ..., K} indicating which action is most preferred by human experts. We assume that the state first sampled from some fixed distribution The actions (a',..,,a )) are then sampled from some joint distribution (i.e., a behavior policy) μ conditioned on Under the Plackett-Luce model (Plackett, 1975; Luce, 1959), the label y is sampled according to the probability distribution:
Let
exp (rg. (s,az))
Pp ly = k s axl
Σ
exp
re- {,a;)
For the Plackett-Luce (PL) model Plackett (1975); Luce (1959) for K-wise comparisons between actions, let TI be the set of all permutations π : [K] + [],, which denotes the ranking of K actions, where (x(() denotes the j-th ranked action. Under the PL model, we define the loss of a permutation
II for a state
exp (re s, (s,ax()))
2(0;s, πt) = log
LV exp rro (s, (s,ax(x)))
Theorem 5. Under the same setting of Theorem 4, the output of Algorithm with loss function E(0;s, πt) salisfies
K2L
1
vd Vmne
E - 0r S Ō
KY
mn
The Big-Ö notation omits other logarithmic terms.
Remark 3. When K = 2 or K = 0(1), the PL model reduces to the pairwise comparison considered in the BTL model, yielding the same utility as Theorem
B.5 Lower Bound of User-level DP-RLHF
On the other side, we will study the lower bound of the estimation error for user-level DP-RLHF. Consider a family of distributions P over (x'')", where X' represents the data universe, denotes the sample size, and refers the user size. Our goal to estimate parameter 6, which is mapping 0: P - @ that characterizes the underlying distribution. To quantify the estimation error, we define a pseudo-metric p x O - R+, which serves as the loss function for evaluating the accuracy of the estimate. The minimax risk under the loss function p for the class P is given by:
R(P,p) == min max Ex-p(p(((x),
PCP
In the following, we focus estimating an unknown parameter 0, within the BTL model under a use-level privacy framework. Data collected from users, where each user provides samples. We consider a fixed design setup, meaning that the feature vectors X1, Rd for samples E [n] from user j [m] are known. Our objective to infer based on sequence of private responses Øi.--
19

---

Published as a conference paper at COLM 2025
Theorem 6. For a large enough n, m, any prioate estimator @ based on samples form the BTL model that satisfies (e, -us---err-eeee-llaee DP has the estimation error lower bounded as
E 0 20
001
d Vu
vd
Vmn(e= 8)
Remark 4. The estimation bound in Theorem 6 consists of two components: a non-private term and a private term. Compared to the item-level setting in Chowdhury et al. (2024b), both the non-private and the private terms include an additional factor of 1/vm. In particu- lar, when m = 1, our results reduce to those in Chowdhury et al. (2024b), demonstrating consistency and generality with their findings.
C Omitted Proofs
C.1 Proof of Theorem 1
Proof. We follow the proof method of Theorem 4.2 in Chowdhury et al. (2024b) to prove the sub-optimality of the random response algorithm at user-level setting. First recall from our de-biased loss function
1 nm
IK
(D)(0)
107 =) (o(e/m)logott xz,) (1 (0emo((mm -0((- oo xx,)))
+1 =) 0) (a(e/m) log(1 -orgg xx,)) (1 (100((mmm))ll0( xzj)
The gradient of the loss function is given by
VID
1
m E
Vej.j X1.
x Va.
mm
nm
where
(00OTTx xij)
o'(0Txx x(j)x
Voli
1(bt, =1
(8)) +
(1 (Ee)
x(T
1 o(0Tx ((Tx)
m
o'(0 ((Txx))) xzj))
d'OTTxp xii)
11(1 0)
(E))
(1
E
1-0 x11))
o(0 xx,)
m
holds that
(o'(0Txxs) xx))xy) ((()Tx,))
o'( (10Txz,))
Eo Ee[Vesslx, = (0(0Tx
(1-o(() xxx))))) (1--0)))
o(e/m)
o(e/m))
1 100 x1,)
d'0 d(0Tx))))
x(OTxxn))
-(1-0(00xx,))) (.)))(emm)++) +o (1,)(1- - -((e/))))
((e/m)-- + o(0 xij))
(1 (1-o(t/m)) =
o(00xx)) xij)
x(xxx;))
Furthermore, we have
d'0 ((e/m) + 1- a(8 x1,j)
o'(0Txii) Xi,j
[Verjl a(8Tx:)) xi,))
(1 o(e/m)),
d' (8TTxxx) x1,1)
d'(8 xiji)
(Ve Bu 1 o(f xiji)
(e/m))+
(1 - o(e/m)).
o xiji
The first derivative of the logistic function o(.) is given by d'(z) = o(2) o(z)), which gives us
VV bi. 1 (1 (1-o(0 xx)))o((/m)) + o(e (1- =t) = Polo: =0,x,]]
20

---

Published as a conference paper at COLM 2025
| a(0
o(0 xty)o((/m) + (1- o00" (1=))(0) (10((1(mmm))) Polii, 1|x,,]-
Therefore, it holds that Vaj.j is zero-mean and sub-Gaussian under the conditional distribution Pel-|xz,y]-
Now the Hessian of the loss function is given by
b))x(0)) m:: ΣΣ
1 100h= 1) (11-ofeem)) x(,)) - -(ee/m) xxs)
+1 = 0) (l-ooe/m))V22og xi,)) o(e/mm/m
log(1 o(0 x(,)))]
where
V logo(( xij)= d0 x1)) (0) x1,))
o' d0T xij)2 xi,j
o(0) x;,)
log(1 o00 x1;))) = d' xt,) a(0) xi,j)) + d' xzj)2 x1,
(1 o(0 xi,i )2
Now the second derivative of the logistic function (--) is given by o² = d') -20(2)), which gives us
2 log x1,)) v log(1 - a00 xij)) = o x1,
Hence, the Hessian of the loss function takes the form
(0) = 1
10r = 1)((0(e/m)) 1))d (0 xi,)) + (Brj (2)( 1)00 ()Tx(( x1s2i.
Now, under Assumption 1, observe that d'(0Txx x;) 2 y for all 0 E θB, where y -expp_22B8)-epppi This implies that In is Ye := 7(20(e/m) - 1) strongly convex in Og for all > with respect the semi-norm. Since 0" E Og, introducing the error vector åR 8*, we conclude that
7e A E
<
VIDa (0+)
12 Ip
|
Introducing M = X we now have
VVD,, ا = VØ. MVg. Then, the Bern-
7/
stein's inequality for sub-Gaussian random variables quadratic form (see e.g. Theorem 2.1 in Hsu et al. (2012)) implies that with probability at least a,
Vina (0*)
2 Ez!
MVp <²² (T(M) + 2 tr(M M)log(1/a)) + M|| log(1/a)
+ log(1/a)
< C 12. v2
nm
For some C > This gives us
TellAllE & ViD
& VG..0 .G..02.
d+ (+ogg(1/a) (1/a)
Solving for the above inequality, we get
D2
d log(1/a)
Al|E < C2.
CC
V
T/
nm
for some constant C2 > Now note that
x.
1.e c/m
1
Hence, we get
7
7
erim
C.
f/m m +
d + log 1/a)
||0RR - 0- 01112 <
nm
21

---

Published as a conference paper at COLM 2025
Equivalently
C
e
d log (1/a)
|RR
0011
YV Amin (Ep)
et/m
for some C > which holds for any o0). This completes our proof.
C.2
Proof of Theorem 3
Proof. As the subsets Dj are disjoint. It is sufficient to show Algorithm 2 is (e, user-level (label) DP.
To prove the privacy guarantee, note that there are two components related to privacy in each iteration of Algorithm 2, the 10-15). For the AboveTTrreshoke as the query st. Thus, by Dwork et al. (2014), we can see will be S-DP for T iterations in total. Thus, it is sufficient for show steps 10-15 are ($ -user-ellll (label) DP.
(step 9) and private mean oracle (step
Since it consists of T-folds, we first recall the advanced composition theorem Dwork et al. (2014).
Lemma (Advanced Composition Theorem Dwork et (2014)). Given target privacy parameters 0 < e < 1 and 0 < 8 < 1, to ensure (e, (8' + 8)-DP over T mechanisms, it suffices that and 8' 4
each mechanism is (e', -DD,, where e' 2V/21m(2/5)
Thus, we have to show each iteration satisfies (E',8')-DP, where e' 4 222T11(2/8) and 8 8
We then recall the following privacy amplification via Poison subsampling.
Lemma ((Bassily et al., 2014; Beimel et al., 2010)). Let A be (e algorithm. Now we construct the algorithm as follows: On input D {x,, sub-sampled dalaset D5 where each x; E D4 with probability q. Then we run algorithm A on the dataset Ds. Then BDD) A(Ds) is (E, where Ě = O(ge) and ő qo.
b, first we construct a new
Note that when there is no subsampling, i.e., the batch size is n. Then when S O( /Tin(1/8) ), it will be the private mean oracle as in Liu & Asi (2024b). Thus, it will
be (E', Jes-ueerll (label) DP and the T-fold composition is uesereuser-level (label) DP.
Thus, when there is Poison subsampling with the probability & the whole algorithm (step 10-15) will be (O e),, ( -ueer-lell (label) DP. That is when we take & Ō /Tln(1/8) ), it will be (e',8') -userrlvll (label)DP and the T-fold composition is (e, 8) du-eser-leeel (label) DP.
C.3 Proof of Theorem 4
We begin with the definition of Lipschitz continues and strongly convexity. Definition 4. (Lipschitz Continuity) A function f IR" + R is said to be Lipschitz continuous with constant if there exists a constant L 2 0 such that for all x, E R"
[If(x) - f(y)ll < L||x-
where || denotes the norm in R" (typically the Euclidean norm).
Definition 5. (Strong Convexity) function : IR" - RR is said to be strongly convex with parameter μ >> if there exists a constant μ such that for all x, E IR", we have:
f(y) > f(x) + Vf(x) x) lly x||
where μ is the strong convexity parameter.
22

---

Published as a conference paper at COLM 2025
We can when use the full batch in Algorithm 2, i.e,, ñi n,, based on our parameters, Algorithm will be the same as the method in Liu & Asi (2024b) for DP-SCO with strongly convex loss in the user-level DP setting. Specifically, we have the following result by Theorem 4.11 in Liu & Asi (2024b)
Lemma 3 (Derived by Theorem 4.11 in Liu & Asi (2024b)). For 0 < & < 10,0 8 1, if the population loss function
(dl (d (o 1} log 100 x) I[ 0) log - o(0 xy-strongly convex and 4L-Lipschitz continuous, under the same parameters in Theorem 4, Algorithmm outputs such that
(0) Espp()),
L2 NY
(
dlog (ndm/d)
E
Lp
min LP (0*) 0 pre0
+
nm
n2me?
Thus, it is sufficient for us to show that population loss function is ry-strongly convex and 4L-Lipschitz continuous under Assumption 1 and 2.
Proof of Theorem 4 By strongly convexity, we have
2 IE [p)((0)) Trp (07)
E| E|10
0-112
kY
L2
1
d log (ndmi/d
x2
nm
m2me²
The second inequality comes from Lemma 3. Lemma 4. Under Assumption 1 and 2, the loss function
(0) = Es-p((), (f ((())))=((ss)) 1} log logo (0=x)) + I[y = 0} log(1 o(0 x))
is syy-strongly contex and 4L-Lipschitz continuous.
Proof of Lemma 4. Lipschitz continuous
The gradient of the loss function is given by
(0) E s.-p()), [Vxx]
where
V I(y 1} d'00xx
d'(0xx)
Ily = 0} - 0
x(0xx)
Furthermore, we have
Vely d(0"x)
= 1 - 000 x) < 1.
x(0Tx)
VVoly < 1.
Therefore, by Assumption 1, holds that
[V), < Vol |x| < 4L
This means (0) is 4L Lipschitz continuous Strongly convex Now, the Hessian of the loss function is given by
(0) = =E (e ((9a)))(((1)) [(y = 100'(00x)) 0) xxx
23

---

Published as a conference paper at COLM 2025
observe that o'(0x) y for all 0 OR where
1
= + exp(eepp220 (xP(-)LB) exp(2LB)
by Assumption 2,
- lv)pp xy||u|12.
This implies that 1, xy-strongly convex in ØB.
C.4 Proof of Theorem 5
We follow the proof of Theorem 4. First, we demonstrate that the objective loss function Cp πt) is ry-strongly convex and 2LK2-Lipschitz continuous. Then, with the help of the lemma 3, the proof is completed.
Lemma We define Lp(0, π) s-pp)) (4)m,)))=- (0;s,
π). Under Assumptiio and 2, (0 πt) is xy--srongly convex and 2LK Lipschitz continuous, where "r exp(-4LB)/2.
Proof of Lemma Let be state and A1...., ag be K actions to be compared at that state. Let the label/ preference feedback y E {1,2,..., K} indicate which action is most preferred by the human labeler. Let
Xij ((, -(,,)))))sss))))))
i
be the feature difference between a a; and a, at state s. Define the population covariance matrix
E E Expp(()) (x [3,%%)]
Assumption (Coverage of feature space) The data distributions p, 1 are such that
Amin (En)) 2 k for some constant x > 0 for all i K.
(xp((0,p(s)) (())))
{(0) =
log
- exp( ((, (x1))))
Strongly convexity of (e, (folllw Proof of Theorem 4.1 in Zhu et al. (2023))
The Hessian of the negative log likelihood can be written
K (A, (()) + ((5
exp
#T()) (_ exp (0, (18,((s.0n(()))))
(p(), (((.
k
Since exp((.1)) E [exp(- 1 LBB), exp((.B)) we know that the coefficients satisfy
exp (0, p(s, (((5))
2
21K1--1 j)?
Σ exp ((0,0(s, ((x))s))x(()))))
y exp-=xxxpBBBB// We can verify that for any vector E RK one has
K T
Σ
((s,Ax()) -((,sa))))))))) ((( -
K=kk
24

---

Published as a conference paper at COLM 2025
K
K
K Σ
2 Eyu
min π)]](K) (K 1)?
Σ
(x()) o (x()))
xx 2
The last inequality uses Assumption 3.
So, (0, πt) is xy-strongly convex with respect to f2-norm.
Lipschitz continuous The gradient of the negative log likelihood is
exp ((0.0) (s, (s,
Ve(0,
(o (s.Ar1i)) -p
(0(s))0((((s)))))) (s,
exp (00.0) s, (,(x)()))) )))
We set xik @ a)) 4 (s) X 1)/2)= has the differencing vector Xj its (k + (K+E*=Kj+t) Li=K-j+1 th row. We also define Vjx to be the random variable of the coefficient of xj in equation above under the PL model, iee, conditioned on arbitrary permutation
(xp(((.)(sAA)))
if 7)) <
<
( expl (0,0) (B0( (())))))) exp( (AA())))))
V
otherwise.
1(8) exp 0.00 m())))
(k) means that the j-th item ranks higher than the k-th item. Let V E IRK(K-1) 1)/2 be the concatenated random vector of [Vih<s<< Furthermore, since under any permutation, the sum of the absolute value of each element in V is at most K. Thus,
Here, πt (f)
|VE(0, v xx < | VI2 < 4
Thus, (l is 2K continuous, and (p πt) is also L- continu- ous.
The rest of the iroof is the same as that of Theorem 4.
C.5 Proof of Theorem 6
To establish our lower bounds, begin by introducing key background concepts, notations, and properties. Consider a family of distributions P over (Xr")", where X' represents the data universe, denotes the sample size, and и refers to the user size. Our goal is to estimate a parameter 0, which is a mapping 0 P -> that characterizes the underlying distribution.
To quantify the estimation error, we define a pseudo-metric p: + θ + R which serves as the loss function for evaluating the accuracy of the estimate. The minimax risk under the loss function p for the class P is given by:
R(P,p) min max Ex-p(p(((X),
à PCP
In this study, we focus estimating unknown parameter, 6, within the Bradley-Terry- Luce model under a use-level privacy framework. Data collected from n users, where each user provides samples. We consider fixed design setup, meaning that the feature
25

---

Published as a conference paper at COLM 2025
vectors x E R for samples é [n| from user j [m]] are predetermined and known. Our objective is to infer 0 based sequence of private responses yi,j-
Without privacy constraints, responses yij follow logistic model:
IP (yi, 1 x = (0 xi,)) + exp x,,)
1
P P(V.. = xi,)) =1 - 0 (0 Xi,i
We refer to this distribution family as Pg. Under the use-level privacy constraint, our goal is to construct an estimator è that closely approximates 0 while preserving use-level-label differential privacy, ensuring that an entire user's labels remain protected. Depending on the estimation framework, the loss function p is defined either the squared æ--norm squared semi-norm.
Lemma (Assouad's s lemma Chowdhury et al. (2024b)). Let = (P)" set of distributions indexed by the hypercube & = {i1]d. Suppose there exists a T E R and a > O, such that satisfies: Ed, (w)) (P))) 2 2T L 1 (Nj + v;) and (ii) p (0 (Pu) ( (P.)) < a (p (0 (Pa), , (Px)) + (0 (P)) , (Pw) )), i.e, a-triangle inequality, For each [d], define the
(i) for all u,
mixture distributions:
2
P+ = Ed
Σ
Pe and P-;:=
Σ
Pe-
EEal eEE
eEE
Then, we have
d -
R(P, Z
(1
2x 1=1
Corollary 2. Under the same conditions of Lemma 6, we have
1/27
R(P, p) 2 dr
1
d 1 2
Σ ecCa
1Pe
Pe
lltvv
2a
d
where el is vector in Ea that flips the i-th coordinate of
Lemma 7 (Assouad's lemma Chowdhury et al. (2024b)). Let the same conditions of Lemma 6
hold. for all E (d), there exists a coupling (x, Y) between P+; and P-; with E [dHam (X, Y) S D
for some D 2 0, then
dr R(P,p,E,0) 2 (0.9c 10eD 10D6)
2x
1 Fact 1. Let Pa = H and pb Ite5 Then, the sum of KL-divergences between the corresponding Bernoulli distributions satisfies:
kl (pollpb) + kl (pollp.) S (a ()-
where kl(pl) represents the KL-divergence between Bernoulli distributions with parameters p and q DKL (Bernoulll(()) Bernoulligg)..
Proof of Fact 1. By direct calculation, the sum of KL-divergences simplifies to:
kl (pallpb) + kl (Pollpa) (Pa Pb) log
Pa
1
Pb
i- Pa
1
pb
From the definitions of pa and Pb. we substitute:
(pa - Pb) log (
Pu
1-Pb
1-
Pbb
Pb
1
1 1
(b a).
1 Pa
Pb
1 co
Now, assuming without loss of generality that b 2 a, we bound the difference:
1
1
b ea 1 c
1 aa
1 eb
e
26

---

Published as a conference paper at COLM 2025
Using the inequality e²h 2 + (a - b), we obtain:
1 e_ S b - a.
Thus, combining these results gives the final bound:
kl (pallpb) + kl (pollpa) (a
This completes the proof.
Now, we proceed to prove Theorem 6, which we break down into two parts: the non-private component and the private component.
Non-private component. We begin by selecting a parameter A >> 0 and defining 0, = Ae for each e E Eg {=1} Each Pe is probability distribution associated with specific vector e E &g. This means that for every binary vector e = (e1, ea),, there is a corresponding probability distribution P.- Since we consider each user provides m samples, thus here P m-prrouuct distribution. Our goal is verify the two conditions stated in Lemma 6.
First, we observe that the function p || 113 adheres to the 2-triangle inequality, meaning a = 2. Additionally, for any u, v E Ed, the squared norm difference satisfies
0 0011 4A2
1 (ui 0;),
indicating that r = 2A2. Now, let P" represent the distribution corresponding to inde- pendent samples from m users of the (non-private) observations Vi, when 6.. Then, by applying Corollary 2, we obtain
dA2 2
d d
1/2
R p 11 e,,,,5 2 R P 8m 11 11311
-
Σ EEE
Pe
PR
2
Using Pinsker's ss inequality along with the chain rule for KL-divergence, we obtain the following bound by bounding the total variation (TV) distance for any 11, E Ed.
PP
P 1i - 4
(DeL (PHIIPE) + DKL (PTII
Σ
kl Pu (xki))
1| (xhi)) + kl (po (Xh.i) 1l (x..)
))
Next, applying Fact 1, we derive an upper bound on the total variation distance:
(z ())( 0))2
|P 1 PM
4
Moreover, we have
1
A 4d 2d
m
R
PH
PI
<
Σ
2x
d2d
EEE,
Rewriting in terms of the Frobenius norm,
PM - pd 1 3E
22 2
A2
Σ
Σ rEEp
||
d2d 1
TV
2
Here, X E R represents the aggregated data matrix, where each row x E Rd corre-
sponds to a sample from user j, and we derive the following lower bound:
|| denotes the Frobenius norm. Using this bound,
2
2
1/2
R
8m .l 1122,,,))
X
2
d
27

---

Here, D represents upper bound on the expected Hamming distance between (X, Y), where (x, Y) is a coupling of PH and P Our next step is to determine an appropriate bound for D, which requires analyzing the expected Hamming distance between these Published as a conference paper at COLM 2025
To optimize the bound, we set:
d
A2
4 X
which simplifies the expression to:
d2
R
mm |l
11 e,
16 16
amm
-=
Xk,
Given the assumption that xxu|| - L.2, we further refine the bound as:
R (P |l (2,,, 2 Ω (
12
Now we consider the Private component. Similar to the non-private part, we verify A, 8e, p. Since we consider user-level privacy, we will assume p is an m-product distribution. Applying Lemma 6, we obtain the following lower bound:
dA2
( pe .1 {,,
2
(0.9e -000))
2
By using the fact that
2 1+ + x, we further derive:
dA2
R
Pg Ro
12 12,,,0 2
(0.9 - 10D(+++
2
two product distributions. For a lower bound, it suffices to consider Xtj = x E RR where ||x||0> S for all k [n].j E [m]. Applying the standard result on maximal coupling, we obtain:
E Hd (X, Y) n || P-illTV
Using above and the joint convexity of TV distance, we derive:
|P+ P-ll =
Σ 3EE.
Potti Pe.-i
EE
TV
Σ
|| - Pa, Pr,-illTV
Eal
PEE
max
|P Pe,-ilITv
eEEareid
max ecEpic|d]
| - PollTV-
Here, 전i represents a modified version of where its i-th coordinate is flipped. Applying Pinsker's inequality for any i e [d], we obtain:
P: - Pa < (DKL (PellPg) + DKL (PellPg) S mA2
The last inequality follows from Fact 1, the assumption that ||*||>> < 1 and the conclusion in Levy al. (2021). Combining these results, we establish
E [d (X, Y) = n [P+ - P-illTv S Vmn = D.
With the derived value of D, we now arrive the following lower bound:
2
pp@m pm
-12,,, >
(0.9 10 + +)).
2
28

---

Published as a conference paper at COLM 2025
To optimize this bound, we select
0.04
A
Vmn(e + 6)
Substituting this choice into the expression, we obtain:
R (P8" mm || (B2,, 2 mn² + 5)2²
d
for some universal constant Finally, combining this result with the non-private case completes the proof.
29


Reviews:
[{"review_id": "XaNrbzt2xt", "reviewer": "Reviewer_1im1", "summary": "- Quality and clarity: this paper proposes AUP-RLHF algorithm that integrates user-level label differential privacy into RLHF. It contains theoretical analysis for upper and lower bounds; as well as empirical experiment on PPO for sentiment and summarization tasks. The content is rich and clear.\n\n- Originality: It applies the existing user-level private mean estimation on DP-SGD for the new task of user preference label privacy protection and derives bounds for preference label DP.\n\n- Significance: this paper focuses on protecting user preference label on pair-wise preference data. It is a first attempt to protect this type of preference privacy.", "questions": "", "limitations": "", "rating": 7, "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": "- Clear writing with both theoretical analysis for bounds and empirical results.\n- New task of user preference label privacy protection.", "reasons_to_reject": "- Based on existing user-level DP methods; some small modifications to adapt to new objective (algorithm-wise).", "questions_to_authors": "Could you provide more explanations for how you conduct experiments for user preference label protection, for example how well is the preference label protected (what is the baseline) (and the case without DP)? What does timestep mean in Figure 4?", "extra_scores": {}}, {"review_id": "gatYHt6b57", "reviewer": "Reviewer_c7jp", "summary": "This paper presents AUP-RLHF, a framework to ensure user-level label differential privacy in reinforcement learning from human feedback (RLHF), addressing a gap in current methods which mostly focus on item-level privacy. The authors provide a theoretical analysis, including a lower bound for user-level DP-RLHF and a provably tighter upper bound for their proposed method’s estimation error. The algorithm uses adaptive sampling and gradient concentration techniques to reduce noise while preserving privacy. Empirical results on IMDB sentiment generation and TL;DR summarization tasks demonstrate strong performance over existing baselines. Overall, the paper addresses an important and underexplored problem with a thoughtful approach and it is technically sound.", "questions": "", "limitations": "", "rating": 4, "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": "This paper tackles an important and timely problem in aligning large language models with human preferences while preserving user-level privacy—an area with growing practical relevance and limited prior work. The proposed AUP-RLHF framework is novel in its integration of adaptive sampling and gradient concentration into DP-SGD for RLHF, and it is supported by both theoretical guarantees and empirical improvements over existing user-level DP baselines.", "reasons_to_reject": "While the paper addresses an important problem and offers a novel algorithm, several concerns limit its readiness for publication. First, the theoretical analysis, while rigorous, relies on strong assumptions, which may not hold in practice. Second, the empirical validation is limited in scope, using small-scale datasets and relatively simple tasks, making it unclear how well the method generalizes to more practical or large-scale RLHF settings. Third, the practical feasibility of the adaptive concentration mechanism is not thoroughly evaluated in terms of computational overhead or stability. Lastly, the overall utility gains over baselines are modest and may not justify the additional algorithmic complexity in real-world applications.", "questions_to_authors": "1. Can authors clarify the computational overhead introduced by the adaptive concentration mechanism in AUP-RLHF compared to standard DP-SGD or RR-based approaches?\n2. How sensitive is the performance of AUP-RLHF to the choice of hyperparameters?\n3. Do the authors have empirical results on how AUP-RLHF performs in large-scale or more diverse RLHF tasks?", "extra_scores": {"ethics_concerns_details": "NA"}}, {"review_id": "2lOjGttDCE", "reviewer": "Reviewer_yUzC", "summary": "This paper applies differential privacy (DP) to reinforcement learning with human feedback (RLHF) from the perspective of protecting all of the labels for a user rather just individual users. This is more challenging that label-level (DP) as all of the data from a specific user provides more revealing information to a potentially snooper. The paper provides a theoretical deep-dive into the solution, which is further supported by experiments on two datasets.", "questions": "", "limitations": "", "rating": 7, "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": "Preference-learning is being increasing applied to align large models, including models already deployed to the general public for wide spread use. Guaranteeing the privacy of users via their feedback is important.\n\nMany papers that focus on theoretical privacy guarantees for preference learning require overly simplifying assumption to be practically useful, such as the form of model that can be applied. Here the authors demonstrate application on reasonably sized language models.", "reasons_to_reject": "Algorithm 2 -- Line 12:  a user is removed if they are considered an outlier. Does this mean that there are users for which the model cannot be aligned? Specifically, if the data for those users are effectively removed then the model cannot be adapted to them. Might this be problematic in the context of bias, where sub-populations of users might be harmed because their preferences are ignored?", "questions_to_authors": "It would be useful to quantify the performance improvements at the end of the abstract.\n\nLine 42: end the sentence at \"user privacy\". Adding \"by introducing noise into the data\" is just repeating the earlier part of the sentence.\n\nLines 64-66: What in particular is \"sufficiently small\"? I cannot tell if it is the SGD update steps, the noise add, or the concentration parameters.\n\nLine 68: \"which outperforms well\" should be \"which performs well\".\n\nLine 245: sigma is used to represent the noise, whereas earlier it was used to denote the sigmoid function in the Bradley-Terry model. Symbols should have a specific meaning in the paper to ensure there is no ambiguity.\n\nLine 256: log appears twice when setting k, is this intentional?\n\nLine 285: Will using GPT-4 as a proxy for humans mean the model will best to users that are most like GPT-4?\n\nLine 296: Reorder the references to the figures so that they are in order (currently Figure 1, 4, 3).\n\nLine 328: \"multiple datasets\". Technically two is multiple, but you could say \"two commonly used datasets\".\n\nLine 331: Place a space before the word \"Second\".", "extra_scores": {"ethics_concerns_details": "N/A"}}, {"review_id": "atOkL7Z6IM", "reviewer": "Reviewer_Bw9U", "summary": "This paper investigates user-level privacy guarantees for the user labels in RLHF. It presents a theoretical analysis of the upper bound and lower bound of the estimation error when using the random response (RR) mechanism to achieve user-level DP. The analysis reveals a large estimation error when each users' contribution becomes large, showing the RR-based method as infeasible for user-level privacy. It then presents AUP-RLHF, which is exhibits better utility than the RR algorithm in theoretical analysis and also outperforms User-wise DPSGD, RR, and Group Privacy in the experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "- Achieving user-level privacy guarantees for user labels in RLHF is an important problem. This paper makes novel contributions to this problem through both theoretical analysis and empirical improvements.\n- The paper is well-written and easy to follow.\n- The proposed method leverage outlier removal and adaptive sampling processes to achieve (ε, δ) user-level differential privacy guarantees with better utility.", "reasons_to_reject": "N/A", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "45GN9JtVdk", "reviewer": "Reviewer_WBhh", "summary": "In this paper, the authors proposed AUP-RLHF, a user-level differentially private RLHF method. The authors first theoretically showed that existing DP methods that can achieve item-level differential privacy does not work well when naively extended to user level privacy, especially when each user make a lot of contributions. Then, the authors outlined AUP-RLHF in detail, and provided theoretical justification of the privacy and estimation error of the proposed algorithm. Finally, the author conducted experiments on RLHF on sentiment controlled generation and text summarization tasks, where the authors showed that AUP-RLHF outperforms other DP RLHF baselines under user-level DP settings, and that overall AUP-RLHF requires less noise addition compared to baselines.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "1. There is extensive theoretical justification and proof for each claim (for both \"user-level RR does not do well when m is large\" and \"AUP-RLHF is both user-level private and does not differ much from optimal model\").\n\n2. The experiment results clearly shows that AUP-RLHF outperforms other user-level DP algorithms.", "reasons_to_reject": "1. The experiments are done on relatively simple tasks, and the authors did not provide qualitative examples of generated text from RLHF.\n\n2. Presentation issues: \n\n(1) Line 68: it is unclear what \"outperforms well\" means. Do you just mean \"perform well\"?\n\n(2) Line 167: Is the feature bound L or B? They are being mixed up in this line.", "questions_to_authors": "1. In all experiments and theoretical justifications, the authors assume that each user label the same amount of data; however, this is likely not going to be true in real world settings. If different users contribute a vastly different amount of data points to the dataset, how would that impact the performance and privacy guarantees of the proposed method?\n\n2. Is it possible to provide a qualitative example of a model trained by AUP-RLHF on some user-contributed data that illustrates its privacy-preserving property? Currently all definitions about \"user-level privacy\" exists in terms of probability bounds, and it is kind of difficult for readers to get an intuitive grasp on the concept of user-level DP and why it matters.\n\n3. How much does k matter in AUP-RLHF? According to line 256, the k for the experiments needs to be 3, but the k is set to 1 in all experiments. Also, strictly according to Algorithm 1, 1/2^k data would not be included in training (since each partition will have 1/2,1/4,...,1/2^k data), so in the experiments, when k=1, are you only using half the data to train?", "extra_scores": {}}, {"review_id": "S9M3XPGP4M", "reviewer": "Reviewer_vYQH", "summary": "This paper studies Reinforcement Learning with Human Feedback (RLHF) for aligning LLMs with human preferences. They propose AUP-RLHF, which integrates user-level label DP into RLHF. They use outlier removal and adaptive sampling to ensure that the gradient is concentrated, and show an upper bound on the estimation error. Overall, this paper is clearly written and well motivated, but the experiments could be more thorough.", "questions": "", "limitations": "", "rating": 5, "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": "- User-level privacy is an important topic in LLM training.\n- The authors present an improved algorithm for user-level label DP and give a theoretical upper bound on the estimation error.", "reasons_to_reject": "Experiments could cover a wider range of hyperparameters.\n- How do the results vary with the user contributions $m$?\n- How much hyperparameter tuning was done? The results for DP training can be quite sensitive to the hyperparameters.", "questions_to_authors": "Could the techniques be generalized to improve user-wise DP-SGD?", "extra_scores": {}}, {"review_id": "iWVUC1FoZb", "reviewer": "Reviewer_Kvf8", "summary": "The paper proposes a new privacy-aware approach to RLHF (AUP-RLHF). The method satisfies user level differential privacy and is based on computing the average gradient of the loss with respect to each user’s preferences for updating model parameters during RL. Experiments include sentiment analysis and summarization tasks using two model families of different sizes (Gemma2-2b and Llama2-7b).", "questions": "", "limitations": "", "rating": 4, "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": "* The proposed method looks novel and well motivated (however the overall narrative is hard to follow, see comments below).", "reasons_to_reject": "* The experimental setting is not very clear. The authors should provide details on what are the private attributes in each dataset.* \n* No results are reported for Llama in the summarization task. In general, the paper lacks consistency in the way that the results are presented and discussed.\n* In general, the paper is really dense and can be improved by providing more clear/simple definitions of the underlying concepts presented.", "questions_to_authors": "* You propose AUP-RLHF but what AUP stands for is never defined in the abstract or introduction.\n* You introduce mathematical expressions in the introduction but these are not clearly defined, i.e. what each variable represents?", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a framework for addressing user-level label differential privacy in RLHF. The work is well-grounded with a solid theoretical analysis, establishing both lower and upper bounds for estimation error, and is supported by empirical results on sentiment generation and summarization tasks that demonstrate a superior privacy-utility trade-off compared to several baselines. While some reviewers initially raised valid concerns regarding experimental scope and practical assumptions, these concerns are addressed by additional results and detailed clarifications. This paper makes important contribution to the field of trustworthy AI, outweigh the remaining minor concerns.
Decision: Accept