# Agnostic Multi-Robust Learning Using ERM

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 15 Mar 2023.

## Builds on (most cited first, 19 of 19)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Adversarial Patch](https://mlsanity.com/paper/1712.09665/) (2017)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [LaVAN: Localized and Visible Adversarial Noise](https://mlsanity.com/paper/1801.02608/) (2018)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [PatchAttack: A Black-box Texture-based Attack with Reinforcement Learning](https://mlsanity.com/paper/2004.05682/) (2020)
- [PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier](https://mlsanity.com/paper/2108.09135/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Minority Reports Defense: Defending Against Adversarial Patches](https://mlsanity.com/paper/2004.13799/) (2020)
- [PatchGuard++: Efficient Provable Attack Detection against Adversarial Patches](https://mlsanity.com/paper/2104.12609/) (2021)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Efficient Certified Defenses Against Patch Attacks on Image Classifiers](https://mlsanity.com/paper/2102.04154/) (2021)
- [Calibration for the (Computationally-Identifiable) Masses](https://mlsanity.com/paper/1711.08513/) (2017)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking](https://mlsanity.com/paper/2005.10884/) (2020)

## Built on by (most cited first, 2 of 2)

- [Panprediction: Optimal Predictions for Any Downstream Task and Loss](https://mlsanity.com/paper/2510.27638/) (2025)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)

## Abstract (arXiv)

A fundamental problem in robust learning is asymmetry: a learner needs to correctly classify every one of exponentially-many perturbations that an adversary might make to a test-time natural example. In contrast, the attacker only needs to find one successful perturbation. Xiang et al.[2022] proposed an algorithm that in the context of patch attacks for image classification, reduces the effective number of perturbations from an exponential to a polynomial number of perturbations and learns using an ERM oracle. However, to achieve its guarantee, their algorithm requires the natural examples to be robustly realizable. This prompts the natural question; can we extend their approach to the non-robustly-realizable case where there is no classifier with zero robust error? Our first contribution is to answer this question affirmatively by reducing this problem to a setting in which an algorithm proposed by Feige et al.[2015] can be applied, and in the process extend their guarantees. Next, we extend our results to a multi-group setting and introduce a novel agnostic multi-robust learning problem where the goal is to learn a predictor that achieves low robust loss on a (potentially) rich collection of subgroups.