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.