# On the Paradox of Certified Training

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 51 references that are in the map.
- First posted on arXiv 12 Feb 2021.

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

- [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)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [RobustBench: a standardized adversarial robustness benchmark](https://mlsanity.com/paper/2010.09670/) (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)
- [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)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming](https://mlsanity.com/paper/2010.11645/) (2020)
- [The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification](https://mlsanity.com/paper/2006.14076/) (2020)
- [Scaling Polyhedral Neural Network Verification on GPUs](https://mlsanity.com/paper/2007.10868/) (2020)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [Universal Approximation with Certified Networks](https://mlsanity.com/paper/1909.13846/) (2019)

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

- [Understanding Certified Training with Interval Bound Propagation](https://mlsanity.com/paper/2306.10426/) (2023)
- [Expressive Losses for Verified Robustness via Convex Combinations](https://mlsanity.com/paper/2305.13991/) (2023)
- [CTBENCH: A Library and Benchmark for Certified Training](https://mlsanity.com/paper/2406.04848/) (2024)
- [TAPS: Connecting Certified and Adversarial Training](https://mlsanity.com/paper/2305.04574/) (2023)
- [Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations](https://mlsanity.com/paper/2403.07095/) (2024)
- [On Using Certified Training towards Empirical Robustness](https://mlsanity.com/paper/2410.01617/) (2024)
- [How robust accuracy suffers from certified training with convex relaxations](https://mlsanity.com/paper/2306.06995/) (2023)
- [Cross-Input Certified Training for Universal Perturbations](https://mlsanity.com/paper/2405.09176/) (2024)
- [Training Verification-Friendly Neural Networks via Neuron Behavior Consistency](https://mlsanity.com/paper/2412.13229/) (2024)
- [Learning Better Certified Models from Empirically-Robust Teachers](https://mlsanity.com/paper/2602.02626/) (2026)
- [Adaptive Certified Training: Towards Better Accuracy-Robustness Tradeoffs](https://mlsanity.com/paper/2307.13078/) (2023)
- [Improving Certified Robustness via Adversarial Distillation](https://mlsanity.com/paper/2606.31653/) (2026)

## Abstract (arXiv)

Certified defenses based on convex relaxations are an established technique for training provably robust models. The key component is the choice of relaxation, varying from simple intervals to tight polyhedra. Counterintuitively, loose interval-based training often leads to higher certified robustness than what can be achieved with tighter relaxations, which is a well-known but poorly understood paradox. While recent works introduced various improvements aiming to circumvent this issue in practice, the fundamental problem of training models with high certified robustness remains unsolved. In this work, we investigate the underlying reasons behind the paradox and identify two key properties of relaxations, beyond tightness, that impact certified training dynamics: continuity and sensitivity. Our extensive experimental evaluation with a number of popular convex relaxations provides strong evidence that these factors can explain the drop in certified robustness observed for tighter relaxations. We also systematically explore modifications of existing relaxations and discover that improving unfavorable properties is challenging, as such attempts often harm other properties, revealing a complex tradeoff. Our findings represent an important first step towards understanding the intricate optimization challenges involved in certified training.