Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective

We thank the reviewer for the thoughtful and constructive feedback. We are glad that the reviewer found the theoretical contributions comprehensive, the experiments well-designed, and the writing clear in presenting the connections between sparsity and preference learning. Below, we respond to each of the comments in detail.

(1) "It focuses solely on the fixed design setup (i.e., a deterministic set of pairs) and does not address generalization error." "To address the limitation of the fixed design setup, can we explore ways to generalize the model?"

We appreciate the reviewer for this comment. While our current study focuses on a fixed design setup, this setting is commonly encountered in real-world applications, such as crowdsourced comparisons or benchmark datasets, where the pairwise comparisons are predetermined. That said, extending our analysis to the random design setup and studying generalization error is an exciting and important direction for future work. We thank the reviewer for highlighting this point. In particular, recent work on linear regression under random design (e.g., [1-3]) may provide valuable insights. For example, as suggested in [2], techniques from random matrix theory and random projections may be helpful for such an extension.

[1] https://jmlr.org/papers/volume23/19-571/19-571.pdf

[2] https://arxiv.org/pdf/2303.01372

[3] https://arxiv.org/pdf/2203.08564

(2) "The experimental results primarily focus on the accuracy of the reward model. Can we take this further by evaluating LLMs after applying PPO with the sparsity-regularized reward model?"

We thank the reviewer for this suggestion. Indeed, a natural extension is to evaluate LLMs fine-tuned via PPO using the learned reward model. For example, given a set of prompts, one could compare LLM-generated responses through human evaluation or an oracle model, using win rate as a downstream metric. Although we initially considered such a metric, we eventually chose not to pursue it in this paper to maintain our focus on reward modeling without incorporating additional policy optimization. Nonetheless, we agree with the reviewer that this evaluation approach is a compelling direction for future work.

(3) "Maybe I missed the details, in Appendix D.2, you report accuracy versus the number of samples. How are these samples selected? Are they guaranteed to be the same set for training with and without L1 regularization?"

Yes, we use the same set of samples across models to ensure a fair comparison. Specifically, for each trial, the training data is sampled uniformly at random and fixed in advance; this identical dataset is then used to train both the regularized and unregularized models. We will make this point more explicitly in the revised version.

(4) "Just brainstorm, to verify the presence of sparsity in LLMs, could we train a reward model without regularization at different sample sizes, measure its sparsity, and analyze whether sparsity naturally increases as training progresses?"

We appreciate this interesting idea. In theory, the estimation error in $\ell_2$-norm $\lVert\hat{\theta} - \theta^*\rVert_2$ without sparse-regularization will gradually be small given that 1) the number of samples is sufficiently large relative to the feature dimension $d$, and 2) the Gram matrix $\Sigma$ is well-behaved, e.g., satisfying the restricted eigenvalue condition. As a result, in practice, if the ground-truth parameter $\theta^*$ is sparse, the learned parameter would be sparse even without regularization under the above conditions. Nonetheless, given the high dimensionality of the feature space in LLM-based reward models, the current dataset does not meet the scale required for such behavior to emerge. We appreciate the suggestion and agree that this would be an interesting empirical direction to pursue with enough annotated data.

We once again thank the reviewer for the recognition and thoughtful questions. We believe these discussions will help guide valuable extensions of this work.

We thank the reviewer for the thoughtful and constructive feedback. We greatly appreciate the recognition of our theoretical contributions and the time taken to carefully examine the proofs of our four main theorems. Below, we address the comments and questions in detail.

(1) Evidence for k-sparse assumption for RUM. "I think the k-sparse claim for RUM needs further evidence…"

We thank the reviewer for raising this point, which was also noted by Reviewer ACSW. A detailed response is provided there in (2) On the sparsity assumption and its practical validity. Due to space constraints, we refer the reviewer to that response. Here, we offer additional clarifications specific to the reviewer’s comments.

• "I wonder if there're other baselines the authors could use in the literature to support this assumption…"

  As noted in the introduction, the theoretical and empirical foundations for sparsity in preference learning remain largely underexplored. Nevertheless, we observe increasing interest in related domains. For example, a very recent work by Jin et al. (Sparsity-Agnostic Linear Bandits with Adaptive Adversaries, NeurIPS 2024) studies sparsity in linear reward functions in the context of adaptive bandits. While not directly addressing pairwise comparisons, this work provides complementary motivation for sparse reward structures.

• "the second experiment uses the prediction accuracy as the evaluation metric, which is supportive but not directly linked to the sparsity assumption"

  We thank the reviewer for the constructive feedback. Empirically, we observe that the learned parameters under $\ell_1$ regularization are indeed highly sparse. For example, in Figure 4 (frozen backbone setting), the learned sparsity level $k/d$ is around 4-8% for both datasets, and the sparsity-aware method consistently outperforms the baseline. These results help to empirically validate the sparsity assumption. We will include these results in the updated version.

(2) Real-Data Experiments.

• "the second experiment could be conducted with one more dataset…" "The experiments lack sufficient baselines."

  We thank the reviewer for this suggestion. In addition to rm-static, we include results on the SHP dataset in Appendix D due to page limitation. Notably, SHP contains human-written responses, while rm-static contains machine-generated ones, giving us two distinct distributions, as mentioned by Ethayarajh et al., (2022). In both cases, $\ell_1$ regularization outperforms the baseline.

• "However, the rm-static dataset… may contain noise [2], reducing the reliability of the experiment results. The authors should consider adding a cleaner dataset for experiment."

  We thank the reviewer for the observation. While rm-static is widely used as a benchmark dataset for alignment-based preference learning, we agree that evaluating on cleaner datasets, or applying data-filtering techniques (e.g., confidence-based data filtering in [2]) beforehand, could provide additional value. We are very interested exploring this direction and will consider it in the future work.

• "Are there any other evaluation metrics for the quality of reward models in experiment 4.2?"

  We thank the reviewer for this question. One indirect way is to evaluate the performance of an aligned LLM associated with the reward models. Specifically, one can sample prompts, generate responses from the aligned LLMs, and then assess quality via human annotation or an oracle model. The win rate of the aligned LLM can serve as a downstream measure of the quality of the reward model.

(3) Synthetic Experiments. "The experiment 4.1 validates the effectiveness of l1-regularization compared with standard MLE in the preference learning case. However, the ground-truth is manually set to be sparse, which undermines this experiment." "Is the experiment in section 4.1 necessary? … what is the main difference between preference learning under sparsity and previous literature?"

We thank the reviewer for this question. As correctly pointed out, the purpose of Experiment 4.1 is not to justify the sparsity assumption, but to validate the effectiveness of $\ell_1$ regularization in the sparse RUM setting. It serves as a sanity check for our theoretical analysis, which provides estimation error bounds under sparse ground truth. While $\ell_1$ regularization has been well-studied in sparse regression and related settings, sparse preference learning under RUM poses unique challenges. In particular, each pair of data only provides one-bit comparison feedback, rather than direct access to real-valued rewards. For completeness, we include the numerical experimental results in Section 4.1 in the paper.

We thank the reviewer again for the constructive comments and the recognition of our work. We will incorporate the above clarifications, along with other suggestions from the reviewer, in our updated version.

We thank the reviewer for the thoughtful feedback and the recognition of our theoretical contributions, the clarity of our motivation, the novelty of applying sparsity to preference learning, and the solid experimental setup. Below, we address the concerns and questions:

(1) On the empirical gains (~3%). “The improvement they report is only about 3%, which isn’t huge. It raises the question of whether the extra effort is worth such a small gain”

• Limited room for improvement due to inherent randomness. Under RUM, the probability of a pairwise preference is given by $P(A\succ B) = F(\frac{r^*(A) - r^*(B)}{\sigma})$, which captures the inherent randomness in human decision-making. Thus, the same pair (A, B) may receive conflicting annotations, fundamentally bounding the maximum achievable test accuracy. For example, if 7 out of 10 data points prefer $A\succ B$, and 3 prefer $B\succ A$, then the maximum achievable accuracy on this pair is 70%. In real-world datasets, [1] reports 19–37% of crowd-labeled preferences are noisy. This implies that even with the ground-truth model, the expected accuracy would be limited to roughly 63–81%. Given that a random guess yields 50% accuracy, a 3% improvement represents a substantial fraction of the remaining improvement room.
• Consistent gains and interpretability with negligible extra effort. Adding regularization term to the training loss does not change the model architecture and incurs marginal overhead. Despite its simplicity, $\ell_1$ regularization consistently improves performance, particularly in low-sample regimes. Moreover, the sparsity induced by $\ell_1$ regularization enhances interpretability by identifying the most relevant features for the preference model of interest.

(2) On the sparsity assumption and its practical validity. “It is unknown how often the ground-truth parameter is sparse in real-world application. Hence, it is unclear how effective the approach actually is.” “Can you provide insights or examples when your assumptions are realistically met or potentially violated?”

• When does sparsity arise? Sparsity commonly emerges in classical preference learning, especially in high-dimensional feature space where human preferences are influenced by only a few factors. For example, a user’s preference for smartphones may depend primarily on price, camera quality, and UI design, whereas many other attributes (e.g., place of manufacture) may have little influence for that user. Similarly, a reader’s preference over articles may depend solely on the presence of a few key words. When the feature vector is a binary indicator over a large vocabulary, the reward parameter is naturally sparse.

• When might the assumption be violated? Sparsity may not hold when the feature space is low-dimensional (e.g., 3–5 features), or when features have been manually curated. In such cases, the benefits of sparsity-aware estimation are expected to diminish. Nonetheless, in many modern applications, such as LLM alignment or recommendation systems, feature spaces often contain thousands to millions of dimensions. In these settings, identifying relevant features beforehand is infeasible, making sparsity both a practically and necessary modeling assumption.

• Empirical support in LLM alignment. Our LLM alignment experiments show that $\ell_1$ regularization induces highly sparse models while outperforming the baseline, even without hyperparameter tuning. For example, in the frozen backbone training setup (Figure 4, Section D.2), where the pre-trained model defines the feature map $\phi$, we observe:

  • rm-static dataset: $k/d\approx$ 4.5% (n=800) and $k/d\approx$ 7.5% (n=3200).
  • SHP dataset: $k/d\approx$ 4.2% (n=800) and $k/d\approx$ 7.2% (n=3200).

  These results show that $\ell_1$ regularization selects a small and informative subset of features, reinforcing the practical validity of the sparsity assumption.

(3) Implication on DPO. “Can you share a few insights about the implication of your work on DPO?”

DPO ([2]) bypasses explicit reward modeling by directly optimizing the policy, where $\beta \log(\pi/\pi_{\text{ref}})+\beta\log Z$ acts as a proxy reward that depends on the policy $\pi$. This contrasts with reward-based approaches, where reward and policy are decoupled, allowing assumptions (e.g., sparsity) and regularization to be applied directly to the reward model. However, since DPO couples the reward signal with the policy and the policy architecture is fixed, incorporating sparsity-aware regularization is non-trivial. Additionally, even when the reward model $r(x)$ is sparse, the parameter of the optimal policy $\pi^*(x) = \frac{1}{Z}\pi_{\text{ref}}(x)\exp(\frac{1}{\beta}r(x))$ is not necessarily sparse.

We thank the reviewer again for the insightful comments. We will incorporate the discussion in the updated version.

[1]https://arxiv.org/pdf/2306.05685

[2]https://arxiv.org/pdf/2305.18290

We appreciate the reviewer’s recognition of the clarity of our presentation, the significance of the theoretical contributions, and the relevance of our work to both RLHF and choice modeling. We also thank the reviewer for taking the time to examine the proofs, and are glad that the experimental results were found solid. We address the reviewer’s comments and questions below.

(1) Comparison with Bower & Balzano (2020). "One important related work on RUMs with sparse features is not discussed." "How does this model and these sample complexity results compare to those in Bower & Balzano (2020)?"

We thank the reviewer for pointing out this closely related paper. While both works consider comparisons based on a subset of features, there are two key differences: 1) In our setting, the subset of relevant features, which correspond to nonzero entries in a globally sparse parameter vector, is fixed across all comparisons. In contrast, Bower & Balzano (2020) identify salient features in a context-dependent manner, selecting those with the largest pairwise variance for each comparison. 2) Our subset of features are selected through optimization whereas Bower & Balzano (2020) select feature sets through sample variance of features. As a result, their model is not globally sparse, and the corresponding estimation rate is $O(d \log (d))$, whereas our analysis yields a sharper rate of $O(k \log (d/k))$ under global sparsity.

(2) Clarifying the rate from Zhu et al. (2023). "The bounds in Zhu, Jordan, and Jiao 2023 appear to be rather than as stated Table 1. Is there something I'm missing about their results?"

We thank the reviewer for this observation. We note that our results are stated in terms of the squared semi-norm $\lVert \cdot \rVert_\Sigma^2$ as the error metric, whereas Zhu et al. (2023) report bounds in terms of the semi-norm $\lVert \cdot \rVert_\Sigma$. We will clarify this in the caption of Table 1 to avoid confusion.

(3) Brief review of the listed works. “A few other papers that could have been in the related work, but are not essential (listing in case the authors were not aware of these and feel that any of them are worth including)”

We thank the reviewer for highlighting these additional related works and pointing out their connection to our work. We will include the references and discussion in the updated version of the paper.

We will incorporate the above discussion, along with the other suggestions mentioned by the reviewer, in our updated version of the paper.