# Label Ranking through Nonparametric Regression

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 108 references that are in the map.
- First posted on arXiv 4 Nov 2021.

## Builds on (most cited first, 12 of 12)

- [Estimation and Inference of Heterogeneous Treatment Effects using Random Forests](https://mlsanity.com/paper/1510.04342/) (2015)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Understanding Random Forests: From Theory to Practice](https://mlsanity.com/paper/1407.7502/) (2014)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [A Structured Prediction Approach for Label Ranking](https://mlsanity.com/paper/1807.02374/) (2018)
- [Narrowing the Gap: Random Forests In Theory and In Practice](https://mlsanity.com/paper/1310.1415/) (2013)
- [Estimation and Inference with Trees and Forests in High Dimensions](https://mlsanity.com/paper/2007.03210/) (2020)
- [Aggregating Incomplete and Noisy Rankings](https://mlsanity.com/paper/2011.00810/) (2020)
- [Random Forest for Label Ranking](https://mlsanity.com/paper/1608.07710/) (2016)
- [Ranking Median Regression: Learning to Order through Local Consensus](https://mlsanity.com/paper/1711.00070/) (2017)
- [A Multiclass Classification Approach to Label Ranking](https://mlsanity.com/paper/2002.09420/) (2020)
- [Non-linear Label Ranking for Large-scale Prediction of Long-Term User Interests](https://mlsanity.com/paper/1606.08963/) (2016)

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

- [Fairness in Ranking: Robustness through Randomization without the Protected Attribute](https://mlsanity.com/paper/2403.19419/) (2024)
- [Multimodal Label Relevance Ranking via Reinforcement Learning](https://mlsanity.com/paper/2407.13221/) (2024)
- [MORE-PLR: multi-output regression employed for partial label ranking](https://mlsanity.com/paper/2609.29386/) (2026)

## Abstract (arXiv)

Label Ranking (LR) corresponds to the problem of learning a hypothesis that maps features to rankings over a finite set of labels. We adopt a nonparametric regression approach to LR and obtain theoretical performance guarantees for this fundamental practical problem. We introduce a generative model for Label Ranking, in noiseless and noisy nonparametric regression settings, and provide sample complexity bounds for learning algorithms in both cases. In the noiseless setting, we study the LR problem with full rankings and provide computationally efficient algorithms using decision trees and random forests in the high-dimensional regime. In the noisy setting, we consider the more general cases of LR with incomplete and partial rankings from a statistical viewpoint and obtain sample complexity bounds using the One-Versus-One approach of multiclass classification. Finally, we complement our theoretical contributions with experiments, aiming to understand how the input regression noise affects the observed output.