ISyE Seminar Series: Rad Niazadeh

“From Offline Greedy Algorithms to Online Learning: Theory and Applications”

Rad Niazadeh

Assistant Professor of Operations Management and Asness Junior Faculty Fellow
The University of Chicago Booth School of Business

About the seminar:

Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones using Blackwell approachability. We show that the resulting online algorithms have O(T^{1/2}) (approximate) regret under the full information setting. We further introduce a bandit extension of Blackwell approachability and leverage this notion to transform greedy robust offline algorithms into a O(T^{2/3})(approximate) regret in the bandit setting. Demonstrating the flexibility of our framework, we apply our offline-to-online transformation to several problems at the intersection of revenue management, market design, and online optimization, including product ranking optimization in online platforms, reserve price optimization in auctions, and submodular maximization. We show that our transformation, when applied to these applications, leads to new regret bounds or improves the current known bounds. If time permits, I will also elaborate on some open problems and future directions stemming from this work. 

The talk is based on the following paper:

Conference version has appeared in ACM EC'21 
Journal version in Management ScienceBio:https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3613756

Bio:

Rad Niazadeh is an Assistant Professor of Operations Management and Asness Junior Faculty Fellow at The University of Chicago Booth School of Business. He is also part of the faculty at Toyota Technological Institute of Chicago (TTIC) by a courtesy appointment. Prior to joining Chicago Booth, he was a visiting researcher at Google Research NYC and a postdoctoral fellow at Stanford University, Computer Science Department. He finished his PhD in Computer Science (minored in Applied Mathematics) at Cornell University. Rad primarily studies the theory and applications of online algorithms and learning, as well as data-driven sequential decision making and mechanism design. His research aims to design market algorithms and mechanisms for real-time operations of online marketplaces and e-commerce platforms, as well as operations of governmental agencies and non-profit organizations. Rad has received several awards for his research, including the INFORMS Auctions and Market Design 2021 Rothkopf Junior Researcher Paper Award (first place), the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention), Service Science Best Student Paper (third place), and the Google PhD Fellowship (in Market Algorithms).