You are here

Speakers and Abstracts

Mor Harchol-Balter, CMU

SOAP: One Clean Analysis of All Age-Based Scheduling Policies
 

Analyzing the response time of scheduling policies in the M/G/1 setting has been the focus of thousands of papers over the past half century. Typically, each scheduling policy requires a custom response time analysis that takes into account its particular combination of features. Furthermore, results are limited to a relatively small number of simple scheduling policies. This talk introduces the SOAP class: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in the literature as well as an infinite number of variants which have never been analyzed, or maybe even conceived. SOAP policies include the highly intractable SERPT policy (Shortest-Expected-Remaining-Processing-Time), as well as the famously complex Gittins Index policy. SOAP also includes all sorts of "combination" policies, like a policy that performs SRPT on jobs with known size and FB on jobs with unknown size, or a policy that is allowed to preempt jobs only when they hit certain ages. In this talk we present an algorithm for deriving the Laplace transform of response time for all SOAP policies via a single universal framework.

 

Joint work with Ziv Scully and Alan Scheller-Wolf

Munther Dahleh, MIT

A Marketplace for Data: An Algorithmic Solution

 

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.

Jeff Fessler, Univ of Michigan at Ann Arbor

Inverse problem regularization using adaptive signal models
 

Inverse problems are usually ill-conditioned or ill-posed, meaning that there are multiple candidate solutions that all fit the measured data equally or reasonably well. Modeling assumptions are needed to distinguish among candidate solutions. This talk will focus on contemporary adaptive signal models and their use as regularizers for solving inverse problems. The terms "deep" and "convolutional" might be mentioned somewhere. Applications illustrated will include MRI and CT.

 

Joint work with Sai Ravishankar, Il Yong Chung, and Raj Nadakuditi, among others.

Bruce Hajek, UIUC

On Community Detection in Preferential Attachment Networks
 

An extensive theory of community detection has developed within the past few years. The goal is to discover clusters of vertices in a graph based on the edges of the graph. Much work has focused on evaluation of algorithms for a particular generative model, namely, the stochastic block model. The stochastic block model is a variant of Erdos-Renyi type graph, such that, conditioned on the community memberships of the vertices, edges are drawn or not drawn between different pairs of vertices independently. This talk discusses instead the problem of community detection the Barabasi-Albert preferential attachment model with communities. In the preferential attachment model, vertices are sequentially attached to the graph, with preference to attach more edges to existing vertices with larger degrees. The resulting graphs have heavy-tail degree distribution, as observed in many data sets.

 

Based on joint work with Suryanarayana Sankagiri.

Babak Hassibi, CalTech

Stochastic- Gradient and Mirror Descent: Minimax Optimality and Self-Regularization

 

Stochastic descent methods (of the gradient and mirror varieties) have become extremely popular in optimization and, especially, in deep learning. In an attempt to shed some light on why this is the case, we shall revisit some minimax properties of stochastic gradient descent for linear regression---originally developed in the 1990's---and extend them to stochastic mirror descent. These minimax properties can be used to explain the self-regularization behavior of the algorithms when the linear regression problem is over-parametrized. In the nonlinear setting, exemplified by training a deep neural network, we show that when the setup is "highly over-parametrized", stochastic descent methods have similar minimax optimality and self-regularization properties. This observation gives some insight into why deep networks exhibit such powerful generalization abilities. We shall also make connections to online learning.

Ramesh Johari, Stanford University

Bandit Learning with Positive Externalities

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 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.
 

Alon Orlitsky, UCSD

From two to all: Optimal Maxing, Ranking, and Preference Learning

 

Maximum selection (maxing) of n objects using n-1 pairwise comparisons, and sorting (ranking) using O(n log n) pairwise comparisons are algorithmic staples taught in most introductory classes and used in a myriad of applications. Recent preference-learning research has brought about renewed interest in these problems, where the pairwise comparisons are noisy. Yet even for the simplest comparison models, such as Plackett-Luce, the complexity of maxing and ranking was known only to a log n factor. We describe a simple comparison hierarchy that determines the complexity of the two problems to a constant factor in nearly all cases. We conclude with a helpful 1-d jigsaw puzzle, and a bonus omnibus. Joint work with Moein Falahatgar, Yi Hao, Ayush Jain, Venkatadheeraj Pichapati, Vaishakh Ravindrakumar, and Ananda Theertha Suresh.

R. Srikant, UIUC

On the Loss Surface of Neural Networks for Binary Classification


Deep neural networks used for classification problems are trained so that their parameters achieve a local minimum of an appropriate loss function. The loss function is typically intended to approximate the classification error in training samples. In this talk, we will show that approximations of widely-used neural network architectures have the property that every local minimum of a surrogate loss function is a global minimum, and further achieves the global minimum of the training error. Joint work with Shiyu Liang, Ruoyu Sun, and Jason Lee.
 

Wojciech Szpankowski, Purdue University

Structural and Temporal Information

 

F. Brooks argued in his 2003 JACM paper on the challenges of computer sciences that there is ``no theory that gives us a metric for the information embodied in structure''.  More generally, we lack an information theory of data structures (e.g., graphs, sets, social networks, chemical structures, biological networks). Similarly, temporal information was largely ignored in the original Shannon information theory. In this talk, we present some recent results on structural and temporal information.  We start with a motivating example where we show how to extract temporal information (arrival of nodes)  in dynamic networks from its structure (unlabeled graphs). We then proceed to propose some fundamental limits of information content for a wide range of data structure, and asymptotically optimal lossless compression algorithms achieving these limits for various graph models.

Eva Tardos, Cornell University

Learning in Games with Dynamic Population

Selfish behavior can often lead to suboptimal outcome for all participants. This is especially true in dynamically changing environments where the game or the set of the participants can change at any time without even the players realizing it. Over the last decade we have developed good understanding how to quantify the impact of strategic user behavior on overall performance via studying stable Nash equilibria of the games. In this talk we will consider the quality of outcomes in games when the population of players is dynamically changing, and where participants have to adapt to the dynamic environment. We show that in large classes of games (including traffic routing), if players use a form of learning that helps them to adapt to the changing environment, this guarantees high social welfare, even under very frequent changes. Joint work with Thodoris Lykouris and Vasilis Syrgkanis.

 Lang Tong, Cornell University

Reversing death spiral: the stability and limiting capacity of solar adoption
 

The death spiral hypothesis in electric utilities points to a positive feedback phenomenon in which a regulated utility is driven to financial instability by rising prices and declining demand. In this talk, we present a nonlinear dynamical system model that characterizes the dynamics of distributed energy resources (DER) and the impact of retail tariff on the stability of adoption. In particular, we present conditions for the existence of death spiral, the stability of the adoption process, and the limiting capacity of DER adoption.

David Tse, Stanford University

Understanding Generative Adversarial Networks
 

Generative Adversarial Networks (GANs) are a novel approach to the age-old problem of learning a probability model from data. Many GAN architectures with different optimization metrics have been introduced recently. To understand the many design and analysis issues surrounding GANs , we ask a basic question: what is a natural GAN architecture to learn a high-dimensional Gaussian distribution? Answering that question leads to an exploration of several fascinating issues, such as the connection between supervised and unsupervised learning, the generalizability of GANs and the stability of their training.

Adam Wierman, CalTech

Transparency and Control in Platforms & Networked Markets


Platforms have emerged as a powerful economic force, driving both traditional markets, like the electricity market, and emerging markets, like the sharing economy.  The power of platforms comes from their ability to tame the complexities of networked marketplaces -- marketplaces where there is not a single centralized market, but instead a network of interconnected markets loosely defined by a graph of feasible exchanges. Despite the power and prominence of platforms, the workings of platforms are often guarded secrets.  Further, many competing platforms make very different design choices, but little is understood about the impact of these differing choices.  In this talk, I will overview recent work that focuses on reverse engineering the design of platforms and understanding the consequences of design choices underlying transparency in modern platforms.  I will use electricity markets and ridesharing services as motivating examples throughout.

Roy Yates, Rutgers University

The Age of Information: Status Updates for Real-time Systems
 

Increasingly ubiquitous network connectivity has engendered applications in which sources send updates of their status to interested recipients. These applications require timely status updates at the recipients; however, this is typically constrained by communication and network resources. In this talk, we introduce a status-age timeliness metric for the evaluation of status update systems. We develop general methods for calculating the age metric that we apply to network models of sources and service facilities. We characterize optimal updating rates and policies based on the communication constraints of the senders and systems.