Yoram Bresler

University of Illinois, Urbana-Champaign

Guaranteed Multichannel Sparse Blind Deconvolution Under Minimal Modeling Assumptions

Multichannel blind deconvolution (MBD) is the problem of recovering an unknown signal and multiple unknown channels from their circular convolution. It arises in blind image deblurring, blind channel equalization, speech dereverberation, and seismic data analysis. It is also related to blind gain and phase calibration in sensor array processing with miscalibrated arrays. MBD is an ill-posed bilinear inverse problem, that does not admit a unique solution without further constraints. We consider the case where the channels are sparse, which is of significant practical interest. Formulating the joint channel and signal recovery problem as a nonconvex optimization problem on the unit sphere, we show that all local minima of the objective function correspond to the global optimum, and all saddle points have strictly negative curvatures. This friendly geometric landscape allows successful recovery using a simple manifold gradient descent algorithm. This is the first guaranteed algorithm for this problem that does not rely on restrictive assumptions on the signal or sparse channels.
 

Robert Calderbank

Duke University

Recent Progress in Quantum Computing

Quantum computers promise to be more capable than any classical computer at solving certain problems, and are now becoming generally programmable. This talk will describe how we approach the problem of building a "quantum compiler" that is able to generate short depth physical circuits.
 

Joao Hespanha

University of California Santa Barbara 

P. R. Kumar

Texas A&M University

Security of Cyberphysical Systems

The coming decades may see the large scale deployment of networked cyber–physical systems to address global needs in areas such as energy, water, health care, and transportation. However, as recent events have shown, such systems are vulnerable to cyber attacks. We begin by revisiting classical linear systems theory, developed in more innocent times, from a security-conscious, even paranoid, viewpoint. Then we present a general technique, called "dynamic watermarking," for detecting any sort of malicious activity in networked systems of sensors and actuators. We present experimental demonstration of this technique on laboratory versions of a prototypical intelligent transportation system and a process control system, and a simulation study of defense against an attack on Automatic Gain Control (AGC) in a synthetic four area power system. [Joint work with Bharadwaj Satchidanandan, Jaewon Kim, Woo Hyun Ko, Le Xie and Tong Huang].
 

Jane Macfarlane

University of California at Berkeley and Lawrence Berkeley National Laboratory

High Performance Computing Solutions for Real-World Transportation Systems Understanding

Increasing populations, new modes of on-demand transportation and changing demand patterns for goods deliveries in our cities is crippling our transportation infrastructure. In 2018, the US had three cities in the top five congested cities in the world - which accounts for a collective economic cost of $62B for just these three cities. The additional energy use associated with this congestion contributes to a growing consumption of fossil fuel. Designing transportation solutions for real-world urban scale systems has mostly been accomplished with very limited analytics because of the very complex dynamics and interacting constraints that effect this flow of goods and travelers. Traffic assignment models and simulation are the traditional tools that city planners use, however, the computational scale mediates the effectiveness of these tools. Planners are forced to reduce the complexity of the problem (eg. create smaller networks, or aggregate and reduce demand models) to be able to run the tool in a reasonable time. New large-scale computational capabilities (e.g. cloud computing and supercomputing), data analytics (e.g machine learning and intelligent data compression) and modeling (e.g. dynamic traffic assignment and agent-based modeling) that scales in both time and space are now possible. By combining massive amounts of data from real-world sensors and very large road network models, both closed form analytics and emergent behaviors from large scale agent models can be used to build our understanding of urban scale problems. This discussion will focus on the real-world issues of handling geospatial data at scale, the data veracity issues and intelligent data compression opportunities and the use of large-scale computing to address urban scale dynamic models that can be used to examine emergent behavior under a variety of conditions.

Upamanyu Madhow

University of California Santa Barbara

Can signal models inform deep learning? Two case studies

Deep neural networks (DNNs) have become the state of the art for learning and inference in a diversity of fields, including computer vision, speech recognition, and natural language processing. A particular strength of DNNs is that, once the input is translated to a tensor, explicit feature engineering based on domain knowledge is not required. We argue in this talk, however, that application-specific signal models can be crucial as we apply DNNs to safety- and security-critical domains. We present preliminary results from two case studies. In the first, we discuss the problem of combating adversarial perturbations by invoking a rather general signal model, corresponding to the assumption that the input data lies in a low-dimensional manifold embedded in a high-dimensional space. In the second, we consider the problem of using DNNs to extract radio frequency (RF) signatures that enable identification of transmitters in a manner robust to simple spoofing techniques (e.g., message, ID, carrier offset). We show how protocol- and channel-aware signal modeling is important in preventing the unreasonably good accuracy associated with vulnerability to such spoofing.

Muriel Medard
Massachusetts Institute of Technology
 

Guessing Random Additive Noise Decoding (GRAND)
 

We introduce a new algorithm for Maximum Likelihood (ML) decoding based on guessing noise. The algorithm is based on the principle that the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in an element of the code-book is the ML decoding. For common additive noise channels, we establish that the algorithm is capacity achieving for uniformly selected code-books, providing an intuitive alternate approach to the channel coding theorem. When the code-book rate is less than capacity, we identify exact asymptotic error exponents as the block-length becomes large. We illustrate the practical usefulness of our approach in terms of speeding up decoding for existing codes. Joint work with Ken Duffy, Kishori Konwar, Jiange Li, Prakash Narayana Moorthy, Amit Solomon.

George J. Pappas

University of Pennsylvania

Robustness Analysis of Neural Networks via Semidefinite Programming
 

Deep neural networks have dramatically impacted machine learning problems in numerous fields. Despite these major advances, neural networks are not robust and hence not suitable for safety-critical applications. In this lecture, we will present a novel framework for analyzing the robustness of deep neural networks against norm-bounded nonlinearities. In particular, we develop a semidefinite programming (SDP) framework for safety verification and robustness analysis of neural networks with general activation functions. Our main idea is to abstract various properties of activation functions (e.g., monotonicity, bounded slope, bounded values, and repetition across layers) with the formalism of quadratic constraints. We then analyze the safety properties of the abstracted network via the S-procedure and semidefinite programming. Compared to other approaches proposed in the literature, our method is less conservative, especially for deep networks, with an order of magnitude reduction in computational complexity. Furthermore, our approach is applicable to any activation functions. Such bounds are very important in analyzing the safety of control systems regulated by neural networks.

Yannis Paschalidis

Boston University

Distributionally Robust Learning with Applications to Health Analytics

We will present a distributionally robust optimization approach to learning predictive models, using general loss functions that can be used either in the context of classification or regression. Motivated by medical applications, we assume that training data are contaminated with (unknown) outliers. The learning problem is formulated as the problem of minimizing the worst case expected loss over a family of distributions within a certain Wasserstein ball centered at the empirical distribution obtained from the training data. We will explore the generality of this approach, its robustness properties, its ability to explain a host of "ad-hoc" regularized learning methods, and we will establish rigorous out-of-sample performance guarantees. Beyond predictions, we will discuss methods that can leverage the robust predictive models to make decisions and offer specific personalized prescriptions and recommendations to improve future outcomes. We will provide some examples of medical applications of our methods, including predicting hospitalizations for chronic disease patients, predicting hospital length-of-stay for surgical patients, and making treatment recommendations for diabetes and hypertension. (joint work with Ruidi Chen)

H. Vincent Poor

Princeton University

Sanjay Shakkottai

University of Texas at Austin

Multi-Fidelity Tree-Search for Hyper-parameter Tuning

We study the application of online learning techniques in the context of hyper-parameter tuning, which is of growing importance in general machine learning. Modern neural networks have several tunable parameters, where training for even one such parameter configuration can take several hours to days. We first cast hyper-parameter tuning as optimizing a multi-fidelity black-box function (which is noise-less) and propose a multi-fidelity tree search algorithm for the same. We then present extensions of our model and algorithm, so that they can function even in the presence of noise. We show that our tree-search based algorithms can outperform state of the art hyper-parameter tuning algorithms on several benchmark data-sets.

Venu Veeravalli

University of Illinois at Urbana-Champaign

Quickest Detection of Dynamic Events in Networks

We study the problem of efficiently detecting a dynamically evolving event using a sensor network. At some unknown time, an event occurs, and a subset of nodes in the network are affected, which undergo a change in the statistics of their observations. It is assumed that the event propagates dynamically along the edges in the network, in that the affected nodes form a connected subgraph. The event propagation dynamics are assumed to be unknown. The goal is to design a sequential algorithm that can detect a ``significant" event, i.e., when the event has affected a large enough number of nodes, as quickly as possible, while controlling the false alarm rate. We construct computationally efficient algorithms for this problem, for both structured and unstructured networks, and establish their first-order asymptotically optimality as the false alarm rate goes to zero. We end with a discussion of distributed approaches to implementing the algorithms.

Qing Zhao

Cornell University

Active Learning on a Tree
 

The problem of detecting a few target processes with abnormally high mean values among a large number of processes is considered. Each process is i.i.d. with an unknown distribution. Processes follow a tree-structured hierarchy, which encodes the following relationship: the abnormal mean of a target propagates through all ancestors of the target on the tree. The objective is an active learning strategy that determines, sequentially, which node on the tree to sample and when to terminate the search in order to detect all targets with a minimum sample complexity under a reliability constraint. A strategy that induces a biased random walk on the tree based on confidence bounds of sample statistics is proposed and shown to be order optimal in terms of both the size of the tree and the reliability requirement. The results find applications in hierarchical heavy hitter detection, noisy group testing, stochastic online convex optimization, and adaptive sampling for classification and stochastic root finding.