Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
Speakers
Negin Golrezaei
Associate Professor, MIT Sloan School of Management
Negin Golrezaei is the W. Maurice Young (1961) Career Development Associate Professor of Management and an Associate Professor of Operations Management at the MIT Sloan School of Management. Her research focuses on advancing online marketplaces—such as e-commerce, online advertising, and emissions trading systems—by designing and implementing data-driven strategies and algorithmic innovations. She aims to create more resilient, equitable, and sustainable digital ecosystems. Before joining MIT, Negin was a postdoctoral fellow at Google Research in New York, where she collaborated with the Market Algorithm team to develop and test new mechanisms for online marketplaces. She holds a BSc (2007) and MSc (2009) in electrical engineering from Sharif University of Technology, Iran, and a PhD (2017) in operations research from the University of Southern California. Negin serves as an associate editor for Operations Research, Production and Operations Management, Operations Research Letters, and Naval Research Logistics. Her recognitions include the 2021 ONR Young Investigator Award, the 2018 Google Faculty Research Award, the 2017 George B. Dantzig Dissertation Award, the INFORMS Revenue Management and Pricing Section Dissertation Prize, and the USC Outstanding Teaching Award (2017).
| Date: |
| Friday, 11 October 2024 |
| Time: |
| 10:00 am - 11:30 am |
| Venue: |
|
NUS Business School Mochtar Riady Building BIZ1 0201 15 Kent Ridge Drive Singapore 119245 (Map) |
Abstract
In today’s digital landscape, the ability to make timely and informed decisions is paramount. Our research addresses the challenge of adapting offline algorithms to dynamic online scenarios, presenting a versatile framework with wide-reaching implications. We focus on combinatorial problems that lend themselves to efficient approximations through robust greedy algorithms. Our framework leverages the concept of “Blackwell approachability” to seamlessly transform these algorithms from offline to online settings.
Under full information conditions, our online algorithms exhibit approximate regrets of 𝑂(√𝑇). Taking our approach further, we introduce “Bandit Blackwell approachability,” extending its applicability to dynamic online decision-making. In the bandit setting, our framework achieves approximate regrets of 𝑂(𝑇^{2/3}).
Our research extends to various domains, including revenue management, market design, and online optimization. We tackle challenges such as product ranking optimization, auction reserve price optimization, and submodular maximization. Moreover, we apply our techniques to first-order methods in continuous optimization, facilitating efficient solutions in various contexts. Numerical simulations demonstrate that our approach outperforms theoretical expectations in real-world scenarios.