How to conduct near real-time analytics of streaming data in the smart grid? This talk offers a dynamic systems approach to utilizing emerging data for improved monitoring of the grid. The first example of the talk presents how to leverage the underlying spatio-temporal correlations of synchrophasors for early anomaly (e.g., subsynchronous oscillations) detection, localization, and data quality outlier detection. The second example presents a dynamic systems approach to modeling price responsive demand in real-time energy markets. The underlying theme of the work suggests the importance of integrating data with dynamic physics-based analytics in the context of electric energy systems.

Cyber-physical systems (CPS) integrate computation with physical processes. Examples of CPS include modern automobiles, avionics, medical devices, robots, power systems, sensor networks, and many more. Many of these systems operate in uncertain, evolving, or partially unknown environments, and even so must provide strong assurances of safety and performance. In this talk, I will discuss algorithmic problems arising in the real-time verification and control of cyber-physical systems. In particular, I will talk about the use of temporal logic for specifying desired and undesired behavior of CPS, and the use of online algorithms and optimization for verification and control of temporal logic properties of CPS.

We consider the problem of separating error messages generated in large distributed data center networks into error events. In such networks, each error event leads to a stream of messages generated by all network components affected by the event. These messages are stored in a giant message log, with no information about the associated events. We study the unsupervised learning problem of identifying the signatures of the events that generated these messages; here, the signature of an error event refers to the probability distribution of messages generated by the event. We design a low-complexity algorithm for this purpose, and demonstrate its scalability on a real dataset consisting of 97 million messages collected over a period of 15 days, from a distributed data center network which supports the operations of a large wireless service provider.

Intersections are hazardous places. Threats arise from interactions among pedestrians, bicycles and vehicles; more complicated vehicle trajectories in the absence of lane markings; phases that prevent knowing who has the right of way; invisible vehicle approaches; vehicle obstructions; and illegal move- ments. These challenges are not fully addressed by the “road diet” and road redesign prescribed in Vision Zero plans. Nor will they be completely overcome by autonomous vehicles with their many on-board sensors and tireless attention to sensor readings. Accidents can also occur because drivers, bicyclists and pedestrians do not have the information they need to avoid wrong decisions. In these cases, the missing information can be calculated and communicated by an intelligent intersection. The information gives the current full signal phase, an estimate of the time when the phase will change, the occupancy of the blind spots of the driver or autonomous vehicle, and detection of red-light violators. The talk develops a design of the intelligent intersection, motivated by the analysis of an accident at an intersection in Tempe, AZ, between an automated Uber Volvo and a manual Honda CRV. The intelligent intersection functions as a ‘protected intersection’ using I2V communication.

There is a data type, that we may call "hierarchical log data", which arises across a wide range of societal networks. It consists of event records in a complex structured activity by an agent. Examples: a commuter makes trips, and for each trip there are tap-in and tap-out events recorded; a user sends requests to a web service, and this triggers a cascade of internal requests in a data center each of which is logged; a person engages in a sequence of purchases in order to complete a project and the credit card purchases are all logged.

Hierarchical log data is central to the understanding of societal networks. Yet it has received very little attention, neither in the database community, nor in data science, nor machine learning. I will describe the challenges, share a dataset, and suggest and some ways forward.

The problem is to optimize the appointments of customers with a single server to minimize a combination of idle time, waiting time, and overtime.  We consider static appointments (come at 10:30am) and dynamic appointments (I will warn you one hour before you should come).  The processing times of the customers are random and have unknown distributions. We design learning algorithms for situations where similar processing tasks repeat over time.

Machine Learning and Data Science (ML) is starting to take the place in industry that "Information Technology" had in the late 1990s: businesses of all sizes and in all sectors, are recognizing how necessary it has become to develop predictive capabilities for continued profitability of their core competencies. To be effective, ML algorithms rely on high-quality training data – and not just any data, but data that is specific to the business problem that ML is applied to. Obtaining relevant training data can be very difficult for firms to do themselves, especially those early in their path towards incorporating ML into their operations. This problem is only further exacerbated, as businesses increasingly need to solve these prediction problems in real-time (e.g. a ride-share company setting prices, retailers/restaurants sending targeted coupons to clear inventory), which means that data gets “stale” quickly. Therefore, it is imperative that there are real-time market structures for the buying and selling of training data for ML. Further it is insufficient to view ML performance metrics (e.g. RMSE) in isolation of real-world applications; for example, a 10% increase in prediction accuracy means very different things for a hedge fund maximizing profits vs. a retailer decreasing inventory costs vs. a hospital trying to save lives. Hence the value of a dataset will necessarily have to consider more than simply the prediction accuracy it provides. Domain knowledge will be just as essential, if not more so, if we aim to view data as an asset and create a rigorous method to define its value.

In this work, we aim to create a data marketplace – a robust matching mechanism to efficiently buy and sell data while optimizing social welfare and maximizing revenue. While the monetization of data and pre-trained models is an essential focus by many industries and vendors today, there does not exist a market mechanism that can price data and match suppliers to vendors while still addressing the (computational and other) complexity associated with creating a market platform. The challenge in creating such a marketplace stems from the very nature of data as an asset: (i) it can be replicated at zero marginal cost; (ii) its value to a firm is inherently combinatorial (i.e. the value of a particular dataset depends on what other (potentially correlated) datasets are available); (iii) its value to a firm is dependent on which other firms get access to the same data; (iv) prediction tasks and the value of an increase in prediction accuracy vary widely between different firms, and so it is not obvious how to set prices for a collection of datasets with correlated signals; (v) finally, the authenticity and truthfulness of data is difficult to verify a priori without first applying to a prediction task. Our proposed marketplace will take a holistic view of this problem and provide an algorithmic solution combining concepts from statistical machine learning, economics of data with respect to various application domains, algorithmic market design, and mathematical optimization under uncertainty. We will discuss some examples motivating this work.

This is joint work with Anish Agarwal, Tuhin Sarkar, and Devavrat Shah.

Many modern data-intensive computational prob- lems either require, or benefit from distance or similarity data that adhere to a metric. The algorithms run faster or have better performance guarantees. Unfortunately, in real applications, the data are messy and values are noisy. The distances between the data points are far from satisfying a metric. Indeed, there are a number of different algorithms for finding the closest set of distances to the given ones that also satisfy a metric (sometimes with the extra condition of being Euclidean). These algorithms can have unintended consequences; they can change a large number of the original data points, and alter many other features of the data.

The goal of sparse metric repair is to make as few changes as possible to the original data set or underlying distances so as to ensure the resulting distances satisfy the properties of a metric. In other words, we seek to minimize the sparsity (or the l0 “norm”) of the changes we make to the distances subject to the new distances satisfying a metric. We give three different combinatorial algorithms to repair a metric sparsely. In one setting the algorithm is guaranteed to return the sparsest solution and in the other settings, the algorithms repair the metric. Without prior information, the algorithms run in time proportional to the cube of the number of input data points and, with prior information we can reduce the running time considerably.

I will discuss what happens in a transportation network when travel times are uncertain and users who want to route between their respective sources and destinations are risk-averse.  I'll propose a measure of quantifying how much the degree of risk-aversion degrades the system performance (measured as the total expected delay of all users), separately from the effect of selfish routing choices of the users. I will conclude with the effect of user diversity on the quality of the resulting traffic equilibria, and specifically when diversity of user preferences improves outcomes in selfish routing.

Many platforms are characterized by the fact that future user arrivals are likely to have preferences similar to users who were satisfied in the past. In other words, arrivals exhibit {\em positive externalities}. We study multiarmed bandit (MAB) problems with positive externalities. Our model has a finite number of arms and users are distinguished by the arm(s) they prefer. We model positive externalities by assuming that the preferred arms of future arrivals are self-reinforcing based on the experiences of past users. We show that classical algorithms such as UCB which are optimal in the classical MAB setting may even exhibit linear regret in the context of positive externalities. We provide an algorithm which achieves optimal regret and show that such optimal regret exhibits substantially different structure from that observed in the standard MAB setting.

Joint work with Virag Shah and Jose Blanchet.

Ridesharing services have had a profound impact on transportation throughout the world and are poised to have an even greater impact in the future with the advent of self-driving cars. Ridesharing represents not only a technological innovation in transportation but also an economic innovation in how transportation is priced. In this talk, we examine the market design innovations in ridesharing and discuss pricing challenges for the industry as it matures.

The dispatch problems is a critical primitive of ridesharing systems: upon receiving a ride request, the platform must choose a nearby car to serve the ride, while ensuring that it maximizes vehicle availability in the future. The problem has close connections to optimal control of stochastic processing networks, as well as to online stochastic bipartite-matching and the k-server problems. I will talk about some recent work where we developed new state-independent and state-dependent control policies for this problem, with strong approximation guarantees. These results are based on using ideas from product-form Markov chains and large-deviations theory; I will briefly describe these new techniques, and outline some open questions and potential connections with other online decision problems.

Joint work with Daniel Freund and Thodoris Lykouris, and Yash Kanoria and Pengyu Qian.

The theory of matching has a long history in economics, mathematics, and graph theory, with applications in many other 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 are given by 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. One of the most compelling applications is kidney paired donation by United Network for Organ Sharing.
We will present recent results for 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 relaxation of the stochastic control problem will be discussed, which is found to be a special case of an inventory model, as treated in the classical theory of Clark and Scarf. The optimal policy for the relaxation admits a closed-form expression. Based on the policy for this relaxation, we propose a new matching policy. 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.

For decades power systems academics have proclaimed the need for real time prices to create a more efficient grid.   The rationale is economics 101:   proper price signals will lead to an efficient outcome.

In this talk we will review a bit of economics 101;  in particular, the definition of efficiency.   We will see that the theory supports the real-time price paradigm, provided we impose a particular model of rationality.    It is argued however that this standard model of consumer utility does not match reality:   the products of interest to the various "agents" are complex functions of time.  The product of interest to a typical consumer is only loosely related to electric power -- the quantity associated with price signals.

There is good news:  an efficient outcome is easy to describe, and we have the control technology to achieve it.  We need supporting market designs that respect dynamics and the impact of fixed costs that are inherent in power systems engineering, recognizing that we need incentives on many time-scales.   Most likely the needed economic theory will be based on an emerging theory of efficient and robust contract design.