Rad Niazadeh
Assistant Professor of Operations Management
University of Chicago

From Offline Greedy Algorithms to Online Learning: Theory and Applications

Abstract

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 an 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 (with Negin Golrezaei, Joshua Wang, Fransisca Susan, and Ashwinkumar Badanidiyuru): "Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization", Management Science, 2022 (the conference version has appeared in ACM EC'21) https://pubsonline.informs.org/doi/10.1287/mnsc.2022.4558

Biography

Rad Niazadeh is an Assistant Professor of Operations Management 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 interplay between algorithms, incentives, and learning in real-time operations of online marketplaces and e-commerce platforms. His research aims to build theoretical methodologies and generic frameworks to design faster and economically efficient market algorithms, and also to help with addressing humanitarian needs (such as equity, fairness, and non-discrimination) in 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), and the Google PhD Fellowship (in Market Algorithms).

Martin Wainwright
Professor of Electrical Engineering and Computer Science
Massachusetts Institute of Technology

Challenges with Covariate Shift: What is it and what to do about it?

Abstract

A central problem in statistics and machine learning is prediction: learning how to predict responses based on observed features/covariates. It is very well-understood under the canonical assumption of test and training distributions being identical. But what if they differ, as has been documented in many applications? In this talk, we give an overview of some research that characterizes fundamental limits, and provides some computationally efficient algorithms for prediction under covariate shift.

Biography

Martin Wainwright is currently the Cecil H. Green Professor at MIT in EECS and Mathematics, with affiliations with LIDS, IDSS and SDSC. He received a Bachelor's degree in Mathematics from University of Waterloo, Canada, a Ph.D. degree in EECS from Massachusetts Institute of Technology (MIT). His research interests include high-dimensional statistics, stochastic control and reinforcement learning, causal inference, and information-theoretic methods in statistics. Among other awards, he has received the COPSS Presidents' Award (2014) from the Joint Statistical Societies; the David Blackwell Medal (2017) and Medallion Lectureship (2013) from the Institute of Mathematical Statistics, Section Lecturer at the International Congress of Mathematicians in 2014.

Saurabh Amin
Associate Professor of Civil and Environmental Engineering
Massachusetts Institute of Technology

Platform-Enabled Learning and Information Provision for Congestion Management

Abstract

In this talk, we focus on analyzing the dynamic interactions between users and AI-driven platforms in the face of uncertainty. This entails modeling the learning capabilities of platforms using data generated by users who make strategic decisions in an uncertain environment. First, we present our work on the learning dynamics induced by users who repeatedly interact with each other, while learning an unknown parameter (latent state) that impacts their payoffs. Here, platform updates the belief estimate of the parameter given users’ strategies and realized payoffs. Players then adjust their strategies based on the updated belief. We develop convergence and stability results on these learning dynamics and present conditions for the identifiability of the latent state. We apply these results to learning-based incentive design, in particular to socially optimal tolling for congestion management. Next, we discuss an information design problem to manage strategic users providing service across a network. In the presence of uncertain location-specific payoffs, users can make decisions that lead to unwanted congestion, and hence unreliable service. We design an optimal signaling mechanism over the payoff uncertainty that shapes users’ choices to align outcomes with the platform’s preferences. We show that information provision is an effective tool for managing congestion in comparison to simple benchmarks, and discuss applications to managing hybrid work to contain disease spread and improving driver availability in ride-hailing systems.

Biography

Saurabh Amin is Associate Professor in the Department of Civil and Environmental Engineering (CEE) at Massachusetts Institute of Technology (MIT). He currently serves as Director of Henry L. Pierce Laboratory for Infrastructure Science and Engineering and CEE Undergraduate Officer. He is a member of the Laboratory of Information and Decision Systems (LIDS) and the Operations Research Center (ORC) at MIT. Since joining MIT in 2012, he has pursued research in the design of inspection and control algorithms for infrastructure systems. His work has addressed problems in resilient network control, information systems and incentive design, and optimal resource allocation in large-scale infrastructure systems. Amin received his Ph.D. in Systems Engineering from the University of California Berkeley in 2011.

Necmiye Ozay
Associate Professor of Electrical Engineering and Computer Science
University of Michigan

Formal methods for Cyber Physical Systems: State of the Art and Future Challenges

Abstract

Modern cyber-physical systems, like high-end passenger vehicles, aircraft, or robots, are equipped with advanced sensing, learning, and decision making modules. On one hand these modules render the overall system more informed, possibly providing predictions into the future. On the other hand, they can be unreliable due to problems in information processing pipelines or decision making software. Formal methods, from verification and falsification to correct-by-construction synthesis hold the promise to detect and possibly eliminate such problems at design-time and to provide formal guarantees on systems' correct operation. In this talk, I will discuss several recent advances in control synthesis and corner case generation for cyber-physical systems with a focus on scalability, and what role data and learning can play in this process. I will conclude the talk with some thoughts on challenges and interesting future directions.

Biography

Necmiye Ozay received her B.S. degree from Bogazici University, Istanbul in 2004, her M.S. degree from the Pennsylvania State University, University Park in 2006 and her Ph.D. degree from Northeastern University, Boston in 2010, all in electrical engineering. She was a postdoctoral scholar at the California Institute of Technology, Pasadena between 2010 and 2013. She joined the University of Michigan, Ann Arbor in 2013, where she is currently an associate professor of Electrical Engineering and Computer Science, and Robotics. Dr. Ozay’s research interests include hybrid dynamical systems, control, optimization and formal methods with applications in cyber-physical systems, system identification, verification & validation, autonomy and dynamic data analysis. Her papers received several awards. She has received the 1938E Award and a Henry Russel Award from the University of Michigan for her contributions to teaching and research, and five young investigator awards, including NSF CAREER, DARPA Young Faculty Award, ONR Young Investigator Award, and NASA Early Career Faculty Award. She is also a recent recipient of the Antonio Ruberti Young Researcher Prize from the IEEE Control Systems Society for her fundamental contributions to the control and identification of hybrid and cyber-physical systems.