1 Introduction↩︎

The alignment post-training in large language models (LLMs) relies on human preference data to ensure that model outputs are both helpful and harmless [3], [4]. While widely adopted in practice, these preference labels are often noisy [5]. Noise can arise from corruption or misspecification during label generation—such as data poisoning attacks [6]—or from privacy concerns that lead individuals to provide noisy and privatized preferences rather than their true rankings [7].

Motivated by these challenges, recent works have begun to study the theoretical impact of noisy preference labels in alignment, e.g., [1], [8]–[10]. However, several aspects of the existing results remain unsatisfactory.

First, on the privacy side, current approaches [1], [8]–[10] typically require designing new losses that deviate from the natural maximum-likelihood-estimation (MLE) loss. Some even suggest that the private MLE log loss fails to achieve a near-optimal rate [9].

Contribution 1. We give an affirmative answer: the standard private MLE-type log loss can, in fact, achieve a near-optimal rate. This sharpens our understanding of private alignment. Our result is enabled by a new uniform convergence result for log loss under label privacy, an ingredient that may be useful more broadly in other learning scenarios.

Turning to adversarial Huber corruption and its interplay with privacy, existing state-of-the-art guarantees are strictly suboptimal [1].

Contribution 2. We give an affirmative answer to Q2: through a new analysis, we show that existing algorithms already admit stronger guarantees in both the corruption-only and the joint corruption–privacy settings. This improvement is enabled by a new uniform convergence result for the square loss under privacy and corruption, which is widely useful given the square loss’s central role in reinforcement learning broadly [11].

Finally, most prior results on private and robust alignment focus on the offline setting, where guarantees inevitably depend on how well the dataset covers the optimal policy [12]. By contrast, recent advances show that online alignment with active exploration can achieve rates determined only by the intrinsic complexity of the policy class [2].

Contribution 3. The answer is yes. Building on our new uniform convergence results for log and square losses under privacy and corruption, we show that a simple one-line modification of existing online alignment algorithms suffices to achieve near-optimal rates in the presence of noisy preference labels.

Taken together, our results advance the theoretical foundations of private and robust alignment post-training and open the door to broader applications of uniform convergence in other learning scenarios.

Tables 1 and 2 summarize our theoretical guarantees relative to prior work in the offline and online settings, respectively. We further provide empirical evaluations in Appendix 8, including experiment on the real-world PKU-SafeRLHF preference dataset.

2 Preliminaries↩︎

In this section, we present some background on the alignment in language models as well as its privacy and robustness issues.

2.1 Offline and Online Alignment↩︎

In the offline setting [4], the learner has access to an offline preference dataset \(\cD_{\pref}=\{(\tau_{-1}^{(i)}, \tau_1^{(i)}, y^{(i)})\}_{i=1}^n\), which consists of two responses and one preference label. The two responses (full trajectories) are i.i.d. samples from a reference policy \(\piref\) starting from an initial prompt (state) \(s^{(i)} \sim \rho\), i.e., \(\tau_{-1}^{(i)} \sim \piref \mid s^{(i)}\) and \(\tau_1^{(i)} \sim \piref \mid s^{(i)}\). We assume that each response includes the initial state. The preference label \(y^{(i)} \in \{-1,1\}\) is generated according to \(\{-1,1\}\)-valued Bernoulli distribution, i.e., \(y^{(i)} \sim \mathsf{Ber}(\cP^{\star}(\tau_1^{(i)} \succ \tau_{-1}^{(i)} \mid s^{(i)}))\), where \(\cP^{\star}(\tau_1^{(i)} \succ \tau_{-1}^{(i)} \mid s^{(i)}) \in [0,1]\) is the probability that given \(s^{(i)}\), \(\tau_1^{(i)}\) is preferred over \(\tau_{-1}^{(i)}\). Following the literature, we assume that the preference follows the Bradley-Terry model [13]: for two responses \(\tau\) and \(\tau'\) from \(s\) \[\begin{align} \label{eq:BT} \cP^{\star}(\tau \succ \tau' \mid s) = \frac{\exp(r(\tau))}{\exp(r(\tau)) + \exp(r(\tau'))}, \end{align}\tag{1}\] where the unknown function \(r \in [0, R_{\mathsf{max}}]\) specifies the reward for each response. The goal in offline alignment is often to find a policy that maximizes the (unregularized) reward \[\begin{align} J(\pi):= \mathbb{E}_{\pi}[r(\tau)], \end{align}\] where \(\mathbb{E}_{\pi}[\cdot] := \mathbb{E}_{s \sim \rho, \tau \sim \pi(\cdot\mid s)} [\cdot]\).

In the online setting, the learner has access to online samples using the current model during training [14]. In particular, the protocol proceeds in \(T\) rounds. At each round \(t\), the learner generates two responses \(\tau^{(t)}, \widetilde{\tau}^{(t)}\) using the current policy \(\pi^{(t)}\) and some other sampling policy, respectively, starting from a sampled initial state \(s^{(t)}\) from a distribution \(\rho\).

The two responses are then labeled as \(y^{(t)} \in \{-1,1\}\) via human feedback, such that if \(y^{(t)}=1\), \(\tau^{(t)}\) is preferred over \(\widetilde{\tau}^{(t)}\) and if \(y^{(t)}=-1\), \(\widetilde{\tau}^{(t)}\) is preferred over \(\tau^{(t)}\). As before, we assume the preference follows from the Bradley-Terry model as in 1 . Then, the online preference dataset is updated via \(\cD_{\pref}^{(t)} = \cD_{\pref}^{(t-1)} \cup \{(\tau^{(t)}, \widetilde{\tau}^{(t)}, y^{(t)})\}\). The goal in online alignment is to leverage the online interaction to find a policy that maximizes the (regularized) reward \[\begin{align} \label{eq:reg-obj} J_{\beta}(\pi):= \mathbb{E}_{\pi}\left[ r(\tau) - \beta \log \frac{\pi(\tau)}{\piref(\tau)}\right], \end{align}\tag{2}\] where \(\beta >0\) is a parameter for the KL regularization.

2.2 Privacy and Robustness in Alignment↩︎

A natural privacy concern in the alignment process is that the preference label could reveal humans’ private and sensitive information. Thus, for privacy protection, the learner may only have access to privatized labels, which is achieved by a local randomizer that randomly flips the label. This can ensure the so-called local differential privacy (LDP) [15]–[17].

In practice, the preference labels may be corrupted due to adversary manipulation or simple recording errors. To capture this, we borrow the classic Huber corruption model from robust statistics.

As in previous work [1], we mainly focus on the interplay between privacy and corruption by considering the co-existence of them with different orders, which gives results for the corruption-only case.

3 Uniform Convergence: Privacy and Corruption↩︎

In this section, we will present our main technical contributions: uniform convergence results for both log loss and square loss under privacy and/or corruption.

3.1 Log Loss under LDP↩︎

In this subsection, our main result is the following lemma, which gives the uniform convergence with log loss under local privacy. This can be viewed as a variant of the standard MLE-type generalization guarantee under log loss [20].

Implications. This lemma has several important and concrete implications. First, it helps to clarify our current understanding of MLE with log loss under privacy. Specifically, some previous works have shown that one needs to construct a new de-biased loss to work with local privacy, which turns out to be unnecessary. For instance, in the context of reward model learning with private preference data, [9] attempted to work with the MLE estimator directly, but only obtained a suboptimal rate. This motivates their new de-biased loss design, which was later adopted in the alignment setting as well [8]. However, with our above new result, we can show that the MLE estimator under local privacy can also yield an optimal rate for the reward model, by a simple application of the mean-value theorem. Further, via the reduction framework in [8], our result can be directly leveraged in the offline alignment problem with linear function approximation, see more discussions on these in Appendix 12. Second, in Section 4, we will show that the above lemma can also be utilized to design new algorithms with log loss for both offline and online alignment, even with a general function class. Finally, given the wide application of log loss in decision-making problems [21], [22], our result could find wide applications beyond alignment.

3.2 Square Loss under CTL and LTC↩︎

In this subsection, our main result is the following lemma, which gives the uniform convergence with square loss under both local privacy and adversary corruption. This can be viewed as a variant of the standard generalization bound of least squares (e.g., [11]).

Improvement over the prior art. The above lemma improves the state-of-the-art [1] in both and settings. In particular, for , [1] established that the corruption term is \(n \alpha\), which is strictly worse than our optimal bound of \(n \alpha^2\) as \(\alpha \in [0,1/2)\). For , [1] showed a bound of \(n c(\epsilon) \alpha\), which is again worse than ours for the meaningful range of \(c(\epsilon) \alpha \lesssim 1\). In Section 5, we will apply the above lemma to both offline and online alignment to arrive at state-of-the-art results.

4 Private Alignment: Log Loss↩︎

This section presents two log-loss–based algorithms with theoretical guarantees for alignment under private labels: one for the offline setting and the other for the online setting. Each algorithm is obtained through a simple yet principled modification of its non-private counterpart, and their guarantees are established using our earlier result, i.e., Lemma 1.

4.1 Offline Setting↩︎

In this subsection, we focus on the offline setting and present Priv(Algorithm 1), which is the private version of proposed in [12].

Privtakes as input a preference dataset \(\widetilde{\mathcal{D}}_{\pref}\) with privatized labels. It first ranks the two responses using the private label and then computes the reparameterization function \(h_{\chipo}^{(i)}(\pi)\) using the function \(\phi(u)\), which has an additional linear term \(u\) compared to the standard \(\log (u)\) term in DPO [24]. This additional term arises due to the use of \(\chi^2\)-divergence (in addition to standard KL-divergence) when regularizing the final policy with respect to \(\piref\) in RLHF. Next, the preference probability \(P^{(i)}_{\chipo}(\pi)\) is computed based on the BT-model (cf. 1 ), with the truncated \(h_{\chipo}^{(i)}(\pi)\) \(\in [-2R_{\mathsf{max}}, 2R_{\mathsf{max}}]\) being the reward difference. Here, the truncation is adopted to slightly improve the final bound, as in [12]. Finally, the policy is found by the private MLE, inspired by \(\hat{L}^{(n)}\) in Lemma 1, which reduces to the standard log loss when \(\epsilon = \infty\), i.e., non-private case. In summary, the only change compared to is the loss objective.

In the following, we will present the sample complexity guarantee for Priv. To this end, we first make several standard assumptions as in the non-private case [12]. The first one is the realizability assumption, which states that the policy class \(\Pi\) contains the optimal policy under regularization.

The next assumption asserts that the implicit reward difference under any policy in \(\Pi\) is upper bounded by some constant.

Finally, as is typical in offline RL, we need some notion of concentrability to measure the quality of the offline data. Following [12], our main result relies on the following one.

Now, the main sample complexity bound for Privis as follows, with proof in Appendix 10.1.

This theorem shows that the cost due to local label privacy is a multiplicative factor \(c(\epsilon)\), which is indeed optimal up to \(\kappa(\pi^{\star})\) factor. We highlight that this is the first result showing that a standard log-loss MLE-type algorithm can yield a near-optimal rate under privacy, without the design of any de-biased loss. The dependence of single-policy concentrability (rather than the larger all-policy concentrability) is the key benefit of using the additional \(\chi^2\)-regularization.

4.2 Online Setting↩︎

In this subsection, we turn to the online alignment setting. Our main algorithm is Priv(Algorithm 2), which is a simple modification to the non-private counterpart in [2].

To better present the online privacy protection process, we divide the algorithm into two parts: the user side and the learner side in Algorithm 2. For each step \(t \in [T]\), user \(t\) submits a question \(s_1^{(t)}\) and receives two responses¹ \(\tau^{(t)} \sim \pi^{(t)} \mid s^{(t)}_1\), and \(\widetilde{\tau}^{(t)} \sim \pi_{\mathsf{ref}} \mid s^{(t)}_1\). Then, user \(t\) generates the true preference label and the private one, respectively. On the learner side, after receiving the \(t\)-th new data, it ranks the responses, updates the online dataset, and computes the probability \(P^{(i)}_{\xpo}\). Here, the reparameterization function is just the standard DPO-type, i.e., only the log function in \(h_{\xpo}^{(i)}\). This probability is then used to construct the empirical loss \(\hat{L}_{\xpo}^{(t)}\), similar to the offline setting, which is again inspired by Lemma 1. Finally, the learner updates the policy by minimizing a composite loss function, which adds an additional term \(\gamma \sum_{i \in [t]}\log \pi(\widetilde{\tau}^{(i)})\) to solicit active exploration via global optimism, which is the key component in . As before, the only fundamental change compared with is the loss objective.

In the following, we turn to the theoretical guarantee of Priv. To this end, we will make the same set of statistical assumptions as in  [2].

We also need the following boundedness assumption.

Note that this is slightly stronger than the one in Assumption 2, which only requires the difference to be bounded.

Finally, we require a notion to quantify the exploration difficulty as in online RL, which is necessary for RL with general function approximations. We follow to use a condition known as coverability [25], which is formally defined below.

This coverability notion for online RL is closely related to concentrability in offline RL in that coverability can be viewed as the best concentrability in a certain case (due to the inf operator in the definition), see [25] for more discussions.

We are now ready to state the following sample complexity guarantee of Priv, with its proof given by Appendix 10.2.

The above theorem gives the first sample complexity result for online alignment with label privacy. When compared with the offline counterpart in Theorem 7, we can see that, roughly, the online guarantee above replaces the concentrability-related term by the coverability-related term, which indicates the benefit of active online exploration. As before, the additional \(c(\epsilon)\) factor is the cost due to privacy protection, compared to the non-private in [2].

5 Private and Robust Alignment: Square Loss↩︎

In this section, we turn to study alignment under both privacy protection and adversarial corruption by considering and settings. The only major difference compared to the last section is a square loss in place of the log loss.

A natural question is why we do not include the private and robust alignment results for log-loss. The key reason is that the log loss is unbounded, while the square loss is bounded, which enables us to control the effect of Huber corruption easily. That being said, whether one can establish some guarantees for log loss under Huber corruption is an interesting question, given its wide use in practice. This represents a fundamental technical challenge that we identify as an open direction.

5.1 Offline Setting↩︎

In the offline setting, we will show that the existing algorithm (i.e., Squarein [1]) actually enjoys an improved sample complexity bound, as an application of Lemma 2.

We recap Squarein Algorithm 3 using our notations. It essentially replaces the log loss in \(\texttt{Priv}\chipo\) (and ) with a square loss. Note that to match the specific form of square loss in Lemma 2, we do not rank the responses using \(+/-\) here. As mentioned before, one key advantage of the square loss in Algorithm 3 is that it is bounded, which helps us to handle the corruption easily.

Next, as a direct application of Lemma 2, we will establish an improved bound for Squarecompared to the one in [1]. In particular, under the same assumptions as before, we have the following sample complexity guarantee. See Appendix 11.1 for the proof.

The above theorem gives better bounds for both and , compared with [1]. For , it improves from \(\sqrt{\alpha}\) to \(\alpha\) and for , it improves from \(\sqrt{c(\epsilon)\alpha}\) to \({c(\epsilon)\alpha}\). An astute reader may already observe that this essentially comes from the improvement in Lemma 2 over the previous result.

5.2 Online Setting↩︎

In the online setting with both privacy and corruption, we again adopt a square loss but in to propose Square(Algorithm 4). This new algorithm is the first one with theoretical guarantees that can handle both privacy and corruption in the online setting.

Squareshares the same flow as in Privin the last section. We still divide it into two parts: the user side and the learner side. For each step \(t \in [T]\), on the user side, the private and corrupted preference label is generated following or . On the learner’s side, the optimization objective changes from a log loss to a square loss. Finally, the policy is updated with the global optimism for exploration.

We have the following sample complexity bound for Square, with proof in Appendix 11.2.

This theorem shows that similar sample complexity difference between and maintains in the online setting by our Square. This separation is in fact optimal (up to \(\kappa_{\mathsf{cov}}(\Pi)\)) by reusing existing lower bound for simpler online MAB problem [23]. Once again, this near-optimal result is obtained via our Lemma 2.

6 Conclusion↩︎

We presented a theoretical analysis for private and robust alignment of language models, analyzing both the offline and online settings. Our results resolve several important questions in the literature: we showed that the standard log-loss MLE algorithm can indeed achieve near-optimal rates under privacy constraints, we improved guarantees in both the corruption-only and corruption–privacy settings by leveraging uniform convergence under square loss, and we extended these results to the online regime with active exploration.

Looking forward, several promising directions remain. First, an important next step is to extend our empirical evaluation to broader model scales and additional privacy-and-corruption regimes. Second, our results are established under the classical Huber corruption model; developing theoretical guarantees under stronger adaptive corruption models remains an open challenge for general function approximations [8]. Finally, our algorithms could be extended to hybrid settings that combine offline datasets with online preference feedback to enjoy additional benefits.

Acknowledgement↩︎

XZ would like to thank Francesco Orabona on discussion about the MLE loss. This work is supported by NSF grants under CAREER-2441519, CNS-2312835, and CNS-2153220.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of theoretical Reinforcement Learning from human feedback. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

7 Detailed Related Work↩︎

In this section, we review several different topics related to our paper.

Differentially private bandits and RL. The theoretical foundations of private alignment are closely connected to a broader literature on reinforcement learning and bandits under differential privacy constraints. Early work primarily focuses on multi-armed bandits (MABs), establishing near-optimal regret bounds under local or central differential privacy [26]–[31]. These results were subsequently extended to contextual bandits [32]–[36], where perturbing rewards, gradients, or sufficient statistics typically enforce privacy. Beyond bandits, a growing body of work studies differentially private reinforcement learning in episodic MDPs [37]–[40]. Among these, only a small number of papers explicitly address policy optimization under privacy constraints. In particular, [39] and [41] analyze private policy optimization in exploratory settings, characterizing the cost of privacy in regret by privatizing optimistic variants of PPO or natural policy gradient under tabular and linear function approximation, respectively. More recently,  [42] establishes the first comprehensive set of sample complexity bounds for differentially private policy optimization.

Standard offline and online alignment. Theoretical analysis of alignment algorithms has become an active research area. One line of research focuses on the purely offline setting where the preference dataset is pre-collected, e.g.,  [12], [43]–[48]. Among them, in [12] will serve as our basis for the offline alignment due to its state-of-the-art result with a simple implementation, which is a simple one-line change to the DPO algorithm in [24]. One key limitation of offline alignment is that it requires the offline dataset to have a good coverage with respect to the optimal policy (or any other comparator policy). This motivates the study of online alignment, where the algorithm has access to online preference feedback, which often requires active exploration to achieve the optimal rates, e.g., [2], [46], [48]–[51]. Among them, in [2] will be our basis for the online setting due to its good result achieved again via a one-line change to the DPO algorithm in [24]. We also mention that some works consider the hybrid setting that has both an offline dataset and online feedback (e.g., [52], [53]), which may have further advantages.

Private and robust alignment. The current theoretical results in this area mainly focus on the offline setting. With a linear model assumption, [9] studies the reward model learning with private randomized labels [15]. After showing that the standard MLE-type log loss fails to achieve the optimal rate, it turns to propose a new de-biased log loss, which has been used in many follow-up works, e.g., [8], [10]. An important question here is whether the failure of the standard MLE-type log loss in [9] is due to their specific analysis or to the intrinsic limitation of such a loss. Our paper shows that it is the former by giving near-optimal results for private alignment using standard MLE-type log loss. When it comes to adversary corruption of labels (e.g., Huber corruption [19]) and the joint-corruption-privacy case, the boundedness of the square loss (when compared with the unboundedness of log loss) becomes extremely useful. By utilizing such a property, [1] proposed Square—which modifies the log loss in to a square loss—to study the interplay between corruption and privacy in offline alignment. Although it is a pioneering work, the guarantees of Squareturn out to be strictly suboptimal in terms of both the corruption parameter and the interplay between corruption and privacy parameters. Our paper shows that Squarein fact has a stronger guarantee via a new analysis. We note that a recent work [54] also establishes faster rates for the regularized objective in both offline and online settings under DP. One key difference is that no corruption is considered in their results.

8 Additional Experiments↩︎

In this chapter, we present a small set of proof-of-concept experiments to complement our theoretical results. As with many ICML theoretical works, our primary focus is on establishing sharp theoretical guarantees rather than extensive empirical evaluations.

Nevertheless, since our analysis shows that multiple loss functions (i.e., the debiased log loss, square loss, and our MLE-type log loss) achieve the same theoretical rates in the private alignment setting, a natural question arises:

8.1 Experiment Setup↩︎

We follow exactly the same dataset, model architecture, and training pipeline as in prior works on private alignment (e.g., [1], [8]), and only modify the loss function used for preference optimization. We compare the following three approaches: MLE-type log loss; Debiased log loss [8] and Square loss [1] for private alignment.

8.1.0.1 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.

8.1.0.2 SFT Training.

We begin by fine-tuning GPT2-large using the finance_sft dataset to obtain the SFT policy, \(\pi_{\mathsf{sft}}\). For this, we directly utilize the SFT trainer from the Transformer Reinforcement Learning (TRL) library [55], with the hyperparameters listed in Table 3.

8.1.0.3 Evaluation.

All methods are evaluated under the same privacy budget \(\varepsilon = 0.5\). Following standard practice in the alignment literature, performance is measured by the win rate (%) against the supervised fine-tuned policy \(\pi_{\mathsf{sft}}\). For each test prompt, responses are generated by the evaluated policy and compared against the corresponding response produced by \(\pi_{\mathsf{sft}}\). Pairwise comparisons are conducted using the llama3:70b model as an automated judge, following the evaluation protocol of [24]. The win rate is defined as the fraction of test instances for which the judge prefers the response generated by the evaluated policy over that of \(\pi_{\mathsf{sft}}\).

All methods are evaluated under the same privacy budget \(\varepsilon = 0.5\). Performance is measured by the win rate (%) against the supervised fine-tuned policy \(\pi_{\mathsf{sft}}\), following standard practice in the alignment literature.

8.2 Results↩︎

Table 4 reports the win rate (%) over \(\pi_{\mathsf{sft}}\) for different loss functions.

All reported results are averaged over 5 independent random seeds. We observe that all three approaches achieve comparable performance, which is consistent with our theoretical findings that they attain the same convergence rates in the private alignment setting. Together with our theoretical results, these experiments help clarify the practical implications of our new uniform convergence analysis and position our contributions relative to previous work.

8.3 Additional Experiment on PKU-SafeRLHF↩︎

To complement the controlled synthetic experiment above, we further evaluate the three private-alignment objectives on a real-world safety preference dataset, PKU-Alignment/PKU-SafeRLHF [56]. Specifically, we compare the MLE-type log loss, debiased log loss [8], and square loss [1] under the same privacy budget \(\varepsilon = 0.5\).

8.3.0.1 Dataset.

We use the training split of PKU-SafeRLHF and retain only examples in which exactly one of the two candidate responses is marked safe. This filtering yields 10813 eligible preference pairs. We then select 1697 examples with selection seed 42, using 1442 examples for preference optimization, 85 examples for validation, and 170 held-out prompts for evaluation. The safe response is treated as “chosen” and the unsafe response as “rejected”, matching the official safer_response_id field on all selected examples.

8.3.0.2 SFT Training.

We fine-tune GPT2-large on the safe responses to obtain the supervised fine-tuned policy \(\pi_{\mathsf{sft}}\). The SFT hyperparameters are identical to those in Table 3: learning rate \(1\mathrm{e}{-5}\), batch size 8, and 3 training epochs.

8.3.0.3 Private Preference Optimization.

For each method, we run 5 independent private dataset seeds. Preference labels are privatized by randomized response under \(\varepsilon = 0.5\), with flip probability \(1/(1+\exp(\varepsilon))\). In the strict private-only \(\chi\)PO implementation, we set \(\alpha=0\), \(\beta=0.01\), and the \(\chi\)PO coefficient to 0.25. All three methods use the same strict private-only \(\chi\)PO transformed score and the same training, generation, and evaluation protocol; only the loss function is varied. Each trained policy is then used to generate one response for each of the 170 held-out test prompts.

8.3.0.4 Evaluation.

For consistency with the win-rate evaluation above, every generated response is paired with the corresponding response from \(\pi_{\mathsf{sft}}\) using a fixed A/B randomization rule. We use llama3:70b as the judge model and evaluate 3 methods \(\times\) 5 seeds \(\times\) 170 held-out test prompts, resulting in 2550 pairwise comparisons in total. We report the win rate over all comparisons, computed as the fraction of comparisons in which the method’s output is preferred by the judge.

Table 5 reports the mean and standard deviation over 5 independent random seeds. The three losses achieve closely comparable win rates on this real-world safety preference dataset, consistent with the behavior observed in the synthetic finance experiment in Table 4 and with our theoretical characterization of these objectives in the private alignment setting.

9 Missing Proofs For Section 3↩︎

9.1 Detailed Proof of Lemma 1↩︎

We first state the standard non-private uniform convergence result under log loss. Similar results can be found in many existing works, e.g.,  [20],  [57],  [2], and [58].

9.2 Detailed Proof of Lemma 2↩︎

We first state the standard non-private non-corrupted uniform convergence result under square loss. The following particular result is an adaptation based on Lemmas 6 and 7 (along with their proof) in [58]. We note that one can also prove Lemma 2 using Freedman’s inequality directly. However, we tend to believe that utilizing existing results is a more modular approach.

10 Missing Proofs For Section 4↩︎

10.1 Detailed Proof of Theorem 7↩︎

We first present the following meta theorem for Priv.

10.2 Detailed Proof of Theorem 9↩︎

For the proof of Theorem 9, we mainly follow from Lemma 1, which gives the private uniform convergence result under log loss. Our proof is modular once we have the generalization error bounds. Here we first present a meta theorem, which is a simple adaptation from the proof in [2] to our algorithm. We will then provide the mapping from Lemma 1 to Algorithm 2 here to demonstrate why we can utilize such a lemma.

Recall the update rule in both Algorithm 2 and 4 and define \(\hat{B}^{(t)}(\pi) = \gamma \sum_{\widetilde{\tau}}\log \pi(\widetilde{\tau})\), then

\[\begin{align} \pi^{(t+1)} \leftarrow \argmin_{\pi \in \Pi}\left\{\hat{B}^{(t)}(\pi) - \hat{L}^{(t)}(\pi)\right\}, \end{align}\] where \(\hat{L}^{(t)}(\pi) = c(\epsilon)^2 \cdot \hat{L}_{\xpo}^{(t)}(\pi)\) for Priv, as for Square, \(\hat{L}^{(t)}(\pi) = \hat{L}_{\texttt{sq}\xpo}^{(t)}(\pi).\)

To satisfy Equation 6 , we need the following two lemmas.

Combining Lemma 6 and Lemma 7, taking an union bound over all time steps \(t \in T\), and note that \(\hat{B}^{(t)}(\pi) - \hat{L}^{(t)}(\pi) \le \hat{B}^{(t)}(\pi_{\beta}^\star) - \hat{L}^{(t)}(\pi_{\beta}^\star)\), then we get the stated result.

11 Missing Proofs For Section 5↩︎

11.1 Detailed Proof of Theorem 13↩︎

We first adapt the meta theorem of [1] to our notation for Square.

By this theorem, we only need to focus on the term of \(\err^2_{\mathsf{stat}}\). In contrast to [1], we will leverage our tighter uniform convergence lemma (i.e., Lemma 2) to achieve a better bound.

11.2 Detailed Proof of Theorem 15↩︎

12 Further Discussions↩︎

In this section, we discuss further applications of our two uniform convergence results in the context of alignment (e.g., reinforcement learning from human feedback (RLHF), reward model learning).

12.0.0.1 Novelty and Conceptual Insights.

We provide additional discussion to clarify the conceptual novelty and technical insights of our results, complementing the main theoretical developments presented in the paper. A prevailing belief in the alignment literature is that MLE-type log loss cannot achieve optimal statistical rates under local privacy constraints, which has motivated the adoption of alternative objectives such as square loss. In contrast, our results demonstrate that MLE-type log loss can still attain near-optimal rates in private alignment. This is enabled by a new uniform convergence bound under log loss (Lemma 1), which appears to be previously unavailable in the presence of local privacy and may be of independent theoretical interest.

Our analysis also resolves an open question in prior work regarding the optimal dependence on the corruption parameter and its interplay with local privacy. By establishing a new uniform convergence bound under square loss without introducing stronger assumptions (Lemma 2), we obtain guarantees that simultaneously achieve optimal dependence on both privacy and corruption parameters. The key technical ingredient is a new analytical approach that fully exploits the probabilistic structure of the Huber corruption model.

Reward model learning. Our two uniform convergence lemmas directly give a bound for the estimation error for the greedy estimator that minimizes the empirical loss, in the context of privacy and corruption. Note that this estimation error is in terms of probability difference. To convert it to a reward difference in expectation, one can simply use the mean-value theorem and pay the inversion cost of \(e^{R_{\mathsf{max}}}\) (e.g., [1], [45]). If the interest is the empirical reward difference (as in [43]), one can further convert from the population one to the empirical one, say using Lemma C.1 in [60] or Lemma 39 in [61] for the special case of a linear model. With such a reward model learning result, one can then leverage the reduction framework in [8] to derive results for both RLHF and DPO.

Improved bounds for regularized objective in 2 for large \(\beta\). For the regularized objective with a large \(\beta >0\), one can leverage the local strong convexity of the KL-divergence to achieve a faster rate of \(1/(\beta T)\) rather than \(1/\sqrt{T}\) (but is independent of \(\beta\), hence true for any \(\beta\)). This has been hinted for in [2] and recently formally proved (although for different algorithms) in [60], [62], [63] without privacy and corruption. In particular, [62] gives the first faster rate in the offline alignment with single-policy concentrability. We can easily modify it to give a private and/or robust version of it. For the privacy-only case, we can simply modify their non-private MLE estimation (i.e., Algorithm 4 in [62]) with our private one in Lemma 1. For the privacy-corruption cases (and ), we can replace the objective by our square loss in Lemma 2. To derive the guarantees of these two new algorithms, an astute reader may already realize the same trick used in our main paper—replacing the statistical/estimation error term with our new bounds. More specifically, we only need to replace the bound in Lemma F.1 of [62] by our new results in Lemmas 1 and 2, respectively (with mean-value theorem conversions). Then, we can have the following results:

Moving to the online setting, [63] gives the first fast rate for objective 2 , in the reward-based case rather than the preference-based case. However, as already mentioned by the authors, it is quite straightforward for the extension. In particular, one only needs to define a preference-based eluder dimension by introducing a baseline in their Definition 3.3 to account for the fact that in the preference-based setting, one can only learn the reward difference. A similar extension is already used in [62] for the offline setting. Then, as in the offline case, the final guarantee scales linearly with the estimation error (in square). Hence, using our two uniform convergence results, we have the following guarantees.

References↩︎

---

1. This two-response interaction indeed often pops up in the ChatGPT app or website.↩︎