Events Calendar

Fundamental Limits of Passive and Active Learning: A New Look via Feedback Information Theory

Speaker: Max Raginsky , UIUC

Talk Title: Fundamental Limits of Passive and Active Learning: A New Look via Feedback Information Theory

Abstract: Statistical learning theory is concerned with making accurate predictions on the basis of past observations. One of the main characteristics of any learning problem is its sample complexity: the minimum number of observations needed to ensure a given prediction accuracy at a given confidence level. For the most part, the focus has been on passive learning, in which the learning agent receives independent training samples. However, recently there has been increasing interest in active learning, in which past observations are used to control the process of gathering future observations. The main question is whether active learning is strictly more powerful than its passive counterpart. One way to answer this is to compare the sample complexities of passive and active learning for the same accuracy and confidence.

In this talk, based on joint work with Sasha Rakhlin (Department of Statistics, University of Pennsylvania), I will present a new unified approach to deriving tight lower bounds on the sample complexity of both passive and active learning in the setting of binary classification. This approach is fundamentally rooted in information theory, in particular, the simple but powerful data processing inequality for the f divergence. I will give a high-level overview of the proof technique and discuss the connections between active learning and hypothesis testing with feedback.


Biography: Maxim Raginsky received the B.S. and M.S. degrees in 2000 and the Ph.D. degree in 2002 from Northwestern University, all in electrical engineering. He has held research positions with Northwestern, the University of Illinois at Urbana-Champaign (where he was a Beckman Foundation Fellow from 2004 to 2007), and Duke University. In 2012, he has returned to the UIUC, where he is currently an Assistant Professor with the Department of Electrical and Computer Engineering and a Research Assistant Professor in the Coordinated Science Laboratory. His research interests lie at the intersection of information theory, learning, and control.


Host: Urbashi Mitra

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos