Review for NeurIPS paper: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent

Summary and Contributions: The paper studies a variant of online ranking problem. In the offline settings preferred items belong to different groups, and one need to generate a sequence of items so that qualitatively speaking for each group R_t of items at least k_t elements appear high in the list. More formally they formulate the problem as an online version of the known "Generalized Min-Sum Set Cover" (GMSSC) task: In this problem, given a set U {1,...,n} of n items, in each step 1. The learner selects a permutation \pi_t items in U 2. The adversary selects a request R_t \subset U with demand k_t . The goal is to minimize the multiplicative regret, that is the ratio of the total cost to the cost of selecting a fixed optimal permutation \pi* in all steps.