Timezone: »

 
Poster
Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent
Dimitris Fotakis · Thanasis Lianeas · Georgios Piliouras · Stratis Skoulakis

Thu Dec 10 09:00 PM -- 11:00 PM (PST) @ Poster Session 6 #1817
in Poster Session 7 »

We consider a natural model of online preference aggregation, where sets of preferred items R1, R2, ..., Rt, ..., along with a demand for kt items in each Rt, appear online. Without prior knowledge of (Rt, kt), the learner maintains a ranking \pit aiming that at least kt items from Rt appear high in \pi_t. This is a fundamental problem in preference aggregation with applications to e.g., ordering product or news items in web pages based on user scrolling and click patterns.

The widely studied Generalized Min-Sum-Set-Cover (GMSSC) problem serves as a formal model for the setting above. GMSSC is NP-hard and the standard application of no-regret online learning algorithms is computationally inefficient, because they operate in the space of rankings. In this work, we show how to achieve low regret for GMSSC in polynomial-time. We employ dimensionality reduction from rankings to the space of doubly stochastic matrices, where we apply Online Gradient Descent. A key step is to show how subgradients can be computed efficiently, by solving the dual of a configuration LP. Using deterministic and randomized rounding schemes, we map doubly stochastic matrices back to rankings with a small loss in the GMSSC objective.

Author Information

Dimitris Fotakis (National Technical University of Athens)
Thanasis Lianeas (National Technical University of Athens)
Georgios Piliouras (Singapore University of Technology and Design)
Stratis Skoulakis (Singapore University of Technology and Design)

More from the Same Authors