Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
On the map: LLM alignment / RLHF / preference optimisation → LLM preference optimization methods
Abstract (arXiv)
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 ℓ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.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 44 of its 105 references that are in the map. First posted on arXiv 30 Jan 2025.
Builds on
44 of 105 references.
Closest ancestors · 6
Same direction, newest first
- 2024Accelerated Preference Optimization for Large Language Model Alignment8 Oct
- 2024The Crucial Role of Samplers in Online Direct Preference Optimization29 Sep
- 2024Is DPO Superior to PPO for LLM Alignment? A Comprehensive Study16 Apr
- 2023A General Theoretical Paradigm to Understand Learning from Human Preferences18 Oct
- 2023Statistical Rejection Sampling Improves Preference Optimization13 Sep
- 2022Training language models to follow instructions with human feedback4 Mar
Other references · 38
- 2024The Llama 3 Herd of Modelscited by 14,715
- 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
- 2017Deep reinforcement learning from human preferencescited by 3,912
- 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
- 2020Learning to summarize from human feedbackcited by 2,588
- 2019Fine-Tuning Language Models from Human Preferencescited by 2,150
- 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,786
- 2017Neural Collaborative Filteringcited by 1,111
- 2022Scaling Laws for Reward Model Overoptimizationcited by 1,095
- 2024Self-Rewarding Language Modelscited by 681
- 2018Scalable agent alignment via reward modeling: a research directioncited by 447
- 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
26 more
- 2021Understanding Dataset Difficulty with V-Usable Informationcited by 291
- 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
- 2024Self-Play Preference Optimization for Language Model Alignmentcited by 232
- 2024Generative Reward Modelscited by 148
- 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
- 2023DeepSpeed-Chat: Easy, Fast and Affordable RLHF Training of ChatGPT-like Models at All Scalescited by 108
- 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
- 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 102
- 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
- 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
- 2015Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependencecited by 61
- 2024Rethinking Bradley-Terry Models in Preference-Based Reward Modeling: Foundations, Theory, and Alternativescited by 48
- 2021Choice modelling in the age of machine learning -- discussion papercited by 26
- 2014Minimax-optimal Inference from Partial Rankingscited by 24
- 2021Optimal Full Ranking from Pairwise Comparisonscited by 16
- 2023Block Coordinate Descent on Smooth Manifolds: Convergence Theory and Twenty-One Examplescited by 16
- 2019Discovering Context Effects from Raw Choice Datacited by 14
- 2019Predicting Choice with Set-Dependent Aggregationcited by 13
- 2015Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisonscited by 11
- 2020Learning Interpretable Feature Context Effects in Discrete Choicecited by 10
- 2020Preference Modeling with Context-Dependent Salient Featurescited by 8
- 2023Learning Rich Rankingscited by 8
- 2022Graph-Based Methods for Discrete Choicecited by 6
- 2023Learning Choice Functions with Gaussian Processescited by 5
- 2024A tutorial on learning from preferences and choices with Gaussian Processescited by 4
- 2020Learning Choice Functions via Pareto-Embeddingscited by 3
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.
Similar, not cited
Close in wording, no citation either way
- 2025Preference Learning with Response Time: Robust Losses and Guarantees
- 2025Preference learning made easy: Everything should be understood through win rate
- 2024Enhancing Preference-based Linear Bandits via Human Response Time
- 2026Reward Learning from Best-of-N Preference Data: Targets, Tradeoffs, and Design Principles
- 2025Preference Optimization via Contrastive Divergence: Your Reward Model is Secretly an NLL Estimator
- 2025DCRM: A Heuristic to Measure Response Pair Quality in Preference Optimization
- 2025SparseRM: A Lightweight Preference Modeling with Sparse Autoencoder
- 2025Clear Preferences Leave Traces: Reference Model-Guided Sampling for Preference Learning