Research map / Learning theory and algorithms / Sample complexity
Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that under a sparse random utility model, preference learning's minimax error rate drops from Θ(d/n) to Θ((k/n)log(d/k)), and proves ℓ1-regularized MLE achieves near-optimal rates, with experiments on synthetic data and LLM reward modeling.
Problem
Preference learning (reward modeling from pairwise comparisons) needs sample size linear in the feature dimension d for the classical Θ(d/n) error rate, which is costly when d is large and human labels are expensive.
Approach
Exploits sparsity of the true reward parameter (k-sparse) in the random utility model to derive sparse minimax lower and upper bounds, and shows ℓ0-constrained MLE is minimax optimal while ℓ1-regularized MLE is nearly optimal under a restricted eigenvalue condition; applies the ℓ1 penalty to the reward head in LLM reward modeling.
Key results
- Sparse minimax lower bound Omega((k/n)log(d/k)) and l0-constrained MLE attains the matching rate, versus Theta(d/n) without sparsity.
- On rm-static with frozen Llama-3.2-1B (d=2048), l1 regularization improves test accuracy by at least 3% over the unregularized baseline.
- Full fine-tuning with l1 on the last layer improves accuracy by about 0.9-1.0 points (e.g., Llama-3.2-1B rm-static 66.8% to 67.7%; Pythia-70M 60.5% to 61.8%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add ℓ1 regularization to the final layer | Pythia-70M reward model · rm-static test | accuracy: 60.5 -> 61.8 | Helped |
| Add ℓ1 regularization to the final layer | Llama-3.2-1B reward model · rm-static test | accuracy: 66.8 -> 67.7 | Helped |
| Add ℓ1 regularization to the final layer | Llama-3.2-3B reward model · rm-static test | accuracy: 68.4 -> 69.4 | Helped |
| Add ℓ1 regularization to the final layer | Pythia-70M reward model · SHP test | accuracy: 60.8 -> 62.1 | Helped |
| Add ℓ1 regularization to the final layer | Llama-3.2-1B reward model · SHP test | accuracy: 64.4 -> 65.5 | Helped |
| Add ℓ1 regularization to the final layer | Llama-3.2-3B reward model · SHP test | accuracy: 66.5 -> 67.3 | Helped |
| Add ℓ1 regularization to the final layer | Llama-3.2-1B frozen-backbone reward model · rm-static and SHP, test accuracy across sample sizes | accuracy: at least 3% | Helped |
| Use ℓ1 regularization instead of the unregularized maximum-likelihood estimator | Synthetic preference learning · Synthetic data, varying sparsity ratio and sample size | estimation error | Helped |
| Increase sparsity of the ground-truth parameter | Synthetic preference learning with the ℓ1-regularized estimator · Synthetic data, decreasing k/d | estimation error | Helped |
Limitations
- l0-constrained estimator is computationally intractable; only the l1 estimator is practical.
- Fixed design analysis with assumptions (strong log-concavity, restricted eigenvalue/incoherence) that may not hold for real LLM features.
- Real-data experiments use a small set of models and a fixed linear reward head; improvements are modest (about 1-3 points).
Experimental setup
Datasets: rm-static SHP synthetic data
Benchmarks: rm-static test accuracy SHP test accuracy synthetic estimation error
Metrics: estimation error in Sigma semi-norm pairwise prediction accuracy
Baselines: maximum likelihood estimator (unregularized, beta=0)
Builds on: Bradley-Terry-Luce model Thurstone-Mosteller model LASSO DeepSpeed-Chat
Closest papers by meaning
- Preference Learning with Response Time: Robust Losses and Guarantees (NeurIPS 2025 · similarity 0.88)
- Preference learning made easy: Everything should be understood through win rate (ICML 2025 · similarity 0.87)
- Enhancing Preference-based Linear Bandits via Human Response Time (NeurIPS 2024 · similarity 0.87)
- Differentially Private Sparse Reward Estimation with Preference Feedback (NeurIPS 2026 · similarity 0.86)
- Geometric-Averaged Preference Optimization for Soft Preference Labels (NeurIPS 2024 · similarity 0.86)
- Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.