Timezone: »

 
A Light-speed Linear Program Solver for Personalized Recommendation with Diversity Constraints
Miao Cheng · Haoyue Wang · Aman Gupta · Rahul Mazumder · Sathiya Selvaraj · Kinjal Basu

@
in OPT 2022: Optimization for Machine Learning »
Event URL: https://openreview.net/forum?id=3qeYTmrEAOP »

We study a structured linear program (LP) that emerges in the need of ranking candidates or items in personalized recommender systems. Since the candidate set is only known in real time, the LP also needs to be solved in real time. Latency and user experience are major considerations, requiring the LP to be solved within just a few milliseconds. Although typical instances of the problem are not very large in size, this stringent time limit is beyond the capability of most existing commercial LP solvers, which can take 20 milliseconds or more to find a solution. Thus, reliable methods that address the real-world complication of latency become necessary.In this paper, we propose a fast specialized LP solver for a structured problem with diversity constraints.Our method solves the dual problem, making use of the piece-wise affine structure of the dual objective function, with an additional screening technique that helps reduce the dimensionality of the problem as the algorithm progresses. Experiments reveal that our method can solve the problem within roughly 1 millisecond, yielding a 20x improvement in speed over the most performant standard LP solvers. This speed-up can help improve the quality of recommendations without affecting user experience, highlighting how optimization can provide solid orthogonal value to machine-learned recommender systems.

Author Information

Miao Cheng (LinkedIn)
Miao Cheng

I am currently part of the Data/AI team at LinkedIn, building end-to-end innovative AI/ML solutions for products at scale. Tsinghua University (Bachelor's degrees in Automation/EECS and Economics) + UPenn Computer Science Grad.

Haoyue Wang (Massachusetts Institute of Technology)
Aman Gupta (LinkedIn)
Rahul Mazumder (MIT)
Sathiya Selvaraj (LinkedIn)
Kinjal Basu (LinkedIn)

More from the Same Authors