Computational and Statistical Tradeoffs in Learning to Rank
This work addresses computational-statistical trade-offs in ranking for large-scale applications, offering incremental improvements in efficiency and accuracy.
The paper tackles the problem of balancing computational resources and statistical accuracy in learning to rank for massive datasets, by proposing a hierarchy of rank-breaking mechanisms that trade off data collection against computation while guaranteeing accuracy, with theoretical guarantees provided under canonical data structures.
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.