Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples

Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai +1

We present a transductive learning algorithm that takes as input training examples from a distribution $P$ and arbitrary (unlabeled) test examples, possibly chosen by an adversary.…