When Quantity makes Quality: Learning with Information Constraints

In standard learning models, it is assumed that the learner has a complete and fully available training set at hand. However, in many real-world applications, obtaining full information on the training examples is expensive, illegal, or downright impossible. In this talk, I will discuss some new methods to learn in such information-constrained settings. These range from learning with only a few available features from each example; through coping with extremely noisy access to the data; to privacy-preserving learning. The underlying theme is that by gathering less information on more examples, one can be provably competitive with learning mechanisms which enjoy full access to the data. Along the way, I’ll describe some novel techniques which might be of interest in their own right.

The talk is based on some recent joint works with Nicolo Cesa-Bianchi and Shai Shalev-Shwartz.

Speaker Bios

Ohad Shamir is finishing his Ph.D. in computer science at the Hebrew University, under the guidance of Naftali Tishby. His research interests range across all topics on the border of machine learning theory and practice. He is particularly interested in using theoretical ideas and insights to develop practical new algorithms, for important but hard settings which defy standard techniques.