The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems

Dec 3 2021 - 1pm


Prof. Haihao Lu


Abstract: Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker.

We design a general class of algorithms that attain good performance in various inputs models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under stochastic i.i.d. input model as well as various non-stationary stochastic input models (i.e., robust corruption, Markov process and periodic process), and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover dual sub-gradient descent and dual exponential weights algorithm. The resulting algorithms are simple, fast, robust, and does not require convexity/concavity on the reward functions, consumption functions and the action space, in contrast to existing methods for online allocation problems.

Bio: Haihao (Sean) Lu is an assistant professor of Operations Management at the University of Chicago Booth School of Business. His research interests are in extending the computational and mathematical boundaries of methods for solving the large-scale optimization problems that arise in data science, machine learning, and operations research. Before joining Booth, he was a research scientist at Google Research large-scale optimization team, where he primarily worked on designing and implementing a huge-scale linear programming solver. He obtained his Ph.D degree jointly in Operations Research and in Mathematics at MIT in 2019. He is the winner of INFORMS Optimization Society Young Researcher Prize (2021).