Problems in Learning under Limited Resources and Information

The main theme of this thesis is to investigate how learning problems can be solved in the face of limited resources and with limited information to base inferences on. We study feature-efficient prediction when each feature comes with a cost and our goal is to construct a good predictor during training time with total cost not exceeding the given budget constraints. We also study complexity-theoretic properties of models for recovering social networks with knowledge only about how people in the network vote or how information propagates through the network.