# On Robustness to Adversarial Examples and Polynomial Optimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2019.

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [A Multiclass Boosting Framework for Achieving Fast and Provable Adversarial Robustness](https://mlsanity.com/paper/2103.01276/) (2021)
- [A Manifold View of Adversarial Risk](https://mlsanity.com/paper/2203.13277/) (2022)
- [Learning-Augmented Robust Algorithmic Recourse](https://mlsanity.com/paper/2410.01580/) (2024)
- [Optimal Robust Recourse with Lp-Bounded Model Change](https://mlsanity.com/paper/2509.21293/) (2025)
- [Computational Asymmetries in Robust Classification](https://mlsanity.com/paper/2306.14326/) (2023)
- [Adversarial Attacks to Latent Representations of Distributed Neural Networks in Split Computing](https://mlsanity.com/paper/2309.17401/) (2023)
- [Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks](https://mlsanity.com/paper/2310.04916/) (2023)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries](https://mlsanity.com/paper/2104.08382/) (2021)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)
- [MBGDT:Robust Mini-Batch Gradient Descent](https://mlsanity.com/paper/2206.07139/) (2022)

## Abstract (arXiv)

We study the design of computationally efficient algorithms with provable guarantees, that are robust to adversarial (test time) perturbations. While there has been an proliferation of recent work on this topic due to its connections to test time robustness of deep networks, there is limited theoretical understanding of several basic questions like (i) when and how can one design provably robust learning algorithms? (ii) what is the price of achieving robustness to adversarial examples in a computationally efficient manner? The main contribution of this work is to exhibit a strong connection between achieving robustness to adversarial examples, and a rich class of polynomial optimization problems, thereby making progress on the above questions. In particular, we leverage this connection to (a) design computationally efficient robust algorithms with provable guarantees for a large class of hypothesis, namely linear classifiers and degree-2 polynomial threshold functions (PTFs), (b) give a precise characterization of the price of achieving robustness in a computationally efficient manner for these classes, (c) design efficient algorithms to certify robustness and generate adversarial attacks in a principled manner for 2-layer neural networks. We empirically demonstrate the effectiveness of these attacks on real data.