  We study binary classification in the setting where the learner is presented
with multiple corrupted training samples, with possibly different sample sizes
and degrees of corruption, and introduce an approach based on minimizing a
weighted combination of corruption-corrected empirical risks. We establish a
generalization error bound, and further show that the bound is optimized when
the weights are certain interpretable and intuitive functions of the sample
sizes and degrees of corruptions. We then apply this setting to the problem of
learning with label proportions (LLP), and propose an algorithm that enjoys the
most general statistical performance guarantees known for LLP. Experiments
demonstrate the utility of our theory.
