ISyE Seminar Series: Ali Makhdoumi

"Sequence-Submodularity and its Application to Online Advertising"

Presentation by Professor Ali Makhdoumi
Assistant Professor of Decision Sciences
Fuqua School of Business
Duke University
 

Wednesday, February 24
3:30-5:00 PM CST — Graduate Seminar and Reception (Zoom)
 

About the seminar:

Motivated by applications in online advertising, we consider a class of maximization problems where the objective is a function of the sequence of actions as well as the running duration of each action. For these problems, we introduce the concepts of sequence-submodularity and sequence-monotonicity which extend the notions of submodularity and monotonicity from functions defined over sets to functions defined over sequences. We establish that if the objective function is sequence-submodular and sequence-non-decreasing, then there exists a greedy algorithm that achieves 1− 1/e of the optimal solution.
 
We apply our algorithm and analysis to two applications in online advertising and one application in resource extraction. In particular, we establish that online ad allocation, query rewriting, and online resource extraction problems can be formulated as maximizing non-decreasing sequence-submodular functions. We then apply our framework to these problems, leading to simple greedy approaches with guaranteed performances. (This is joint work with Saeed Alaei and Azarakhsh Malekian.)

Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability (pdf)
 

Bio:

Ali Makhdoumi is an Assistant Professor of Decision Sciences at Fuqua School of Business, Duke University. Before joining Fuqua in 2018, he has earned his Ph.D. from the Laboratory for Information and Decision Systems (LIDS) at the Massachusetts Institute of Technology. His research interest includes optimization, game theory, and learning theory with applications to social and technological systems. His recent works explore problems in data markets with privacy concerns, online review systems, online advertisement, online streaming platforms, and testing strategies during pandemics.