Differentially Private Sparse Reward Estimation with Preference Feedback

1 Introduction

• Existing private alignment methods treat rewards as dense, while high-dimensional features and limited preference data make dimension-dependent noise problematic.The paper motivates sparsity by evidence that reward functions and feature representations can depend on a small subset of salient features.Source: §1 · p. 2
• Sample-DP-IHT uses iterative hard thresholding with private peeling to protect the interaction tuple, while Label-DP RR+IHT uses randomized response and debiased gradient estimation to protect preference labels.Both algorithms address sparse reward estimation under the Bradley-Terry model.Source: §1 · p. 2
• The squared ℓ2 error upper bounds are eO(s*/n + (s*)^2/(n^2ε^2)) for (ε, δ)-Sample-DP and eO(s*/n + s*/(nε^2)) for ε-Label-DP.Here n is the training data size.Source: §1 · p. 3
• The Sample-DP rate is nearly optimal, while the Label-DP guarantee cannot be improved within randomized response; the paper also gives a general Label-DP lower bound.The general lower bound applies to the Label-DP problem beyond the randomized-response framework.Source: §1 · p. 3
• On Sentiment Generation and Safety Alignment benchmarks, exploiting sparsity consistently yields superior privacy-utility trade-offs than dense DP-SGD and Randomized Response baselines, with significantly higher reward scores and alignment rates in high-privacy regimes.Source: §1 · p. 3

2 Related Work

• Prior private alignment work largely assumes dense rewards or general function approximation, leaving sparse reward learning under privacy constraints unexplored.The surveyed work includes private reward estimation, preference optimization, offline alignment, regularization, self-play, and user-level privacy.Source: §2 · p. 3
• Private sparse learning offers guarantees for regression, local-DP iterative hard thresholding, and sparse spectral estimation, but these results do not directly extend to preference learning.The preference setting combines paired data dependence with the nonlinear Bradley-Terry-Luce model.Source: §2 · p. 3

3 Preliminaries

• The data consist of n i.i.d. labeled comparisons, with a context, two candidate responses, and a label indicating the preferred response.The objective is to estimate the unknown reward parameter by maximizing comparison likelihood subject to privacy constraints.Source: §3 · pp. 3–4
• Preferences follow the Bradley-Terry-Luce model, with a linear reward rθ(k, a) = ⟨ϕ(k, a), θ⟩ and comparison-difference features.Under this parameterization the conditional preference distribution reduces to logistic regression.Source: §3 · pp. 3–4
• The high-dimensional setup assumes bounded comparison features and covariance eigenvalues bounded between positive constants.The paper uses an ℓ∞ feature bound, ∥x∥∞ ≤ 1, rather than an ℓ2 bound; it notes this permits covariance eigenvalues µ, γ = Θ(1).Source: §3 · p. 4
• Sample-DP protects an entire comparison record, whereas Label-DP protects only its preference label while holding features fixed.The paper describes Sample-DP as a strictly stronger guarantee because it also conceals the query context.Source: §3 · p. 4

4.1 Sample-DP

• Sample-DP-IHT splits data across gradient updates and uses private peeling to select the s largest-magnitude coordinates at each iteration.The mechanism zeros the remaining coordinates after support selection.Source: §4.1 · p. 5
• Sample-DP-IHT has error polynomial in s* rather than d, and its lower bound matches up to logarithmic factors, establishing near-minimax optimality.The comparison with dense results uses different feature-normalization assumptions and is not obtained by simply setting s*=d.Source: §4.1 · pp. 5–6

4.2 Label-DP

• Label-DP treats feature vectors as public and preference labels as sensitive, then combines randomized response, debiased gradients, and standard IHT.The debiased gradient is an unbiased optimization direction, and subsequent updates incur no additional privacy cost because they post-process privatized labels.Source: §4.2 · pp. 6–7
• RR+IHT achieves an eO(s*/n + s*/(nε^2)) bound, replacing dense methods’ ambient-dimension dependence with sparsity, up to logarithmic and condition-number factors.The bound is for the central Label-DP setting.Source: §4.2 · p. 8
• The randomized-response lower bound shows that the Label-DP estimator cannot be improved within the RR-based framework, up to logarithmic and condition-number factors.The result is also interpreted as a sparse lower bound for estimators using locally privatized labels.Source: §4.2 · p. 8
• A general lower bound applies to any central Label-DP mechanism, but a gap remains between that bound and the estimator’s upper bound.Improving privacy dependence beyond randomized response remains an open question.Source: §4.2 · p. 8

5.1 Experimental Setup

• The evaluation covers sentiment generation on IMDb and safety alignment on harmful prompts, comparing sparse methods with DP-SGD and randomized response baselines.The policy networks are LLaMA-7b for sentiment generation and Gemma-3-1B for safety alignment; competing methods share architectures and initializations.Source: §5.1 · p. 9

5.2 Experimental Results

• At ε=2 and ε=8, DP-IHT and RR-IHT achieve higher rewards than DP-SGD and RR at any given KL divergence in sentiment generation.The reported comparison is summarized in Figure 1 and Table 2.Source: §5.2 · p. 9, Table 2 · p. 9
• At ε=8, Gemma-3-1B win rates were 62% for Label-DP RR-IHT, 55% for Sample-DP IHT, 51% for RR, and 47% for DP-SGD; Llama-2-7B rates were 70%, 62%, 58%, and 53%, respectively.Figures 2 and 3 report safety-alignment win rates for Gemma-3-1B and Llama-2-7B, respectively.Source: §5.2 · pp. 9–10, Figure 2 · p. 9, Figure 3 · p. 9

• The paper introduces Sample-DP-IHT and Label-DP RR+IHT for sparse reward estimation under the BTL preference model.The framework also provides a general lower bound for arbitrary central Label-DP mechanisms.Source: §6 · p. 10
• The Sample-DP rates are nearly minimax-optimal, while RR-based Label-DP guarantees cannot improve within the randomized-response framework.The paper also gives a general lower bound for arbitrary central Label-DP mechanisms.Source: §6 · p. 10
• Experiments on sentiment generation and safety alignment show improved privacy-utility trade-offs over dense baselines in the d ≫ n regime.Source: §6 · p. 10

• Sentiment reward models are evaluated with a fixed independent evaluator, while safety alignment is evaluated by win rate against baseline models.The sentiment scores are reported every 20 training steps; safety prompts come from the toxic-prompts dataset.Source: A Addition Experimental Details and… · p. 15
• Both safety-alignment models use the same PPO settings, including RMSProp, a 10^-5 learning rate, KL penalty 0.15, LoRA rank 16, and LoRA alpha 32.The shared configuration is intended to keep performance differences mainly attributable to reward-estimation methods.Source: A Addition Experimental Details and… · p. 15, Table 3 · p. 15
• At ε=2, Label-DP RR+IHT improves win rates over dense RR from 51% to 57% on Gemma-3-1B and 53% to 65% on Llama-2-7B; Sample-DP-IHT improves over DP-SGD from 43% to 53% and 50% to 60%, respectively.Figures 4 and 5 show the Gemma-3-1B and Llama-2-7B results, respectively.Source: A Addition Experimental Details and… · p. 15

• Sentiment scores use a fixed independent evaluator, and safety win rates are judged by GPT-4.1; evaluators remain fixed across methods and privacy budgets.The models start from public pretrained checkpoints, and no SFT stage uses sensitive user data.Source: §A.1 · p. 15
• PPO uses the private reward model and public prompts, making PPO post-processing with respect to private preference-training data.Source: §A.1 · p. 15
• The additional safety-alignment figures cover Gemma-3-1B and Llama-2-7B at ε=2.Source: Figure 4 · p. 16, Figure 5 · p. 16

A.2 Non-private Reference and Direct Reward-model Evaluation

• 2.44 and 2.88 are the highest private policy scores at ε = 2 and ε = 8, versus 3.07 for the non-private reference.The corresponding absolute score gaps are 0.63 and 0.19.Source: Table 4 · p. 16, §A.2 · p. 16
• 0.0135 and 0.0028 are the DP-IHT and RR-IHT NLL gaps versus the non-private reference; preference accuracies are lower by 0.67 and 0.04 percentage points.Table 5 reports direct held-out reward-model performance.Source: Table 5 · p. 16, §A.2 · p. 16

A.3 Reward-model and PPO Learning-rate Sensitivity

• 10^-4, 10^-4, 10^-3, and 10^-2 are the lowest-loss learning rates for DP-SGD, RR, DP-IHT, and RR-IHT within the tested grid.The additional reward-model learning-rate search is reported in Table 6.Source: §A.3 · p. 16, Table 6 · p. 17
• 59%, 57%, 55%, and 47% are the highest safety-alignment win rates in the tested grid for RR-IHT, DP-IHT, RR, and DP-SGD.The sweep uses Gemma-3-1B at ε = 8; the comparison policy and evaluation sample size remain unspecified.Source: §A.3 · p. 16, Table 7 · p. 17

B Supported Lemmas and Facts

• Under bounded covariance eigenvalues, L_D is α-strongly convex on the ball ||θ||2 ≤ B, with α = m(B)µ.The stated covariance condition bounds the minimum and maximum eigenvalues of Σ.Source: B Supported Lemmas and Facts · p. 17

C.1 Proof of Theorem 4.1

• Disjoint data subsets are processed by iterations whose peeling mechanism satisfies (ε, δ)-DP, so parallel composition gives Algorithm 1 an (ε, δ)-Sample-DP guarantee for the full dataset.The proof invokes the Parallel Composition Theorem through sample splitting.Source: §C.1 · p. 17
• The proof tracks the supports of successive iterates and the target parameter; the stated bound is |I_t| ≤ 2s + s*.The passage defines S_t and S_t+1 as the supports of w_t and w_t+1, respectively.Source: §C.1 · p. 17
• The stated loss inequality relates the squared distance to the target parameter to the population-loss difference under the covariance and parameter assumptions.The inequality uses γ and m(B)µ as its bounding coefficients.Source: §C.1 · p. 23

C.2 Proof of Theorem 4.4

• The score attack measures correlation between estimation error and a candidate point's score function; successful attack implies a privacy violation, limiting estimator accuracy.The proof uses this connection to motivate the lower-bound argument.Source: §C.2 · p. 24
• The lower-bound setup uses sparse logistic preference observations, with diagonal covariance, bounded maximum covariance eigenvalue, bounded feature infinity norm, and bounded second derivative of ψ.The supplied assumptions include λmax(Σ) ≤ γ, ||x||inf < 1, and ||ψ''||∞ < 1/4.Source: §C.2 · p. 24

C.3 Proof of Theorem 4.5

• Each randomized-response label satisfies ε-DP, and post-processing preserves that guarantee for the final output θ_T.The privatized label set satisfies ε-Label-DP.Source: §C.3 · p. 25
• The utility proof uses debiased gradients after randomized response; its first and last terms vanish because index selection and the final released output receive no added noise.The passage contrasts this with Theorem 4.1 and states the resulting bound holds with probability at least 1 − δ for all t ∈ [T].Source: §C.3 · p. 26

C.4 Proof of Theorem 4.7

• The lower-bound proof constructs sparse, Hamming-separated parameter vectors, then uses KL bounds and Fano’s inequality for its non-private part.The private construction is a subset of binary vectors with Hamming weight s.Source: §C.4 · pp. 26–27

C.5 Proof of Theorem 4.9

• The proof restricts parameters to a fixed support and uses a sparse hypercube, classical Assouad’s lemma, and a coupling argument for the central Label-DP lower bound.The covariates are public under Label-DP, so the proof conditions on them; the supplied passages do not show the resulting lower-bound formulas.Source: §C.5 · pp. 27–29

Limitations

• The analysis covers sparse linear reward estimation under BTL; extending it to nonlinear or neural rewards and other sparsity forms remains future work.Source: Limitations · p. 29

Broader Impact

• The work aims to reduce privacy costs in high-dimensional reward estimation, while noting that real deployments still require standard safety and bias evaluations.Source: Broader Impact · p. 29

NeurIPS Paper Checklist

• The checklist answers yes on complete theoretical proofs, experimental reproducibility, and error-bar reporting, and says code will be released after the public version.Source: §2 · pp. 30–32
• The paper reports that it releases no new assets and says all assets are cited.The license question is answered [N/A], with the justification that all assets are cited; the new-assets question is answered [N/A] because no new assets are released.Source: §2 · pp. 34–35
• The paper reports no crowdsourcing or research with human subjects, and answers [N/A] to the related participant-instructions and IRB questions.Source: §2 · p. 35
• The paper says its core method development does not involve LLMs as an important, original, or non-standard component.Source: §2 · p. 36