Learning to Predict Under A Budget