Information Systems Lab (ISL) Colloquium

IT Forum & ISL Colloquium present "Proving Coding Theorems using Poisson Processes"

Topic: 
Proving Coding Theorems using Poisson Processes
Abstract / Description: 

In information theory, coding theorems are usually proved in the asymptotic regime where the blocklength tends to infinity. While there are techniques for finite blocklength analysis, they are often more complex than their asymptotic counterparts. In this talk, we study the use of Poisson processes in proving coding theorems, which not only gives sharp finite blocklength results, but also gives significantly shorter proofs than conventional asymptotic techniques in some settings. Instead of using fixed-size random codebooks, we construct the codebook as a Poisson process. We present a lemma, called the Poisson matching lemma, which can replace both packing and covering lemmas in proofs based on typicality. We then demonstrate its use in settings such as channel coding with channel state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, and distributed lossy source coding. This shows that the Poisson matching lemma is a viable alternative to typicality for most problems in network information theory.

The talk is based on a joint work with Prof. Venkat Anantharam (UC Berkeley).

 

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

ISL & IT Forum present "Human-Interpretable Concept Learning via Information Lattices"

Topic: 
Human-Interpretable Concept Learning via Information Lattices
Abstract / Description: 

Is it possible to learn the laws of music theory directly from raw sheet music in the same human-interpretable form as a music theory textbook? How little prior knowledge needs to be encoded to do so? We consider these and similar questions in other topical domains, in developing a general framework for automatic concept learning. The basic idea is an iterative discovery algorithm that has a student-teacher architecture and that operates on a generalization of Shannon's information lattice, which itself encodes a hierarchy of abstractions and is algorithmically constructed from group-theoretic foundations. In particular, learning this hierarchy of invariant concepts involves iterative optimization of Bayesian surprise and entropy. This gives a first step towards a principled and cognitive way of automatic concept learning and knowledge discovery. We further discuss applications in computational creativity, and limit theorems for creativity.

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

IT Forum & ISL Colloquium present "Learning from Sparse Data"

Topic: 
Learning from Sparse Data
Abstract / Description: 

In many scientific domains, the number of individuals in the population under study is often very large, however the number of observations available per individual is often very limited (sparse). Limited observations prohibit accurate estimation of parameters of interest for any given individual. In this sparse data regime, the key question is, how accurately can we estimate the distribution of parameters over the population? This problem arises in various domains such as epidemiology, psychology, health-care, biology, and social sciences. As an example, suppose for a large random sample of the population we have observations of whether a person caught the flu for each year over the past 5 years. We cannot accurately estimate the probability of any given person catching the flu with only 5 observations, however our goal is to estimate the distribution of these probabilities over the whole population. Such an estimated distribution can be used in downstream tasks, like testing and estimating properties of the distribution.

In this talk, I will present our recent results where we show that the maximum likelihood estimator (MLE) is minimax optimal in the sparse observation regime. While the MLE for this problem was proposed as early as the late 1960's, how accurately the MLE recovers the true distribution was not known. Our work closes this gap. In the course of our analysis, we provide novel bounds on the coefficients of Bernstein polynomials approximating Lipschitz-1 functions. Furthermore, the MLE is also efficiently computable in this setting and we evaluate the performance of MLE on both synthetic and real datasets.

Joint work with Weihao Kong, Gregory Valiant, and Sham Kakade.

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

ISL & IT Forum present "Feedback capacity of channels with memory via Reinforcement Learning and Graph-based auxiliary random variable""

Topic: 
Feedback capacity of channels with memory via Reinforcement Learning and Graph-based auxiliary random variable
Abstract / Description: 

In this talk we present two novel ideas: the first is novel method to compute the feedback capacity of channels with memory using reinforcement learning (RL). The second is a new technique of using Graph-based auxiliary random variable to convert a multi-letter expression of feedback capacity formula into a single letter expression.

In RL, one seeks to maximize cumulative rewards collected in a sequential decision-making environment. This is done by collecting samples of the underlying environment and using them to learn the optimal decision rule. The main advantage of this approach is its computational efficiency, even in high dimensional problems. Hence, RL can be used to estimate numerically the feedback capacity of unifilar finite state channels (FSCs) with large alphabet size. The outcome of the RL algorithm sheds light on the properties of the optimal decision rule, which in our case, is the optimal input distribution of the channel.

The insights gained from the RL computation can be converted into analytic, single-letter capacity expressions by solving corresponding lower and upper bounds. The bounds are based on another novel idea of using Graph-based auxiliary random variable

We demonstrate the efficiency of this method by analytically solving the feedback capacity of the well-known Ising channel with a large alphabet. We also provide a simple coding scheme that achieves the feedback capacity.

 

Date and Time: 
Friday, August 2, 2019 - 3:00pm
Venue: 
Packard 202

ISL & IT Forum present "Resource-efficient quantized deep learning"

Topic: 
Resource-efficient quantized deep learning
Abstract / Description: 

Reducing the numerical precision of neural networks is one of the simplest, most effective and most common methods to improve resource efficiency (e.g. by reducing the memory and power requirements). Much research has been invested in finding how to quantize neural nets without significantly degrading performance. I will describe the main bottlenecks and solutions in various settings:
1) 1bit inference (1bit weights and activations), NIPS 2016 - link
2) 8bit training (8bit weights, activations, gradients, and batch-norm), NeurIPS 2018 - link
3) 4bit inference when quantization is done only post-training, Arxiv 2019 - link
4) Calculating the maximum trainable depth as a function of the numerical precision, Arxiv 2019 - link

Date and Time: 
Friday, July 26, 2019 - 2:00pm
Venue: 
Packard 202

ISL & IT Forum present "Towards Achieving Secure Consensus and Trusted Data Exchange for Multi-Robot Teams""

Topic: 
Towards Achieving Secure Consensus and Trusted Data Exchange for Multi-Robot Teams
Abstract / Description: 

As physical robot networks become more pervasive all around us, in the form of teams of autonomous vehicles, fleets of delivery drones, and smart and mobile IoT, it becomes increasingly critical to question the robustness of their coordination algorithms to security threats and/or corrupted data. Indeed, it has been shown that many multi-robot tasks easily fail in the presence of erroneous or hacked data. We investigate the vulnerabilities of important multi-robot algorithms such as consensus, coverage, and distributed mapping to malicious or erroneous data and we demonstrate the potential of communication to thwart certain attacks, such as the Sybil Attack, on these algorithms. Our key insight is that coordinated mobility can be combined with signal processing of communication signals to allow agents to learn important information about the environment and the nature of other agents in the network (for example the presence of cooperative versus adversarial agents). Along these lines, we will present a theoretical and experimental framework for provably securing multi-robot distributed algorithms through careful use of communication. We will present both theoretical results and experimental results on actual hardware implementations for bounding the influence of a Sybil Attack on consensus and on coverage by using observations over the wireless channels. In some cases, we show that the effect of a Sybil Attack can be nearly eliminated with high probability by deriving the appropriate switching function using a sufficient number of observations over the wireless network. Finally, we will briefly describe promising results on new methods for outlier rejection and active rendezvous in a pose graph optimization framework that exploits feedback gathered from communication channels to arrive at improved accuracy.

Date and Time: 
Wednesday, July 24, 2019 - 2:00pm
Venue: 
Packard 202

ISL & IT Forum present "Building a DNA information storage system from the bottom up"

Topic: 
Building a DNA information storage system from the bottom up
Abstract / Description: 

DNA has emerged as a compelling data storage medium due to its density, longevity, and eternal relevance compared to current memory technologies. However, the high price of synthesizing DNA (list price $3,500 per megabyte) remains a major bottleneck for adoption of this promising storage solution. In this talk, I will present our work towards breaking down this barrier using enzymatic DNA synthesize and a tailored codec for robust data retrieval. I will also touch upon some fundamental considerations when designing DNA information storage systems.

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

ISL & IT Forum present "Tensor networks and quantum Markov chain"

Topic: 
Tensor networks and quantum Markov chain
Abstract / Description: 

Tensor networks can often accurately approximate various systems that are of interest to physicists, but the computational cost of contracting the network is often prohibitively demanding. Quantum computer can resolve this bottleneck, but because the size of the computation scales with the size of the network, the existing quantum computers may appear to be far too noisy for this task. We prove a nontrivial error bound on the outcome of the computation that does not scale with the size of the network. This is possible because certain tensor networks are secretly implementing a quantum analogue of a (classical) Markovian dynamics. The long-time stability of the Markovian dynamics gives rise to a nontrivial error bound on the outcome of the computation. This suggests that there may be practical problems of interest that are amenable to relatively noisy quantum computers.

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

ISL & Stats present Stability and uncertainty quantification

Topic: 
Bridging convex and nonconvex optimization in noisy matrix completion: Stability and uncertainty quantification
Abstract / Description: 

This talk is concerned with noisy matrix completion: given partial and corrupted entries of a large low-rank matrix, how to estimate and infer the underlying matrix? Arguably one of the most popular paradigms to tackle this problem is convex relaxation, which achieves remarkable efficacy in practice. However, the statistical stability guarantees of this approach is still far from optimal in the noisy setting, falling short of explaining the empirical success. Moreover, it is generally very challenging to pin down the distributions of the convex solution, which presents a major roadblock in assessing the uncertainty, or "confidence", for the obtained estimates–a crucial task at the core of statistical inference. 

Our recent work makes progress towards understanding stability and uncertainty quantification for noisy matrix completion. When the rank of the unknown matrix is a constant: (1) we demonstrate that convex programming achieves near-optimal estimation errors vis-'avis random noise; (2) we develop a de-biased estimator that admits accurate distributional characterizations, thus enabling asymptotically optimal inference. All of this is enabled by bridging convex relaxation with the nonconvex approach, a seemingly distinct algorithmic paradigm that is provably robust against noise.


This is joint work with Cong Ma, Yuling Yan, Yuejie Chi, and Jianqing Fan.

Date and Time: 
Tuesday, May 28, 2019 - 4:30pm
Venue: 
Herrin Hall Room T175

Reinforcement Learning & ISL present "Do Deep Generative Models Know What They Don't Know?"

Topic: 
Do Deep Generative Models Know What They Don't Know?
Abstract / Description: 

A neural network deployed in the wild may be asked to make predictions for inputs that were drawn from a different distribution than that of the training data. A plethora of work has demonstrated that it is easy to find or synthesize inputs for which a neural network is highly confident yet wrong. Generative models are widely viewed to be robust to such mistaken confidence as modeling the density of the input features can be used to detect novel, out-of-distribution inputs.

In this talk, we challenge this assumption. We find that the density learned by deep generative models (flow-based models, VAEs, and PixelCNNs) cannot distinguish images of common objects such as dogs, trucks, and horses (i.e. CIFAR-10) from those of house numbers (i.e. SVHN), assigning a higher likelihood to the latter when the model is trained on the former. Moreover, we find evidence of this phenomenon when pairing several popular image data sets: FashionMNIST vs MNIST, CelebA vs SVHN, ImageNet vs CIFAR-10 / CIFAR-100 / SVHN. To investigate this curious behavior, we focus analysis on flow-based generative models in particular since they are trained and evaluated via the exact marginal likelihood. We find such behavior persists even when we restrict the flows to constant-volume transformations. These transformations admit some theoretical analysis, and we show that the difference in likelihoods can be explained by the location and variances of the data and the model curvature. Our results caution against using the density estimates from deep generative models to identify inputs similar to the training distribution until their behavior for out-of-distribution inputs is better understood.

Date and Time: 
Tuesday, May 28, 2019 - 4:00pm
Venue: 
Packard 101

Pages

Subscribe to RSS - Information Systems Lab (ISL) Colloquium