Square$\chi$PO: Differentially Private and Robust $\chi^2$-Preference Optimization in Offline Direct Alignment
Authors: Xingyu Zhou
Yulian Wu
Wenqian Weng
Francesco Orabona
Venue: ICML 2025 poster (2025)
Keywords: Offline alignment
general function approximations
differential privacy
robustness
single-policy concentrability
Primary area: theory->reinforcement_learning_and_planning
TL;DR: The new state-of-the-art theoretical guarantees in differentially private and robust offline alignments

Abstract: In this paper, we theoretically study the offline alignment of language models with human preference feedback, under both preference label corruption and privacy protections. To this end, we propose a variant of \texttt{$\chi$PO} -- \texttt{Square}\texttt{$\chi$PO}, which is a simple one-line change of \texttt{$\chi$PO}  with the standard log-loss replaced by a new square loss over probability. Thanks to the inherent nice properties of this new loss, we have advanced the state-of-the-art of differentially private and robust alignment. Specifically, for the local model of label privacy, \texttt{Square}\texttt{$\chi$PO}  is the first one that attains optimal rate based on single-policy concentrability even with general function approximations. It also gives the first result under the central model of privacy protection over both prompts (responses) and labels. On the robustness side against Huber label corruption, \texttt{Square}\texttt{$\chi$PO}  is the first alignment method that has a meaningful theoretical guarantee under general function approximations. More importantly, \texttt{Square}\texttt{$\chi$PO}  can address privacy protection and corruption \emph{simultaneously}, where an interesting separation is observed, implying that the order of privacy and corruption matters. Furthermore, we show that \texttt{Square}\texttt{$\chi$PO}  can also be easily extended to handle the scenario of the general preference model with state-of-the-art guarantees under corruption and privacy. Last but not least, all of our theoretical guarantees enjoy a unified analysis, building upon a new result on the generalization error bounds of least-square regression under corruption and privacy constraints, which we believe is of independent interest to the community.

SquarexPO: Differentially Private and Robust in Offline Direct Alignment
x PPerferree Optimization
Xingyu Zhou' 1
Yulian Wu² 2 Wengian Weng' Francesco Orabona 2
Abstract
1. Introduction
Aligning large language models (LLMs) to human values is crucial for their responsible deployment. Two primary paradigms have emerged: indirect alignment, where a re- ward model learned before the policy optimized via Rein- forcement Learning (RL) (Christiano et al., 2017; Ouyang et al., 2022), and direct alignment, an RI.-free approach leveraging reparametrization techniques like Direct Pref- erence Optimization (DPO) (Rafailov et al., 2023). Very recently, a variant of DPO, called XPO (Huang et al., 2024), addresses the overoptimization issue in direct alignment by relying on a significantly weaker condition - single-policy concentrability making the first offline direct alignment method with such guarantee.
In this paper, we theoretically study the offline alignment of language models with human pref- erence feedback, under both preference label cor- ruption and privacy protections. To this end, we propose SquarexPO, simple one-line change to XPO where the standard log-loss is replaced by a new square loss over probability. Thanks to the inherent properties of this new loss, we have ad- vanced the state-of-the-art of differentially private and robust offline direct alignment. Specifically, for the local model of label privacy, Square XPO is the first algorithm that attains an optimal rate based on single- policy concentrability even with general function approximations. It also gives the first result under the central model of privacy pro- tection over both prompts (responses) and labels. On the robustness side against Huber label cor- ruption, Square (PO is the first alignment method that has a meaningful theoretical guarantee under general function approximations. More impor- tantly, SquarexPD can address privacy protection and corruption simultaneously, where an interest- ing separation is observed, implying that the order of privacy and corruption matters. Furthermore, we show that SquarexPO can also be easily ex- tended to handle the scenario of the general prefer- ence model with state-of-the-arr guarantees under corruption and privacy. Last but not least, all of our theoretical guarantees enjoy a unified analysis, building upon new result on the generalization error bounds of least-square regression under cor- ruption and privacy constraints, which we believe is of independent interest to the community.
Meanwhile, privacy and robustness concerns in the pref- erence datasets of the alignment process have gained sig- nificant attention. Membership inference attacks expose privacy vulnerabilities (Feng et al., 2024), while data poison- ing undermines label integrity (Casper et al., 2023). Recent efforts have addressed these challenges separately, provid- ing theoretical guarantees for privacy robustness. On the privacy side, existing theoretical work has primarily fo- cused on simple linear function approximations (Zhou et al., 2025; Chowdhury et al., 2024b; Korkmaz & Brown-Cohen, 2024), which are insufficient for practical scenarios involv- ing non-linear reward or policy function classes (e.g., neural networks).
Q1. For general function approximations, we achieve optimal (or better) rates under privacy constraints?
We answer Q1 affirmatively by introduc- ing SquarexPO, simple variant of XPO which replaces the log loss with a new square loss over probabilities. For pref- erence label privacy under the local model of Differential Privacy (DP) (Kasiviswanathan et al., 2011: Chaudhuri Hsu, 2011), Square achieves the optimal privacy cost, even with general function approximations. Furthermore, under the standard central DP model (Dwork et al., 2006), it provides the first pure DP guarantees for the case of general function approximations.
Contribution 1.
'Wayne State University, USA 'King Abdullah University of Science and Technology, Saudi Arabia. Correspondence to: Xingyu Zhou <xingyu.zhou @ way.e.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Moving now to the robustness side, Mandal et al. (2024) takes an indirect approach, focusing on the linear setting,

---

Square-xPO
while Chowdhury et al. (2024a) follows a DPO-style direct method, which, however only achieves suboptimal rate for the linear case and suffers from non-vanishing suboptimal- ity gap for general function approximations.
demonstrating that an iterative version of SquarexPO pro- vides the first set of results for private and robust alignment under general preference model, achieving guarantees analogous to the results of iterative XPO (Huang et al., 2024)
Q2. Can we improve these results under label corruption, even for general function approximations?
Finally, on the technical side, it is often desirable to have a clean and unified analysis across different settings, which in our case includes privacy (local or central models), corrup- tion, as well as BT and general preference models.
Contribution 2. Our SquarexPO provides an affirmative answer to Q2. Specifically, it not only preserves the favor- able single-policy concentrability property of xPO, but also achieves the optimal ((1/v)) rate for general function approximations under the same random-flipping corruption setting in Chowdhury et al. (2024a). Furthermore, due to the inherent boundedness of our new loss, Square XPO is the first alignment method to provide meaningful guarantees under stronger Huber label corruption (Huber, 1964), match- ing the best-known results in the con-prefereece feedback offline RL setting (Zhang et al., 2022).
Q5. Can we have a unified analysis of SquarexPO?
We answer this question affirmatively by establishing all of our theoretical results through key com- mon analytical tool: new generalization error bounds for least-square regression under privacy constraints and corrup- tion. Given the widespread use of least-square regression oracles in RL (Agarwal et al., 2019), we believe these results could be of independent interest.
Contribution 5.
In the interest of space, we relegate the discussion on further related work to Appendix A.
Instead of studying privacy protection and robustness to corruption separately, there is growing interest in under- standing their interplay, driven by both practical scenarios and theoretical insights, for example. in bandits (Zhou & Zhang, 2024; Wu et al., 2024b; Charisopoulos et al., 2023) or general statistical tasks; please refer to Kamath (2024) for a wonderful recent survey.
2. Preliminaries
2.1. Offline Alignment
In the offline alignment problem, there exists a pre-collected preference dataset DD Pret = {(r,, aP, at, )= where each context/prompt x; is i.i.d. sampled from a distri- bution p. and two responses af and at are i.i.d sampled from reference policy Tref, i.c., of Teer(- | xx) and of ~ Tref(- æ;). and finally the preference label Yi E (0, 1} is generated according to some probability distribution, i.c., Yi ~ Ber(P" > a. xx)). where p* (a: > a. x;) E [0 is the probability that given zi, a is preferred over af and Ber(-) denotes Bernoulli distribution. Without loss of generality, we assume that p(z) > 0 for all and (a x)) > 0 for all and a. Depending on the modeling assumption of the preference probability P* > of zz),, the (offline) alignment is often categorized into the following two settings.
Q3. Can we achieve privacy protection and robustness si- multaneously, and what are the interplays between them?
Contribution 3. Our Square simultaneously addresses privacy and robustness in offline direct alignment, uncov- ering interesting interplays between the two. For the local model of label privacy, we examine two settings that differ in the order of privacy and corruption. SquarexPO is adap- tive, as does not require prior knowledge of the specific setting while providing sharp rates. Notably, our results re- veal that corruption following privacy leads to worse bounds. For the central model of DP, our findings illustrate that the effects of privacy and coruppiion are only additive. Both are consistent with prior observations in mean estimation and bandits (Zhou& & Zhang, 2024; Wu et al., 2024b).
Bradley- Terry (BT) preference model (Bradley & Terry, 1952). In this setting, there exists an unknown true reward function r" X A - [0, Runax] that induces the prefer- ence probability as follows
All the above results (including those prior work) are es- tablished under the assumption of the Bradley-Tene Terry (BT) preference model (Bradley& & Terry, 1952), which implic- itly assumes transitive preferences (i.e., a > b,b c + > c). However, transitivity does not always hold in prac- tice. Building on recent work in the non-private and non- corrupted setting, where general preference models have been explored (Munos et al., 2023; Swamy et al., 2024), it is natural to pose the next question:
exp(r*(4x, az)) (* af 1 exp(r* at)) + exp(r (xi,
With the preference dataset DD preef, the goal under this setting is to learn a policy के that minimizes the suboptimality gap:
Q4. For general preference model, can we still achieve privacy protection and robustness simultaneously?
SG x²) J(x*)~ J()).
(1)
where J(TT) := Em=p.arr(1a) (x= a)] and T is any com- parator policy (e.g., could be the optimal policy maximiz-
Contribution 4. We answer this question affirmatively by
2

---

Square-xPO
ing (Tr or any other policy). For notation simplicity, we will abbreviate [=]] == (()))---(((()))
which leads to the following optimization"
ExPO argmax xell
Σ
loglo(sh a+, a-))],
General preference model (Munos et al., 2023). In this setting, one directly works with a general preference model Paaaa > af (i)) without the parametrization of a re- ward function as above. This general preference model has several advantages over the BT-preference model, e.g.. is better at capturing non-tree non-transitive preferences (a > b, b > C, a). Without the reward function, the solution concept now becomes minimax winner (von Neumann win- ner) (Munos et al., 2023; Swamy et al., 2024; Wang et al., 2023b), which is given by
(2,0+ ppD
where hxpo( a a_.a-):=g [vrr(a+)22) Fror(a- ((r) and ((u) := + log u. Compared to DPO, there is an ad- ditional linear term in ((2) that introduces pessimism (Jin et al., 2021b), which enables suboptimality gap that only depends on single policy concentrability (Rashidinejad et al., 2021). On the other hand, DPO could only achieve sub- optimality gap in terms of all-policy concentrabiliiy coef- ficien (Chen & Jiang, 2019) due to the lack of pessimism. Moreover, XPO can also be extended to handle the general preference model with a meaningful upper bound on the duality gap. Given the stronger performance of XPO, we will mainly focus on it when we consider robustness and privacy in offline alignment, as discussed below.
saa [x]
TMW == argmax min P* > x'),
Well w'ell
where PM(T > x) = E > nt (x) z]] for a pair of policies π,, n in a policy class II. often more convenient to work with scaled and shifted version of (a > a æ²) as (x, ad)) == 2P*(a" > a" 1x) which leads to an equivalent definition of minimax winner
2.3. Robustness and Privacy in Preference Data
Label corruption. In practice, the preference label y/ may not be sampled from the clean distribution Ber(P* (a) > of x;)). To characterize this, we borrow the classic Huber corruption model from robust statistics.
TMW == argmax min 8 ((TTT))
*ell w'lll
where E (π, T') := (n-patt
(1)))) (x, )-
Since this minimax winner can be viewed as a Nash equi- librium of two-player constant-sum game, our goal in this setting is to minimize the duality gap
Definition 2.1 (a-Huber corruption (Huber, 1964)). We consider the following o-Huber corruption: each label is independently sampled from (1 (1-aae a)G; + aB, where G is the clean distribution Ber(P"(a! > af xx)) and B, is some arbitrary unknown Bernoulli distribution. That is, with probability a E [0, 1/2], each label is sampled from some bad distribution.
DG iT)
max (' (T, minn l' (T, TEll
FEll
2.2. DPO and XPO
DPO. One of the most popular offline alignment algorithms Direct Preference Optimization (DPO) (Rafailov et al., 2023). Its popularity could be partially attributed to its success in eliminating the reward model learning process, achieved by reparameterization of reward by the optimal policy of a KL-regularized optimization objective. In par- ticular, under the BT-preference model, given a preference dataset D pref and user-specified policy class II, DPO solves
Label privacy in the local model. The preference label is often collected via human feedback, which could potentially reveal each person's 's private information, as discussed before. To this end, a strong privacy protection is to ensure Local Differential Privacy (LDP) via a local randomizer. Given the binary data of the preference label, it is natural to consider the classic randomized response mechanism.
Definition 2.2 (Randomized response and e-LDP (Warner, 1965)). Let & > be the privacy parameter and y E (0. 1} be the true label. The randomized response (RR) mecha- nism R flips y and outputs private ÿ based on the following distribution
TDP = argmax TE
Σ
lo a-)a
le.44.0))EDm
x log mecr(a [z) a(2) I is the sigmoid function, and 8 > 0 is some regularization parameter. Here, for any data point (x, a", a²_ v) in Drref we set a,, = ad (the preferred one) and a = a (the non-preferred one).
where lIpPo (z, a4, a_) = log (a+ (m)
1
P P 1+ and P +
I+
This can be easily shown to satisfy e LDLPP, i.c., for any y, v' and any subset S in the range of R such that
XPO. To address the inherent overoptimization issue in DPO, Huang et al. (2024) recently proposed a simple variant of DPO by introducing an additional reguguaarin term,
P(R(v) E < e P ( ES.
We ignore the clipping operation for the ease of presentation.
3

---

Square-XPO
Interplay between corruption and LDP. In practice, cor- ruption and LDP protection can exist together, which moti- vates us to consider their interplay in the following settings. Definition 2.3 (CTL and LTC), Given a raw preference dataset D Pref = {(x;; a,, ";) H== and two parameters a E [0, 10.1/2]. < > O, we consider the following two set- tings that differ in the order of corruption and label privacy protection in the local model:
Algorithm SquarexPO for CTL and LTC
1: Input: Locally private and corrupted preference dataset Drref = (2,, af, a. 24) }² under CTL and LTC, pri- vacy parameter > regularization coefficient, | > 0,
reference policy re
2: Define
Ø(u) == log v
(4)
π {(a: xis)
π(aa 22))
Corruption-then-LDe (CTL). The raw label y: is first corrupted by the o- o-Huber model, which is then further privatized by s-LDP RR mechanism, leading to the final preference dataset given by prrtf = {(T,, af at, 2:) K=1-
hxpo,
(5)
TTref (a; Tii)
Tear (a² xii)
3: Optimize the following objective:
CoDruten-Corruption (LTC), The raw label yi first privatized by E-LDP RR mechanism, which is then further comrppted by the a-Huber model, leading to the final prefer- ence dataset given by Prref {(x,, of, af, z)] }
ā + 4-argminn TEll VE(M)
Σ
[2o (clip2
where c(E) = ex+1 and 224 -1 4: Output: म et
One of our goals is to study whether there exists a separation between the two settings, implying the order of corruption and LDP matters.
Remark 2.4. The two settings naturally include corruption- only and privacy-only as special cases by setting 6 = do and a = 0, respectively. Moreover, it is easy to see that, combining the results of CTL and LTC directly gives us the result for an even practical setting where corruption happens both before and after LDP.
Remark 2.7. As before, cDP recovers privacy-only and corruption-only settings by setting a 0 and ε = cc. respectively.
3. Bradley-Terry Preference Model
Differential privacy in the central model. We will also consider the standard DP definition, which is defined in the central model where the learner has access to the raw data and needs to ensure similar output two neighboring datasets.
In this section, study offline alignment in the BT- preference model under privacy constraints and corruption. We first focus on the interplay between corruption and the label LDP (i.e., CTL and LTC) and then turn to the setting of central DP, i.e., cDP.
Definition 2.5 ((e, 6)-DP (Dwork et al., 2006)). Let & > 0 and 5 E [0, 1]. and A be a given offline alignment algorithm. We say A satisfies eDD if for any measurable set S in the range of A
3.1. Local Model
Our proposed algorithm, SquarexPO in Algorithm 1, is the same for both CTL and LTC, i.c., adaptive. The key modification compared with XPO to use a square loss instead of the log loss, plus an additional c(e) factor for the private case. We will dive into the intuition about the choice of our loss function in the sequel. Before that, we remark that the clipping clip = max min u, R}. -R) with R = R is adopted in XPO as well, mainly used for a slightly tighter theoretical bound.
P[A(Dpref) E S] .P [PA (Drttt) E 8,
holds for any pair of (Dpref, Pirer) that only differs in one sample (Ir,, a. at yi) for some E [n]. If = O, we simply write SD (i.e., pure DP).
Here, we not only protect the preference label, but also the prompt and responses. As before, we would also like to study the interplay between corruption the central DP. In contrast to the local model, here the label corruption can only happen before the central privacy protection.
1.1.1. INTUITION BEIIIND SQUAREXPO
We now discuss our new loss function in SquarexPO, high- lighting the intuition how it helps to handle corruption and privacy protection. It is worth noting that our new loss function could be of its own interest even in the standard scenario, i.c., non-private and non-corrupted cases, with DPO-type (rather than XPO-type) reparameterization.
Definition 2.6 (Corruption and DP (cDP)). Given raw preference dataset Drref = (11, af, at }:)) and two parameters a E 1/2], ε > 0, we consider the following interplay: each label y/ is first corrupted by a-Huber model, resulting in Dpref= = {Z,, al a! b.)) Then, the learner employs an algorithm that c-DP with respect pretf
1. Square loss over probability, Without privacy protection

---

Square-xPO
(c(s) = 1), our new loss function essentially reduces to
We start with the same assumptions as in xPO (Huang et al., 2024), i.e., policy realizability and bounded range.
Σ (pi(T)) - );²² kE(n]
(6)
Assumption 3.2 (Policy realizability). Fix > 0. The policy class Il satisfies T E II, where T3 is the optimal policy of the following mixed x² regulllari objective:
where we define pT( == a (clip2 Rmaae po.d). while DPO and XPO essentially adopts the standard log-loss, i...
B Nim (T): (r- ax) 3 [ ( ret] DKL (T] (ee])
(11-z]] -z, log - (1 -1- z:) log(1 - pi()))
(7)
The J²m (अ)) in XPO mixes x² regularizztion with the stan- dard KL-regularization in DPO, which in turn leads to the new reward reparameterization using optimal solution #3.
In fact, the loss in (6) is often referred to as Brier score (Brier, 1950) in probabilistic predictions. One di- rect observation here is that the Brier score is always upper bounded by 1 while the log-loss can be unbounded, which implies that label corruption under log-loss may have larger impact than that under the Brier score.
T3(aaz)) Traf (a|zz)
r r" a) = B6
+ (z)
where we recall that d(u) = u + log u and Zp.r (x) is some cetion-independent normalization term. Thus, As- sumption 3.2 essentially implies the implicit reward realiz- ability under the above parameterization.
2. Converting to =1 with d(s) scaling. Instead of working with 2, E {0. 1}. we convert 2, 22, 1 E 1 and we similarly update the probability part. There main reasons for this: (i) From (3) of RR, we can easily see that the private mean (under 1) is 1/c(E) of the true mean (probability). This implies that the c(E) factor in front of the private data leads to an unbiased estimate of the true probability, which essentially follows from the same intuition as in private mean estimation under RR, since the empirical average mean estimator can also be written the solution to square loss; (ii) Recall that for the general preference model, it often works with +1 (ef. (2)). As we will see later, this conversion allows us to essentially employ the same technique to analyze both BT-preference and general preference models, altogether.
two
As in xPO (Huang et al., 2024), the next assumption asserts that the implicit reward difference under any policy in II is upper bounded by some constant.
Assumption 3.3 (Bounded implicit reward difference). For a parameter Vmaxx > Rmaxx it holds that for all π E II, at E X, and a, E A.
x(a x)) Trof (a x) ) 36
(Tb x)) Trof (b x))
Viaax
Finally, we will measure the theoretical performance using the same type of single-policy concentrability as in XPO.
Remark 3.1. We mention in passing that many alignment al- gorithms draw inspiration from binary classification for their loss functions, in the non-private non-corrupted cases. For instance, in addition to log-loss in DPO and XPO, SLiC (Zhao et al., 2023) leverages the hinge loss while IPO (Azar et al., 2024) adopts the standard square loss. The key conceptual difference between our square loss and that of IPO lies in the fact that the latter takes the square over the raw log-ratio (i.e.. implicit reward) while ours is square over proba- bility (i.e., an additional sigmoid step is applied). More recently, Tang et al. (2024) proposed family of loss func- tions for alignment based on standard supervised learning, including exponential loss, truncated quadratic loss, and savage loss. To the best of our knowledge, our SquareXPO is the first one that proposes to use the Brier score as the loss. In the next section, we will demonstrate its strong theoretical guarantees.
Definition 3.4 (L1 ----eettrabblltt)) The single-policy L1- concentrability coefficient for policy n is given by
π T x))
C := E
Tref ree (z(2z))
where we recall that [.[- == Ex=p,
By a direct calculation, one can see C* = 2D x= ret +1, which is extremely useful in the analysis of both XPO and our next main result on Algorithm 1.
Theorem 3.5. For any given comparator policy x², there exists a proper choice of 3 > 0 such that when Assump- tions 3.2 and 3.3 hold, with probability at least 1 - C. the output of Algorithm I satisfies the following suboptimality gaps under CTL and LTC:
(cee) log(ITI/S)) n Va va).
SGCTL (ic (+;+))))((T))
3.1.2. THEORETICAL GUARANTEES
In this section, our aim to establish the suboptimality gap (cf. (1)) of SquarexPO (Algorithm 1), under both CTL and LTC, without knowledge of the setting in advance.
log( ([)(( + + La. v(()
SGLTC (ttt(((;t)))
c(E))
n
5

---

Square-xPO
where a S b as shorthand for a Ob)) d(e)
- and
Algorithm 2 SquarexPO for cDP
<((²)= := e2 Yuaz
vC is the single-polic concen-
1: Input: Possibly label corrupted preference dataset Drref = {2,, af, a.. Mi) li= privacy parameter > O, regularization coefficient / > 0, reference policy Fief=
Rmas
trability related term.
Remark 3.6. Thanks to the use of RR in CTL and LTC, our algorithm is s-LDP. Setting = = oo and a = 0 in the above utility bounds, leads to the same bound as in XPO. Moreover, as a by-product, the above theorem also directly gives results for privacy-only and corruption-only settings. Furthermore, it can be easily leveraged to establish bounds for the setting where corruption happens both before and after local privacy with a simple summation of the two bounds above. We stress that, as in Huang et al. (2024), we consider a finite policy class II for the ease of presentation. The extension an infinite function class can be easily achieved via the standard covering number argument. For example, for a linear reward model in Rd (or equivalently, log-linear policy class), log [TT] will roughly be (d))
Nxpo, in (5)
2: Define
L(T:: D prret) ==
Σ 6E(m]
[20 (clip2Rmax [Bhxpo.1)) -1 -9/]
where T/ = 28: - 1 E {1, -1]
3: Sample a policy म from II via the following distribution
P(T) x exp (- E
[[TT; Prret))
8
4: Output: मे
With the above theorem, several important observations and remarks are in order.
noise under RR after simple reparameterization. Thus, it is in fact more fair to compare it with Theorem 3.5 under a = O. In this context, our main result has two significant improvements over Chowdhury et al. (2024a): (i) Even un- der the linear model, Chowdhury et al. (2024a) only archives O(1/n (1/n//4) rate with worse all-policy concentrability de- pendence while ours is the optimal (11/n//2) rate with single-policy concentrability; (ii) For the general function approximation setting, Chowdhury et al. (2024a) fails to achieve a vanish suboptimality gap as + Do while ours maintains the optimal (11/n2/2) rate. Another related work is Mandal et al. (2024), which only considers RL-based alignment with linear function approximations under adver- sary corruption of both prompt (responses) and labels. In contrast, our main focus is RL-free alignment for general function approximations while under label-corruption only, Finally, we refer readers to Section 6 for comparisons with one concurrent work (Zhou et al., 2025) on robust align- ment.
Interplay between local privacy and corruption. One can see that under CTL, the impact of local privacy parameter e (i.e., the first term and corruption parameter a (i.e., the second term) is separable (additive), while there exists a multiplicative term in LTC, which leads to an additional Vc(E) b 1 factor. While these are only upper bound results, we tend to believe that the different interplay between local privacy and corruption (i.e., additive vs. multiplicative) indeed exists, especially given the recent similar tight result in mean estimation (Zhou& & Zhang, 2024).
Comparison with prior private alignment. To the best of our knowledge, Chowdhury et al. (2024b) is the only related work that studies label privacy protection in offline alignment. However, it considers the standard RL-based ap- proach where a reward model is explicitly learned before the policy optimization, rather than our RL.-free direct optimiza- tion method. More importantly, it only considers the linear reward setting while ours is the first one that establishes formal guarantees for the general function approximation settings with the same (optimal) privacy cost of c(E) and similar single-policy concentrability dependence. Finally, we refer readers to Section 6 for comparisons with one concurrent work (Zhou et al., 2025) on private alignment.
3.2. Central Model
We now turn to privacy protection in the central model where both the prompt (responses) and labels are sensitive information (cf. cDP in Definition 2.6).
Our proposed algorithm is presented Algorithm 2, which essentially applies the exponential mechanism (McSherry & Talwar, 2007) with square loss as the score func- tion. The boundedness of our square loss (in contrast to the unboundedness of log-loss) plays a key role in balancing privacy and utility thanks to its bounded sensitivity, i.e., changing any single sample at most modify L(mT; Dpref) by 4, which leads to our sampling distribution in Algorithm 2.
Comparison with prior robust alignment. To the best of our knowledge, only Chowdhury et al. (2024a) provides formal theoretical bound on the suboptimality gap of robust variant of DPO under particular type of label corrup- tion. Specifically, it considers the so-called rundom-flippngg corruption (i.c., with some known probability, the true la- bel is flipped). An astute reader may already observe that this corruption model is weaker than our Huber corruption, and moreover, is essentially equivalent to label privacy
We now proceed present the privacy and utility guarantees of Algorithm 2.
6

---

Square-xPO
Theorem 3.7. Let > O, Algorithm 2 satisfies E-DP. For any given comparator policy x², there exists a proper choice of 3 > 0 such that when Assumptions 3.2 and 3.3 hold, with probability at least 1 Ç. the output of Algorithm 2 satisfies the following suboptimality gap under cDP
ting, it is impossible achieve single-policy concentrabil- ity dependence in the sample complexity bound under the general preference model. Thus, we will aim to achieve a coverage dependence the same as in XPO under the general preference model, which is somewhat in between single- policy and all all-policy concentrability.
((++ 322
log( (C) + Va
SG,DP (() SS((T')
In the interest of space, our proposed algorithm for the general preference model under privacy and corruption is presented in Algorithm 3 in appendix. It mainly consists of two key steps: (i) preference model estimation and (ii) pol- icy optimization with self-play. Our modification compared to iterative XPO in Huang et al. (2024) only lies in the first step, since the labeled data set (which is our corruption and privacy protection target) is only used during the first step while the second step works with an unlabeled dataset D...
72
where k((T)) = 2Bmax. Yuua C is the single-policy
Rmaa
concentrability related term.
With this theorem in hand, several interesting and important observations are in order.
Interplay between central DP and corruption. One can first observe that as in CTL, the cost of privacy and corrup- tion is separable (i.e., additive). However, the privacy cost is smaller in the central model than that under the local model.
(i) Preference model estimation. Depending on the local or central privacy model, we have two different ways of finding ?. For the local model, ? is found via a modified least-square regression where an additional factor of c(s) is applied in (10), which will essentially reduce to the same loss as in Huang et al. (2024) when s = do (i.e., no privacy protection). We can now also observe that the loss function under the BT-preference model in Algorithm is simply specifie instantiation of (10) by plugging BT-preference probability (via sigmoid function) into ((r;; af; a!). ). Sim- ilarly, for the central model, we again use the exponential mechanism to find é, based on the square loss, which also generalization of the loss used in Algorithm 2 under the BT preferennce model.
Comparison with prior alignment under central DP. To the best of our knowledge, there are two concurrent works (Chowdhury et al., 2024b; Korkmaz& & Brown-Cohen 2024) that studied RL-based alignment under central DP constraint in the context of linear reward model in IR In particular, they both consider weaker approximate DP constraint (i.e., 8- 0) and establish privacy cost of Vne
O eral fiunction approximations with a stronger pure DP guar- antee. In fact, if one simply generalizes their approaches by following the non-private counterpart in Zhu et al. (2023) to tackle non- linear functions, it will lead to strictly subop- timal non- vanishini suboptimality gap. Further, our result under a linear model reduces to a privacy cost of O vd which has worse dependence on d (due to the stronger pure DP) while getting rid of the additional log(1 /8) factor (which is typically at least on the order of Iog
(dlog(1/6))// In contrast, our result can handle gen-
(ii) Policy optimization with self-play. With the estimated preference model i in hand, we proceed to run policy op- timization over a unlabeled dataset via self-play, which means that F is constructed using the current policy a' (i.e., by ~ n² (x)). With this ft, our algorithm (which is the same as in Huang et al. (2024)) updates its policy by mirror descent (Nemirovskij & Yudin, 1983) with a mixed regularizer (i.e., x--regularizer and K[-regularizer) over both the current policy n' and Tee This type of mirror descent can be rewritten using the same XPO reparametriza- tion as a regression over reward difference, leading to the loss (xr;; D.) in (11) with the reparametrization function par (ar, a, b) given by
Remark 3.8. It should be clear that Algorithm 2 is not a computationally efficient due to the sampling operation, especially for an infinite class II. Hence, we view it as an information-theoretic result, which serves as an important theoretical benchmark for our next step in developing computationally efficient algorithm. This is indeed a typical path in the private machine learning literature.
3 (1+ + 1)) B. 1-- 1x (2, a, 12 (x, a,a
4. General Preference Model
(8)
In this section, we turn to the general preference model, which does not assume preference transitivity as in previ- ous BT-preference model. We will demonstrate that our SquarexPO can be easily extended to this setting based on the self-play framework (Swamy et al., 2024; Gao et al., 2024; Rosset et al., 2024). As already shown in XPO (Huang et al., 2024) for the standard non-private non-con concorrupted set-
((bb))) is es- where fixoxx a, b, == 06 x(2lz) Φ
(Ta)( sentially the same reparametrization used in the last section (cf. (5)) with ø(u) = u + log being the same as before. At a high level, this policy optimization step can be viewed as a combination of the techniques developed in Gao et al. (2024) (i.e., regression over the reward difference with a
)))((|)))
7

---

Square-XPO
reparametrization trick) and in Chang et al. (2024) (i.e., regularized over both r' and rff) We will provide more intuition on this step in the next section.
Theorem 4.4. Let O, Algorithm 3 satisfies e-LDP or DP, respectively. Let subopt C) maxzen E (T,, 7) max 8 (I,, it) and Il := { maxxEx (x) (z)r & C). Then, for any Ç E (0. 1] and each setting of JJC and cDP, under Assumptions 4. 4.2 and 4.3, there exists corresponding proper choices of T, B,T such that with probability 1 C, the following bounds hold:
4.1. Theoretical Guarantees
In this section, we present our main theoretical result Iterative SquarexPO in Algorithm 3. First, we state the same set of assumptions as in Huang et al. (2024).
DG( S min (subopt(7, CC+C.B)
C>1
Assumption 4.1 (Preference function realizability). The model class L satisfies L E L where E is the ground truth preference function.
where {BeTL, BLTC, BaDP) are defined as
BCTL: :
Vm +
a
The next assumption is about the policy realizability during each policy update step, which is analogous to Assump- tion 3.2 in the BT BTT-prfferecce model.
8
log( [T
|I|
BLTC
Vm + cCE))
(xc(E) log
5
Assumption 4.2 (Policy realizability for general prefer- ences). For any policy x E Il and & E C, the policy class contains the minimizer of the following regularized opti- mization objective: Vx E X
log (
11
BcDp:=
Vm +
1 vo
a log
n
8
where Vm == Viax (11()
E (a) ((x PEA(X)
(p,TTaa
vm
Remark 4.5. We remark again that this is the first set of results for private and robust alignment under a general preference model.
where the regularizer R2 (p. Trefi R²) is given by
(P, Firt π) = SD (wl) + 3 (,,
5. Key Techniques Highlight
with Dj Dism (pllg) = : (pl14) + DKL (pllg) and (p. q) being the Bregman divergence induced by the convex func- tion F(u)= Dxxmn. (ull i.e.,
In this section, we would like to highlight a key common technique behind all the results in previous sections. In particular, all of our sample complexity bounds build upon the following lemma that characterize generazation error bounds of least-square regression under CTL, LTC or cDP.
(z g) F(p)
F()) - F(4)=
(VF(g).P- PFF()).--o)) -9)-
Lemma 5.1 (Informal statement of Lemma B.1). Let {U1 b')r== be a clean dataset and H. be a hypothesis class such that realizability holds (h" E H.) Define gener- alization error for any h as
While it may seem to be complicated, we now pause briefly to provide further intuition on the above optimization by comparing it with Jzm in Assumption 3.2. We first note that the in म (2; l, T) will be ní in our algorithm. Thus,
err : -Euupp [[r((u) -h (v))),,
compared with Jz' the above optimization basically adds another regularization over x² via Bz (p. n²), which directly gives us the reparametrization function in (8)² with T' n².
for feature distribution p'. Then, with probability at least S, we have
Finally, analogous to Assumption 3.3, we assume that the implicit reward is bounded.
I. Under CTL and LTC, given {(u, H input dataset, h argmin Σn (h(w) c achieves
Assumption 4.3 (Bounded implicit reward difference for general preferences). For a parameter Vmax > 2, it holds that for all π,, n' E II, x E X, and a, E A.
err gTn S c(s)) lox((HL/C)) + a,
err LTC S c(s)). log((Hl//C) c(e)
1 (z, a, b)l < Vmax.
2. Under cDP, given {ww,, 81 as input dataset, running
Our main guarantee for Algorithm 3 is as follows.
exponential mechanism using square loss over Jl yields
Note that the last term in B2 (p. g) will not contrihute, since the gradient of it independent of p.
log((((/C) + log((7)/() + a.
err err
gen 2
8

---

Square-XPO
The above result is nontrivial extension of the standard findings in (Song et al., 2022) the private and corrupted settings. Given the widespread use of least-squares regres- sion oracles in offline, online, and hybrid RL (Agarwal et al., 2019), we believe this result can be readily applied to drive new advancements in the private and corrupted scenarios.
References
Abdin, M. I., Jacobs, S. A., Awan, A. A., Aneja, J., Awadal-
lah, A., Awadalla, H., Bach, N., Bahree, A., Bakhtiari, A., Behl, H. S., Benhaim, A., Bilenko, M.. Bjorck, J.. Bubeck, S., Cai, M., Mendes, C. C. T., Chen, W., Chaudhary. V., Chopra, P., Giorno, A. D., de Rosa, G., Dixon, M., EI- dan, R., Iter, D., Garg. A., Goswami, A., Gunasekar, S., Haider, E., Hao, J., Hewett, R. J., Huynh, J., Javaheripi. M., Jin, X., Kauffmann, P., Karampatziakis, N., Kim, D., Khademi, M., Kurilenko, L., Lee, J. R., Lee, Y. T., Li, Y., Liang, C., Liu, W., Lin, E.,, Lin, Z., Madan, P., Mitra, A., Modi, H., Nguyen, A., Norick, B., Patra, B., Perez- Becker, D., Portet, T., Pryzant, R., Qin, H., Radmilac, M., Rosset, C., Roy, S., Ruwase, O., Saarikivi, O., Saied, A., Salim, A., Santacroce, M., Shah, S., Shang, N., Sharma, H.,, Song, X., Tanaka, M., Wang, X., Ward, R., Wang, G., Witte, P., Wyatt, M., Xu, C., Xu, J., Yadav, S., Yang. F,, Yang, Z., Yu, D., Zhang, C., Zhang, C., Zhang, J., Zhang, L. L., Zhang, Y., Zhang, Y., Zhang, Y., and Zhou, X. Phi-3 technical report: A highly capable language model locally on your phone. arXiv preprint arXiv:2404. 14219, 2024.
6. Discussion
In this section, we first provide detailed discussion the concurrent work (Zhou et al., 2025) on private and robust offline alignment, which shares similar motivations but has the following key differences. First, Zhou et al. (2025) only focuses on the linear model with BTT-preference, while we consider general function approximations for BT-preference as well as general preference model. Second, Zhou al. (2025) only considers local DP, while we also consider central DP. Third, Zhou et al. (2025) considers strong cor- ruption model while we consider a slightly weaker model, i.e., Huber corruption model. This gives a different term regarding the interplay between privacy and corruption, i.c., e(c) vs. Vc(E)a. We also believe that the dependence on in Lemma 5.1 can be improved to a² by leveraging the Huber corruption property². Second, although we mainly focus on the theory in the main body, we have also man- aged to conduct some experiments as proof-of sooofoff-coceppl see Appendix E. for details.
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Rein- forcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019.
Amortila, P., Foster, D. J., Jiang, N., Sekhari, A., and Xie, T. Harnessing density ratios for online reinforcement learning. arXiv preprint arXiv:2401.0968) 2024a.
7. Conclusion
We introduced SquarexPO, novel offline alignment method that achieves tfate-of-the-atr theoretical guarantees in the presence of noisy labels caused by privacy protections and/or adversarial corruption. Our algorithm can handle both BT B'T-preference and general preference models. While our primary focus is theoretical, SquarexPO remains practi- cal and easy to implement, requiring only a minor modifica- tion XPO and DPO. Future work will focus on comprehen- sive empirical evaluations to further validate findings.
Amortila, P., Foster, D. J., and Krishnamurth, A. Scal- able online exploration via coverability. arXiv preprint urXiv:2403.066 2024b.
Azar, M. G., Guo, 7. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandriello, D. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pp. 4447-4455 PMLR, 2024.
Acknowledgements
Bagnell, J., Kakade, S. M., Schneider, J., and Ng, A. Policy search by dynamic programming. Advances in neural information processing systems, 16, 2003.
XZ is supported in part by NSF CNS-2153221 2153220 and CNS- 2312835.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D.,, Fort, S., Ganguli, D.,, Henighan, T., Joseph, N., Kadavath, S., Kermion, J.. Conerly, T., El-Showk, S., Elhage, N., Hatfield-Dodde Z., Herman- dez, D., Hume, T., Johnston, S.,, Kravec, S., Lovitt, L., Nanda, N., Olsson, C., Amodei, D., Brown, T., Clark, J., McCandlish, S., Olah, C., Mann, B., and Kaplan, J. Training a helpful and harmless assistant with reinforce- ment learning from human feedback. arXiv preprint arXiv:2204.00 005822, 2022a.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning, There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
'In fact, we are working on new paper that will have a more thorough discussion. Stay tuned.
9

---

Square-xPO
Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J.,
Chhor, J. and Sentenac, F. Robust estimation of discrete distributions under local differential privacy. In Interna- tional Conference on Algorithmic Learning Theory, pp. 411-446, PMLR, 2023.
Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McK-
innon, C., Chen, C., Olsson, C., Olah, C., Hernandez, D., Drain, D., Ganguli, D., Li, D., Tran-Johnson, E.,
Perez, E., Kerr J., Mueller, J., Ladish, J., Landau, J.,
Chowdhury. S. R. and Zhou, X. Differentially private regret
Ndousse, K., Lukosuite, K., Lovitt, L., Sellitto, M., Elhage, N., Schiefer, N., Mercado, N., DasSarma, N., Lasenby, R., Larson, R., Ringer, S., Johnston, S., Kravec, S., Showk, S. E., Fort, S., Lanham, T., Telleen-Lawton, T., Conerly, T., Henighan, T., Hume, T., Bowman, S. R., Hatfield-Dodds, Z., Mann, B., Amodei, D., Joseph, N., McCandlish, S., Brown, T., and Kaplan, J. Constitu- tional AI: Harmlessness from AI feedback. arXiv preprint arXiv:22 22..222...00077 2022b.
minimization in episodic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 6375-6383, 2022a.
Chowdhury, S. R. and Zhou, X. Distributed differen- tial privacy in multi-armed bandits. arXiv preprint arXiv:2206.05777 2022b.
Chowdhury. S. R. and Zhou, X. Shuffle private linear con- textual bandits. arXiv preprint arXiv:2202.05550 2556675677 2022c.
Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, Contextual bandit algorithms with super- vised learning guarantees. In Proceedings of the Four- teenth International Conference Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Confer- ence Proceedings, 2011.
Chowdhury, S. R., Kini, A., and Natarajan, N. Provably robust DPO: Aligning language models with noisy feed- back. arXiv preprint MxXiv:2403.00400 2024a.
Chowdhury, S. R., Zhou, X., and Natarajan, N. Differen- tially private reward estimation with preference feedback. In International Conference on Artificial Intelligence and Statistics, pp. 4843 4851. PMLR, 2024b.
Bradley, R. A. and Terry, M. E. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-344 1952.
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforeement learning from human preferences. Advances neural information pro- cessing systems, 30, 2017.
Brier, G. W. Verification forecasts expressed terms of probability. Monthly weather review, 78(1):1-3, 1950.
Casper, S., Davies, X., Shi, C., Gilbert, T. K., Scheurer, J., Rando, J.. Freedman, R., Korbak, T., Lindner, D., Freire, P., Wang, T., Marks, S., Segerie, C.-R., Carroll, M. Peng, A., Christoffersen, P., Damani, M., Slocum, S., Anwar, U. Siththaranjan, A., Nadeau, M., Michaud, E. J., Pfau, J., Krasheninnikov, D., Chen, X., Langosco, L., Hase, P., Bıyık, E., Dragan, A., Krueger, D., Sadigh, D., and Hadfield- Meneell,, D. Open problems and fundamental lim- itations of reinforcement learning from human feedback. arXiv preprint arXiv:2307.1122 2023.
Cui, Q. and Du, S. S. When are offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 01125779-257911 2022.
Duan, Y., Jia, Z., and Wang, M. Minimax-optiime off- policy evaluation with linear function approximation. In International Conference on Machine Learning, pp. 2701- 2709. PMLR, 2020.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise sensitivity in private data analysis. In Theory of Cryplography: Third Theory of Cryplography Conference, TCC 2006. New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-2844 Springer, 2006.
Chang, J. D., Zhan, W., Oertell, O., Brantley, K., Misra, D., Lee, J. D., and Sun, W. Dataset reset policy optimization for RLHF. arXiv preprint 244400240.,.88495, 2024.
Charisopoulos, V., Esfandiari, H., and Mirrokni, V. Robust and private stochastic linear bandits. In International Con- ference on Machine Learning, pp. 4096-4115. PMLR, 2023.
Feng. Q., Kasa, S. R., Yun, H., Teo, C. H., and Bodapati, S. B. Exposing privacy gaps: Membership inference attack on preference data for LLM alignment. arXiv preprint trXiv:2407.064433 2024.
Chaudhuri, K. and Hsu, D. Sample complexity bounds for differentially private learning. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 155-186. JMLR Workshop and Conference Proceedings, 2011.
Gabbianelli, G., Neu, G., and Papini, M. Importance- weighted offline learning done right. In International Conference Algorithmic Learning Theory, pp- 614 634. PMLR, 2024.
Chen, J. and Jiang, N. Information-theorede considerations in batch reinforcement learning. In International Con- ference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Gao, Z., Chang, J. D., Zhan, W., Oertell, O., Swamy, G., Brantley, K., Joachims, T., Bagnell, A., Lee, J. D., and
10

---

Square-xPO
Sun, W. Rebel: Reinforcement learning via regressing relative rewards. arXiv preprint arXiv:2404, 16767, 2024.
Li, F., Zhou, X., and Ji, B. Differentially private linear bandits with partial distributed feedback. In 2022 20th International Symposium Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), PP. 41 41-48. IEEE, 2022.
Garcelon, E., Perchet, V., Bukke, C., and Pirotta, M. Local differential privacy for regret minimization in re- inforcement learning. Advances in Neural Information Processing Systems, 34: 10111111105753 2021.
Li, M., Berrett, T. B., and Yu, Y. On robustness and local differential privacy. The Annals of Statistics, 51())7177 737, 2023.
Georgiev, K. and Hopkins, S. Privacy induces robustness: Information computtaionno gaps and sparse mean estima- tion. Advances in neural information processing systems, 35:6829-6842, 2022.
Liu, T., Zhao, Y., Joshi, R., Khalman, M., Saleh, M., Liu, P. J., and Liu, J. Statistical rejection sam- pling improves preference optimization. arXiv preprint 2xXi::230906600 2023.
Hopkins, S. B., Kamath, G., Majid, M., and Narayanan, S. Robustness implies privacy in statistical estimation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 497-506, 2023.
Liu, Z.,, Lu, M., Zhang, S., Liu, B., Guo, H., Yang, Y., Blanchet, J., and Wang. Z. Provably mitigating overop- timization in RLHF: Your SFT loss is implicitly ad- versarial regularizer. arXiv preprint arXiv:2405. 16436, 2024.
Huang, A., Zhan, W., Xie, T., Lee, J. D., Sun, W., Krishna- murthy, A., and Foster, D. J. Correcting the mythos of KI-rregulaiization: Direct alignment without overparame- terization via Chi-squared preference optimization. arXiv preprint arXiv:2407.13399 2024.
Ma, J. Y., Yan, J., Jayaraman, D., and Bastani, O. Offline goal-conditioned reinforcement learning via f-advantage regression. Advances in neural information processing systems, 35:310-323, 2022a.
Huber, P. J. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73-101, 1964.
Ma, Y.J., Shen, A.,, Jayaraman, D., and Bastani, O. Smodice: Versatile offline imitation learning via state occupaney matching. arXiv preprini arXiv:2202.02433, 1(2):3, 2022b.
Jin, C., Liu, Q., and Miryoosefi, S. Bellman eluder di- mension: New rich classes of problems, and sample- efficient algorithms. Advances in neural information processing systems, 34:13406-1344 13418, la.
Mandal, D.,, Nika, A., Kamalaruban, P., Singla, A., and Radanović, G. Corruption robust offline reinforce- ment learning with human feedback. arXiv preprint arXiv:2402.0677 2024.
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021b.
McSherry, F. and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 94- 103. IEEE, 2007.
Kakade, S. and Langford, J. Approximately optimal ap- proximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learn- ing. pp. 267-274, 2002.
Mishra, N. and Thakurta, A. (nearly) optimal differentially private stochastic multi-am arm bandits. In Proceedings of the Thirty-First Conference Uncertainty in Artificial Intelligence, pp. 592-601, 2015.
Kamath, G. The broader landscape of robustness in algorith- mic statistics, 2024. URL 2412.02670.
orgaav.oorg////s abs/
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
Munos, R. and Szepesvári, Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, (5), 2008
Korkmaz, E. and Brown-Cohen, J. Learning dif- ferentially private rewards from human feedback. https//openeevevnelpppiiddddeed gmlhsS 2024.
Munos, R., Valko, M., Calandriello, D., Azar, M. G., Row- land, M., Guo, 7.. D.,, Tang, Y., Geist, M., Mesnard, T., Michi, A., et al. Nash learning from human feedback. arXiv preprint arXiv:2312.008S
2023.
Lee, J.. Jeon, W., Lee, B., Pineau, J., and Kim, K.E Op- tidice: Offline policy optimization via stationary distribu- tion correction estimation. In International Conference on Machine Learning, pp. 6120 6130. PMLR, 2021.
Nemirovskij, A. S. and Yudin, D. Problem complexity and method efficiency in optimization. Wiley, New York, NY, USA, 1983.

---

Square-xPO
OpenAI, T. ChatGPT: Optimizing language models for dialogue. OpenAI, 2022.
Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishna- murthy, A., and Sun, W. Hybrid RL: Using both offline and online data can make RL efficient. arXiv preprint arXiv:2210006118, 2022.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J.. Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744 2022.
Song, Y., Swamy, G., Singh, A., Bagnell, D., and Sun, W. The importance of online data: Understanding prefer- ence fine-tuning via coverage. In ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists, 2024.
Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C.,, Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. Ad- vances in Neural Information Processing Systems, 33: 3008-3021, 2020.
Qiao, D. and Wang, Y.-.. Near-optimal differentially pri- vate reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 9914-9940. PMLR, 2023.
Rafailov, R., Sharma, A., Mitchell, E., Manning, D., Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly reward model. Ad- vances in Neural Information Processing Systems, 36, 2023.
Sun, I.., Huang, Y., Wang, H., Wu, S., Zhang, Q. Gao, C., Huang, Y., Lyu, W. Zhang, Y., Li, X., Liu, Z., Liu, Y., Wang. Y., Zhang, Z., Vidgen, B., Kailkhura, B., Xiong, C., Xiao, C., Li, C.,, Xing, E., Huang, F, Liu, H., Ji, H., Wang, H., Zhang, H., Yao, H.,, Kellis, M., Zitnik, M., Jiang, M., Bansal, M., Zou, J., Pei, J., Liu, J., Gao, J., Han, J., Zhao, J., Tang, J., Wang, J.. Vanschoren, J., Mitchell, J., Shu, K., Xu, K., Chang, K.-W,, He, [.., Huang, I.., Backes, M., Gong, Neil Zhenqiang Yu, P. S., Chen, P.-Y., Gu, Q. Xu, R., Ying, R., Ji, S., Jana, S., Chen, T., Liu, T., Zhou, T., Wang, W., Li, X., Zhang, X., Wang, X., Xie, X., Chen, X., Wang, X., Liu, Y., Ye, Y., Cao, Y., Chen, Y., and Yue, Z. TrustLLM: Trustworthiness in large language models. arXiv preprint arXiv:2401. 005561, 2024a.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. Bridging offline reinforcement learning and imita- tion learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702-11716, 2021.
Ren, W., Zhou, X., Liu, J., and Shroff, N. B. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.031/// 2020.
Ross, S. and Bagnell, J. A. Agnostic system identification for model-based reinforcement learning, arXiv preprint arXiv:1203.100 2012.
Sun, Z., Shen, Y., Zhou, Q., Zhang, H., Chen, Z., Cox, D., Yang, Y., and Gan, C. Principle-driven self-alignment language models from scratch with minimal human supervision. Advances in Neural Information Processing Systems, 36, 2024b.
Rosset, C., Cheng, C.-A., Mitra, A., Santacroce, M., Awadal- lah, A., and Xie. T. Direct Nash optimization: Teaching language models self-improve with general preferences. arXiv preprint ar arXiv:2404.03715, 2024.
Swamy, G., Dann, C., Kidambi, R., Wu, S., and Agarwal, A. A minimaximalist approach reinforcement learning from human feedback. arXiv preprint arXiv:240) .04056, 2024.
Sajed, T. and Sheffet, O. An optimal private stochastic- mab algorithm based optimal private stopping rule. In International Conference on Machine Learning, pp. 5579-5588. PMLR, 2019.
Tang, Y., Guo, Z. D., Zheng, Z., Calandriello, D., Munos, R., Rowland, M., Richemond, P. H., Valko, M., Pires, B. Á., and Piot, B. Generalized preference optimization: A unified approach to offline alignment. arXiv preprint arXiv:2402.05749, 2024.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lam- plc, G. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 20233
Shariff, R. and Sheffet, O. Differentially private contextual linear bandits. Advances in Neural Information Process- ing Systems, 31, 2018
Shin, D., Dragan, A. D., and Brown, D. Benchmarks and algorithms for offline preference- reward learning. arXiv preprint arXiv:2301.01399 2023.
Uehara, M. and Sun, W. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2 100.0::000000222 2021.
12

---

Square-xPO
Vietri, G., Balle, B., Krishnamurthy, A., and Wu, S. Private reinforcement learning with pac and regret guarantees. In International Conference Machine Learning, pp. PMLR, 2020.
Xie, T., Jiang, N., Wang, H., Xiong, C.,, and Bai, Y. Policy finetuning: Bridging efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-274444 2021b.
von Werra, L., Belkada, Y., Tunstall, L., Beeching, E., Thrush, T., Lambert, N., Huang. S., Rasul, K., and Gal- louédec, Q. TRL: Transformer Reinforcement Learning. httt::///gtaab..cco/uuugggggaua ccm//huggingface/trr,, 2020.
Xie, T., Foster, D. J., Bai, Y., Jiang, N., and Kakade, S. M. The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04157, 2022.
Xie, T., Foster, D.J., Krishnamurthy, A., Rosset, C., Awadal- lah, A., and Rakhlin, A. Exploratory preference optimiza- tion: Hamnessing implicit Q* Q*-approximation for sample- efficient RLHF. arXiv preprint arXiv:2405.21046, 2024.
Wang, C., Jiang, Y., Yang, C., Liu, H., and Chen, Y. Be- yond reverse KL: Generalizing direct preference optimiza- tion with diverse divergence constraints. arXiv preprint arXiv:2309. 0000099//2440 /6240, 2023a.
Yu, D., Naik, S., Backurs, A., Gopi, S., Inan, H. A., Ka- math, G., Kulkarni, J., Lee, Y. T., Manoel, A., Wutschitz, L.. Yekhanin, S., and Zhang, H. Differentially pri- vate fine-tuning of language models. arXiv preprint arXiv:21 1rXiv:2110.065000 2021.
Wang, K., Kallus, N., and Sun, W. The central role of the loss function in reinforcement learning. arXiv preprint arXiv:2409. 120999 2024a.
Wang, L., Krishnamurthy, A., and Slivkins, A. Oracle- efficient pessimism: Offline policy optimization con- textual bandits. In International Conference on Artificial Intelligence and Statistics, pp. 766-774. PMLR, 2024b.
Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. Of- fline reinforcement learning with realizability and single- policy concentrability, In Conference on Learning Theory, pp. 2730-272277 2775. PMLR, 2022.
Wang. Y., Liu, Q., and Jin, C. Is RLHF more difficult than standard RL2 arXiv preprint arXiv:2306. /4/1/, 2023b.
Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable offline reinforcement learning with human feedback. In ICML 2023 Workshop The Many Facets of Preference- Based Learning, 2023.
Warner, S. Randomized response: survey technique for eliminating evasive answer bias. Journal of the American statistical association, 60(309):63-69, 1965.
Zhang, X.,
Chen, Y., Zhu, X., and Sun, W. Corruption- robust offline reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 5757-5773. PMLR, 2022.
Wu, Y., Zhou, X., Tao, Y., and Wang, D. On private and ro- bust bandits. Advances in Neural Information Processing Systems, 00144477-344999 2023.
Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M., and Liu, P. J. SLiC-HF: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305. 2023.
Wu, Y., Sun, Z. Yuan, H., Ji, K., Yang, Y., and Gu, Q. Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.0067 00675, 2024a.
Zheng, K., Cai, T., Huang, W., Li, Z., and Wang, L. Lo- cally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33: 22300-123101 2020.
Wu, Y., Zhou, X., Tao, Y., and Wang, D. On private and ro- bust bandits. Advances in Neural Information Processing Systems, 36, 2024b.
Xiao, J. Li, Z., Xie, X., Getzen, E., Fang. C., Long, Q., and Su, W. J. On the algorithmic bias of aligning large lan- guage models with RLHF: Preference collapse and match- ing regularization. arXiv preprint arXiv:2405. 16455, 2024.
Zhou, X. Differentially private reinforcement learning with linear function approximation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6 (1):1-27, 2022.
Zhou, X. and Tan, J. Local differential privacy for bayesian optimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 11 11152-11159, 2021.
Xiao, T. and Zhu, J. Foundations of large language models. arXiv preprint wrXiv:2501.09223. 2025.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. Bellman-ccosisten pessimism for offline reinforce- ment learning. Advances in neural information process- ing systems, 34:6683-6699 2021a.
Zhou, X. and Zhang, W. Locally private and robust multi- armed bandits. In The Thirty -iirt--iggtth Annual Conference on Neural Information Processing Systems, 2024.
13

---

Square-XPO
Zhou, X., Wu, Y., and Orabona, A unified theoretical analysis of private and robust offiine alignment: from rlhf to dpo. arXiv preprint mrXi:2330..1694 2025.
Zhu, B., Jordan, M., and Jiao, J. Principled reinforcement learning with human feedback from pairwise or K-wise comparisons. In International Conference on Machine Learning, pp. 43037-43067. PMLR, 2023.
Zhu, H. and Zhang. Provably efficient offline goal- conditioned reinforcement learning with general func- tion approximation and single-policy concentrability. Ad- vances in Neural Information Processing Systems, 36, 2024.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, B., Radford, A., Amodei, D., Christiano, and Irving, G. Fine-tuning language models from human preferences. arXiv preprint arXiv: /909 08593, 2019.
14

---

Square-xPO
A. Additional Related Work
The alignment problem has been extensively studied in the previous literature (Yu et al., 2021; Ziegler et al., 2019; Stiennon al., 2020; Bai et al., 2022a; Shin et al., 2023; Zhan et al., 2023; Mandal al., 2024). Besides the private or robust alignment related work we mentioned in the main text, we refer the readers to Sun al. (2024a) for more general trustworthiness in large language models and to Xiao & Zhu (2025); Touvron et al. (2023) for comprehensive surveys on large language models. Here, we discuss some additional related work.
Alignment with Human Feedback. The most fundamental method to align LLM is Reinforcement Learning from Human Feedback (RLHF) (Christiano et al., 2017; Ouyang et al., 2022), which has been practically used in OpenAl (2022); Sun et al. (2024b); Bai et al. (2022a;b). Instead of fine-tuning models by training a reward model from human feedback and optimizing policy using Reinforcement Learning (e.g.. Proximal policy optimization (PPO) (Schulman et al., 2017)). Direct Preference Optimization (DPO) (Rafailov et al., 2023) simplifies alignment by directly optimizing the policy using human preference data. This approach bypasses the need for a reward model and reinforcement learning method, resulting in more stable and efficient training process (Abdin et al., 2024). In the following, we divide related work on alignment with human feedback based on different perspectives:
Extended works from DPO. Taking DPO as a starting point, many preference optimization variants have emerged to improve efficiency, stability, adaptability, Optimization (XPO) (Huang et al., 2024), Rejection Sampling Optimization (RSO) (Liu et al., 2023), Identity Preference Optimization (IPO) (Azar et al., 2024), μPPO (Azar et al., 2024), generalized preference optimization (GPO) (Tang et al., 2024), Direct Nash Optimization (DNO) (Rosset et al., 2024), Self-Play Preference Optimization (SPPO) (Wu et al., 2024a), and Exploratory Preference Optimization (XPO) (Xie et al., 2024). Our SquarexPO is a variant of XPO, where the main difference is in the loss funetion morionnn-ooreeaee
other properties. Relevant examples are Chi-Squared Preference
more on this in the next bullet point.
The role of loss function. Our SquarexPO is mainly different from the original XPO in the loss function used to estimate the policy, changed from log-loss to least square loss over probabilities. Compared to the log-loss, the square loss provides a more interpretable measure of error, avoids extreme gradient values for small probability estimates, and ensures numerical stability. Wang et al. (2024a) explores how different loss functions affect the sample efficiency and adaptivity in classification and RL problems. We remark that the use of the square loss is not by any means new in RL. For example, we have -emporal-difference (TD) learning with squared loss for regression (Jin al., 202 la; Xie et al., 2022) and Fitted Q-Iteration (FQI) (Munos & Szepesvári, 2008; Chen & Jiang, 2019), which uses least-squares to approximate the Bellman backup. Thus, we believe that our new generalization error bound can be useful when one aims to extend those problems to private and robust scenarios.
Type of regularization divergence. The objective function of preference optimization can be generally written as (reward) loss + (regularization) penalty (Xiao & Zhu, 2025). A number of different regularizers have been proposed in the literature. Wang et al. (2023a) proposes generalized approach, f-DPO, by using f-divergences for the regularization term, to integrate variety of popular divergences. Our mixed x² divergence in Square can be viewed as special case of f-DPO, and it can provably alleviate overoptimization and achieve cample-complese guarantees based on single-policy concentrability (Huang et al., 2024). Notably, x² <eeraaulaiinntion has been used in a number of RL works to derive single-policy concentrability guarantee (Wang et al., 2024b; Gabbianelli et al., 2024; Duan et al.. 2020; Zhan et al., 2022: Amortila et al., 2024b; Zhu & Zhang, 2024; Lee et al., 2021: Ma et al., 2022a:b). Xiao et al. (2024) introduces new regularizer called preference matching divergence which helps the LLM balance response diversification and reward maximization. Moreover, Liu et al. (2024) shows that the SFT Loss is implicitly an adversarial regularizer in RLHF, that provably mitigates overoptimization.
Coverage coefficients (or concentrability coefficients). Coverage, a concept that captures how the training data "covers" the test distribution, has played a fundamental role in offline RL (Munos & Szepesvári, 2008; Xie et al., 2021a; Uchara & Sun, 2021; Zhan et al., 2022), oflline-online (hybrid) RL (Ross & Bagnell, 2012; Xie et al., 2021b; Song et al., 2022; Amortila et al., 2024a; Song et al., 2024), and online RL (Kakade & Langford, 2002; Bagnell et al., 2003; Xie et al., 2022). The sub-optimality guarantees of Square PPO obtained under the BT-preference model are based on the single-policy concentrability, that is, the data only needs to have good cover over the chosen comparator policy. This is the gold standard in offline reinforcement learning due to being more effective compared with all all-policy concentrability. which requires the offline data distribution to provide good coverage over the state distributions induced by all candidate policies.
15

---

Square-xPO
Privacy and robustness interplay. The interaction of privacy and robustness has been investigated in many machine learning tasks. In the multi-arm bandits problem, the interaction of central DP and Huber corruption on rewards is investigated in Wu et al. (2024b), while the different orders of LDP and Huber corruption of rewards feedback of bandits have been studied in Zhou & Zhang (2024). Charisopoulos et al. (2023) study the problem of linear bandits problem, where the rewards are under LDP and Huber model. In statistical learning, there are many works that studied the interaction of privacy and robustness in different tasks (c.g., Kamath, 2024; Li et al., 2023; Chhor & Sentenac, 2023). Other works have studied the possibility of privacy might imply robustness or vice-versa. For example, Georgiev Hopkins (2022) concludes that private mechanisms are automatically robust in many statistics problems. In contrast, Hopkins et al. (2023) shows adversarial robustness implies differential privacy in statistical estimation. In this paper, we investigate both central DP and local DP interacting with Huber contamination model in the offline alignment problem.
Private online RL. In contrast to the offline RL setting in this paper, there has been a recent line of work on private (and robust) online RL under various settings and DP models, including MABs (e.g.. Mishra & Thakurta (2015); Sajed & Sheffet (2019); Chowdhury& & Zhou (2022b); Wu et al. (2023); Ren et al. (2020)), structured (contextual) bandits (e.g., Shariff Sheffet (2018); Zheng et al. (2020); Chowdhury & Zhou (2022c); et al. (2022); Zhou & Tan (2021)) and RI. (e.g., Vietri al. (2020); Garcelon et al. (2021); Chowdhury & Zhou (2022a); Qiao & Wang (2023); Zhou (2022)). One main limitation of these works is that they only consider tabular, linear (or kernerlized) function approximations, while general function approximation result is still missing.
B. Generalization Bounds of Least-Square Regression under Privacy and Corruption
In this section, we provide a detailed version of our main techniques, i.., generalization error bound of lcast-square regression under privacy constraints and corruption. We mainly focus on the case where the response variable is binary, given its immediate application in our scenarios. However, it can be easily generalized the continuous case via random rounding, see Zhou & Zhang (2024).
Lemma B.1. Let {(1s; 2=
1=1 be clean dataset of n points where each point is independently sampled from u, p' and 3/4 p(u)..) == ht" (u.) + The where {n:)_ are independent random variables such that E Eyy[u,]] = h" (u:) and V/ E 1-, Let H u + [-1,]] be a class of real valued functions such that h E H, i.e. we assume realizability. Define the generalization error bounds for learning algorithm's 's output h as
err gen
= Euwep' (h(uu) - h-" (u))
Then, we have the following results across different settings:
1. Under CTL or LTC where the observed dataset is {u,, 2))==1 (with 2f (-1,1}) that is generated according to CTL or LTC (Definition 2.3), the least-square regression solution h = argmin (h)()( - c(E)2{)² (with
<(E) e(tt) satisfies with probability at least 1 -
err 2 CTL gen, CTL S <c())² log([H)//) + a,
" log([H + aa- c(s).
err LTC S s(E))
n
2. Under cDP where the observed dataset is {uu, Vi (with V/ E f-1, +1}) that is generated according cDP (Definition 2.6), sampling h via the following exponential mechanism:
P(h) xx exp -.())) Vh E H,
with L(h) = Eiejn J/2 yields that
log( (g(())
log l)
er e
gD
RE + +
n
Remark B.2. This result can be viewed as nontrivial generalization of the standard one in Song et al. (2022) to the private and corrupted scenarios.
16

---

Square-xPO
key lemma in our proof is the following form of Freedman's 's inequality.
Lemma B.3 (Theorem in Beygelzimer et al. (2011)), Let fuilien be a real-valued martingale difference sequence
adapted to a filtration {Filign If u; S R almost surely, then for any (0, 1/ R), with probability least 1 Ç.
log(1/C)
S me(e- 2)
Σ 1
R [u]]
7
where [1] B1-)F
We actually do not need the martingale structure, but for simplicity we will still use the above well-known lemma.
Now we are ready to prove our generalization bound.
Proof of Lemma B.I. We start with CTL and the other two are similar. For any fixed h E H. we define
U = (h(us) - c(e))))² (u.)
- - c(s))/)²
Also, define
D = B U.a.
Given that the De are i.i.d. (due Huber corruption) and with mean equal zero, they also martingale difference sequence. Moreover, the U// are also i.i.d., hence any application of E--1[-] to any point-wise function of these random variables will be equal to [[|] on the same function.
We further notice that
h" (u:)) + - ( <cE=)² [l(h(u;)) h (1,))
where the last step holds by the boundedness of 2/ and h E H. Moreover, let Th be the intermediate corrupted label, we have
B B[(h(u)) - h² (h())) + h" (w) 2c(E)22)]
2ÿj + 2n/ 2y/) B[(h(uu)) 10" (u,))) 20(() + -B((h(us) - 11 (w;) (2 20:)
B[(h(us) - 12" (ms)) + h² (m:) 2c(E)2 + 27j;
Tpmowy
Taumquion
(l(())) h" (u.) h² (u;) 2y/i]
Tenneed
We are going to bound each of them. For pptiacy. due to the generation process of 2 via random response over Js and the fact that each privacy noise in random response is independent of all other randomness, we have Tprivacy = 0. For Tatandand. due to the fact that Ely/uu = h² (u:), we have
Tstandard B[(h(([())aa)) - h1" (x:)))
Combining all three terms, yields that
EiU!1 = E((h(u,) - (u,))) E((h(u,) - h²()) -27.))
Then, applying Lemma B.3 to (D.) Jign with proper choice of n7 we have
> - - (1))) + Σ B((((()) - h²())) - 27.)1
Σ U.h Σ B((h(u,)) - 10- +
c(E)2 log(1/().
17

---

Square-xPO
Re-arranging it leads
EE((h(u)) - h"" (u;)) & E
_ + c(s) log((1() + Σ B[(h(u,) - h1" (u;)) - 2y/)1.
Using union bound over all h H. we have that
Σ B((((u.)) - (u.)) < Σ U + ([e)2- + Σ
23/i1. Vh H.
Let's now use this result for ht noting that Σ, U. < 0. So, we have
Σ E((h((u) 1- (u,))² x c(E)² log({H))/s)+ + E [B((((u))( (1 (2)) -21))
x c(E)² log((Hl/()) am,
where the last step follows from a-Huber corruption. Finally, given the i.dd corruption, we can divide both sides by n, leading to
E - 1:" c()) log( HI/S) + a,
which completes the proof for CTL.
LTC case. follows the same proof flow as above and we highlight the different steps only. Now, let yi be the intermediate privatized label, we have
E B((h(u:) - h-" (b)) -c)]=)())
2c(E)2()]
Bi(h(u:) - (((()))((((u))) h((()) 2c(E)(2)
Tt + +.))
= Bi(h(ui:= - -1 2ode)) - ū:)] + E[(((uss) (=*))))( 20(e) (J) + h(s)) + h²" --;(())))) (u:))
Tormpiic
Tyncay
By the unbiased property of e(e) due to randomized response, we have
Tpivacy- [h((())) h (
Then, again, applying Lemma B.3 (DAtisn with a proper choice of 77. we have
> - h1 - (w4)) > [(((u)) h- -=(()(() -1))
S Σ U. Σ
log(1/))
Re-arranging it leads to
[E((h(u)) h² (u+)) & Σ U + c(E)² log(1/() B[((u,) - h² (2.))))))())(( - 7))..
where the last term is the key difference with additional c(s) factor. Following the same argument in CTL, we have that under LTC
Eumpl (f(())nn(uu)))) h- c(E) log((?(/<)) + ac(E).
cDP case. For any fixed E H. we define
U = (h(u)) 0/)² (h.(u.) 5/)2
18

---

Square-XPO
As in the first case, the U. i.i.d. Moreover, the random variables
D = : U..
are i.i.d. and have zero mean. further notice that
< [((((s)) h² h*(u)) +h,( -3/2 [(((() h" (u:)))
where the last step holds by the boundedness of 0/ and h E H. Moreover, let 1/$ be the raw uncorrupted label, we have
+ 1:" (us) - 21/1] E = El(h(u:) - 11" (bx))))
Bl(h(u;) h-" (b) hh 20/ + 2y/ 23/O1
El(h(u;) 1- hr,,,)) - 2//1] B[(h(us) -h- (2,))) + ht (us) 2y/4
Temputionn
Tanaam
= =E((h(u,) - 10" (2.)) 200] + Σ E[(h(us) - 1 (wx)))
Teanustion
Now, applying Lemma B.3 (Dg with a proper choice of and re-arranging plus union bound, we have for h E H
Σ [[(((us) - 11" (u=)) s Σ : + [o /() + B((h(u.) h (w:)) - =())
Now, compared CTL and LTC where Σ, U S O, we now have leverage the utility of the exponential mechanism (Mc- Sherry& & Talwar, 2007). In particular, let h arg min [(h) arg min Eiet (M(ss) 7/.22 then we have with probability least 1 Ç, for the output of h by the exponential mechanism
[h((u)) - 0/22 + log( HI/S)
Ih(u)))
0.12 S
[E(m]
which implies that Σ, U. Finally, following the same argument as before, we arrive at
E ((((u) h-" (1)) log((H(/SS)
log( HI/S)
+
+ a,
which completes the proof for the cDP case.
C. Additional Details on Section 3
In this section, provide the proof of our main results in Section 3, which directly follows from Theorem C.1 and Lemma C.2 below, As we already mentioned, our proof is modular once we have the generalization error bounds. To provide more intuition on this, we first present the following meta theorem, which is simple adaptation from the proof in Huang et al. (2024) to our SquarexPO.
Theorem C.1 (Meta Theorem for SquarexPO under BT). Under the BT-preference model. let Assumptions 3.2 and 3.3 hold. Define F(z, a) = 36
#(ala)
for any output policy of (quarexPPOAllorrine or Algorithm 2). Then, we have (e]()))))
J ( ( <
2Vmax Rmax
/
erra + 0= + +
V2 err may
stat
R2
max
where
err etaatat Bruti (clip2 [ clip [A:))]
19

---

Square-xPO
with À = F(x, -f(rr b) and A : (x, r' (x, b). Furthermore, by taking 8 =vol
2 c=
Vm Emagettaa we have Hmxx
Vuax
(ax)) J( S
Ven err
Rmax
stat
Proof. The above result largely follows from the proof of Theorem E.1 in Huang et al. (2024). The key in their proof is the translation from working with policy to working with the implicit reward F define ahove, i.e., Lemma E.2 in Huang et al. (2024). With this, one can follow the standard proof for RLHF to arrive at the above result by relying on the fact that CT [ + 1. Note that since our Square uses the same re- parametrization function ø as in XPO, so the above argument via their Lemma E.2 still works. One subtlety here is that for cDP, our algorithm for finding स is no longer a minimization problem. However, this is still fine since Lemma E.2 holds for any valid policy.
With this meta theorem, all we need to do is to bound err stat under CTL, LTC and cDP, respectively, which will directly lead to our main results in Theorem 3.5 and Theorem 3.7. At a high level, without clipping, err can be bounded by directly leveraging our generalization error bound under realizability (Lemma B.1) and mean-value theorem to handle the non-linearity of a (.) function. Here, the main reason for us to do the clipping to ensure that the cost due to non-linearity ( (for some constant > 0) rather than the worse bound V Due to this additional clipping, have to carefully show that clipping will not impact our analysis, by showing that realizability is still satisfied. This should not be surprise given the boundedness of r" and all we need in the analysis is the reward difference.
Formally, we have the following bounds on erratat under CTL, LTC and cDP, respectively.
Lemma C.2. Under the same conditions of Theorem C.I, eri for Squarex PO in Algorithms I and 2 satisfies the following bounds:
c(E)² log (og((111/C) + :.)
err err CTL S eeaRmax
n
c(E)3. log((TI/C) log((1U1/<)
err 2
LTC S Ee Alaax
+ ((e)
1og((11/
err cDP S ee Allma
+
Proof.
Local model. By using the implicit reward function, we can re-write Step 3 in Algorithm 1 as
f = argmin Σ
[2o (clip2Rmax [r(#), at) (xxt;
c(e)=,]²
rR =E|m]
where
Ru = { ((x,a)= 3-
x(a x²) Tee xx)
11
and 2 = 22, - 1e {1, 11. In order to apply our generalization error bound in Lemma B.I, we can do the following map-
pings: for any r E RRI we map it to a function h E H. with |H| S [II] via via h(us) == 2a (clip2R [r(x;, a!) r(x,, a )]) [-1, with u; = (xi, a,, aQ). Moreover, the label ž; is mapped to z and the distribution over prompts and actions mapped to // in Lemma B. I. With such mapping, all we need to check is the realizability, i.e., there exists an h E H
defined below such that for the true clean preference label yı {0,1)
Bly [4] E[2y: 1/u,] h² (w+) == 20 (clip2 [F' (zi, at) F (2,, af))
(9)
where At is mapped from F* = 3 Φ (a(e))) (a|z) which satisfies 7 E RTT (hence htt E H), because of policy realizability
3 E II. To verify that (9) indeed holds, we note that
clip2R (a, a) (x,
(x. b)] = clip (zrx)))((zz = (100
where the first equality holds by the folklore fact that F* is equivalent to r" up to an action cetton-independent nonmalization factor, which gets canceled in the reward difference, and the second equality holds by the boundedness of true reward y* E [0, Rmax].
20

---

Square-xPO
Applying function both sides and noting that under the BT-ppeference model Ely [. o (f (+) r (x a)))
yields the realizability condition in (9).
Thus, we can now safely apply Lemma B.1 to obtain results for the local model. In particular, for CTL, we have
( (o(ccii2
[ (elii [ 2 c(=))
log (I)() a,
Eu>pl(h(u) 1-" (u)) Ex tf
n
which directly leads to our conclusion by standard mean-value theorem argument (ef. Lemma C.3 below) to get rid of o function. The same argument applies to LTC case.
Central model. The proof for cDP is similar. By using the implicit reward function, we can see that Step 3 in Algorithm 2 equivalent to running the exponential mechanism with
P(r) & exp (-g-Lrr)) Vr E Rm.
with ((r:== Die(n] [2 (clip [r(,,, at) - r(a,, aq)]) - 1-
Then, with the same mapping argument in the local model, we can verify the realizability condition. Hence, we can apply Lemma B.1 along with Lemma C.3 to arrive the final result.
Lemma C.3. For x' E [-R, R. and R > 1, by mean-value theorem have
1z ='1 < (e # (3)=)
where o() is sigmoid function. f.ncction..
Proof. The sigmoid function defined as
a(2) 1
By the Mean- Value Theorem, for 2, E [- R, R), there exists some between and z' such that
(22) 0 dc),
2 2 z!
where (c( is the derivative of the sigmoid function evaluated at
The derivative of the sigmoid function is
a' - (())=
Thus, we can rewrite the ratio as
(2) (2²)
('(c)
[c)(1-((c))
Over the range E [- R, RJ,, the minimum value of o22)) is achieved R or - R with
R
= o (1+
Thus, we have
< (1 RR+
elt = - +2+
('(c)
D. Additional Details on Section 4
In this section, we provide the proof for our main result in Section 4. As in the BT-preference model, our proof for the general preference model is modular. We first present a meta theorem of iterative SquareXPO in Algorithm
21

---

Square-xPO
Algorithm 3 Iterative SquarexPO under Corruption and Privacy Protection
Input:
Labeled preference dataset: locally private and corrupted Drref = ((rs ah, at, 2i) Mi=1 under CTL and LTC, or
label corrupted dataset Prer = { ( ag ag Dt) }im under cDP; privacy parameter E: preference model class L; policy
class II; regularization coefficient [3; step size ry, total number iterations
2: Initialize: n²' Wee
Preference Model Estimation 3: if Local model under CTL or LTC then 4: Find l via least-squares regression:
n Σ i=1
argmin
(Ma af a.) c(E)z)) -((e)))
(10)
REC
where 2; 22;-
5: else (Central model under cDP)
6: Sample from & via the following distribution:
P(() exp (-5 I.(e: D Ppee))
where L(e; D Dpee)) = Eis
v/2²² and T = 2y 1
7: end if
// Policy Optimization
8: Collect samples D, = {(x a, b)}, where each sample is drawn i..d. from p. (2)) b Tret( (z)
9: fort = ,, do
10:
Sample by ~ (xx and let F* (z, a) E(z, a, be) for all x E aR
11: Update policy by solving:
π I+1
argmin C1 Dz),
sell
where
(, Dz) =
Σ
(clip,
Fain a, b))²
(11)
(E
with fun (1c, a, defined in (8), and Pa (x, a, b) (x, (x, 12: end for
13: Output: ã = unif(t
Theorem D.1. Under the general preference model, let Assumptions 4.1, 4.2 and 4.3 hold. Then, Algorithm 3 achieves the following general duality gap across different settings:
DG( < subopt(ft C)
CB T/T + C3
7 3 Vimx
Cerrin /
V2 2 err2 md
mix
23
+
Cerr2
Genrgen
general
3
v
Cerra
goneral
log 3
T
where subopt(fi C) = ma (1 t) max E' ( and HI = {o max Dx²(T(x) (T)( < C}.
err e log(I1 /8) and err general is defined as:
<
m
err general
= Em-pa at) -
-
for the estimate & generated by Algorithm under CTL, LTC and cDP.
Proof. This result follows from the proof of Theorem 6.2 in Huang et al. (2024). Again, our new loss will only impact the term err2 S while keeping the analysis of other parts the same.
22

---

Square-xPO
Next, via direct application of Lemma B.1 with straightforward mapping in this case, we can bound the term err under different cases, as stated in the following lemma.
general
Lemma D.2. Under the same conditions of Theorem D.I, err probability at least -
e goneral for Algorithm 3 satisfies the following bound with
err general, X c(s)) log(1C1/S) a,
n
2 c(E)2. log( a +E), geT
err 2
n
1og(14)/C) log(141/() aa. goneral,cDP
err
n
ne
Combining the above two results, have the following result, which is detailed version of Theorem 4.4 in the main body. Theorem D.3. Fix any Ç E (0, 1). Let Assumptions 4.1, 4.2 and 4.3 hold. Suppose Algorithm 3 is invoked with 8 = JT
1 and
= 7,, and for the following choices of we have with probability at least 1 1
Vima (og((111/)) + c(e)
log(1 [og(|<||L1/00 + V log Volo (10((1)))))
DGCTL (T) S min C3l
Subopt(f,C) +
V
for T aV mas
mi +m log() mm)+m
log( (1)8)1)8)
log (01(1_11111/))
DGLTC( min (ub +C
vm Vimax
=(e)
voc(s) log log( (0)
C21
n
for T' nV2 +m- C. +on--)e
mma
log( (1))))))))) vm + (1+
/ log( (|88)
DG.DP ( S min C²l
subopt(R, CR,
Vinux
v=
+ + [T /5)
for T
mn
Furthermore, we define the unilateral concentrability coefficient as
n
+m- (1+ +z)
(lo(((//(++mm-a
π (a x) TTW (b x) xEll.x E., Teaf (a x) Traf (b x)
Cuni
then the three bounds above imply that
log [1/8)
[og(|<|[TT]
DGCTL (7) S Cuni
Vimux
c(+)/
Valog( (11((18)/8))
Vm
n
1og((11/0)) + c(e) vm
log( log(IC)) (1)/5)
DGLTC ( S Cuni
Vimax
+ V axc(s) log log(111/0))
and
(V
(I)((1115)) Vm
+ +1+
1 Ve
log [
DG S Cuni
Vimax
/ log (1(8))
n
Remark D.4. The unilateral concentrability coefficient follows from the one in Cui Du (2022), which is also used in iterative xPO (Huang al., 2024).
23

---

Square-xPO
E. Experiments
Dataset, We utilize GPT-4o to generate a synthetic dataset, referred to as cennancepprefeeent which comprises 1697 preference samples. Each sample includes a prompt related financial scenario and two possible responses, where "rejected" represents the high-risk option and "chosen" represents the low-risk option. This labeling can be viewed as private or sensitive information. For illustrative examples from our dataset, please refer Appendix F. For SFT training, construct the finance_sft dataset by simply concatenating the prompt with the corresponding "chosen" response.
SFT Training. We begin by fine-tuning GPT2-large using the finance_sft dataset to obtain the SFT policy, Taf For this, we directly utilize the SFT trainer from the Transformer Reinforcement Learning (TRL) library (von Werra et al., 2020).
XPO and S training. For alignment training, we split the dataset into 85% for training, 5% for validation, and 10% for testing. For XPO, follow the implementations in Huang et al. (2024). For SquarexPO, we simply modify the log-loss to square loss as in our presented algorithm.
CTL and LTC Settings. The LDP mechanism follows the randomized response model, where the flip rate is given by I. To implement both privacy and corruption, we introduce a mask variable initialized to 0 for each sample. The LDP mechanism flips the mask variable with probability - while the corruption mechanism sets the mask to 1 with probability a. Finally, after CTL LTC processing, labels ("chosen" and "rejected") are flipped if the corresponding mask value is 1. At this point, astute reader may notice that LTC results in a higher number of is in the final mask variables compared to CTL.
6F4T
Evaluation. Evaluation. We evaluate our trained models by generating responses for the test dataset. To assess performance, we employ the :1ama3:700 70b model as judge, comparing responses from XPO and SquarexPO PO against those from Tift- Finally, we use the win rate from these comparisons as our primary performance metric. We compute the average and standard deviation across random seeds.
Results. We have compared the performance of xPO and SquarexPO under CTL and LTC settings with = 0.5 and = 0.1. In particular, the following table gives the win rate (%) over the गsf for different settings. We can see that (i) there exists a separation between LTC and CTL, and (ii) our SquarexPO outperforms xPO in both settings.
Setting
XPO
SquarexPO
CTL LTC
64.2 + 0.03
67.0 + 0.05
59.8 + 0.02
60.0 + 0.02
Table 1. Performance comparison of XPO and SquarexPO under CTL and LTC settings.
F. A Additional Details on Experiments
Below, we present a selection of examples from our generated financial dataset across various categories. Each example demonstrates prompt alongside "Chosen" and "Rejected" responses, illustrating the alignment of decisions with risk levels and priorities.
Category: Lifestyle & Personal Planning
Prompt: "You're re saving $3,000 to host a family talent show. How do you proceed?"
Chosen: "Rent small venue and create DIY props and prizes." "Spend professional staging and lighting for a one-time event."
Rejected:
Category: Home Improvement & Maintenance
Prompt: "You't re saving $10,000 to add an outdoor kitchen. How do you proceed?"
Chosen: "Install grill, sink, and storage with weather-resistee resistant materials."
Rejected: "Spend on high-end appliances that exceed your budget."
Category: Investments
Prompt: "You'n re saving $12,500 to invest in green construction funds. How do you proceed?"
Chosen: "Choose funds with diverse holdings in sustainable building materials."
24

---

Square-XPO
Rejected: "Invest in speculative green startups with limited financial history."
Category: Small Business Ventures
Prompt: "You're 're saving $10,000 start custom clothing line. How do you proceed?"
Chosen: "Focus on affordable designs and use an online platform to sell."
Rejected: "Spend on luxury boutique storefront before establishing demand."
Category: Education & Skill Development
Prompt: "You't re saving $5,000 to attend a data visualization course. How do you proceed?"
Chosem: "Enroll in a course with interactive projects and industry relevance."
Rejected: "Choose a program with limited hands-on training."
Category: Debt Management
Prompt: "You're 're saving $12,000 pay off business loan. How do you proceed?"
Chosen: "Apply the funds directly reduce the principal and future interest." Rejected: "Use the funds for operational expenses while extending the loan term."
Category: Miscellaneous
Prompt: "You want to save S4,500 to organize youth art festival. How do you proceed?"
Chosen: "Partner with local sponsors and focus on cost-effective exhibits."
Rejected: "Spend heavily on promotional campaigns without engaging artists."
These examples illustrate the structured nature of our dataset and its alignment with decision-making scenarios across diverse financial categories.
25


Reviews:
[{"review_id": "jbW0YDgxcc", "reviewer": "Reviewer_bvkr", "summary": "LLMs is important to have alignment with human response. This work focuses on an approach from direct preference optimization, especially on CHI-PO. This approach is to address overoptimization issue in DPO on single-policy concentrability, which is a kind of offline alignment approach. In such approach, privacy and robustness of preference datasets are not well studied. \n\nOn privacy part, this work proposes Square CHI-PO by using a new square loss over probabilities in vanilla CHI-PO with differential privacy for general function approximations. On robustness part, Square CHI-PO preserves vanilla CHI-PO’s single-policy concentrability. It also achieves optimal rate for the approximation against random-flipping corruption as well as Huber label corruption.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your positive evaluation of our paper. We appreciate your recognition of our theoretical contributions to offline alignment, as well as our approach to privacy and robustness.\n\nWe're also grateful for your appreciation of a purely theoretical paper. To further support our main results, we have made an effort to include some preliminary empirical results as a proof of concept. Please see our response to Reviewer 6UpT.", "claims_and_evidence": "The claims is well stated the gap of offline DPO by observing limited work on theoretical guarantees for both privacy and robustness. None current work is sufficient to guarantee general function approximation. In advance, this work applies a square-based loss with DP to replace the log-based loss in CHI-PO from Huang et al., 2024 to balance both privacy and robustness.", "methods_and_evaluation_criteria": "Algorithm 1 and 2 well sketch the procedure to make this work tackle the issue. However, since this work is a pure theory work, authors did not provide any evaluation criteria and experimental results.", "theoretical_claims": "Section 3 and 4 as well as appendix Section C and D provides enough details to show the effectiveness of this work in the theoretical perspective.", "experimental_designs_or_analyses": "Although the theoretical claims and analysis are good, this work is lack of experimental results to support the theory, so it is a pure theory paper.", "relation_to_broader_scientific_literature": "This work has well discussed DPO work from Rafailov et al., 2023 and the most related variant CHI-PO from Huang et al. 2024 on either privacy or robustness perspective in the introduction.\n\n(1) For privacy, Chowdhury et al., 2024b and Korkmaz & Brown-Cohen, 2024 work on linear function approximation and are insufficient for non-linear or policy functions, while this work works for general function approximation.\n\n(2) For robustness, Mandal et al. 2024 uses RLHF-based method for linear setting, and Chowdhury et al., 2024a uses DPO approach, but with a suboptimal rate. None of them tackles the robustness for general function approximation. For Huber label corruption, this work matches offline RL setting in Zhang et al., 2022.\n\nIn addition, in preliminaries, this work discuss two offline alignment approaches, where Bradley & Terry, 1952 is to learn a policy to minimize the suboptimality gap, and Munos et al., 2023 captures non-transitive preferences without using reward function, which relies on minimax function.", "essential_references_not_discussed": "To my best knowledge, this work has discussed the most essential related work for its topic.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MdTQxfXqeO", "reviewer": "Reviewer_6UpT", "summary": "The paper proposes differentially private and robust offline preference alignment with human feedback. The method is based on the prior work of $\\chi$PO, but uses square loss instead of the log loss.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for time and feedback. We will recap your comments and present our detailed response. We hope our answers will resolve your concerns.\n\n**1. Significance of the difference compared to $\\chi$PO**\n\nWe clarify that the key significance and benefits of moving from log-loss to square loss in our Square$\\chi$PO is that it allows us to address privacy and robustness **simultaneously** for **both** BT and the general preference model. The reasons behind this have been highlighted in Section 3.1.1. To recap, the boundedness of square loss (rather than the unboundedness in log-loss) allows us to handle corruption easily. Meanwhile, square loss enables us to handle BT and the general preference model in a unified manner. \n\n**2. Preliminary experiments**\n\nWhile our contribution is mainly a theoretical one, we have now also made an effort to run some preliminary experiments as a proof of concept. \n\n- **A quick summary of results.** We have compared the performance of $\\chi$PO and Square$\\chi$PO under CTL and LTC settings with $\\epsilon = 0.5$ and $\\alpha = 0.1$. In particular, the following table gives the win rate (%) over the `π_sft` for different settings.  We can see that (i) there exists separation between LTC and CTL, and (ii) our Square$\\chi$PO\noutperforms $\\chi$PO in both settings. \n\n\n| Setting | $\\chi$PO          | Square$\\chi$PO   |\n|:-------:|:-----------------:|:----------------:|\n| CTL     | $64.2 \\pm 0.03$    | $67.0 \\pm 0.05$   |\n| LTC     | $59.8 \\pm 0.02$    | $60.0 \\pm 0.02$   |\n\n---\nMore details about our experiments are given below:\n\n - **Dataset.** We utilize `GPT-4o` to generate a synthetic dataset, referred to as `finance_preference`, which comprises $1697$ preference samples. Each sample includes a prompt related to a financial scenario and two possible responses, where `rejected` represents the high-risk option and `chosen` represents the low-risk option. This labeling can be viewed as private or sensitive information. For SFT training, we construct the `finance_sft` dataset by simply concatenating the prompt with the corresponding `chosen` response.\n\n - **SFT Training.**  We begin by fine-tuning `GPT2-large` using the `finance_sft` dataset to obtain the SFT policy, `π_sft`. For this, we directly utilize the SFT trainer from the Transformer Reinforcement Learning (`TRL`) library\n\n - **$\\chi$PO and Square$\\chi$PO Training.**  For alignment training, we split the dataset into `85%` for training, `5%` for validation, and `10%` for testing.  For $\\chi$PO, we follow the implementations in Huang et al. For Square$\\chi$PO, we simply modify the log-loss to square loss as in our presented algorithm. \n\n - **CTL and LTC Settings.**  The LDP mechanism follows the randomized response model, where the flip rate is given by $1 / (e^ε + 1)$. To implement both privacy and corruption, we introduce a mask variable initialized to `0` for each sample. The LDP mechanism flips the mask variable with probability $1 / (e^ε + 1)$, while the corruption mechanism sets the mask to `1` with probability `α` (different from random flipping).  Finally, after CTL or LTC processing, labels (`chosen` and `rejected`) are flipped if the corresponding mask value is `1`.\n\n - **Evaluation.**  We evaluate our trained models by generating responses for the test dataset. To assess performance, we employ the `llama3:70b` model as a judge, comparing responses from $\\chi$PO and Square$\\chi$PO against those from `π_sft`.  Finally, we use the win rate from these comparisons as our primary performance metric. We compute the average and standard deviation across `5` random seeds.", "claims_and_evidence": "The paper claims to achieve optimal rates in general function approximations under privacy constraints and achieves both privacy and robustness. However, it is not clear how these are achieved by replacing log loss with square loss. Does $\\chi$PO not obtain privacy and robustness?", "methods_and_evaluation_criteria": "There are no experimental evaluations in this paper.", "theoretical_claims": "I did not check the theoretical proofs in the appendix.", "experimental_designs_or_analyses": "The paper lacks experiments.", "relation_to_broader_scientific_literature": "The paper directly builds upon the previous state-of-art offline preference alignment work, $\\chi$PO, that solved the overoptimization problem in direct alignment. The proposed work claims to achieve both privacy and robustness.", "essential_references_not_discussed": "I'm not aware of any related works in this area.", "other_strengths_and_weaknesses": "- The novelty of the approach is limited as the proposed approach is a modification of the existing $\\chi$PO approach with the log loss being replaced with squared loss. While this does allow for some interesting observations for privacy and robustness alignment, it is not clear how significant the differences are from the prior works (mainly w.r.t. $\\chi$PO).\n- Lack of experimental comparison with other policy optimization algorithms. While the paper mainly focuses on theoretical results, their method can be implemented in practice as the authors point out. Thus, a thorough comparison with prior approaches would be useful, especially given that the method is a modification of a prior approach.", "other_comments_or_suggestions": "It would be helpful to include an experimental evaluation of the proposed Square$\\chi$PO method and compare it with prior works.\n\n[EDIT:] I'm raising my score based on the rebuttal response. I would recommend the authors to include the experiment results discussed in the rebuttal.", "questions_for_authors": "Can you please highlight the key differences between $\\chi$PO and Square$\\chi$PO and how these are benefited by going from log loss to square loss?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KVuVFnCpyW", "reviewer": "Reviewer_Rnup", "summary": "The paper studies algorithms for alignment given privacy and robustness considerations. In alignment we are given examples x, two model responses $a_0, a_1$, and a label $y$ denoting that $a_y$ was preferred to $a_{1-y}$. The labels are generated under one of two models, a reward model where each label-response pair has a reward and $y$ is set to 0/1 w.p. proportional to exponential in the reward of the corresponding action, or a generalized model where each pair can have arbitrary probability of preference, and preferences need not be transitive. With privacy, the label is privatized using randomized response (i.e. flipped w.p. $1 / (1 + e^\\epsilon)$ for some $\\epsilon$), and under corruption the true distribution is replaced with an unknown Bernoulli w.p. $\\alpha \\leq 1/2$. Given a policy class, the canonical DPO picks a policy that maximizes the sum of the log a certain utility function over the data. $\\chi$PO is a recent modification of DPO that adds a regularization term to the utility function. The authors propose Square$\\chi$PO, which minimizes a squared loss on the $\\chi$PO utility function instead of the log. Square$\\chi$PO also uses a scaling to de-bias the labels after randomized response. For preferences determined by a reward function, under a single-policy concentrability assumptioned used in $\\chi$PO, the authors bound the suboptimality of Square$\\chi$PO. The suboptimality bound consists of a bias term $\\sqrt{\\alpha}$ (that is $c(\\epsilon)$ larger if the labels are corrupted after instead of before privatization, where $c(\\epsilon)$ is the scaling for de-biasing) plus a term $c(\\epsilon) \\sqrt{(\\log |\\Pi|)/n}$, where $\\Pi$ is the size of the policy class. This retrieves the $1/\\sqrt{n}$ optimal dependence on dataset size. The authors also consider a central model where the entire example (not just the label) is private, but does not need to be privatized with local DP. They propose an exponential mechanism based on their square loss, and show similar guarantees. They also show similar guarantees for general preference models instead of preferences dictated by a reward function.\n\n## update after rebuttal\nI remain in support of accepting the paper", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your positive evaluation of our paper. We appreciate your recognition of our general analysis with non-trivial modifications of previous results. \n\nWe are also grateful for your recognition of our transparency in acknowledging the computational efficiency limitations in the central model. We'd like to take this opportunity to elaborate further. Our generic analytical framework is modular and allows for the integration of any advances in computationally efficient private regression. Under the realizability assumption, the estimation error under the square loss used in our current analysis aligns with the population excess risk in private stochastic optimization, both convex and non-convex. This means that, rather than relying on exponential mechanisms, one could substitute existing efficient methods.\nHowever, a key limitation is that these methods typically yield a slower $1/\\sqrt{n}$ rate in the non-private term without additional structural assumptions (rather than our $1/n$ under the exponential mechanism), which ultimately translates to a worse rate of $1/n^{1/4}$ in the end (for the non-private term). Exploring how to leverage additional structure (e.g., strong convexity or even weaker assumptions) to achieve optimal rates in a computationally efficient manner is an exciting direction for future work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A; there are no empirical results in the paper", "theoretical_claims": "Theoretical claims were not checked in detail", "experimental_designs_or_analyses": "N/A; there are no empirical results in the paper", "relation_to_broader_scientific_literature": "For local DP, a prior work of Chowdhury et al. studies robust but not private alignment, and achieves worse dependence on dataset size $1/n^{1/4}$ under the assumption that the reward is a linear model, with a stronger concentrability assumption, and does not extend to general reward functions. A different paper by Chowdhury et al. studies private but not robust alignment and only focuses on linear rewards, whereas the authors extend to general rewards. For central DP, concurrent works study weaker approximate DP while this work studies pure DP, but these works get better dimension-dependence in part due to the weaker DP definition. These works also focus on linear reward models while the present work tolerates general reward models.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n* In addition to allowing both privacy and robustness, extending to general reward functions and the general preference model is a strong contribution, as many past works assume a very restrictive linear reward model (not even a general reward model). I view the primary strength of this work as its wide generality in the scope of results compared to many of the past results.\n* Paper structure and presentation is quite clean, it is easy to understand the problem setup, the algorithms, and the comparisons to past work.\n* Authors are transparent about the limitations of results: e.g., they achieve different results for LTC and CTL (ordering of privatization and corruption), but clarify this is evidence for added difficulty of LTC but not a formal hardness result separating the two, and they state their exponential mechanism is not feasible to run in practice.\n* The algorithm and its analysis are not a trivial modification/combination of past results\n\nWeakness:\n* As the authors mention, the central DP algorithm is an exponential mechanism which may be infeasible to run in practice. However, there are no computationally efficient results for pure-central-DP private and robust alignment to compare to.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "No questions that would substantially affect my evaluation.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5Bf6fbumGZ", "reviewer": "Reviewer_G75h", "summary": "This paper studies the problem of alignment of language models with preference feedback, under two variations: (i) label corruption and (ii) privacy protections. While motivated by language models, there is nothing is specific to language models in the techniques, and they are more generally applicable to any offline alignment problem.\n\nIn the offline alignment problem, we are given a dataset where each \"example\" contains a tuple $(x, a^0, a^1, y)$ where,\n* $x$ is drawn from some distribution $\\rho$,\n* $a^0$ and $a^1$ are two independent draws from some reference policy $\\\\pi\\_{ref}(\\\\cdot | x)$, and\n* $y \\\\in \\\\{0, 1\\\\}$ indicates the preference between $a^0$ and $a^1$, that is sampled from the Bernoulli distribution $\\\\mathrm{Ber}({\\\\cal P}^*(a^1 > a^0 | x))$.\n\nThe goal is to learn a \"good policy\" $\\\\pi(\\\\cdot | x)$. There are two ways considered for quantifying how good a policy is.\n\n1. In the Bradley-Terry preference model, it is assumed that ${\\\\cal P}^*(a^1 > a^0 | x)$ is defined as $\\\\frac{e^{r^*(x, a^1)}}{e^{r^*(x, a^1)} + e^{r^*(x, a^0)}}$ for some reward function $r^*(x, a)$, and the goal is to learn a policy $\\\\widehat{\\\\pi}$ that minimizes the suboptimality gap $J(\\\\pi^*) - J(\\\\widehat{\\\\pi})$ where $J(\\\\pi) := \\\\mathbb{E}_{x \\\\sim \\\\rho, a \\\\sim \\\\pi(\\\\cdot | x)} r^*(x, a)$.\n\n2. In the General Preference model, there is no assumed parameterization of $({\\\\cal P}^*(a^1 > a^0 | x)$. Here the quality of a policy $\\\\widehat{\\\\pi}$ is measured in terms of a duality gap (see the paper for definition).\n\nTwo models of data perturbation are considered:\n1. Label corruption (in particular, a Huber model of corruption of the label $y$), and Local differential privacy (where the label $y$ is randomized with some known probability). These are considered in both orders (first Label corruption then Local DP or vice versa).\n\n2. Label corruption and central DP, wherein, the labels are assumed to be corrupted as per the Huber model, and then some central differentially private mechanism is applied for learning.\n\nThe paper proposes a new policy learning algorithm referred to as _Square$\\\\chi$PO_. For both the settings of data perturbation, the paper provides provable upper bounds on the quality of the learnt policy. (For pertubration of type 1, the rates are shown for both label corruption then local DP, and vice versa).\n\n### Post-rebuttal update\n\nI thank the authors for the discussion, and I will maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for the detailed feedback and constructive suggestions. We address the main points below and hope it will help to resolve your concerns. \n\n**1. Motivation of LTC.** The main motivation behind LTC is that after users privatize their preferences, the collected preference signals may be corrupted—either due to communication errors or adversarial attacks in the collection/transmission process.\n\n**2. Tightness of bounds.** Thanks for this sharp question. We provide our thoughts in detail below.\n\n- **Privacy only.** For the local model under BT-preference, when there is no corruption ($\\alpha = 0$), our rate is minimax optimal [R1]. Under the central model, we conjecture that the current $1/\\sqrt{n \\epsilon}$ additive cost cannot be improved if one relies on the statistical error in $L_2$. One possible way to improve this is to work with the $L_1$ norm, which we believe is a promising direction for achieving a better (and potentially optimal) $1/(n\\epsilon)$ additive privacy cost.\n\n- **Corruption only.** When there is no privacy constraint, our current rate is $O(\\sqrt{\\alpha})$ under Huber corruption. We conjecture this to be suboptimal compared to the ideal $O(\\alpha)$ rate. However, our current rate matches existing results in [R2], which considers standard offline RL with direct observation of rewards.\n\n- **Interplay between privacy and corruption.** Currently, under LTC, our rate is approximately $O(\\sqrt{\\alpha / \\epsilon})$ when $\\epsilon \\le 1$. This differs from the known interplay in the mean estimation problem, which yields a rate of $O(\\alpha/\\epsilon)$ [R3]. We leave a careful study of the precise interaction between privacy and corruption as an interesting direction for future work.\n\n---\n\n[R1] Chowdhury, S. R., Zhou, X., and Natarajan, N. Differentially private reward estimation with preference feedback.\nIn International Conference on Artificial Intelligence and\nStatistics, pp. 4843–4851. PMLR, 2024b.\n\n[R2] Zhang, X., Chen, Y., Zhu, X., and Sun, W. Corruption-robust offline reinforcement learning. In International\nConference on Artificial Intelligence and Statistics, pp.\n5757–5773. PMLR, 2022.\n\n[R3] Zhou, X. and Zhang, W. Locally private and robust multiarmed bandits. In The Thirty-eighth Annual Conference\non Neural Information Processing Systems, 2024.", "claims_and_evidence": "All claims are supported by proofs in the Appendix.", "methods_and_evaluation_criteria": "There are no experiments in the paper, so this question is not relevant.", "theoretical_claims": "I looked at the theoretical claims at a high level, and only briefly skimmed the Appendix.", "experimental_designs_or_analyses": "There are no experiments in the paper, so this question is not relevant.", "relation_to_broader_scientific_literature": "The paper studies the offline alignment problem in the context of label corruption and differential privacy. This seems novel and interesting to me.", "essential_references_not_discussed": "As far as I can tell, all essential references have been adequately discussed.", "other_strengths_and_weaknesses": "The paper considers a nice twist on the offline alignment problem of label corruption and differential privacy, and provides upper bounds on the sub-optimality gap / duality gap.\n\nOne thing that was not clear to me was how tight the established bounds are. Without the tightness results, it is difficult to be convinced of the exact interplay between label corruption and DP guarantees.", "other_comments_or_suggestions": "I think it would be beneficial to discuss some motivation for when $\\\\mathsf{CTL}$ and $\\\\mathsf{LTC}$ settings could be applicable in practice.\n\nI can see why $\\\\mathsf{CTL}$ makes sense: the corruption is a way to handle misspecification in the model, and the Local DP randomization is added for privacy. But I don't know where $\\\\mathsf{LTC}$ comes up.", "questions_for_authors": "Is it clear how tight the established upper bounds on sub-optimality gap and duality gap are? Is it possible to prove any lower bounds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposed new algorithms for private and robust alignment of language models by modifying a previous algorithm CHI-PO. This algorithm enables nice theoretical gurantees and most of the reviewers found the theoretical contribution valuable. The authors also provided preliminary empirical studies during the rebuttal which further demonstrated the efficacy of the proposed method.
Decision: Accept (poster)