EE Student Information

Information Systems Lab (ISL) Colloquium

ISL Colloquium: Reinforcement Learning: Hidden Theory, and New Super-Fast Algorithms

Topic: 
Reinforcement Learning: Hidden Theory, and New Super-Fast Algorithms
Abstract / Description: 

Stochastic Approximation algorithms are used to approximate solutions to fixed point equations that involve expectations of functions with respect to possibly unknown distributions. The most famous examples today are TD- and Q-learning algorithms. The first half of this lecture will provide an overview of stochastic approximation, with a focus on optimizing the rate of convergence. A new approach to optimize the rate of convergence leads to the new Zap Q-learning algorithm. Analysis suggests that its transient behavior is a close match to a deterministic Newton-Raphson implementation, and numerical experiments confirm super fast convergence.

Date and Time: 
Tuesday, May 1, 2018 - 4:30pm
Venue: 
Packard 101

ISL Seminar: Inventing Algorithms via Deep Learning

Topic: 
Inventing Algorithms via Deep Learning
Abstract / Description: 

Deep learning is a part of daily life, owing to its successes in computer vision and natural language processing. In these applications, the success of the model-free deep learning approach can be attributed to a lack of (mathematical) generative model. In yet other applications, the data is generated by a simple model and performance criterion mathematically precise and training/test samples infinitely abundant, but the space of algorithmic choices is enormous (example: chess). Deep learning has recently shown strong promise in these problems too (example: alphazero). In this talk, we study two canonical problems of great scientific and engineering interest through the lens of deep learning.

The first is reliable communication over noisy media where we successfully revisit classical open problems in information theory; we show that creatively trained and architected neural networks can beat state of the art on the AWGN channel with noisy feedback by a 100 fold improvement in bit error rate.

The second is optimization and classification problems on graphs, where the key algorithmic challenge is scalable performance to arbitrary sized graphs. Representing graphs as randomized nonlinear dynamical systems via recurrent neural networks, we show that creative adversarial training allows one to train on small size graphs and test on much larger sized graphs (100~1000x) with approximation ratios that rival state of the art on a variety of optimization problems across the complexity theoretic hardness spectrum.

Apart from the obvious practical value, this study of mathematically precise problems sheds light on the mysteries of deep learning methods: training example choices, architectural design decisions and loss function/learning methodologies. Our (mostly) empirical research is conducted under the backdrop of a theoretical research program of understanding gated neural networks (eg: attention networks, GRU, LSTM); we show the first provably (globally) consistent algorithms to recover the parameters of a classical gated neural network architecture: mixture of experts (MoE).

Date and Time: 
Thursday, April 26, 2018 - 4:15pm
Venue: 
Packard 101

ISL Colloquium: Reinforcement Learning without Reinforcement

Topic: 
Reinforcement Learning without Reinforcement
Abstract / Description: 

Reinforcement Learning (RL) is concerned with solving sequential decision-making problems in the presence of uncertainty. RL is really about two problems together. The first is the 'Bellman problem': Finding the optimal policy given the model, which may involve large state spaces. Various approximate dynamic programming and RL schemes have been developed, but either there are no guarantees, or not universal, or rather slow. In fact, most RL algorithms have become synonymous with stochastic approximation (SA) schemes that are known to be rather slow. This is an even more difficult problem for MDPs with continuous state (and action) spaces. We present a class of non-SA algorithms for reinforcement learning in continuous state space MDP problems based on 'empirical' ideas, which are simple, effective and yet universal with probabilistic guarantees. The idea involves randomized Kernel-based function fitting combined with 'empirical' updates. The key is the first known "probabilistic contraction analysis" method we have developed for analysis of fairly general stochastic iterative algorithms, wherein we show convergence to a probabilistic fixed point of a sequence of random operators via a stochastic dominance argument.

The second RL problem is the 'online learning (or the Lai-Robbins) problem' when the model itself is unknown. We propose a simple posterior sampling-based regret-minimization reinforcement learning algorithm for MDPs. It achieves O(sqrt{T})-regret which is order-optimal. It not only optimally manages the "exploration versus exploitation tradeoff" but also obviates the need for expensive computation for exploration. The algorithm differs from classical adaptive control in its focus on non-asymptotic regret optimality as opposed to asymptotic stability. This seems to resolve a long standing open problem in Reinforcement Learning.

Date and Time: 
Tuesday, April 24, 2018 - 4:00pm to Wednesday, April 25, 2018 - 3:55pm
Venue: 
Packard 101

ISL Colloquium: Recent Developments in Compressed Sensing

Topic: 
Recent Developments in Compressed Sensing
Abstract / Description: 

Compressed sensing refers to the reconstruction of high-dimensional but low-complexity objects from a limited number of measurements. Examples include the recovery of high-dimensional but sparse vectors, and the recovery of high-dimensional but low-rank matrices, which includes the so-called partial realization problem in linear control theory. Much of the work to date focuses on probabilistic methods, which are CPU-intensive and have high computational complexity. In contrast, deterministic methods are far faster in execution and more efficient in terms of storage. Moreover, deterministic methods draw from many branches of mathematics, including graph theory and algebraic coding theory. In this talk a brief overview will be given of such recent developments.

Date and Time: 
Thursday, April 19, 2018 - 4:15pm
Venue: 
Packard 101

IT Forum: From Gaussian Multiterminal Source Coding to Distributed Karhunen–Loève Transform

Topic: 
From Gaussian Multiterminal Source Coding to Distributed Karhunen–Loève Transform
Abstract / Description: 

Characterizing the rate-distortion region of Gaussian multiterminal source coding is a longstanding open problem in network information theory. In this talk, I will show how to obtain new conclusive results for this problem using nonlinear analysis and convex relaxation techniques. A byproduct of this line of research is an efficient algorithm for determining the optimal distributed Karhunen–Loève transform in the high-resolution regime, which partially settles a question posed by Gastpar, Dragotti, and Vetterli. I will also introduce a generalized version of the Gaussian multiterminal source coding problem where the source-encoder connections can be arbitrary. It will be demonstrated that probabilistic graphical models offer an ideal mathematical language for describing how the performance limit of a generalized Gaussian multiterminal source coding system depends on its topology, and more generally they can serve as the long-sought platform for systematically integrating the existing achievability schemes and converse arguments. The architectural implication of our work for low-latency lossy source coding will also be discussed.

This talk is based on joint work with Jia Wang, Farrokh Etezadi, and Ashish Khisti.


The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:15 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Yanjun Han. To suggest speakers, please contact any of the students.

Date and Time: 
Friday, April 13, 2018 - 1:15pm
Venue: 
Packard 202

ISL Special Seminar: Low- and high-dimensional computations in neural circuits

Topic: 
Low- and high-dimensional computations in neural circuits
Abstract / Description: 

Computation in the brain is distributed across large populations. Individual neurons are noisy and receive limited information but, by acting collectively, neural populations perform a wide variety of complex computations. In this talk I will discuss two approaches to understanding these collective computations. First, I will introduce a method to identify and decode unknown variables encoded in the activity of neural populations. While the number of neurons in a population may be large, if the population encodes a low-dimensional variable there will be low-dimensional structure in the collective activity, and the method aims to find and parameterize this low-dimensional structure. In the rodent head direction (HD) system, the method reveals a nonlinear ring manifold and allows encoded head direction and the tuning curves of single cells to be recovered with high accuracy and without prior knowledge of what neurons were encoding. When applied to sleep, it provides mechanistic insight into the circuit construction of the ring manifold and, during nREM sleep, reveals a new dynamical regime possibly linked to memory consolidation in the brain. I will then address the problem of understanding genuinely high-dimensional computations in the brain, where low-dimensional structure does not exist. Modern work studying distributed algorithms on large sparse networks may provide a compelling approach to neural computation, and I will use insights from recent work on error correction to construct a novel architecture for high-capacity neural memory. Unlike previous models, which yield either weak (linear) increases in capacity with network size or exhibit poor robustness to noise, this network is able to store a number of states exponential in network size while preserving noise robustness, thus resolving a long-standing theoretical question.
These results demonstrate new approaches for studying neural representations and computation across a variety of scales, both when low-dimensional structure is present and when computations are high-dimensional.

Date and Time: 
Tuesday, March 6, 2018 - 10:00am to Wednesday, March 7, 2018 - 9:55am
Venue: 
Clark S360

ISL Colloquium: Deep Exploration via Randomized Value Functions

Topic: 
Deep Exploration via Randomized Value Functions
Abstract / Description: 

An important challenge in reinforcement learning concerns how an agent can simultaneously explore and generalize in a reliably efficient manner. It is difficult to claim that one can produce a robust artificial intelligence without tackling this fundamental issue. This talk will present a systematic approach to exploration that induces judicious probing through randomization of value function estimates and operates effectively in tandem with common reinforcement learning algorithms, such as least-squares value iteration and temporal-difference learning, that generalize via parameterized representations of the value function. Theoretical results offer assurances with tabular representations of the value function, and computational results suggest that the approach remains effective with generalizing representations.

Date and Time: 
Thursday, February 22, 2018 - 4:15pm
Venue: 
Packard 101

ISL Special Seminar: Computational structure in large-scale neural population recordings: how to find it, and when to believe it

Topic: 
Computational structure in large-scale neural population recordings: how to find it, and when to believe it
Abstract / Description: 

One central challenge in neuroscience is to understand how neural populations represent and produce the remarkable computational abilities of our brains. Indeed, neuroscientists increasingly form scientific hypotheses that can only be studied at the level of the neural population, and exciting new large-scale datasets have followed. Capitalizing on this trend, however, requires two major efforts from applied statistical and machine learning researchers: (i) methods for finding structure in this data, and (ii) methods for statistically validating that structure. First, I will review our work that has used factor modeling and dynamical systems to advance understanding of the computational structure in the motor cortex of primates and rodents. Second, while these methods and the broader class of such methods are promising, they are also perilous: novel analysis techniques do not always consider the possibility that their results are an expected consequence of some simpler, already-known feature of the data. I will present two works that address this growing problem, the first of which derives a tensor-variate maximum entropy distribution with user-specified moment constraints along each mode. This distribution forms the basis of a statistical hypothesis test, and I will use this test to answer two active debates in the neuroscience community over the triviality of structure in the motor and prefrontal cortices. I will then discuss how to extend this maximum entropy formulation to arbitrary constraints using deep neural network architectures in the flavor of implicit generative modeling.

Date and Time: 
Thursday, February 15, 2018 - 10:00am to Friday, February 16, 2018 - 9:55am
Venue: 
Munzer Auditorium

ISL Colloquium: Data Driven Dialog Management

Topic: 
Data Driven Dialog Management
Abstract / Description: 

Modern virtual personal assistants provide a convenient interface for completing daily tasks via voice commands. An important consideration for these assistants is the ability to recover from automatic speech recognition (ASR) and natural language understanding (NLU) errors. I present our recent work on learning robust dialog policies to recover from these errors. To this end, we developed a user simulator which interacts with the assistant through voice commands in realistic scenarios with noisy audio, and use it to learn dialog policies through deep reinforcement learning. We show that dialogs generated by our simulator are indistinguishable from human generated dialogs, as determined by human evaluators. Furthermore, preliminary experimental results show that the learned policies in noisy environments achieve the same execution success rate with fewer dialog turns compared to fixed rule-based policies.

Date and Time: 
Wednesday, February 7, 2018 - 4:30pm
Venue: 
Packard 202

ISL Colloquium: Data-driven analysis of neuronal activity

Topic: 
Data-driven analysis of neuronal activity
Abstract / Description: 

Recent advances in experimental methods in neuroscience enable the acquisition of large-scale, high-dimensional and high-resolution datasets. In this talk I will present new data-driven methods based on global and local spectral embeddings for the processing and organization of high-dimensional datasets, and demonstrate their application to neuronal measurements. Looking deeper into the spectrum, we develop Local Selective Spectral Clustering, a new method capable of handling overlapping clusters and disregarding clutter. Applied to in-vivo calcium imaging, we extract hundreds of neuronal structures with detailed morphology, and demixed and denoised time-traces. Next we introduce a nonliner model-free approach for the analysis of a dynamical system, developing data-driven tree-based transforms and metrics for multiscale co-organization of the data. Applied to trial-based neuronal measurements, we identify, solely from observations and in a purely unsupervised manner, functional subsets of neurons, activity patterns associated with particular behaviors and pathological dysfunction caused by external intervention.

Date and Time: 
Thursday, February 15, 2018 - 4:15pm
Venue: 
Packard 101

Pages

Subscribe to RSS - Information Systems Lab (ISL) Colloquium