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 attributes 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 compensate for the lack of full information on each training
example. We demonstrate the efficiency 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.
