# mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 16 May 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [A single gradient step finds adversarial examples on random two-layers neural networks](https://mlsanity.com/paper/2104.03863/) (2021)
- [Adversarial Examples in Multi-Layer Random ReLU Networks](https://mlsanity.com/paper/2106.12611/) (2021)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [Improved Generalization Bounds for Adversarially Robust Learning](https://mlsanity.com/paper/1810.02180/) (2018)
- [The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise](https://mlsanity.com/paper/2007.15220/) (2020)
- [Adversarial Risk Bounds via Function Transformation](https://mlsanity.com/paper/1810.09519/) (2018)
- [Adversarial Examples from Cryptographic Pseudo-Random Generators](https://mlsanity.com/paper/1811.06418/) (2018)

## Abstract (arXiv)

We present a detailed study of estimation errors in terms of surrogate loss estimation errors. We refer to such guarantees as mathscrH-consistency estimation error bounds, since they account for the hypothesis set mathscrH adopted. These guarantees are significantly stronger than mathscrH-calibration or mathscrH-consistency. They are also more informative than similar excess error bounds derived in the literature, when mathscrH is the family of all measurable functions. We prove general theorems providing such guarantees, for both the distribution-dependent and distribution-independent settings. We show that our bounds are tight, modulo a convexity assumption. We also show that previous excess error bounds can be recovered as special cases of our general results. We then present a series of explicit bounds in the case of the zero-one loss, with multiple choices of the surrogate loss and for both the family of linear functions and neural networks with one hidden-layer. We further prove more favorable distribution-dependent guarantees in that case. We also present a series of explicit bounds in the case of the adversarial loss, with surrogate losses based on the supremum of the ρ-margin, hinge or sigmoid loss and for the same two general hypothesis sets. Here too, we prove several enhancements of these guarantees under natural distributional assumptions. Finally, we report the results of simulations illustrating our bounds and their tightness.