Name
Title | ||
|---|---|---|
Improved Bounds for Online Learning Over the Permutahedron and Other Ranking Polytopes. |
Abstract | ||
|---|---|---|
Consider the following game: There is a fixed set V of n items. At each step an adversary chooses a score function s(t) : V bar right arrow [0, 1], a learner outputs a ranking of V, and then s(t) is revealed. The learner's loss is the sum over v is an element of V, of s(t)(v) times v's position (0th, 1st, 2nd, ...) in the ranking. This problem captures, for example, online systems that iteratively present ranked lists of items to users, who then respond by choosing one (or more) sought items. The loss measures the users' burden, which increases the further the sought items are from the top. It also captures a version of online rank aggregation. We present an algorithm of expected regret O(n root OPT + n(2)), where OPT is the loss of the best (single) ranking in hindsight. This improves the previously best known algorithm of Suehiro et. al (2012) by saving a factor of Omega(root log n). We also reduce the per-step running time from O(n(2)) to O(n log n). We provide matching lower bounds. The goal of the system is to minimize its total loss after T steps. (For simplicity assume T is known in this work.) The total loss of the system is (additively) compared against that of the best (in hindsight) single ranking played throughout. The difference is called regret. |
Year | Venue | Field |
|---|---|---|
2014 | JMLR Workshop and Conference Proceedings | Online learning,Ranking,Computer science,Permutohedron,Polytope,Artificial intelligence,Adversary,Score,Machine learning |
DocType | Volume | ISSN |
Conference | 33 | 1938-7288 |
Citations | PageRank | References |
6 | 0.48 | 12 |
Authors | ||
1 | ||