The NodeHopper: Enabling Low Latency Ranking with Constraints via a Fast Dual Solver

Anton Zhernov, Krishnamurthy Dj Dvijotham, Ivan Lobov, Dan A. Calian, Michelle X. Gong, Natarajan Chandrashekar, Timothy A. MannKDD 2020 · OpenReview

Abstract

Modern recommender systems need to deal with multiple objectives like balancing user engagement with recommending diverse and fresh content. An appealing way to optimally trade these off is by imposing constraints on the ranking according to which items are presented to a user. This results in a constrained ranking optimization problem that can be solved as a linear program (LP). However, off-the-shelf LP solvers are unable to meet the severe latency constraints in systems that serve live traffic. To address this challenge, we exploit the structure of the dual optimization problem to develop a fast solver. We analyze theoretical properties of our solver and show experimentally that it is able to solve constrained ranking problems on synthetic and real-world recommendation datasets an order of magnitude faster than off-the-shelf solvers, thereby enabling their deployment under severe latency constraints.
BibTeX
@inproceedings{zhernov2020nodehopper,
  author = {Anton Zhernov and Krishnamurthy Dj Dvijotham and Ivan Lobov and Dan A. Calian and Michelle X. Gong and Natarajan Chandrashekar and Timothy A. Mann},
  title = {{The NodeHopper: Enabling Low Latency Ranking with Constraints via a Fast Dual Solver}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=zphJBaZu8_z},
}

Loading related content...

Figure