# Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples

arXiv: https://arxiv.org/abs/2007.05145 · HTML: https://mlsanity.com/paper/2007.05145/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2020.

## Built on by (most cited first, 30 of 44)

- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [Adversarial Attacks of Vision Tasks in the Past 10 Years: A Survey](https://mlsanity.com/paper/2410.23687/) (2024)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [A Learning Based Hypothesis Test for Harmful Covariate Shift](https://mlsanity.com/paper/2212.02742/) (2022)
- [Efficient Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2102.07802/) (2021)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds](https://mlsanity.com/paper/2404.02364/) (2024)
- [Uncovering Adversarial Risks of Test-Time Adaptation](https://mlsanity.com/paper/2301.12576/) (2023)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [Generalizing Importance Weighting to A Universal Solver for Distribution Shift Problems](https://mlsanity.com/paper/2305.14690/) (2023)
- [Efficient Discrepancy Testing for Learning with Distribution Shift](https://mlsanity.com/paper/2406.09373/) (2024)
- [Towards Evaluating the Robustness of Neural Networks Learned by Transduction](https://mlsanity.com/paper/2110.14735/) (2021)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Data Models for Dataset Drift Controls in Machine Learning With Optical Images](https://mlsanity.com/paper/2211.02578/) (2022)
- [Stratified Adversarial Robustness with Rejection](https://mlsanity.com/paper/2305.01139/) (2023)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Weight Clipping for Robust Conformal Inference under Unbounded Covariate Shifts](https://mlsanity.com/paper/2605.02072/) (2026)
- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)
- [Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://mlsanity.com/paper/2602.20111/) (2026)
- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Towards Adversarial Robustness via Transductive Learning](https://mlsanity.com/paper/2106.08387/) (2021)
- [p-DkNN: Out-of-Distribution Detection Through Statistical Testing of Deep Representations](https://mlsanity.com/paper/2207.12545/) (2022)
- [Adversarial Robustness: What fools you makes you stronger](https://mlsanity.com/paper/2102.05475/) (2021)
- [Provable Adversarial Robustness in the Quantum Model](https://mlsanity.com/paper/2112.09625/) (2021)

## Abstract (arXiv)

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. This is unlike prior work that assumes that test examples are small perturbations of P. Our algorithm outputs a selective classifier, which abstains from predicting on some examples. By considering selective transductive learning, we give the first nontrivial guarantees for learning classes of bounded VC dimension with arbitrary train and test distributions---no prior guarantees were known even for simple classes of functions such as intervals on the line. In particular, for any function in a class C of bounded VC dimension, we guarantee a low test error rate and a low rejection rate with respect to P. Our algorithm is efficient given an Empirical Risk Minimizer (ERM) for C. Our guarantees hold even for test examples chosen by an unbounded white-box adversary. We also give guarantees for generalization, agnostic, and unsupervised settings.