Efficient learning with partially observed attributes

We describe and analyze efficient algorithms for learning a linear predictor from examples when the learner can only view a few at-tributes of each training example. This is the case, for instance, in medical research, where each patient participating in the experiment is only willing to go through a small number of tests. Our analysis bounds the number of additional examples sufficient to compen-sate for the lack of full information on each training example. We demonstrate the ef-ficiency of our algorithms by showing that when running on digit recognition data, they obtain a high prediction accuracy even when the learner gets to see only four pixels of each image. 1