Information Systems Lab (ISL) Colloquium

ISL Colloquium presents "Learn to Communicate - Communicate to Learn"

Topic: 
Learn to Communicate - Communicate to Learn
Abstract / Description: 

Machine learning and communications are intrinsically connected. The fundamental problem of communications, as stated by Shannon, "reproducing at one point either exactly or approximately a message selected at another point," can be considered as a classification problem. With this connection in mind, I will focus on the fundamental joint source-channel coding problem using modern machine learning techniques. I will introduce uncoded "analog" schemes for wireless image transmission, and show their surprising performance both through simulations and practical implementation. This result will be used to motivate unsupervised learning techniques for wireless image transmission, leading to a "deep joint source-channel encoder" architecture, which behaves similarly to analog transmission, and not only improves upon state-of-the-art digital schemes, but also achieves graceful degradation with channel quality, and performs exceptionally well over fading channels despite not utilizing explicit pilot signals or channel state estimation.

In the second part of the talk, I will focus on distributed machine learning, particularly targeting wireless edge networks, and show that ideas from coding and communication theories can help improve their performance. Finally, I will introduce the novel concept of "over-the-air stochastic gradient descent" for wireless edge learning, and show that it significantly improves the efficiency of machine learning across bandwidth and power limited wireless devices compared to the standard digital approach that separates computation and communication. This will close the circle, making another strong case for analog communication in future communication systems.

Date and Time: 
Thursday, March 14, 2019 - 4:15pm
Venue: 
Packard 101

ISL Colloquium presents "Sensing the World Wirelessly: Perception in the Age of IoT"

Topic: 
Sensing the World Wirelessly: Perception in the Age of IoT
Abstract / Description: 

The success of wireless and mobile systems has led to a digital infrastructure that is integrated into the fabric of the physical world at a scale unimaginable two decades ago. This has come to be known as the internet of things, or the IoT. Batteryless devices constitute the largest component of this infrastructure, as they are attached to clothing, food, drugs, and manufacturing parts. However, due to their batteryless nature, these devices were assumed to be intrinsically limited in bandwidth, range, and sensing capability. To overcome these limitations, existing approaches required designing new hardware that replaces the hundreds of billions of devices already deployed.

In this talk, I will describe how our research enables transforming batteryless devices into powerful sensors without modifying their hardware in any way, thus bringing direct benefits to the billions of devices deployed in today's world. Specifically, I will describe how we can extract a sensing bandwidth from batteryless devices that is 10,000x larger than their communication bandwidth, and how we can extend their operation range by over 10x. I will also describe how we have designed novel inference algorithms and learning models that build on these techniques to deliver a variety of sensing tasks including sub-centimeter positioning, deep-tissue communication, and non-contact food sensing.

The systems we have built have transformative implications on smart environments, healthcare, manufacturing, and food safety. They enable agile robots to operate in non-line-of-sight environments where vision systems typically fail. They have led to the first demonstration of communication with deep-tissue batteryless micro-implants in a large living animal (pig) from meter-scale distances. Most recently, we demonstrated the potential of using these techniques to sense contaminated food in closed containers. I will conclude by describing how rethinking the abstractions of computing will enable us to bring the next generation of micro-computers to exciting new domains ranging from the human body to the depth of the ocean.

Date and Time: 
Thursday, March 7, 2019 - 4:15pm
Venue: 
Packard 101

ISL Colloquium and IT-Forum presents "Coding over Sets for DNA Storage"

Topic: 
Coding over Sets for DNA Storage
Abstract / Description: 

DNA based storage is a novel technology, where digital information is stored in synthetic DNA molecules. The recent advance in DNA sequencing methods and decrease in sequencing costs have paved the way for storage methods based on DNA. The natural stability of DNA molecules, (the genetic information from fossils is maintained over tens of thousands of years) motivate their use for long-term archival storage. Furthermore, because the information is stored on molecular levels, such storage systems have extremely high data densities. Recent experiments report data densities of 2 PB/gram, which corresponds to the capacity of a thousand conventional hard disk drives in one gram of DNA.

In this talk we present error-correcting codes for the storage of data in synthetic DNA. We investigate a storage model where data is represented by an unordered set of M sequences, each of length L. Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal.

Date and Time: 
Friday, March 8, 2019 - 1:15pm
Venue: 
Packard 202

ISL Colloquium presents "Reinforcement Learning and Optimal Control: An Overview"

Topic: 
Reinforcement Learning and Optimal Control: An Overview
Abstract / Description: 

We will provide an overview of a book in preparation, which will provide a synthesis of optimization/control and artificial intelligence methodologies as they relate to sequential decision problems. In particular, we consider large and challenging multistage problems, which can be solved in principle by dynamic programming, but their exact solution is computationally intractable. We discuss solution methods that rely on approximations to produce suboptimal policies with adequate performance. These methods are collectively referred to as reinforcement learning, and also by alternative names such as approximate dynamic programming, and neuro-dynamic programming. Our subject has benefited greatly from the interplay of ideas from optimal control and from artificial intelligence. One of the aims of the book is to explore the common boundary between these two fields and to form a bridge that is accessible by workers with a background in either field.

Date and Time: 
Monday, March 4, 2019 - 4:00pm
Venue: 
Packard 101

ISL Colloquium and IT-Forum presents "Compression for biological data analysis"

Topic: 
Compression for biological data analysis
Abstract / Description: 

Compression has for decades served primarily the utilitarian purpose of enabling easier storage and transmission of data. Here however, I show how compression can be used to better understand biological processes and assist in data analysis.

First, I will demonstrate the relationship between lossy compression and understanding the perceptual characteristics of downstream agents. Quartz, my lossy compression program for next-generation sequencing quality scores counterintuitively improves SNP calling, despite discarding 95% of quality scores, showing the oversensitivity of variant callers to sequencer noise. More recently, I developed HyperMinHash, a lossy floating-point compression of the popular MinHash Jaccard index sketch, that reduces the space-complexity from log(n) to loglog(n) by using the understanding that MinHash cares less about large hash values than smaller ones.

In the second part of this talk, I show how we exploit the compressive structure of biological data to speed up similarity search. I prove that by organizing the database to facilitate clustered search, our time-complexity scales with metric entropy (number of covering hyperspheres) if the fractal dimension of a dataset is low. This is the key insight behind our compressively accelerated versions of standard tools in genomics (CORA, 10-100x speedup for all-mapping of NGS reads), metagenomics (MICA, 3.5x speedup Diamond), and chemical informatics (Ammolite, 150x speedup SMSD).

Date and Time: 
Friday, February 1, 2019 - 1:15pm
Venue: 
Packard 202

IT Forum presents "Adapting Maximum Likelihood Theory in Modern Applications"

Topic: 
Adapting Maximum Likelihood Theory in Modern Applications
Abstract / Description: 

Maximum likelihood estimation (MLE) is influential because it can be easily applied to generate optimal, statistically efficient procedures for broad classes of estimation problems. Nonetheless, the theory does not apply to modern settings --- such as problems with computational, communication, or privacy considerations --- where our estimators have resource constraints. In this talk, I will introduce a modern maximum likelihood theory that addresses these issues, focusing specifically on procedures that must be computationally efficient or privacy- preserving. To do so, I first derive analogues of Fisher information for these applications, which allows a precise characterization of tradeoffs between statistical efficiency, privacy, and computation. To complete the development, I also describe a recipe that generates optimal statistical procedures (analogues of the MLE) in the new settings, showing how to achieve the new Fisher information lower bounds.

Date and Time: 
Friday, February 22, 2019 - 1:15pm
Venue: 
Packard 202

ISL Colloquium presents "Statistical Inference Under Local Information Constraints"

Topic: 
Statistical Inference Under Local Information Constraints
Abstract / Description: 

Independent samples from an unknown probability distribution p on a domain of size k are distributed across n players, with each player holding one sample. Each player can send a message to a central referee in a simultaneous message passing (SMP) model of communication, whose goal is to solve a pre-specified inference problem. The catch, however, is that each player cannot simply send their own sample to the referee; instead, the message they send must obey some (local) information constraint. For instance, each player may be limited to communicating only L bits, where L << log k; or they may seek to reveal as little information as possible, and preserve local differentially privacy.

We propose a general formulation for inference problems in this distributed setting, and instantiate it to two fundamental inference questions, learning and uniformity testing. We study the role of randomness for those questions, and obtain striking separations between public- and private-coin protocols for the latter, while showing the two settings are equally powerful for the former. (Put differently, "sharing with neighbors does help a lot for the test, but not really for learning.")

Based on joint works with Jayadev Acharya (Cornell University), Cody Freitag (Cornell University), and Himanshu Tyagi (IISc Bangalore).

Date and Time: 
Friday, February 1, 2019 - 1:15am
Venue: 
Packard 202

ISL Colloquium presents "Learning in Non-Stationary Environments: Near-Optimal Guarantees"

Topic: 
Learning in Non-Stationary Environments: Near-Optimal Guarantees
Abstract / Description: 

Motivated by scenarios in which heterogeneous autonomous agents interact, in this talk we present recent work on the development of learning algorithms with performance guarantees for both simultaneous and hierarchical decision-making. Adoption of new technologies is transforming application domains from intelligent infrastructure to e-commerce, allowing operators and intelligently augmented humans to make decisions rapidly as they engage with these systems. Algorithms and market mechanisms supporting interactions occur on multiple time-scales, face resource constraints and system dynamics, and are exposed to exogenous uncertainties, information asymmetries, and behavioral aspects of human decision-making. Techniques for synthesis and analysis of decision-making algorithms, for either inference or influence, that fundamentally depend on an assumption of environment stationarity often breakdown in this context. For instance, humans engaging with platform-based transportation services make decisions that are dependent on their immediate observations of the environment and past experience, both of which are functions of the decisions of other users, multi-timescale policies (e.g., dynamic pricing and fixed laws), and even environmental context that may be non-stationary (e.g., weather patterns or congestion). Implementation of algorithms designed assuming stationarity may lead to unintended or unforeseen consequences.

Stochastic models with high-probability guarantees that capture the dynamics and the decision-making behavior of autonomous agents are needed to support effective interventions such as physical control, economic incentives, or information shaping mechanisms. Two fundamental components are missing in the state-of-the-art: (i) a toolkit for analysis of interdependent learning processes and for adaptive inference in these settings, and (ii) certifiable algorithms for co-designing adaptive influence mechanisms that achieve measurable improvement in system-level performance while ensuring individual-level quality of service through design-in high-probability guarantees. In this talk, we discuss our work towards addressing these gaps. In particular, we provide (asymptotic and non-asymptotic) convergence guarantees for simultaneous play, multi-agent gradient-based learning (a class of algorithms that encompasses a broad set of multi-agent reinforcement learning algorithms) and performance guarantees (regret bounds) for hierarchical decision-making (incentive design) with bandit feedback in non-stationary, Markovian environments. Building on insights from these results, the talk concludes with a discussion of interesting future directions in the design of certifiable, robust algorithms for adaptive inference and influence.

Date and Time: 
Thursday, January 24, 2019 - 4:15pm
Venue: 
Packard 101

ISL Colloquium presents "Algorithms and Algorithmic Intractability in High Dimensional Linear Regression"

Topic: 
Algorithms and Algorithmic Intractability in High Dimensional Linear Regression
Abstract / Description: 

In this talk we will focus on the high dimensional linear regression problem. The goal is to recover a hidden k-sparse binary vector \beta under n noisy linear observations Y=X\beta+W where X is an n \times p matrix with iid N(0,1) entries and W is an n-dimensional vector with iid N(0,\sigma^2) entries. In the literature of the problem, an apparent asymptotic gap is observed between the optimal sample size for information-theoretic recovery, call it n*, and for computationally efficient recovery, call it n_alg.

We will discuss several new contributions on studying this gap. We first identify tightly the information limit of the problem using a novel analysis of the Maximum Likelihood Estimator (MLE) performance. Furthermore, we establish that the algorithmic barrier n_alg coincides with the phase transition point for the appearance of a certain Overlap Gap Property (OGP) over the space of k-sparse binary vectors. The presence of such an Overlap Gap Property phase transition, which originates in spin glass theory, is known to provide evidence of an algorithmic hardness. Finally, we show that in the extreme case where the noise level is zero, i.e. \sigma=0, the computational-statistical gap closes by proposing an optimal polynomial-time algorithm using the Lenstra-Lenstra-Lov\'asz lattice basis reduction algorithm.

This is joint work with David Gamarnik.

Date and Time: 
Friday, January 18, 2019 - 3:00pm
Venue: 
Gates 463A

ISL Colloquium presents "Stochastic Descent Algorithms: Minimax Optimality, Implicit Regularization, and Deep Networks"

Topic: 
Stochastic Descent Algorithms: Minimax Optimality, Implicit Regularization, and Deep Networks
Abstract / Description: 

Stochastic descent methods have had a long history in optimization, adaptive filtering, and online learning and have recently gained tremendous popularity as the workhorse for deep learning. So much so that, it is now widely recognized that the success of deep networks is not only due to their special deep architecture, but also due to the behavior of the stochastic descent methods used, which plays a key role in reaching "good" solutions that generalize well to unseen data. In an attempt to shed some light on why this is the case, we revisit some minimax properties of stochastic gradient descent (SGD)---originally developed for quadratic loss and linear models in the context of H-infinity control in the 1990's---and extend them to general stochastic mirror descent (SMD) algorithms for general loss functions and nonlinear models. These minimax properties can be used to explain the convergence and implicit-regularization of the algorithms when the linear regression problem is over-parametrized (in what is now being called the "interpolating regime"). In the nonlinear setting, exemplified by training a deep neural network, we show that when the setup is "highly over-parametrized", stochastic descent methods enjoy similar convergence and implicit-regularization properties. This observation gives some insight into why deep networks exhibit such powerful generalization abilities. It is also a further example of what is increasingly referred to as the "blessing of dimensionality".

Date and Time: 
Thursday, January 17, 2019 - 4:15pm
Venue: 
Packard 101

Pages

Subscribe to RSS - Information Systems Lab (ISL) Colloquium