  In this paper, we consider batch supervised learning where an adversary is
allowed to corrupt instances with arbitrarily large noise. The adversary is
allowed to corrupt any $l$ features in each instance and the adversary can
change their values in any way. This noise is introduced on test instances and
the algorithm receives no label feedback for these instances. We provide
several subspace voting techniques that can be used to transform existing
algorithms and prove data-dependent performance bounds in this setting. The key
insight to our results is that we set our parameters so that a significant
fraction of the voting hypotheses do not contain corrupt features and, for many
real world problems, these uncorrupt hypotheses are sufficient to achieve high
accuracy. We empirically validate our approach on several datasets including
three new datasets that deal with side channel electromagnetic information.
