Prof. Van-Anh Truong
Assistant Professor, Columbia University
Talk:
Dynamic Optimization of Mobile Push Advertising Campaigns
Abstract:
We study a novel resource-allocation problem faced by Alibaba Group. In this problem, mobile “push messages” must be sent over the course of a day to hundreds of millions of users. Each message can be sent to any number of users, and yields a reward when it generates a clickthrough, subject to a budget constraint on the total reward over all users for the message. This budget represents the maximum amount that an advertiser is willing to pay for clickthroughs for the message on a given day. Given users’ diverse preferences, the problem aims to deliver the “right messages” to the “right users” to maximize ad revenues without overwhelming each user with too many messages. Due to the large size of the real application, we analyze algorithms for the above problem in an asymptotic regime. We consider a novel scaling of the problem “size,” called big-data scaling. In this scaling, as the problem size grows, the number of users, as well as their diversity, grow. The scaling captures the fact that individual user information remains highly granular and distinctive even as the size of the user base increases. We prove that solving the problem as a static assignment problem results in a regret of O( √ t), where t is the parameter scaling the problem. Furthermore, adding a single recourse opportunity, by sending push messages in two cycles over the course of a day and making use of information observed in the first cycle to adapt decisions in the second cycle, can reduce the regret to O(t 1/4 log t). Finally, the difference in regret between the static and dynamic strategy can be Ω(√ t). Numerical experiments on three real data sets, each containing several hundred million users, show that the latter strategy improves the regret of the former by at least 10%-50%.
Biography:
Professor Van-Anh Truong joined the Industrial Engineering and Operations Research Department in 2010. She received a Bachelor's degree from University of Waterloo in Mathematics in 2002, and a Ph.D. from Cornell University in Operations Research in 2007. Before coming to Columbia, Professor Truong was a quantitative associate at Credit Suisse, and a quantitative researcher at Google.Professor Truong is interested in a broad class of problems that arise in Operations Management. These problems address decision making under uncertainty in information-rich and highly dynamic environments. Her research focuses on developing approaches to circumvent the “curse of dimensionality” in these problems.
