# Expressive Losses for Verified Robustness via Convex Combinations

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 85 references that are in the map.
- First posted on arXiv 23 May 2023.

## Builds on (most cited first, 30 of 58)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets](https://mlsanity.com/paper/1707.08819/) (2017)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Adversarial Risk and the Dangers of Evaluating Against Weak Attacks](https://mlsanity.com/paper/1802.05666/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers](https://mlsanity.com/paper/2011.13824/) (2020)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [Branch and Bound for Piecewise Linear Neural Network Verification](https://mlsanity.com/paper/1909.06588/) (2019)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [General Cutting Planes for Bound-Propagation-Based Neural Network Verification](https://mlsanity.com/paper/2208.05740/) (2022)

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

- [Understanding Certified Training with Interval Bound Propagation](https://mlsanity.com/paper/2306.10426/) (2023)
- [CTBENCH: A Library and Benchmark for Certified Training](https://mlsanity.com/paper/2406.04848/) (2024)
- [Expressivity of ReLU-Networks under Convex Relaxations](https://mlsanity.com/paper/2311.04015/) (2023)
- [Adversarial Attacks Leverage Interference Between Features in Superposition](https://mlsanity.com/paper/2510.11709/) (2025)
- [Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations](https://mlsanity.com/paper/2403.07095/) (2024)
- [Faster Verified Explanations for Neural Networks](https://mlsanity.com/paper/2512.00164/) (2025)
- [On Using Certified Training towards Empirical Robustness](https://mlsanity.com/paper/2410.01617/) (2024)
- [Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification](https://mlsanity.com/paper/2410.06816/) (2024)
- [BEAVER: An Efficient Deterministic LLM Verifier](https://mlsanity.com/paper/2512.05439/) (2025)
- [Towards Generalized Certified Robustness with Multi-Norm Training](https://mlsanity.com/paper/2410.03000/) (2024)
- [Average Certified Radius is a Poor Metric for Randomized Smoothing](https://mlsanity.com/paper/2410.06895/) (2024)
- [A Scalable Approach to Probabilistic Neuro-Symbolic Robustness Verification](https://mlsanity.com/paper/2502.03274/) (2025)
- [On the Security Risks of ML-based Malware Detection Systems: A Survey](https://mlsanity.com/paper/2505.10903/) (2025)
- [Bridging Efficiency and Safety: Formal Verification of Neural Networks with Early Exits](https://mlsanity.com/paper/2512.20755/) (2025)
- [Learning Better Certified Models from Empirically-Robust Teachers](https://mlsanity.com/paper/2602.02626/) (2026)
- [Support is All You Need for Certified VAE Training](https://mlsanity.com/paper/2504.11831/) (2025)
- [Compression Aware Certified Training](https://mlsanity.com/paper/2506.11992/) (2025)
- [Lipschitz-aware Linearity Grafting for Certified Robustness](https://mlsanity.com/paper/2510.25130/) (2025)
- [Dual Randomized Smoothing: Beyond Global Noise Variance](https://mlsanity.com/paper/2512.01782/) (2025)
- [Rethinking Evaluation Paradigms in IBP-based Certified Training](https://mlsanity.com/paper/2606.02134/) (2026)
- [Hybrid Robustness Verification for Spatio-Temporal Neural Networks](https://mlsanity.com/paper/2606.09746/) (2026)
- [Improving Certified Robustness via Adversarial Distillation](https://mlsanity.com/paper/2606.31653/) (2026)
- [Certified Training for Convolutional Perturbations](https://mlsanity.com/paper/2607.18195/) (2026)

## Abstract (arXiv)

In order to train networks for verified adversarial robustness, it is common to over-approximate the worst-case loss over perturbation regions, resulting in networks that attain verifiability at the expense of standard performance. As shown in recent work, better trade-offs between accuracy and robustness can be obtained by carefully coupling adversarial training with over-approximations. We hypothesize that the expressivity of a loss function, which we formalize as the ability to span a range of trade-offs between lower and upper bounds to the worst-case loss through a single parameter (the over-approximation coefficient), is key to attaining state-of-the-art performance. To support our hypothesis, we show that trivial expressive losses, obtained via convex combinations between adversarial attacks and IBP bounds, yield state-of-the-art results across a variety of settings in spite of their conceptual simplicity. We provide a detailed analysis of the relationship between the over-approximation coefficient and performance profiles across different expressive losses, showing that, while expressivity is essential, better approximations of the worst-case loss are not necessarily linked to superior robustness-accuracy trade-offs.