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

arXiv: https://arxiv.org/abs/2501.18282 · HTML: https://mlsanity.com/paper/2501.18282/

## 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.

## Placed in

- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

## Builds on (most cited first, 30 of 44)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Self-Rewarding Language Models](https://mlsanity.com/paper/2401.10020/) (2024)
- [Scalable agent alignment via reward modeling: a research direction](https://mlsanity.com/paper/1811.07871/) (2018)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Statistical Rejection Sampling Improves Preference Optimization](https://mlsanity.com/paper/2309.06657/) (2023)
- [Understanding Dataset Difficulty with V-Usable Information](https://mlsanity.com/paper/2110.08420/) (2021)
- [Is DPO Superior to PPO for LLM Alignment? A Comprehensive Study](https://mlsanity.com/paper/2404.10719/) (2024)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Generative Reward Models](https://mlsanity.com/paper/2410.12832/) (2024)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [DeepSpeed-Chat: Easy, Fast and Affordable RLHF Training of ChatGPT-like Models at All Scales](https://mlsanity.com/paper/2308.01320/) (2023)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [Rethinking Bradley-Terry Models in Preference-Based Reward Modeling: Foundations, Theory, and Alternatives](https://mlsanity.com/paper/2411.04991/) (2024)
- [The Crucial Role of Samplers in Online Direct Preference Optimization](https://mlsanity.com/paper/2409.19605/) (2024)
- [Choice modelling in the age of machine learning -- discussion paper](https://mlsanity.com/paper/2101.11948/) (2021)

## Built on by (most cited first, 3 of 3)

- [Understanding the Performance Gap in Preference Learning: A Dichotomy of RLHF and DPO](https://mlsanity.com/paper/2505.19770/) (2025)
- [Learning Parametric Distributions from Samples and Preferences](https://mlsanity.com/paper/2505.23557/) (2025)
- [Learning Distributions from Samples and Qualities](https://mlsanity.com/paper/2610.17956/) (2026)

## 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.