IEOR-DRO Seminar

[View Recording]

Title: A (slightly) Improved Approximation algorithm for Metric TSP

Abstract: In an instance of the (metric) traveling salesperson problem (TSP), we are given a list of n cities and their pairwise symmetric distances satisfying the triangle inequality, and we want to find the shortest tour that visits all cities exactly once and returns back to the starting point. I will talk about an algorithm that provably returns a tour whose cost is at most 50-eps percent more than the optimum where eps>0 is a small constant independent of n. This slightly improves classical algorithms of Christofides and Serdyukov from the 1970s. 

The proof exploits a deep connection to the rapidly evolving area of geometry of polynomials. In this area, we encode discrete phenomena, in our case uniform spanning tree distributions, in coefficients of complex multivariate polynomials, and we understand them via the interplay of the coefficients, zeros, and function values of these polynomials. Over the last fifteen years, this perspective has led to several breakthroughs in computer science such as construction of Ramanujan graphs and the Mihail-Vazirani's and Mason's conjectures for matroids. I will discuss how some of the ideas of this field can be used to design and analyze algorithms for TSP. 

Based on a joint work with Anna Karlin and Nathan Klein.

Bio: Shayan Oveis Gharan is an associate professor of the Paul Allen School of Computer Science and Engineering at University of Washington. He received his PhD from the MS&E department at Stanford University in 2013. Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley. Shayan's research exploits several tools in Mathematics such as theory of real stable and log-concave polynomials, and spectral graph theory to design and analyze (optimization) algorithms for discrete objects.

[View Recording]

Title: On Incorporating Forecast Information into MDPs

Abstract: In an increasing number of sequential decision-making applications, one has forecast information that can be used to enhance the decision process. In particular, in developing more efficient energy systems, one has the ability to use weather forecasts to improve the control of the associated system. In this talk, we will discuss ongoing work at Stanford that relates to the operation of Stanford’s district heating and cooling system, as well as a mathematical MDP formulation for linear control systems that takes into account forecast information in a principled way. By principled, we mean that the forecasts are required to be mathematically consistent with the underlying state dynamics, in the sense that the forecasts are required to satisfy a cerain martingale property. This work is joint with Jacques de Chalendar.

Bio: Peter W. Glynn is the Thomas Ford Professor in the Department of Management Science and Engineering (MS&E) at Stanford University, and also holds a courtesy appointment in the Department of Electrical Engineering. He was Director of Stanford's Institute for Computational and Mathematical Engineering from 2006 until 2010 and served as Chair of MS&E from 2011 through 2015. He is a Fellow of INFORMS and a Fellow of the Institute of Mathematical Statistics, and was an IMS Medallion Lecturer in 1995 and INFORMS Markov Lecturer in 2014. He was co-winner of the Outstanding Publication Awards from the INFORMS Simulation Society in 1993, 2008, and 2016, was a co-winner of the Best (Biannual) Publication Award from the INFORMS Applied Probability Society in 2009, was the co-winner of the John von Neumann Theory Prize from INFORMS in 2010, and gave the INFORMS Philip McCord Morse Lecture in 2020. In 2012, he was elected to the National Academy of Engineering. He was Founding Editor-in-Chief of Stochastic Systems and served as Editor-in-Chief of Journal of Applied Probability and Advances in Applied Probability from 2016 to 2018. His research interests lie in simulation, computational probability, queueing theory, statistical inference for stochastic processes, and stochastic modeling.

[View Recording]

Title: Research in Online Ad Markets: Automation, Robustness, and Learning

Abstract: We provide an overview of recent trends and future challenges in online ad markets with a focus on robustness, incentive-aware learning, and the auto-bidding world. In the first part,  we survey recent results and highlight challenges that emerge as the majority of advertisers adopt automatic bidding algorithms to bid on their behalf and the market transitions to the so-called auto-bidding world. As part of the move to more automation, we discuss (adversarial) robustness in designing online algorithms, learning, and pricing schemes. In particular, we present online learning algorithms that work under stochastic models with adversarial corruptions and describe recently developed algorithmic techniques that achieve the best of many worlds in a variety of online stochastic and adversarial models. Along the same lines, we discuss the design of dynamic mechanisms for repeated auctions that are robust to the presence of noise or imprecise forecasts. Next, we touch upon robustness in pricing, and explore incentive-aware learning algorithms for pricing in both dynamic and static auctions. Finally, we complement these results by exploring data-driven techniques to measure the extent to which bidders have incentives to strategize their bids in ad auctions.

Bio: Vahab Mirrokni is a distinguished scientist, serving as senior director for the New York and Zurich algorithms research groups at Google Research. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 2001. He joined Google Research in 2008, after spending a couple of years at Microsoft Research, MIT and Amazon.com. He is the co-winner of paper awards at KDD'15, ACM EC'08, and SODA'05. His research areas include algorithms, distributed and stochastic optimization, and computational economics. The specific areas include Market Algorithms, Graph Mining, and Large-scale Optimization.

[View Recording: Part 1 & Part 2]

Title: Exactness in SDP Relaxations of Quadratically Constrained Quadratic Programs

Abstract: Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly

nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in general, they admit a natural family of tractable convex relaxations.  In this talk, we will study the standard semidefinite program (SDP) relaxation for general QCQPs and examine when this relaxation is exact. By analyzing the "geometry" of the SDP relaxation, we will give both sufficient conditions and necessary conditions for different types of "exactness" conditions, and discuss a number of implications of these results for various applications.

This is joint work with Alex L. Wang and C.J. Argue.

Bio: Fatma Kılınç-Karzan is the Frank A. and Helen E. Risch Faculty Development Chair and Associate Professor of Operations Research at Tepper School of Business, Carnegie Mellon University. She holds a courtesy appointment at the Department of Computer Science as well.  She completed her PhD at Georgia Institute of Technology in 2011. Her research interests are on foundational theory and algorithms for convex optimization and structured nonconvex optimization, and their applications in optimization under uncertainty, machine learning and business analytics. Her work was the recipient of several best paper awards, including 2015 INFORMS Optimization Society Prize for Young Researchers and 2014 INFORMS JFIG Best Paper Award. Her research has been supported by generous grants from NSF and ONR, including an NSF CAREER Award.

[View Recording]

Title: Learning through the Grapevine: The Impact of Noise and the Breadth and Depth of Social Networks

Abstract: We study how communication platforms, or a society more generally, can improve social learning without censoring or fact-checking messages. We analyze learning as a function of social network depth (how many times information is relayed) and breadth (the number of relay chains accessed). Noise builds up as depth increases, so learning requires greater breadth. We characterize sharp thresholds for breadths above which receivers learn fully and below which they learn nothing. However, slight uncertainty about the noise structure can destroy learning even in arbitrarily broad networks. Learning can be restored by capping depth or, if that is not possible, limiting breadth (e.g., by capping the number of people to whom someone can forward a given message). Although it reduces total communication, limiting breadth increases the fraction of received messages originating closer to the receiver, thereby increasing the signal to noise ratio. We also extend our model to study learning from message survival when people are more likely to pass messages with one conclusion than another. We find that as depth grows, all information comes from either the total number of messages received or their content, but the learner does not need to pay attention to both. Thus, a forwarding cap for the policymaker is robust to whether receivers are fully Bayesian or naive and simply count relative rates of messages they receive.

Bio: Matthew O. Jackson is the William D. Eberle Professor of Economics at Stanford University and an external faculty member of the Santa Fe Institute. He was at Northwestern University and Caltech before joining Stanford, and received his BA from Princeton University in 1984 and PhD from Stanford in 1988. Jackson's research interests include game theory, microeconomic theory, and the study of social and economic networks, on which he has published many articles and the books `The Human Network' and `Social and Economic Networks'. He also teaches an online course on networks and co-teaches two others on game theory. Jackson is a Member of the National Academy of Sciences, a Fellow of the American Academy of Arts and Sciences, a Fellow of the Econometric Society, a Game Theory Society Fellow, and an Economic Theory Fellow, and his other honors include a Guggenheim Fellowship, the Social Choice and Welfare Prize, the von Neumann Award from Rajk Laszlo College, an honorary doctorate from Aix-Marseille University, the Jean-Jacques Laffont Prize from the Toulouse School of Economics, the B.E.Press Arrow Prize for Senior Economists, and teaching awards. He has served on the editorial boards of Econometrica, Games and Economic Behavior, PNAS, the Review of Economic Design, and as the President of the Game Theory Society.

[View Recording]

Title: Advances in Gaussian Processes

Abstract: I present some of our group’s recent work on Gaussian processes (GP) both from a theoretical and applied perspective. I first introduce the Renye GP which is an alternative objective for GPs capable of improving generalization through tuning the induced regularization. I then highlight the ability of mini-batch stochastic gradient descent to perform inference in GPs (a correlated setting) and hence scaling them far beyond what has been thought possible. From an applied perspective, I introduce predictive GP models that can be used for joint event data, weakly supervised settings and state of the art multi-output regression.

Bio: Raed Al Kontar is an Assistant Professor in the Department of Industrial & Operations Engineering at the University of Michigan and an affiliate with both the Michigan Institutes for Data science (MIDAS) and Computational Discovery and Engineering (MICDE). Raed's main research interest is data science using probabilistic models. Raed also focuses on data science applications within Internet of Things (IoT) enabled systems, specifically in tele-service settings. Some of his awards include best paper finalist in INFORMS QSR section (2018-winner, 2019) and Data mining section (2020).