Abstract: Black-box reduction from offline optimization to online algorithms has been the topic of study of numerous works (Kalai and Vempala (2005); Dudík et al. (2017); Kakade et al. (2009); Hazan and Koren (2016)). In this work, we consider designing online algorithms for problems with greedy approximation algorithms which are robust to local errors. Our first result is a reduction which gives a $O(\sqrt{T})$-regret algorithm for the full information setting via Blackwell Approachability. Next, we introduce Bandit Blackwell Sequential Games which is a bandit version of Blackwell Approachability, and leverage this to get a reduction which gives a $O(T^{2/3})$-regret algorithm in the bandit setting. We further show several applications of these reductions to problems including submodular maximization, reserve pricing in auctions, and assortment optimization. 

Bio: Negin Golrezaei is the KDD Career Development Professor in Communications and Technology and an Assistant Professor of Operations Management at the MIT Sloan School of Management. Her current research interests are in the area of machine learning, statistical learning theory, mechanism design, and optimization algorithms with applications to revenue management, pricing, and online markets. Before joining MIT, Negin spent a year as a postdoctoral fellow at Google Research in New York where she worked with the Market Algorithm team to develop, design, and test new mechanisms and algorithms for online marketplaces. She received her Ph.D. (2017) in operations research from USC. Negin is the recipient of several awards including the 2021 Young Investigator Award at ONR, the 2018 Google Faculty Research Award, and the 2017 George B. Dantzig Dissertation Award.