Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Authors: Yunzhen Yao
Lie He
Michael Gastpar
Venue: ICML 2025 poster (2025)
Keywords: preference learning
RLHF
sparsity
statistical estimation
reward modeling
sample efficiency
Primary area: social_aspects->alignment

Abstract: This paper considers the sample-efficiency of preference learning, which models and predicts human choices based on comparative judgments. The minimax optimal estimation error rate $\Theta(d/n)$ in classical estimation theory requires that the number of samples $n$ scales linearly with the dimensionality of the feature space $d$. However, the high dimensionality of the feature space and the high cost of collecting human-annotated data challenge the efficiency of traditional estimation methods. To remedy this, we leverage sparsity in the preference model and establish sharp error rates. We show that under the sparse random utility model, where the parameter of the reward function is $k$-sparse, the minimax optimal rate can be reduced to $\Theta(k/n \log(d/k))$. Furthermore, we analyze the $\ell_{1}$-regularized estimator and show that it achieves near-optimal rate under mild assumptions on the Gram matrix. 
Experiments on synthetic data and LLM alignment data validate our theoretical findings, showing that sparsity-aware methods significantly reduce sample complexity and improve prediction accuracy.

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Yunzhen Yao
Lie H
Michael Gastpar'
Abstract
preferences (Resnick & Varian, 1997: Rendle al., 2009; He et al., 2017). Similarly, information retrieval systems can leverage user clickthrough data from search-engine query logs to improve the relevance of retrieved results (Joachims, 2002; Burges et al., 2005; Liu et al., 2009). More recently, large language models (LLMs) are often pretrained on large- scale internet data, which may contain harmful biased content, making direct deployment risky. Learning from hu- man preferences is thus adopted to align pretrained models with human values and objectives (Christiano et al., 2017; Stiennon et al., 2020; Ouyang et al., 2022; Bai et al., 2022).
This paper considers the sample-efficiency of preference learning, which models and pre- dicts human choices based on comparative judg- ments. The minimax optimal estimation error rate (d/nn) in classical estimation theory requires that the number of samples scales linearly with the dimensionality of the feature space d. How- ever, the high dimensionality of the feature space and the high cost of collecting human-annotaan annotated data challenge the efficiency of traditional esti- mation methods. To remedy this, we leverage sparsity in the preference model and establish sharp error rates. We show that under the sparse random utility model, where the parameter of the reward function is k-sparse, the minimax optimal rate can be reduced to @kk/n log(d/k)). Further- more, we analyze the & reggulaaree estimator and show that achieves near-optimal rate under mild assumptions on the Gram matrix. Experiments on synthetic data and LLM alignment data validate our theoretical findings, showing that sparsity- aware methods significantly reduce sample com- plexity and improve prediction accuracy.
Preferences among alternatives can be represented by a real-valued utility function, where a higher function value corresponds to more preferred option, provided that the preference relation is complete, transitive, and continuous, according to Debreu's 's representation theorem (Debreu et al., 1954). Moreover, to account for inconsistencies and random- ness in human decision decision-making arising from subjective interpretations, ambiguous guidelines, and fluctuating fo- cus-a deterministic utility function can be extended to stochastic utility model, in which the probability of choos- ing one alternative is higher when its utility is greater. This paper focuses on learning preferences by training a parame- terized random utility model.
A major challenge in preference learning is the high cost of collecting human preference data (Gao et al., 2023; Wang et al., 2023; Mahan al., 2024). For example, aligning L.MMs with human values requires significant amount of samples labeled by experienced human annotators who select the most "helpful" and "harmless" response among all candidates. This difficulty is compounded by the fact that alternatives often lie in feature spaces whose dimensionality far exceeds the number of available samples n, leading to high estimation error ((/nn) for prevalent maximum likelihood methods (Shah et al., 2016; Faury et al., 2020; Saha et al., 2023; Zhu et al., 2023).
1. Introduction
1.1. Motivation
Preference learning focuses on modeling and predicting subjective choices or priorities from empirical comparative data to support tasks such as decision- maainn, ranking, and recommendation. For example, commercial recommender systems select items from a set of candidates based on user
'LINX, EPFL, Lausanne, Switzerland Key Laboratory Inter- disciplinary Research of Computation and Economics (Shanghai University of Finance and Economics), Ministry of Education, China 'School of Computing and Artificial Intelligence, Shanghai University of Finance and Economies, Shanghai, China. Corre- spondence to: Yunzhen Yao eyunzhen.yao yao@epfl..c..
While alternatives may have thousands of attributes (di- mensions), human preferences are usually driven by only a small set of critical factors in a given context. For instance, when a user selects among smartphones, the decision might hinge primarily on price, camera quality, and UI design, whereas many other attributes (e.g., place of manufacture)
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
Table 1. Estimation error rates for preference learning in non-sparse and sparse settings with error metric || I. Notation: d is the ambient dimension, & is the sparsity level, and n is the sample size.
Non-Sparse Settings
Minimax Optimal
Minimax Optimal
log(d/k)
Theorem 3.1 and 3.2
Sparse Settings
( Regullarized (Slow)
O
log d T2
Theorem 3.3
f ReRgullarree (Fast)
O
log d
Theorem 3.4
(Shah et al., 2016; Faury et al., 2020; Saha et al., 2023; Zhu et al., 2023).
may have little influence for that user. Similarly, reader's preference over articles may depend solely 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. Moreover, in many modern applications, such as LLM alignment or recommendation systems, feature spaces often contain thousands to millions of dimensions, rendering identifying relevant features beforehand imprac- tical. The concept of sparsity offers a promising way to address the above challenges. Building on this idea, the well-established field of compressed sensing demonstrates how leveraging sparsity can significantly reduce sample complexity (Donoho, 2006; Candes & Tao, 2006; Tropp & Gilbert, 2007; Ye & Zhang, 2010; Rigollet& & Tsybakov, 2011; Raskutti et al., 2011: Verzelen, 2012; Candes & Dav- enport, 2013), making sparsity- approaches particu- larly promising for preference learning. Despite successes in other domains, the theoretical and empirical foundations of sparsity in preference learning remain underdeveloped, pointing to a rich area for further study.
theoretical lower bound of 2 ((k/n) log(d/E)) for the empirical estimation error in the sparse RUM setting, contrasting it with (dd/n) in the non-sparse setting.
Minimax optimal rate. We show that an to- constrained estimator achieves the minimax-optimal rate under the common strong log-concavity assump- tion that covers a class of popular models like Bradley- Terry-Luce (BTL) model (Bradley & Terry, 1952; Luce, 1959) and Thurstone-Mostellee (TM) model (Thur- stone, 1994; Mosteller, 2006).
Upper bounds for the lj-regularized estima- tor. We show that, with a penalty of @(1/Vn), the fi-regularized estimator achieves the rate O (V(k/n)logg logd). Furthermore, under certain as- sumption on the spectrum of the Gram matrix, it at- tains a sharper rate O ((k/n) log d), which is nearly minimax optimal.
Experimental evaluation. Our experimental evalua- tions demonstrate that sparsity-aware estimators out- perform widely used baselines in reward modeling, evaluated on both synthetic datasets and LLM align- ment datasets using popular language models. These findings underscore the potential of sparsity-aware approaches in preference- tasks, including rein- forcement learning from human feedback (RLHF).
1.2. Contribution
In this paper, we focus on the problem of sample-efficient estimation for preference learning models. Since the sam- ple complexity scales linearly with the ambient dimension (Shah al., 2016; Faury al., 2020; Saha al., 2023; Zhu et al., 2023), the high dimensionality of the ambient space poses a bottleneck for accurate estimation. To ad- dress this challenge, we consider the sparse RUM setting (see Equation (5) below), where the model parameter is k- sparse. Under this assumption, we show that the upper and lower bounds on estimation error rates can be improved with respect to d. To the best of our knowledge, this work is the first theoretically investigate sparsity in preference learn ing and analyze its impact estimation rates. Specifically, our contributions are as follows.
We summarize the estimation error rates across different settings in Table 1. contrast to classical regression prob- lems, which rely on cardinal labels of measurable quantities, preference learning only has access to pairwise comparison data, each providing most one bit of information. Despite these challenges, our upper and lower bounds on estima- tion errors remain in the same order as those in classical
Codee can be found this link: https: http//gttttccoooo////
Minimax lower bound. We establish an information-
2

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
compressed sensing (Donoho, 2006; Candes & Tao, 2006; Tropp & Gilbert, 2007).
The goal of preference learning is to estimate the parameter #* of the reward function r*, based on preference samples {6: {
2. Preliminaries
Maximum likelihood (ML) estimator. Given samples
2.1. Problem Formulation of Preference Learning
{ fi=1 the negative log-likelihood for parameter 0 R is defined
Let A be a set of alternatives, and let Φ :AA + IRd be a fixed and known feature map, where d(a) represents a d- dimensional feature vector corresponding
Σ log ((-1)") (0, 2o.) (8, x1.))
<(; (c)
E A. The
feature space of A induced by di is defined the image of db, denoted D> ((A) Rdd A preference relation defined on D satisfies Debreu's 's representation theorem can be char- acterized by reward or utility function r". Specifically, for two feature vectors To, 21 E 'D such that rat < r (x1), we state that Jı is preferred to zo, denoted as zg < Z1. The ground-truth reward function r" fixed and unknown. We assume that the feature map á on accounts for the non-linearity, whereas r" is linear.
We suppose that 0 is bounded by a constant, i.c.,
lr E θ = {0 R |0112 S B).
The maximum likelihood (ML) estimator 0 is defined as
ÔMI. arg min L(0, (1))))) DEO
Performance measure. We measure the performance of estimate 0 using the empirical error, defined as
Consider preference dataset comprising n pairs of samples drawn from D, denoted as { where each sample & is represented as
n2
((f(zo.) f(x1,,)) (r" (x0,) r" (21,))))
& (20,i, vi) D D 10.
71
Here, To,; == ((a,s) and T1,5 := )(a1;) are the feature vectors of the alternatives being compared. The binary vari- able y/ is the preference signal, with y; 0 indicating æ0 is observed to be preferred over 21,6. and y indicat- ing the opposite. In this paper, we consider fixed design setup, where { x1,,) Y==1 is deterministic, and {3t | is the realization of the set of random variables {Y Specifically, Y, conforms to the random utility model.
1
0 0", J0,; xI..)
n
where the estimated reward function associated with ê. The Gram matrix E E Rdxd also called the data covariance matrix, associated with
X [ -1,1) (20,n =1,))l E Radd is defined by
Random utility model (RUM). To account for potential inconsistencies or randomness in human decision- -akiing. the random utility model assumes that the probability of choosing zo is higher than choosing 21 if r" rxo) is greater than r=(1)). Specifically, the conditional distribu- tion Py (x.,
n
Σ Σ x - n.
(fo. (0os--21,,000 (1,4) - x1,))
n
The Gram matrix induces semi-norm
0 x = VOTEA, 0 PER'
P(Y- = Zo, x1) = (r"(x))-r'((1)
-r* (21))
(1)
often called the data-induced semi-norm. The empirical error the estimation error in the squared data-induced semi-norm, i.e.,
σ
where F R + [0, satisfies F(L) = 1 1 and E R is the randomness level of Y. If F(t) is the sigmoid function, i..,, Ftt) = -2) then (1) corresponds to the well-known Bradlcy- -erlee--Terr--uccee (BTL) model (Bradley & Terry, 1952; Luce, 1959). If Ftt) is the cumulative distribu- tion function of the standard Gaussian distribution, then (1) becomes the Thurstone- Mostellle (TM) model (Thurstone, 1994; Mosteller, 2006).
12 0" ,0, - -21.5
0
(4)
Σ
Evaluating the estimation error using the squared data- induced semi-norm yields estimation error rates independent of data distribution.
We assume y* D + R is parameterized by 0* E [Rd, i.e.,
In the rest of the paper, we use the term reward, while noting utility is often used interchangeably in related contexts. The complete list of notations can be found in Appendix B.
(x) 10" .²)
3

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
2.2. Preference Learning and RLHF
space D is bounded, i.e., there is constant such that
Preference learning serves as foundational component of Reinforcement Learning with Human Feedback (RLHF). Here focus reward-baser RLHF.
|| - - - L, Vz1, 12 E D.
(6)
The parameters and L, along with the function F and the randomness level a, determines parameter ( defined
A preparatory step for RLHF is supervised fine-tuning (SFT), which fine-tunes the pretrained model on high- quality demonstration data, enabling the model to mimic the provided examples (e.g., summarizations or dialogues).
ma (t) : F(BL/o) (1-FL//)
(7)
We observe that when B = L S = 1.99 in the BTL model and 1.19 in the TM model, respectively. In practical scenarios, since the problem- dependent parameters and are generally independent of d and n, the parameters B, L, o, and have O(1) values (Negahban et al., 2017; Shah et al., 2016). We thus consider these parameters to remain fixed.
1, the parameter
Next, RLHF aligns the model's behavior with human pref- erences by using human feedback. Let S denote the prompt (state) space and A represent the set of responses (actions or alternatives). For reward-baat based RLHF, the first step is to train a reward model to approximate the unknown re- ward function reflecting human preferences from the human preference data {s, du,s 01,s, is where y E {0, 1} indi- cates whether 00 or (11, is chosen as the preferred response given prompt 8;- This step is called reward modeling, and is exactly the problem of preference learning formulated in Section 2.1. To be specific, let & be known and fixed fea- ture mapping Φ(s, a) : x A + Rd, typically a language model with the last layer removed. For a given prompt 8; E S, the image (s;; A) is the feature space in prefer- ence learning. With the feature map Φ, the preference data can be represented {ō(s;; i), pp a1,;), y:l
In Section 3.1, we establishes an information-thhorrtiicll lower bound for sparse preference learning. In Scction 3.2.1, we demonstrates that the fg-constrained estimator achieves the minimax optimal rate. In Section 3.2.2, provides two estimation error rates for the l f1-regularized estimator under difference assumptions. All the proofs are presented in Appendix E.
3.1. Minimax Lower Bound
Once reward model is trained, the remaining step of RLHF is to further fine-tune the supervised fine-tuned (SFT) model using reinforcement learning (RL) algorithms, leveraging the reward model to optimize the policy for better alignment with human preferences and objectives.
To characterize the fundamental limits of sparse preference learning, Theorem 3.1 establishes a minimax lower bound for the empirical error (4).
Theorem 3.1 (Minimax lower bounds). Consider the sparse RUM (5) with k S rank(E))/8. For a sample size
In this work, we focus exclusively on preference learning (reward modeling), leaving other components of the RLHF process, including SFT and RL, unmodified.
o²
log (1+ rank (E)
(8)
64 (Trmn(())))))
2k
where Xnan)(2)) denotes the smallest non-zero eigenvalue of Σ, any estimator 0 derived from samples satisfies
3. Theoretical Foundations of Sparse Preference Learning
0² klog (1
ron
inf sup E
2
2k
(9)
We propose sparse preference learning, wherein the ground- truth parameter 0" in Equation (2), and accordingly the
0 8" E-B
n
where Ç is defined in (7).
RUM framework in (I), is k-sparse, with & potentially un- known. Formally, we consider the sparse RUM as follows.
The proof of Theorem 3.1 is provided in Appendix E.1. Corollary 3.1. Suppose the assumptions in Theorem 3.1 hold. For nonsingular Gram matrix Σ, the minimax lower bound is of the order 52 ((k/m log(d/k))
Sparse RUM
P(Y- = | x1) = (0" (0)) no) -(0" (0*,00) .11)
Remark 3.1. Theorem 3.1 shows that the order of the mini- max lower bound depends on rank(2)), rather than the am- bient dimension
8" E 0g == {0 ERd |101|2 I B, |101|o < k3. (5)
Compared to the non-sparse case which has a lower bound of ((d) (Shah et al., 2016; Zhu et al., 2023), the lower bound in Theorem 3.1 reduces the dimension dependency to S2(k log(d/k)).
Furthermore, throughout the paper, we assume the feature
We make this assumption for simplicity, while in Ouyang al. (2022), @ is also trainable.

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
3.2. Upper Bounds
Assumption 3.2 does not impose full-rank requirement the Gram matrix E. Moreover, if {20,2;21,i) are domly sampled from absolutely continuous probability measure, Assumption 3.2 is satisfied with probability 1. Remark 3.2. Assumption 3.2 is not required if (4) is replaced with the regularized metric
To derive upper bounds on the estimation errors of the esti- mators under consideration, assume that F in the sparse RUM (5) is strongly log-concave in neighborhood of the origin.
Assumption 3.1 (Strong log-concavity). For the function F in the sparse RUM (5), there exists >> 0 such that for any / E -L, BL/a),
10 0 13 B
(14)
where À > is fixed, and is the d x d identity matrix. Adding the regularization term AI Σ ensures that the semi-norm || 11/x: becomes norm -|I=Arr- However, adopting (14) as the metric introduces an additive constant term XB2 to the upper bound, similar to Lemma 3.1 in Zhu et al. (2023). We note that this constant term does not affect the order of the bound, as À can be made arbitrarily small. For simplicity, we adopt (4) as the metric in this paper.
d² dt
log F(t)) 2 27.
(10)
Assumption 3.1 satisfied by the BTL (where F is the sig- moid function) and TM models (where F is the cumulative distribution function of the standard Gaussian distribution). This assumption is common in prior works, such as Shah et al. (2016) and Zhu et al. (2023).
Theorem 3.2 (Minimax optimal rate for the Ey co-cosstr estimator). Consider the sparse RUM (5) with k S d/2. Suppose Assumption 3.1 and 3.2 hold. With probability at least 1, 6,
Define the parameter wa as the supremum of the logarithmic derivative of F over the interval |BL//o, BL/ol.ic.. i.c.
d dt
sup w EE BL/
log F(t).
(11)
0% - 001
24w² k log (2) 1og(1/0)
(15)
72
n
w represents the Lipschitz continuity constant of log F over the given interval. Similar to B, L, Ç, we treat y and as
where is defined in (11).
fixed. Specifically, when B- L = 7,7 0.10, w 0.73
in the BTL model and y 0.18, w 1.52 in the TM model.
The proof of Theorem 3.2 is provided in Appendix E.2. From Theorem 3.1 and 3.2, it follows that the co-conatrd estimator defined in (12) achieves minimax optimality over + B, with respect to and n, and with the full-rank assump- tion on Σ, also with respect to
3.2. 1. G6-CONSRRAINE ESTIMATOR
Now let us consider the fo-constrained maximum likelihood estimator 0% defined as
For sparse preference learning under Assumption 3.1, the sample complexity is of the same order as that of sparse lin- ear regression under sub-Gaussian noise (Vershynin, 2015; Rigollet & Hütter, 2023).
0 arg mig L(0, 11) de0n,
(12)
Finding such minimizers is computationally intractable in general, as it involves searching over all possible i subset out of d-dimensional vector, which takes (+) number of maximum likelihood estimates. Nevertheless, we are inter- ested in its estimation eиror rate as theoretical benchmark.
3.2.2. & REGGULARIZED ESTIMATOR
One widely adopted approach to overcoming the computa- tional intractability of fn-mrrm constrained problems is to relax the f--nom constraint by incorporating weighted E fi-orrm term into the objective function, as seen in meth- ods like LASSO (Tibshirani, 1996). Motivated by this ap- proach, this subsection focuses on evaluating the perfor- mance of estimating the sparse parameter 6² by minimizing the maximum likelihood loss with a regularization term 011011, We refer to this -nomm penalized estimator as the f f-regularried estimator, formally defined as:
To provide an upper bound on the estimation error of the co-constrained estimator, we begin by introducing some notation. For an index set S C [d] == 2, (1,2,...,d} d} and a vector x E IRd, we denote &s E si as the vector of consisting of the elements indexed by S, and [8] the cardinality of S. We then define the principal submatrix of E accordingly, i.e..
Es = Σ (so.s I1A)s(F0, - 21,13 sl (13)
de, E arg min L(O, (5))))) + $|1011 9e@n
(16)
We then make the following assumption. Assumption 3.2 (Nonsingularity of submatrices). For each S such that & S [S| < 2k. rank(Es)) = (S].
Since the E norm is the convex envelope of the fo-norm, the transformed problem becomes convex and can be efficiently
5

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
solved using methods such coordinate descent (Boyd al., 2011; Peng & Vidal, 2023) and proximal gradient algorithms (Tseng, 2008; Beck & Teboulle, 2009; Becker et al., 2011). Notably, this approach does not require the prior knowledge of k.
3.3 hold. With probubility at least 6, the & ry-egularized estimator (16) with
4w
log 2d + log(1/0)
B
(21)
We define H to characterize the boundedness of the columns of the feature matrix X, i.e.,
satisfies
128w2 2² k log 2d + log(1/5)
00. - 0"
max, |X
<
(22)
H
(17)
722
Vn
and
where X, denotes the j-th column of X. We note that the parameter H always exists and satisfies I L, as the feature space bounded (see Equation (6)).
0c. -0-
001
0-
256w2
ls loog 2d + log(1/0)
(23)
72
n
Theorem 3.3 (Slow rate for the & frrreularieed estimator). Consider the sparse RUM (5). Suppose Assumption 3.1 holds. With probability at least 1 8, the Ez-regularized estimator (16) with
The proof of Theorem 3.4 is provided in Appendix E.4.
Theorem 3.4 establishes that computationally tractable es- timator achieves an estimation error rate of O ((k/n) log d) under Assumption 3.3, which is nearly minimax optimal. Remark 3.3. Theorem 3.3 and 3.4 suggest that, achieve the estimation error rate of the corresponding order, the regularization parameter should scale as 3 -0.55 0.5 Yet,
V2WH
log 2d + log(1/5)
B =
(18)
n
satisfies
the optimal choice of / in practice remains unclear. To investigate this, we conduct a hyperparameter search; imple- mentation details are provided in Appendix C.I. As shown in Figure 1, 3 is expected to decrease as the sample size n increases. The red line represents log(5) (5) as linear function of log(n) with slope of -0.5. Notably, this line aligns with the valley of the contour map, validating that our theoretical results offer reasonable guideline for picking 8.
2v2 wH 0c., 0²1
110% log 2d + log(1/6)
(19)
7
where w is defined in (11), and H in (17).
The proof of Theorem 3.3 is provided in Appendix E.3. According (5), we have |10111 I BVk. The estima- tion error rate in Theorem 3.3 is thus O (V(k/n) (og/)))log)) logd) which has gap from the minimax optimal rate θ ((k/n) log(d/k)) in Theorem 3.2. Next, we show that the l-regularized estimator can achieve a nearly minimax opti- mal rate under the following assumption on the spectrum of Σ.
0.6
log( 0.5xlog(n)
0.0
-1.2
2.0
-1.8
Assumption 3.3 (Restricted eigenvalue condition). We as- sume that the Gram matrix Σ satisfies
log(8)
-2.5
-2,4
-3.0
-3.0
-3.6
|0
4.2
inf Sks
inf 8ECs
2
(20)
|001
2
3.5
4,8
4
where Cs = {0 Rd 8 8 05= 111 < 3 1/sl2).
log(m)
Assumption 3.3 implies that the smallest eigenvalue of Es is lower bounded by positive constant for all S of cardi- mality no more than k. A stronger version of the assump- tion requires Σ satisfies the incoherence condition, namely, | 15-17 - -Tllumxx < 1/(32k), where || mmmx denotes the largest absolute value among the elements a matrix (Bickel et al., 2009; Wainwright, 2019).
Figure 1. Contour of the estimation error of ||0e, 8 with
respect to 3 and n in the log space for d = 100, = 0.1. The
logarithm uses base
4. Experimental Results
To demonstrate the sample efficiency of the proposed e regularized estimator, we conduct experiments on synthetic data (Section 4.1) as well on the task of LLM alignment
Theorem 3.4 (Fast rate for the L regeullarieed estimator).
Consider the sparse RUM (5). Suppose Assumption 3. and
6

---

Leveraging Sparsity for Sample-Effiieet Preference Learning: A Theoretical Perspective
(Section 4.2) in two settings: frozen backbone training and full fine-tuning. We defer additional results and discussion to Appendix D. The code can be found at this link..
Data. We train reward models using the rm-stat i dataset (Bai et al., 2022y and SHP dataset (Ethayarajh et al., 2022)². em-statie c is curated dataset specifically de- signed for training reward models. The dataset consists of 76.3K samples, each comprising a prompt and a pair of responses, where one response is marked as chosen and the other as rejected, based on annotations provided by human evaluators. An example is shown in Appendix C.2.
4.1. Numerical Evaluation on Synthetic Data
Experimental setting. The ground-truth parameter 8* is sampled from the set {0 E g=-1; ||0||2 = 1, |10||o = k). Specifically, k out of d coordinates are selected uniformly at random. The value at each selected coordinate is i.i.d. drawn from the standard Gaussian distribution. Finally, the resulting vector is normalized to have a unit Euclidean norm. Each Tu,s and T1, in {(To,,, 21,1) are inddpen- dently sampled from the uniform distribution [10, )) The observed preference signal y/ with respect to z0,4 and Fi is generated according to the random utility model, as shown in (I), where F(t) = -+) is the sigmoid func- tion. Specifically, y/1 is a Bernoulli random variable with parameter p derived from the random utility model. Both the maximum likelihood estimator and the l f1-regularized es- timator are implemented using the SciPy package (Virtanen et al., 2020) with the SLSOP optimization method (Kraft, 1988). To ensure convergence, we set the maximum number of iterations to 1000.
Models and Methods. We employ the pretrained lan- guage models Pythia-70000 OM (Biderman et al., 2023) and Llama-3 1amm--3.2 2-1B (Dubey et al., 2024) as the foundation for reward modeling. To adapt such model, the final layer is replaced with a scalar head to produce reward values for in- put responses. For the 4 erreullarieed method, we add 3||0[11 to the original loss function, where represents the param- eter of the final layer. As a baseline for comparison, we set = 0, namely removing the regularization term. The code is based on Deepspeed Chat (Yao et al., 2023), Detailed parameter settings can be found in Appendix C.3.
Results for full fine-tuning, To mitigate the influence of randomness from different random seeds, we fit a quadratic model to capture the relationship between accuracy and the f-normm regularization parameter /3, as shown in Figure 3. The results indicate that applying é regularization to the last layer leads to a 0.9% improvement in accuracy for both models examined. Furthermore, the f--regularized models (gray curve) consistently outperforms the baseline models (dashed line) across a wide range of 3 values. The empirical results validate the effectiveness of the proposed sparse-aware reward modeling approach, demonstrating its potential value in RLHF
Results. Figure 2 compares the fi-regularized estimator and the maximum likelihood estimator under varying spar- sity ratios (k/d) and sample sizes (n). The estimation error is evaluated using the semi-norm I|s, defined in (4). In Figure 2a, as the ground-truth parameter 0* is increas- ingly sparse (the ratio k/d decreases), the 4 l--reullarized estimator demonstrates superior performance compared to the maximum likelihood estimator, which is agnostic to sparsity level. Similarly, in Figure 2b, the f--regularized estimator consistently exhibits greater sample efficiency, particularly when the sample size n is small. Note that the penalization parameter / is selected based on the theoretical results presented in Section 3.2.2 and the outcomes of our hyperparameter search described in Appendix C.I.
Frozen backbone training In frozen backbone training, only the last layer is trained, while all other parameters (the backbone) remain frozen-al method often referred to as lin- ear probing or feature-based fine-tuning. Since LLMs have billions of parameters, full fine-tuning can be extremely ex- pensive. By updating only the last layer, memory usage and computation time are drastically reduced. This approach is widely used when computational resources are constrained, data is scarce, or bascline before full fine-tuning.
4.2. Empirical Evaluation
We present proof-of-concept results on real-world datasets to assess the performance of the sparsity-aware methods in reward learning, which is a critical component of RI.HF. The performance of a reward model is evaluated based on prediction accuracy on the test dataset. A prediction is considered correct for a given prompt-response pair if the reward model assigns higher reward to the chosen response than to the rejected response.
Results for frozen backbone training Figure 4 compares the test accuracy of l f1-regularized reward modeling (or- ange curve) and the baseline (blue curve). The underlying model is Llama-3. 2-1B, where the dimensionality of the second-last layer output is = 2048, and the dataset is rm-static. Our results show that leveraging spar-
httpp://haggingaaee.///aaassss rm-static stanfordn1p/SHP
hhtpps: / http//ttttttttt//// www.///o///ooeeee cww.:/oy.//////y///// /aoyzh/ Sparse
7

---

Leveraging Sparsity for Sample-Efficien Preference Learning: A Theoretical Perspective
10
0.08
0ML
00- 0"
0.06
0
|6 0r
|
0ML
10
0.04
0.02
0.0
0.2
0.4
0.6
0.8
1.0
10
10a
k/d
a
(a) 100,
0.1, 8
0.1
(b) = 5, a = 0.1, g
1
Figure 2. Estimation error of 0r and An... Results are based on 20 repetitions of experiments conducted with dimension d 100.
64
69.0
quadratic fit f = 2. acc.61.4% O, 60.%%
quadratic fit
68.5
B 6.3e-04, acc:67.7%
B acc:66.8%
Accuracy
Accuracy
68.0
67.5
61
60
66.5
10-4
10-3
10-2
10-1
10
101
10
B
B
(a) Pythia-70M
(b) Llama-3.2-1B
Figure 3. Full fine-tuning: accuracy versus & regularization parameter 3. Each gray dot represents the accuracy for specific value of 3 from single trial. The gray curve each sub-figure illustrates average accuracy over five trials (five gray dots) each specific 3. The red curve represents the quadratic fit across all trials (all gray dots), with the maximum accuracy of the fit curve highlighted. The black dashed line indicates the average accuracy obtained without any regularization. The dataset is rm-statie
64
6=
62
62
erregularized
60
Acouracy
Accuracy
58
56
P=
d rrrguulariedd
54
200
400
800
1600
3200
6400
200
400
800
1600
3200
6400
(log scale)
(log scale)
(a) rm-static
(b) SHP
Figure Frozen backbone training: test accuracy vs. n. The backbone model is amaama-., 2-18, which the dimensionality of the second-las layer output is d 2048, We set / = 0.5 n- -0.5 for the & rerreuulaiization Each setting evaluated over trials.
sity can improve accuracy by least 3%. Notably, we do not manually tune the hyperparameter 8; instead, 0.5 for the L f--regularized method. In
both datasets, the r-regularized method (orange curve) consistently outperforms the baseline (B blue curve) across all values of n. Furthermore, observe that for
set 3 0.5
8

---

Leveraging Sparsity for Sample-Effiieet Preference Learning: A Theoretical Perspective
the rm-static dataset, the learned parameters has spar-
typically involves two main steps: first, training a reward model based user feedback capture human intentions, and second, training policy using reinforcement learning to optimize the learned reward model. Various enhancements to RLHF have been proposed to improve its efficiency and effectiveness, including accelerated training methods (He et al., 2024) and self-play techniques (Wu et al., 2024). No- tably, Direct Preference Optimization (DPO), a reward-frre approach, has been demonstrated to yield the same solu- tions as reward-based RLHF (Rafailov et al., 2024; Xu et al., 2024; Shi et al., 2024), incorporating methods such as re- ject sampling (Liu et al., 2024). Iterative DPO approaches, as explored by Xiong et al. (2024) and Yuan et al. (2024), leverage the LLM itself as the reward model to provide preference signals, a strategy referred to as self-rewarding, Moreover, Zhu et al. (2023) introduces a pessimistic max- imum likelihood estimation (MLE) approach for training policies. The theoretical foundations of these methods of- ten draw from dueling bandit frameworks (Lu et al., 2010; Yue et al., 2012; Saha, 2021: Bengs et al., 2021), with on- line RLHF approaches initially developed for finite and small state spaces (Xu et al., 2020; Novoseller et al., 2020; Pacchiano et al., 2021) and subsequently generalized to approximate complex functions (Chen et al., 2022b).
sity ratio k/d 4.5% if 800 and k/d x 7.5% if = 3200; for the SHP dataset: k/d x 4.2% if n = 800 and k/d ~ 7.2% if n = 3200. These results show that 4 regularization selects a small and informative subset of features, and sparsity regularization is beneficial for reward modeling, leading to higher test accuracy.
5. Related Works
Expected utility, originating from mathematical economics, posits that rational agents maximize their utility under uncer- tainty (Ramsey, 1926; Von Neumann & Morgenstern, 1947). Debreu et al. (1954) established the preference representa- tion theorem, which asserts that any complete, transitive, and continuous preference relation can be represented by continuous ordinal utility function. This deterministic model is extended to the Random Utility Model (RUM) (McFadden, 1974; 1978; Rosenfeld et al., 2020; Azar et al., 2024; Samuelson, 2024; Sun et al., 2024), incorporating ele- ments such as Gaussian noise (Thurstone, 1994), Gumbel noise (Luce, 1959), and others (Tesauro, 1988; Crammer & Singer, 2003; Chajewska et al., 2001). Furthermore, the RUM can be extended to incorporate multiple utility func- tions (Moulin, 1985; Eliaz& & Ok, 2006; Benson et al., 2018;
Sparse linear models have become cornerstone of high- dimensional statistics, leveraging the assumption that only a few predictors significantly influence the response. It has been shown that ε -bsed methods, such as LASSO (Tibshi- rani, 1996) and the Dantzig Selector (Candes & Tao, 2007), can achieve ((k//n) log(d)) (Candes & Tao, 2006; Bickel et al., 2009) under incoherence conditions, which is close to the minimax rate (((k/n) log(d/k) (Ye & Zhang, 2010; Rigollet & Tsybakov, 2011; Raskutti et al., 2011; Verzelen, 2012; Candes & Davenport, 2013; Reeves & Gastpar, 2013). Later, Bellec et al. (2018) has shown that the minimax rate is achievable by polynomial time methods. Due the vast literature on sparsity, we refer readers Hastic al. (2015) and Wright & Ma (2022) for comprehensive discussions.
Pfannschmidt & Hüllermeier, 2020; Benavoli et al., 2023), non-linear utility models based on Gaussian processes (Be- navoli& & Azzimonti, 2024), and context-dependent models (Seshadri et al., 2019; Bower& & Balzano, 2020; Tomlinson & Benson, 2021: 2024).
Apart from based methods, preference learning can be achieved through preference ranking (Haddawy et al., 2003; Fürnkranz& & Hüllermeier, 2003; Brazdil et al., 2003; Negahban et al., 2012; Wauthier et al., 2013; Hajek et al., 2014; Rajkumar& & Agarwal, 2014; Park et al., 2015; Shah et al., 2016; Seshadri et al., 2020; Chen et al., 2022a) with- out explicitly modeling utility functions, or by framing it as a classification problem in machine learning contexts (Fürnkranz& & Hüllermeier, 2011; Van Cranenburgh et al., 2022). Other closely related fields include ranking learning and ordinal regression, which involve predicting ordered classes for each sample (Frank& & Hall, 2001; Kramer et al., 2001; Chu & Keerthi, 2005).
6. Conclusion and Future Work
In this paper, we address the challenge of sample-efficient preference learning in high-dimensional settings. Lever- aging the sparse random utility model, we establish the minimax optimal rate and propose efficient é--regularized estimators to reduce the sample complexity. Experimental results on synthetic data and LLM alignment datasets vali- date these theoretical insights, demonstrating that sparsity- aware methods not only reduce sample complexity but also enhance prediction accuracy. For future work, we aim to investigate the optimality of RLHF policies induced by such sparse reward models and further extend the sparsity- induced sample-efficient estimation framework to DPO.
Powerful large language models (LLMs) trained through next-token prediction can generate unhelpful and unsafe content that is misaligned with human instructions (Leike et al., 2018). To address this, a popular approach is to align pretrained models with human instructions through Rein- forcement Learning from Human Feedback (RLHF) (Ziegler et al., 2019; Ouyang et al., 2022; Wu et al., 2024). Based on whether an explicit reward function is employed, RLHF methods primarily fall into two categories: reward-based ap- proaches and reward-free approaches. Reward- based RLHF
9

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Acknowledgements
Benson, A. R., Kumar, R., and Tomkins, A. A discrete choice model for subset selection. ACM International Conference on Web Search and Data Mining, 2018.
This work was supported in part by the Swiss National
Science Foundation under Grant 200364.
Bergstra, J., Yamins, D., and Cox, D. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. International Con- ference on Machine Learning, 2013.
Impact Statement
This paper aims to advance the fields of Preference Learn- ing and LLM Alignment through both theoretical analysis and empirical evaluation of preference learning (reward modeling). The theoretical findings provide insights into the sample complexity of this problem, while the proposed methods demonstrate improved estimation of human ethics and preferences. These advancements enhance the helpful- ness and controllability of LLMs, ultimately contributing to societal welfare.
Bickel, P. J., Ritov, Y., and Tsybakov, A. B. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, 37(4):1705-1732, 2009.
Biderman, S., Schoelkopf, H., Anthony, Q. G., Bradley, H., O'Brien, K., Hallahan, E., Khan, M. A., Purohit, S., Prashanth, U. S., Raff, E., et al. Pythia: A suite for analyzing large language models across training and scaling. International Conference on Machine Learning, 2023.
References
Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandriello, D. A general theoretical paradigm to understand learning from human preferences. International Conference on Artificial Intelligence and Statistics, 2024.
Bower, A. and Balzano, L. Preference modeling with context-dependent salient features. In International Con- ference on Machine Learning. pp. 1067-1077. PMLR. 2020.
Boyd, S., Parikh, N., Chu, E.,, Peleato, B., Eckstein, J., et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training helpful and harmless assistant with rein- forcement learning from human feedback. arXiv preprint arXiv:2204.00 05860,8862222 2022.
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-33) 345, 1952.
Beck, A. and Teboulle, M. A fast iterative shrinkage- thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202 2009.
Brazdil, P. B., Soares, C., and Da Costa, J. P. Ranking learn- ing algorithms: Using ibl and meta-learning accuracy and time results. Machine Learning, 50:251 50:251-2771 1-77, 2003.
Becker, S., Bobin, J., and Candès, Nesta: fast and accurate first-order method for sparse recovery. SIAM Journal on Imaging Sciences, 4(1):1-39,201
Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., and Hullender, G. Learning to rank using gradient descent. In Proceedings the 22nd international conference on Machine learning, pp. 89-96, 2005.
Bellec, P. C., Lecué, G., and Tsybakov, A. B. Slope meets lasso: improved oracle bounds and optimality. The Annals of Statistics, 46666):360-3642) 2018.
Candes, E. and Davenport, M. A. How well can we estimate a sparse vector? Applied and Computational Harmonic Analysis, 34(2):317-323, 2013.
Benavoli, A. and Azzimonti, D. A tutorial on learning from preferences and choices with gaussian processes. arXiv preprint 2rXiv:2403. 11782, 2024.
Candes, E. and Tao, T. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory. 52(12):5406-5425 2006.
Benavoli, A., Azzimonti, D., and Piga, Learning choice functions with gaussian processes. Uncertainty in Artifi- cial Intelligence, 2023.
Candes, E. and Tao, T. The dantzig selector: Statistical estimation when p is much larger than n. The Annals of Statistics, pp. 2313-2351, 2007.
Bengs, V., Busa-Fekete. R.. El Mesaoudi-Paul, A., and Hüllermeier, E. Preference-based online learning with ducling bandits: A survey. Journal of Machine Learning Research, 22(7):1-108, 2021.
Chajewska, U., Koller, D., and Ormoneit, D. Learning an agent's utility function by observing behavior. Interna- tional Conference on Machine Learning, 2001.
10

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Chen, P., Gao, C., and Zhang, A. Y. Optimal full ranking from pairwise comparisons. The Annals of Statisties, 50 (3):1775-1805, 2022a.
Fürkkranz, and Hüllermeier, B. Preference Learning. Springer Berlin, Heidelherg, 2011.
Gao, L., Schulman, J., and Hilton, J. Scaling laws for reward model overoptimization. International Conference on Machine Learning, 2023.
Chen, X., Zhong, H., Yang, Z., Wang. Z., and Wang, L. Human-in -ooth-loop Provably efficient preference-basee reinforcement learning with general function approxima- tion. International Conference on Machine Learning, 2022b.
Haddawy, P., Ha, V., Restificar, A., Geisler, B., and Miyamoto, J. Preference elicitation via theory refine- ment. The Journal of Machine Learning Research, 4: 317-337, 2003.
Christiano, P. F., Leike, J., Brown, T., Martic, M.. Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems, 2017.
Hajek, B., Oh, S., and Xu, Minimax canimax-optimal inference from partial rankings. Advances in Neural Information Processing Systems, 2014.
Chu. W. and Keerthi, S. S. New approaches to support vector ordinal regression. International Conference on Machine Learning, 2005.
Hastie, T., Tibshirani, R., and Wainwright, M. Statistical learning with sparsity. Monographs on statistics and applied probability, 143(143):8, 2015.
Crammer, K. and Singer, A family of additive online algorithms for category ranking. Journal of Machine Learning Research, ((Feb):10255110) 2003.
He, J., Yuan, H., and Gu, Q. Accelerated preference op- timization for large language model alignment. arXiv preprint arXiv:2410.0000
2024.
Debreu, G. et al. Representation of preference ordering by numerical function. Decision processes, 3:159-165, 1954.
He, X., Liao, L., Zhang, H., Nie, L., Hu, X., and Chua, T.-S. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pp- 173-182, 2017.
Donoho, D. L. Compressed sensing. IEEE Transactions information theory, 52(4)) 2006.
Hsu, D., Kakade, S. M., and Zhang, T. A tail inequality for quadratic forms of subgaussian random vectors. Elec- tronic Communications P Probability, 17, 2012.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et The llama herd of models. arXiv preprint arXiv:2407.21788, 2024.
Joachims, T. Optimizing search engines using clickthrough data. In Proceedings of the eighth ACM SIGKDD inter- national conference on Knowledge discovery and data mining, pp. 133-142, 2002.
Duchi, J. Information theory and statisties. Lecture Notes, 2024.
Kraft, D. A software package for sequential quadratic pro- gramming. Forschungsberichn--DDF..M 88-28, 1988.
Eliaz, K. and Ok, E. A. Indifference indecisiveness? choice-theoretic foundations of incomplete preferences. Games and economic behavior, 56(1) 1666- 2006.
Kramer, S., Widmer, G., Pfahringer, B., and De Groeve, M. Prediction of ordinal classes using regression trees. Fundamenta Informaticae, 47(1-2): 2001.
Ethayarajh, K., Choi, Y., and Swayamdipta, S. Under- standing dataset difficulty with-usable information. International Conference Machine Learning, 2022.
Leike, J., Krueger, D., Everitt, T., Martic, M., Maini, V., and Legg, S. Scalable agent alignment via reward modeling: a research direction. arXiv preprint arXiv: 10ee:81117700 1.07871, 2018.
Faury, L., Abeille, M.. Calauzènes, C., and Fercoq. O. Im- proved optimistic algorithms for logistic bandits. In In- ternational Conference Machine Learning, 2020.
Liu, T., Zhao, Y., Joshi, R., Khalman, M., Saleh, M., Liu, P. J., and Liu, Statistical rejection sampling improves preference optimization. International Conference Learning Representations, 2024.
Frank, E. and Hall, M. A simple approach to ordinal clas- sification. European Conference on Machine Learning, 2001.
Fürmkranz, J. and Hüllermeier, E. Pairwise preference learn- ing and ranking. European Conference on Machine Learn- ing, 2003.
Liu, T. Y. et al. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3): 225-331, 2009.

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Lu, T., Pál, D., and Pál, M. Contextual multi-armed bandits. In International Conference Artificial Intelligence and Statistics, pp. 485-492, 2010.
Pfannschmidt, K. and Hüllermeier, E. Learning choice functions via pareto-embeddings. German Conference on AI, Bamberg, Germany, pp. 327-333, 2020.
Luce, R. D. Individual choice behavior, volume 4. Wiley New York, 1959.
Rafailov, R.,. Sharma, A., Mitchell, E., Manning, D., Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances in Neural Information Processing Systems, 2024.
Mahan, D., Van Phung, D., Rafailov, R., Blagden, C.,, Lile, N., Castricato, L., Fränken, J.-P., Finn, C., and Albalak, A. Generative reward models. arXiv preprint 17X1::2410.12832. 2024.
Rajkumar, A. and Agarwal, A statistical convergence per- spective of algorithms for rank aggregation from pairwise data. International Conference on Machine Learning, 2014.
McFadden, D. The measurement of urban travel demand. Journal of public economics, 3(4):303-33) 328, 1974.
Ramsey, F. Truth and probability. The Foundations of Mathematics and other Logical Essays, 1926.
McFadden, D. Modeling the choice of residential location. Spatial Interaction Theory and Planning Models, 1978.
Raskutti, G., Wainwright, M. J., and Yu, B. Minimax rates of estimation for high-dimenniioall linear regression over lq- balls. IEEE transactions information theory, 57 (10):6976-6994, 2011.
Mosteller, F. Remarks on the method of paired compar- isons: I. the least squares solution assuming equal stan- dard deviations and equal correlations. Selected Papers of Frederick Mosteller, pp. 157-162, 2006.
Reeves, G. and Gastpar, M. C. Approximate sparsity pattern recovery: fformation-theoretie lower bounds. IEEE Transactions Information Theory, 59(6):3451-3465 2013. doi: 10.1109/TT.200122255555.
Moulin, H. Choice functions over a finite set: a summary. Social Choice and Welfare, 2(2):147-166) 1985.
Negahban, S., Oh, S., and Shah, D. Iterative ranking from pair-wise comparisons. Advances in neural information processing systems, 25, 2012.
Rendle, S., Freudenthaler, C., Gantner, Z., and Schmidt- Thieme, L. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pp- 452-461, 2009.
Negahban, S., Oh, S., and Shah, D. Rank centrality: Rank- ing from pairwise comparisons. Operations Research, 65 1177266-287, 2017.
munications of the ACM, 40(3):56-58, 1997. Resnick, P. and Varian, H. R. Recommender systems. Com-
Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, Du- eling posterior sampling for preference- preeeeence-based reinforce- ment learning. Conference on Uncertainty in Artificial Intelligence, 2020.
Rigollet, P. and Hütter, J.-C. High-dimensional statistics. arXiv preprint arXiv:2310. 19244, 2023.
Rigollet, P. and Tsybakov, A. Exponential screening and op- timal rates of sparse estimation. The Annals of Statistics, pp. 731-771, 2011.
Ouyang. L., Wu, J.. Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 2022.
Rosenfeld, N., Oshiba, K., and Singer, Y. Predicting choice with set-dependent aggregation. International Con- ference on Machine Learning. pp. 8220-8222 PMLR, 2020.
Pacchiano, A., Saha, A., and Lee, J. Dueling rl: reinforce- ment learning with trajectory preferences. arXiv preprint DrXiv:2//1.04882 2021.
Saha, A. Optimal algorithms for stochastic contextual prefer- ence bandits. Advances Neural Information Processing Systems, 2021.
Park, D., Neeman, J., Zhang, J., Sanghavi, S., and Dhillon, I. Preference completion: Large-scale collaborative ranking from pairwise comparisons. International Conference on Machine Learning, 2015.
Saha, A., Pacchiano, A., and Lec, J. Dueling rl: Reinforce- ment learning with trajectory preferences. International Conference on Artificial Intelligence and Statistics, 2023.
Peng, L. and Vidal, R. Block coordinate descent on smooth manifolds: Convergence theory and twenty-one examples. arXiv preprint arXiv:2305 14744, 2023.
Samuelson, P. A. A note on the pure theory of consumer's behaviour, In The Foundations of Price Theory Vol 4, pp. 101-116. Routledge, 2024.
12

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Seshadri, A., Peysakhovich, A., and Ugander, J. Discovering context effects from raw choice data. In International conference machine learning, pp. 5660-5669. PMLR, 2019.
Van Cranenburgh, S., Wang, S., Vij, A., Pereira, E, and Walker, J. Choice modelling in the age of machine learning-discussinn paper. Journal of choice modelling, 2022.
Seshadri, A., Ragain, S., and Ugander, J. Learning rich rankings. Advances Neural Information Processing Systems, 33:9435-94444 9446, 2020.
Vershynin, R. Estimation in high dimensions: geomet- ric perspective. In Sampling Theory, Renaissance: Compressive Sensing and Other Developments, pp. 3- 66. Springer, 2015.
Shah, N. B., Balakrishnan, S., Bradley, J., Parekh, A., Ramch, K., Wainwright, M. J., et al. Estimation from pairwise comparisons: Sharp minimax bounds with topol- ogy dependence. Journal of Machine Learning Research, 17(58):1-47, 2016.
Verzelen, N. Minimax risks for sparse regressions: Ultra- high dimensional phenomenons. Electronic Journal of Statisties, 6:38-90, 2012.
Virtanen, P., Gommers, R., Oliphant, T. E.,, Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M.. Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, I., Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A., Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F., van Mulbregt, P., and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
Shi, R., Zhou, R., and Du, S. The crucial role of samplers in online direct preference optimization. In NeurlPS 2024 Workshop on Mathematics of Modern Machine Learning, 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.
Sun, H., Shen, Y., and Ton, J.F. Rethinking bradley- terry models in preference-based reward modeling: Foundations, theory, and alternatives. arXiv preprint arXiv:2411.0490 2024.
Von Neumann, J. and Morgenstem, O. Theory of games and economic behavior. In Theory of games and economic behavior. Princeton university press, 1947.
Tesauro, G. Connectionist learning of expert preferences by comparison training. Advances in Neural Information Processing Systems, 1988.
Wainwright, M. High-Dimensional Statistics: A Non- Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019.
Thurstone, L. L. A law of comparative judgment. Psycho- logical review, (2):266, 1994.
Wang. Y., Zhong, W., Li, L., Mi, F., Zeng, X., Huang, W., Shang, L., Jiang, X., and Liu, Q. Aligning large language models with human: survey. arXiv preprint arXiv:2307. 12966, 2023.
Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology. 58(1):267-288 1996.
Wauthier, F., Jordan, M., and Jojic, N. Efficient ranking from pairwise comparisons. International Conference on Machine Learning, 2013.
Tomlinson, K. and Benson, A. R. Learning interpretable feature context effects in discrete choice. In Proceed- ings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp. 1582-1592, 2021.
Wright, and Ma. Y. High-ddieesional data analysis with low-dimensional models: Principles, computation, and applications. Cambridge University Press, 2022.
Tomlinson, K. and Benson, A. R. Graph-based methods for discrete choice. Network Science, 12(1):21-40, 2024.
Wu, Y., Sun, 7.,, Yuan, H., Ji, K., Yang. Y., and Gu, Q. Self-play preference optimization for language model aligmment. arXiv preprint arXiv:2405.0067. 2024.
Tropp, A. and Gilbert, A. C. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on information theory, 53(12):465544666 2007.
Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. International Conference on Machine Learning, 2024.
Tseng, On accelerated proximal gradient methods for convex- concave optimization. submitted to SIAM Journal on Optimization, 2(3), 2008.
13

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Xu, S., Fu, W., Gao, J., Ye, W., Liu, W. Mei, Z., Wang, G., Yu, C., and Wu, Y. Is dpo superior ppo for Ilm align- ment? comprehensive study. International Conference on Machine Learning, 2024.
Xu, Y., Wang, R., Yang. L., Singh, A., and Dubrawski, A. Preference-basee reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 2020.
Yao, Z., Aminabadi, R. Y., Ruwase, O., Rajbhandari, S., Wu, X., Awan, A. A., Rasley, J., Zhang, M., Li. C., Holmes, Easy, fast and affordable rlhf training of chatgpt-like models at all scales. arXiv preprint arXiv:2308. 2...20338...222 01320, 2023.
C.. et al. Deepspeed-chits
Ye, F. and Zhang, C.
H. Rate minimaxity of the lasso and dantzig selector for the lq loss in Ir balls. Journal of Machine Learning Research, 11:3519-3544 2010.
Yuan, W. Pang, R. Y., Cho, K., Sukhbaatar, S., Xu, J., and Weston, Self-rewarding language models. arXiv preprint ar arXiv:2401.10020 2024.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5): 153--1556, 2012.
Zhu, B., Jordan, M., and Jiao, J. Principled reinforce- ment learning with human feedback from pairwise or k-wise comparisons. International Conference Ma- chine Learning. 2023.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D.. Christiano, P., and Irving, G. Sine-tuning language models from human preferences. arXiv preprint arXiv; 05ti::1900005555 2019.
14

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
A. Structure of the Appendix
The appendix is structured as follows:
Appendix B lists all notations used in the main text.
Appendix provides detailed experimental settings.
Appendix D presents additional experimental results for reward modeling with real data in full fine-tuning.
Appendix E contains proofs for all theorems.
B. List of Notations
The list of notations applies exclusively to the main text and does not include those used in the proofs in the appendix.
Symbol
Description
A
Set of alternatives, action space, response space.
ag: 01, C0,i 01,5 E A
Element in A.
6:A-1 + Rd
Feature map from A to Rd
D c Rd
Feature space, ((A) or A).
Tu, 11, To,1, 01,
Element in D, Fb,; == ((ag.)).
y. 10
Preference signal indicating the preferred feature vector.
&: = (5o.s, 21,i,
Data sample.
r²: D + I
Ground-truth reward function.
0" E IR
Ground-truth parameter of the reward function r".
k
Number of non-zero elements of 0", i.e., ||0* |lo-
d
Ambient dimension of the feature space D.
n
Number of samples.
Py((X.x1)
Conditional distribution y E (0,1) 1} given (1),2)).
o R4
Randomness level of y or temperature parameter.
F:R - [0.1]
Function of the random utility model, and F(t) 1-
(1)
Euclidean inner product.
C(0; (E))e.); L())
Negative log-likelihood function with respect to dataset (& 1
Parameter space.
15

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Symbol
Description
B
Radius of the parameter space, or norm constraint bound.
ML
Maximum likelihood estimator in parameter space e
0, f
Estimate of d"
Estimated reward function associated with é.
X
Matrix with the i-th row being (No,, 211i)).
E
Gram matrix, or data covariance matrix, Σ 1 X.
Semi-norm induced by positive semi-definite matrix E, i.e, || = V Ex.
s
Prompt space, or state space.
8: E
Prompt.
6(;-): S x A + RRd
Feature mapping, or feature embedding of a given prompt-response pair (5, a).
θB
Parameter space with radius B.
θ B.K
B == {0 Rd |101|, S B, 1101lo $ k)..
L
Diameter of the feature space D
See definition (7).
(ra)
Smallest non-zero eigenvalue Σ.
7
See definition (3.1).
See definition (11).
%
Maximum likelihood estimator in parameter space θ B,
[d]
[d] (I.....d).
S C [d]
Index set.
So c [d]
The set complement of S.
Cardinality of set S.
ns R(S)
Vector of elements in indexed by S.
Es
Principal submatrix of E with respect to S; see definition (13).
I, Ia dddd
Identity matrix.
-erggularized estimator parameter space O Bi see definition (16).
16

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Symbol
Description
||
The largest absolute value among the elements of matrix.
H
See definition (17).
C. Experimental Details
C.1. Hyperparameter Search
We use hyperopt package (Bergstra et al., 2013) to conduct hyperparameterr search for 3 with n varying from 10 to 10 Figure 1 is a contour of estimation errors |10g, 0 [| over a series of experiments with different choices of n, 3, and random seeds, extrapolated through cubic polynomials. The red line in the figure represents log(33 as linear function of log(n) with slope -05, Our results show that given by the theoretical results 3 n 0.5 in Theorem 3,3 and 3.4 does lead to the valley the contour surface. All experiments are repeated for 20 times.
C.2. Illustrative Examples for Datasets
An illustrative example for data sample in rm-static
Prompt:
Human: Can you describe the steps clean fingerprints and smudges from laptop screen Assistant: Yes, certainly. To clean your screen, you first need to use microfiber cloth or soft, damp cloth to gently wipe down the surface of the screen. Next, you'll II want to grab soft, lint-free, microfiber cleaning cloth and gently rub it back and forth across the screen to remove fingerprints and smudges. Human: Can I spray isopropyl alcohol onto the cloth and clean it that way? Assistant:
Chosen response:
Yes, you can do that to help the cloth pick up even more dirt from the screen. Be always use clean, soft cloth, not a piece of scratchy, roughened, textured material, and make sure it's lint-free.
Rejected response:
Yes, you can spray it directly onto the cloth.
In addition to rm am-statin ic mentioned in Section 4.2, we also the dataset SHP (Ethayarajh et al., 2022) As noted by the authors of Ethayarajh et al. (2022):
Most notably, all the data in SHP is naturally occurring and wiitten whereas the responses in rm-static are machine-written, giving us two very different distributions that can complement each other.
C.3. Parameter Setting for Real-Data Experiments
The learning rate is set 10-5, and the weight decay is to 0.1. The batch size is 8 for Pythia-70M, 16 for Llama- 2-1B and 32 for Llama -3 2B, and the training runs for 1 epoch. The regularization hyperparameter 3 for the & érregularieed method is selected from the range 101-4.5:0.5:0) U {2, 4, 8}. Each 3 value, including & = 0, is evaluated across 5 trials with random seeds in (0, 1, 2, 43 for Pythia-70M and L 1lama-3 -ama-3.. 3. 2,1B, and 3 trials with random seeds in {0, 1,2] for Llama-3.2-32.
D. Additional Experimental Results for Reward Modeling
D.1. Full Fine-Tuning
This section presents additional results for full fine-tuning, where all backbone model parameters fine-tuned, consistent with Section 4.2.
17

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
We conduct experiments using three base models: Pythia-
3. 3-21B, and Llama -3 2-3B. The results summarized in Table 3 for rm-static and in Table 4 for SHP. Each reported value represents the average five trials for Pythia-700 70M and Llama- 3-2-1B, and three trials for Llama 3 2B. For the & fi-regularized estimator, the displayed value corresponds to the regularization parameter that achieved the highest average accuracy. From the tables, we observe that: 1) larger models consistently produce more accurate predictions, which is expected, and 2) the E--regularized models consistently outperforms baseline models, demonstrating its sample efficiency.
Table Test accuracy on rm-statii
Model
Baseline (%)
f ---egularizee (%)
Pythia-700
60.5
61.8
4lama-3.2 2BBB
66.8
67.7
Llama - 2B
68.4
69.4
Table 4. Test accuracy on SHP
Model
Baseline (%)
{ R--uuularized (%)
Pythia-70M
60.8
62.1
Alama-3.2-12
64.4
65.5
Llama-3.2-2
66.5
67.3
E. Proofs
E.1. Proof of Theorem 3.1
Before proceeding, we first prepare some ingredients.
Lemma E.1 (Sparse Varshamov-Gilke Lemma 4.14 in Rigollet & Hütter (2023)). For any two integers i and d such that
1 < k < d/8 and Hamming distance Ham(-s)), )), there exist binary vectors Wi,... WMr E {0,, 1]a such that
1. Ham(wi, wy) 2 t for all +j: j:
2. log(M)) 2 log (1 )::
3. ||wyllo = for all j E [M].
Lemma E.2 (Upper bound for pairwise KL divergence). For any pair of 01, 02 Og (0 Rd: |101| S B), we have
Nc
DRL (Po, (fE.)))) Pe, (15.)
||0 -2213
where Poş ((5)) 1TL (0, (1-8.) (1 F /(0220-011L)) 8: is the joint distribution of Y Vi...., Y
given (Z0, I1,1) 11, } with parameter 0y.
See Appendix E.5 for the proof of Lemma F.2.
18

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
Lemma E.3 (Pairwise Fano minimax lower bound, The local Fano method in Duchi (2024)). We call subset of vectors
{01, 0x) } O (v, pacckin of ④ in a pseudo-metric p
min p (0, - 02) 2 v, and
Σ
DEL (P(O.) || P(0,)) S n
(JEMM 1
(2)
LF$
If we can construct a (v, n) packing with cardinality M, then the minimax risk in the square of the pseudo-metric p is lower bounded as
(0 ( )
2 u² (1 (1- 1) log 2
inf sup E are0
(24)
2 log M
With the above three lemmas at hand, we can now cook up the lower bound in Theorem 3.1 as follows. We first apply Lemma E.1 by replacing in Lemma E.1 with rank(E.) obtain subset of binary vectors (U1,..., uns E (0, 1) ]rank(2) as such. Then for each j [M,, append (d- (d-rank(2)) zeros to the bottom of by and get d-dimensional binary vector w i.c.
W = [o 0 0] 10,
(25)
Since Σ is symmetric and positive semi-definite it has an orthogonal diagonalization U AU, where U E Rdddd is orthogonal matrix, and A is diagonal matrix with non-negative elements in descending order. Let diagonal matrix At denote the Moore-Pennoos pseudo-inverse of A. Let 0 .... AM be such that for each [M]
log
+
rank(2) 2k
0j
U
Af wj
SVC
Then,
log 1 +
rank(_] 2k
|001122
8VC V
o
U Af wj
log 1 +
rank(_] 2k
At Wy
8/{
A log
+1+ r2nk(>2)) 2k
σ S
max diag( V A1)
B
The last inequality holds as we assume
0²
14 rank(E)
o² max (diag(A))) k: log (1 rank (Σ)
n 64 (P
k log
2k
64B²C
2k
Furthermore, we have
10: - 0; = (0: - -0;)
TTO, -
0,)
o² log + rank(2) 21
(we - (w;;-w;) (T VATUU TAUT VAt(w; -
64ç
0² log
1 + 2k
m))((2))
(w: - wy) (ATAVA
64c
7
o² log
rank(2))
2k
[w w511
64C
19

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
where the last equality holds because the last d rank(E) entries of w,; wy are zeros according the way we construct w's (c.f. (25)), and each of the first rank(E) diagonal elements in A is non-zero. Furthermore, by Lemma E.1, each element of (w: wy) is in (-1, 0, 1), and hence the Hamming distance between w, and wj can be bounded as
k - Hamn wi, wz)
I|w; wy 21 I|w; wy S ||willo ||e llo 2k
2
Then,
0
k log (1
26
< 110: 10010
a 8/C
2k log (1 + 2%.
8 8VC
2n
By Lemma E.2, have constructed (v, n) packing of cardinality M with
k log
1 rank(E)
log
rank(E)
A log
rank (2) 21:
8VC
2n
7
32
log M 2
g
Apply Lemma E.3, and we get
v²
+ log 2
inf sup i e
E
0 0+
1
log M
1
A log
(I +
(ank(E) 2k
8 log 2
o²
128Ç
2n
k log
1 1+
rank (2)
2k
k log
1 +
rank
1
2
2k
1
128Ç
2n
4
x²
A: klog
1
(a.)(2))
26
1024C
71
where the last inequality holds if k 2 7. To it, notice that as 1 s k < (an A 2 7, then & logg1
it holds that log(1 + rank(E) 2 log(5). If
+ 2k
(ank(2)
N logg(5) > 16 log,2), and hence
8log 2
à: log
For < h < 6, let W C Rd be a set of vectors of cardinality 2rank(E) such that for wy E W. || = 1, E (+1), and the last (d rank (E)) elements of wy are all zeros. This means Wj E W only has one non-zero element, this element is either pair 10, Wy W such that u/ * Wy. it holds that 2 I|l; wyll < 4. We construct ( "/"ackinn by letting
1, and this non-zero element can only appear in the first rank(E) entries. In this way, for any
02 8VC
log
VA wy. Then, for the same reason above, we have 10,112 B by our assumption on n.
a
Also,
σ
2 logg1 + rank (2)/k)) < 110 1001= S σ
Alog(1 + rank(E)/22)
n
8v
Hence, 1/ =
2 log(1 (2)n)+))))))) n/
1 log(1 + rank ra)) log M = rank log 2. Apply Lemma E.3, and we 16
8v7 get lower bound
log( + (ank())/2k)
(
log(1 + rank (E)/kk)
30²
log(1 + rank (2))
64çn
8
16nk(2)) log 2
256
n
because
log( (r))k()))(2)))))) rank 16 log?
< 1 We can rewrite this lower bound as
Co k log(1 (rank(2)/22
as l: O(1), and this lower bound of the same order as the one for k: 2 7.
20

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
E.2. Proof of Theorem 3.2
For simplicity, we denote [()) = [(0; (6:)=-)) Before proceeding, we define Es(O; (E:)==)) for an index S [d] as
log (M1::=03 . (8s, (au.s .1.1)ss
Es(0) = (s((;; (&r)-)) ==
n Σ
0
+1 +v,==1 FF ( (8g, (To.s (10. 21,)ss
σ
Then, for any 0 such that supp(0) c S, it holds that |00| |10|| ((0) ls(0), and (Vls(0)) (VL(0))s For 0*, we define S = (5 C [d] |S| S 2k, supp(0") C S).
The following two lemmas play a role in the upper bounds in this paper. More specific versions of these two lemmas are used for upper bounding the estimation error of the maximum likelihood estimator with discrete D in Shah et al. (2016). For completeness, we put the proof of Lemma E.4 in Appendix E.6 and the proof of Lemma E.5 in Appendix E.7.
Lemma E.4. If F satisfies the strong log-concavity assumption (10), then for any non-empty index set 5 [d].
(s 0 - (s(0)) - (VEs(0)), 2
7 22 11's.1
408g E I such that 0" + E OB
Lemma E.5. For any non-empty index set S C [d]. (Ves(0))) = = na X Vs. where
Xs [ 11,1)s; ... (No.n 31,n)s) ss TR
and Vs E IR" is random vector with independent components such that V[[s] = 0, and VVlloo S S.
By the definition of the fo-constrained estimator.
((O%,)
min [(0) L())) 0.0n,
Let == supp(0t.) supp(0"). Then, |S| S 2k, and S S. Notice that $ is function of (ed) and hence a random variable. Moreover,
&g (0%) S kz(00), and (VEg(0)) s. = =0
By Lemma E.4, since F' satisfies (10), we have
? d²
(0%
(lg(0r), 0 - =0-)|
((V(s(0*)) 9: (0h - 0r) )00ss)
< (0% 0*) I zg
[[(e)(())) slbsg
where the last inequality is by the Cauchy-Schwarz inequality for dual norms. Hence,
( 88) ) s 0² 22 (VVEg(0)))
We now need to upper bound [[(Ve (0*) big.. By Lemma E.5, (VEg(0))) = - X where
X3 = [ +1,))s (0o,n [s] E x
and Vgg 12 a random vector with independent components defined as
Fx (100) -1.08)//
w.p. F ((8g, ( - -1,5))) /o)
(Vs);
w.p. F ((Ag. (Do.s - f1,)8) /0)
21

---

Leveraging Sparsity for Sample-Effiieen Preference Learning: A Theoretical Perspective
Then, [[([g)+]] = 0 and (Vgg,1 by the definition (11). Define
a² Mg
X3
X3
E
Radd
n2
Then, [(Veg(0)) nt V
X s
V || 0 o0) /V¹S M3V3
V
V
-'m
M3V3
M3Vg. and
8
Since Σg E [ is positive definite by assumption, has an orthogonal diagonalization Σg = U3A - x
where Ugg E ( is an orthogonal matrix, and Ag is diagonal matrix with positive diagonal elements. Then, Xg VnA 1/2 1/2
g Us. and
o² A U (UTASU))
U = o² 72n 1ss
Mg = 72n
Therefore,
18|02 tr(M = 72n I
2ko2 ny²
tr(M3) = 18|01 2ho 7t2² I n2yt ||Mlll = A
d²
722
We then apply Lemma E.6 to get high probability upper bound for V M3Vs.
Lemma E.6 (Bernstein's 's inequality for aub-Gaussian in quadratic form, Theorem 2.1 in Hsu et al. (2012)). Let A Rdxd be matrix, and Σ AT A. Suppose that (#15...,, Fn,) is random vector such that, for some μ R and o 2 it holds for all a E IR" that Elexp(a (x p)}] S exp(Ila|]200 /2). For any t O.
$1 ')
E t tr(2²)
P ||a2|2 > o² (r(()) (<<
+ tr(EppT
1+2
Se-
Since Vg is sub-Gaussian with parameter w2, by Lemma E.6,
P V M3V3
w2 (t((Mg) + +2 tr(M2)t 211AMlll2t) se
]
22k02 1222
2ho4
t + 2 02 $) set
P
V MgV
> w²
+ +2
n2ya
72n
Equivalently, with probability at least 8'
2w²g² (Vi+ + Vlog(1/07)
2
(00% - ) |1 s VVM M&V3 <
t²
72
We notice that for any deterministic S E S and â E θ such that S sup supp(0") and L(0) - L(0"), the above reasoning holds by replacing S and 0t with S and 0, respectively. In other words, for any index set S₁ such that |SA| S for any Ô E B, such that S₁+ supp(0) and L()) = L((*), let S = S& U supp(@") S, and then
P [1 or) s
2 1' 80
The cardinality of S is E (d-H), and E (d= S (4e)
because S d/2. Since S E S is a random variable, we
22

---

Leveraging Sparsity for Sample-Efficienn Preference Learning: A Theoretical Perspective
apply the union bound for all possible S, and get
(1((0t -0-)
2 )
1 P
max SES
0g - 85
2 t'
Eg
0s 0
2 t
Eg
SES
de
8'
<
8'
k
SES
Let = (4)) 8". and we get log(1/0") = k log & + + log(1/6). Then, vk + Vlog(1/0') & 2 2/log lo/////(/)///// (1/0",
and
2w (2 (2V1og(1/01)) 2
8u202 k (alog(d/)) + k log(1/8)
e' <
72
72
n
2Aw² 02 ks log (og(d/k) + log(1/0)
72
n
Hence,
P 0t 0/133 2t
P
||
0%
03'
2
Eg
(0%)
P
033 15
1 8
E.3. Proof Theorem 3.3
For simplicity, we denote C(0, (= as C(0). By the definition of the rrrrgularieed estimator, we have C(O,,) + 11 - (( + 11
B110 1|2 :110, 1l C(de,) -(00)
By the strong log-concavity of F' and Lemma E.4, we have
C( - (06,)-((00)) (V -0") )
2 11 11
0²
Thus,
2 10 -/
80113: s 3/100 3110 11 (V2(0)), 01,) (VL(()) 0*)
3 [1 3110 11 + |V )1 /0,, |V [|
<[ + () |0 111 + (|V - 3) 110e,
where the second inequality is by Hölder's inequality. Next, upper bound |V((0*)) We construct random vector V = Vs as in Lemma E.5 with S = [d], and then no X, V 1 E XiyV, Vs is sub-Gaussian with parameter
=²=² under the assumption that maxigysd |Xill2 I H vr. Hence, 1 ng*
1 |x V
(- fno
P P[]] 2 20=P =P
max Isisd
< 2dexp
(- H2
2w
Let 5 = 2dexp
Eno? H²² ). and get /2wH
log 2d 2d (/8))
B. Thus, with probability at least 1 ō, we have
10
100, - 0'113- < (II + 3) (L(0))l 33) 10
o2
< 11
20 B||0 1|1
= 110,, 83113
23

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
E.4. Proof of Theorem 3.4 For simplicity, we denote [(0, ((:)==)) as [(0). By the definition of the -r-reullarieed estimator,
c(Og,) ) 0 11 s (()0) + 3110"|| = 3110-112 3110,, ll [(de,) _()0)
By the strong log-concavity F' and Lemma E.4, we have
03 10 10 - ((0c.) [(0)) (VC(0)), 0c, - -0r)
s 3 - 3100,111 11I (VC(O"), Or - 0-)
s 0|1001 B B100,, |1 |V )1, 110s, -1
where the last inequality by Hölder's inequality. By assumption, Σ Tallmax I 322 equivalently, x
la
max
1 Hence, ||x & n + 1/(2k)) I 2n for any E [d]. We construct random vector V = Vs as in Lemma E.5 with S [d]. and then + XJV V is sub-Gaussian with parameter " 1X,112
32k
2 na?
Thus,
_tno22
P [[ 2 =P
max IsiSd
2dexp
(-
Aw
Let 5 = 2dexp (- nn 4u
and then, t = 2n
log log(18)
Let 3 = 2t, and then, with probability at least - 6, it holds
that (VC(0))l S 4. Therefore, with probability at least 1-6, 6,
0² 10 - -0 < 3|00 11 - BB10,, 11 + [l= 111
s 310111 - 3110,,11 + B _10e, 11
Denote S = supp(f"), and then,
σ2 110g 11: + $ 010,, 12 s 11 3|10, 11 + Bl1 - 8¹1
7
2
S B(110 |/2 110,,11) (1) +1 (0*)s11 + 311 )s=111) )==111
((1((())sll [1(0,)ssl)) )sll)) ())(0,,) (0*)sll
S 2, )s (0*)sll
where the last inequality due to |1(00)s (1(00,sss)) ssh S =((0,)ss )s (0*) )s || by triangle inequality. Since 2x 100 -0' and
B 10e, 11
3
((0 )s (0*)sll 1 + [ [1( )s ll1
2
(0 )s (0r)sll + ( )s- - (00)s-
2
it holds that
B [1( )s (8*)) - _ )= -00)s= 28)1(),,)s )00)
3
[(0,,)ss - so*))=ll ||| s (l )s - sll)
Thus,
-
(0")slli 5 vIsiI( )s (0')s112 = Vklla 0 S v2 -0'
24

---

Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
where the first inequality is by the Cauchy-Schwarz (a, b) < |||||||||2 by taking 11, and the last is by Assumption 3.2. Then,
7 0 100s 03 s 23
S 22322k100 - -1
110e, 001 23V2k o²
110r, 031 S 8 o²
7 8
Again by Assumption 3.2, we have |00z, - 11 < 16 - 32
E.5. Proof of Lemma E.2
The proof of Lemma E.2 has the same idea of the proof of Lemma Shah et al. (2016) with finite D.
Given ( ()) 1 for any 01, 82 Og Ø. the KL divergence between the two distributions Po, (15))-1) and Po₂ ((5))=)) of preference samples with parameters 0,, 02, respectively, is
(0,,00,1-11.1
(01, T1.s)
DKL. (Pa, ((G))=)) I| Poo ((&))=1)
= Σ
log
F
(02,00, c-21.
==1
+ (1
(881. F1.s)
1 F
(01,200 -x1,T)
log
a
1 F
(022.rp - 3..)
Since for any a, E (0, a log ot s (a- f. we have
DKL (Po. (1&))=)))
Po. (1E))=1)
(61
To,i To.i
x1,s)
(02, Fo,i x1.1)
F
(0
F
F
(02.0011BB..)
(9 2o.i x1,1) F
(02, No.s - -111)) ))
F
(01,2a.-211
F
1 F
(02,20.-21..)
d
n
F
(01.20.:-
F
(02.it0. 2
(82,00,-21.5)
(02.00,1-110) -
Since 110112, |10 < B, || 21,il1a < L for all E [m], by the mean value theorem and ('s definition (7),
Fp.i 21.s)
(62, Fo.; 21.i)
DKL (Pe, ((&)))) Po. ((E)))))
Σ5
0
i=1
nC
(0]
02) TT(0 02)
nC
110
0g 1
25

---

Leveraging Sparsity for Sample-Effiiient Preference Learning: A Theoretical Perspective
E.6. Proof of Lemma E.4
The gradient of Es is of the form
1
Σ
F" (10s, (Fo. - x1,5)s) /0)
(Vis(0))s
10==0)
F ((0s, (Zo, x1,))s) /0)
no i=1
- -F' ((0s: (10, x1,1)s)
1 [m=1)
1 - F ((0g, (Fu,5 z1,1)s) /0) (xo 01,)s
(V(s(0)) =
The sub-matrix of the Hessian of lg indexed by S S is
(V22(0)
1 no Σ (1 (m=0) To,s + 1 (u==)) T1,s) (no.s - 21,0s(F05 - 21.)5
where
(F' ((0s: (20, - x1,1)s /0))2 F F(00s, ( 115sss) /0) F" (10s, (vo.; x11)ss) /0)
To.
(F (Fss,, (Zo,e 21,1)s) /0))
V log F ((0s, (20,5- 21)))s) /0) 2 27
T1. (F' ((0s, (2o,) (1)1))s)/00 /0) 2 (1 F ((0g, (Fu,S - 21,1ss) lo)) (f0, - x1,1ss) /0)
(1- - ((0s, (#o.s 21,)s) /o)2
= V2 log(1 - F' (10s, (Io - 21,4ss /o))
= Vo FF (- (0s, (fo.; - =11,)s) /o) 2 27
and zero the entries in the complement of x S. Hence, for any Rd. have for any 0 On.
27 u
v V²L( = ./g (V² ss us 2
Thus, for any 0' E Rdd such that 0 0' θ holds that
ts( + 0²) Ls((0) -V=))))) > 2 10'1
E.7. Proof of Lemma E.5
F' (10g, (xo.5 - 21,))s) /0)
(Vis(0)))
Σ
1(m==))
F (10'g (No.i x1,)ss) /0)
i=1
F² (18%, (Ko.. (1,s)s)/(1 /0) (1o.5 21,is
+ +1|x==11
F (103, (No, x1,19) /0)
Define Vs as
F' -
w.p. F ((03, (20, - -11.)s) /a)
F( F( (wo, -21)))))1
(Vs);
P' (F0, - 111))
w.p. 1 1- F- ((03, (Fo.i s)) /0)
Then, (Vis(0))) - 1 X3 Vs. Notice that [[[vs] 0, and by the definition (7) of w.
no
F'(2) F'(2)
(VVs) <
sup
F(z) 1- (())')=((2))
=E| 2Bl-2/L/o.2BL/o
26


Reviews:
[{"review_id": "1dnlZjLOuu", "reviewer": "Reviewer_ACSW", "summary": "The paper investigates leveraging sparsity in preference learning to achieve improved sample efficiency. Under the sparse random utility model (RUM), the authors derive minimax optimal estimation rates, emphasizing the theoretical benchmark provided by an $l_0$-constrained estimator. However, recognizing that this estimator is computationally intractable, the authors propose practical $l_1$-regularized estimators and rigorously establish their estimation guarantees. Empirical evaluations substantiate that the $l_1$-regularized estimator, being computationally feasible, achieves significant improvements over standard methods, particularly when sparsity is present.", "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 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:\n\n**(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”*\n\n- **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.\n- **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.\n\n**(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?”*\n\n- **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.\n- **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. \n- **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: \n    - rm-static dataset: $k/d\\approx$ 4.5% (n=800) and $k/d\\approx$ 7.5% (n=3200).\n    - SHP dataset: $k/d\\approx$ 4.2% (n=800) and $k/d\\approx$ 7.2% (n=3200).\n\n    These results show that $\\ell_1$ regularization selects a small and informative subset of features, reinforcing the practical validity of the sparsity assumption. \n\n**(3) Implication on DPO.**  *“Can you share a few insights about the implication of your work on DPO?”*\n\nDPO ([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. \n \nWe thank the reviewer again for the insightful comments. We will incorporate the discussion in the updated version.\n\n[1]https://arxiv.org/pdf/2306.05685\n\n[2]https://arxiv.org/pdf/2305.18290", "claims_and_evidence": "1. When the sparsity is present, *sparse preference learning* reduces the sample complexity from $\\Theta(d/n)$ to $\\Theta(k/n \\log(d/k))$. The claim is well supported by theoretical derivations. The statements about matching upper and lower bounds are accompanied by detailed proofs.\n\n2. An $l_1$-regularized estimator can be made computationally tractable. Under an additional assumption, it can achieve a near-optimal rate. In particular, a \"fast rate\" of $O(k/n\\log(d))$ is shown if the Gram matrix satisfies a restricted eigenvalue-type condition. The claims are also well-supported.", "methods_and_evaluation_criteria": "1. I think $l_0$-constrained MLE method is mainly for the theoretical purpose. It makes sense to develop $l_1$-regularized MLE method, both theoretically and empirically. \n\n2. The authors use synthetic data to control sparsity and dimension, and they verify that the $l_1$-based estimator outperforms the unregularized baseline in small-sample, large-dimension conditions, which is consistent with the theoretical predictions.", "theoretical_claims": "I did not check the proofs in detail.", "experimental_designs_or_analyses": "In Section D.1, they try full fine-tuning (rather than just the last layer) on the same dataset and metrics to see if regularization still helps. The setup seems solid, with consistent hyperparameter choices and a straightforward accuracy measure. However, 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. Even so, I don’t see any major flaws in how they designed or evaluated these experiments.", "relation_to_broader_scientific_literature": "The paper fits into the broader RLHF literature by addressing sample-efficiency concerns in reward modeling.", "essential_references_not_discussed": "Nothing noteworthy to me.", "other_strengths_and_weaknesses": "Strengths:\n1. Their theoretical analysis is thorough and lines up with known compressed sensing results.\n2. They give a clear reason for using sparse preference learning. I think the direction is novel and meaningful.\n\nWeakness:\n1. It is unknown that how often the ground-truth parameter is sparse in real-world application. Hence, it is unclear how effective the approach actually is.\n2. The reported performance gains can be modest, which might limit its practical impact.", "other_comments_or_suggestions": "It might be useful for you to study widely used real-world reward models—perhaps from different RLHF or recommendation pipelines—and check if they already show sparsity in practice. If they do, your approach is strongly reinforced; if not, you could explore alternative ways to handle approximate or partial sparsity.", "questions_for_authors": "1. Can you provide insights or examples of practical scenarios in which your assumptions are realistically met or potentially violated?\n2. Can you share a few insights about the implication of your work on direct preference optimization (DPO)?", "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": "ZO7Engt4wP", "reviewer": "Reviewer_3Ass", "summary": "The authors analyze the sample complexity of RUMs where utilities are an inner product between $d$-dimensional item features $x$ and preference parameters $\\theta$, and where $\\theta$ is $k$-sparse. Whereas existing results on the sample complexity of learning $\\theta$ find that error decays as $\\Theta(d / n)$ with $n$ samples, the authors show that when $\\theta$ is $k$-sparse, this rate can be improved to $\\Theta(k \\log (d / k) / n)$, a large improvement when $d$ is large and $k$ is small. Moreover, the authors show that the $\\ell_1$-regularized MLE has a near-optimal sample complexity. In experiments on synthetic data, the authors demonstrate the sample complexity benefit of using $\\ell_1$ regularization, in line with their theoretical results. They also demonstrate the usefulness of accounting for the sparsity of preferences with $\\ell_1$ regularization in RLHF of LLMs.\n\n### Update after rebuttal\nAh, the squared vs not squared norm explains my confusion. Thanks! Glad to see the other reviewers agree on recommending acceptance.", "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": "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.\n\n**(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)?\"*\n\nWe 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. \n\n**(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?\"*\n\nWe 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. \n\n**(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)”*\n\nWe 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.\n\nWe will incorporate the above discussion, along with the other suggestions mentioned by the reviewer, in our updated version of the paper.", "claims_and_evidence": "All claims are well supported by theoretical, simulation, and experimental evidence.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are solid.", "theoretical_claims": "The claims are very clearly stated and the supplement has proofs. I skimmed the proof of Theorem 3.1, which looks reasonable.", "experimental_designs_or_analyses": "The experiments and subsequent analyses, while not central to the paper, are well done.", "relation_to_broader_scientific_literature": "This paper provides theoretical backing for the practice of $\\ell_1$ regularization in RUMs when the utility parameters are sparse, proving an asymptotic improvement of the best known sample complexity rates when preferences are sparse.", "essential_references_not_discussed": "There is another ICML paper that comes to mind involving sparse RUMs (where only a subset of features are \"salient\" in a particular comparison) that also derives sample complexity rates:\nBower & Balzano. Preference Modeling with Context-Dependent Salient Features, ICML 2020:\nhttps://proceedings.mlr.press/v119/bower20a.html \n\nFrom what I can tell, their convergence rate is $O(\\sqrt{d \\log d / n})$. I think this paper is very much worth discussing in relation to authors' results.\n\n\nA 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)\n- https://proceedings.mlr.press/v97/seshadri19a.html (has sample complexity results for a RUM variant)\n- https://proceedings.neurips.cc/paper/2020/hash/6affee954d76859baa2800e1c49e2c5d-Abstract.html (above model applied to rankings, in the style of Plackett-Luce; also has sample complexity results)\n- https://dl.acm.org/doi/10.1145/3447548.3467250 (uses $\\ell_1$ regularization in a RUM to learn sparse parameters)\n- https://doi.org/10.1017/nws.2023.20 (discusses sample complexity benefit of Laplacian regularization for RUMs with preferences correlated over graphs)\n- https://proceedings.mlr.press/v119/rosenfeld20a.html (another ML-based RUM variant)", "other_strengths_and_weaknesses": "I wish all papers were this well written; thanks to the authors for submitting something so polished. The results and experiments are very nice and I would like to see this paper accepted. It just needs a discussion of Bower & Balzano (2020) and I would like to resolve my question below about the convergence rate from Zhu et al (2023). \n\n\nStrengths:\n- The paper is extremely clearly written, to a very high standard.\n- The problem is both timely in its applications to RLHF and timeless in its application to choice modeling more broadly\n- The results appear to be a significant improvement on prior sample complexity results in the sparse setting, which is very encouraging for using $\\ell_1$ regularization\n- The experiments do a great job of succinctly demonstrating the benefit of leveraging sparsity through $\\ell_1$ regularization\n\nWeaknesses:\n- People have been using $\\ell_1$ regularization when fitting choice models with sparse parameters for many years, so while these new bounds provide some nice theoretical grounding for this approach, it doesn't necessarily impact practice. Perhaps raising this issue is necessary for the RLHF crowd\n- One important related work on RUMs with sparse features is not discussed", "other_comments_or_suggestions": "1. In 1.2, it's worth mentioning in the contribution bullet points that the $\\ell_0$-regularized estimator is infeasible in practice, but $\\ell_1$-regularization is practical (otherwise from reading this section, it's not clear why we wouldn't always use $\\ell_0$ regularization). This point is made very clearly in 3.2.1 and 3.2.2.", "questions_for_authors": "1. The bounds in Zhu, Jodan, and Jiao 2023 appear to be $O(\\sqrt{d / n})$ rather than $O(d / n)$ as stated Table 1. Is there something I'm missing about their results?\n2. How does this model and these sample complexity results compare to those in Bower & Balzano (2020)?", "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": "aw7Wx3B6do", "reviewer": "Reviewer_PinM", "summary": "This paper proposes a sparse setting for preference learning, the authors state that human preferences are driven by some critial factors, of which the dimension is generally low.\nTherefore, the authors study the preference learning problem in the sparse setting from a theoretical perspective, deriving bounds for estimation error under $l_0$ and $l_1$ regularizations, respectively.", "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": "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.\n\n**(1) Evidence for k-sparse assumption for RUM.** *\"I think the k-sparse claim for RUM needs further evidence…\"*\n\nWe 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. \n\n- *\"I wonder if there're other baselines the authors could use in the literature to support this assumption…\"*\n\n    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.\n\n- *\"the second experiment uses the prediction accuracy as the evaluation metric, which is supportive but not directly linked to the sparsity assumption\"*\n\n    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. \n \n**(2) Real-Data Experiments.**\n- *\"the second experiment could be conducted with one more dataset…\" \"The experiments lack sufficient baselines.\"*\n\n    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. \n- *\"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.\"*\n\n    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. \n- *\"Are there any other evaluation metrics for the quality of reward models in experiment 4.2?\"*\n\n    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. \n\n**(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?\"*\n\nWe 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. \n\nWe 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.", "claims_and_evidence": "I think the k-sparse claim for RUM needs further evidence.\nAlthough the authors provide better theoretic bounds for estimation error in dimension $d$, the overall claim of this paper that RUM is sparse is not validated in experiments.\nThe first experiment directly uses this assumption to sample the ground-truth $\\theta^*$, and the second experiment uses the prediction accuracy as the evaluation metric, which is supportive but not directly linked to the sparsity assumption.\nI wonder if there're other baselines the authors could use in the literature to support this assumption.\n\nI have no problems with other assumptions.", "methods_and_evaluation_criteria": "If the authors could have further justification for the sparsity assumption, then the proposed methods make sense.\n\nActually, the second experiment could be conducted with one more dataset, to provide more comprehensive evaluation.", "theoretical_claims": "Yes, I checked the derivation of the four main theorems in the Appendix.", "experimental_designs_or_analyses": "The experiment 4.1 validates the effectiveness of $l_1$ regularization compared with standard MLE in the preference learning case.\nHowever, the ground-truth parameter $\\theta^*$ is manually set to be sparse, which undermines this experiment. \nAlso, this experiment does not justify the assumption that RUM in preference learning satisfies sparsity.\n\nThe experiment 4.2 uses LLM alignment as the task, and the reward model accuracy on the test set is used as the evaluation metric. \nHowever, the rm-static dataset, which is a split of HH dataset [1], may contain noise [2], reducing the reliability of the experiment results.\nThe authors should consider adding a cleaner dataset for experiment. \n\n[1] https://huggingface.co/datasets/Anthropic/hh-rlhf\n\n[2] Impact of preference noise on the alignment performance of generative language models, COLM 2024", "relation_to_broader_scientific_literature": "The authors may consider apply the sparsity setting to other preference learning algorithms with utility models, for example, DPO [1];\nThe sparsity assumption might somehow relate to sparse attention [2, 3], but in different perspectives.\n\n\n[1] Direct Preference Optimization: Your Language Model is Secretly a Reward Model, NeurIPS 2023\n\n[2] Linformer: Self-Attention with Linear Complexity\n\n[3] Efficient Streaming Language Models with Attention Sinks, ICLR 2024", "essential_references_not_discussed": "I think the authors have covered the most related literature.", "other_strengths_and_weaknesses": "Strengths:\n\nThe theoretical derivations in this paper are complete and provide insights for learning utility functions based on pairwise comparisons under the sparsity assumption.\n\nWeaknesses:\n1. The sparsity assumption in this paper is not well justified.\n2. The experiments lack sufficient baselines.", "other_comments_or_suggestions": "From a reader's perspective, I would suggest the authors adding references for theorem derivations around each theorem in the main content.", "questions_for_authors": "1. How would the authors justify that using sparsity in this scenario is a reasonable approach?\n2. Is the experiment in section 4.1 necessary? As previous research has shown that $l_1$ regularization works well under the sparsity condition in MLE, what is the main difference between preference learning under sparsity and previous literature?\n3. Are there any other evaluation metrics for the quality of reward models in experiment 4.2?", "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": "GdAgGQDy74", "reviewer": "Reviewer_Q6xK", "summary": "The paper explores the impact of sparsity in preference learning, establishing a minimax lower bound on empirical error under sparse RUM and deriving upper bounds for two sparsity-regularized estimators. The experiments, conducted on both a synthetic dataset and an LLM alignment setting, validate the theoretical findings.", "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 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.\n\n(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?\"*\n\nWe 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.\n\n[1] https://jmlr.org/papers/volume23/19-571/19-571.pdf\n\n[2] https://arxiv.org/pdf/2303.01372\n\n[3] https://arxiv.org/pdf/2203.08564\n\n(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?\"*\n\nWe 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.\n\n(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?\"*\n\nYes, 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.\n\n(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?\"*\n\nWe 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.\n\nWe once again thank the reviewer for the recognition and thoughtful questions. We believe these discussions will help guide valuable extensions of this work.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check the details into the proofs due to time constraints.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper connects the well-known role of sparsity in traditional compressed sensing to preference learning, highlighting its ubiquity across broader literature.", "essential_references_not_discussed": "Reference well discussed.", "other_strengths_and_weaknesses": "**Strengths:**  \n- The paper is comprehensive, establishing both a lower bound and upper bounds for different estimators, along with a clear comparison between them.  \n- The experimental setup is well-designed and effectively validates the theoretical contributions.  \n- The writing is clear and seamlessly integrates the two topics in a straightforward manner.  \n\n**Weaknesses:**  \n- It focuses solely on the fixed design setup (i.e., a deterministic set of pairs) and does not address generalization error.", "other_comments_or_suggestions": "No.", "questions_for_authors": "- To address the limitation of the fixed design setup, can we explore ways to generalize the model? \n- 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?  \n- 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?  \n- 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?", "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: Paper studies choice modeling (preference learning) under $k$-sparsity constraint on the $d$-dimensional parameters. Authors show that if the true model is sparse then the minimax sample complexity lower-bound for learning the choice model is only $\widetilde{\Omega}(k)$ instead $\widetilde{\Omega}(d)$. Further, they show that $\ell_1$ regularized MLE estimator achieves this rate. Finally, paper uses synthetic experiments and very few LLM reward modeling results to showcase their algorithm. The paper is well written and the proofs appear correct. However, it was noted that analysis and algorithmic techniques used in the paper mostly follow from past literature on compressed sensing. So overall the theoretical and synthetic results are not surprising. Further, since the paper studies choice modeling in the context of RLHF, authors could have spent more effort on evaluating and verifying their ideas on more reward modeling datasets and LLMs and its effectiveness.
Decision: Accept (poster)