# On the tightness of linear relaxation based robustness certification methods

Cheng Tang 111This is a preliminary version of the paper (author contact info:
<EMAIL_ADDRESS>
###### Abstract

There has been a rapid development and interest in adversarial training and
defenses in the machine learning community in the recent years. One line of
research focuses on improving the performance and efficiency of adversarial
robustness certificates for neural networks [5, 16, 9, 15, 17, 11, 6, 13, 18].
While each providing a certification to lower (or upper) bound the true
distortion under adversarial attacks via relaxation, less studied was the
tightness of relaxation. In this paper, we analyze a family of linear outer
approximation based certificate methods via a meta algorithm, IBP-Lin. The
aforementioned works often lack quantitative analysis to answer questions such
as how does the performance of the certificate method depend on the network
configuration and the choice of approximation parameters. Under our framework,
we make a first attempt at answering these questions, which reveals that the
tightness of linear approximation based certification can depend heavily on
the configuration of the trained networks.

##  1 Introduction

Given a $m$-layer neural network classifier
$f^{1:m}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d_{m}}$, where $d$ denotes the
input data dimension and $d_{m}$ denotes the output classes, for any train or
test data point $x\in\mathbb{R}^{d}$,
$i^{*}:=\max_{i\in[d_{m}]}f^{1:m}_{i}(x)$ gives the predicted output label on
$x$. It was observed by previous works (see, e.g., [19]) that an adversarial
attack problem can be formulated as below:

$\displaystyle\min_{j\in[d_{m}]}\min_{\delta\in
B}f^{1:m}_{i^{*}}(x+\delta)-f^{1:m}_{j}(x+\delta)$ (1)

where $\delta\in\mathbb{R}^{d}$ is a perturbation variable and
$B\subset\mathbb{R}^{d}$ is a constraint set. If the exact solution to the
above minimization problem can be found and the minimal value is positive, we
know that the model is robust to any perturbation around $x$ within $B$.

In this paper, we focus on the most commonly used $\ell_{\infty}$-attack,
where $B:=\\{\delta|\|\delta\|_{\infty}\leq\epsilon\\}$ for some radius
$\epsilon$. To understand the robustness of a trained neural network, one
would ideally gauge the largest $\epsilon$ for it to be robust at a test
point. However, for any fixed $\epsilon$, exactly solving the minimization
problem is hard. For ReLU networks, it has been recently established that, as
a special case of the property-testing problem, the adversarial attack problem
is NP-complete in general [7].

All attack algorithms [4, 3, 12] effectively establish upper bounds on the
attack radius $\epsilon$ of a given example: If an adversarial example
generated by an attack algorithm flips the label of prediction, then its
attack radius is an upper bound. But a failed attack at radius $\epsilon$ does
not guarantee that the model is safe at attack radius $\epsilon$. There is a
growing body of research dedicated to finding a lower bound to the optimal
$\epsilon$, by solving a relaxed version of the minimization problem [5, 16,
9, 15, 17, 11, 6, 13, 18].

However, the gap between the true minimum and a lower bound computed from any
of the methods above are currently less understood. In this paper, we analyze
the tightness of approximation of a family of linear outer approximation based
certificate methods.

###  1.1 Related Works

In this section, we review recent methods that try to establish a lower bound
on the attack radius $\epsilon$, which guarantees that no attack vector
$\delta$ can be successful at attacking the model within $\epsilon$-distance.

#### Integer program (exact solver)

In the safety verification community, recent works formulated the input-
perturbed network property verification problem, which includes adversarial
robustness as a special case, as integer program and developed exact solvers
based on the formulation [7, 8, 14]. However, these solvers are intractable
beyond toy networks; it was proved in [7] that the property verification
problem of ReLU network is NP-complete.

#### Linear and SDP relaxations

For ReLU networks, [15] proposes to use a pair of linear functions to lower
and upper bound the network output at each point layer-wise, and then the
attack problem at the final output layer can be formulated as a linear program
and solved exactly. A very similar algorithm is developed by [16] from the
dual LP perspective. Follow-up works [18, 1, 19, 17] use similar approaches to
extend the applicability of the approach to activations beyond ReLU function
and to more general networks. The benefit of the linear relaxation approach is
that besides fully-connected layers, the lower bound calculation for linear
operators such as pooling and convolution can be easily implemented with
built-in functions from standard deep learning libraries. Another line of work
[9] uses an exact quadratic formulation of the ReLU adversarial attack
problem, which can be approximately solved by SDP (semi-definite program)
relaxation.

#### Interval bound propagation (IBP)

A more scalable but coarse relaxation is the “interval bound propagation”
(IBP) [5, 6, 18], where the layer-wise output range of a feed-forward neural
network is outer approximated by product of intervals. The IBP bound trades
off tightness of certificate with scalability as compared to the other convex
approximation bounds.

#### Tightness analysis and enhancement of relaxation

Empirically, [10] observed that “convexification” based certification methods,
including LP-based methods, may suffer from a relaxation barrier in the sense
that even solving the exact convex relaxation problem do not significantly
close the gap between the work of [16], an approximate solution to the
convex/linear formulation, and the exact bound. Since the convex relaxation
framework in [10] relies on single-neuron relaxation, [13, 11] proposed to
close the gap between the relaxed and the exact solution using a multi-neuron
joint relaxation. On the other hand, theoretically, it was shown that the
quadratic (and exact) formulation of ReLU attack with SDP relaxation in [9],
which is not included in the family of methods studied in [10], is tight on a
single-layer network [20], where the author argues that SDP-relaxation is
likely non-tight for a multi-layer network without further analysis.

#### Our contribution

In this paper, we study the tightness of linear outer approximation methods,
which belongs to the family of convex relaxation methods studied in [10].
Here, we focus on the theoretical analysis of the gap between the linear
approximated lower bounds and that of the exact bound; in particular, we
analyze the effect of network weights, network dimensions, number of layers,
and approximation parameters on the tightness of linear approximation.

Table 1: Examples of neural network layers that Algorithm 1 is applicable

Neural function types | Examples
---|---
General | convolution
affine functions | average pooling
| fully-connected layers
Element-wise | ReLU
non-decreasing |
activation function | sigmoid (most activation functions)
| max pooling

###  1.2 Notation

#### General feed-forward networks and sub-networks:

In this paper, we restrict our attention to a general $m$-layer feed-forward
neural network: For any $\ell\in\\{1,\dots,m-1\\}$, its $\ell$-th layer is a
composite function
$f^{\ell}:\mathbb{R}^{d_{\ell-1}}\rightarrow\mathbb{R}^{d_{\ell}}$, such that
for any input $x\in\mathbb{R}^{d_{\ell-1}}$,

$f^{\ell}(x)=g^{\ell}(W^{\ell}x+b^{\ell})$

where $g^{\ell}$ is an element-wise non-decreasing activation function and
$(W^{\ell},b^{\ell})$ is a matrix-vector pair that represents a general affine
function. Table 1 provides a summary of general affine functions and element-
wise non-decreasing activation functions. We will use $f^{\ell-k:\ell}$ to
denote the sub-network from layer $\ell-k$ to $\ell$, for any
$k\in\\{0,1,\dots,\ell-1\\}$, i.e.,

$f^{\ell-k:\ell}(x)=f^{\ell}\circ f^{\ell-1}\circ\dots\circ
f^{\ell-k}(x),~{}~{}~{}\mbox{for any~{}}x\in\mathbb{R}^{d_{\ell-k-1}}$

To make the notation consistent, we let $f^{\ell:\ell}(x)=f^{\ell}(x)$.

#### Last-layer modified network

Given a network $f^{1:m}$, and any $\ell\in\\{1,\dots,m\\}$ and
$k\in\\{0,\dots,\ell-1\\}$, we use $\tilde{f}^{\ell-k:\ell}$ to denote the
last-layer modified version of the sub-network $f^{\ell-k:\ell}$ as such: For
$s\in\\{\ell-k,\dots,\ell-1\\}$, $\tilde{f}^{s}:=f^{s}$, and at layer $\ell$,
$\tilde{f}^{\ell}(x)=W^{\ell}x+b^{\ell}$ (that is, activation at last layer
$\ell$ is dropped). In addition, if $\ell=m$, then the weight matrix $W^{m}$
is modified based on a test point $x_{0}\in\mathbb{R}^{d}$: Let
$i^{*}:=\arg\max_{i}f_{i}^{1:m}(x_{0})$. Then
$\tilde{f}^{m}(x)=\tilde{W}^{m}x+\tilde{b}^{m}$, where

$\tilde{W}^{m}_{i}=W^{m}_{i^{*}}-W^{m}_{i},\mbox{~{}for all~{}}i\neq
i^{*},i\in[d_{m}]$ $\tilde{b}^{m}_{i}=b^{m}_{i^{*}}-b^{m}_{i},\mbox{~{}for
all~{}}i\neq i^{*},i\in[d_{m}]$

####  $\ell_{\infty}$-norm attack score

The $\ell_{\infty}$-norm attack problem for a fixed input $x_{0}$ can be
directly formulated as

$s:=\min_{j}\min_{\|\delta\|_{\infty}\leq\epsilon}\tilde{f}_{j}^{1:m}(x_{0}+\delta)$
(2)

We refer to $s$ as the optimal attack score. The objective of most robustness
certification methods is to provide an estimate $\hat{s}$, that lower bounds
the optimal score $s$. If $\hat{s}$ is positive, the model is
$\epsilon$-robust at $x_{0}$ and this particular $\epsilon$ is a lower bound
to the “optimal” attack radius.

#### General notation

We use $W_{i}$ to denote the $i$-th row of matrix $W$ and $W_{\star,i}$ to
denote its $i$-th column; we use $b_{i}$ to denote the $i$-th element of
vector $b$. We use superscript $\ell$ to denote network parameters or
functions at the $\ell$-th layer, e.g., $(g^{\ell},W^{\ell},b^{\ell})$ and
$f^{\ell}$; we use superscript $\ell-k:\ell$ to denote parameters or functions
from $\ell-k$ to $\ell$-th layer, e.g., $f^{\ell-k:\ell}$ denotes the part of
a network starting from $\ell-k$-th layer and ending at $\ell$-th layer. For
two vectors $x,y$, we use $x\succeq y$ to denote element-wise “greater than”;
“$\preceq$” is defined similarly. We use $[\cdot]_{+}$ to denote the element-
wise $\max(\cdot,0)$ operation (i.e., ReLU), and we use $[\cdot]_{-}$ to
denote the element-wise $\min(\cdot,0)$ operation. We use $|\cdot|$ to denote
the element-wise absolute value operation. We use $\|\cdot\|_{2}$ to denote
vector $\ell_{2}$-norm and $\|\cdot\|_{F}$ to denote matrix Frobenius norm. We
use $[n]$ to denote the set of integers from 1 up to $n$.

##  2 IBP-Lin: A meta-algorithm for analyzing linear robustness certificates

In this section, we introduce IBP-Lin, a meta-algorithm that interpolates
between IBP [5] and linear outer approximation based methods [18, 19, 15]. We
start by reviewing IBP, an empirically efficient robustness certificate
method: Since exactly solving the optimization problem in Eq (2) is difficult,
a layer-wise constraint set propagation approach is adopted by IBP, where the
constraint set is fixed to be a hyper-rectangle.

######  Definition 1 (Hyper-rectangle).

Let $\alpha_{i}\leq\beta_{i}$, for all $i\in[d]$. A hyper-rectangle in
$\mathbb{R}^{d}$ is defined by the Cartesian product of intervals, i.e.,
$\Pi_{i=1}^{d}[\alpha_{i},\beta_{i}]$.

At the $\ell$-th layer of a feed-forward network, input from $\ell-1$-th layer
can be outer-approximated by a hyper-rectangular constraint, represented by
the upper and lower limits of its axes $(\alpha^{\ell},\beta^{\ell})$, where
$\alpha^{\ell},\beta^{\ell}\in\mathbb{R}^{d_{\ell}}$.

IBP recursively applies two steps: At layer $\ell$, given a hyper-rectangular
bound $(\alpha^{\ell-1},\beta^{\ell-1})$ from previous layer, it computes a
pre-activation IBP bound $(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$ that
represents a hyper-rectangle containing the pre-activation polytope (induced
by an affine transformation of the input hyper-rectangle:
$W^{\ell}x+b^{\ell}$), where

$\displaystyle\hat{\alpha}_{i}^{\ell}:=\min_{\alpha^{\ell-1}\preceq
x\preceq\beta^{\ell-1}}W_{i}^{\ell}x+b_{i}^{\ell}=b_{i}^{\ell}+W_{i}^{\ell}\beta^{\ell-1}+[W_{i}^{\ell}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})$
(3)

and

$\displaystyle\hat{\beta}_{i}^{\ell}:=\max_{\alpha^{\ell-1}\preceq
x\preceq\beta^{\ell-1}}W_{i}^{\ell}x+b_{i}^{\ell}=b_{i}^{\ell}+W_{i}^{\ell}\beta^{\ell-1}+[-W_{i}^{\ell}]_{+}(\beta^{\ell-1}-\alpha^{\ell-1})$
(4)

Then it applies the element-wise activation function to the pre-activation
bound to obtain the IBP bound at layer $\ell$:

$\alpha^{\ell}:=g^{\ell}(\hat{\alpha}^{\ell})~{}~{}\mbox{and}~{}~{}\beta^{\ell}:=g^{\ell}(\hat{\beta}^{\ell})$
(5)

By the assumption that $g^{\ell}$ is non-decreasing, the hyper-rectangle
$(\alpha^{\ell},\beta^{\ell})$ is guaranteed to contain the output of network
at the $\ell$-th layer. Exact solutions to Eq (3) and (4) have different forms
in the literature. In Appendix H, we show that our form of pre-activation IBP
bound is equivalent to the original IBP bound in [5].

###  2.1 From IBP to IBP-Lin

One way to view linear outer approximation methods [18, 19, 15] is that, we
may tighten the IBP hyper-rectangular bound at layer $\ell$ with an
alternative (or additional) hyper-rectangular constraint,
$(\alpha^{\prime},\beta^{\prime})$.

$\displaystyle\min_{x}W_{i}^{\ell}x+b_{i}^{\ell}$
$\displaystyle\mbox{s.t.~{}~{}}\alpha^{\ell-1}\preceq
x\preceq\beta^{\ell-1}\mbox{~{}~{}and~{}~{}}\alpha^{\prime}\preceq
x\preceq\beta^{\prime}$ (6)

The enhanced constraint is equivalent to

$\max(\alpha^{\ell-1},\alpha^{\prime})\preceq
x\preceq\min(\beta^{\ell-1},\beta^{\prime})$

Existing linear outer approximation techniques [18, 19, 15] follow a similar
template to systematically derive an alternative hyper-rectangular constraint
$(\alpha^{\prime},\beta^{\prime})$, built on top of a layer-wise single-layer
linear outer approximation, which is summarized in Definition 2.

######  Definition 2 (Single-layer linear approximation of neural functions).

Let $f^{\ell}(x)$ be the $\ell$-th layer function in a feed-forward network.
Let $(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$ be any two vectors such that
any input $x$ to $f^{\ell}$ satisfies the following

$\hat{\alpha}^{\ell}\preceq\hat{z}^{\ell}(x):=W^{\ell}x+b^{\ell}\preceq\hat{\beta}^{\ell}$
(7)

We say $(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$ is the pre-activation
lower/upper bound at layer $\ell$. In addition, we say $f^{\ell}(x)$ has a
linear outer approximation, if there exists two affine functions
$T_{L}^{\ell}$ and $T_{U}^{\ell}$ of form

$T_{L}^{\ell}(x):=D_{L}^{\ell}\hat{z}^{\ell}(x)+b_{L}^{\ell}\mbox{~{}~{}and~{}~{}}T_{U}^{\ell}(x):=D_{U}^{\ell}\hat{z}^{\ell}(x)+b_{U}^{\ell}$

with the following holds

$\forall
x,~{}~{}s.t.~{}~{}\hat{\alpha}^{\ell}\preceq\hat{z}^{\ell}(x)\preceq\hat{\beta}^{\ell},~{}T_{L}^{\ell}(x)\preceq
f^{\ell}(x)\preceq T_{U}^{\ell}(x)$

where $D_{L}^{\ell},D_{U}^{\ell}$ are diagonal matrices and
$b_{L}^{\ell},b_{U}^{\ell}$ are vectors.

The pre-activation bounds $(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$, the
basis for constructing a single-layer linear outer approximation, can be any
pair of bounds that guarantees Eq (7). For example, they can be IBP pre-
activation bounds or pre-computed linear outer approximation bounds. Based on
the single-layer relaxation, a multi-layer linear outer approximation is
defined as below.

######  Definition 3 (Multi-layer linear approximation operator for sub-
network $\tilde{f}^{\ell-k:\ell}$).

For any $\ell$ and $k<\ell$. If a network admits single-layer linear
approximation from layer $\ell-k$ to layer $\ell-1$. Let
$\tilde{f}^{\ell-k:\ell}$ be a last-layer modified version of
$f^{\ell-k:\ell}$. We define a $k$-layer linear outer approximation operator
to $\tilde{f}^{\ell-k:\ell}(x)$ as

$T^{\ell-k:\ell}_{L}(x):=W_{L}^{\ell-k:\ell}(x)+b_{L}^{\ell-k:\ell}$
$T^{\ell-k:\ell}_{U}(x):=W_{U}^{\ell-k:\ell}(x)+b_{U}^{\ell-k:\ell}$

where

$W_{L}^{\ell:\ell}=W_{U}^{\ell:\ell}:=W^{\ell}\,,\mbox{~{}~{}}b_{L}^{\ell:\ell}=b_{U}^{\ell:\ell}:=b^{\ell}$

And for $s=1,\dots,k-1,$

$W_{L}^{\ell-s:\ell}:=P_{L}^{\ell-s+1}W^{\ell-s}\mbox{~{}and~{}}W_{U}^{\ell-s:\ell}:=P_{U}^{\ell-s+1}W^{\ell-s}$

with

$P_{L}^{\ell-s+1}:=W_{L}^{\ell-s+1:\ell}D_{U}^{\ell-s}+[W_{L}^{\ell-s+1:\ell}]_{+}(D_{L}^{\ell-s}-D_{U}^{\ell-s})$
$P_{U}^{\ell-s+1}:=W_{U}^{\ell-s+1:\ell}D_{U}^{\ell-s}+[-W_{U}^{\ell-s+1:\ell}]_{+}(D_{U}^{\ell-s}-D_{L}^{\ell-s})$

and

$\displaystyle
b_{L}^{\ell-s:\ell}:=P_{L}^{\ell-s+1}b^{\ell-s}+[W_{L}^{\ell-s+1:\ell}]_{-}b_{U}^{\ell-s}+[W_{L}^{\ell-s+1:\ell}]_{+}b_{L}^{\ell-s}+b_{L}^{\ell-s+1:\ell}$
$\displaystyle
b_{U}^{\ell-s:\ell}:=P_{U}^{\ell-s+1}b^{\ell-s}+[W_{U}^{\ell-s+1:\ell}]_{+}b_{U}^{\ell-s}+[W_{U}^{\ell-s+1:\ell}]_{-}b_{L}^{\ell-s}+b_{U}^{\ell-s+1:\ell}$

LinApprox (Algorithm 2) is a general scheme for linear outer approximation of
networks (sub-networks) using Definition 3. Its input constraint
$(\alpha^{\ell-k-1},\beta^{\ell-k-1})$ specifies the input hyper-rectangle to
sub-network $\tilde{f}^{\ell-k:\ell}$; the pre-activation bounds
$(\widehat{\alpha}^{s},\widehat{\beta}^{s})_{s=\ell-k}^{\ell}$ are pre-
computed to ensure for any $\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}$, at layer $s\in\\{\ell-k,\dots,\ell\\}$,

$\widehat{\alpha}^{s}\preceq\tilde{f}^{\ell-k:s}(x)\preceq\widehat{\beta}^{s}.$

The flexibility of LinApprox comes from the choice of pre-activation bounds
$(\widehat{\alpha}^{s},\widehat{\beta}^{s})_{s=\ell-k}^{\ell}$ and the
specific single-layer linear approximation method.

The multi-layer linear-outer approximation (LinApprox) augmented bound
propagation algorithm, IBP-Lin, is presented in Algorithm 1. Corollary 2.0.1
shows that IBP-Lin (Algorithm 1) returns an element-wise lower bound vector
$\alpha^{m}$ to $\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}^{1:m}(x)_{i}$, for all $i\in[d_{m}]$.

Input : $\tilde{f}^{1:m}$; $\epsilon>0$, $x_{0}\in\mathbb{R}^{d}$; linear
approximation schedule vector $s\in\mathbb{N}^{m}$

Output : Robustness lower bound vector $\alpha^{m}$

1 init  __

2 $\alpha^{0}\leftarrow x_{0}-\epsilon\mathbbm{1}$

3 $\beta^{0}\leftarrow x_{0}+\epsilon\mathbbm{1}$

4

5for  _$\ell\in 1,\dots,m$_ do

6 $\widehat{\alpha}^{\ell}\leftarrow
W^{\ell}\beta^{\ell-1}+b^{\ell}+[W^{\ell}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})$

7 $\widehat{\beta}^{\ell}\leftarrow
W^{\ell}\beta^{\ell-1}+b^{\ell}+[-W^{\ell}]_{+}(\beta^{\ell-1}-\alpha^{\ell-1})$

8 if  _$s_{\ell}\neq 0$_ then

9 Get number of backward approximation layers $k\leftarrow s_{\ell}$

10 Get sub-network function
$\tilde{f}^{\ell-k+1:\ell}(x):=W^{\ell}f^{\ell-k+1:\ell-1}(x)+b^{\ell}$
$(\widehat{\alpha}^{\prime},\widehat{\beta}^{\prime})\leftarrow
LinApprox((\alpha^{\ell-k},\beta^{\ell-k}),\tilde{f}^{\ell-k+1:\ell},(\hat{\alpha}^{s},\hat{\beta}^{s})_{s=\ell-k}^{\ell})$;

11 (Re-estimate pre-activation bounds at layer $\ell$ by Algorithm 2)

12
$\widehat{\alpha}^{\ell}\leftarrow\max(\widehat{\alpha}^{\ell},\widehat{\alpha}^{\prime})$;

13
$\widehat{\beta}^{\ell}\leftarrow\min(\widehat{\beta}^{\ell},\widehat{\beta}^{\prime})$;

14

15 end if

16 $\alpha^{\ell}\leftarrow g^{\ell}(\widehat{\alpha}^{\ell})$ and
$\beta^{\ell}\leftarrow g^{\ell}(\widehat{\beta}^{\ell})$;

17

18 end for

return $\alpha^{m}$;

Algorithm 1 IBP-Lin

Input : Initial constraints $(\alpha^{\ell-k-1},\beta^{\ell-k-1})$; Sub-
network function $\tilde{f}^{\ell-k:\ell}$ with pre-activation bounds
$(\hat{\alpha}^{s},\hat{\beta}^{s})_{s=\ell-k}^{\ell}$; Single-layer linear
approximation method

Output : $\hat{\alpha}^{\prime},\hat{\beta}^{\prime}$

1 init  __

2 $W_{L}^{\ell:\ell}\leftarrow W^{\ell}$ and $W_{U}^{\ell:\ell}\leftarrow
W^{\ell}$; $b_{L}^{\ell:\ell}\leftarrow b^{\ell}$ and
$b_{U}^{\ell:\ell}\leftarrow b^{\ell}$;

3

4

5for  _$s\in\\{1,\dots,k\\}$_ do

6 Construct $D_{L}^{\ell-s},D_{U}^{\ell-s},b_{L}^{\ell-s},b_{U}^{\ell-s}$ with
the provided single-layer linear approximation method (Definition 2) based on
pre-activation bounds $(\hat{\alpha}^{\ell-s},\hat{\beta}^{\ell-s})$ ;

7

8 Update
$W_{L}^{\ell-s:\ell},W_{U}^{\ell-s:\ell},b_{L}^{\ell-s:\ell},b_{U}^{\ell-s:\ell}$
based on the iterative rule in Definition 3 ;

9 end for

10 $\hat{\alpha}^{\prime}\leftarrow
W_{L}^{\ell-k:\ell}\beta^{\ell-k-1}+[W_{L}^{\ell-k:\ell}]_{+}(\alpha^{\ell-k-1}-\beta^{\ell-k-1})+b_{L}^{\ell-k:\ell}$
;

11 $\hat{\beta}^{\prime}\leftarrow
W_{U}^{\ell-k:\ell}\beta^{\ell-k-1}+[-W_{U}^{\ell-k:\ell}]_{+}(\beta^{\ell-k-1}-\alpha^{\ell-k-1})+b_{U}^{\ell-k:\ell}$
;

12 return $(\hat{\alpha}^{\prime},\hat{\beta}^{\prime})$;

Algorithm 2 LinApprox

######  Corollary 2.0.1 (Correctness of IBP-Lin).

Let $f^{1:m}$ be $m$-layer feed-forward network. Suppose there exists single-
layer linear outer approximation for every layer of the network as defined in
Definition 2. Suppose the input to the network $\tilde{f}^{1:m}$ satisfies

$\alpha^{0}\preceq x\preceq\beta^{0}$

Let $\widehat{\alpha}^{\ell},\widehat{\beta}^{\ell}$ be defined as in line 5
and 6 of Algorithm 1, and let $\alpha^{m}$ be as defined in line 16 of
Algorithm 1.

  1. 1.

For any $\ell\in[m]$, and for any $x$ such that $\alpha^{0}\preceq
x\preceq\beta^{0}$,

$\widehat{\alpha}^{\ell}\preceq\tilde{f}^{1:\ell}(x)\preceq\widehat{\beta}^{\ell}$

  2. 2.

For any $x$ such that $\alpha^{0}\preceq x\preceq\beta^{0}$,

$\alpha^{m}\preceq\tilde{f}^{1:m}(x)$

The proof of Corollary 2.0.1 relies on Proposition A.1 (see Appendix), whose
main idea is the same as the correctness proof of CROWN [19, Theorem 3.2].

#### Schedule vector in IBP-Lin (Algorithm 1):

Given a trained network $\tilde{f}^{1:m}$ (with last-layer modified according
to), fix any input data $x_{0}$, and attack radius $\epsilon>0$, IBP-Lin is
parametrized by the linear approximation schedule vector $s\in\mathbb{N}^{m}$.
The value $s_{\ell}$ specifies the number of backward unrolling used to
linearly approximate the network output at layer $\ell$: If $s_{\ell}=0$, no
linear approximation is used; if $s_{\ell}=k,k\in\\{1,\dots,\ell\\}$, then the
sub-network $\tilde{f}^{\ell-k:\ell}$ is linearly approximated.

#### Relation to existing algorithms

IBP-Lin reduces to IBP [5] if the schedule vector $s$ is null (all-zero); it
reduces to CROWN-IBP style algorithm [18] if $s_{\ell}=0,\forall\ell<m$, and
$s_{m}=m$; it reduces to CROWN and Fast-Lin style algorithm [19, 15] if
$s_{\ell}=\ell,\forall\ell\in[m]$.

There are some slight generalization and improvement in IBP-Lin: First, IBP-
Lin allows more freedom in choosing the single-layer approximation functions;
second, while existing linear approximation methods unfold the network from
layer $\ell$ to the first layer, IBP-Lin leaves the number of backward
unfolding layers as a parameter (specified by the schedule $s_{\ell}$);
lastly, after obtaining the alternative pre-activation bounds
$(\hat{\alpha}^{\prime},\hat{\beta}^{\prime})$ from LinApprox, it takes its
intersection with the original pre-activation bounds (line 11 and 12), this is
to make sure that we never get a worse approximation by the additional
computation in LinApprox, as is clear from Eq. (2.1).

##  3 Main result

While IBP-Lin allows different choices of linear approximation, intuitively
the tightness of a linear outer-approximation will be determined by the
“width” of the approximation tube around the boundary points. The “thinner”
the approximation tube is, the better the approximation result should be.
Before proceeding, we characterize one common single-layer linear outer
approximation method as the parallelogram relaxation.

######  Definition 4 (Parallelogram relaxation).

We say a neural network layer $f^{\ell}(x)$ admits a parallelogram relaxation,
if it has a single-layer linear outer approximation (Definition 2) with

$D:=D^{\ell}_{L}=D^{\ell}_{U}$

such that for some pre-activation bounds
$(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$,

$\forall
x~{}~{}s.t.~{}~{}\hat{\alpha}^{\ell}\preceq\hat{z}(x)=W^{\ell}x+b^{\ell}\preceq\hat{\beta}^{\ell},~{}D\hat{z}(x)+b_{L}\preceq
f^{\ell}(x)\preceq D\hat{z}(x)+b_{U}$

The parallelogram relaxation is adopted by IBP and Fast-Lin [5, 15]. In [19]
and [18], another type of of relaxation method is used to minimize the volume
of the relaxed area. In our subsequent analysis, we focus on parallelogram
relaxation, which captures our intuition that the “parallelogram width” of the
relaxed region controls the quality of approximation. Proposition 3.1 uses the
layer-wise “parallelogram width”, $b_{U}^{\ell}-b_{L}^{\ell}$, as a parameter
to upper bound the gap between the relaxed hyper-rectangular approximation of
network output and the tightest hyper-rectangle containing the network output.

######  Proposition 3.1 (Approximation error of multi-layer parallelogram-
relaxation).

Let $f^{1:m}$ be a neural network classifier that can be layer-wise outer
approximated by parallelogram relaxation from $\ell=1,\dots,m-1$. For any
$\ell,0<k<\ell$, let $\tilde{f}^{\ell-k:\ell}$ denote the last-layer modified
version of sub-network $f^{\ell-k:\ell}$. Let
$T_{L}^{\ell-k:\ell},T_{U}^{\ell-k:\ell}$ be a multi-layer linear outer
approximation of $\tilde{f}^{\ell-k:\ell}$ based on parallelogram relaxation.
Then for all $i\in[d_{\ell}]$,

$\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}\geq\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)-\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$

and

$\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{U}^{\ell-k:\ell}(x)_{i}\leq\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)+\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$

For any sub-network $\tilde{f}^{\ell-k:\ell}$, Proposition 3.1 can be used to
derive an upper bound of approximation error, starting from an input
constraint set at layer $\ell-k-1$: In the statement of Proposition 3.1, the
difference

$\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}-\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$

represents the gap between the approximated lower bound at dimension $i$ and
the optimal lower bound induced by the tightest hyper-rectangle containing
$\tilde{f}^{\ell-k:\ell}(x)$. The difference is non-positive due to the
correctness of IBP-Lin. The larger the quantity
$\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$,
the larger the approximation error. Similar interpretation applies to the
other direction.

###  3.1 Approximation error of different types of ReLU networks

For the rest of the analysis, we restrict our attention to parallelogram
relaxation of ReLU networks. Let $f^{\ell}(x)$ be a ReLU layer function, it
admits a single-layer parallelogram approximation whose approximation
parameters $D^{\ell},b_{L}^{\ell},b_{U}^{\ell}$, given pre-activation
$(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$, are defined as

$\displaystyle
D_{i,i}^{\ell}=\begin{cases}1,\mbox{~{}if}~{}i\in\mathcal{I}^{\ell}_{+}\\\
0,\mbox{~{}if}~{}i\in\mathcal{I}^{\ell}_{-}\\\
\frac{\hat{\beta}_{i}^{\ell}}{\hat{\beta}_{i}^{\ell}-\hat{\alpha}_{i}^{\ell}},\mbox{~{}if}~{}i\in\mathcal{I}^{\ell}\end{cases}b_{L}^{\ell}=0,~{}~{}~{}\mbox{and~{}~{}}b_{U}^{\ell}=\begin{cases}0,\mbox{~{}if}~{}i\in\mathcal{I}^{\ell}_{+}\\\
0,\mbox{~{}if}~{}i\in\mathcal{I}^{\ell}_{-}\\\
\frac{-\hat{\alpha}_{i}^{\ell}\hat{\beta}_{i}^{\ell}}{\hat{\beta}_{i}^{\ell}-\hat{\alpha}_{i}^{\ell}},\mbox{~{}if}~{}i\in\mathcal{I}^{\ell}\end{cases}$
(8)

where

$\begin{cases}\mathcal{I}^{\ell}_{+}:=\\{i|0\leq\hat{\alpha}^{\ell}_{i}\leq\hat{\beta}^{\ell}_{i}\\}\\\
\mathcal{I}^{\ell}:=\\{i|\hat{\alpha}^{\ell}_{i}<0<\hat{\beta}^{\ell}_{i}\\}\\\
\mathcal{I}^{\ell}_{-}:=\\{i|\hat{\alpha}^{\ell}_{i}\leq\hat{\beta}^{\ell}_{i}\leq
0\\}\end{cases}$

The definition of subsets
$\mathcal{I}^{\ell},\mathcal{I}_{+}^{\ell},\mathcal{I}_{-}^{\ell}$, which
partitions $[d_{\ell}]$, is a common approach used in linear approximation
methods [18, 19, 15, 16] to refine approximation based on pre-activation
bounds.

In [20], the author showed that SDP-relaxation is tight on a single hidden-
layer ReLU network (independent of weight assignment), but argued that for
multi-layer networks SDP-relaxation is likely non-tight without a formal
analysis. For single hidden-layer ReLU networks, it is not hard to see that
with parallelogram approximation, the upper bound is always tight. We show for
random Gaussian input, the lower bound is non-tight in expectation.

######  Proposition 3.2 (Lower bound on approximation error of single hidden-
layer random networks).

For any weight matrix $W^{1}$, let $[W^{1}x]_{+}$ be a single-hidden layer
ReLU network (bias free). Let $D^{1}W^{1}x+b_{L}^{1}$ and
$D^{1}W^{1}x+b_{U}^{1}$ be the lower/upper bound of the single-hidden layer
parallelogram approximation as defined in Eq (8).

  1. 1.

Let $\alpha^{0}=x_{0}-\epsilon\vec{1},\beta^{0}=x_{0}+\epsilon\vec{1}$, with
$x_{0}\sim\mathcal{N}(0,I)$. Then let $\Phi(\cdot)$ denote the cumulative
distribution function of standard normal, and for any $i$, let
$\kappa_{i}:=\frac{\|W_{i}^{1}\|_{1}}{\|W_{i}^{1}\|_{2}}$. The following holds

$\displaystyle\operatorname{\mathbb{E}}_{x_{0}}\bigg{(}\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}[W_{i}^{1}x]_{+}\bigg{)}$
$\displaystyle\leq(\Phi(\epsilon\kappa_{i})-1/2)\|W_{i}^{1}\|_{2}(\frac{1}{\epsilon\kappa_{i}}-\epsilon\kappa_{i})$

  2. 2.

For any $(\alpha^{0},\beta^{0})$,

$\max_{\alpha^{0}\preceq
x\preceq\beta^{0}}D_{i}^{1}W^{1}x+(b_{U}^{1})_{i}=\max_{\alpha^{0}\preceq
x\preceq\beta^{0}}[W_{i}^{1}x]_{+}$

The first statement of Proposition 3.2 translates to a lower bound on the
expected approximation error at the $i$-th output neuron, that is,

$(\Phi(\epsilon\kappa_{i})-1/2)\|W_{i}^{1}\|_{2}(\epsilon\kappa_{i}-\frac{1}{\epsilon\kappa_{i}})$

which is only meaningful (non-negative) when $\epsilon$ is chosen so that
$\epsilon>\frac{1}{\kappa_{i}}$. Here
$\kappa_{i}=\frac{\|W_{i}^{1}\|_{1}}{\|W_{i}^{1}\|_{2}}\in[1,\sqrt{d}]$
characterizes the sparsity of $W_{i}^{1}$. For fixed $\|W_{i}^{1}\|_{2}$,
$\kappa_{i}$ becomes larger when $W_{i}^{1}$ becomes more dense. The lower
bound suggests that the approximation error grows with $\epsilon$ (attack
radius), $\|W_{i}^{1}\|_{2}$ (norm of row weights), and $\kappa_{i}$ (dense
level of row weights). To simplify our analysis, for the rest of the paper we
make the following assumptions:

  1. 1.

We restrict $(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$ to IBP pre-activation
bounds

  2. 2.

We consider an $m$-layer ReLU network $f^{1:m}(x)$ such that
$\forall\ell\in[m]$, $W^{\ell}\in\mathbb{R}^{d\times d}$, where $d$ equals to
the input dimension.

We let $T_{L}^{1:m},T_{U}^{1:m}$ ($T_{L}^{\ell-k:\ell},T_{U}^{\ell-k:\ell}$)
be a multi-layer linear approximation of the network (sub-network) based on
the single-layer relaxation in Eq (8).

While we cannot obtain positive results regarding approximation error of
linear approximation methods on arbitrary or random multi-layer networks,
Proposition 3.3 below demonstrates that there exists ReLU networks where exact
bound can be computed.

######  Proposition 3.3 (Tight bound on non-negative sub-networks).

Suppose $\forall\ell\in[m]$, $W_{i,j}^{\ell}\geq 0$ and $b_{i}^{\ell}=0$, for
any $i,j\in[d]$. Let $(\alpha^{0},\beta^{0})$ be any hyper-rectangular input
constraint. Then for any $2\leq\ell\leq m$ and $1\leq k\leq\ell-2$,

$\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}=\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$

and

$\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{U}^{\ell-k:\ell}(x)_{i}=\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$

Note that the result holds only when $\ell-k\geq 2$, i.e., when we approximate
a sub-network after the first layer. The proof is simple and uses the fact
that the output of ReLU network is non-negative and the property of IBP
bounds. The intuition is that parallelogram approximation becomes tight (lower
bound coincides with upper bound) in case for all neuron $i$,
$i\in\mathcal{I}_{+}$. In contrast to the positive result in Proposition 3.3,
when one uses parallelogram approximation for the entire ReLU network
(starting from the first layer), Proposition 3.4 shows that the approximation
error can depend heavily on the magnitude of the network weights.

######  Proposition 3.4 (“Phase transition” of approximation error can
happen).

Suppose $\forall\ell\in[m]$, $W_{i,j}^{\ell}\geq 0$ and $b_{i}^{\ell}=0$, for
any $i,j\in[d]$. Suppose the input constraint is such that
$\alpha^{0}=x_{0}-\epsilon\vec{1},\beta^{0}=x_{0}+\epsilon\vec{1}$. Then

  1. 1.

Let $x_{0}$ be any fixed test point. If $W_{ij}^{\ell}=\frac{1}{d^{p}}$ for
some $p>1$. Then for any $\delta>0$, choosing the number of layers
$m\geq\frac{1}{p-1}\log_{d}\frac{\epsilon}{2\delta}$ guarantees that $\forall
i\in[d]$,

$\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}\geq\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)-\delta$

  2. 2.

Suppose $x_{0}\sim\mathcal{N}(0,I)$ and let $\Phi(\cdot)$ denote the c.d.f. of
the standard normal distribution. If $W_{ij}^{\ell}=\frac{1}{d^{p}}$ for some
$p<1$ and suppose $\epsilon>\sqrt{1/d}$. Then for any $B>0$, choosing the
number of layers $m$ to be

$m>\frac{1}{1-p}\log_{d}\frac{Bd}{(\Phi(\epsilon\sqrt{d})-1/2)(\epsilon
d-\frac{1}{\epsilon})}$

guarantees that $\forall i\in[d]$,

$\operatorname{\mathbb{E}}_{x_{0}}\bigg{(}\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)\bigg{)}\leq-B$

The intuition behind this result is that the parallelogram approximation is
not tight at the first layer, and depending on the magnitude of the network
weights, this small error either explodes up or vanishes as the approximated
bounds propagate through layers of the network.

Our last result is motivated by the following question: Does the linear outer
approximation become more accurate at a fixed layer $\ell$ if we apply
LinApprox starting from layer $k_{1}<k_{2}$? This seems to be implicitly
assumed to be true in the current literature. However, Proposition 3.5
suggests that this is not necessarily the case.

######  Proposition 3.5 (Using more layers in LinApprox can hurt
approximation).

For any $B>0$, there exists an $m$-layer ReLU network and choice of
$(x_{0},\epsilon)$ such that for any $2\leq k\leq m-1$, and for any $i\in[d]$

$\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{k}\preceq
x\preceq\beta^{k}}T_{L}^{k:m}(x)_{i}\leq-B$

Proposition 3.5 shows that there exists network configuration where
approximation of $T_{L}^{1:m}(x)$ (CROWN-IBP) can be made arbitrarily worse
than that of $T_{L}^{k:m}(x)$ (IBP-Lin) for $2\leq k\leq m-1$. This suggests
that in addition to computational savings, using less layers of linear
approximation may at times improve approximation tightness.

## References

  * [1] Akhilan Boopathy, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel.  Cnn-cert: An efficient framework for certifying robustness of convolutional neural networks.  volume 33, pages 3240–3247, 2019.
  * [2] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.
  * [3] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  arXiv, 2016.
  * [4] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv, 2014.
  * [5] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Arthur Mann, and Pushmeet Kohli.  Scalable verified training for provably robust image classification.  In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 4841–4850, 2019.
  * [6] Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham, and Pushmeet Kohli.  Achieving verified robustness to symbol substitutions via interval bound propagation, 2019.
  * [7] Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer.  Reluplex: An efficient smt solver for verifying deep neural networks.  In Rupak Majumdar and Viktor Kunčak, editors, Computer Aided Verification, pages 97–117, Cham, 2017. Springer International Publishing.
  * [8] Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer.  Towards proving the adversarial robustness of deep neural networks.  Electronic Proceedings in Theoretical Computer Science, 257:19–26, sep 2017.
  * [9] Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang.  Semidefinite relaxations for certifying robustness to adversarial examples.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [10] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang.  A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks.  Curran Associates Inc., Red Hook, NY, USA, 2019.
  * [11] Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin Vechev.  Beyond the single neuron convex barrier for neural network certification.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [12] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks, 2013.
  * [13] Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma.  The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification, 2020.
  * [14] Vincent Tjeng and Russ Tedrake.  Verifying neural networks with mixed integer programming.  ArXiv, abs/1711.07356, 2017.
  * [15] Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane S. Boning, Inderjit S. Dhillon, and Luca Daniel.  Towards fast computation of certified robustness for relu networks.  In ICML, 2018.
  * [16] Eric Wong and Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5286–5295. PMLR, 2018.
  * [17] Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter.  Scaling provable adversarial defenses.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [18] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane S. Boning, and Cho-Jui Hsieh.  Towards stable and efficient training of verifiably robust neural networks.  ArXiv, abs/1906.06316, 2020.
  * [19] Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel.  Efficient neural network robustness certification with general activation functions.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 4944–4953, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * [20] Richard Zhang.  On the tightness of semidefinite relaxations for certifying robustness to adversarial examples.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 3808–3820. Curran Associates, Inc., 2020.

##  Appendix A Proof of Proposition A.1

######  Proposition A.1 (Correctness of multi-layer linear approximation
operator).

Let $f^{\ell-k:\ell}$ be a sub-network of any $m$ layer feed-forward network,
for some $\ell\in[m]$ and $k\in\\{0,\dots,\ell-1\\}$. Let
$\tilde{f}^{\ell-k:\ell}$ be the last-layer modified version of
$f^{\ell-k:\ell}$. Suppose for any $k\in\\{0,\dots,\ell-1\\}$, there exists
two vectors $(\hat{\alpha}^{\ell-k},\hat{\beta}^{\ell-k})$ satisfying for any
$\alpha^{0}\preceq x\preceq\beta^{0}$,

$\hat{\alpha}^{\ell-k}\preceq\tilde{f}^{1:\ell-k}(x)\preceq\hat{\beta}^{\ell-k}\mbox{~{}~{}~{}($\hat{\alpha}^{\ell-k},\hat{\beta}^{\ell-k}$
as defined in Definition~{}\ref{defn:single-layer-relax})}$

Suppose there exists single-layer linear outer approximation of the network,
where the layer-wise approximation parameters
$D_{L}^{\ell-k},D_{U}^{\ell-k},b_{L}^{\ell-k},b_{U}^{\ell-k}$ are constructed
based on $(\hat{\alpha}^{\ell-k},\hat{\beta}^{\ell-k})$. Let
$T_{L}^{\ell-k:\ell}$ and $T_{U}^{\ell-k:\ell}$ be a $k$-layer linear
approximation to $\tilde{f}^{\ell-k:\ell}$ as defined in Definition 3. Then
for any $k\in\\{0,\dots,\ell-1\\}$,

$T_{L}^{\ell-k:\ell}(f^{1:\ell-k-1}(x))\preceq\tilde{f}^{1:\ell}(x)\preceq
T_{U}^{\ell-k:\ell}(f^{1:\ell-k-1}(x)),~{}~{}\forall
x\text{~{}s.t.~{}}\alpha^{0}\preceq x\preceq\beta^{0}$

(we abuse notation by letting $f^{1:0}(x):=x$). In particular, $\forall
x,\alpha^{0}\preceq x\preceq\beta^{0}$

$T_{L}^{1:m}(x)\preceq\tilde{f}^{1:m}(x)\preceq T_{U}^{1:m}(x)$

###### Proof.

We prove the first statement by induction on $k$:

#### Base case:

For $k=0$,

$\displaystyle
T_{L}^{\ell:\ell}(f^{1:\ell-1}(x))=W_{L}^{\ell:\ell}f^{1:\ell-1}(x)+b_{L}^{\ell:\ell}=W^{\ell}f^{1:\ell-1}(x)+b^{\ell}\mbox{~{}~{}(Definition~{}\ref{defn:multi-
layer-lin-appx}})$ $\displaystyle=\tilde{f}^{1:\ell}(x)~{}~{}~{}(\mbox{and
hence~{}}\preceq\tilde{f}^{1:\ell}(x))$

The case for $T_{U}^{\ell:\ell}$ can be proved similarly. This shows the
statement holds for $k=0$.

#### From $k$ to $k+1$:

Suppose the statement holds for any $k\in\\{0,\dots,\ell-1\\}$, we next show
it must hold for $k+1$. We expand $T_{L}^{\ell-k:\ell}(f^{1:\ell-k-1}(x))$ to
reveal the term $f^{1:\ell-k-2}$:

$\displaystyle
T_{L}^{\ell-k:\ell}(f^{1:\ell-k-1}(x))=W_{L}^{\ell-k:\ell}f^{1:\ell-k-1}(x)+b_{L}^{\ell-k:\ell}$
$\displaystyle=W_{L}^{\ell-k:\ell}g^{\ell-k-1}(W^{\ell-k-1}f^{1:\ell-k-2}(x)+b^{\ell-k-1})+b_{L}^{\ell-k:\ell}$
$\displaystyle=W_{L}^{\ell-k:\ell}g^{\ell-(k+1)}(W^{\ell-(k+1)}f^{1:\ell-(k+1)-1}(x)+b^{\ell-(k+1)})+b_{L}^{\ell-k:\ell}$

By property of pre-activation bounds $\hat{\alpha}^{\ell-(k+1)}$ and
$\hat{\beta}^{\ell-(k+1)}$, for any $\alpha^{0}\preceq x\preceq\beta^{0}$,

$\hat{\alpha}^{\ell-(k+1)}\preceq\tilde{f}^{1:\ell-(k+1)}(x)=W^{\ell-(k+1)}f^{1:\ell-(k+1)-1}(x)+b^{\ell-(k+1)}\preceq\hat{\beta}^{\ell-(k+1)}$

By property of single-layer linear approximation,
$\forall\hat{z},~{}s.t.~{}\hat{\alpha}^{\ell-(k+1)}\preceq\hat{z}\preceq\hat{\beta}^{\ell-(k+1)}$

$D_{L}^{\ell-(k+1)}(\hat{z})+b_{L}^{\ell-(k+1)}\preceq
g^{\ell-(k+1)}(\hat{z})$

It follows that for any $\alpha^{0}\preceq x\preceq\beta^{0}$,

$\displaystyle
D_{L}^{\ell-(k+1)}(W^{\ell-(k+1)}f^{1:\ell-(k+1)-1}(x)+b^{\ell-(k+1)})+b_{L}^{\ell-(k+1)}$
$\displaystyle=D_{L}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)+b_{L}^{\ell-(k+1)}$
$\displaystyle\preceq g^{\ell-(k+1)}(\tilde{f}^{1:\ell-(k+1)}(x))$

Similarly, we get

$\displaystyle g^{\ell-(k+1)}(\tilde{f}^{1:\ell-(k+1)}(x))\preceq
D_{U}^{\ell-(k+1)}(\tilde{f}^{1:\ell-(k+1)}(x))+b_{U}^{\ell-(k+1)}$

Then for any $\alpha^{0}\preceq x\preceq\beta^{0}$, for any $i\in[d_{\ell}]$,

$\displaystyle
T_{L}^{\ell-k:\ell}(f^{1:\ell-k-1}(x))_{i}=W_{L,i}^{\ell-k:\ell}g^{\ell-(k+1)}(\tilde{f}^{1:\ell-(k+1)}(x))+b_{L,i}^{\ell-k:\ell}$
$\displaystyle\geq\min_{D_{L}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)+b_{L}^{\ell-(k+1)}\preceq
y\preceq
D_{U}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)+b_{U}^{\ell-(k+1)}}W_{L,i}^{\ell-k:\ell}y+b_{L,i}^{\ell-k:\ell}$

For a fixed $x$, the RHS is a minimization problem that can be solved exactly
by applying Eq. (3):

$\displaystyle\min_{D_{L}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)+b_{L}^{\ell-(k+1)}\preceq
y\preceq
D_{U}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)+b_{U}^{\ell-(k+1)}}W_{L,i}^{\ell-k:\ell}y+b_{L,i}^{\ell-k:\ell}$
$\displaystyle=W_{L,i}^{\ell-k:\ell}(D_{U}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)+b_{U}^{\ell-(k+1)})$
$\displaystyle+[W_{L,i}^{\ell-k:\ell}]_{+}(D_{L}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)$
$\displaystyle+b_{L}^{\ell-(k+1)}-D_{U}^{\ell-(k+1)}\tilde{f}^{1:\ell-(k+1)}(x)-b_{U}^{\ell-(k+1)})+b_{L,i}^{\ell-k:\ell}$
$\displaystyle=\bigg{(}W_{L,i}^{\ell-k:\ell}D_{U}^{\ell-(k+1)}+[W_{L,i}^{\ell-k:\ell}]_{+}(D_{L}^{\ell-(k+1)}-D_{U}^{\ell-(k+1)})\bigg{)}\tilde{f}^{1:\ell-(k+1)}(x)$
$\displaystyle+W_{L,i}^{\ell-k:\ell}b_{U}^{\ell-(k+1)}+[W_{L,i}^{\ell-k:\ell}]_{+}(b_{L}^{\ell-(k+1)}-b_{U}^{\ell-(k+1)})+b_{L,i}^{\ell-k:\ell}$
$\displaystyle=P_{L,i}^{\ell-k}\tilde{f}^{1:\ell-(k+1)}(x)+[W_{L,i}^{\ell-k:\ell}]_{-}b_{U}^{\ell-(k+1)}+[W_{L,i}^{\ell-k:\ell}]_{+}b_{L}^{\ell-(k+1)}+b_{L,i}^{\ell-k:\ell}$
$\displaystyle=P_{L,i}^{\ell-k}(W^{\ell-(k+1)}f^{1:\ell-(k+1)-1}(x)+b^{\ell-(k+1)})$
$\displaystyle+[W_{L,i}^{\ell-k:\ell}]_{-}b_{U}^{\ell-(k+1)}+[W_{L,i}^{\ell-k:\ell}]_{+}b_{L}^{\ell-(k+1)}+b_{L,i}^{\ell-k:\ell}$
$\displaystyle=P_{L,i}^{\ell-k}W^{\ell-(k+1)}f^{1:\ell-(k+1)-1}(x)$
$\displaystyle+P_{L,i}^{\ell-k}b^{\ell-(k+1)}+[W_{L,i}^{\ell-k:\ell}]_{-}b_{U}^{\ell-(k+1)}+[W_{L,i}^{\ell-k:\ell}]_{+}b_{L}^{\ell-(k+1)}+b_{L,i}^{\ell-k:\ell}$
$\displaystyle=W_{L,i}^{\ell-(k+1):\ell}f^{1:\ell-(k+1)-1}(x)+b_{L,i}^{\ell-(k+1):\ell}$
$\displaystyle=T_{L}^{\ell-(k+1):\ell}(f^{1:\ell-(k+1)-1}(x))_{i}$

This shows that

$T_{L}^{\ell-k:\ell}(f^{1:\ell-k-1}(x))_{i}\geq
T_{L}^{\ell-k-1:\ell}(f^{1:\ell-k-2}(x))_{i}$

By inductive hypothesis,

$f^{1:\ell}(x)_{i}\geq T_{L}^{\ell-k:\ell}(f^{1:\ell-k-1}(x))_{i}\geq
T_{L}^{\ell-k-1:\ell}(f^{1:\ell-k-2}(x))_{i}$

The case for $T_{U}^{\ell-k-1:\ell}(f^{1:\ell-k-2}(x))$ can be proved
similarly. Thus, it can be shown inductively that first statement holds for
any $k\in\\{0,\dots\ell-1\\}$. The second statement can be shown by letting
$\ell=m$ and $k=\ell-1$ and noting that $f^{1:0}(x)=x$. ∎

##  Appendix B Proof of Corollary 2.0.1

See 2.0.1

###### Proof.

To prove the first statement, we first claim that for any $\ell\in[m]$, it
holds that $\forall x~{}s.t.~{}\alpha^{0}\preceq x\preceq\beta^{0}$,

$\hat{\alpha}^{\ell}\preceq\tilde{f}^{1:\ell}(x)=W^{\ell}f^{1:\ell-1}(x)+b^{\ell}\preceq\hat{\beta}^{\ell}$

Since the algorithm’s instruction implies that
$(\hat{\alpha}^{\ell},\hat{\beta}^{\ell})$ is either calculated by IBP
iteration or is an intersection of previously computed pre-activation bounds
and the LinApprox pre-activation bounds, we divide the proof of the claim by
these two cases.

#### Case 1: IBP pre-activation bounds

In this case, Lemma B.1 shows the first statement holds

#### Case 2: An intersection of existing and LinApprox bounds

In this case, we can prove the first statement by induction on the number of
times the existing bound gets updated: If it’s the first time, it corresponds
to the case where the existing bound is IBP pre-activation bounds, which
satisfies the condition for Proposition A.1 to hold by Lemma B.1. So to prove
the statement holds for LinApprox bounds, we can apply Proposition A.1 on the
sub-network $\tilde{f}^{1:\ell}$: First, note that by Eq (3),
$\hat{\alpha}^{\prime}$ (line 7 of Algorithm 2) satisfies for any
$i\in[d_{\ell}]$,

$\displaystyle\hat{\alpha}_{i}^{\prime}=(W_{L}^{1:\ell})_{i}\beta^{0}+[(W_{L}^{1:\ell})_{i}]_{+}(\alpha^{0}-\beta^{0})+(b_{L}^{1:\ell})_{i}$
$\displaystyle=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}(W_{L}^{1:\ell})_{i}x+(b_{L}^{1:\ell})_{i}=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}(T_{L}^{1:\ell}(x))_{i}$

By Proposition A.1,

$\hat{\alpha}_{i}^{\prime}=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}(T_{L}^{1:\ell}(x))_{i}\leq\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}^{1:\ell}_{i}(x)$

and similarly by Eq (4) and Proposition A.1,

$\hat{\beta}_{i}^{\prime}=\max_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{U}^{1:\ell}(x)_{i}\geq\max_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}^{1:\ell}(x)_{i}$

This shows the first statement holds for the intersection of IBP pre-
activation bounds and the LinApprox bounds based off it. Now, using the same
argument we can prove inductively the first statement holds: That is, we can
assume the first statement holds when the existing bound is updated for the
$k$-th time (replacing the IBP pre-activation bound with the updated
$\hat{\alpha},\hat{\beta}$) and show that it holds when the existing bound is
updated for $k+1$-th time.

We prove the second statement by noting that

$\alpha^{m}=g^{m}(\hat{\alpha}^{m})=\hat{\alpha}^{m}\preceq\tilde{f}^{1:m}(x)$

where the inequality is implied by applying the first statement to
$\tilde{f}^{1:m}$. This concludes the proof. ∎

######  Lemma B.1 (Correctness of IBP pre-activation bounds).

Let $f^{1:m}$ be a $m$-layer feed-forward network, and let
$(\hat{\alpha}^{\ell},\hat{\beta}^{\ell}),\ell\in[m]$ be the pre-activation
bounds calculated by IBP-Lin with null schedule vector (i.e., IBP). Then for
any $x$ such that $\alpha^{0}\preceq x\preceq\beta^{0}$,

$\hat{\alpha}^{\ell}\preceq\tilde{f}^{1:\ell}(x)\preceq\hat{\beta}^{\ell}$

###### Proof.

We prove the lemma by induction on $\ell$:

#### Base case $\ell=1$:

By definition of pre-activation IBP bound, for any $i\in[d_{1}]$,

$\displaystyle\hat{\alpha}_{i}^{1}=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}W_{i}^{1}x+b_{i}^{1}=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:1}(x)\leq\tilde{f}_{i}^{1:1}(x),~{}~{}~{}\forall\alpha^{0}\preceq
x\preceq\beta^{0}$

and

$\displaystyle\hat{\beta}_{i}^{1}=\max_{\alpha^{0}\preceq
x\preceq\beta^{0}}W_{i}^{1}x+b_{i}^{1}=\max_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:1}(x)\geq\tilde{f}_{i}^{1:1}(x),~{}~{}~{}\forall\alpha^{0}\preceq
x\preceq\beta^{0}$

Therefore,

$\hat{\alpha}^{1}\preceq\tilde{f}^{1:1}(x)\preceq\hat{\beta}^{1}~{}~{}~{}\forall\alpha^{0}\preceq
x\preceq\beta^{0}$

This shows the claim holds for the base case.

#### From $\ell$ to $\ell+1$:

Suppose the statement holds for some $\ell$, we show it holds for $\ell+1$. By
definition, for any $i\in[d_{\ell+1}]$,

$\hat{\alpha}_{i}^{\ell+1}=\min_{\alpha^{\ell}\preceq
x\preceq\beta^{\ell}}W_{i}^{\ell+1}x+b_{i}^{\ell+1}$

where $\alpha^{\ell}=g^{\ell}(\hat{\alpha}^{\ell})$ and for any $i\in
d_{\ell}$, $\alpha_{i}^{\ell}=g^{\ell}(\hat{\alpha}_{i}^{\ell})$. By the
inductive hypothesis

$\hat{\alpha}_{i}^{\ell}\leq\tilde{f}_{i}^{1:\ell}(x),~{}~{}\forall
i\in[d_{\ell}]$

and since $g^{\ell}$ is non-decreasing,

$\alpha_{i}^{\ell}=g^{\ell}(\hat{\alpha}_{i}^{\ell})\leq
g^{\ell}(\tilde{f}_{i}^{1:\ell}(x))=f_{i}^{1:\ell}(x)$

Similarly, it can be derived that for any $\alpha^{0}\preceq
x\preceq\beta^{0}$,

$f^{1:\ell}(x)\preceq\beta^{\ell}$

And thus, for any $x$ such that $\alpha^{0}\preceq x\preceq\beta^{0}$, for any
$i\in[d_{\ell+1}]$,

$\displaystyle\hat{\alpha}_{i}^{\ell+1}=\min_{\alpha^{\ell}\preceq
x\preceq\beta^{\ell}}W_{i}^{\ell+1}x+b_{i}^{\ell+1}\leq
W_{i}^{\ell+1}f^{1:\ell}(x)+b_{i}^{\ell+1},\mbox{~{}~{}for
any~{}}\alpha^{0}\preceq x\preceq\beta^{0}$

which implies

$\hat{\alpha}^{\ell+1}\preceq
W^{\ell+1}f^{1:\ell}(x)+b^{\ell+1}=\tilde{f}^{1:\ell+1}(x)\mbox{~{}~{}for
any~{}}\alpha^{0}\preceq x\preceq\beta^{0}$

Similarly, it can be derived that

$\tilde{f}^{1:\ell+1}(x)\preceq\hat{\beta}^{\ell+1}\mbox{~{}~{}for
any~{}}\alpha^{0}\preceq x\preceq\beta^{0}$

which proves the lemma by induction. ∎

##  Appendix C Proof of Proposition 3.1

See 3.1

###### Proof.

We first prove the case for the lower bound on $\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}$. Let $x^{\star}$ denote a
minimizer of the modified network function at dimension $i$, i.e.,

$\tilde{f}_{i}^{\ell-k:\ell}(x^{\star})=\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$

and let $\hat{x}$ denote a minimizer of the lower bound function at dimension
$i$,

$T_{L}^{\ell-k:\ell}(\hat{x})_{i}=\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}$

Since

$\displaystyle\tilde{f}_{i}^{\ell-k:\ell}(x^{\star})-T_{L}^{\ell-k:\ell}(\hat{x})_{i}=\underbrace{\tilde{f}_{i}^{\ell-k:\ell}(x^{\star})-\tilde{f}_{i}^{\ell-k:\ell}(\hat{x})}_{A}+\underbrace{\tilde{f}_{i}^{\ell-k:\ell}(\hat{x})-T_{L}^{\ell-k:\ell}(\hat{x})_{i}}_{B}$

Term $A\leq 0$ by minimality of $\tilde{f}_{i}^{\ell-k:\ell}(x^{\star})$, and
we can bound the difference $B$ by the fact that
$\tilde{f}_{i}^{\ell-k:\ell}(x)$ is between $T_{L}^{\ell-k:\ell}(x)$ and
$T_{U}^{\ell-k:\ell}(x)$ for any $x$ within the constraint set:

$\displaystyle B\leq\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}~{}\tilde{f}_{i}^{\ell-k:\ell}(x)-T_{L}^{\ell-k:\ell}(x)_{i}$
$\displaystyle\leq\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}~{}T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}$

So we can upper bound
$\tilde{f}_{i}^{\ell-k:\ell}(\hat{x})-T_{L}^{\ell-k:\ell}(\hat{x})_{i}$ by
upper bounding
$\max_{x}~{}T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}$, where

$\displaystyle
T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}=(W_{U}^{\ell-k:\ell}-W_{L}^{\ell-k:\ell})_{i}x+(b_{U}^{\ell-k:\ell}-b_{L}^{\ell-k:\ell})_{i}$

We first prove by induction on $k$ that
$W^{\ell-k:\ell}_{U}=W^{\ell-k:\ell}_{L}$ for parallelogram approximation. For
$k=0$, $W_{U}^{\ell:\ell}-W_{L}^{\ell:\ell}=W^{\ell}-W^{\ell}=0\,.$ For any
$k$, given that $W_{U}^{\ell-k:\ell}-W_{L}^{\ell-k:\ell}=0$, we have

$\displaystyle
W_{U}^{\ell-k-1:\ell}-W_{L}^{\ell-k-1:\ell}=(P^{\ell-k}_{U}-P^{\ell-k}_{L})W^{\ell-k-1}$
$\displaystyle=(W^{\ell-k:\ell}_{U}-W^{\ell-k:\ell}_{L})D_{U}^{\ell-k-1}W^{\ell-k-1}=0$

where in the derivation above the terms involving
$D_{L}^{\ell-k}-D_{U}^{\ell-k}$ equal to zero because we are applying
parallelogram approximation here. By induction, we have

$W_{U}^{\ell-k:\ell}-W_{L}^{\ell-k:\ell}=0$

Let $W^{\ell-k:\ell}:=W_{U}^{\ell-k:\ell}=W_{L}^{\ell-k:\ell}$. We get

$\displaystyle
T_{U}^{\ell-k:\ell}(x)-T_{L}^{\ell-k:\ell}(x)=b_{U}^{\ell-k:\ell}-b_{L}^{\ell-k:\ell}=(P_{U}^{\ell-k+1:\ell}-P_{L}^{\ell-k+1:\ell})b^{\ell-k}$
$\displaystyle+([W_{U}^{\ell-k+1:\ell}]_{+}-[W_{U}^{\ell-k+1:\ell}]_{-})b^{\ell-k}_{U}+([W_{U}^{\ell-k+1:\ell}]_{-}-[W_{U}^{\ell-k+1:\ell}]_{+})b^{\ell-k}_{L}$
$\displaystyle+b_{U}^{\ell-k+1:\ell}-b_{L}^{\ell-k+1:\ell}$
$\displaystyle=(W^{\ell-k+1:\ell}_{U}-W^{\ell-k+1:\ell}_{L})D_{U}^{\ell-k}b^{\ell-k}$
$\displaystyle+|W_{U}^{\ell-k+1:\ell}|b^{\ell-k}_{U}-|W_{U}^{\ell-k+1:\ell}|b^{\ell-k}_{L}+b_{U}^{\ell-k+1:\ell}-b_{L}^{\ell-k+1:\ell}$
$\displaystyle=|W^{\ell-k+1:\ell}|(b^{\ell-k}_{U}-b^{\ell-k}_{L})+b_{U}^{\ell-k+1:\ell}-b_{L}^{\ell-k+1:\ell}$
$\displaystyle=\dots=$
$\displaystyle|W^{\ell-k+1:\ell}|(b^{\ell-k}_{U}-b^{\ell-k}_{L})+|W^{\ell-k+2:\ell}|(b^{\ell-k+1}_{U}-b^{\ell-k+1}_{L})+\dots+|W^{\ell:\ell}|(b^{\ell-1}_{U}-b^{\ell-1}_{L})$
$\displaystyle=\sum_{s=0}^{k-1}|W^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$

So for each dimension $i$,

$T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}=\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$

Note that this quantity does not depend on $x$, so

$\displaystyle\tilde{f}_{i}^{\ell-k:\ell}(x^{\star})-T_{L}^{\ell-k:\ell}(\hat{x})_{i}\leq\max_{x}T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}$
$\displaystyle=\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$

For the inequality involving

$\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{U}^{\ell-k:\ell}(x)_{i}-\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)\,,$

We similarly have

$\displaystyle\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{U}^{\ell-k:\ell}(x)_{i}-\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$
$\displaystyle\leq\max_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}~{}T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}$

So we get the exact same bound as before. ∎

######  Lemma C.1 (Property of parallelogram relaxation).

Let $f^{1:m}$ be a neural network that can be layer-wise outer approximated by
parallelogram relaxation. For any $\ell$ and $0<k<\ell$, let
$\tilde{f}^{\ell-k:\ell}$ denote the last-layer modified version of sub-
network $f^{\ell-k:\ell}$. Let $T_{L}^{\ell-k:\ell},T_{U}^{\ell-k:\ell}$ be a
multi-layer outer approximation of $\tilde{f}^{\ell-k:\ell}$ based on
parallelogram relaxation. Then 1). $W_{L}^{\ell-k:\ell}=W_{U}^{\ell-k:\ell}$
and 2). $T_{U}^{\ell-k:\ell}(x)-T_{L}^{\ell-k:\ell}(x)$ doesn’t depend on $x$.

###### Proof.

We prove by induction on $k$.

$\displaystyle
T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}=(W_{U}^{\ell-k:\ell}-W_{L}^{\ell-k:\ell})_{i}x+(b_{U}^{\ell-k:\ell}-b_{L}^{\ell-k:\ell})_{i}$

For $k=0$, by property of parallelogram approximation,

$W_{U}^{\ell:\ell}-W_{L}^{\ell:\ell}=W^{\ell}-W^{\ell}=0\mbox{~{}~{}and~{}~{}}b_{U}^{\ell:\ell}-b_{L}^{\ell:\ell}=b^{\ell}-b^{\ell}=0$

For any $k$, given that $W_{U}^{\ell-k:\ell}-W_{L}^{\ell-k:\ell}=0$, we have

$\displaystyle
W_{U}^{\ell-k-1:\ell}-W_{L}^{\ell-k-1:\ell}=(P^{\ell-k}_{U}-P^{\ell-k}_{L})W^{\ell-k-1}$
$\displaystyle=(W^{\ell-k:\ell}_{U}-W^{\ell-k:\ell}_{L})D_{U}^{\ell-k-1}W^{\ell-k-1}=0$

where in the derivation above the terms involving
$D_{L}^{\ell-k}-D_{U}^{\ell-k}$ equal to zero due to the property of
parallelogram relaxation again. By induction, we have

$W_{U}^{\ell-k:\ell}-W_{L}^{\ell-k:\ell}=0$

This implies that for any $x$ and $\forall i\in[d_{\ell}]$

$T_{U}^{\ell-k:\ell}(x)_{i}-T_{L}^{\ell-k:\ell}(x)_{i}=(b_{U}^{\ell-k:\ell}-b_{L}^{\ell-k:\ell})_{i}$

which is independent of $x$. ∎

##  Appendix D Proof of Proposition 3.2

See 3.2

###### Proof.

To prove the first statement, any neuron $i$ satisfies

$\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}=\min_{x}D_{i}^{1}W^{1}x=D_{ii}^{1}\min_{x}W_{i}^{1}x=D_{ii}^{1}\hat{\alpha}_{i}^{1}$

For $i\in\mathcal{I}$,
$D_{ii}=\frac{\hat{\beta}_{i}^{1}}{\hat{\beta}_{i}^{1}-\hat{\alpha}_{i}^{1}}$
and

$\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}=\frac{\hat{\beta}_{i}^{1}}{\hat{\beta}_{i}^{1}-\hat{\alpha}_{i}^{1}}\hat{\alpha}_{i}^{1}$

where

$\hat{\alpha}^{1}_{i}=W_{i}^{1}x_{0}-|W_{i}^{1}|\epsilon\vec{1}=W_{i}^{1}x_{0}-\epsilon\|W_{i}^{1}\|_{1}\mbox{
~{}~{} and ~{}~{}
}\hat{\beta}^{1}_{i}=W_{i}^{1}x_{0}+|W_{i}^{1}|\epsilon\vec{1}=W_{i}^{1}x_{0}+\epsilon\|W_{i}^{1}\|_{1}$

The expected gap is

$\displaystyle\operatorname{\mathbb{E}}\big{(}\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{x}[W_{i}^{1}x]_{+}\big{)}$
$\displaystyle=\operatorname{\mathbb{P}}(i\in\mathcal{I})\operatorname{\mathbb{E}}\big{(}\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{x}[W_{i}^{1}x]_{+}|i\in\mathcal{I}\big{)}$
$\displaystyle+(1-\operatorname{\mathbb{P}}(i\in\mathcal{I}))\operatorname{\mathbb{E}}\big{(}\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{x}[W_{i}^{1}x]_{+}|i\notin\mathcal{I}\big{)}$
$\displaystyle\leq\operatorname{\mathbb{P}}(i\in\mathcal{I})\operatorname{\mathbb{E}}\big{(}\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{x}[W_{i}^{1}x]_{+}|i\in\mathcal{I}\big{)}$
$\displaystyle\leq\operatorname{\mathbb{P}}(i\in\mathcal{I})\operatorname{\mathbb{E}}\big{(}\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}|i\in\mathcal{I}\big{)}$
$\displaystyle=\operatorname{\mathbb{P}}(i\in\mathcal{I})\operatorname{\mathbb{E}}\big{(}\frac{\hat{\beta}_{i}^{1}}{\hat{\beta}_{i}^{1}-\hat{\alpha}_{i}^{1}}\hat{\alpha}_{i}^{1}|i\in\mathcal{I}\big{)}$
$\displaystyle=\operatorname{\mathbb{P}}(i\in\mathcal{I})\operatorname{\mathbb{E}}\big{(}\frac{(W_{i}^{1}x_{0})^{2}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}\big{|}i\in\mathcal{I}\big{)}$

where the first inequality is due to the correctness of IBP-Lin, which implies
$\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{x}[W_{i}^{1}]_{+}\leq 0$ always
hold, and the second inequality is due to non-negativity of
$\min_{x}[W_{i}^{1}x]_{+}$. Since

$\\{i\in\mathcal{I}\\}=\\{W_{i}^{1}x_{0}<\epsilon\|W_{i}^{1}\|_{1}\\}\cap\\{W_{i}^{1}x_{0}>-\epsilon\|W_{i}^{1}\|_{1}\\}=\\{(W_{i}^{1}x_{0})^{2}<(\epsilon\|W_{i}^{1}\|_{1})^{2}\\}$

We get

$\displaystyle\operatorname{\mathbb{E}}\big{(}\frac{(W_{i}^{1}x_{0})^{2}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}\big{|}i\in\mathcal{I}\big{)}=\frac{\operatorname{\mathbb{E}}\big{(}(W_{i}^{1}x_{0})^{2}|i\in\mathcal{I}\big{)}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}$
$\displaystyle\leq\frac{\operatorname{\mathbb{E}}(W_{i}^{1}x_{0})^{2}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}=\frac{\|W_{i}^{1}\|_{2}^{2}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}$

Substituting $\kappa_{i}=\frac{\|W_{i}^{1}\|_{1}}{\|W_{i}^{1}\|_{2}}$ in the
inequality above, we get

$\displaystyle\operatorname{\mathbb{E}}\big{(}\frac{(W_{i}^{1}x_{0})^{2}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}\big{|}i\in\mathcal{I}\big{)}\leq\frac{\|W_{i}^{1}\|_{2}^{2}-(\epsilon\kappa_{i}\|W_{i}^{1}\|_{2})^{2}}{2\epsilon\kappa_{i}\|W_{i}^{1}\|_{2}}$
$\displaystyle=\frac{\|W_{i}^{1}\|_{2}-(\epsilon\kappa_{i})^{2}\|W_{i}^{1}\|_{2}}{2\epsilon\kappa_{i}}=\frac{\|W_{i}^{1}\|_{2}}{2}(\frac{1}{\epsilon\kappa_{i}}-\epsilon\kappa_{i})$

By property of Gaussian distribution, we can explicitly represent
$\operatorname{\mathbb{P}}(i\in\mathcal{I})$ as

$\operatorname{\mathbb{P}}(|W_{i}^{1}x_{0}|<\epsilon\|W_{i}^{1}\|_{1})=\operatorname{\mathbb{P}}(|\frac{W_{i}^{1}x_{0}}{\|W_{i}^{1}\|_{2}}|<\epsilon\frac{\|W_{i}^{1}\|_{1}}{\|W_{i}^{1}\|_{2}})=2\Phi(\epsilon\frac{\|W_{i}^{1}\|_{1}}{\|W_{i}^{1}\|_{2}})-1\geq
0$

Here the second equality holds because
$\frac{W_{i}^{1}x_{0}}{\|W_{i}^{1}\|_{2}}$ has standard normal distribution.
Therefore,

$\displaystyle\operatorname{\mathbb{E}}\big{(}\min_{x}D_{i}^{1}W^{1}x+(b_{L}^{1})_{i}-\min_{x}[W_{i}^{1}x]_{+}\big{)}$
$\displaystyle\leq\operatorname{\mathbb{P}}(i\in\mathcal{I})\operatorname{\mathbb{E}}\big{(}\frac{(W_{i}^{1}x_{0})^{2}-(\epsilon\|W_{i}^{1}\|_{1})^{2}}{2\epsilon\|W_{i}^{1}\|_{1}}\big{|}i\in\mathcal{I}\big{)}$
$\displaystyle\leq(2\Phi(\epsilon\kappa_{i})-1)\frac{\|W_{i}^{1}\|_{2}}{2}(\frac{1}{\epsilon\kappa_{i}}-\epsilon\kappa_{i})=(\Phi(\epsilon\kappa_{i})-1/2)\|W_{i}^{1}\|_{2}(\frac{1}{\epsilon\kappa_{i}}-\epsilon\kappa_{i})$

To prove the second statement, consider $D_{i}^{1}W^{1}x+(b_{U}^{1})_{i}$ for
any $i$. For $i\in\mathcal{I}_{-}\cup\mathcal{I}_{+}$,

$D_{i}^{1}W^{1}x+(b_{U}^{1})_{i}=D_{i}^{1}W^{1}x=[W_{i}^{1}x]_{+}$

For $i\in\mathcal{I}$,

$\max_{x}D_{i}^{1}W^{1}x+(b_{U}^{1})_{i}=D_{i}^{1}\max_{x}W^{1}x+(b_{U}^{1})_{i}=\frac{\hat{\beta}_{i}^{1}}{\hat{\beta}_{i}^{1}-\hat{\alpha}_{i}^{1}}\hat{\beta}_{i}^{1}-\frac{\hat{\alpha}_{i}^{1}\hat{\beta}_{i}^{1}}{\hat{\beta}_{i}^{1}-\hat{\alpha}_{i}^{1}}=\hat{\beta}_{i}^{1}$

And for $i\in\mathcal{I}$,

$\max_{x}[W_{i}^{1}x]_{+}=[\hat{\beta}_{i}^{1}]_{+}=\hat{\beta}_{i}^{1}$

which finishes proving the second statement. ∎

##  Appendix E Proof of Proposition 3.3

See 3.3

###### Proof.

By Proposition 3.1,

$\displaystyle\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}\geq\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$
$\displaystyle-\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})$

By Lemma F.1, for any $s=\\{0,\dots,\ell-3\\}$,

$b_{U}^{\ell-s-1}=b_{L}^{\ell-s-1}$

This implies that for any $1\leq k\leq\ell-2$,

$\sum_{s=0}^{k-1}|W_{i}^{\ell-s:\ell}|(b^{\ell-s-1}_{U}-b^{\ell-s-1}_{L})=0$

So

$\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}\geq\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$

But by correctness of LinApprox (Proposition A.1 applied to the sub-network
$\tilde{f}^{\ell-k:\ell}$),

$\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}T_{L}^{\ell-k:\ell}(x)_{i}\leq\min_{\alpha^{\ell-k-1}\preceq
x\preceq\beta^{\ell-k-1}}\tilde{f}_{i}^{\ell-k:\ell}(x)$

This proves the first statement. The second statement can be proved similarly.
∎

##  Appendix F Proof of Proposition 3.4

See 3.4

###### Proof.

Proof of first statement: By Lemma F.1, for any $s\in\\{0,\dots,m-3\\}$,
$b_{U}^{m-s-1}-b_{L}^{m-s-1}=0$. This implies that for any $1\leq k\leq m-2$,

$\sum_{s=0}^{k-1}|W_{i}^{m-s:m}|(b_{U}^{m-s-1}-b_{L}^{m-s-1})=0$

By Proposition 3.1, for any $k\in\\{0,\dots,m-1\\}$,

$\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{m-k:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{m-k:m}(x)\geq-\sum_{s=0}^{k-1}|W_{i}^{m-s:m}|(b_{U}^{m-s-1}-b_{L}^{m-s-1})$

Let $k=m-1$,

$\displaystyle\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)\geq-\sum_{s=0}^{m-2}|W_{i}^{m-s:m}|(b_{U}^{m-s-1}-b_{L}^{m-s-1})$
$\displaystyle=-\sum_{s=0}^{m-3}|W_{i}^{m-s:m}|(b_{U}^{m-s-1}-b_{L}^{m-s-1})-|W_{i}^{2:m}|(b_{U}^{1}-b_{L}^{1})$
$\displaystyle=-|W_{i}^{2:m}|(b_{U}^{1}-b_{L}^{1})$

Temporarily let $r:=\frac{1}{d^{p}}$. By Lemma F.2,

$|W^{2:m}|=|r^{m-1}d^{m-2}\vec{1}\vec{1}^{T}|=r^{m-1}d^{m-2}\vec{1}\vec{1}^{T}$

Now consider $b_{U}^{1}-b_{L}^{1}=b_{U}^{1}$, which is determined by pre-
activation vectors $\hat{\alpha}^{1},\hat{\beta}^{1}$:

$\hat{\alpha}^{1}=W^{1}\beta^{0}+[W^{1}]_{+}(\alpha^{0}-\beta^{0})=W^{1}\alpha^{0}=W^{1}x_{0}-\epsilon
W^{1}\vec{1}$

and

$\hat{\beta}^{1}=W^{1}\beta^{0}+[-W^{1}]_{+}(\beta^{0}-\alpha^{0})=W^{1}\beta^{0}=W^{1}x_{0}+\epsilon
W^{1}\vec{1}$

For any $i$ such that $i\in\mathcal{I}$,

$\displaystyle(b_{U}^{1})_{i}=\frac{-\hat{\alpha}_{i}^{1}\hat{\beta}_{i}^{1}}{\hat{\beta}_{i}^{1}-\hat{\alpha}_{i}^{1}}=\frac{-((W_{i}^{1}x_{0})^{2}-(\epsilon
W_{i}^{1}\vec{1})^{2})}{2\epsilon W_{i}^{1}\vec{1}}$
$\displaystyle\leq\frac{(\epsilon W_{i}^{1}\vec{1})^{2}}{2\epsilon
W_{i}^{1}\vec{1}}=\frac{\epsilon\|W_{i}^{1}\|_{1}}{2}=\frac{\epsilon rd}{2}$

For $i\notin\mathcal{I}$, $(b_{U}^{1})_{i}=0\leq\frac{\epsilon rd}{2}$.
Therefore, we can conclude that

$\displaystyle\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)$
$\displaystyle\geq-|W_{i}^{2:m}|(b_{U}^{1}-b_{L}^{1})=-r^{m-1}d^{m-2}\vec{1}_{i}\vec{1}^{T}\frac{\epsilon
rd}{2}\vec{1}=-\frac{\epsilon}{2}r^{m}d^{m}=-\frac{\epsilon}{2}\frac{1}{d^{m(p-1)}}$

Since $m\geq\frac{1}{p-1}\log_{d}\frac{\epsilon}{2\delta}$, we get

$(\frac{1}{d^{p-1}})^{m}\frac{1}{2}\epsilon\leq\delta$

And

$\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)\\\ \geq-\delta$

#### Proof of second statement:

By the first statement of Lemma F.2, $T_{L}^{1:m}(x)=W^{1:m}x$. Temporarily
let denote $r=\frac{1}{d^{p}}$; by the second statement of Lemma F.2,

$\displaystyle\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}W_{i}^{1:m}x=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}W_{i}^{2:m}D^{1}W^{1}x$
$\displaystyle=W_{i}^{2:m}D^{1}W^{1}\beta^{0}+[W_{i}^{2:m}D^{1}W^{1}]_{+}(\alpha^{0}-\beta^{0})=W_{i}^{2:m}D^{1}W^{1}\alpha^{0}$

On the other hand, since for all $\ell\in[m]$, $W_{ij}^{\ell}\geq 0$,

$\displaystyle\min_{x}\tilde{f}_{i}^{1:m}(x)=\min_{x}W_{i}^{m}\dots[W^{2}[W^{1}x]_{+}]_{+}$
$\displaystyle=\min_{x}W_{i}^{m}\dots
W^{2}[W^{1}x]_{+}=\min_{x}W_{i}^{2:m}[W^{1}x]_{+}$

Since by property of IBP activation bounds, for all $\alpha^{0}\preceq
x\preceq\beta^{0}$,

$[\hat{\alpha}^{1}]_{+}\preceq[W^{1}x]_{+}\preceq[\hat{\beta}^{1}]_{+}$

So

$\displaystyle\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)=\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}W_{i}^{2:m}[W^{1}x]_{+}$
$\displaystyle\geq\min_{[\hat{\alpha}^{1}]_{+}\preceq
y\preceq[\hat{\beta}^{1}]_{+}}W_{i}^{2:m}y$
$\displaystyle=W_{i}^{2:m}[\hat{\beta}^{1}]_{+}+[W_{i}^{2:m}]_{+}([\hat{\alpha}^{1}]_{+}-[\hat{\beta}^{1}]_{+})$
$\displaystyle=W_{i}^{2:m}[\hat{\alpha}^{1}]_{+}$

Therefore,

$\displaystyle\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)$ $\displaystyle\leq
W_{i}^{2:m}D^{1}W^{1}\alpha^{0}-W_{i}^{2:m}[\hat{\alpha}^{1}]_{+}$

By definition of IBP pre-activation bounds, for all $i$,

$\hat{\alpha}_{i}^{1}=W_{i}^{1}\beta^{0}+[W_{i}^{1}]_{+}(\alpha^{0}-\beta^{0})=W_{i}^{1}\alpha^{0}$

and thus,

$\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)\leq
W_{i}^{2:m}D^{1}\hat{\alpha}^{1}-W_{i}^{2:m}[\hat{\alpha}^{1}]_{+}$

Consider any $j$,

$D_{j}^{1}\hat{\alpha}^{1}=D_{jj}^{1}\hat{\alpha}_{j}^{1}=\begin{cases}\hat{\alpha}_{j}^{1}=[\hat{\alpha}_{j}^{1}]_{+}~{}~{}j\in\mathcal{I}_{+}\\\
0=[\hat{\alpha}_{j}^{1}]_{+}~{}~{}j\in\mathcal{I}_{-}\\\
\frac{\hat{\beta}_{j}^{1}}{\hat{\beta}_{j}^{1}-\hat{\alpha}_{j}^{1}}\hat{\alpha}_{j}^{1}~{}~{}j\in\mathcal{I}\end{cases}$

This implies that

$D_{j}^{1}\hat{\alpha}^{1}-[\hat{\alpha}_{j}^{1}]_{+}=\begin{cases}0\text{~{}~{}if~{}~{}}j\notin\mathcal{I}\\\
\frac{\hat{\beta}_{j}^{1}\hat{\alpha}_{j}^{1}}{\hat{\beta}_{j}^{1}-\hat{\alpha}_{j}^{1}}~{}~{}j\in\mathcal{I}\end{cases}$

Since

$\hat{\alpha}_{j}^{1}=W_{j}^{1}\alpha^{0}=W_{j}^{1}x_{0}-\epsilon\|W_{j}^{1}\|_{1}\mbox{~{}~{}and~{}~{}}\hat{\beta}_{j}^{1}=W_{j}^{1}\beta^{0}=W_{j}^{1}x_{0}+\epsilon\|W_{j}^{1}\|_{1}$

We have

$\frac{\hat{\beta}_{j}^{1}}{\hat{\beta}_{j}^{1}-\hat{\alpha}_{j}^{1}}\hat{\alpha}_{j}^{1}=\frac{(W_{j}^{1}x_{0})^{2}-(\epsilon\|W_{j}^{1}\|_{1})^{2}}{2\epsilon\|W_{j}^{1}\|_{1}}$

Therefore,

$\displaystyle\operatorname{\mathbb{E}}_{x_{0}}\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)$
$\displaystyle\leq\operatorname{\mathbb{E}}W_{i}^{2:m}(D^{1}\hat{\alpha}^{1}-[\hat{\alpha}^{1}]_{+})=\sum_{j}\operatorname{\mathbb{E}}W_{ij}^{2:m}(D_{j}^{1}\hat{\alpha}^{1}-[\hat{\alpha}_{j}^{1}]_{+})$
$\displaystyle=\sum_{j}\operatorname{\mathbb{E}}r^{m-1}d^{m-2}(\vec{1}\vec{1}^{T})_{ij}(D_{j}^{1}\hat{\alpha}^{1}-[\hat{\alpha}_{j}^{1}]_{+})\text{~{}~{}~{}
(By Lemma~{}\ref{lemma:approx-error-prop-from-first-layer}) }$
$\displaystyle=\sum_{j}r^{m-1}d^{m-2}\operatorname{\mathbb{E}}(D_{j}^{1}\hat{\alpha}^{1}-[\hat{\alpha}_{j}^{1}]_{+})$
$\displaystyle=\sum_{j}r^{m-1}d^{m-2}\operatorname{\mathbb{E}}\big{(}D_{j}^{1}\hat{\alpha}^{1}-[\hat{\alpha}_{j}^{1}]_{+}|j\in\mathcal{I}\big{)}\operatorname{\mathbb{P}}(j\in\mathcal{I})$
$\displaystyle=\sum_{j}r^{m-1}d^{m-2}\operatorname{\mathbb{E}}\big{(}\frac{(W_{j}^{1}x_{0})^{2}-(\epsilon\|W_{j}^{1}\|_{1})^{2}}{2\epsilon\|W_{j}^{1}\|_{1}}|j\in\mathcal{I}\big{)}\operatorname{\mathbb{P}}(j\in\mathcal{I})$

By the same argument as in proof of statement 1 of Proposition 3.2, we get

$\displaystyle\operatorname{\mathbb{E}}\big{(}\frac{(W_{j}^{1}x_{0})^{2}-(\epsilon\|W_{j}^{1}\|_{1})^{2}}{2\epsilon\|W_{j}^{1}\|_{1}}|j\in\mathcal{I}\big{)}\leq\frac{\|W_{j}^{1}\|_{2}^{2}-(\epsilon\|W_{j}^{1}\|_{1})^{2}}{2\epsilon\|W_{j}^{1}\|_{1}}$

Since $\|W_{j}^{1}\|_{2}^{2}=r^{2}d$ and $\|W_{j}^{1}\|_{1}^{2}=(rd)^{2}$, we
get

$\operatorname{\mathbb{E}}\big{(}\frac{(W_{j}^{1}x_{0})^{2}-(\epsilon\|W_{j}^{1}\|_{1})^{2}}{2\epsilon\|W_{j}^{1}\|_{1}}|j\in\mathcal{I}\big{)}\leq\frac{r^{2}d-\epsilon^{2}r^{2}d^{2}}{2\epsilon
rd}$

We bound $\operatorname{\mathbb{P}}(j\in\mathcal{I})$ using the same argument
as in statement 1 of Proposition 3.2: By property of Gaussian distribution, we
can explicitly represent $\operatorname{\mathbb{P}}(j\in\mathcal{I})$ as

$\displaystyle\operatorname{\mathbb{P}}(|W_{j}^{1}x_{0}|<\epsilon\|W_{j}^{1}\|_{1})=\operatorname{\mathbb{P}}(|\frac{W_{j}^{1}x_{0}}{\|W_{j}^{1}\|_{2}}|<\epsilon\frac{\|W_{j}^{1}\|_{1}}{\|W_{j}^{1}\|_{2}})$
$\displaystyle=2\Phi(\epsilon\frac{\|W_{j}^{1}\|_{1}}{\|W_{j}^{1}\|_{2}})-1=2\Phi(\epsilon\frac{rd}{r\sqrt{d}})-1=2\Phi(\epsilon\sqrt{d})-1$

Combining this with the equality earlier, we get

$\displaystyle\operatorname{\mathbb{E}}_{x_{0}}\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)$
$\displaystyle\leq\sum_{j=1}^{d}r^{m-1}d^{m-2}\frac{r^{2}d-\epsilon^{2}r^{2}d^{2}}{2\epsilon
rd}(2\Phi(\epsilon\sqrt{d})-1)$
$\displaystyle=\sum_{j=1}^{d}r^{m-1}d^{m-2}(\frac{r}{2\epsilon}-\frac{\epsilon
rd}{2})(2\Phi(\epsilon\sqrt{d})-1)$
$\displaystyle=(2\Phi(\epsilon\sqrt{d})-1)r^{m}d^{m-1}(\frac{1}{2\epsilon}-\frac{\epsilon
d}{2})$
$\displaystyle=(\Phi(\epsilon\sqrt{d})-1/2)r^{m}d^{m-1}(\frac{1}{\epsilon}-\epsilon
d)$

Since $\epsilon>\sqrt{1/d}$, which implies $\epsilon d-\frac{1}{\epsilon}>0$,
and since $m$ is chosen so that

$m>\frac{1}{1-p}\log_{d}\frac{Bd}{(\Phi(\epsilon\sqrt{d})-1/2)(\epsilon
d-\frac{1}{\epsilon})}$

It can be derived that

$(\Phi(\epsilon\sqrt{d})-1/2)r^{m}d^{m-1}(\epsilon d-\frac{1}{\epsilon})>B$

And we may conclude that

$\operatorname{\mathbb{E}}_{x_{0}}\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}T_{L}^{1:m}(x)_{i}-\min_{\alpha^{0}\preceq
x\preceq\beta^{0}}\tilde{f}_{i}^{1:m}(x)\leq-B$

∎

######  Lemma F.1 (“Zero-width” tube on non-negative matrices).

Suppose $T_{L}^{1:m},T_{U}^{1:m}$ are lower and upper linear approximation
functions to $\tilde{f}^{1:m}$ with network weights $W_{i,j}^{\ell}\geq 0$ and
$b_{i}^{\ell}=0$, for any $i,j\in[d]$, $\forall\ell\in[m-1]$. Then for any
$2\leq\ell\leq m-1$, $b_{U}^{\ell}=b_{L}^{\ell}=0$.

###### Proof.

Fix any $\alpha^{\ell-1},\beta^{\ell-1}$ for $\ell\geq 2$, by IBP iteration,

$\displaystyle\hat{\alpha}^{\ell}=W^{\ell}\beta^{\ell-1}+[W^{\ell}]_{+}(\alpha^{\ell}-\beta^{\ell})+b^{\ell}$
$\displaystyle=[W^{\ell}]_{-}\beta^{\ell-1}+[W^{\ell}]_{+}\alpha^{\ell-1}=[W^{\ell}]_{+}\alpha^{\ell-1}~{}~{}~{}(W_{ij}^{\ell}\geq
0)$ $\displaystyle\succeq 0$

where the last term $[W^{\ell}]_{+}\alpha^{\ell-1}$ is non-negative since for
$\ell>1$, the bound vector

$\alpha^{\ell-1}=g^{\ell-1}(\hat{\alpha}^{\ell-1})=[\hat{\alpha}^{\ell-1}]_{+}\succeq
0\,,$

So its inner product with the non-negative matrix $[W^{\ell}]_{+}$ is a non-
negative vector. Thus, $\forall i\in[d_{\ell}],\hat{\alpha}_{i}^{\ell}\geq 0$,
and by definition all output nodes at layer $\ell$ satisfies
$i\in\mathcal{I}_{+}$ (i.e.,
$0\leq\hat{\alpha}_{i}^{\ell}\leq\hat{\beta}_{i}^{\ell}$, for all
$i\in[d_{\ell}]$), and thus

$b_{U}^{\ell}=b_{L}^{\ell}=0$

∎

######  Lemma F.2.

Suppose $T_{L}^{1:m},T_{U}^{1:m}$ are lower and upper linear approximation
functions to $\tilde{f}^{1:m}$ with network weights $W_{i,j}^{\ell}\geq 0$ and
$b_{i}^{\ell}=0$, for any $i,j\in[d]$, $\forall\ell\in[m-1]$. Then

  1. 1.

$T_{L}^{1:m}(x)=W^{1:m}x$.

  2. 2.

In addition, suppose $\forall\ell\in[m],\forall i,j\in[d],W_{ij}^{\ell}=r$.
Then

$W^{1:m}=W^{2:m}D^{1}W^{1}~{}~{}~{}\mbox{where}~{}~{}W^{2:m}=r^{m-1}d^{m-2}\vec{1}\vec{1}^{T}$

###### Proof.

Proof of first statement: By definition,
$T_{L}^{1:m}(x)=W_{L}^{1:m}(x)+b_{L}^{1:m}$ (see Definition 3). By Lemma F.1,
for any $2\leq\ell\leq m-1$, $b_{U}^{\ell}=b_{L}^{\ell}=0$, which implies that

$\displaystyle
b_{L}^{1:m}=b_{L}^{m:m}+\sum_{k=1}^{m-1}[W^{k+1:m}]_{-}b_{U}^{k}+[W^{k+1:m}]_{+}b_{L}^{k}$
$\displaystyle=\sum_{k=1}^{m-1}[W^{k+1:m}]_{-}b_{U}^{k}+[W^{k+1:m}]_{+}b_{L}^{k}~{}~{}~{}(\mbox{$b_{L}^{m:m}=b^{m}=0$})$
$\displaystyle=(\sum_{k=2}^{m-1}[W^{k+1:m}]_{-}b_{U}^{k}+[W^{k+1:m}]_{+}b_{L}^{k})+[W^{2:m}]_{-}b_{U}^{1}+[W^{2:m}]_{+}b_{L}^{1}$
$\displaystyle=[W^{2:m}]_{-}b_{U}^{1}+[W^{2:m}]_{+}b_{L}^{1}~{}~{}~{}(b_{U}^{\ell}=b_{L}^{\ell}=0,\forall
2\leq\ell\leq m-1)$

On the other hand, $W^{2:m}$ is product of non-negative matrices, so
$W^{2:m}_{ij}\geq 0$ and thus

$[W^{2:m}]_{-}b_{U}^{1}+[W^{2:m}]_{+}b_{L}^{1}=[W^{2:m}]_{+}b_{L}^{1}=[W^{2:m}]_{+}0=0$

This shows that $T_{L}^{1:m}(x)=W_{L}^{1:m}x=W^{1:m}x$.

Proof of second statement: Consider $D_{ii}^{\ell}$ for any
$\ell\in\\{2,\dots,m\\}$, which is determined by the pre-activation IBP bounds
$\hat{\alpha}^{\ell}_{i},\hat{\beta}^{\ell}_{i}$:

$\hat{\alpha}_{i}^{\ell}=W_{i}^{\ell}\beta^{\ell-1}+[W_{i}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})=[W_{i}]_{-}\beta^{\ell-1}+[W_{i}]_{+}\alpha^{\ell-1}=[W_{i}]_{+}\alpha^{\ell-1}$

and

$\hat{\beta}_{i}^{\ell}=W_{i}^{\ell}\beta^{\ell-1}+[-W_{i}]_{+}(\beta^{\ell-1}-\alpha^{\ell-1})=[W_{i}]_{+}\beta^{\ell-1}+[W_{i}]_{-}\alpha^{\ell-1}=[W_{i}]_{+}\beta^{\ell-1}$

Since for any $\ell-1\geq 1$, the vectors $\alpha^{\ell-1},\beta^{\ell-1}$
obtained from IBP iteration are non-negative valued due to the ReLU operation
(i.e., $\alpha^{\ell-1}=g^{\ell-1}(\hat{\alpha}^{\ell-1})\succeq 0$ and
$\beta^{\ell-1}=g^{\ell-1}(\hat{\beta}^{\ell-1})\succeq 0$), we get

$\hat{\alpha}_{i}^{\ell}=[W_{i}]_{+}\alpha^{\ell-1}\geq
0\mbox{~{}~{}and~{}~{}}\hat{\beta}_{i}^{\ell}=[W_{i}]_{+}\beta^{\ell-1}\geq 0$

Therefore, we can conclude that for any $\ell\geq 2$,
$0\leq\hat{\alpha}_{i}^{\ell}\leq\hat{\beta}_{i}^{\ell}$, and by definition

$D_{ii}^{\ell}=1,~{}~{}~{}\forall i\in[d]\implies D^{\ell}=I$

And therefore,

$W^{1:m}=W^{2:m}D^{1}W^{1}\mbox{~{}~{}where~{}~{}}W^{2:m}=W^{m}W^{m-1}W^{m-2}\dots
W^{2}$

By the assumption that $W_{ij}^{\ell}=r,\forall\ell\in[m]$,
$W^{\ell}=r\vec{1}\vec{1}^{T}$. So

$W^{m}W^{m-1}W^{m-2}\dots
W^{2}=\underbrace{r\vec{1}\vec{1}^{T}r\vec{1}\vec{1}^{T}\dots
r\vec{1}\vec{1}^{T}}_{\text{A product of $m-1$
terms}}=r^{m-1}d^{m-2}\vec{1}\vec{1}^{T}$

∎

##  Appendix G Proof of Proposition 3.5

See 3.5

###### Proof.

Let $f^{1:m}$ be a network as specified in the second statement of Proposition
3.4. Temporarily let $W^{k:m}$ denote the product of matrices
$W^{m}W^{m-1}\dots W^{k}$. For any $i$,

$\min_{x}T_{L}^{1:m}(x)_{i}=W^{2:m}D^{1}W^{1}\alpha^{0}$

and since for $k-1\geq 1$, $\alpha^{k-1}\succeq 0$, we get $D^{k}=I$ and

$\min_{x}T_{L}^{k:m}(x)_{i}=W^{k+1:m}D^{k}W^{k}\alpha^{k-1}=W^{k+1:m}W^{k}\alpha^{k-1}=W^{k:m}\alpha^{k-1}$

Therefore,

$\min_{x}T_{L}^{1:m}(x)_{i}-\min_{x}T_{L}^{k:m}(x)_{i}=W^{k:m}(W^{2:k-1}D^{1}W^{1}\alpha^{0}-\alpha^{k-1})$

Since for all $i$,

$\hat{\alpha}_{i}^{k-1}=W_{i}^{k-1}\beta^{k-2}+[W_{i}^{k-1}]_{+}(\alpha^{k-2}-\beta^{k-2})=W_{i}^{k-1}\alpha^{k-2}$

So for $k-2\geq 1$,

$\alpha^{k-1}=[W^{k-1}\alpha^{k-2}]_{+}=W^{k-1}\alpha^{k-2}$

Applying this recursively, we get

$\alpha^{k-1}=W^{k-1}\dots W^{2}\alpha^{1}=W^{2:k-1}\alpha^{1}$

Plug this into the inequality earlier, we get

$\displaystyle\min_{x}T_{L}^{1:m}(x)_{i}-\min_{x}T_{L}^{k:m}(x)_{i}=W^{k:m}(W^{2:k-1}D^{1}W^{1}\alpha^{0}-W^{2:k-1}\alpha^{1})$
$\displaystyle=W^{2:m}(D^{1}W^{1}\alpha^{0}-\alpha^{1})=W^{2:m}(D^{1}W^{1}\alpha^{0}-[\hat{\alpha}^{1}]_{+})$

We may conclude the proof by noting that we can apply the same argument as
that in Proposition 3.4. The existence of $(x_{0},\epsilon)$ can be shown by
drawing $x_{0}\sim\mathcal{N}(0,I)$ and since by Proposition 3.4, with
appropriate choice of $m$ as a function of $\epsilon,d,B$, the expected gap
$\min_{x}T_{L}^{1:m}(x)_{i}-\min_{x}T_{L}^{k:m}(x)_{i}$ is bounded by $B$.
This implies that there exists $x_{0}$ in the sample space so that the
corresponding $(\alpha^{0},\beta^{0})$ satisfies
$\min_{x\in(\alpha^{0},\beta^{0})}T_{L}^{1:m}(x)_{i}-\min_{x\in(\alpha^{k},\beta^{k})}T_{L}^{k:m}(x)_{i}<-B$.
∎

##  Appendix H Exact solution to hyper-rectangular constrained linear program

In our analysis, we frequently use the exact solution to the hyper-rectangular
constrained linear optimization problem (as formulated in Eq (3) and (4)).
Here, we show the derivation of our exact solution. We re-state the hyper-
rectangular constrained linear optimization objectives:

$\displaystyle\widehat{\alpha}^{\ell}_{i}:=\min_{\alpha^{\ell-1}\preceq
x\preceq\beta^{\ell-1}}e_{i}^{T}(W^{\ell}x+b^{\ell})$
$\displaystyle\widehat{\beta}^{\ell}_{i}:=\max_{\alpha^{\ell-1}\preceq
x\preceq\beta^{\ell-1}}e_{i}^{T}(W^{\ell}x+b^{\ell})$

We derive the exact expression of $\widehat{\alpha}^{\ell}_{i}$ here (the
derivation of $\hat{\beta}_{i}^{\ell}$ is similar). To solve the linear
program, we introduce two Lagrange multipliers $\mu,\lambda\succeq 0$, and
define Lagrangian of the original objective (readers may refer to [2] for more
background knowledge.)

$\displaystyle
L(x,\mu,\lambda)=W_{i}^{\ell}x+b_{i}^{\ell}+\mu^{T}(\alpha^{\ell-1}-x)+\lambda^{T}(x-\beta^{\ell-1})$

Via the Lagrangian and the Lagrange multipliers, we define the dual LP
function $g(\mu,\lambda)$ as

$\displaystyle
g(\mu,\lambda):=\min_{x}L(x,\mu,\lambda)=\min_{x}(W_{i}^{\ell}-\mu^{T}+\lambda^{T})x+b_{i}^{\ell}+\mu^{T}\alpha^{\ell-1}-\lambda^{T}\beta^{\ell-1}$

The dual LP objective is

$\max_{\mu,\lambda}g(\mu,\lambda)$

Since the term $(W_{i}^{\ell}-\mu^{T}+\lambda^{T})x$ is linear in $x$, its
minimum becomes unbounded if $W_{i}^{\ell}-\mu^{T}+\lambda^{T}\neq 0$. The
dual variables $\mu,\lambda$ are only feasible if
$W_{i}^{\ell}-\mu^{T}+\lambda^{T}=0$ (see [2, Chapter 5] for detailed
introduction of Lagrangian, Lagrange multipliers, and duality). So we can add
these constraints to the dual LP objective

$\lambda\succeq 0\mbox{~{}~{}and~{}~{}}W_{i}^{\ell}+\lambda^{T}\succeq 0$

Utilizing these constraints, we can simplify the dual LP objective as

$\displaystyle\max_{\mu,\lambda}b_{i}^{\ell}+\mu^{T}\alpha^{\ell-1}-\lambda^{T}\beta^{\ell-1}=\max_{\lambda}b_{i}^{\ell}+(W_{i}^{\ell}+\lambda^{T})\alpha^{\ell-1}-\lambda^{T}\beta^{\ell-1}$
$\displaystyle=\max_{\lambda}b_{i}^{\ell}+W_{i}^{\ell}\alpha^{\ell-1}+\lambda^{T}(\alpha^{\ell-1}-\beta^{\ell-1})$

Since $\alpha^{\ell-1}-\beta^{\ell-1}\preceq 0$, the constraints on $\lambda$
implies that

$\lambda_{j}=\begin{cases}-W_{i,j}^{\ell}\mbox{~{}~{}if~{}~{}}W_{i,j}^{\ell}<0\\\
0\mbox{~{}~{}o.w.}\end{cases}$

So

$\max_{\lambda}\lambda^{T}(\alpha^{\ell-1}-\beta^{\ell-1})=[-W_{i}^{\ell}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})$

Thus,

$\displaystyle\widehat{\alpha}^{\ell}_{i}=\max_{\lambda}g(\lambda)=b_{i}^{\ell}+W_{i}^{\ell}\alpha^{\ell-1}+[-W_{i}^{\ell}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})$
$\displaystyle=b_{i}^{\ell}+W_{i}^{\ell}\alpha^{\ell-1}-[W_{i}^{\ell}]_{-}(\alpha^{\ell-1}-\beta^{\ell-1})$
$\displaystyle=b_{i}^{\ell}+W_{i}^{\ell}\beta^{\ell-1}-[W_{i}^{\ell}]_{+}\beta^{\ell-1}+W_{i}^{\ell}\alpha^{\ell-1}-[W_{i}^{\ell}]_{-}\alpha^{\ell-1}$
$\displaystyle=b_{i}^{\ell}+W_{i}^{\ell}\beta^{\ell-1}+[W_{i}^{\ell}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})$

Similarly, it can be derived that

$\widehat{\beta}^{\ell}_{i}=b_{i}^{\ell}+W_{i}^{\ell}\beta^{\ell-1}+[-W_{i}^{\ell}]_{+}(\beta^{\ell-1}-\alpha^{\ell-1})$

In vector form, they can be written as

$\displaystyle\hat{\alpha}^{\ell}=W^{\ell}\beta^{\ell-1}+[W^{\ell}]_{+}(\alpha^{\ell-1}-\beta^{\ell-1})+b^{\ell}$
$\displaystyle\hat{\beta}^{\ell}=W^{\ell}\beta^{\ell-1}+[-W^{\ell}]_{+}(\beta^{\ell-1}-\alpha^{\ell-1})+b^{\ell}$

In what follows, we show that when $(W^{\ell},b^{\ell})$ are network weights
at layer $\ell$ and when the input hyper-rectangular constraint covers the
output space of layer $\ell-1$, then Eq (H) coincides with the pre-activation
IBP bound in [5].

######  Claim H.1 (bound equivalence).

Given the same input bounds $\alpha,\beta$ and fix a network layer with
general affine operation represented by $(W,b)$. Let $\underline{z}$ and
$\bar{z}$ denote the two vectors representing the pre-activation IBP lower and
upper bounds as defined in Eq (6) [5], and let
$\alpha^{\prime},\beta^{\prime}$ denote the two vectors obtained using updates
Eq (3) and Eq (4). Then

$\underline{z}=\alpha^{\prime}\text{~{}~{}and~{}~{}}\beta^{\prime}=\bar{z}$

###### Proof.

So we have $W=[W]_{+}+[W]_{-}$. We consider $\alpha^{\prime}-\underline{z}$:

$\displaystyle\alpha^{\prime}-\underline{z}=W\beta+[W]_{+}(\alpha-\beta)-(W\frac{\beta+\alpha}{2}-|W|\frac{\beta-\alpha}{2})$
$\displaystyle=W\frac{\beta-\alpha}{2}+[W]_{+}(\alpha-\beta)+([W]_{+}-[W]_{-})\frac{\beta-\alpha}{2}$
$\displaystyle=(W-[W]_{-})\frac{\beta-\alpha}{2}+[W]_{+}\frac{\alpha-\beta}{2}$
$\displaystyle=([W]_{+}+[W]_{-}-[W]_{-})\frac{\beta-\alpha}{2}+[W]_{+}\frac{\alpha-\beta}{2}=0$

And similar argument applies to show $\beta^{\prime}=\bar{z}$, which we skip
here. ∎

#### Comment:

In terms of computation, the update form [5, Eq (6)] is perhaps more
advantageous since it involves two matrix-vector multiplications, whereas ours
need three. Their absolute value operator can also be implemented by ReLU
operators ($|W|=[W]_{+}+[-W]_{+}$), which makes the overall forward update
supported by standard deep learning libraries and more friendly to
optimization.