# Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent

arXiv: https://arxiv.org/abs/2011.02817 · HTML: https://mlsanity.com/paper/2011.02817/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2020.

## Built on by (most cited first, 6 of 6)

- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)
- [An Improved Algorithm For Online Min-Sum Set Cover](https://mlsanity.com/paper/2209.04870/) (2022)
- [Tight Bounds for γ-Regret via the Decision-Estimation Coefficient](https://mlsanity.com/paper/2303.03327/) (2023)
- [Learning-Augmented Algorithms for k-median via Online Learning](https://mlsanity.com/paper/2603.18157/) (2026)

## Abstract (arXiv)

We consider a natural model of online preference aggregation, where sets of preferred items R1, R2, ldots, Rt along with a demand for kt items in each Rt, appear online. Without prior knowledge of (Rt, kt), the learner maintains a ranking πt aiming that at least kt items from Rt appear high in π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 oblivious deterministic and randomized rounding schemes, we map doubly stochastic matrices back to rankings with a small loss in the GMSSC objective.