Past Seminars

Bruce Hajek

University of Illinois at Urbana-Champaign

On Non-unique Solutions in Mean Field Games

Slides and Paper

Date: July 13, 2020



More info.

Abstract

The theory of mean field games has arisen as a tool to understand noncooperative dynamic stochastic games with a large number of agents. Much of the theory has evolved under conditions ensuring uniqueness of the mean field game Nash equilibrium. However, in some situations, typically involving symmetry breaking, non-uniqueness of solutions is an important feature. To investigate the nature of non-unique solutions, we focus on the technically simple setting where agents have one of two states, with continuous time dynamics, and the game is symmetric in the players, and players are restricted to using Markov strategies. We identify all the mean field game Nash equilibria. Such equilibria correspond to symmetric ϵ-Nash Markov equilibria for the large N finite systems such that ϵ→0 as N→∞. In contrast to the mean field game, for the finite systems there is a unique Nash equilibrium. We focus on the problem of identifying which mean field game equilibria correspond to the limit of the Nash equilibria for the finite N system.

This is joint work with Michael Livesay.

Bio

Bruce Hajek is a Center for Advanced Study Professor and Head of Electrical and Computer Engineering, Hoeft Chair of Engineering, and Research Professor in the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign, where he has been on the faculty since 1979. He received a BS in Mathematics and MS in Electrical Engineering from the University of Illinois and the Ph. D. in Electrical Engineering from the University of California at Berkeley. Prof. Hajek's research interests include communication networks, auction theory, stochastic analysis, combinatorial optimization, machine learning, information theory, and bioinformatics. He served as Editor-in-Chief for the IEEE Transactions on Information Theory, and as President of the IEEE Information Theory Society. He received the Institute of Electrical and Electronics Engineers (IEEE) Kobayashi Award for Computer Communication and the ACM SIGMETRICS Achievement Award and he is a member of the US National Academy of Engineering.

Amy Ward

University of Chicago Booth School of Business

Behavior-aware Queueing

Slides and Paper

Date: July 20, 2020



More info.

Abstract

Service system design is often informed by queueing theory, which helps system managers understand the impact of design decisions on performance. Traditional queueing theory assumes servers work at constant (possibly heterogeneous) rates, or speeds. That is reasonable in computer science and manufacturing contexts. However, the servers in service systems are people, and, in contrast to machines, their work speed can be influenced by the systemic incentives design decisions create. Workload is one such systemic incentive. Empirical research documents servers speeding up or slowing down depending both on how much work there is (i.e., the number of customers waiting) and amongst how many people that work is divided (i.e., the number of servers). We develop an analytical model to investigate how server work speed is affected by the system design decisions concerning (i) how many servers to staff, and (ii) whether and when to turn away customers.


We do this in the context of a finite-buffer, many-server queue (specifically, an M/M/N/k queue), except that we do not assume that service rates are exogenous. Instead, we assume each server selfishly chooses her service rate in order to maximize an expected utility that captures an inherent trade-off between idleness and effort cost in a fixed-wage service system with no monetary incentives. Then, the service rates emerge as the solution to a noncooperative game. We provide results on equilibrium existence and uniqueness, and demonstrate non-monotonic behavior. These results indicate that the commonly accepted rule of thumb that reducing workload decreases customer waiting can be flawed.


This is joint work with Raga Gopalakrishnan (Smith School of Business, Queen’s University) and Yueyang Zhong (Booth PhD Student).

Bio

Amy R. Ward is the Rothman Family Professor of Operations Management at the University of Chicago Booth School of Business. She received her Ph.D. from Stanford University in 2001. She recently was the chair of the Applied Probability Society (term 11/2016–11/2018) and the Service Management SIG Chair for the MSOM Society (term 6/2017–6/2019). She is the Stochastic Models co-Area Editor for the journal Operations Research (term 1/2018–present).

Mariana Olvera-Cravioto

University of North Carolina at Chapel Hill

Stochastic Recursions on Random Graphs

Slides

Date: July 27, 2020



More info.

Abstract

We study a family of Markov processes on directed graphs where the values at each vertex are influenced by the values of its inbound neighbors and by independent fluctuations either on the vertices themselves or on the edges connecting them to their inbound neighbors. Typical examples include PageRank and other information propagation processes on directed graphs. Assuming a stationary distribution exists for this Markov chain, our goal is to characterize the marginal distribution of a uniformly chosen vertex in the graph. In order to obtain a meaningful characterization, we assume that the underlying graph is either a directed configuration graph or an inhomogeneous random digraph, both of which are known to converge, in the local weak sense, to a marked Galton-Watson process. We then prove that the stationary distribution we study on the graph converges in some Wasserstein metric to a function of i.i.d. copies of the special endogenous solution to a branching distributional fixed-point equation.

This is joint work with Nicolas Fraiman and Tzu-Chi Lin.

Bio

Mariana Olvera-Cravioto obtained her BS in Applied Mathematics from the “Instituto Tecnológico Autónomo de México (ITAM)” and her PhD in Management Science and Engineering from Stanford University. She has been an Associate Professor at UNC Chapel Hill since 2018, and prior to that she was a faculty member at the Industrial Engineering and Operations Research departments at Columbia University and UC Berkeley. Her recent research is mostly focused on the study of processes and algorithms on scale-free random graphs, such as those used to model the web and other social networks. More broadly, she is interested in random graph theory, branching processes, distributional fixed-point equations, heavy-tailed phenomena, and stochastic simulation.

R Srikant

University of Illinois at Urbana-Champaign

Load Balancing in Bipartite Graphs

Slides

Date: August 3, 2020



More info.

Abstract

Motivated by the problem of achieving zero queueing delay and minimum response time in cloud computing systems with data locality, we consider a bipartite graph where the left nodes generate jobs and the right nodes are servers. A job arriving at a left node can be routed to one of the right nodes to which it is connected. The servers have heterogeneous processing rates. We show that the JFSQ policy for routing is asymptotically optimal in the large-system limit, provided that the graph is sufficiently well connected. Under JFSQ (join-the-fastest-of-the shortest-queues), a job is routed to a server with the smallest job backlog, breaking ties in favor of faster servers.

Joint work with Wentao Weng and Xingyu Zhou.

Bio

R. Srikant is the co-Director of the C3.ai Digital Transformation Institute, and the Fredric G. and Elizabeth H. Nearing Professor in the Department of Electrical and Computer Engineering and the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. He is the recipient of the 2015 INFOCOM Achievement Award and the 2019 IEEE Koji Kobayashi Computers and Communications Award, and has received several Best Paper awards including the 2015 INFOCOM Best Paper Award, and the 2017 Applied Probability Society Best Publication Award. He was the Editor-in-Chief of the IEEE/ACM Transactions on Networking from 2013-2017. His research interests include applied probability, machine learning, and communication networks.

Andrea Montanari

Stanford University

Self-induced regularization from linear regression to neural networks

Slides

Date: August 10, 2020



More info.

Abstract

Modern machine learning methods – most noticeably multi-layer neural networks – require to fit highly non-linear models comprising tens of thousands to millions of parameters. Despite this, little attention is paid to the regularization mechanism to control model's complexity. Indeed, the resulting models are often so complex as to achieve vanishing training error: they interpolate the data. Despite this, these models generalize well to unseen data: they have small test error.

I will discuss several examples of this phenomenon, beginning with a simple linear regression model, and ending with two-layers neural networks in the so-called lazy regime. For these examples precise asymptotics could be determined mathematically, using tools from random matrix theory. I will try to extract a unifying picture. A common feature is the fact that a complex unregularized nonlinear model becomes essentially equivalent to a simpler model, which is however regularized in a non-trivial way.

Based on joint papers with: Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Feng Ruan, Youngtak Sohn, Jun Yan, Yiqiao Zhong.

Bio

Andrea Montanari received a Laurea degree in Physics in 1997, and a Ph. D. in Theoretical Physics in 2001 (both from Scuola Normale Superiore in Pisa, Italy). He has been post-doctoral fellow at Laboratoire de Physique Théorique de l'Ecole Normale Supérieure (LPTENS), Paris, France, and the Mathematical Sciences Research Institute, Berkeley, USA. Since 2002 he is Chargé de Recherche (with Centre National de la Recherche Scientifique, CNRS) at LPTENS. In September 2006 he joined Stanford University as a faculty, and since 2015 he is Full Professor in the Departments of Electrical Engineering and Statistics.

He was co-awarded the ACM SIGMETRICS best paper award in 2008. He received the CNRS bronze medal for theoretical physics in 2006, the National Science Foundation CAREER award in 2008, the Okawa Foundation Research Grant in 2013, and the Applied Probability Society Best Publication Award in 2015. He is an Information Theory Society distinguished lecturer for 2015-2016. In 2016 he received the James L. Massey Research & Teaching Award of the Information Theory Society for young scholars, and in 2017 was elevated to IEEE Fellow. In 2018 he was an invited sectional speaker at the International Congress of Mathematicians. He is an invited IMS Medallion lecturer for the 2020 Bernoulli-IMS World Congress.

Jing Dong

Columbia University

Spectral gap of replica-exchange Langevin diffusion

Slides

Date: August 17, 2020



More info.

Abstract

Langevin diffusion (LD) is one of the main workhorses for sampling problems. However, its convergence rate can be significantly reduced if the target distribution is a mixture of multiple densities, each of which concentrates around a different mode. Replica-exchange Langevin diffusion (ReLD) is a sampling method that can circumvent this issue. In particular, ReLD adds another LD sampling a high-temperature version of the target density, and exchange the locations of two LDs according to a Metropolis-Hasting type of law. This approach can be further extended to multiple-replica-exchange Langevin diffusion (mReLD), where K additional LDs are added to sample distributions at different temperatures and exchanges take place between neighboring-temperature processes. While ReLD and mReLD have been used extensively in statistics, molecular dynamics, and other applications, there is little existing analysis on their convergence rate and the choices of temperatures. Our work closes these theoretical gaps assuming the target distribution is a mixture of log-concave densities. We show that ReLD can obtain constant or better convergence rates even when the density components of the mixture concentrate around isolated modes. We also show that using mReLD with K additional LDs can achieve the same convergence rate while the exchange frequency only needs to be (1/K)-th power of the one in ReLD.

This is joint work with Xin T. Tong at the National University of Singapore.

Bio

Jing Dong is an Associate Professor at the Decision, Risk, and Operations Division of Columbia Business School. Her research is at the interface of applied probability and service operations management. She also develops efficient simulation algorithms to facilitate better decision making in complex stochastic systems. She received her Ph.D. in Operations Research from Columbia University. Before joining Columbia Business School, she was an Assistant Professor at Northwestern University.

Mohsen Bayati

Stanford University

On Worst-Case Regret of Thompson Sampling and a General Framework to Analyze Linear Bandit

Slides

Date: August 24, 2020



More info.

Abstract

Multi-armed bandit (MAB) experiments have recently received significant attention in data-centric enterprises, given their promise in reducing opportunity cost of experimentation. In this talk we consider the well-known stochastic linear bandit problem which includes (as special case) standard MAB experiments and their personalized (contextual) counterpart. In this setting a decision-maker sequentially chooses among a set of given actions in Rd, observes their noisy reward, and aims to maximize her cumulative expected reward over a horizon of length T.

A well-known algorithm for this problem is Linear Thompson Sampling (LinTS) that is shown, by Russo and Van Roy (2014), to achieve the best possible asymptotic reward (i.e., is rate optimal) in the Bayesian setting. However, in the frequentist setting, there is a factor d gap between the minimax lower bound and the best provable upper bound for LinTS. This best upper bound, shown by Agrawal and Goyal (2013), requires the posterior variance to be inflated by a factor d, in each round of LinTS. In this talk we first show that the bound of Agrawal and Goyal (2013) is the best achievable. Specifically, we construct examples to show that, without the inflation, LinTS can incur linear regret. We then demonstrate that, under mild conditions, a slightly modified version of LinTS requires only a constant inflation. Our proof technique involves introducing a unified approach to analyze well-known algorithms such as LinTS, optimism in the face of uncertainty linear bandit (OFUL), and OLS Bandit.

Based on joint work with Nima Hamidi.

Bio

Mohsen Bayati received a B.Sc. degree in Mathematics from Sharif University of Technology in 2000, and an M.Sc. degree in Mathematics, and Ph.D. in Electrical Engineering from Stanford University in 2007. He was a Postdoctoral Researcher at Microsoft Research and at Stanford University during 2007-2011, working mainly on graphical models and high-dimensional statistics with applications in healthcare. Since 2011, he has been a faculty in the Operations, Information, and Technology group at Stanford University Graduate School of Business. He was awarded the INFORMS Healthcare Applications Society best paper (Pierskalla) award in 2014 and in 2016, INFORMS Applied Probability Society best paper award in 2015, and National Science Foundation CAREER award in 2016.

Bert Zwart

CWI and Eindhoven University of Technology, The Netherlands

Why Are Blackout Sizes in Power Grids Heavy-tailed?

Slides

Date: August 31, 2020



More info.

Abstract

Securing a reliable power grid is of tremendous societal importance due to the highly disruptive repercussions of blackouts. Yet, the study of cascading failures in power grids is a notoriously challenging problem due to its sheer size, combinatorial nature, mixed continuous and discrete processes, physics and engineering specifications.

Traditional epidemics models are unsuitable for its study, as the physics of power flow are responsible for a non-local propagation of failures. This challenge has created extensive interest from the engineering and physics communities. Analytic models determining the blackout size ignore the microscopic dynamics of power flow, while the analysis of more realistic networks typically does not go beyond simulation studies. Therefore, a fundamental understanding of blackouts is lacking.

In this work, we model power grids as graphs with heavy-tailed sinks, which represent demand from cities and study cascading failures on such graphs using a DC load flow model. Our analysis links the scale-free nature of blackout sizes to the scale-free nature of city sizes, contrasting previous studies suggesting that this nature is governed by self-organized criticality. Our results are based on a new mathematical framework combining the physics of power flow with rare event analysis for heavy-tailed distributions.

While the blackout size is a discontinuous function of demand in general, it is possible to develop mathematically rigorous tail estimates. These are validated using various synthetic networks, nonlinear load flow models and a case study for the German transmission grid.

Further info can be found on
https://arxiv.org/abs/2007.06967
https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.125.058301
https://physics.aps.org/articles/v13/122


Joint work with Tommaso Nesti (CWI) and Fiona Sloothaak (TU/e).

Bio

Bert Zwart is the leader of the Stochastics group at CWI Amsterdam and professor at the Eindhoven University of Technology. Before that, Bert was at the industrial engineering department of Georgia Tech. Bert has the recipient of the Erlang prize in 2008, the best paper award of the Informs revenue management and pricing section in 2016, and has been area editor at Operations Research until 2017.

A significant part of his current research efforts focuses on understanding rare events in systems with heavy-tailed phenomena, and on the stochastic modeling and analysis of power systems. To this end, Bert co-organized a special semester on the mathematics of energy networks at the Isaac Newton Institute in Cambridge, in 2019.

John Tsitsiklis

Massachusetts Institute of Technology

Excursions of Max-Weight Dynamics

Slides

Date: September 14, 2020



More info.

Abstract

We provide a new perspective into the structural properties of the celebrated max-weight policy, a much studied centerpiece within the field of stochastic network scheduling. We argue that the deterministic max-weight dynamics have a key property: the effects of input (arrival) fluctuations on state trajectories are bounded by a constant multiple of the fluctuations of the cumulative arrival process. This fact, in conjunction with concentration assumptions on the arrival process, provides a new machinery for deriving old and new limiting results, e.g., on fluid limits or state space collapse.

Joint work with A. Sharifnassab and S. J. Golestani.

Bio

John N. Tsitsiklis received the B.S. degree in mathematics and the B.S., M.S., and Ph.D. degrees in electrical engineering from the Massachusetts Institute of Technology (MIT), Cambridge, MA, USA, in 1980, 1980, 1981, and 1984, respectively. His research interests are in systems, optimization, communications, control, and operations research. He has coauthored four books and several journal papers in these areas.

He is currently a Clarence J. Lebel Professor with the Department of Electrical Engineering and Computer Science at MIT, and serves as the director of the Laboratory for Information and Decision Systems. He is a member of the National Academy of Engineering and holds three honorary doctorates. Among other distinctions, he is a recipient of the ACM SIGMETRICS Achievement Award (2016), the IEEE Control Systems Award (2018), and the INFORMS von Neumann Theory Prize (2018).

Richard Combes

Centrale-Supelec, France

Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits

Date: September 21, 2020



More info.

Abstract

We consider combinatorial semi-bandits over a set of arms X∈{0,1}d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = O(d(ln m)2(ln T)/Δmin) after T rounds, where m = maxx (1Tx) . However, ESCB it has computational complexity O(|X|), which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm that is both computationally and statistically efficient for this problem with regret R(T) = O(d(ln m)2(ln T)/Δmin) and computational asymptotic complexity O(δT1poly(d)) where δT is a function which vanishes arbitrarily slowly. Our approach involves carefully designing an approximate version of ESCB with the same regret guarantees, showing that this approximate algorithm can be implemented in time O(poly(d)/δT) by repeatedly maximizing a linear function over X subject to a linear budget constraint, and showing how to solve this maximization problems efficiently.

This is a joint work with Thibaut Cuvelier and Eric Gourdin. More information here https://arxiv.org/abs/2002.07258.

Bio

Richard Combes is currently an assistant professor in Supelec. He received the Engineering Degree from Telecom Paristech (2008), the Master's Degree in Mathematics from University of Paris VII (2009) and the Ph.D. degree in Mathematics from University of Paris VI (2013). He was a visiting scientist at INRIA (2012) and a post-doc in KTH (2013). He received the best paper awards at SIGMETRICS 2019 and CNSM 2011. His current research interests are machine learning, networks and probability.

Ana Bušić

INRIA and ENS, Paris

Optimal Control in Dynamic Matching Systems

Date: September 28, 2020



More info.

Abstract

The theory of matching has a long history in mathematics, economics, and computer science, with applications in many fields. However, most of the research considers the static setting. In recent years, with the increased popularity of online advertising, various online matching models have been proposed that consider random arrivals of one population, while the other is static. In this talk we consider extensions to fully dynamic bipartite matching models, in which both populations arrive according to a stochastic process. This line of work combines classical matching theory with queuing and inventory theory. The main departure from traditional queueing networks is that there is no notion of servers. Instead of ``service'', activities correspond to instantaneous matching of a particular unit of supply with a unit of demand.

We will start by analyzing the FCFS policy in which each is matched to the earliest compatible unmatched item in the system. Then we will consider an infinite-horizon average-cost optimal control problem. A new class of policies is introduced: the h-MaxWeight with threshold. Performance analysis is based on a one-dimensional relaxation of the stochastic control problem, which is found to be a special case of an inventory model from the classical theory of Clark and Scarf. Consequently, the optimal policy for the relaxation admits a closed-form expression based on a threshold rule. These observations inform the choice of function h, taken to be a perturbation of the cost function, and the choice of threshold. For a parameterized family of models in which the network load approaches capacity, this policy is shown to be approximately optimal, with bounded regret, even though the average cost grows without bound.

Based on joint papers with: Ivo Adan, Arnaud Cadas, Josu Doncel, Jean-Michel Fourneau, Jean Mairesse, Sean Meyn, Pascal Moyal, and Gideon Weiss.

Bio

Ana Bušić is a Research Scientist at Inria Paris and in the Computer Science Department at École Normale Supérieure, PSL University, CNRS, Paris, France. She is a member of the Laboratory of Information, Networking and Communication Sciences (LINCS). She received a M.S. degree in Mathematics in 2003, and a Ph.D. degree in Computer Science in 2007, both from the University of Versailles. She was previously a post-doctoral fellow at Inria Grenoble Rhone-Alpes and at University Paris Diderot-Paris 7. She was a recipient of the 2015 Google Faculty Research Award. Her research interests include stochastic modeling, reinforcement learning, simulation, and performance evaluation, with applications to networks and power systems.

Balaji Prabhakar

Stanford University

CloudEx: Using Accurate Clocks to Build a Financial Exchange in the Cloud

Date: October 12, 2020



More info.

Abstract

Electronic trading exchanges are required to provide "fair access". This means a trader's order cannot be overtaken by another trader's order (thus, orders have to be processed in a globally FIFO manner), and no trader should receive market data before any other trader. Currently, exchanges meet these requirements using carefully-engineered, bespoke data networks, limiting their scale and scope.

In this talk we show that accurate clock synchronization deployed at scale can transform an unpredictable market into a nearly perfect FIFO machine, even if the market is built upon extremely jittery infrastructure such as the public cloud. This would not only allow exchanges to scale but it would also significantly reduce the cost of participation, thereby democratizing financial trading.

We describe the clock synchronization algorithm, Huygens, and present some of its mathematical properties. We will also describe CloudEx, an exchange built on top of a public cloud. We aim to run CloudEx in a Computer Science course offered in Spring 2020, with students writing HFT programs and becoming "traders". Thus, CloudEx has the potential to be a testbed for trying out a variety of matching algorithms.

Bio

Balaji Prabhakar is VMware Founders Professor of Computer Science, Electrical Engineering and, by courtesy, in the Graduate School of Business, Stanford University. Balaji’s research interests are in computer networks; notably, data centers and cloud computing. From 2008 to 2016 he worked on Societal Networks: networks vital for society's functioning, such as transportation, electricity and recycling systems. He led the development and deployment of "nudge engines" for transportation systems (notably, Singapore mass transit and the Bay Area Rapid Transit (BART)), wellness programs, and corporate learning programs. Based on this work, he co-founded Urban Engines, a startup which was acquired by Google in 2016.

Balaji has received the NSF CAREER Award, the Erlang Prize from the INFORMS Applied Probability Society, the Rollo Davidson Prize from the University of Cambridge and delivered the Lunteren Lectures of the Dutch Operations Research Society. He is a Fellow of the IEEE, the ACM and the Alfred P. Sloan Foundation. He has received the inaugural IEEE Innovation in Societal Infrastructure Award for his work on Societal Networks, and the IEEE Koji Kobayashi Award for his work on Computer Communications. He has served on the Advisory Board of the Future Urban Mobility Initiative of the World Economic Forum.

Peter Glynn

Stanford University

Poisson’s Equation: Three Applications

Date: October 19, 2020



More info.

Abstract

Poisson’s equation plays a key role in the equilibrium analysis of Markov chains and Markov processes. In this talk, we will describe three recent applications of Poisson’s equation. In the first application, we discuss how Poisson’s equation can be applied to compute expectations associated with boundary functionals of a Markov process subject to reflection. We will then discuss how Poisson’s equation arises in the setting of sensitivity analysis for Markov chains. In our last application, Poisson’s equation plays a key role in the asymptotic analysis of a non-parametric MLE arising in adaptive experimental design.

This work is joint with Ramesh Johari, Mohammad Rasouli, Chang-Han Rhee, and Rob Wang.

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 received his Ph.D in Operations Research from Stanford University in 1982. He then joined the faculty of the University of Wisconsin at Madison, where he held a joint appointment between the Industrial Engineering Department and Mathematics Research Center, and courtesy appointments in Computer Science and Mathematics. In 1987, he returned to Stanford, where he joined the Department of Operations Research. From 1999 to 2005, he served as Deputy Chair of the Department of Management Science and Engineering, and was Director of Stanford's Institute for Computational and Mathematical Engineering from 2006 until 2010. He 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 will give 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.

Sujay Sanghavi

University of Texas at Austin

Towards Model Agnostic Robustness

Date: October 26, 2020



More info.

Abstract

It is now common practice to try and solve machine learning problems by starting with a complex existing model or architecture, and fine-tuning/adapting it to the task at hand. However, outliers, errors or even just sloppiness in training data often lead to drastic drops in performance.

We investigate a simple generic approach to correct for this, motivated by a classic statistical idea: trimmed loss. This advocates jointly (a) selecting which training samples to ignore, and (b) fitting a model on the remaining samples. As such this is computationally infeasible even for linear regression. We propose and study the natural iterative variant that alternates between these two steps (a) and (b) - each of which individually can be easily accomplished in pretty much any statistical setting. We also study the batch-SGD variant of this idea. We demonstrate both theoretically (for generalized linear models) and empirically (for moderate-sized neural network models) that this effectively recovers accuracy in the presence of bad training data.

This work is joint with Yanyao Shen and Vatsal Shah and appears in NeurIPS 2019, ICML 2019 and AISTATS 2020.

Bio

Sujay Sanghavi is an Associate Professor at the University of Texas, Austin. He received a PhD in ECE and an MS in Math and ECE from the University of Illinois, and was a postdoc at LIDS in MIT. Sujay’s research focus is rigorous methodological innovation in machine learning, using ideas from optimization, statistics and graph theory. He has received early career awards from the NSF and DoD, and currently leads the NSF TRIPODS Institute on the Foundations of Data Science at UT.

Sujay is also interested in learning from and applying his ideas in industry. He has been a Visiting Scientist at Google Research, a senior quant at Engineers Gate and is currently a Principal Research Scientist and Amazon Scholar at Amazon.

Sem Borst (Markov Lecture)

Eindhoven University of Technology, The Netherlands

Discussant: Neil Walton

Load Balancing in Networked Systems: Scalable Algorithms and Resource Pooling Issues

Slides (Markov Lecture)
Slides (Discussion)

Date: November 9, 2020

More info.

Abstract

Load balancing algorithms play a crucial role in distributing service requests in large-scale parallel-resource systems such as data centers and cloud networks. Due to the massive size of these systems, implementation complexity of load balancing algorithms has emerged as a critical concern besides conventional performance metrics such as delay. In the first part of the talk we explore fundamental trade-offs between these two criteria in the baseline scenario of the celebrated supermarket model. We establish asymptotic universality properties for a broad class of randomized algorithms, and discuss some related resource pooling perspectives.

In the second part of the talk we move beyond the supermarket model, and turn to network settings and multi-class systems with compatibility constraints. These scenarios may arise due to heterogeneity issues and network topology and locality constraints which are increasingly common in data centers and cloud environments. We identify conditions in terms of the underlying compatibility graph in order for similar universality properties to hold in a many-server scenario, and leverage product-form distributions for related redundancy models to demonstrate resource pooling a heavy-traffic regime. Strikingly, across a wise range of scenarios, the performance of a fully flexible system can be matched even with quite stringent compatibility constraints.

Note: Based on joint work with Ellen Cardinaels, Johan van Leeuwaarden, Debankur Mukherjee (Georgia Tech) and Phil Whiting (Macquarie)

Bio

Sem Borst has been a Full Professor in Stochastic Operations Research in the Department of Mathematics & Computer Science at Eindhoven University of Technology (TU/e) since 1998. He also had a (part-time) position in the Mathematics of Systems research department at Bell Laboratories in Murray Hill, USA, from 1995 to 2019, and was a Senior Researcher at the Center for Mathematics & Computer Science (CWI) in Amsterdam from 1998 to 2006. During the fall of 1994, he was a visiting scholar at the Statistical Laboratory of the University of Cambridge, England. His main research interests are in the area of performance evaluation and resource allocation algorithms for large-scale stochastic networks, in particular computer-communication systems.

Sem was (co-)recipient of the best-paper awards at SIGMETRICS/Performance 1992 and IEEE Infocom 2003, the 2001 Yosef Levy Prize, the 2005 Van Dantzig Prize, and the 2017 ACM SIGMETRICS Achievement Award. He serves or has served on the editorial boards of several journals, such as ACM Transactions on Modeling and Performance of Computing Systems, IEEE/ACM Transactions on Networking, Operations Research, Queueing Systems and Stochastic Models, and has been a program committee member of numerous conferences.

Ramesh Johari

Stanford University

Interference in Experimental Design in Online Platforms

Date: November 16, 2020



More info.

Abstract

Many experiments ("A/B tests") in online platforms exhibit interference, where an intervention applied to one market participant influences the behavior of another participant. This interference can lead to biased estimates of the treatment effect of the intervention.

In this talk we first focus on such experiments in two-sided platforms where "customers" book "listings". We develop a stochastic market model and associated mean field limit to capture dynamics in such experiments, and use our model to investigate how the performance of different designs and estimators is affected by marketplace interference effects. Platforms typically use two common experimental designs: demand-side ("customer") randomization (CR) and supply-side ("listing") randomization (LR), along with their associated estimators. We show that good experimental design depends on market balance: in highly demand-constrained markets, CR is unbiased, while LR is biased; conversely, in highly supply-constrained markets, LR is unbiased, while CR is biased. We also introduce and study a novel experimental design based on two-sided randomization (TSR) where both customers and listings are randomized to treatment and control. We show that appropriate choices of TSR designs can be unbiased in both extremes of market balance, while yielding relatively low bias in intermediate regimes of market balance. (This is based on joint work with Hannah Li, Inessa Liskovich, and Gabriel Weintraub.)

Time permitting, we will conclude the talk with some discussion of other experimental designs used by online platforms to address interference, including adaptive designs such as switchback experiments, and clustered experimental designs. The goal is to provide an overview of some of the open challenges that arise in this domain. (This part of the talk is based in part on joint work with Peter Glynn and Mohammad Rasouli, previously presented in the SNAPP seminar by Peter Glynn.)

Bio

Ramesh Johari is a Professor at Stanford University, with a full-time appointment in the Department of Management Science and Engineering (MS&E), and courtesy appointments in the Departments of Computer Science (CS) and Electrical Engineering (EE). He is a member of the Operations Research group and the Social Algorithms Lab (SOAL) in MS&E, the Information Systems Laboratory in EE, and the Institute for Computational and Mathematical Engineering. He is also an Associate Director of Stanford Data Science. He received an A.B. in Mathematics from Harvard, a Certificate of Advanced Study in Mathematics from Cambridge, and a Ph.D. in Electrical Engineering and Computer Science from MIT. He served as co-chair of the ACM Economics and Computation (EC) program committee in 2019, and he is an Area Co-Editor of the Revenue Management and Market Analytics Area for Operations Research, and associate editor for Management Science (in the Stochastic Models and Simulation area) and Stochastic Systems. His research interests are in online platform and marketplace design, experimentation and data science for online platforms, and (more recently) application of these techniques to personalized health care via telemedicine.

Ashia Wilson

Microsoft Research New England


Variational Perspectives on Machine Learning: Algorithms, Inference, and Fairness

Date: November 23, 2020



More info.

Abstract

Many experiments ("A/B tests") in online platforms exhibit interference, where an intervention applied to one market participant influences the behavior of another participant. This interference can lead to biased estimates of the treatment effect of the intervention.

In this talk we first focus on such experiments in two-sided platforms where "customers" book "listings". We develop a stochastic market model and associated mean field limit to capture dynamics in such experiments, and use our model to investigate how the performance of different designs and estimators is affected by marketplace interference effects. Platforms typically use two common experimental designs: demand-side ("customer") randomization (CR) and supply-side ("listing") randomization (LR), along with their associated estimators. We show that good experimental design depends on market balance: in highly demand-constrained markets, CR is unbiased, while LR is biased; conversely, in highly supply-constrained markets, LR is unbiased, while CR is biased. We also introduce and study a novel experimental design based on two-sided randomization (TSR) where both customers and listings are randomized to treatment and control. We show that appropriate choices of TSR designs can be unbiased in both extremes of market balance, while yielding relatively low bias in intermediate regimes of market balance. (This is based on joint work with Hannah Li, Inessa Liskovich, and Gabriel Weintraub.)

Time permitting, we will conclude the talk with some discussion of other experimental designs used by online platforms to address interference, including adaptive designs such as switchback experiments, and clustered experimental designs. The goal is to provide an overview of some of the open challenges that arise in this domain. (This part of the talk is based in part on joint work with Peter Glynn and Mohammad Rasouli, previously presented in the SNAPP seminar by Peter Glynn.)

Bio

Ramesh Johari is a Professor at Stanford University, with a full-time appointment in the Department of Management Science and Engineering (MS&E), and courtesy appointments in the Departments of Computer Science (CS) and Electrical Engineering (EE). He is a member of the Operations Research group and the Social Algorithms Lab (SOAL) in MS&E, the Information Systems Laboratory in EE, and the Institute for Computational and Mathematical Engineering. He is also an Associate Director of Stanford Data Science. He received an A.B. in Mathematics from Harvard, a Certificate of Advanced Study in Mathematics from Cambridge, and a Ph.D. in Electrical Engineering and Computer Science from MIT. He served as co-chair of the ACM Economics and Computation (EC) program committee in 2019, and he is an Area Co-Editor of the Revenue Management and Market Analytics Area for Operations Research, and associate editor for Management Science (in the Stochastic Models and Simulation area) and Stochastic Systems. His research interests are in online platform and marketplace design, experimentation and data science for online platforms, and (more recently) application of these techniques to personalized health care via telemedicine.