BERN-NN: Tight Bound Propagation For Neural Networks Using Bernstein Polynomial Interval Arithmetic

Wael Fatnassi, Haitham Khedr, Valen Yamamoto, Yasser Shoukry

Abstract

Verifying the safety of neural networks (NNs) is a critical challenge, particularly in safety-critical domains like autonomous systems. This paper introduces BERN-NN, a novel framework that utilizes Bernstein polynomials to perform bound propagation. By leveraging the unique mathematical properties of these polynomials and encoding them as multi-dimensional tensors for GPU acceleration, BERN-NN achieves output bounds that are significantly tighter and often faster to compute than state-of-the-art linear relaxation methods like $\alpha$-CROWN.

Introduction

Neural network verification requires determining the range of possible outputs given a range of possible inputs—a process known as bound propagation. Because NNs are highly non-linear and non-convex, finding exact output ranges is NP-hard. Most current tools rely on linear relaxations (over-approximations) that draw simple "sandwiches" around non-linear functions like ReLU. However, these linear approximations introduce significant "slack" or error that accumulates across layers, leading to loose bounds that may fail to prove a system's safety.

Methodology

BERN-NN addresses this by replacing linear approximations with higher-order Bernstein polynomials. Unlike Taylor series, Bernstein polynomials can uniformly approximate any continuous function, including the non-differentiable ReLU.

The Secret Sauce: Bernstein Polynomials

Bernstein polynomials possess a "Range Enclosing Property": the minimum and maximum values of the polynomial over a specific domain are guaranteed to be contained within the range of its coefficients. This allows for the efficient calculation of tight bounds. As shown in the figure below, increasing the degree ($L$) of the polynomial allows for a much closer fit to the ReLU function compared to linear methods.

Bernstein polynomial approximations of the ReLU function (left) and their corresponding error functions (right) for various degrees L.

GPU-Accelerated Tensors and Complexity Management

To overcome the computational overhead of polynomial arithmetic, the authors encode Bernstein polynomials as multi-dimensional tensors. This enables the use of standard GPU-accelerated libraries like PyTorch for additions, multiplications, and power operations. To maintain scalability, the framework includes a linearization parameter ($Lin$), which allows the user to periodically "reset" polynomials to a linear form, balancing the trade-off between bound tightness and speed.

Key Results

BERN-NN was evaluated against standard control benchmarks and randomly generated networks. The results demonstrate a significant improvement over existing linear relaxation techniques.

  • Tighter Bounds: The non-convex nature of higher-order Bernstein polynomials allows them to fit the ReLU function more snugly than linear convexification. As illustrated below, the "slack" (represented by the shaded area $A$) is significantly reduced when using Bernstein polynomials ($A_1$) compared to standard linear bounds ($A_2, A_3$).
  • Performance: Compared to $\alpha$-CROWN, BERN-NN achieved an average 25% reduction in execution time and a 10% reduction in the volume of output bounds.
  • Scalability: The tool successfully processed networks with over 1,000 neurons in under two minutes.
Comparison of the approximation error (slack area A) between Bernstein polynomials (left) and two common linear relaxation methods (middle and right).

Conclusion and Future Work

BERN-NN represents a significant step forward in NN verification by demonstrating that polynomial-based methods can be both tighter and faster than linear relaxations when properly accelerated. While high-dimensional input spaces (like large images) remain a challenge due to memory constraints, the framework's ability to handle complex controllers and large-scale networks makes it a powerful tool for safety-critical verification.

Summary updated

BibTeX
@inproceedings{fatnassi2023bern,
  author = {Wael Fatnassi and Haitham Khedr and Valen Yamamoto and Yasser Shoukry},
  title = {{BERN-NN: Tight Bound Propagation For Neural Networks Using Bernstein Polynomial Interval Arithmetic}},
  booktitle = {HSCC},
  year = {2023},
  doi = {10.1145/3575870.3587126},
}
Figure