Computational and Statistical Tradeoffs in Learning to Rank

By Ashish Khetan, Sewoong Oh. 2016

15 citations recorded by the source corpus.

For massive and heterogeneous modern datasets, it is of fundamental interest to provide guarantees on the accuracy of estimation when computational resources are limited. In the application of learning to rank, we provide a hierarchy of rank-breaking mechanisms ordered by the complexity in thus generated sketch of the data. This allows the number of data points collected to be gracefully traded off against computational resources available, while guaranteeing the desired level of accuracy. Theoretical guarantees on the proposed generalized rank-breaking implicitly provide such trade-offs, which can be explicitly characterized under certain canonical scenarios on the structure of the data.

Subfields: Artificial Intelligence, Management Science and Operations Research, Information Retrieval & Search, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Heejong Bong
2. Alessandro Rinaldo
3. Kengo Kato

In Management Science and Operations Research

1. Heejong Bong
2. Alessandro Rinaldo

In Information Retrieval & Search

1. Heejong Bong
2. Alessandro Rinaldo

Citations in the corpus

• Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, background): “Novel bounds on the (cid:96) 2 estimation of the BLT models are derived in Negahban et al. (2012); Hajek et al. (2014); Khetan & Oh (2016); Shah et al. (2016); Chen et al. (2020a).”