Online rank aggregation

Shota Yasutake, Kohei Hatano, Eiji Takimoto, Masayuki Takeda

Research output: Contribution to journalConference articlepeer-review

12 Citations (Scopus)


We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We prove a lower bound of the cumulative loss and hardness results. Then, we propose an algorithm for this problem and prove its relative loss bound which shows our algorithm is close to optimal.

Original languageEnglish
Pages (from-to)539-553
Number of pages15
JournalJournal of Machine Learning Research
Publication statusPublished - 2012
Event4th Asian Conference on Machine Learning, ACML 2012 - Singapore, Singapore
Duration: Nov 4 2012Nov 6 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Online rank aggregation'. Together they form a unique fingerprint.

Cite this