# Universal Approximation with Certified Networks

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

## Key facts

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

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

- [A Review of Formal Methods applied to Machine Learning](https://mlsanity.com/paper/2104.02466/) (2021)
- [Understanding Certified Training with Interval Bound Propagation](https://mlsanity.com/paper/2306.10426/) (2023)
- [On the Paradox of Certified Training](https://mlsanity.com/paper/2102.06700/) (2021)
- [On the Convergence of Certified Robust Training with Interval Bound Propagation](https://mlsanity.com/paper/2203.08961/) (2022)
- [The Fundamental Limits of Interval Arithmetic for Neural Networks](https://mlsanity.com/paper/2112.05235/) (2021)
- [Complexity of Injectivity and Verification of ReLU Neural Networks](https://mlsanity.com/paper/2405.19805/) (2024)
- [Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification](https://mlsanity.com/paper/2410.06816/) (2024)
- [DISCO Verification: Division of Input Space into COnvex polytopes for neural network verification](https://mlsanity.com/paper/2105.07776/) (2021)
- [Efficient Symbolic Reasoning for Neural-Network Verification](https://mlsanity.com/paper/2303.13588/) (2023)

## Abstract (arXiv)

Training neural networks to be certifiably robust is critical to ensure their safety against adversarial attacks. However, it is currently very difficult to train a neural network that is both accurate and certifiably robust. In this work we take a step towards addressing this challenge. We prove that for every continuous function f, there exists a network n such that: (i) n approximates f arbitrarily close, and (ii) simple interval bound propagation of a region B through n yields a result that is arbitrarily close to the optimal output of f on B. Our result can be seen as a Universal Approximation Theorem for interval-certified ReLU networks. To the best of our knowledge, this is the first work to prove the existence of accurate, interval-certified networks.