# Interval Universal Approximation for Neural Networks

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

## Key facts

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

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

- [Understanding Certified Training with Interval Bound Propagation](https://mlsanity.com/paper/2306.10426/) (2023)
- [A Quantitative Geometric Approach to Neural-Network Smoothness](https://mlsanity.com/paper/2203.01212/) (2022)
- [Expressivity of ReLU-Networks under Convex Relaxations](https://mlsanity.com/paper/2311.04015/) (2023)
- [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)
- [Functional Homotopy: Smoothing Discrete Optimization via Continuous Parameters for LLM Jailbreak Attacks](https://mlsanity.com/paper/2410.04234/) (2024)
- [A Tale of Two Approximations: Tightening Over-Approximation for DNN Robustness Verification via Under-Approximation](https://mlsanity.com/paper/2305.16998/) (2023)
- [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)
- [Exact Upper and Lower Bounds for the Output Distribution of Neural Networks with Random Inputs](https://mlsanity.com/paper/2502.11672/) (2025)
- [Efficient Symbolic Reasoning for Neural-Network Verification](https://mlsanity.com/paper/2303.13588/) (2023)
- [Inferring Data Preconditions from Deep Learning Models for Trustworthy Prediction in Deployment](https://mlsanity.com/paper/2401.14628/) (2024)
- [Towards Global Neural Network Abstractions with Locally-Exact Reconstruction](https://mlsanity.com/paper/2210.12054/) (2022)
- [Taming Reachability Analysis of DNN-Controlled Systems via Abstraction-Based Training](https://mlsanity.com/paper/2211.11127/) (2022)

## Abstract (arXiv)

To verify safety and robustness of neural networks, researchers have successfully applied abstract interpretation, primarily using the interval abstract domain. In this paper, we study the theoretical power and limits of the interval domain for neural-network verification. First, we introduce the interval universal approximation (IUA) theorem. IUA shows that neural networks not only can approximate any continuous function f (universal approximation) as we have known for decades, but we can find a neural network, using any well-behaved activation function, whose interval bounds are an arbitrarily close approximation of the set semantics of f (the result of applying f to a set of inputs). We call this notion of approximation interval approximation. Our theorem generalizes the recent result of Baader et al. (2020) from ReLUs to a rich class of activation functions that we call squashable functions. Additionally, the IUA theorem implies that we can always construct provably robust neural networks under ℓ_∞-norm using almost any practical activation function. Second, we study the computational complexity of constructing neural networks that are amenable to precise interval analysis. This is a crucial question, as our constructive proof of IUA is exponential in the size of the approximation domain. We boil this question down to the problem of approximating the range of a neural network with squashable activation functions. We show that the range approximation problem (RA) is a Delta2-intermediate problem, which is strictly harder than mathsfNP-complete problems, assuming mathsfcoNPnotsubset mathsfNP. As a result, IUA is an inherently hard problem: No matter what abstract domain or computational tools we consider to achieve interval approximation, there is no efficient construction of such a universal approximator.