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

Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, Stratis Skoulakis

Abstract

The Generalized Min-Sum-Set-Cover (GMSSC) problem is a fundamental challenge in online ranking, where a system must order items to satisfy user demands with minimal access cost. Standard online learning approaches face an exponential explosion in the search space ($n!$ permutations). This paper introduces a framework that reduces the problem's dimensionality to $n^2$ by operating within the space of doubly stochastic matrices. By applying Online Projected Gradient Descent (OPGD) and novel rounding schemes, the authors provide the first polynomial-time algorithms with provable regret bounds, specifically achieving 28-regret for GMSSC and 11.713-regret for the Min-Sum-Set-Cover (MSSC) variant.

Introduction

In many real-world applications, such as search engines or e-commerce platforms, items must be ranked to satisfy diverse user preferences. In the Generalized Min-Sum-Set-Cover (GMSSC) problem, each user $t$ has a set of preferred items $R_t$ and a demand $k_t$. The goal is to minimize the "access cost"—the position of the $k_t$-th preferred item in the ranking.

The online version of this problem is particularly difficult. An algorithm must choose a ranking for the current user without knowledge of future requests. Traditional "experts" algorithms like Multiplicative Weights Update are computationally infeasible because the number of possible rankings (experts) is $n!$. This paper addresses this bottleneck through a continuous relaxation and dimensionality reduction approach.

Methodology: From Permutations to Matrices

The core innovation lies in shifting the optimization from the discrete space of permutations to the continuous space of doubly stochastic matrices.

Dimensionality Reduction

Instead of searching the $n!$ corners of a permutohedron, the authors map the problem to the space of $n \times n$ doubly stochastic matrices (where rows and columns sum to 1). This reduces the search space to $n^2$ dimensions, making the problem computationally tractable.

Conceptual mapping from the $n!$-dimensional permutohedron to $n^2$-dimensional doubly stochastic matrices.

Optimization and the Duality Trick

The authors define a "fractional access cost" using a Configuration Linear Program (LP). Although this LP has exponentially many variables, its subgradients can be computed in polynomial time by solving the dual problem. The algorithm uses Online Projected Gradient Descent (OPGD) to update the matrix $A^t$ at each step. While the ellipsoid method can be used for subgradient computation, the authors also provide faster quadratic-time algorithms for specific cases like MSSC.

Rounding Schemes

To produce a physical ranking, the fractional matrix must be "rounded" back to a permutation. The paper introduces both randomized and deterministic rounding schemes. The randomized schemes ensure that the expected cost of the ranking is within a constant factor of the fractional cost, while the deterministic schemes provide robust performance against adversarial requests.

Key Results

The proposed framework yields significant theoretical and empirical improvements over existing methods. The randomized algorithm for GMSSC achieves a 28-regret bound in polynomial time. For the simpler MSSC case (where $k_t = 1$), the regret bound is improved to 11.713.

Summary of regret bounds and running times for GMSSC and MSSC variants.

Empirically, the deterministic rounding scheme for MSSC showed exceptional performance in simulations, achieving a regret bound related to the maximum request set size ($2 \cdot \max_t |R_t|$). In practice, these algorithms tracked closely with state-of-the-art offline approximation algorithms, demonstrating their utility for real-time ranking tasks.

Conclusion

By bridging the gap between continuous convex optimization and discrete combinatorial ranking, this work provides a scalable solution for online GMSSC. The use of doubly stochastic matrices as a proxy for permutations allows for efficient gradient-based learning while maintaining strong theoretical guarantees. Future work remains to close the gap between the current 11.713 upper bound and the known lower bound of 4 for polynomial-time algorithms.

Summary updated

BibTeX
@inproceedings{fotakis2020efficient,
  author = {Dimitris Fotakis and Thanasis Lianeas and Georgios Piliouras and Stratis Skoulakis},
  title = {{Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=ILmAi9sS1Ijt},
}
Figure