Online Ranking with Constraints: A Primal-Dual Algorithm and Applications to Web Traffic-Shaping

ABSTRACT

We study the online constrained ranking problem motivated by an application to web-traffic shaping: an online stream of sessions arrive in which, within each session, we are asked to rank items. The challenge involves optimizing the ranking in each session so that local vs. global objectives are controlled: within each session one wishes to maximize a reward (local) while satisfying certain constraints over the entire set of sessions (global). A typical application of this setup is that of page optimization in a web portal. We wish to rank items so that not only is user engagement maximized in each session, but also other business constraints (such as the number of views/clicks delivered to various publishing partners) are satisfied.

We describe an online algorithm for performing this optimization. A novel element of our approach is the use of linear programming duality and connections to the celebrated Hungarian algorithm. This framework enables us to determine a set of shadow prices for each traffic-shaping constraint that can then be used directly in the final ranking function to assign near-optimal rankings. The (dual) linear program can be solved off-line periodically to determine the prices. At serving time these prices are used as weights to compute weighted rank-scores for the items, and the simplicity of the approach facilitates scalability to web applications. We provide rigorous theoretical guarantees for the performance of our online algorithm and validate our approach using numerical experiments on real web-traffic data from a prominent internet portal.

References

1. Deepak Agarwal, Shaunak Chatterjee, Yang Yang, and Liang Zhang 2015. Constrained Optimization for Homepage Relevance. Proceedings of the 24th International Conference on World Wide Web (WWW '15 Companion). ACM, New York, NY, USA, 375--384. http://dx.doi.org/10.1145/2740908.2745398
2. Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, and Xuanhui Wang 2011. Click Shaping to Optimize Multiple Objectives. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ,11). ACM, New York, NY, USA, 132--140. http://dx.doi.org/10.1145/2020408.2020435
3. Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, and Xuanhui Wang 2012. Personalized Click Shaping Through Lagrangian Duality for Online Recommendation Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '12). ACM, New York, NY, USA, 485--494. http://dx.doi.org/10.1145/2348283.2348350
4. Shipra Agrawal, Zizhuo Wang, and Yinyu Ye 2014. A Dynamic Near-Optimal Algorithm for Online Linear Programming. Operations Research, Vol. 62, 4 (2014), 876--890. http://dx.doi.org/10.1287/opre.2014.1289
5. M. F. Balcan, A. Blum, J. D. Hartline, and Y. Mansour. 2005. Mechanism design via machine learning. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). 605--614. 0.1145/2482540.2482603
6. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani 2005. Adwords and generalized on-line matching. In In FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 264--273.
7. Peter Orlik and Hiroaki Terao 1992. Arrangements of Hyperplanes. Springer-Verlag.
8. A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Learning to rank

        • Ranking

    • Learning settings

      • Online learning settings

    • Machine learning algorithms