DeepBern-Nets: Taming the Complexity of Certifying Neural Networks using
  Bernstein Polynomial Activations and Precise Bound Propagation
Formal certification of Neural Networks (NNs) is crucial for ensuring their
safety, fairness, and robustness. Unfortunately, on the one hand, sound and
complete certification algorithms of ReLU-based NNs do not scale to large-scale
NNs. On the other hand, incomplete certification algorithms are easier to
compute, but they result in loose bounds that deteriorate with the depth of NN,
which diminishes their effectiveness. In this paper, we ask the following
question; can we replace the ReLU activation function with one that opens the
door to incomplete certification algorithms that are easy to compute but can
produce tight bounds on the NN's outputs? We introduce DeepBern-Nets, a class
of NNs with activation functions based on Bernstein polynomials instead of the
commonly used ReLU activation. Bernstein polynomials are smooth and
differentiable functions with desirable properties such as the so-called range
enclosure and subdivision properties. We design a novel algorithm, called
Bern-IBP, to efficiently compute tight bounds on DeepBern-Nets outputs. Our
approach leverages the properties of Bernstein polynomials to improve the
tractability of neural network certification tasks while maintaining the
accuracy of the trained networks. We conduct comprehensive experiments in
adversarial robustness and reachability analysis settings to assess the
effectiveness of the proposed Bernstein polynomial activation in enhancing the
certification process. Our proposed framework achieves high certified accuracy
for adversarially-trained NNs, which is often a challenging task for certifiers
of ReLU-based NNs. Moreover, using Bern-IBP bounds for certified training
results in NNs with state-of-the-art certified accuracy compared to ReLU
networks. This work establishes Bernstein polynomial activation as a promising
alternative for improving NN certification tasks across various applications.
Haitham Khedr, Yasser Shoukry
DeepBern-Nets: Taming the Complexity of Certifying Neural Networks using Bernstein Polynomial Activations and Precise Bound Propagation

###### Abstract

Formal certification of Neural Networks (NNs) is crucial for ensuring their safety, fairness, and robustness. Unfortunately, on the one hand, sound and complete certification algorithms of ReLU-based NNs do not scale to large-scale NNs. On the other hand, incomplete certification algorithms--based on propagating input domain bounds to bound the outputs of the NN--are easier to compute, but they result in loose bounds that deteriorate with the depth of NN, which diminishes their effectiveness. In this paper, we ask the following question; can we replace the ReLU activation function with one that opens the door to incomplete certification algorithms that are easy to compute but can produce tight bounds on the NN's outputs? We introduce DeepBern-Nets, a class of NNs with activation functions based on Bernstein polynomials instead of the commonly used ReLU activation. Bernstein polynomials are smooth and differentiable functions with desirable properties such as the so-called range enclosure and subdivision properties. We design a novel Interval Bound Propagation (IBP) algorithm, called Bern-IBP, to efficiently compute tight bounds on DeepBern-Nets outputs. Our approach leverages the properties of Bernstein polynomials to improve the tractability of neural network certification tasks while maintaining the accuracy of the trained networks. We conduct comprehensive experiments in adversarial robustness and reachability analysis settings to assess the effectiveness of the proposed Bernstein polynomial activation in enhancing the certification process. Our proposed framework achieves high certified accuracy for adversarially-trained NNs, which is often a challenging task for certifiers of ReLU-based NNs. Moreover, using Bern-IBP bounds for certified training results in NNs with state-of-the-art certified accuracy compared to ReLU networks. This work establishes Bernstein polynomial activation as a promising alternative for improving neural network certification tasks across various NNs applications. The code for DeepBern-Nets is publicly available1.

Footnote 1: [https://github.com/rcpsl/DeepBern-Nets](https://github.com/rcpsl/DeepBern-Nets)

## 1 Introduction

Deep neural networks (NNs) have revolutionized numerous fields with their remarkable performance on various tasks, ranging from computer vision and natural language processing to healthcare and robotics. As these networks become integral components of critical systems, ensuring their safety, security, fairness, and robustness is essential. It is unsurprising, then, the growing interest in the field of certified machine learning, which resulted in NNs with enhanced levels of robustness to adversarial inputs [1; 2; 3; 4], fairness [5; 6; 7; 8], and correctness [9].
While certifying the robustness, fairness, and correctness of NNs with respect to formal properties is shown to be NP-hard [10], state-of-the-art certifiers rely on computing upper/lower bounds on the output of the NN and its intermediate layers [11; 12; 13; 14; 15]. Accurate bounds can significantly reduce the complexity and computational effort required during the certification process, facilitating more efficient and dependable evaluations of the network's behavior in diverse and challenging scenarios. Moreover, computing such bounds has opened the door for a new set of "certified training" algorithms [16; 17; 18] where these bounds are used as a regularizer that penalizes the worst-case violation of robustness or fairness, which leads to training NNs with favorable properties. While computing such lower/upper bounds is crucial, current techniques in computing lower/upper bounds on the NN outputs are either computationally efficient but result in loose lower/upper bounds or compute tight bounds but are computationally expensive. In this paper, we are interested in algorithms that can be both computationally efficient and lead to tight bounds.

This work follows a Design-for-Certifiability approach where we ask the question; can we replace the ReLU activation function with one that allows us to compute tight upper/lower bounds efficiently? Introducing such novel activation functions designed with certifiability in mind makes it possible to create NNs that are easier to analyze and certify during their training. Our contributions in this paper can be summarized as follows:

1. We introduce DeepBern-Nets, a NN architecture with a new activation function based on Bernstein polynomials. Our primary motivation is to shift some of the computational efforts from the certification phase to the training phase. By employing this approach, we can train NNs with known output (and intermediate) bounds for a predetermined input domain which can accelerate the certification process.
2. We present Bern-IBP, an Interval Bound Propagation (IBP) algorithm that computes tight bounds of DeepBern-Nets leading to an efficient certifier.
3. We show that Bern-IBP can certify the adversarial robustness of adversarially-trained DeepBern-Nets on MNIST and CIFAR-10 datasets even with large architectures with millions of parameters. This is unlike state-of-the-art certifiers for ReLU networks, which often fail to certify robustness for adversarially-trained ReLU NNs.
4. We show that employing Bern-IBP during the training of DeepBern-Nets yields high certified robustness on the MNIST and CIFAR-10 datasets with robustness levels that are comparable--or in many cases surpassing--the performance of the most robust ReLU-based NNs reported in the SOK benchmark.

We believe that our framework, DeepBern-Nets and Bern-IBP, enables more reliable guarantees on NN behavior and contributes to the ongoing efforts to create safer and more secure NN-based systems, which is crucial for the broader deployment of deep learning in real-world applications.

## 2 DeepBern-Nets: Deep Bernstein Polynomial Networks

### Bernstein polynomials preliminaries

Bernstein polynomials form a basis for the space of polynomials on a closed interval [19]. These polynomials have been widely used in various fields, such as computer-aided geometric design [19], approximation theory [20], and numerical analysis [21], due to their unique properties and intuitive representation of functions. A general polynomial of degree \(n\) in Bernstein form on the interval \([l,u]\) can be represented as:

\[P_{n}^{[l,u]}(x)=\sum_{k=0}^{n}c_{k}b_{n,k}^{[l,u]}(x),\qquad x\in[l,u] \tag{1}\]

where \(c_{k}\in\mathbb{R}\) are the coefficients associated with the Bernstein basis \(b_{n,k}^{[l,u]}(x)\), defined as:

\[b_{n,k}^{[l,u]}(x)=\frac{\binom{n}{k}}{(u-l)^{n}}(x-l)^{k}(u-x)^{n-k}, \tag{2}\]

with \(\binom{n}{k}\) denoting the binomial coefficient. The Bernstein coefficients \(c_{k}\) determine the shape and properties of the polynomial \(P_{n}^{[l,u]}(x)\) on the interval \([l,u]\). It is important to note that unlike
polynomials represented in power basis form, the representation of a polynomial in Bernstein form depends on the domain of interest \([l,u]\) as shown in equation 1.

### Neural Networks with Bernstein activation functions

We propose using Bernstein polynomials as non-linear activation functions \(\sigma\) in feed-forward NNs. We call such NNs as DeepBern-Nets. Like feed-forward NNs, DeepBern-Nets consist of multiple layers, each consisting of linear weights followed by non-linear activation functions. Unlike conventional activation functions (e.g., ReLU, sigmoid, tanh,.), Bernstein-based activation functions are parametrized with learnable Bernstein coefficients \(\mathbf{c}=c_{0},\ldots,c_{n}\), i.e.,

\[\sigma(x;l,u,\mathbf{c})=\sum_{k=0}^{n}c_{k}b_{n,k}^{[l,u]}(x),\qquad x\in[l,u], \tag{3}\]

where \(x\) is the input to the neuron activation, and the polynomial degree \(n\) is an additional hyperparameter of the Bernstein activation and can be chosen differently for each neuron. Figure 1 shows a simplified computational graph of the Bernstein activation and how it is used to replace conventional activation functions.

Training of DeepBern-Nets.Since Bernstein polynomials are defined on a specific domain (equation 2), we need to determine the lower and upper bounds (\(\mathbf{l}^{(k)}\) and \(\mathbf{u}^{(k)}\)) of the inputs to the Bernstein activation neurons in layer \(k\), during the training of the network. To that end, we assume that the input domain \(\mathcal{D}\) is bounded with the lower and upper bounds (denoted as \(\mathbf{l}^{(0)}\) and \(\mathbf{u}^{(0)}\), respectively) known during training. We emphasize that our assumption that \(\mathcal{D}\) is bounded and known is not conservative, as the input to the NN can always be normalized to \([0,1]\), for example.

Using the bounds on the input domain \(\mathbf{l}^{(0)}\) and \(\mathbf{u}^{(0)}\) and the learnable parameters of the NNs (i.e., weights of the linear layers and the Bernstein coefficients \(\mathbf{c}\) for each neuron), we will update the bounds \(\mathbf{l}^{(k)}\) and \(\mathbf{u}^{(k)}\) with each step of training by propagating \(\mathbf{l}^{(0)}\) and \(\mathbf{u}^{(0)}\) through all the layers in the network. Unlike conventional non-linear activation functions where symbolic bound propagation relies on linear relaxation techniques [22; 23], the Bernstein polynomial enclosure property allows us to bound the output of an \(n\)-th order Bernstein activation in \(\mathcal{O}(n)\) operations (Algorithm 1-line 12). We start by reviewing the enclosure property of Bernstein polynomials as follows.

**Property 1** (Enclosure of Range [24]).: The enclosure property of Bernstein polynomials states that for a given polynomial \(P_{n}^{[l,u]}(x)\) of degree \(n\) in Bernstein form on an interval \([l,u]\), the polynomial lies within the convex hull of its Bernstein coefficients. In other words, the Bernstein polynomial is bounded by the minimum and maximum values of its coefficients \(c_{k}\) regardless of the input \(x\).

\[\min_{0\leq k\leq n}c_{k}\leq P_{n}^{[l,u]}(x)\leq\max_{0\leq k\leq n}c_{k}, \qquad\forall x\in[l,u]. \tag{4}\]

Algorithm 1 outlines how to use the enclosure property to propagate the bounds from one layer to another for a single training step in an L-layer DeepBern-Net. In contrast to normal training, we

Figure 1: (Left) shows the structure of a DeepBern-Nets with two hidden layers. DeepBern-Nets are similar to Feed Forward NNs except that the activation function is a Bernstein polynomial. (Right) shows a simplified computational graph of a degree \(n\) Bernstein activation. The Bernstein basis is evaluated at the input \(x\) using \(l\) and \(u\) computed during training, and the output is then computed as a linear combination of the basis functions weighted by the learnable Bernstein coefficients \(c_{k}\).
calculate the worst-case bounds for the inputs to all Bernstein layers by propagating the bounds from the previous layers. Such bound propagation can be done for linear layers using interval arithmetic [25]--referred to in Algorithm 1-line 16 as Interval Bound Propagation (IBP)--or using Property 1 for Bernstein layers (Algorithm 1-line 12). We store the resulting bounds for each Bernstein activation function. Then, we perform the regular forward step. The parameters are then updated using vanilla backpropagation, just like conventional NNs. During inference, we directly use the stored layer-wise bounds \(\mathbf{l}^{(k)}\) and \(\mathbf{u}^{(k)}\) (computed during training) to propagate any input through the network. In Appendix C.3, we show that the overhead of computing the bounds \(\mathbf{l}^{(k)}\) and \(\mathbf{u}^{(k)}\) during training adds between \(0.2\times\) to \(5\times\) overhead for the training, depending on the order \(n\) of the Bernstein activation function and the size of the network.

Stable training of DeepBern-Nets.Using polynomials as activation functions in deep NNs has attracted several researchers' attention in recent years [26, 27]. A major drawback of using polynomials of arbitrary order is their unstable behavior during training due to exploding gradients-which is prominent with the increase in order [27]. In particular, for a general \(n\)th order polynomial in power series \(f_{n}(x)=w_{0}+w_{1}x+\ldots+w_{n}x^{n}\), its derivative is \(df_{n}(x)/dx=w_{1}+\ldots+nw_{n}x^{n-1}\). Hence training a deep NN with multiple polynomial activation functions suffers from exploding gradients as the gradient scales exponentially with the increase in the order \(n\) for \(x>1\).

Luckily, and thanks to the unique properties of Bernstein polynomials, DeepBern-Net does not suffer from such a limitation as captured in the next result, whose proof is given in Appendix A.1.

**Proposition 2.1**.: Consider the Bernstein activation function \(\sigma(x;l,u,\mathbf{c})\) of arbitrary order \(n\). The following holds:

1. \(\left|\frac{d}{dx}\sigma(x;l,u,\mathbf{c})\right|\leq 2n\max_{k\in\{0,\ldots,n\}}|c _{k}|\),
2. \(\left|\frac{d}{dc_{i}}\sigma(x;l,u,\mathbf{c})\right|\leq 1\) for all \(i\in\{0,\ldots,n\}\).

```
1:Given: Training Batch (\(\mathcal{X},\mathbf{t}\)) and input bounds \([\mathbf{l}^{(0)},\mathbf{u}^{(0)}]\)
2:Initialize all parameters
3:Set the learning rate \(\alpha\)
4:\(\triangleright\) Forward propagation
5:Set \(\mathbf{y}^{(0)}=\mathcal{X}\)
6:Set \(\mathcal{B}^{(0)}=[\mathbf{l}^{(0)},\mathbf{u}^{(0)}]\)
7:for\(i\) = 1....Ldo
8:if\(layer\)\(i\) is Bernstein activation then
9:\(\mathbf{l}^{(i)},\mathbf{u}^{(i)}\leftarrow\mathcal{B}^{(i-1)}\)\(\triangleright\) Store Input bounds of the Bernstein layer
10:for each neuron \(z\) in \(layer\)\(i\)do
11: Let \(\mathbf{c}^{(\mathbf{z})}_{\mathbf{z}}\) be the Bernstein coefficients for neuron \(z\) of the \(i\)-th layer
12:\(\mathcal{B}^{(i)}_{z}\leftarrow[\min_{j}c^{(i)}_{zj},\max_{j}c^{(i)}_{zj}]\)
13:endfor
14:\(\mathcal{B}^{(i)}\leftarrow[\mathcal{B}^{(i)}_{0},\mathcal{B}^{(i)}_{1},..., \mathcal{B}^{(i)}_{m}]\)\(\triangleright\)\(m\) denotes the number of neurons in layer \(i\)
15:else
16:\(\mathcal{B}^{(i)}\leftarrow\)IBP(\(\mathcal{B}^{(i-1)}\))
17:endif
18:\(\mathbf{y}^{(i)}\leftarrow\) forward(\(\mathbf{y}^{(i-1)}\))\(\triangleright\) Regular forward step
19:endfor
20:\(\triangleright\) Backpropagation
21:Compute the loss function: \(\mathcal{L}(\mathbf{y}^{(L)},\mathbf{t})\)
22:Compute the gradients with respect to all model parameters (including Bernstein coefficients)
23:for each Parameter \(\theta\)do\(\triangleright\) Weights, biases, and Bernstein coefficients \(c_{k}\)
24:\(\theta\leftarrow\theta-\alpha\nabla_{\theta}\mathcal{L}\)
25:endfor
```

**Algorithm 1** Training step of an L-layer DeepBern-Net \(\mathcal{NN}\)
Proposition 2.1 ensures that the gradients of the proposed Bernstein-based activation function depend only on the value of the learnable parameters \(\mathbf{c}=(c_{0},\ldots,c_{n})\). Hence, the gradients do not explode for \(x>1\). This feature is not enjoyed by the polynomial activation functions in [27] and leads to better stable training properties when the Bernstein polynomials are used as activation functions. Moreover, one can control these gradients by adding a regularizer-to the objective function-that penalizes high values of \(c_{k}\), which is common for other learnable parameters, i.e., weights of the linear layer. Proof of Proposition 2.1 is in Appendix A.1

## 3 Bern-IBP: Certification using Bernstein Interval Bound Propagation

### Certification of global properties using Bern-IBP

We consider the certification of global properties of NNs. Global properties need to be held true for the entire input domain \(\mathcal{D}\) of the network. For simplicity of presentation, we will assume that the global property we want to prove takes the following form:

\[\forall\mathbf{y^{(0)}}\in\mathcal{D}\Longrightarrow y^{(L)}=\mathcal{N}\mathcal{ N}(\mathbf{y}^{(0)})>0 \tag{5}\]

where \(y^{(L)}\) is a scalar output and \(\mathcal{N}\mathcal{N}\) is the NN of interest. Examples of such global properties include the stability of NN-controlled systems [28] as well as global individual fairness [8].

In this paper, we focus on the incomplete certification of such properties. In particular, we certify properties of the form (5) by checking the lower/upper bounds of the NN. To that end, we define the lower \(\mathcal{L}\) and upper \(\mathcal{U}\) bounds of the NN within the domain \(\mathcal{D}\) as any real numbers that satisfy:

\[\mathcal{L}\left(\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}),\mathcal{D}\right)\leq \min_{\mathbf{y}^{(0)}\in\mathcal{D}}\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}),\qquad \mathcal{U}\left(\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}),\mathcal{D}\right)\geq \max_{\mathbf{y}^{(0)}\in\mathcal{D}}\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}) \tag{6}\]

Incomplete certification of (5) is equivalent to checking if \(\mathcal{L}\left(\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}),\mathcal{D}\right)>0\). Thanks to the Enclosure of Range (Property 1) of DeepBern-Nets, one can check the condition \(\mathcal{L}\left(\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}),\mathcal{D}\right)>0\) in constant time, i.e., \(\mathcal{O}(1)\), by simply checking the minimum Bernstein coefficients of the output layer.

### Certification of local properties using Bern-IBP

Local properties of NNs are the ones that need to be held for subsets \(S\) of the input domain \(\mathcal{D}\), i.e.,

\[\forall\mathbf{y^{(0)}}\in S\subset\mathcal{D}\Longrightarrow y^{(L)}=\mathcal{N }\mathcal{N}(\mathbf{y}^{(0)})>0 \tag{7}\]

Examples of local properties include adversarial robustness and the safety of NN-controlled vehicles [29; 30; 31]. Similar to global properties, we are interested in incomplete certification by checking whether \(\mathcal{L}\left(\mathcal{N}\mathcal{N}(\mathbf{y}^{(0)}),S\right)>0\).

The output bounds stored in the Bernstein activation functions are the worst-case bounds for the entire input domain \(\mathcal{D}\). However, for certifying local properties over \(S\subset\mathcal{D}\), we need to refine these output bounds on the given sub-region \(S\). To that end, for a Bernstein activation layer \(k\) with input bounds [\(\mathbf{l}^{(k)}\), \(\mathbf{u}^{(k)}\)] (computed and stored during training), we can obtain tighter output bounds thanks to the following subdivision property of Bernstein polynomials.

**Property 2** (Subdivision [24]).: Given a Bernstein polynomial \(P_{n}^{[l,u]}(x)\) of degree \(n\) on the interval \([l,u]\), the coefficients of the same polynomial on subintervals \([l,\alpha]\) and \([\alpha,u]\) with \(\alpha\in[l,u]\) can be computed as follows. First, compute the intermediate coefficients \(c_{j}^{k}\) for \(k=0,...,n\) and \(j=k,...,n\)

\[c_{j}^{k}=\left\{\begin{array}{ll}c_{j}&\text{if }k=0\\ (1-\tau)c_{j-1}^{k-1}+\tau c_{j}^{k-1}&\text{if }k>0\end{array}\right., \quad c_{i}^{\prime}=c_{i}^{i}\quad c_{i^{\prime}}^{\prime\prime}=c_{n}^{n-i} \quad i=0\ldots n,\]

where \(\tau=\frac{\alpha-l}{u-l}\). Next, the polynomials defined on each of the subintervals \([l,\alpha]\) and \([\alpha,u]\) are:

\[P_{n}^{[l,\alpha]}(x)=\sum_{k=0}^{n}c_{k}^{\prime}b_{n,k}^{[l,\alpha]}(x), \qquad P_{n}^{[\alpha,u]}(x)=\sum_{k=0}^{n}c_{k}^{\prime\prime}b_{n,k}^{[\alpha,u]}(x).\]
Indeed, we can apply the Subdivision property twice to compute the coefficients of the polynomial \(P_{n}^{[\alpha,\beta]}\). Computing the coefficients on the subintervals allows us to tightly bound the polynomial using property 1. Therefore, given a DeepBern-Net trained on \(\mathcal{D}=[\boldsymbol{l}^{(0)},\,\boldsymbol{u}^{(0)}]\), we can compute tighter bounds on the subregion \(S=[\boldsymbol{l}^{(0)},\,\boldsymbol{\hat{u}}^{(0)}]\) by applying the subdivision property (Property 2) to compute the Bernstein coefficients on the sub-region \(S\), and then use the enclosure property (Property 1) to compute tight bounds on the output of the activation equivalent to the minimum and maximum of the computed Bernstein coefficients. We do this on a layer-by-layer basis until we reach the output of the NN. Implementation details of this approach is given in Appendix B.

## 4 Experiments

**Implementation:** Our framework has been developed in Python, and is designed to facilitate the training of DeepBern-Nets and certify local properties such as Adversarial Robustness and certified training. We use PyTorch [32] for all neural network training tasks. To conduct our experiments, we utilized a single GeForce RTX 2080 Ti GPU in conjunction with a 24-core Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz. Only 8 cores were utilized for our experiments.

### Experiment 1: Certification of Adversarial Robustness

The first experiment assesses the ability to compute tight bounds on the NN output and its implications for certifying NN properties. To that end, we use the application of adversarial robustness, where we aim to certify that a NN model is not susceptible to adversarial examples within a defined perturbation set. The results in [33; 34] show that state-of-the-art IBP algorithms fail to certify the robustness of NNs trained with Projected Gradient Descent (PGD), albeit being robust, due to the excessive errors in the computed bounds, which forces designers to use computationally expensive sound and complete algorithms. Thanks to the properties of DeepBern-Nets, the bounds computed by Bern-IBP are tight enough to certify the robustness of NNs without using computationally expensive sound and complete tools. To that end, we trained several NNs using the MNIST [35] and CIFAR-10 [36] datasets using PGD. We trained both Fully Connected Neural Networks (FCNN) and Convolutional Neural Networks (CNNs) on these datasets with Bernstein polynomials of orders \(2,3,4,5\), and \(6\). For detailed information regarding the model architectures, please refer to Appendix C.2. Further information about the training procedure can be found in Appendix C.1.

#### 4.1.1 Formalizing adversarial robustness as a local property

Given a NN model \(\mathcal{NN}:[0,1]^{d}\rightarrow\mathbb{R}^{o}\), a concrete input \(\boldsymbol{x_{n}}\), a target class \(t\), and a perturbation parameter \(\epsilon\), the adversarial robustness problem asks that the NN output be the target class \(t\) for all the inputs in the set \(\{\boldsymbol{x}\mid\|\boldsymbol{x}-\boldsymbol{x_{n}}\|_{\infty}\leq\epsilon\}\). In other words, a NN is robust whenever:

\[\forall\boldsymbol{x}\in S(\boldsymbol{x_{n}},\epsilon)=\{\boldsymbol{x}\mid \|\boldsymbol{x}-\boldsymbol{x_{n}}\|_{\infty}\leq\epsilon\}\quad\implies \quad\mathcal{NN}(\boldsymbol{x})_{t}>\mathcal{NN}(\boldsymbol{x})_{i},\ i\neq t\]

where \(\mathcal{NN}(\boldsymbol{x})_{t}\) is the NN output for the target class and \(\mathcal{NN}(\boldsymbol{x})_{i}\) is the NN output for any class \(i\) other that \(t\). To certify the robustness of a NN, one can compute a lower bound on the adversarial robustness \(\mathbb{L}_{\text{robust}}\) for all classes \(i\neq t\) as:

\[\mathbb{L}_{\text{robust}}(\boldsymbol{x_{n}},\epsilon) =\min_{i\neq t}\left(\mathcal{L}\big{(}\mathcal{NN}(\boldsymbol{ x})_{t},S(\boldsymbol{x_{n}},\epsilon)\big{)}-\mathcal{U}\big{(}\mathcal{NN}( \boldsymbol{x})_{i},S(\boldsymbol{x_{n}},\epsilon)\big{)}\right) \tag{8}\] \[\leq\min_{i\neq t}\left(\min_{\boldsymbol{x}\in S(\boldsymbol{x_{ n}},\epsilon)}\mathcal{NN}(\boldsymbol{x})_{t}-\mathcal{NN}(\boldsymbol{x})_{i}\right) \tag{9}\]

Indeed, the NN is robust whenever \(\mathbb{L}_{\text{robust}}>0\). Nevertheless, the tightness of the bounds \(\mathcal{L}(\mathcal{NN}(\boldsymbol{x})_{t},S(\boldsymbol{x_{n}},\epsilon))\) and \(\mathcal{U}(\mathcal{NN}(\boldsymbol{x})_{i},S(\boldsymbol{x_{n}},\epsilon))\) plays a significant role in the ability to certify the NN robustness. The tighter these bounds, the higher the ability to certify the NN robustness.

#### 4.1.2 Experiment 1.1: Tightness of output bounds - Bern-IBP vs IBP

For each trained neural network, we compute the lower bound on robustness \(\mathbb{L}_{\text{robust}}(\boldsymbol{x_{n}},\epsilon)\) using Bern-IBP and using state-of-the-art Interval Bound Propagation (IBP) that does not take into account
the properties of DeepBern-Nets. In particular, for this experiment, we used auto_LiRPA[11], a tool that is part of \(\alpha\beta\)-CROWN[11]--the winner of the 2022 Verification of Neural Network (VNN) competition [34]. Figure 2 shows the difference between the bound \(\mathbb{L}_{\text{robust}}(\mathbf{x_{n}},\epsilon)\) computed by Bern-IBP and the one computed by IBP using a semi-log scale. The raw data for the adversarial robustness bound \(\mathbb{L}_{\text{robust}}(\mathbf{x_{n}},\epsilon)\) for both Bern-IBP and IBP is given in Appendix C.4.

The results presented in Figure 2 clearly demonstrate that Bern-IBP yields significantly tighter bounds in comparison to IBP. Figure 2 also shows that for all values of \(\epsilon\), the bounds computed using IBP become exponentially looser as the order of the Bernstein activations increase, unlike the bounds computed with Bern-IBP, which remain precise even for higher-order Bernstein activations or larger values of \(\epsilon\). The raw data in Appendix C.4 provide a clearer view on the superiority of computing \(\mathbb{L}_{\text{robust}}(\mathbf{x_{n}},\epsilon)\) using Bern-IBP compared to IBP.

#### 4.1.3 Experiment 1.2: Certification of Adversarial Robustness using Bern-IBP

Next, we show that the superior precision of bounds calculated using Bern-IBP can lead to efficient certification of adversarial robustness. Here, we define the certified accuracy of the NN as the percentage of the data points (in the test dataset) for which an adversarial input can not change the class (the output of the NN). Table 1 contrasts the certified accuracy for the adversarially-trained (using 100-step PGD) DeepBern-Nets of orders 2, 4, and 6, using both IBP and Bern-IBP methods and varying values of \(\epsilon\). As observed by the table, IBP fails to certify the robustness of all the NNs. On the other hand, Bern-IBP achieved high certified accuracy for all the NNs with varying values of \(\epsilon\). Finally, we use the methodology reported in [11] to upper bound the certified accuracy using 100-step PGD attack.

It is essential to mention that IBP's inability to certify the robustness of NNs is not unique to DeepBern-Nets. In particular, as shown in [33, 34], most certifiers struggle to certify the robustness

\begin{table}
\begin{tabular}{c c c c|c c|c c|c} \hline \hline \multirow{2}{*}{Dataset} & Model & \multirow{2}{*}{Test acc. (\%)} & \multirow{2}{*}{\(\epsilon\)} & \multicolumn{2}{c|}{IBP} & \multicolumn{2}{c|}{Bern-IBP} & U.B (PGD) \\  & & & & Time (s) & & Certified & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Certified} \\  & & & & & Acc. (\%) & & Acc. (\%) & Acc. (\%) & Acc. (\%) \\ \hline \multirow{4}{*}{MNIST} & CNNa\_4 & \multirow{4}{*}{97.229} & 0.01 & 3.45 & 0 & 1.43 & 88.69 & 95.97 \\  & CNNa\_4 & & 0.03 & 3.41 & 0 & 1.42 & 72.12 & 92.53 \\  & (190,426) & & 0.1 & 3.26 & 0 & 1.39 & 65.22 & 75.27 \\  & CNNb\_2 & & 0.01 & 4.38 & 0 & 2.07 & 80.21 & 95.42 \\  & (905,882) & & 97.14 & 0.03 & 4.58 & 0 & 2.11 & 56.49 & 90.57 \\  & & 0.1 & 4.61 & 0 & 1.97 & 72.35 & 78.6 \\ \hline \multirow{4}{*}{CIFAR-10} & CNNa\_6 & \multirow{4}{*}{46.77} & 1/255 & 3.29 & 0 & 1.82 & 27.74 & 33.53 \\  & (258,626) & & 2/255 & 3.25 & 0 & 1.83 & 33.49 & 35.81 \\ \cline{1-1}  & CNNb\_4 & & 1/255 & 5.17 & 0 & 4.45 & 28.55 & 42.86 \\ \cline{1-1}  & (1,235,994) & & 2/255 & 5.14 & 0 & 4.33 & 14.7 & 36.73 \\ \hline \hline \end{tabular}
\end{table}
Table 1: A comparison of certified accuracy and verification time for neural networks with Bernstein polynomial activations using both IBP and Bern-IBP methods and varying values of \(\epsilon\). The table also presents the upper bound on certified accuracy calculated using a 100-step PGD attack. The results highlight the superior performance of Bern-IBP in certifying robustness properties compared to IBP.

Figure 2: A visual representation of the tightness of bounds computed using Bern-IBP compared to IBP. The figure shows the \(\log\) difference between \(\mathbb{L}_{\text{robust}}\) computed using Bern-IBP and IBP for NNs with varying orders of and different values of \(\epsilon\). The figure demonstrates the enhanced precision and scalability of the Bern-IBP method in computing tighter bounds, even for higher-order Bernstein activations and larger values of \(\epsilon\), as compared to the naive IBP method.
of ReLU NNs when trained with PGD. This suggests the power of DeepBern-Nets, which can be efficiently certified--in a few seconds even for NNs with millions of parameters, as shown in Table 1--using incomplete certifiers thanks to the ability of Bern-IBP to compute tight bounds.

### Experiment 2: Certified training using Bern-IBP

In this experiment, we demonstrate that the tight bounds calculated by Bern-IBP can be utilized for certified training, achieving state-of-the-art results. Although a direct comparison with methods from certified training literature is not feasible due to the use of Bernstein polynomial activations instead of ReLU activations, we provide a comparison with state-of-the-art certified accuracy results from the SOK benchmark [33] to study how effectively can Bern-IBP be utilized for certified training. We trained neural networks with the same architectures as those in the benchmark to maintain a similar number of parameters, with the polynomial order serving as an additional hyperparameter. The training objective adheres to the certified training literature [37], incorporating the bound on the robustness loss in the objective as follows:

\[\min_{\theta}\mathop{\mathbb{E}}_{(\mathbf{x},y)\in(X,Y)}\bigg{[}(1-\lambda) \mathcal{L}_{\text{CE}}(\mathcal{NN}_{\theta}(\mathbf{x}),y;\theta)+\lambda \mathcal{L}_{\text{RCE}}(S(\mathbf{x},\epsilon),y;\theta))\bigg{]}, \tag{10}\]

where \(\mathbf{x}\) is a data point, \(y\) is the ground truth label, \(\lambda\in[0,1]\) is a weight to control the certified training regularization, \(\mathcal{L}_{\text{CE}}\) is the cross-entropy loss, \(\theta\) is the NN parameters, and \(\mathcal{L}_{\text{RCE}}\) is computed by evaluating \(\mathcal{L}_{\text{CE}}\) on the upper bound of the logit differences computed[37] using a bounding method.

For DeepBern-Nets, \(\mathcal{L}_{\text{RCE}}\) is computed using Bern-IBP during training, while the networks in the SOK benchmark are trained using CROWN-IBP [37]. Table 2 illustrates that employing Bern-IBP bounds for certified training yields state-of-the-art certified accuracy (certified with Bern-IBP) on these datasets, comparable to--or in many cases surpassing--the performance of ReLU networks. The primary advantage of using Bern-IBP lies in its ability to compute highly precise bounds using a computationally cheap method, unlike the more sophisticated bounding methods for ReLU networks, such as \(\alpha\)-Crown. For more details about the exact architecture of the NNs, please refer to Appendix C.2

### Experiment 3: Tight reachability analysis of NN-controlled Quadrotor using Bern-IBP

In this experiment, we study the application-level impact of using Bernstein polynomial activations in comparison to ReLU activations with respect to the tightness of reachable sets in the context of safety-critical applications. Specifically, we consider a 6D linear dynamics system \(\dot{x}=Ax+Bu\) representing a Quadrotor (used in [38; 39; 40]), controlled by a nonlinear NN controller where \(u=\mathcal{NN}(x)\). To ensure a fair comparison, both sets of networks are trained on the same datasets, using the same architectures and training procedures. The only difference between the two sets of networks is the activation function used (ReLU vs. Bernstein polynomial).

After training, we perform reachability analysis with horizon \(T=6\) on each network using the respective bounding methods: Crown and \(\alpha\)-Crown for ReLU networks and the proposed Bern-IBP

\begin{table}
\begin{tabular}{c|c c|c c|c c|c c} \hline \hline \multirow{2}{*}{Model} & \multicolumn{3}{c|}{MNIST Certified acc. (\%)} & \multicolumn{3}{c}{CIFAR-10 Certified acc. (\%)} \\  & \(\epsilon=0.1\) & \multicolumn{3}{c|}{\(\epsilon=0.3\)} & \multicolumn{3}{c|}{\(\epsilon=2/255\)} & \multicolumn{3}{c}{\(\epsilon=8/255\)} \\  & DeepBern-Net & SOK & DeepBern-Net & SOK & DeepBern-Net & SOK & DeepBern-Net & SOK \\  & (\%) & (\%) & (\%) & (\%) & (\%) & (\%) & (\%) & (\%) \\ \hline FCNNa & **72** & 68 & **31** & 25 & **38** & 33 & **28** & 27 \\ FCNNb & **86** & 85 & **57** & 54 & **39** & 37 & **26** & 25 \\ FCNNc & **80** & 80 & **51** & 22 & **36** & 32 & **31** & 30 \\ CNNa & **95** & 95 & 82 & **88** & 45 & **46** & 31 & **34** \\ CNNb & **95** & 94 & 77 & **85** & **49** & 49 & **37** & 35 \\ CNNc & 87 & **89** & 72 & **87** & 38 & **51** & 32 & **38** \\ \hline \hline \end{tabular}
\end{table}
Table 2: A comparison of certified accuracy for NNs with Bernstein polynomial activations versus ReLU NNs as in the SOK benchmark [33]. The certified accuracy is computed using Bern-IBP for NNs with polynomial activations, and the method yielding highest certified accuracy as reported in SOK for ReLU NNs. The table highlights the effectiveness of Bern-IBP in achieving competitive certification while utilizing a very computationally cheap method for tight bound computation.
for Bernstein polynomial networks. We compute the volume of the reachable sets after each step for each network. The results are visualized in Figure 3, comparing the error in the volume of the reachable sets for both ReLU and Bernstein polynomial networks. The error is computed with respect to the true volume of the reachable set for each network, which is computed by heavy sampling. As shown in Figure 3, using Bern-IBP on the NN with Bernstein polynomial can lead to much tighter reachable sets compared to SOTA bounding methods for ReLU networks. This experiment provides insights into the potential benefits of using Bernstein polynomial activations for improving the tightness of reachability bounds, which can have significant implications for neural network certification for safety-critical systems.

## 5 Related work

Neural Network verification.NN verification is an active field of research that focuses on developing techniques to verify the correctness and robustness of neural networks. Various methods have been proposed for NN verification to provide rigorous guarantees on the behavior of NNs and detect potential vulnerabilities such as adversarial examples and unfairness. These methods use techniques such as abstract interpretation [13], Satisfiability Modulo Theory (SMT) [41], Reachability Analysis [14; 42] and Mixed-Integer Linear Programming (MILP) [43; 44; 45; 46]. Many tools also rely on optimization and linear relaxation techniques [11; 12; 15] to speedup the verification. Another line of work [47; 48] uses higher order relaxation such as Bernstein Polynomials to certify NNs. However, frameworks for NN verification often result in loose bounds during the relaxation process or are computationally expensive, particularly for large-scale networks.

Polynomial activations.NNs with polynomial activations have been studied in [27]. Theoretical work was established on their expressiveness [49] and their universal approximation property [50] is established under certain conditions. However, to the best of our knowledge, using Bernstein polynomials in Deep NNs and their impact on NN certification has not been explored yet.

Polynomial Neural Networks.A recent work[51] proposed a new class of approximators called \(\Pi\)-nets, which is based on polynomial expansion. Empirical evidence has shown that \(\Pi\)-nets are highly expressive and capable of producing state-of-the-art results in a variety of tasks, including image, graph, and audio processing, even without the use of non-linear activation functions. When combined with activation functions, they have been demonstrated to achieve state-of-the-art performance in challenging tasks such as image generation, face verification, and 3D mesh representation learning. A framework for certifying such networks using \(\alpha\)-convexification was introduced in [52].

## 6 Discussion and limitations

Societal impact.The societal impact of utilizing Bernstein polynomial activations in neural networks lies in their potential to enhance the reliability and interpretability of AI systems, enabling improved safety, fairness, and transparency in various real-world applications.

Figure 3: (Left) The trajectory of the Quadrotor for the ReLU and Bernstein polynomial networks. (Right) the error in the reachable set volume \(e=(\hat{V}-V)/V\) for each of the networks after each step. \(\hat{V}\) is the estimated volume using the respective bounding method and \(V\) is the true volume of the reachable set using heavy sampling
Limitations.While Bernstein polynomials offer advantages in the context of certification, they also pose some limitations. One limitation is the increased computational complexity during training compared to ReLU networks.
