Technical Summary: Improved Bounds for Private and Robust Alignment

1. Problem Statement

This paper addresses the theoretical challenges of aligning Large Language Models (LLMs) when preference labels are subject to privacy constraints and/or adversarial corruption. In standard Reinforcement Learning from Human Feedback (RLHF), models rely on preference data to ensure outputs are helpful and harmless. However, real-world data often suffers from:

• Privacy concerns: Users may privatize their true preferences (e.g., via Local Differential Privacy mechanisms like Randomized Response) to protect sensitive information.
• Adversarial corruption: Labels may be corrupted by data poisoning attacks or recording errors, modeled via the Huber corruption framework.

The paper investigates the suboptimality gap (the difference between the optimal policy's reward and the learned policy's reward) in both offline (static dataset) and online (active exploration) settings under two distinct interaction orders of these threats:

1. Corruption-then-LDP (CTL): Labels are corrupted first, then privatized.
2. LDP-then-Corruption (LTC): Labels are privatized first, then corrupted.

The authors aim to resolve three specific open questions regarding the theoretical limits of existing approaches:

• Q1: Can standard Maximum Likelihood Estimation (MLE) with log loss achieve near-optimal rates in private alignment, or is a specialized de-biased loss required?
• Q2: Can existing algorithms for joint privacy and corruption achieve improved bounds compared to prior state-of-the-art?
• Q3: Can theoretical guarantees be established for online private and/or robust alignment?

2. Methodology and Technical Core

The paper's contributions are grounded in establishing new uniform convergence guarantees for two specific loss functions under privacy and corruption. These lemmas serve as the foundational tools for deriving sample complexity bounds for alignment algorithms.

2.1 Uniform Convergence for Log Loss under Privacy

The authors prove a new uniform convergence result for log loss under Local Differential Privacy (LDP).

• Key Insight: Contrary to previous literature suggesting that standard MLE fails under privacy, the authors show that the standard private MLE log loss achieves near-optimal rates.
• Mechanism: By applying a uniform convergence bound to the privatized data sequence (where labels are flipped via Randomized Response), they demonstrate that the estimation error scales optimally with the privacy parameter $c(\varepsilon) = \frac{e^\varepsilon + 1}{e^\varepsilon - 1}$.
• Implication: This result validates the use of standard log-loss objectives for private reward model learning and alignment without needing complex, custom de-biased losses.

2.2 Uniform Convergence for Square Loss under Privacy and Corruption

The authors establish uniform convergence for square loss under the joint settings of CTL and LTC.

• Key Insight: The bounded nature of the square loss allows for tighter control over the effects of Huber corruption compared to unbounded log loss.
• Mechanism: The analysis leverages the specific probabilistic structure of the Huber corruption model combined with LDP.
• Improvement: The derived bounds for the corruption term are strictly tighter than previous results. Specifically:
  • For CTL, the corruption dependence improves from $O(\sqrt{\alpha})$ to $O(\alpha)$.
  • For LTC, the dependence improves from $O(\sqrt{c(\varepsilon)\alpha})$ to $O(c(\varepsilon)\alpha)$.
• Implication: These improved bounds demonstrate that existing algorithms utilizing square loss (specifically $\chi^2$-Preference Optimization variants) are stronger than previously analyzed.

2.3 Algorithmic Adaptations

Based on these convergence results, the paper proposes or analyzes specific algorithms for different settings:

• Offline Private Alignment (Priv$\chi$PO): A modification of the $\chi$PO algorithm using the standard private MLE log loss.
• Online Private Alignment (PrivXPO): A modification of the XPO algorithm (which uses active exploration) adapted for private labels using log loss.
• Offline/Online Robust Alignment (Square$\chi$PO / SquareXPO): Algorithms utilizing square loss to handle both privacy and corruption simultaneously. These are shown to be adaptive to the specific corruption order (CTL vs. LTC) without prior knowledge.

3. Key Results and Theoretical Guarantees

3.1 Offline Setting

• Private Only: The paper proves that Priv$\chi$PO (using standard log loss) achieves a suboptimality gap of $O\left(\kappa(\pi^*) c(\varepsilon) \sqrt{\frac{\log(|\Pi|/\delta)}{n}}\right)$, where $\kappa(\pi^*)$ is the single-policy concentrability coefficient. This confirms that standard MLE is near-optimal for private alignment.
• Private + Corruption: The analysis of Square$\chi$PO yields improved bounds:
  • CTL: $O\left(\kappa(\pi^*) \left(c(\varepsilon)\sqrt{\frac{\log(|\Pi|/\delta)}{n}} + \alpha\right)\right)$
  • LTC: $O\left(\kappa(\pi^*) \left(c(\varepsilon)\sqrt{\frac{\log(|\Pi|/\delta)}{n}} + c(\varepsilon)\alpha\right)\right)$
    These bounds are shown to be tight (unimprovable) by leveraging lower bounds from offline multi-armed bandit problems.

3.2 Online Setting

• Private Only: PrivXPO achieves a suboptimality gap of $O\left(\kappa_{cov}(\Pi) c(\varepsilon) \sqrt{\frac{\log(|\Pi|T/\delta)}{T}}\right)$, where $\kappa_{cov}(\Pi)$ is the coverability coefficient. This is the first theoretical guarantee for online alignment with label privacy.
• Private + Corruption: SquareXPO provides the first theoretical guarantees for online alignment under both privacy and corruption, achieving bounds analogous to the offline case but dependent on the coverability coefficient and the number of rounds $T$.

4. Significance and Claims

The paper claims to advance the theoretical foundations of private and robust alignment in the following ways:

1. Correction of Misconceptions: It refutes the notion that standard MLE-type log loss is suboptimal for private alignment, showing instead that it achieves near-optimal rates. This simplifies the algorithmic landscape by removing the need for specialized de-biased losses in privacy-only settings.
2. Tighter Bounds for Robustness: It demonstrates that existing algorithms (like Square$\chi$PO) possess stronger theoretical guarantees than previously recognized, specifically improving the dependence on the corruption parameter $\alpha$ and its interaction with privacy $\varepsilon$.
3. Bridging Offline and Online: It extends the theoretical understanding of robust and private alignment to the online regime, showing that active exploration can achieve rates determined by the intrinsic complexity of the policy class (coverability) rather than dataset coverage.
4. General Applicability: The new uniform convergence results for log and square losses under privacy and corruption are presented as having broad applicability beyond alignment, potentially impacting general learning theory and statistics involving noisy or privatized data.

The authors maintain a modest stance, noting that while their theoretical bounds are tight for the specific models considered (Bradley-Terry preferences, Huber corruption, LDP), extending these results to stronger adaptive corruption models or hybrid offline-online settings remains an open challenge. Empirical evaluations on synthetic and real-world datasets (PKU-SafeRLHF) are provided to show that the different loss functions (MLE log, de-biased log, and square) exhibit comparable practical performance, consistent with their theoretical convergence rates.