Speaker: Su Jia

Abstract: The goal of active learning is to learn a classifier in a setting where data comes unlabeled, and any labels must be explicitly requested and paid for. The hope is that an accurate classifier can be found by buying just a few labels. This problem is also known as the optimal decision tree problem in the field of approximation algorithms. In this talk I will introduce some classical results in both these two fields, and present some representative techniques for analyzing the related greedy algorithms.