Large scale multi-objective optimization: Theoretical and practical challenges
This work addresses practical challenges in large-scale recommendation systems for internet applications, representing an incremental improvement over existing constrained optimization approaches.
The paper tackles limitations in multi-objective optimization for recommendation systems, specifically addressing constraints, scalability, and variance issues in constrained optimization formulations. The proposed solutions achieve a 100× scalability improvement over existing R packages and reduce variance of dual estimates by two orders of magnitude.
Multi-objective optimization (MOO) is a well-studied problem for several important recommendation problems. While multiple approaches have been proposed, in this work, we focus on using constrained optimization formulations (e.g., quadratic and linear programs) to formulate and solve MOO problems. This approach can be used to pick desired operating points on the trade-off curve between multiple objectives. It also works well for internet applications which serve large volumes of online traffic, by working with Lagrangian duality formulation to connect dual solutions (computed offline) with the primal solutions (computed online). We identify some key limitations of this approach -- namely the inability to handle user and item level constraints, scalability considerations and variance of dual estimates introduced by sampling processes. We propose solutions for each of the problems and demonstrate how through these solutions we significantly advance the state-of-the-art in this realm. Our proposed methods can exactly handle user and item (and other such local) constraints, achieve a $100\times$ scalability boost over existing packages in R and reduce variance of dual estimates by two orders of magnitude.