🤖 machine learning

Floating-Point Neural Networks Are Provably Robust Universal Approximators

This paper establishes the first Interval Universal Approximation theorem for floating-point neural networks, proving that they can perfectly approximate the direct image map of any rounded target function and thereby guaranteeing the existence of provably robust networks and the computational completeness of floating-point straight-line programs.

Original authors: Geonho Hwang, Wonyeol Lee, Yeachan Park, Sejun Park, Feras Saad

Published 2026-01-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Geonho Hwang, Wonyeol Lee, Yeachan Park, Sejun Park, Feras Saad

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Pixelated" Reality

Imagine you are trying to draw a perfect, smooth curve on a piece of paper. In the world of pure mathematics (the "Real Numbers" setting), you have an infinite supply of ink and can draw a line so thin it has no width. You can hit any point on the curve with absolute precision.

However, in the real world of computers, we don't have infinite ink. We have floating-point numbers. Think of these as a grid of tiny, discrete pixels. You can't draw a perfectly smooth line; you can only place dots on specific grid squares. If you try to draw a curve, it looks "jagged" or "pixelated."

For a long time, computer scientists worried that because neural networks (AI brains) run on these "pixelated" computers, they might lose their superpowers. Specifically, they worried that if you tried to make an AI that is robust (meaning it doesn't get confused by tiny, noisy changes to its input), it would be too "pixelated" to learn complex tasks accurately.

This paper says: "Don't worry. Even with the pixelated grid, the AI can still learn anything perfectly."

The Core Problem: The "Ruler" vs. The "Map"

To understand the breakthrough, we need to look at how we test if an AI is robust.

The Old Way (Real Numbers): Imagine you have a map of a city (the function you want the AI to learn). You want to prove that if you stand anywhere in a specific neighborhood (an input box), you will always end up in the same district on the map. In the old math world, you could prove this by showing the AI's "shadow" (its interval analysis) covers the neighborhood perfectly.
The New Problem (Floating Point): When you switch to a computer, the map isn't smooth anymore; it's a grid. The "neighborhood" is now a collection of specific grid squares. The old math proofs broke because they assumed you could use infinite precision. They didn't account for the fact that computers round numbers off (like rounding $0.99999$ to $1.0$).

The big question was: Can we still prove that a computer-based AI is robust and can learn any function, even with all this rounding and pixelation?

The Solution: The "Perfect Pixel Matcher"

The authors prove that yes, we can. They developed a new mathematical theorem (an "Interval Universal Approximation" theorem) specifically for floating-point numbers.

Here is the analogy:
Imagine you have a target image made of pixels (the "Rounded Target Function"). You want to build a machine (a Neural Network) that, when you feed it a box of pixels, outputs the exact same box of pixels that the target image would produce.

Previous belief: Because computers round numbers, the machine might always be slightly off. It might be "close enough," but never exactly right.
This paper's finding: The authors constructed a specific type of neural network that acts like a perfect pixel matcher. No matter how the computer rounds the numbers, this network can be built to output the exact same result as the target function for every single possible input.

The "Magic" Trick:
The paper shows that the "imperfections" of floating-point math (the rounding errors) can actually be used as features, not bugs. By carefully designing the network, the authors show that the network can "trap" the rounding errors in a way that allows it to distinguish between different grid squares perfectly. It's like using the jagged edges of the pixels to create a sharper, more precise lock and key system.

Key Takeaways (The "So What?")

1. Robustness is Possible (The "Unbreakable Shield")

In the world of AI safety, "robustness" means the AI won't be tricked by a tiny, almost invisible change to an image (like a sticker on a stop sign that makes the AI think it's a speed limit sign).

The Claim: The paper proves that if there is any ideal, robust way to classify data (even if it's not a neural network yet), we can build a neural network that is exactly that robust.
The Metaphor: If there is a perfect, unbreakable shield in theory, this paper proves we can build a physical shield out of computer code that is just as unbreakable. We don't have to sacrifice accuracy to get safety.

2. The "Identity" Surprise

Usually, if you use a very simple activation function (like the "Identity" function, where the output is just the input), a neural network is just a simple straight line. It can't learn complex curves.

The Twist: In the floating-point world, even a network using the "Identity" function can learn complex, non-linear shapes!
Why? Because the computer's rounding errors make the "straight line" wiggle and bend at the pixel level. The paper proves these wiggles are enough to approximate any function. It's like saying a straight ruler can draw a circle if you only have a grid of dots to work with and you know exactly how to round the corners.

3. The "Small Tool" Power

The paper also shows that you don't need fancy tools to simulate any computer program. You only need addition and multiplication (and constants).

The Metaphor: Imagine you have a giant, complex factory (a computer program). The paper proves that you can build a machine that does the exact same job using only a hammer and a screwdriver, provided you arrange them in the right way. This suggests that the basic math operations inside a neural network are incredibly powerful, even in the limited world of floating-point numbers.

Summary

This paper bridges the gap between mathematical theory (which assumes perfect, infinite precision) and computer reality (which uses imperfect, rounded numbers).

It tells us that the "pixelation" of computers does not limit the power of neural networks. We can still build AI systems that are:

Universal: They can learn any task.
Provably Robust: We can mathematically prove they won't be fooled by small errors or attacks.
Exact: They can match a target function perfectly, not just "close enough."

The authors have essentially handed us the blueprints to build a "perfectly robust" AI, even when running on the imperfect hardware of the real world.

Technical Summary: Floating-Point Neural Networks Are Provably Robust Universal Approximators

1. Problem Statement

The classical Universal Approximation (UA) theorem and the more recent Interval Universal Approximation (IUA) theorem establish that neural networks can approximate continuous functions and their direct image maps (intervals) with arbitrary accuracy. However, these theoretical results rely on the unrealistic assumption that neural networks operate over infinitely precise real numbers. In practice, software implementations use finite-precision floating-point arithmetic, which introduces discretization, boundedness, rounding errors, and potential overflow/underflow.

The central open question addressed by this paper is whether the IUA theorem holds in the floating-point setting. Specifically, can a floating-point neural network, when analyzed via abstract interpretation (interval domain), perfectly capture the direct image map of a rounded target function? Previous work has not established this, largely because the rounding errors inherent in floating-point operations invalidate the proof techniques used for real-valued networks (e.g., the construction of specific subnetworks relying on exact arithmetic fails due to rounding).

2. Methodology

The authors develop a rigorous theoretical framework to bridge the gap between real-valued theory and floating-point practice.

2.1 Formalization of Floating-Point Semantics

The paper defines neural networks as functions over the set of finite floating-point numbers $\mathcal{F}$ , utilizing IEEE-754 compliant operations ( $\oplus, \ominus, \otimes$ ) with "round to nearest (ties to even)" mode. The interval semantics $\nu^\sharp$ is defined over abstract intervals $\langle a, b \rangle$ , representing the set of floats within $[a, b]$ .

2.2 Conditions on Activation Functions

To prove the theorem, the authors introduce Condition 1, a set of constraints on the activation function $\sigma: \mathcal{F} \to \mathcal{F}$ . These conditions ensure the function can:

Output exact zero and a specific non-zero value within a bounded range.
Exhibit monotonicity or specific thresholding behavior around a critical value $\eta$ .
Satisfy a Lipschitz-like continuity constraint to prevent unbounded growth.

The paper demonstrates that the correctly rounded versions of common activation functions (ReLU, GELU, Sigmoid, Tanh, etc.) satisfy these conditions, often by leveraging Lemma 1, which maps properties of real-valued functions to their floating-point counterparts.

2.3 Proof Strategy: Separability and Indicator Construction

The core of the proof involves constructing a neural network that acts as a "universal interval approximator." The methodology proceeds in two main stages:

Separability: The authors define a property called $([a, b]_\mathcal{F}, \eta, K, L_\phi, L_\psi)$ -separability. This property guarantees the existence of networks that can implement scaled indicator functions (e.g., mapping inputs $\le z$ to 0 and inputs $> z$ to $K$ ) under interval semantics.
- The proof constructs specific subnetworks (e.g., $\mu_z$ , $\tau_{\theta, \theta'}$ ) that exploit rounding errors to "contract" intervals. For instance, a network is designed such that inputs in a specific range map to a singleton interval $\langle \eta, \eta \rangle$ or $\langle \eta^+, \eta^+ \rangle$ after passing through the activation function.
- Crucially, the construction avoids infinite values in intermediate layers, addressing the overflow issues that plague real-valued proofs when scaling weights to arbitrary magnitudes.
Composition for Universal Approximation: Using the separability property, the authors construct networks for:
- Indicator functions of arbitrary boxes.
- Indicator functions of arbitrary subsets of the input space.
- Finally, the target function itself, by expressing it as a floating-point linear combination of these indicator functions. The proof carefully manages floating-point summation to ensure the accumulated rounding errors align perfectly to reconstruct the target function's image map.

3. Key Contributions

3.1 The Floating-Point IUA Theorem (Theorem 1)

The paper proves that for any target function $f: \mathbb{R}^d \to \mathbb{R}$ and a broad class of activation functions satisfying Condition 1, there exists a floating-point neural network $\nu$ such that its interval semantics $\nu^\sharp$ exactly computes the direct image map of the rounded target function $\hat{f}$ over the domain $[-1, 1]^d \cap \mathcal{F}^d$ .

Exactness: Unlike real-valued IUA which achieves $\delta$ -approximation, the floating-point version achieves $\delta = 0$ (exact match) because the domain is finite.
Generality: The theorem holds for arbitrary target functions (not just continuous ones) and a wide range of activation functions, including the identity function (which is impossible in real-valued IUA).

3.2 Existence of Provably Robust Networks (Theorem 2)

As a corollary, the paper proves that if an ideal robust classifier exists (even if not a neural network), there exists a floating-point neural network that is provably robust via interval analysis and makes identical predictions. This resolves the question of whether fundamental limits exist on the expressiveness of provably robust networks in the floating-point setting: no such limits exist.

3.3 Floating-Point Interval-Completeness (Theorem 3)

The paper establishes a surprising result regarding computational completeness: The class of straight-line floating-point programs using only addition ( $\oplus$ ) and multiplication ( $\otimes$ ) is floating-point interval-complete. This means such simple programs can simulate the interval semantics of any terminating floating-point program that takes finite floats as input and returns finite or infinite floats. This result extends the IUA theorem to the identity activation function over the entire domain $\mathcal{F}^d$ .

4. Results and Comparisons

The paper highlights three fundamental distinctions between the new floating-point IUA theorem and previous real-valued results:

Target Functions: Real-valued IUA approximates continuous functions; Floating-point IUA exactly computes the image of any rounded target function (since the domain is finite).
Activation Functions: Real-valued IUA requires "squashable" activations (non-affine); Floating-point IUA holds even for the identity activation. This is because floating-point affine transformations are not strictly affine over the reals due to rounding errors, allowing them to break linearity and approximate non-linear behaviors.
Approximation vs. Exactness: Real-valued results provide $\delta$ -approximations; Floating-point results provide exact matches for the rounded target.

5. Significance and Claims

The authors claim this work bridges the theoretical gap between abstract interpretation-based robustness verification and practical floating-point implementations.

Theoretical Assurance: It demonstrates that the lack of state-of-the-art accuracy in provably robust networks is not due to a fundamental limitation in their expressive power, but likely due to optimization challenges or the specific verification algorithms used.
Completeness: The interval-completeness result suggests that simple arithmetic operations are sufficient to simulate complex floating-point behaviors under interval semantics, offering new insights into the computational power of floating-point programs.
Practical Relevance: By validating the IUA theorem for floating-point numbers, the paper provides a theoretical foundation for the use of interval analysis in safety-critical domains (healthcare, autonomous driving) where floating-point arithmetic is the standard.

The paper explicitly states that these are existence proofs; it does not claim that current training algorithms can easily find such networks, nor does it propose new training methods. The contribution is strictly theoretical, establishing that the "expressiveness ceiling" for provably robust floating-point networks is effectively non-existent.