You are here
 Home >
 Previous Workshop >
 Program of IMACCS 2018 >
 Abstract of IMACCS 2018
Speakers and Abstracts
Mor HarcholBalter, CMU 
SOAP: One Clean Analysis of All AgeBased 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 Agebased 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 (ShortestExpectedRemainingProcessingTime), 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 SchellerWolf 
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 highquality 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 realtime (e.g. a rideshare 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 realtime 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 realworld 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 pretrained 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 illconditioned or illposed, 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 ErdosRenyi 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 BarabasiAlbert 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 heavytail 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 SelfRegularization
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 regressionoriginally developed in the 1990'sand extend them to stochastic mirror descent. These minimax properties can be used to explain the selfregularization behavior of the algorithms when the linear regression problem is overparametrized. In the nonlinear setting, exemplified by training a deep neural network, we show that when the setup is "highly overparametrized", stochastic descent methods have similar minimax optimality and selfregularization 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 
Alon Orlitsky, UCSD 
From two to all: Optimal Maxing, Ranking, and Preference Learning
Maximum selection (maxing) of n objects using n1 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 preferencelearning research has brought about renewed interest in these problems, where the pairwise comparisons are noisy. Yet even for the simplest comparison models, such as PlackettLuce, 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 1d 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

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 
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 ageold 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 highdimensional 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

Roy Yates, Rutgers University 
The Age of Information: Status Updates for Realtime 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 statusage 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. 