Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective
This work addresses the high cost of collecting human-annotated data for preference learning, offering a theoretical and practical solution for more efficient modeling of human choices, though it is incremental in applying sparsity techniques to this domain.
The paper tackles the sample-efficiency problem in preference learning by leveraging sparsity in the model, reducing the minimax optimal estimation error rate from Θ(d/n) to Θ(k/n log(d/k)) under a sparse random utility model, with experiments showing significant reductions in sample complexity and improved prediction accuracy.
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 $Θ(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 $Θ(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.