# How robust accuracy suffers from certified training with convex relaxations

David S. Hippocampus
Department of Computer Science
Cranberry-Lemon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

Adversarial attacks pose significant threats to deploying state-of-the-art
classifiers in safety-critical applications. Two classes of methods have
emerged to address this issue: empirical defences and certified defences.
Although certified defences come with robustness guarantees, empirical
defences such as adversarial training enjoy much higher popularity among
practitioners. In this paper, we systematically compare the standard and
robust error of these two training paradigms across multiple computer vision
tasks. We show that in most tasks and for both $\ell_{\infty}$-ball and
$\ell_{2}$-ball threat models, certified defences based on convex relaxations
suffer from worse standard and robust error than adversarial training. We
further explore how this error gap depends on the threat model and the data
distribution. In particular, besides the perturbation budget, we identify as
important factors the direction of the adversarial perturbations and the
implicit margin of the data distribution. We support our arguments with
extensive ablations on both synthetic and image datasets.

##  1 Introduction

State-of-the-art classifiers are known to be vulnerable to adversarial
perturbations of the input. These perturbations, whether perceptible or
imperceptible, can manipulate the input in such a way as to drastically alter
the classifier’s predictions [biggio_evasion_2013, szegedy_intriguing_2014].
Hence, robustness to such _adversarial attacks_ has become a crucial design
goal when deploying machine learning models in safety-critical applications.

More precisely, for any given distribution $\mathcal{D}$ and loss function
$L$, we aim to find a classifier $f_{\theta}:\mathbb{R}^{d}\to\mathbb{R}^{k}$
parameterised by $\theta\in\mathbb{R}^{p}$ that minimises the _robust loss_

$\displaystyle\min_{\theta}\mathbf{R}_{\epsilon}(\theta)\;\;\text{where}\;\;\mathbf{R}_{\epsilon}(\theta):=\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\max_{\delta\in\mathcal{B}_{\epsilon}}L(f_{\theta}(x+\delta),y)\right],$
(1)

the threat model
$\mathcal{B}_{\epsilon}:=\\{\delta:\left\lVert\delta\right\rVert_{p}\leq\epsilon\\}$
is a bounded $\ell_{p}$-ball centred at the origin, and
$\mathbf{R}_{\epsilon}(\theta)$ denotes the robust error when $L$ is the 0-1
loss. The main challenge in solving the optimisation problem presented in
Equation 1 is that, when $\theta$ parameterises a neural network, the inner
maximisation becomes a non-convex optimisation problem and computationally
intractable [katz_reluplex_2017, weng_towards_2018]. In order to overcome the
computational barrier, two methods of approximation have been widely discussed
in the literature so far: _empirical_ defences such as adversarial training
and _certified_ defences, including randomised smoothing and convex
relaxations.

Adversarial training (AT) [goodfellow_explaining_2015, madry_towards_2018] is
one of the most popular empirical defences to date: it minimises the empirical
robust loss in Equation 1 by approximately solving the inner maximisation with
iterative first-order optimisation methods. Although adversarial training is
favoured for its simplicity and computational efficiency, it lacks the
robustness guarantees that are essential in safety-critical applications. In
particular, even though empirical evaluation tools like AutoAttack
[croce_reliable_2020] can provide non-trivial lower bounds of the robust
error, it is worth noting that these lower bounds might substantially
underestimate the true robust error.

To address this limitation, certified defences train neural networks for which
it is possible to obtain non-trivial upper bounds of the robust error. In this
paper, we focus our attention on _certified training_ , i.e. the widely
studied class of certified defences based on convex relaxations. The key idea
underlying certified training methods is to solve a convex relaxation of the
optimisation problem in Equation 1, by replacing the non-convex ReLU
constraint sets with larger convex sets [wong_provable_2018,
raghunathan_certified_2018, dvijotham_dual_2018].

(a) $\ell_{\infty}$-ball

(b) $\ell_{2}$-ball

Figure 1: Standard and robust error of adversarial (dotted bars) and certified
training (solid bars) on the CIFAR-10 test set. Models were trained for
robustness against: (a) $\ell_{\infty}$-ball perturbations with radius
$\epsilon_{\infty}=1/255$, and (b) $\ell_{2}$-ball perturbations with radius
$\epsilon_{2}=36/255$. We report the best performing certified training method
among many convex relaxations (FAST-IBP [shi2021fast], IBP
[gowal_scalable_2019], CROWN-IBP [zhang_towards_2020, xu_automatic_2020] and
COAP [wong_scaling_2018, wong_provable_2018]). We refer the reader to Section
2 for further details on the models and robust evaluation.

While certified training offers robustness guarantees, adversarial training is
frequently the preferred choice among practitioners. Beyond computational
efficiency issues, this preference stems from the suboptimal standard and
robust error achieved with this class of certified defences [mao2023taps]. As
we discuss in Section 5, so far, the drawbacks of certified training have
received considerably less attention in the literature than other types of
defences, such as randomised smoothing [mohapatra_hidden_2021,
avidan_spectral_2022, blum_random_2020, kumar_curse_2020]. Further, the most
prominent works on certified training [wong_provable_2018, zhang_towards_2020,
xu_automatic_2020, gowal_scalable_2019, shi2021fast, muller2023certified] do
not include a direct comparison of their methods with adversarial training,
nor are there any existing explanations for the error gap between these two
paradigms of robust training.

In this paper, we fill this void in the literature and systematically compare
the robust and standard error of certified and adversarial training across
three widely adopted computer vision datasets. More specifically, our
contributions can be summarised as follows:

  * •

In Section 2, we show that, in most tasks and for both $\ell_{\infty}$-ball
and $\ell_{2}$-ball threat models, certified training suffers from worse
standard and robust error than adversarial training (e.g. see Figures 1(a) and
1(b)).

  * •

In Section 3, we explore how the error gap between certified and adversarial
training depends on the

    1. (i)

Threat model – via the perturbation budget and the shape of the perturbation
set.

    2. (ii)

Data distribution – via the implicit margin of the data, which denotes the
minimum distance in feature space between any two data points from different
classes.

  * •

In Section 4, we propose a possible explanation for the error gap between
certified and adversarial training. Specifically, through a series of ablation
studies and illustrations, we show that the above factors influence the number
of _unstable neurons_ , which in turn affects the error gap.

##  2 Systematic comparison between adversarial and certified training

In this section, we systematically compare the standard and robust error of
adversarial and certified training, for both $\ell_{2}$-ball and
$\ell_{\infty}$-ball threat models. We consider three widely adopted computer
vision datasets: Tiny ImageNet [le_tiny_2015], CIFAR-10
[krizhevsky_learningmultiple_2009] and MNIST [lecun_gradient-based_1998]. We
note that certified training with convex relaxations does not scale to larger
datasets such as ImageNet, hence we omit them from our comparison.

###  2.1 Experimental setup

#### Adversarial defences

Among certified training methods, we focus on the most popular ones and cover
a wide range of convex relaxations techniques. In particular, we consider:

  * •

Convex outer adversarial polytope (COAP) [wong_scaling_2018,
wong_provable_2018], which uses the DeepZ relaxation [singh_fast_2018] and
achieves state-of-the-art certified robustness under $\ell_{2}$-ball
perturbations.

  * •

Interval bound propagation (IBP) [gowal_scalable_2019], which uses the Box
relaxation [mirman_differentiable_2018].

  * •

Fast IBP [shi2021fast], which is a computationally more efficient version of
IBP and achieves state-of-the-art certified robustness under
$\ell_{\infty}$-ball perturbations.

  * •

CROWN-IBP [xu_automatic_2020], which combines the tight convex relaxation
CROWN [zhang_efficient_2018] with IBP.

We compare the certified training methods against the most popular empirical
defence to date, adversarial training (AT) [goodfellow_explaining_2015,
madry_towards_2018], which is the go-to approach for adversarial robustness
among practitioners.

#### Models and evaluation

For CIFAR-10, we train a residual network (ResNet) and for MNIST we train a
vanilla convolutional neural network (CNN). Both architectures were introduced
in wong_scaling_2018 as standard benchmarks for certified training. For Tiny
ImageNet, we train the WideResNet introduced in xu_automatic_2020. We refer
the reader to Section B.1 for complete experimental details.

We evaluate the performance of these models according to standard and robust
error. More precisely, standard error is defined as in Equation 1 by setting
$L$ to the 0-1 loss function and $\epsilon=0$. As an approximation for the
population quantity, we compute the empirical standard and robust error on the
test set. Further, since exact evaluation of the robust error is
computationally infeasible, we evaluate the models with AutoAttack (AA+)
[croce_reliable_2020], which is widely considered to be one of the most
reliable empirical evaluation tools to date.

Our threat models in this section correspond to $\ell_{2}$-ball and
$\ell_{\infty}$-ball perturbations. For the sake of clarity, we present our
experimental results with a single perturbation budget for each dataset and
threat model, as reported in Table 1 (caption). Nevertheless, we provide
additional experimental results with a wide range of perturbation budgets in
Appendix C. Note that we intentionally choose small perturbation budgets for
$\ell_{2}$-ball perturbations, as larger budgets result in trivial standard
and robust error for certified training.

###  2.2 Standard and robust error gap

We present the results of our comparison in Table 1. Generally, for both
$\ell_{2}$-ball and $\ell_{\infty}$-ball threat models, we observe that
certified training suffers from worse standard and robust error than
adversarial training. An interesting exception to this pattern is found with
the MNIST dataset and the $\ell_{\infty}$-ball threat model, where the best
convex relaxation achieves smaller robust error than adversarial training.

#### Discussion

For MNIST, in Table 1 (first row) we observe a gap in standard error of up to
$2\%$ between adversarial and certified training, under both $\ell_{2}$-ball
and $\ell_{\infty}$-ball perturbations. Similarly, for robust error under
$\ell_{2}$-ball perturbations, we observe a $6\%$ gap between the best convex
relaxation and AT. However, under $\ell_{\infty}$-ball perturbations the best
convex relaxation achieves lower robust error than AT.

For CIFAR-10, in Table 1 (second row) we observe a standard error gap of up to
$25\%$ between the best convex relaxation and AT, under both $\ell_{2}$-ball
and $\ell_{\infty}$-ball perturbations. Unlike MNIST, for robust error, we
observe a gap of up to $15\%$, under both threat models.

For Tiny ImageNet, in Table 1 (third row) we observe a significant standard
error gap of up to $35\%$ between the best convex relaxation and AT, under
both $\ell_{2}$-ball and $\ell_{\infty}$-ball perturbations. Similarly, we
observe a significant robust error gap for both threat models, of up to
$20\%$. Note that COAP does not scale to Tiny ImageNet, and hence we omit it
from our comparison.

We observe that even though COAP is not traditionally recognised as a state-
of-the-art certified training method under $\ell_{\infty}$-ball perturbations,
given its subpar performance for larger perturbation budgets, it surprisingly
surpasses all other convex relaxations for smaller perturbation budgets on the
CIFAR-10 test set. Additionally, it generally performs better under
$\ell_{2}$-ball perturbations for both MNIST and CIFAR, marking it as an
effective convex relaxation in these settings.

|  $\ell_{\infty}$-ball |  $\ell_{2}$-ball
---|---|---
MNIST |  |
CIFAR-10 |  |
Tiny ImageNet |  |
Table 1: Standard and robust error of adversarial (dotted bar) and certified
training (solid bar, tightest to loosest convex relaxation from left to right)
on the MNIST ($\epsilon_{\infty}=0.1,\epsilon_{2}=0.75)$, CIFAR-10
($\epsilon_{\infty}=2/255,\epsilon_{2}=36/255$) and Tiny ImageNet
($\epsilon_{\infty}=1/255,\epsilon_{2}=5/255$) test sets.

#### Tight convex relaxations are better for $\ell_{2}$-ball perturbations

We observe a significantly more pronounced standard and robust error gap for
$\ell_{2}$-ball perturbations compared to $\ell_{\infty}$-ball perturbations.
Surprisingly, we find that the paradox of certified training
[jovanovic_paradox_2021] — the notion that loose interval-based training often
yields better performance than tighter relaxations — does not hold for
$\ell_{2}$-ball perturbations and for $\ell_{\infty}$-ball perturbations when
the perturbation budget is small (e.g. CIFAR-10 with
$\epsilon_{\infty}=\frac{2}{255}$). Instead, we notice that tighter convex
relaxations actually enhance performance in this setting. Notably, COAP
[wong_provable_2018, wong_scaling_2018], which is the tightest among the
convex relaxations considered, stands out as the best-performing method
against $\ell_{2}$-ball perturbations on both MNIST and CIFAR-10 test sets.
Conversely, IBP and FAST-IBP, which are the loosest convex relaxation
considered, emerge as the least effective.

##  3 Which factors influence the (robust) error gap?

In this section, we explore how the standard and robust error gap between
certified and adversarial training depends on the threat model and the data
distribution. Besides the perturbation budget $\epsilon$, we find that the
shape of the perturbation set plays a crucial role: the more _aligned_ it is
with the shortest path towards the (robust Bayes optimal) decision boundary,
the larger the error gap. Furthermore, the natural distribution of the data
also affects the phenomenon via the _implicit margin_ $\gamma$: a small
minimum distance between two classes in feature space leads to a large error
gap. We discuss the intuition underlying these factors in Section 4.

###  3.1 Experimental setup

#### Datasets

We use one synthetic dataset and one image dataset to study the effect of the
aforementioned factors on the error gap. For our controlled synthetic setting,
we consider the concentric spheres distribution studied in
gilmer_adversarial_2018, nagarajan_uniform_2019. To sample from the concentric
spheres distribution with radii $0<R_{0}<R_{1}$, we first draw a binary label
$y\in\\{0,1\\}$ with equal probability, and then a covariate vector $x\in
R^{d}$ uniformly from the sphere of radius $R_{y}$. Note that the implicit
margin of the concentric spheres distribution is given by
$\gamma\vcentcolon=R_{1}-R_{0}$. For image datasets, we present our ablations
on CIFAR-10 but observe similar trends on MNIST and provide additional
experiments in Section D.2.

#### Models and robust evaluation

For all CIFAR-10 experiments, we train a vanilla convolutional neural network
(CNN) as specified in wong_scaling_2018. For all concentric spheres
experiments, we train a multilayer perceptron with $W=100$ neurons and one
hidden layer. For simplicity of exposition, we compare adversarial training
with COAP throughout this section. We choose COAP as a representative for
certified training since it outperforms the other convex relaxations under
$\ell_{2}$-ball perturbations. We refer the reader to LABEL:apx:exp_details
for complete experimental details.

For the ablations on the perturbation budget and the margin, we specifically
concentrate on $\ell_{2}$-ball perturbations, as the phenomena we aim to
investigate are more prominent in this context. Nevertheless, we observe
similar trends for $\ell_{\infty}$-ball perturbations, and we provide
additional experiments in Section D.1. As for the previous section, we
evaluate the empirical robust error for $\ell_{2}$-ball perturbations using
AutoAttack (AA+) [croce_reliable_2020].

###  3.2 Factor (i): Shape of the perturbation set

The first factor we investigate is the shape of the perturbation set. In
particular, we study the alignment of the perturbation set with the shortest
path to the (robust Bayes optimal) decision boundary, which we call the
_signal direction_.

More formally, we define the signal direction $s(x,y)$ for a data point
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ and the robust Bayes optimal classifier
$f^{*}:\mathcal{X}\to\mathcal{Y}$, as the direction along the shortest path to
the decision boundary

$\displaystyle
s(x,y):=\underset{\delta:\|\delta\|_{2}=1}{\mathrm{argmin}}\left\\{\underset{\epsilon\geq
0}{\mathrm{min}}\;\epsilon\;:\;f^{*}(x+\epsilon\cdot\delta)\neq y\right\\}.$

Then, given a data distribution $\mathcal{D}$ and a threat model
$\mathcal{B}_{\epsilon}$, we define the alignment of the perturbation set as

$\displaystyle\text{Alignment}(\mathcal{B}_{\epsilon})$
$\displaystyle:=\mathbb{E}_{(x,y)\sim\mathcal{D}}\sup_{\delta\in\mathcal{B}_{\epsilon}}\left[\frac{s(x,y)^{\top}\delta}{\|s(x,y)\|_{2}\|\delta\|_{2}}\right].$

#### Perturbation sets with different degrees of alignment

Throughout this section, we intervene on the alignment of the perturbation set
by restricting the threat model to $k$ random orthogonal directions. More
formally, we randomly sample $k$ orthogonal unit vectors $\delta_{j}$ and
define the nested threat model as

$\displaystyle\mathcal{B}_{\epsilon,k}=\cup_{j=1}^{k}\left\\{\delta_{j}\beta\mid|\beta|\leq\epsilon\right\\},$
(2)

with $\mathcal{B}_{\epsilon,1}\subset\mathcal{B}_{\epsilon,2}\dots$. It is
important to note that as $k$ increases, there are more choices for the
direction of the adversarial perturbation and hence
$\text{Alignment}(\mathcal{B}_{\epsilon,k})$ increases with $k$ even though
the perturbation budget $\epsilon$ stays constant. Furthermore, unlike
$\ell_{p}$-ball perturbations, we can evaluate the empirical robust error
exactly for this threat model with a line-search along the $k$ random
orthogonal directions.

(a) Concentric spheres

(b) CIFAR-10

Figure 2: Ablations for the signal aligned threat model
$\mathcal{B}_{\epsilon,k}$ defined in Equation 2: (a) We report mean and
standard error over 5 runs for standard and robust error on the concentric
spheres dataset ($n=500,d=10,\gamma=20$, $\epsilon=5.0$). (b) We report mean
and standard error over 3 runs for standard and robust error on the CIFAR-10
dataset ($\epsilon=2.5$).

#### Ablations

We now present a series of ablations on the number of components $k$ to show
that stronger alignment indeed correlates with a wider standard and robust
error gap between COAP and AT. In particular, in Figure 2(a) we observe for
the concentric spheres distribution that stronger alignment yields a gap of up
to $25\%$ for standard error and $45\%$ for robust error. In Figure 2(b), we
observe for CIFAR-10 a standard error gap of up to $15\%$ and robust error gap
of up to $5\%$, for the largest number of components.

###  3.3 Factor (ii): Perturbation budget

The second factor we investigate is the perturbation budget $\epsilon$ of the
threat model. This quantity is directly related to the tightness of convex
relaxations. In particular, wong_provable_2018 show that the COAP relaxation
is very tight for small $\epsilon$, while it becomes loose for larger values
of $\epsilon$. Although it is well-known that a larger perturbation budget
results in worse certified training performance, the same also holds for
adversarial training and it is unknown whether the error gap between the two
increases.

(a) Concentric spheres

(b) CIFAR-10

Figure 3: Ablations for the $\ell_{2}$-ball threat model: (a) We report mean
and standard error over 5 runs for standard and robust error on the concentric
spheres dataset ($n=500,d=10,\gamma=20$). (b) Standard and robust error for
COAP and AT on the CIFAR-10 dataset.

#### Ablations

In Figures 3(a) and 3(b) we show that indeed, a larger perturbation budget
correlates with a wider gap for both standard and robust error. We observe
that for both concentric spheres and CIFAR-10 the error gap monotonically
increases as a function of the perturbation budget. Additionally, it is worth
noting that this increase is not a consequence of a limited sample size. COAP
training can indeed fail when the perturbation budget is significant, even
given a large sample size. This is evident in Figure 3(a) for the case of
concentric spheres, where the sample size is $n=500$ and the data
dimensionality is $d=10$.

###  3.4 Factor (iii): Margin of the data distribution

The third factor we investigate is the implicit margin of the data
distribution, i.e. the minimum distance in feature space between any two data
points of different classes.

More formally, we define the margin $\gamma$ for a dataset
$D=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ as

$\displaystyle\gamma:=\operatorname{min}_{i,j}\|x_{i}-x_{j}\|_{2}\quad\text{
s.t. }\quad i\neq j\;,\;y_{i}\neq y_{j}.$

In any robust classification task, this factor plays a pivotal role. When the
implicit margin is small, the task becomes inherently more challenging,
leading to potential failures in both adversarial and certified training.
However, given that certified training essentially relies on an over-
approximation of the perturbation set, it can be posited that it is
particularly susceptible to failure for small margins. Below, we present as
evidence an ablation study on the concentric spheres dataset.

#### Ablations

We empirically show that a smaller margin correlates with a wider standard and
robust error gap between AT and COAP. As intervening on the implicit margin
for image datasets such as CIFAR-10 is not feasible, we focus our ablations on
the concentric spheres dataset instead. In particular, in Figure 4(a), we
observe that the standard and robust error gap steadily increases as a
function of the inverse margin, reaching up to $30\%$ and $35\%$,
respectively.

(a) Concentric spheres

(b)

Figure 4: (a) Ablations for the $\ell_{2}$-ball threat model: We report mean
and standard error over 5 runs for standard and robust error on the concentric
spheres dataset ($n=500,d=10$, $\epsilon=4.0$). (b) Conceptual illustration of
the COAP convex relaxation for neurons in the unstable state.

##  4 The role of unstable neurons

In this section, we attempt to explain how the previously identified factors
influence the standard and robust error gap. Specifically, we discuss how they
affect the error gap via their impact on the number of _unstable neurons_ , a
quantity which plays a crucial role in the performance of certified training
with convex relaxations.

#### Definition of unstable neurons

For a neural network $f_{\theta}$ with $m$ total number of neurons, we use
$h^{\theta}_{j}(x)$ to denote the pre-activation value for an input $x$ and a
neuron $j$. Similarly, we define lower and upper bounds for this value under
perturbations $\left[\ell_{j}^{\theta}(x),u_{j}^{\theta}(x)\right]$, where
$\ell_{j}^{\theta}(x)\leq h_{j}^{\theta}(x+\delta)\leq u_{j}^{\theta}(x)$ for
all allowed perturbations $\delta\in\mathcal{B}_{\epsilon}$. Formally, we
define _inactive neurons_ for an input $x$, as all neurons $j$ with non-
positive pre-activation upper bounds $u_{j}^{\theta}(x)\leq 0$, i.e. they are
always inactive regardless of input perturbations. Similarly, _active neurons_
have non-negative pre-activation lower bounds $\ell_{j}^{\theta}(x)\geq 0$,
i.e. they are always active. In contrast, _unstable_ neurons have uncertain
activation states given different input perturbations, i.e.
$\ell_{j}^{\theta}(x)\leq 0\leq u_{j}^{\theta}(x)$. Given a neural network
$f_{\theta}$ and a dataset $D=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, we define the
number of unstable neurons as

$\text{UnstNeur}(f_{\theta})=\frac{1}{mn}\sum_{i=1}^{n}\sum_{j=1}^{m}\mathbb{I}\\{\ell_{j}^{\theta}(x_{i})\leq
0\leq u_{j}^{\theta}(x_{i})\\}.$ (3)

#### Unstable neurons and convex relaxations

A key property of certified training with convex relaxations is the tightness
of the over-approximation compared to the original perturbation set. Since
convex relaxations are much looser for unstable neurons compared to active or
inactive neurons (exemplarily illustrated for the COAP convex relaxation
[wong_scaling_2018] in Figure 4(b)), the number of unstable neurons is a good
indicator for quantifying the looseness of the over-approximation of the
perturbation set.

Further, existing works [lee2021towards, shi2021fast, muller2023certified]
suggest that the number of unstable neurons directly affects the performance
of certified training. Intuitively, the looser the over-approximation during
training, the greater the susceptibility to noise becomes. In particular,
noise can be introduced during training when the over-approximated
perturbation set extends over the (robust Bayes optimal) decision boundary,
essentially causing over-regularization. Hence, it is natural to expect that
an increased number of unstable neurons during training might cause a larger
error gap between certified and adversarial training. However, it is
impossible to verify this hypothesis by only intervening on the number of
unstable neurons in a neural network while keeping all other factors fixed.

For the above reasons, we study how the factors identified in Section 3 affect
the total number of unstable neurons during training, i.e.
$\sum_{t=1}^{T}\text{UnstNeur}(f_{\theta^{t}})$ where $f_{\theta^{t}}$ is the
neural network at epoch $t$ and $T$ is the total number of training epochs. In
particular, we first provide empirical evidence that the three factors
correlate with a higher number of unstable neurons. Then, we provide an
intuitive explanation with illustrations on a simple realisation of the
concentric spheres distribution.

(a)

(b) Conc. spheres

(c) CIFAR-10

(d) Conc. spheres

(e) CIFAR-10

(f) Conc. spheres

Figure 5: (a) Conceptual illustration of how the three factors act on the
number of unstable neurons. (b – f) Ablations for the signal aligned and the
$\ell_{2}$-ball threat models: (b,d,f) Concentric spheres dataset
($\gamma=20,n=500,d=10,\epsilon_{2}=5.0,\epsilon_{\text{signal}}=3.0$). (c,e)
CIFAR-10 dataset ($\epsilon_{\text{signal}}=2.5$).

#### How the factors affect unstable neurons

In Figures 5(b), 5(c), 5(d), 5(e) and 5(f), we can observe how for both the
CIFAR-10 and the concentric spheres datasets, the number of unstable neurons
increases with larger alignment, larger perturbation budget and smaller
margin.

We interpret these findings as follows: both smaller margin and larger
perturbation budget increase the model complexity of the decision boundary
with good robust training accuracy (similar to an argument made by
nakkiran19). In particular, they require a larger number of piecewise linear
regions, as also argued in shah2020pitfalls. This intuition is illustrated in
Figure 5(a): for a fixed perturbation set, both smaller margin (iv) and larger
perturbation budget (ii) require a larger number of piecewise linear functions
to approximate the decision boundary. The increased number of linear regions,
together with training points close to the boundary, then results in an
increase in the number of unstable neurons. Further, for less aligned
perturbation sets with the same margin and perturbation budget, i.e.
contrasting (iii) and (ii), the learning task is simplified, and fewer
piecewise regions are required. As a result, fewer neurons become unstable.

##  5 Related work

#### Limitations of certified training with convex relaxations

Certified training with convex relaxations hinges on over-approximating the
potential output range of each neuron for the perturbed versions of any input
point. While this over-approximation allows for tractable computation of an
upper bound on the robust error, it also introduces an inherent looseness that
impacts both robust training and evaluation. For example, salman_convex_2019
investigate the tightness of convex relaxations for verification purposes,
i.e. for certifying the robustness of already trained models, and show that
even the best existing convex relaxation provides only very loose upper bounds
on the robust error.

The effect of the tightness of convex relaxations on certified training has
recently been studied in the context of the so-called paradox of certified
training [jovanovic_paradox_2021], i.e. when training with tighter relaxations
leads to worse certified robustness. lee2021towards show empirically that
tighter convex relaxations affect the smoothness of the loss function, which
in turn impacts the performance of certified training. Instead of comparing
convex relaxations with different tightness, we discuss how tightness affects
the performance of certified training _in the context_ of varying other
factors related to the threat model and the data distribution.

#### Limitations of randomised smoothing

As an alternative to convex relaxations, randomised smoothing gives robustness
guarantees with a certain probability [cohen_certified_2019,
lecuyer_certified_2019, li_certified_2019]. Despite its popularity, randomised
smoothing also suffers from several limitations beyond an increased
computational cost. For example, several works have exposed an accuracy-
robustness tradeoff [blum_random_2020, kumar_curse_2020]. Further, randomised
smoothing can significantly hurt the disparity in class-wise accuracy
[mohapatra_hidden_2021] and is extremely vulnerable to low-frequency
corruptions of the test data [avidan_spectral_2022]. In general, compared to
certified training with convex relaxations, the drawbacks of randomised
smoothing are much better understood, and efforts are being made towards
developing new defences to bridge the gap with adversarial training
[nandy_towards_2022]. Therefore, we focus our attention in this paper on
certified training with convex relaxations.

#### Limitations of adversarial training

Not only certified training comes at the price of reduced test performance -
the same has been reported for adversarial training. For example, it has been
well-studied that adversarial training often results in a trade-off between
robust and standard accuracy; that is, the standard accuracy of adversarially
trained models often decreases even though the robust accuracy increases (see,
e.g. [tsipras_robustness_2019, zhang_theoretically_2019,
raghunathan_understanding_2020]). Attempts to provide an explanation for
consistent perturbations, i.e. perturbations that do not change the true
label, have so far focused on the small sample size regime. For example,
raghunathan_understanding_2020 prove that for small sample sizes, adversarial
training can increase standard error even in the absence of noise. Further,
most related to our work, clarysse_why_2022 recently prove that adversarial
training with perturbations aligned with the signal direction can even
increase the robust error. In contrast to this line of work, our experiments
focus on the large-sample regime and compare certified with adversarial
training.

##  6 Conclusion

In this paper, we show that certified training with convex relaxations suffers
from worse standard error and robust error than adversarial training. Further,
we are the first to provide a systematic comparison of these two robust
training paradigms across multiple datasets and threat models. In doing so, we
explore three important factors which are correlated with a wider standard and
robust error gap between certified and adversarial training. We believe that
shedding light on this error gap will not only provide us with a clearer
picture of the trade-offs observed in practice but also lead to better
approaches for certified robustness.

## Acknowledgements

PDB was supported by the Hasler Foundation grant number 21050 and AS
acknowledges partial support from the ETH AI Center postdoctoral fellowship.

##  Appendix A Theoretical results

In this section, we prove that, for a perfectly aligned threat model, a small
margin is sufficient to observe the robust error gap between COAP and AT. In
particular, our result holds for a linearly separable distribution with margin
$\gamma$ and a simple neural network. Below, we outline our theoretical
setting in more detail.

#### Data and threat model

To sample a data point from the linearly separable distribution with margin
$\gamma>0$, first we sample the label $y\in\\{+1,-1\\}$ with equal
probability. Then, sample $\tilde{x}\in\mathbb{R}^{d-1}$ from a standard
normal distribution $\tilde{x}\sim\mathcal{N}\left(0,\sigma^{2}I_{d-1}\right)$
and set the covariate vector $x=[\gamma\operatorname{sgn}(y);\tilde{x}]$,
where $[;]$ is the concatenation operator. Observe that for the linearly
separable distribution, the signal direction corresponds to the first index of
the input.

We choose our threat model to maximise the alignment with the signal
direction. Hence, we define the set of allowed perturbations

$\displaystyle\mathcal{B}_{\epsilon}(x)=\left\\{z_{1}=x+e_{1}\beta\mid|\beta|\leq\epsilon\right\\},$
(4)

where $e_{1}$ is the canonical basis vector of the first coordinate. Further,
we focus on consistent perturbations, i.e. $\epsilon<\gamma$, and we derive an
extension of the convex outer adversarial polytope (COAP) [wong_provable_2018]
for this threat model in Section E.3.

#### One step gradient descent

We study the early phase of neural network optimisation. Under structural
assumptions on the data, it has been proven that one gradient step with
sufficiently large learning rate can drastically decrease the training loss
[chatterji_when_2021] and extract task-relevant features [frei_random_2022,
daniely_learning_2020]. A similar setting was also studied recently in
ba_high-dimensional_2022 for the MSE loss in the high-dimensional asymptotic
limit. We focus on the classification setting with binary cross-entropy loss:

$\displaystyle
L(x,y)=y\log\left(\boldsymbol{\sigma}\left(x\right)\right)+\left(1-y\right)\log\left(1-\boldsymbol{\sigma}\left(x\right)\right),$
(5)

where $\boldsymbol{\sigma}\left(\cdot\right)$ is the sigmoid function.

#### One neuron neural network

Consider the hypothesis class of one-neuron shallow neural networks
$f_{\theta}:\mathbb{R}^{d}\xrightarrow{}\mathbb{R}$,

$\displaystyle
f_{\theta}(x)=a\operatorname{ReLU}\left(\theta^{\top}x\right)+b,$ (6)

where $x,\theta\in\mathbb{R}^{d}$ and $a,b\in\mathbb{R}$ and the only
trainable parameter is $\theta_{1}$. Note that as our distribution is linearly
separable, our hypothesis class includes the ground truth.

We are now ready to present our theoretical result for the linearly separable
distribution. In particular, Theorem 1 shows for a simple neural network that,
in high dimensions, certified training (COAP) yield higher robust error than
adversarial training (AT) when the margin of the data distribution is small.

######  Theorem 1.

Let $\mathbf{R}_{\epsilon}$ be the robust error of $f_{\theta}$, defined as

$\displaystyle\mathbf{R}_{\epsilon}(\theta):=\mathbb{P}_{(x,y)}\left[\exists
z\in\mathcal{B}_{\epsilon}(x):y\neq\operatorname{sgn}\left(f_{\theta}(z)\right)\right].$

Let $\bar{\theta}$ and $\tilde{\theta}$ be the network parameters after one
step of gradient descent with respect to AT and COAP objectives. If the
initialised network parameters $\theta$ satisfy

$\displaystyle\frac{\left\lVert\theta_{2:d}\right\rVert_{2}}{\left\lVert\theta_{1}\right\rVert_{2}}>\sqrt{\max\left(\frac{(7\epsilon-\gamma)(\gamma+\epsilon)^{4}}{4\sigma^{2}(\gamma^{2}-10\gamma\epsilon+13\epsilon^{2})},\frac{(\gamma+\epsilon)^{3}}{12\sigma^{2}\epsilon}\right)},$

and $\gamma<\frac{3}{2}\epsilon$ , COAP yields higher robust risk than AT,
that is

$\mathbf{R}_{\epsilon}(\tilde{\theta})>\mathbf{R}_{\epsilon}(\bar{\theta}).$

Theorem 1 relies on two main assumptions. The first is an assumption on the
data dimensionality and the initialisation of the network parameters $\theta$.
For instance, if we initialise the network parameters $\theta$ by sampling
from a sub-Gaussian distribution, then the euclidean norm
$\left\lVert\theta\right\rVert_{2}$ concentrates around $\sqrt{d}$ with high
probability. Hence, the assumption is satisfied when the data dimensionality
$d$ is sufficiently high. The second assumption requires that the implicit
margin of the data $\gamma$ is sufficiently small, or equivalently that the
perturbation budget $\epsilon$ is sufficiently large. This provides further
evidence that a small margin or a large perturbation budget are sufficient to
observe the robust error gap between COAP and AT.

###  A.1 Proof of Theorem 1

We assume, without loss of generality, that at initialisation $\theta_{1}>0$,
and since $a$ and $b$ are not trainable parameters, we must have $a>0$ and
$b<0$ to include the ground truth in our hypothesis class.

#### Adversarial training (AT)

First of all, note that when $L$ is the binary cross-entropy loss function, we
can rewrite the inner maximisation problem as

$\displaystyle\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{max}}L(f_{\theta}(x+\delta),y)=L\left(\operatorname{sgn}(y)\overbrace{\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{min}}\operatorname{sgn}(y)f_{\theta}(x+\delta)}^{:=J_{\epsilon}(x,y)},\;y\right).$
(7)

Below, we provide the gradient of the adversarial training objective in
Equation (7) w.r.t. the network parameters $\theta$.

######  Lemma 1.

Consider the neural network $f_{\theta}$ defined in Equation 6 and the threat
model $\mathcal{B}_{\epsilon}$ defined in Equation 4. Let $L$ be the binary
cross-entropy loss function, as defined in Equation 5. Then, we have

$\displaystyle\nabla_{\theta_{1}}\max_{x+\delta\in\mathcal{B}_{\epsilon}(x)}L(f_{\theta}(x+\delta),y)$
$\displaystyle=-\operatorname{sgn}(y)\boldsymbol{\sigma}\left(-J_{\epsilon}(x,y)\right)\begin{cases}a(x_{1}-\epsilon\operatorname{sgn}(\theta_{1}))\mathbf{1}\\{\ell>0\\}&\;\text{if}\;\;a\operatorname{sgn}(y)>0\\\
a(x_{1}+\epsilon\operatorname{sgn}(\theta_{1}))\mathbf{1}\\{u>0\\}&\;\text{if}\;\;a\operatorname{sgn}(y)<0\end{cases},$

where $\ell=\theta^{\top}x-\epsilon|\theta_{1}|$ and
$u=\theta^{\top}x+\epsilon|\theta_{1}|$ are respectively lower and upper
bounds on the $\operatorname{ReLU}$ inputs.

#### Certified training (COAP)

Next, we consider the dual approximation $\widetilde{J_{\epsilon}}(x,y)$ to
the optimisation problem in Equation 7, originally derived in
wong_provable_2018. We restate the dual objective
$\widetilde{J_{\epsilon}}(x,y)$ in Equation 13 and refer the reader to Section
E.3 for a thorough discussion of certified training dual approximation.

We are particularly interested in the data points for which
$J_{\epsilon}(x,y)\neq\widetilde{J_{\epsilon}}(x,y)$, i.e. when the certified
and adversarial training objectives differ. Below, we provide a necessary and
sufficient condition to have a mismatch between the two objectives.

######  Lemma 2.

Consider the neural network $f_{\theta}$ defined in Equation 6 and the threat
model $\mathcal{B}_{\epsilon}$ defined in Equation 4. Let $L$ be the binary
cross-entropy loss function, as defined in Equation 5. Further, we define
$\ell=\theta^{\top}x-\epsilon|\theta_{1}|$ and
$u=\theta^{\top}x+\epsilon|\theta_{1}|$ respectively as lower and upper bounds
on the $\operatorname{ReLU}$ inputs. Let
$\mathcal{I}^{\star}=\\{(x,y):0\in[\ell,u]\wedge a\operatorname{sgn}(y)>0\\}$.
Then, for data points in $\mathcal{I}^{\star}$, we have that AT and COAP
gradients differ

$\displaystyle\nabla_{\theta_{1}}J_{\epsilon}(x,y)\neq\nabla_{\theta_{1}}\widetilde{J_{\epsilon}}(x,y)\;\;\forall(x,y)\in\mathcal{I}^{\star},$

and the COAP gradient is given by

$\displaystyle\nabla_{\theta_{1}}L(\operatorname{sgn}(y)\widetilde{J_{\epsilon}}(x,y),y)$
$\displaystyle=-\frac{a\operatorname{sgn}(y)\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)}{2\epsilon}\left(\frac{\ell}{|\theta_{1}|}(x_{1}+\epsilon\operatorname{sgn}(\theta_{1}))+u\frac{x_{1}|\theta_{1}|-\theta^{\top}x\operatorname{sgn}(\theta_{1})}{\theta_{1}^{2}}\right).$

Further, for data points that are not in $\mathcal{I}^{\star}$ we have that AT
and COAP gradients are equivalent

$\displaystyle\nabla_{\theta_{1}}J_{\epsilon}(x,y)=\nabla_{\theta_{1}}\widetilde{J_{\epsilon}}(x,y)\;\;\forall(x,y)\notin\mathcal{I}^{\star}.$

#### COAP vs. AT after one step of gradient descent

Since we are only training the network parameter $\theta_{1}$, after one
gradient descent step, we have $\bar{\theta}_{2:d}=\tilde{\theta}_{2:d}$.
Further, we can relate the robust error of the classifier $f_{\theta}$ to the
parameter $\theta_{1}$ and show that the robust error monotonically decreases
in $\theta_{1}$, summarized in the following lemma.

######  Lemma 3.

Let $f_{\theta}$ be the neural network defined in Equation 6 and
$\mathcal{B}_{\epsilon}$ the threat model defined in Equation 4. We define the
robust error $\mathbf{R}_{\epsilon}$ of $f_{\theta}$ as

$\displaystyle\mathbf{R}_{\epsilon}(\theta):=\mathbb{P}_{(x,y)}\left[\exists
z\in\mathcal{B}_{\epsilon}(x):y\neq\operatorname{sgn}\left(f_{\theta}(z)\right)\right].$

Then, $\mathbf{R}_{\epsilon}(\theta)$ is monotonically decreasing in
$\theta_{1}$.

It follows from Lemma 3 that AT yields a smaller robust risk than COAP if the
following holds:

$\bar{\theta}_{1}>\tilde{\theta}_{1}\implies\mathbf{R}_{\epsilon}(\tilde{\theta})>\mathbf{R}_{\epsilon}(\bar{\theta}).$

Further, after one step of gradient descent, the left hand side
$\bar{\theta}>\tilde{\theta}$ is equivalent to

$\displaystyle\mathbb{E}_{(x,y)}\left[\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)J_{\epsilon}(x,y)\right),y\right)\right]<\mathbb{E}_{(x,y)}\left[\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)\widetilde{J_{\epsilon}}(x,y)\right),y\right)\right].$

Now recall from Lemmas 1 and 2 that the gradients of AT and COAP differ only
on the set $\mathcal{I}^{\star}$. In particular, we have that

$\displaystyle(x,y)\notin\mathcal{I}^{\star}\implies\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)J_{\epsilon}(x,y)\right),y\right)=\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)\widetilde{J_{\epsilon}}(x,y)\right),y\right)<0,$

and

$\displaystyle(x,y)\in\mathcal{I}^{\star}\implies
0=\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)J_{\epsilon}(x,y)\right),y\right)\neq\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)\widetilde{J_{\epsilon}}(x,y)\right),y\right).$

Hence, for our purpose, we need to show that

$\displaystyle\mathbb{E}_{(x,y)}\left[\nabla_{\theta_{1}}L\left(\boldsymbol{\sigma}\left(\operatorname{sgn}(y)\widetilde{J_{\epsilon}}(x,y)\right),y\right)\mid(x,y)\in\mathcal{I}^{\star}\right]>0.$
(8)

#### Lower bound on the gradient

Our strategy will be to lower-bound the expectation in Equation 8 with some
strictly positive quantity. We define

$\displaystyle Z=\sum_{i=2}^{d}\theta_{i}x_{i}$

and plug-in the gradient computed in Lemma 2 to obtain

$\displaystyle\mathbb{E}_{(x,y)}\biggl{[}\nabla_{\theta_{1}}L\biggl{(}\operatorname{sgn}(y)\boldsymbol{\sigma}\left(\widetilde{J_{\epsilon}}(x,y)\right),y\biggr{)}\bigg{|}(x,y)\in\mathcal{I}^{\star}\biggr{]}$
$\displaystyle=\mathbb{E}_{(x,y)}\biggl{[}\frac{a\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)}{2\epsilon}\biggl{(}-\frac{\ell}{\theta_{1}}(\gamma+\epsilon)+u\frac{\sum_{i=2}^{d}x_{i}\theta_{i}}{\theta_{1}^{2}}\biggr{)}\bigg{|}(x,y)\in\mathcal{I}^{\star}\biggr{]}$
$\displaystyle=\frac{a}{2\theta_{1}\epsilon}\mathbb{E}_{(x,y)}\biggl{[}\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)\biggl{(}-\ell(\gamma+\epsilon)+u\frac{Z}{\theta_{1}}\biggr{)}\bigg{|}(x,y)\in\mathcal{I}^{\star}\biggr{]}$
$\displaystyle=\frac{a}{2\theta_{1}\epsilon}\mathbb{E}_{(x,y)}\biggl{[}\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)u\frac{Z}{\theta_{1}}-\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)\ell(\gamma+\epsilon)\bigg{|}(x,y)\in\mathcal{I}^{\star}\biggr{]}.$

Now, we observe that $Z$ is always negative on the set $\mathcal{I}^{\star}$,
since we need to satisfy the constraint $\ell<0<u$ we have

$\displaystyle(x,y)\in\mathcal{I}^{\star}\implies-\theta_{1}(\gamma+\epsilon)<\sum_{i=2}^{d}\theta_{i}x_{i}<-\theta_{1}(\gamma-\epsilon)<0.$

Further,

$\displaystyle(x,y)\in\mathcal{I}^{\star}\implies\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)\geq\frac{1}{2}.$

Combining these two observations, we can lower-bound the expectation

$\displaystyle\mathbb{E}_{(x,y)}\left[\nabla_{\theta_{1}}L\left(\operatorname{sgn}(y)\boldsymbol{\sigma}\left(\widetilde{J_{\epsilon}}(x,y)\right),y\right)\mid(x,y)\in\mathcal{I}^{\star}\right]$
$\displaystyle=\frac{a}{2\theta_{1}\epsilon}\mathbb{E}_{(x,y)}\left[\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)u\frac{Z}{\theta_{1}}-\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}(x,y)\right)\ell(\gamma+\epsilon)\mid(x,y)\in\mathcal{I}^{\star}\right]$
$\displaystyle\geq\frac{a}{2\theta_{1}\epsilon}\mathbb{E}_{(x,y)}\left[u\frac{Z}{\theta_{1}}-\frac{\gamma+\epsilon}{2}\ell\mid(x,y)\in\mathcal{I}^{\star}\right].$

Now, we need to show that this lower-bound is strictly positive, i.e.

$\mathbb{E}_{(x,y)}\left[u\frac{Z}{\theta_{1}}-\frac{\gamma+\epsilon}{2}\ell\mid(x,y)\in\mathcal{I}^{\star}\right]>0.$

Note that we can further expand this expression as

$\displaystyle\mathbb{E}_{(x,y)}\left[u\frac{Z}{\theta_{1}}-\frac{\gamma+\epsilon}{2}\ell\mid(x,y)\in\mathcal{I}^{\star}\right]$
$\displaystyle=-(\gamma^{2}-\epsilon^{2})\theta_{1}^{2}+(\gamma+\epsilon)\theta_{1}\mathbb{E}\left[Z\mid(x,y)\in\mathcal{I}^{\star}\right]+2\mathbb{E}\left[Z^{2}\mid(x,y)\in\mathcal{I}^{\star}\right].$

Further, $Z\mid(x,y)\in\mathcal{I}^{\star}$ is distributed as a truncated
normal with

$\displaystyle\alpha=-\frac{\theta_{1}(\gamma+\epsilon)}{\sigma\left\lVert\theta_{2:d}\right\rVert_{2}}\;\;\text{and}\;\;\beta=-\frac{\theta_{1}(\gamma-\epsilon)}{\sigma\left\lVert\theta_{2:d}\right\rVert_{2}}.$

Hence, we can plug in the expectations of the truncated normal distribution to
obtain

$\displaystyle-(\gamma^{2}-\epsilon^{2})\theta_{1}^{2}+\theta_{1}(\gamma+\epsilon)\mathbb{E}\left[Z\mid(x,y)\in\mathcal{I}^{\star}\right]+2\mathbb{E}\left[Z^{2}\mid(x,y)\in\mathcal{I}^{\star}\right]$
$\displaystyle=-(\gamma^{2}-\epsilon^{2})\theta_{1}^{2}+2\sigma^{2}\left\lVert\theta_{2:d}\right\rVert_{2}^{2}+\sigma\left\lVert\theta_{2:d}\right\rVert_{2}\theta_{1}\frac{(\gamma-3\epsilon)\phi(\beta)-(\gamma+\epsilon)\phi(\alpha)}{\Phi(\beta)-\Phi(\alpha)}$
$\displaystyle\propto-(\gamma^{2}-\epsilon^{2})+2\sigma^{2}r^{2}+\sigma
r\frac{(\gamma-3\epsilon)\phi(\beta)-(\gamma+\epsilon)\phi(\alpha)}{\Phi(\beta)-\Phi(\alpha)}$
$\displaystyle=-f(r),$

where we define
$r=\frac{\left\lVert\theta_{2:d}\right\rVert_{2}}{|\theta_{1}|}$.

Now, under our assumptions, the following lemma holds.

######  Lemma 4.

Suppose $f:\mathbb{R}\to\mathbb{R}$ is defined as

$\displaystyle f(r)=\gamma^{2}-\epsilon^{2}-2\sigma^{2}r^{2}-\sigma
r\frac{(\gamma-3\epsilon)\phi(\beta)-(\gamma+\epsilon)\phi(\alpha)}{\Phi(\beta)-\Phi(\alpha)},$

where $\alpha:=-\frac{\gamma+\epsilon}{r\sigma}$ ,
$\beta:=-\frac{\gamma-\epsilon}{r\sigma}$, $\Phi$ and $\phi$ are respectively
the standard Gaussian CDF and PDF. Assume that

$\frac{5+2\sqrt{3}}{13}\gamma<\epsilon<\gamma.$

Then, we have

$\displaystyle f(r)<0,\;\;\forall
r>\sqrt{\max\left(\frac{(7\epsilon-\gamma)(\gamma+\epsilon)^{4}}{4\sigma^{2}(\gamma^{2}-10\gamma\epsilon+13\epsilon^{2})},\frac{(\gamma+\epsilon)^{3}}{12\sigma^{2}\epsilon}\right)}.$

Hence, it follows that
$\mathbf{R}_{\epsilon}(\tilde{\theta})>\mathbf{R}_{\epsilon}(\bar{\theta})$,
which concludes the proof.

##  Appendix B Experimental Details

###  B.1 Image experiments with $\ell_{2}$-ball and $\ell_{\infty}$-ball
threat models

Below we provide complete experimental details to reproduce: Tables 1, 4, 5,
3(b) and 5(e).

#### Model architectures

For MNIST, we train the CNN architecture with four convolutional layer and two
fully connected layers of 512 units introduced in wong_scaling_2018. We report
the architectural details in Table 2. For CIFAR-10, we train the residual
network (ResNet) with the same structure used in wong_scaling_2018; we use 1
residual block with 16, 16, 32, and 64 filters. For Tiny ImageNet, we train a
WideResNet as in xu_automatic_2020, using three wide basic blocks with a wide
factor of 10.

CNN
---
CONV $32\;3\times 3+1$
CONV $32\;4\times 4+2$
CONV $64\;3\times 3+1$
CONV $64\;4\times 4+2$
FC 512
FC 512
Table 2: MNIST model architecture. All layers are followed by
$\operatorname{ReLU}\left(\cdot\right)$ activations. The last fully connected
layer is omitted. "CONV $k$ $w\times h+s$" corresponds to a 2D convolutional
layer with k filters of size $w\times h$ using a stride of $s$ in both
dimensions. "FC $n$" is a fully connected layer with $n$ outputs.

#### Dataset preprocessing

For MNIST, we use full $28\times 28$ images without any augmentations and
normalisation. For CIFAR-10, we use random horizontal flips and random crops
as data augmentation, and normalise images according to per-channel
statistics. For Tiny ImageNet, we use random crops of 56 $\times$ 56 and
random flips during training. During testing, we use a central 56 $\times$ 56
crop. We also normalise images according to per-channel statistics.

#### Robust evaluation

We consider $\ell_{2}$-ball perturbations. We evaluate the robust error using
the most expensive version of AutoAttack (AA+) [croce_reliable_2020].
Specifically, we include the following attacks: untargeted APGD-CE (5
restarts), untargeted APGD-DLR (5 restarts), untargeted APGD-DLR (5 restarts),
Square Attack (5000 queries), targeted APGD-DLR (9 target classes) and
targeted FAB (9 target classes).

#### AT training details

For MNIST, we train 100 epochs using Adam optimiser [kingma_adam_2015] with a
learning rate of $0.001$, momentum of $0.9$ and a batch size of 128; we reduce
the learning rate by a factor 0.1 at epochs 40 and 80. For CIFAR-10 with
ResNet, we train 150 epochs using SGD with a learning rate of $0.05$ and a
batch size of 128; we reduce the learning rate by a factor of 0.1 at epochs 80
and 120. For Tiny ImageNet and CIFAR-10 with Wide-Resnet we train 200 epochs
using SGD with a learning rate of 0.1 and a batch size of 512; we reduce the
learning rate by a factor of 0.1 at epochs 100 and 150. For the inner
optimisation of all models and datasets, adversarial examples are generated
with 10 iterations of Auto-PGD [croce_reliable_2020].

#### COAP training details

We follow the settings proposed by the authors and report them here. For
MNIST, we use the Adam optimiser [kingma_adam_2015] with a learning rate of
0.001 and a batch size of 50. We schedule $\epsilon$ starting from 0.01 to the
desired value over the first 20 epochs, after which we decay the learning rate
by a factor of 0.5 every 10 epochs for a total of 60 epochs. For CIFAR-10, we
use the SGD optimiser with a learning rate of 0.05 and a batch size of 50. We
schedule $\epsilon$ starting from 0.001 to the desired value over the first 20
epochs, after which we decay the learning rate by a factor of 0.5 every 10
epochs for a total of 60 epochs. For all datasets and models, we use random
projection of 50 dimensions. For all experiments, we use the implementation
provided in wong_scaling_2018.

#### CROWN-IBP and IBP training details

We follow the settings proposed by the authors and report them here. For
MNIST, we train 200 epochs with a batch size of 256. We use Adam optimiser
[kingma_adam_2015] and set the learning rate to $5\times 10^{-4}$. We warm up
with 10 epochs of regular training and gradually ramp up
$\epsilon_{\text{train}}$ from 0 to $\epsilon$ in 50 epochs. We reduce the
learning rate by a factor of 0.1 at epochs 130 and 190. For CIFAR-10, we train
2000 epochs with a batch size of 256 and a learning rate of $5\times 10^{-4}$.
We warm up for 100 epochs and ramp-up $\epsilon$ for 800 epochs. The learning
rate is reduced by a factor of $0.1$ at epochs 1400 and 1700. For Tiny
ImageNet, we train 600 epochs with batch size 128. The first 100 epochs are
clean training. Then we gradually increase $\epsilon_{\text{train}}$ with a
schedule length of 400. For all datasets, a hyper-parameter $\beta$ to balance
LiRPA bounds and IBP bounds for the output layer is gradually decreased from 1
to 0 (1 for only using LiRPA bounds and 0 for only using IBP bounds), with the
same schedule of $\epsilon$. For all experiments, we use the implementation
provided in the auto LiRPA library [xu_automatic_2020].

#### FAST-IBP training details

We follow the settings proposed by the authors and report them here. Further,
we modify the architecture to add batch normalisation at each layer, as
suggested by the authors. Models are trained with Adam optimiser
[kingma_adam_2015] with an initial learning rate of $5\times 10^{-4}$, and
there are two milestones where the learning rate decays by 0.2. We determine
the milestones for learning rate decay according to the training schedule and
the total number of epochs, as shown in Table 3. The gradient clipping
threshold is set to 10.0. We train the models using a batch size of 256 on
MNIST and 128 on CIFAR-10 and TinyImageNet. The tolerance value $\tau$ in our
warmup regularization is fixed to 0.5.

During the warmup stage, after training with $\epsilon=0$ for a number of
epochs, the perturbation radius $\epsilon$ is gradually increased from 0 until
the target perturbation radius $\epsilon_{\text{target }}$, during the
$0<\epsilon<\epsilon_{\text{target }}$ phase. Specifically, during the first
$25\%$ epochs of the $\epsilon$ increasing stage, $\epsilon$ is increased
exponentially, and after that $\epsilon$ is increased linearly. In this way,
$\epsilon$ remains relatively small and increases relatively slowly during the
beginning to stabilize training. We use the SmooothedScheduler in the
autoLiRPA library as the scheduler for $\epsilon$, similarly adopted by
xu_automatic_2020.

Dataset | Total epochs | Decay-1 | Decay-2
---|---|---|---
MNIST | 70 | 50 | 60
CIFAR-10 | 160 | 120 | 140
TinyImageNet | 80 | 60 | 70
Table 3: Milestones for learning rate decay when the different total number of
epochs are used. "Decay-1" and "Decay-2" denote the two milestones,
respectively, when the learning rate decays by a factor of 0.2.

###  B.2 Image experiments with signal aligned threat model

Below we provide complete experimental details to reproduce: Figures 2(b),
5(c) and 8(a). First, we present our extension of COAP to the threat model
introduced in Equation 2. Rather than deriving the dual problem as in
wong_provable_2018, we consider the conjugate function view introduced in
wong_scaling_2018. In particular, we only have to modify the dual of the input
layer to the network. Below we derive the conjugate bound for the signal-
aligned threat model:

$\displaystyle\sup_{\delta\in\mathcal{B}_{\epsilon,k}}\nu_{1}^{\top}(x+\delta)$
$\displaystyle=\sup_{k,\beta}\nu_{1}^{\top}(x+s_{k}\beta)$
$\displaystyle=\nu_{1}^{\top}x+\epsilon\max_{k}|\nu_{1}^{\top}s_{k}|$

For all experiments, we use the convolutional neural network architecture
described in Table 2. Note that it is not possible to scale to ResNet with the
threat model in Equation 2, as the random projections trick derived in
wong_scaling_2018 is tailored to $\ell_{\infty}$-ball and $\ell_{2}$-ball
threat models.

#### AT training details

For both MNIST and CIFAR-10, we train 20 epochs using Adam optimiser
[kingma_adam_2015] with a learning rate of $0.001$, momentum of $0.9$ and a
batch size of 64; we reduce the learning rate by a factor 0.1 at epochs 10.
For the inner optimisation of all models and datasets, we solve the exact
problem as it is computationally efficient to line-search the maximal
perturbation.

#### COAP training details

For both MNIST and CIFAR-10, we use the Adam optimiser [kingma_adam_2015] with
a learning rate of 0.001 and a batch size of 64. We schedule $\epsilon$
starting from 0.01 to the desired value over the first 3 epochs, after which
we decay the learning rate by a factor of 0.5 every 10 epochs. For all
datasets and models, we do not use random projections. For all experiments, we
use the implementation provided in wong_scaling_2018.

###  B.3 Synthetic experiments with signal-aligned, $\ell_{2}$-ball and
$\ell_{\infty}$-ball threat models

Below we provide complete experimental details to reproduce Figures 2(a),
3(a), 4(a), 5(f), 5(d) and 5(b).

#### Data generation

For the spheres dataset, we generate a random $x\in\mathbb{R}^{d}$ where
$\left\lVert x\right\rVert_{2}$ is either $R_{0}$ or $R_{1}$ , with equal
probability assigned to each norm. We associate with each $x$ a label $y$ such
that $y=-1$ if $\left\lVert x\right\rVert_{2}=R_{0}$ and $y=1$ if $\left\lVert
x\right\rVert_{2}=R_{1}$. We can sample uniformly from this distribution by
sampling $z\sim\mathcal{N}\left(0,I_{d}\right)$ and then setting
$x=\frac{z}{\left\lVert z\right\rVert_{2}}R_{0}$ or $x=\frac{z}{\left\lVert
z\right\rVert_{2}}R_{1}$. For all experiments with the concentric spheres
distribution, we set $d=10,n=500,n_{\text{test}}=10^{4}$.

#### Model and hyper-parameters

For all the experiments, we use an MLP architecture with $W=100$ neurons and
one hidden layer and $\operatorname{ReLU}\left(\cdot\right)$ activation
functions. We use PyTorch SGD optimiser with a momentum of $0.95$ and train
the network for 150 epochs. We sweep over the learning rate
$\eta\in\\{0.1,0.01,0.001\\}$, and for each perturbation budget, we choose the
one that minimises robust error on the test set.

#### Robust evaluation

We evaluate robust error at test-time using Auto-PGD [croce_reliable_2020]
with 100 iterations and 5 random restarts. We use both the cross-entropy and
the difference of logit loss to prevent gradient masking. We use the
implementation provided in AutoAttack [croce_reliable_2020] with minor
adjustments to allow for non-image inputs.

#### Training paradigms

For standard training (ST), we train the network to minimise the cross-entropy
loss. For adversarial training (AT) [madry_towards_2018,
goodfellow_explaining_2015], we train the network to minimise the robust
cross-entropy loss. At each epoch, we search for adversarial examples using
Auto-PGD [croce_reliable_2020] with a budget of 10 steps and 1 random restart.
Then, we update the weights using a gradient with respect to the adversarial
examples. For convex outer adversarial polytope (COAP) [wong_provable_2018,
wong_scaling_2018], we train the network to minimise the upper bound on the
robust error. Our implementation is based on the code released by the authors.

##  Appendix C Detailed experimental results comparing certified and
adversarial training

This section provides a more complete evaluation of certified and adversarial
training, including a wide range of perturbation budgets.

#### MNIST

Similar to Section 2, we observe that for the $\ell_{\infty}$-ball threat
model, FAST-IBP achieves the best robust error across all perturbation
budgets, while AT delivers the best standard error. On the other hand, for the
$\ell_{2}$-ball threat model, AT achieves both the best robust and standard
error across all perturbation budgets.

width=0.7  Dataset Perturbation budget Method Robust error Standard error AT
$0.021$ $\mathbf{0.008}$ COAP $0.026$ $0.010$ MNIST $\epsilon_{\infty}=0.1$
CROWN-IBP $0.024$ $0.010$ IBP $0.026$ $0.010$ FAST-IBP $\mathbf{0.017}$
$0.009$ AT $0.045$ $\mathbf{0.008}$ COAP $0.066$ $0.026$ MNIST
$\epsilon_{\infty}=0.2$ CROWN-IBP $0.050$ $0.014$ IBP $0.060$ $0.014$ FAST-IBP
$\mathbf{0.032}$ $0.010$ AT $0.095$ $\mathbf{0.008}$ COAP $0.224$ $0.110$
MNIST $\epsilon_{\infty}=0.3$ CROWN-IBP $0.075$ $0.017$ IBP $0.091$ $0.021$
FAST-IBP $\mathbf{0.058}$ $0.015$ AT $0.321$ $\mathbf{0.008}$ COAP $0.806$
$0.737$ MNIST $\epsilon_{\infty}=0.4$ CROWN-IBP $0.120$ $0.025$ IBP $0.147$
$0.033$ FAST-IBP $\mathbf{0.104}$ $0.024$ AT $\mathbf{0.020}$ $\mathbf{0.006}$
COAP $0.040$ $0.014$ MNIST $\epsilon_{2}=0.5$ CROWN-IBP $0.059$ $0.027$ IBP
$0.068$ $0.032$ FAST-IBP $0.044$ $0.022$ AT $\mathbf{0.035}$ $\mathbf{0.006}$
COAP $0.100$ $0.030$ MNIST $\epsilon_{2}=0.75$ CROWN-IBP $0.125$ $0.060$ IBP
$0.145$ $0.070$ FAST-IBP $0.124$ $0.053$ AT $\mathbf{0.048}$ $\mathbf{0.006}$
COAP $0.193$ $0.049$ MNIST $\epsilon_{2}=1.0$ CROWN-IBP $0.355$ $0.192$ IBP
$0.539$ $0.432$ FAST-IBP $0.361$ $0.175$ AT $\mathbf{0.092}$ $\mathbf{0.005}$
COAP $0.302$ $0.074$ MNIST $\epsilon_{2}=1.25$ CROWN-IBP $0.760$ $0.696$ IBP
$0.806$ $0.794$ FAST-IBP $0.724$ $0.652$

Table 4: Results on MNIST for both $\ell_{2}$-ball and $\ell_{\infty}$-ball
threat models.

#### CIFAR-10

We observe that for both $\ell_{\infty}$-ball and $\ell_{2}$-ball threat
models, AT consistently achieves the best standard and robust error, with the
only exception being $\epsilon=8/255$, where FAST-IBP slightly outperforms AT
in terms of robust error.

width=0.75

Dataset | Perturbation budget | Method | Robust error | Standard error
---|---|---|---|---
|  | AT | $\mathbf{0.296}$ | $\mathbf{0.150}$
|  | COAP | $0.372$ | $0.309$
CIFAR-10 | $\epsilon_{\infty}=1/255$ | CROWN-IBP | $0.425$ | $0.331$
|  | IBP | $0.459$ | $0.356$
|  | FAST-IBP | $0.384$ | $0.290$
|  | AT | $\mathbf{0.378}$ | $\mathbf{0.166}$
|  | COAP | $0.427$ | $0.336$
CIFAR-10 | $\epsilon_{\infty}=2/255$ | CROWN-IBP | $0.498$ | $0.363$
|  | IBP | $0.526$ | $0.415$
|  | FAST-IBP | $0.476$ | $0.357$
|  | AT | $\mathbf{0.506}$ | $\mathbf{0.193}$
|  | COAP | $0.609$ | $0.502$
CIFAR-10 | $\epsilon_{\infty}=4/255$ | CROWN-IBP | $0.640$ | $0.548$
|  | IBP | $0.614$ | $0.487$
|  | FAST-IBP | $0.585$ | $0.449$
|  | AT | $0.698$ | $\mathbf{0.239}$
|  | COAP | $0.775$ | $0.729$
CIFAR-10 | $\epsilon_{\infty}=8/255$ | CROWN-IBP | $0.673$ | $0.539$
|  | IBP | $0.708$ | $0.606$
|  | FAST-IBP | $\mathbf{0.675}$ | $0.546$
|  | AT | $\mathbf{0.217}$ | $\mathbf{0.151}$
|  | COAP | $0.233$ | $0.219$
CIFAR-10 | $\epsilon_{2}=9/255$ | CROWN-IBP | $0.521$ | $0.491$
|  | IBP | $0.457$ | $0.424$
|  | FAST-IBP | $0.661$ | $0.647$
|  | AT | $\mathbf{0.246}$ | $\mathbf{0.151}$
|  | COAP | $0.316$ | $0.287$
CIFAR-10 | $\epsilon_{2}=18/255$ | CROWN-IBP | $0.721$ | $0.690$
|  | IBP | $0.566$ | $0.515$
|  | FAST-IBP | $0.763$ | $0.753$
|  | AT | $\mathbf{0.298}$ | $\mathbf{0.152}$
|  | COAP | $0.447$ | $0.399$
CIFAR-10 | $\epsilon_{2}=36/255$ | CROWN-IBP | $0.780$ | $0.740$
|  | IBP | $0.680$ | $0.622$
|  | FAST-IBP | $0.849$ | $0.844$
|  | AT | $\mathbf{0.386}$ | $\mathbf{0.172}$
|  | COAP | $0.630$ | $0.574$
CIFAR-10 | $\epsilon_{2}=72/255$ | CROWN-IBP | $0.900$ | $0.900$
|  | IBP | $0.772$ | $0.740$
|  | FAST-IBP | $0.900$ | $0.900$

Table 5: Results on CIFAR-10 for both $\ell_{2}$-ball and $\ell_{\infty}$-ball
threat models

##  Appendix D Additional factor ablations

For the ablations on the perturbation budget and the margin, we focused on
$\ell_{2}$-ball perturbations in Sections 3.3, 3.4 and 4, as the phenomena we
aim to investigate are more prominent in this context. We present similar
results for the $\ell_{\infty}$-ball threat model. Additionally, while our
alignment ablations in Section 3.2 focused on CIFAR-10 for clarity, we will
now illustrate similar trends for MNIST.

###  D.1 $\ell_{\infty}$-ball threat model on concentric spheres

First, we observe in Figures 6(a) and 6(b) that for the concentric spheres
distribution, the standard and robust error gap increases with the
perturbation budget and the inverse margin.

(a)

(b)

Figure 6: Results for $\ell_{\infty}$-ball threat model on the concentric
spheres dataset. (a) Standard and robust error for COAP and AT as the
perturbation budget $\epsilon$ of the threat model increases
($\gamma=20,n=500,d=10$). (b) Standard and robust error for COAP and AT as the
inverse margin increases ($\epsilon\approx 1,n=500,d=10$).

Further, we verify that unstable neurons, i.e. neurons with uncertain
activation states given different input perturbations, are similarly affected
by the factors as for the $\ell_{2}$-ball threat model. In particular, Figures
7(a) and 7(b) shows that unstable neurons increase steadily with the
perturbation budget and the inverse margin.

(a)

(b)

Figure 7: Ablations on perturbation budget and margin for the
$\ell_{\infty}$-ball threat model. (a) Results on concentric spheres dataset
($\gamma=20,n=500,d=10$). (b) Results on concentric spheres dataset
($\epsilon\approx 1,n=500,d=10$).

###  D.2 $\ell_{2}$-ball and signal aligned threat models on MNIST

In addition to the ablation study conducted with CIFAR-10, presented in
Section 3.2, we conduct similar ablations using MNIST.

The results presented here align well with the trends identified on CIFAR-10,
reinforcing our findings. In particular, we observe in Figures 8(a) and 8(b)
that the standard and robust error gap increases with the perturbation budget
and the alignment.

(a)

(b)

Figure 8: Results for $\ell_{2}$-ball and signal aligned threat models on
MNIST. (a) Standard and robust error for COAP and AT ($\epsilon=20$) as the
number of components $k$ of the threat model increases. (b) Standard and
robust error for COAP and AT as the perturbation budget $\epsilon$ increases.

Further, we verify that unstable neurons are similarly affected by the factors
as for CIFAR-10. In particular, Figures 7(a) and 7(b) shows that unstable
neurons increase steadily with the alignment and the perturbation budget.

(a)

(b)

Figure 9: Ablations for alignment and perturbation budget on MNIST. (a)
Results for the signal aligned threat model ($\epsilon=20$). (b) Results for
the $\ell_{2}$-ball threat model.

##  Appendix E Proofs of auxiliary lemmas

###  E.1 Proof of Lemma 3

See 3

###### Proof.

Without loss of generality, we assume that $\theta_{1}>0$, and since $a$ and
$b$ are not trainable parameters, we must have $a>0$ and $b<0$ to solve the
classification problem. The robust error is then equal to

$\displaystyle\mathbf{R}_{\epsilon}(\theta)$
$\displaystyle:=\mathbb{P}_{(x,y)}\left[\exists
z\in\mathcal{B}_{\epsilon}(x):y\neq\operatorname{sgn}\left(f_{\theta}(z)\right)\right]$
$\displaystyle=\frac{1}{2}\left(\mathbb{P}_{x}\left[a\operatorname{ReLU}\left(\theta^{\top}x\right)+b<0\mid
y=1\right]+\mathbb{P}_{x}\left[a\operatorname{ReLU}\left(\theta^{\top}x\right)+b>0\mid
y=-1\right]\right).$

Further, we can remove the $\operatorname{ReLU}\left(\cdot\right)$ using the
fact that $\frac{b}{a}<0$:

$\displaystyle\mathbf{R}_{\epsilon}(\theta)$
$\displaystyle=\frac{1}{2}\left(\mathbb{P}_{x}\left[\\{x:\theta^{\top}x+\frac{b}{a}<0\lor\theta^{\top}x<0\\}\mid
y=1\right]+\mathbb{P}_{x}\left[\\{x:\theta^{\top}x+\frac{b}{a}>0\land\theta^{\top}x>0\\}\mid
y=-1\right]\right)$
$\displaystyle=\frac{1}{2}\left(\mathbb{P}_{x}\left[\theta^{\top}x+\frac{b}{a}<0\mid
y=1\right]+\mathbb{P}_{x}\left[\ \theta^{\top}x+\frac{b}{a}>0\mid
y=-1\right]\right)$
$\displaystyle=\frac{1}{2}\left(\mathbb{P}_{x}\left[\sum_{i=2}^{d}x_{i}\theta_{i}<-\theta_{1}(\gamma-\epsilon)-\frac{b}{a}\right]+\mathbb{P}_{x}\left[\sum_{i=2}^{d}x_{i}\theta_{i}>\theta_{1}(\gamma-\epsilon)-\frac{b}{a}\right]\right).$

Recall now that for the linearly separable distribution we have
$\sum_{i=2}^{d}x_{i}\theta_{i}\sim\mathcal{N}\left(0,\sigma^{2}\left\lVert\theta_{2:d}\right\rVert^{2}\right)$.
Therefore, we can replace the probabilities with the standard normal CDF
$\Phi$:

$\displaystyle\mathbf{R}_{\epsilon}(\theta)$
$\displaystyle=\frac{1}{2}\left(\Phi\left(-\frac{(\gamma-\epsilon)\theta_{1}}{\sigma\left\lVert\theta_{2:d}\right\rVert_{2}}-\frac{b}{a\sigma\left\lVert\theta_{2:d}\right\rVert_{2}}\right)+\Phi\left(-\frac{(\gamma-\epsilon)\theta_{1}}{\sigma\left\lVert\theta_{2:d}\right\rVert_{2}}+\frac{b}{a\sigma\left\lVert\theta_{2:d}\right\rVert_{2}}\right)\right).$

Hence $\mathbf{R}_{\epsilon}(\theta)$ is monotonically decreasing in
$\theta_{1}$ and the statement follows. ∎

###  E.2 Proof of Lemma 1

The basic idea behind adversarial training is to update the network parameters
according to the following rule:

$\displaystyle\theta\leftarrow\theta-\frac{\eta}{|D|}\sum_{(x,y)\in
D}\nabla_{\theta}\max_{x+\delta\in\mathcal{B}_{\epsilon}(x)}L(f_{\theta}(x+\delta),y).$

This is usually done by applying some first-order approximation to the
maximisation problem. However, for our simplified network, we can analytically
compute the gradient. First of all, note that when $L$ is the binary cross-
entropy loss function, we can rewrite the maximisation problem as

$\displaystyle\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{max}}L(f_{\theta}(x+\delta),y)=L\left(\operatorname{sgn}(y)\overbrace{\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{min}}\operatorname{sgn}(y)f_{\theta}(x+\delta)}^{:=J_{\epsilon}(x,y)},\;y\right).$
(9)

In particular, if $J_{\epsilon}$ is strictly positive, then no adversarial
example exists that fools the network.Below we provide the gradient of the
adversarial training objective w.r.t. the network parameters $\theta$.

###### Proof.

Given a data point $x$ with known label $y\in\\{-1,1\\}$, when $L$ is the
binary cross-entropy loss function we have

$\displaystyle\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{max}}L(f_{\theta}(x+\delta),y)=L\left(\operatorname{sgn}(y)\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{min}}\operatorname{sgn}(y)f_{\theta}(x+\delta),\;y\right).$

For our simplified network, we can analytically compute a closed-form solution
to the minimisation problem

$\displaystyle J_{\epsilon}$
$\displaystyle:=\underset{x+\delta\in\mathcal{B}_{\epsilon}(x)}{\operatorname{min}}\operatorname{sgn}(y)\left(b+a\operatorname{ReLU}\left(\theta^{\top}(x+\delta)\right)\right)$
$\displaystyle=\begin{cases}\operatorname{sgn}(y)\left(b+a\operatorname{max}(0,\ell)\right)&\;\text{if}\;\;a\operatorname{sgn}(y)>0\\\
\operatorname{sgn}(y)\left(b+a\operatorname{max}(0,u)\right)&\;\text{if}\;\;a\operatorname{sgn}(y)<0\\\
\end{cases}$
$\displaystyle=\begin{cases}\operatorname{sgn}(y)\left(b+a\operatorname{max}(0,\ell)\right)&\;\text{if}\;\;\
a\operatorname{sgn}(y)>0\\\
\operatorname{sgn}(y)\left(b+a\operatorname{max}(0,u)\right)&\;\text{if}\;\;\
a\operatorname{sgn}(y)<0,\end{cases}$

where $\ell=\theta^{\top}x-\epsilon|\theta_{1}|$ and
$u=\theta^{\top}x+\epsilon|\theta_{1}|$ are respectively lower and upper
bounds on the pre-activations. Thus, we can compute the gradients for
adversarial training w.r.t the signal parameter

$\displaystyle\frac{\partial}{\partial\theta_{1}}J_{\epsilon}=\begin{cases}\operatorname{sgn}(y)a(x_{1}-\epsilon\operatorname{sgn}(\theta_{1}))\mathbf{1}\\{\ell>0\\}&\;\text{if}\;\;a\operatorname{sgn}(y)>0\\\
\operatorname{sgn}(y)a(x_{1}+\epsilon\operatorname{sgn}(\theta_{1}))\mathbf{1}\\{u>0\\}&\;\text{if}\;\;a\operatorname{sgn}(y)<0,\end{cases}$

and applying the chain rule, we have

$\displaystyle\frac{\partial}{\partial\theta_{1}}L\left(\operatorname{sgn}(y)J_{\epsilon},y\right)$
$\displaystyle=\frac{\partial}{\partial
J_{\epsilon}}L\left(\operatorname{sgn}(y)J_{\epsilon},y\right)\cdot\frac{\partial}{\partial\theta_{1}}J_{\epsilon}$
$\displaystyle=\operatorname{sgn}(y)\left[\boldsymbol{\sigma}\left(\operatorname{sgn}(y)J_{\epsilon}\right)-\mathbf{1}\\{y=1\\}\right]\cdot\frac{\partial}{\partial\theta_{1}}J_{\epsilon}$
$\displaystyle=-\operatorname{sgn}(y)\boldsymbol{\sigma}\left(-J_{\epsilon}\right)\begin{cases}a(x_{1}-\epsilon\operatorname{sgn}(\theta_{1}))\mathbf{1}\\{\ell>0\\}&\;\text{if}\;\;a\operatorname{sgn}(y)>0\\\
a(x_{1}+\epsilon\operatorname{sgn}(\theta_{1}))\mathbf{1}\\{u>0\\}&\;\text{if}\;\;a\operatorname{sgn}(y)<0,\end{cases}$

where in the last equality, we use a known property of the sigmoid function,
$\boldsymbol{\sigma}\left(x\right)=1-\boldsymbol{\sigma}\left(-x\right)$. ∎

###  E.3 Certified training (COAP)

We now formulate the convex outer adversarial polytope (COAP)
[wong_provable_2018] for adversaries that concentrate all their budget along
the signal direction in the input.

#### Network architecture

For the sake of clarity, we consider a 2-layers feed-forward ReLU network.
However, our formulation can easily be extended to multiple layers. We define
$f_{\theta}(x):\mathbb{R}^{d}\to\mathbb{R}^{2}$ as

$x\overset{x+\delta}{\longrightarrow}z_{1}\overset{W_{1}z_{1}+b_{1}}{\longrightarrow}\hat{z}_{2}\overset{\operatorname{ReLU}\left(\cdot\right)}{\longrightarrow}z_{2}\overset{W_{2}z_{2}+b_{2}}{\longrightarrow}\hat{z}_{3},$
(10)

where $x\in\mathbb{R}^{d}$, $z_{1}\in\mathcal{B}_{\epsilon}(x)$, $W_{1}$ and
$W_{2}$ are linear operators, and $\theta=\\{W_{i},b_{i}\\}_{i=1,2}$ is the
set of network parameters.

We define the adversarial polytope $\mathcal{Z}_{\epsilon}(x)$ as the set of
all final-layer activations attainable by perturbing $x$ with some
$\tilde{x}\in\mathcal{B}_{\epsilon}(x)$:

$\displaystyle\mathcal{Z}_{\epsilon}(x)=\\{f_{\theta}(\tilde{x}):\tilde{x}\in\mathcal{B}_{\epsilon}(x)\\}.$

The key idea behind COAP [wong_provable_2018] is to construct a convex outer
bound to this adversarial polytope. Specifically, we relax the ReLU
activations $z_{2}=\operatorname{ReLU}\left(\hat{z}_{2}\right)$ with their
convex envelopes

$\displaystyle z_{2}\geq 0,\;z_{2}\geq\hat{z}_{2},\;(u-\ell)z_{2}\leq
u\hat{z}_{2}-u\ell,$

where $u$ and $\ell$ are respectively the pre-activations $\hat{z}_{2}$ upper
and lower bounds. We assume these bounds are known and provide a closed-form
solution to compute them in Lemma 5. Further, let
$\tilde{\mathcal{Z}}_{\epsilon}(x)$ be the outer bound to the adversarial
polytope obtained from relaxing the ReLU constraints. Then, given a data point
$x$ with known label $y$, we can formalise the problem of finding an
adversarial example with a linear program as

$\underset{\hat{z}_{3}}{\operatorname{min}}\;[\hat{z}_{3}]_{y}-[\hat{z}_{3}]_{\bar{y}}=c^{\top}\hat{z}_{3}\;\;\quad\text{s.t.}\;\;\hat{z}_{3}\in\tilde{\mathcal{Z}}_{\epsilon}(x),$
(11)

where $\bar{y}$ is the binary negation of $y$. Note that if we solve this
linear program and find that the objective is positive, then we know that no
input perturbation within the threat model can misclassify the example.
However, solving the linear program in Equation 11 for every example in the
dataset is intractable. Therefore, we solve the dual formulation stated in the
corollary below. Our derivation can be seen as an extension of the main
results in wong_provable_2018, erdemir_adversarial_2021.

######  Corollary 1.1.

The dual of the linear program (11) can be written as

$\displaystyle\begin{array}[]{ll}\underset{\alpha}{\max}&\widetilde{J_{\epsilon}}\left(x,g_{\theta}(c,\alpha)\right)\\\
\text{s.t.}&\;\alpha_{j}\in[0,1],\;\forall j,\end{array}$

where $\widetilde{J_{\epsilon}}(x,\nu_{1},\nu_{2},\nu_{3})$ is equal to

$\displaystyle-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\ell_{j}[\nu_{2}]_{j}^{+}-\hat{\nu}_{1}^{\top}x-\epsilon|[\hat{\nu}_{1}]_{1}|,$

and $g_{\theta}$ is a one-hidden layer neural network given by the equations

$\begin{array}[]{ll}&\nu_{3}=-c\\\ &\hat{\nu_{2}}=W_{2}^{\top}\nu_{3}\\\
&[\nu_{2}]_{j}=0,\;j\in\mathcal{I}^{-}\\\
&[\nu_{2}]_{j}=\left[\hat{\nu}_{2}\right]_{j},\;j\in\mathcal{I}^{+}\\\
&[\nu_{2}]_{j}=\frac{u_{j}}{u_{j}-\ell_{j}}[\hat{\nu}_{2}]_{j}^{+}-\alpha_{j}[\hat{\nu}_{2}]_{j}^{-},\;j\in\mathcal{I}\\\
&\hat{\nu_{1}}=W_{1}^{\top}\nu_{2},\end{array}$

where $\mathcal{I}^{-},\mathcal{I}^{+}$ and $\mathcal{I}$ denote the sets of
activations in the hidden layer where $\ell$ and $u$ are both negative, both
positive or span zero, respectively.

###### Proof.

Consider a data point $x$ and let $\tilde{x}=x+\delta$ be the adversarial
perturbed data point. First, we explicit all the constraints for the linear
program defined in (11):

$\displaystyle\underset{\hat{z}_{3}}{\min}\;[\hat{z}_{3}]_{y}-[\hat{z}_{3}]_{\bar{y}}=c^{\top}\hat{z}_{3}\;,\quad\text{
s.t. }$ $\displaystyle x+\delta\in\mathcal{B}_{\epsilon}(x)$ $\displaystyle
z_{1}=x+\delta$ $\displaystyle\hat{z}_{2}=W_{1}z_{1}+b_{1}$
$\displaystyle\hat{z}_{3}=W_{2}z_{2}+b_{2}$
$\displaystyle[z_{2}]_{j}=0,\;\forall j\in\mathcal{I}^{-}$
$\displaystyle[z_{2}]_{j}=[\hat{z}_{2}]_{j},\;\forall j\in\mathcal{I}^{+}$
$\displaystyle[z_{2}]_{j}\geq 0,\;\forall j\in\mathcal{I}$
$\displaystyle[z_{2}]_{j}\geq[\hat{z}_{2}]_{j},\;\forall j\in\mathcal{I}$
$\displaystyle\left(\left(u_{j}-\ell_{j}\right)[z_{2}]_{j}\right.\left.-u_{j}[\hat{z}_{2}]_{j}\right)\leq-
u_{j}\ell_{j},\;\forall j\in\mathcal{I},$

where $\mathcal{I}^{-},\mathcal{I}^{+}$ and $\mathcal{I}$ denote the sets of
activations in the hidden layer where $\ell$ and $u$ are both negative, both
positive or span zero, respectively. In order to compute the dual of this
problem, we associate the following Lagrangian variables with each of the
constraints:

$\displaystyle\hat{z}_{2}$ $\displaystyle=W_{1}z_{1}+b_{1}\Rightarrow\nu_{2}$
$\displaystyle\hat{z}_{3}$ $\displaystyle=W_{2}z_{2}+b_{2}\Rightarrow\nu_{3}$
$\displaystyle z_{1}$ $\displaystyle=x+\delta\Rightarrow\psi$
$\displaystyle-[z_{2}]_{j}$ $\displaystyle\leq 0\Rightarrow\mu_{j},\;\forall
j\in\mathcal{I}$ $\displaystyle[\hat{z}_{2}]_{j}-[z_{2}]_{j}$
$\displaystyle\leq 0\Rightarrow\tau_{j},\;\forall j\in\mathcal{I}$
$\displaystyle\left(\left(u_{j}-\ell_{j}\right)[z_{2}]_{j}-u_{j}[\hat{z}_{2}]_{j}\right)$
$\displaystyle\leq-u_{j}\ell_{j}\Rightarrow\lambda_{j},\;\forall
j\in\mathcal{I}.$

Note that we do not define explicit dual variables for $[z_{2}]_{j}=0$ and
$[z_{2}]_{j}=[\hat{z}_{2}]_{j}$ as we can easily eliminate them. We write the
Lagrangian as

$\displaystyle\mathcal{L}(z,\hat{z},\nu,\delta,\lambda,\tau,\mu,\psi)=$
$\displaystyle-\left(W_{1}^{\top}\nu_{2}+\psi\right)^{\top}z_{1}-\sum_{\begin{subarray}{c}j\in\mathcal{I}\end{subarray}}\left(\mu_{j}+\tau_{j}-\lambda_{j}\left(u_{j}-\ell_{j}\right)+\left[W_{2}^{\top}\nu_{3}\right]_{j}\right)[z_{2}]_{j}$
$\displaystyle+\sum_{\begin{subarray}{c}j\in\mathcal{I}\end{subarray}}\left(\tau_{j}-\lambda_{j}u_{j}+[\nu_{2}]_{j}\right)[\hat{z}_{2}]_{j}+\left(c+\nu_{3}\right)^{\top}\hat{z}_{3}-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}$
$\displaystyle+\sum_{\begin{subarray}{c}j\in\mathcal{I}\end{subarray}}\lambda_{j}u_{j}\ell_{j}+\psi^{\top}x+\psi^{\top}\delta+\sum_{j\in\mathcal{I}^{-}}[\hat{z}_{2}]_{j}[\nu_{2}]_{j}$
$\displaystyle+\sum_{j\in\mathcal{I}^{+}}[z_{2}]_{j}\left([\nu_{2}]_{j}-[W_{2}^{\top}\nu_{3}]_{j}\right)$
$\displaystyle\text{ s.t. }\tilde{x}\in\mathcal{B}_{\epsilon}(x),$

and we take the infimum w.r.t. $z,\hat{z},\delta$

$\displaystyle\inf_{z,\hat{z},\delta}\mathcal{L}(z,\hat{z},\nu,\delta,\lambda,\tau,\mu,\psi)=$
$\displaystyle-\inf_{z_{2}}\sum_{\begin{subarray}{c}j\in\mathcal{I}\end{subarray}}\left(\mu_{j}+\tau_{j}-\lambda_{j}\left(u_{j}-\ell_{j}\right)+\left[W_{2}^{\top}\nu_{3}\right]_{j}\right)[z_{2}]_{j}$
$\displaystyle+\inf_{\hat{z}_{2}}\sum_{\begin{subarray}{c}j\in\mathcal{I}\end{subarray}}\left(\tau_{j}-\lambda_{j}u_{j}+[\nu_{2}]_{j}\right)[\hat{z}_{2}]_{j}+\inf_{\hat{z}_{3}}\left(c+\nu_{3}\right)^{\top}z_{3}-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}$
$\displaystyle+\sum_{\begin{subarray}{c}j\in\mathcal{I}\end{subarray}}\lambda_{j}u_{j}\ell_{j}+\psi^{\top}x+\inf_{\tilde{x}\in\mathcal{B}_{\epsilon}(x)}\psi^{\top}\delta-\inf_{z_{1}}\left(W_{1}^{\top}\nu_{2}+\psi\right)^{\top}z_{1}$
$\displaystyle+\inf_{\hat{z}_{2}}\sum_{j\in\mathcal{I}^{-}}[\hat{z}_{2}]_{j}[\nu_{2}]_{j}+\inf_{z_{2}}\sum_{j\in\mathcal{I}^{+}}[z_{2}]_{j}\left([\nu_{2}]_{j}-[W_{2}^{\top}\nu_{3}]_{j}\right).$

Now, we can compute the infimum for the $\psi^{\top}\delta$ term:

$\inf_{\tilde{x}\in\mathcal{B}_{\epsilon}(x)}\psi^{\top}\delta=\inf_{\left\lVert\beta\right\rVert_{1}\leq\epsilon}\psi_{1}\cdot\beta=-\epsilon\cdot\left\lVert\psi_{1}\right\rVert_{1},$

and since for all the other terms, the infimum of a linear function is
$-\infty$, except in the special case when it is identically zero, the infimum
of $\mathcal{L}(\cdot)$ becomes

$\inf_{z,\hat{z},\delta}\mathcal{L}(.)=\begin{cases}-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\lambda_{j}u_{j}\ell_{j}+\psi^{\top}x-\epsilon\left\lVert\psi_{1}\right\rVert_{1}&\text{
if }\text{ conditions }\\\ -\infty&\text{ else }\end{cases},$

where the conditions to satisfy are

$\displaystyle\nu_{3}=-c$ $\displaystyle W_{1}^{\top}\nu_{2}=-\psi$
$\displaystyle\left[\nu_{2}\right]_{j}=0,j\in\mathcal{I}_{i}^{-}$
$\displaystyle\left[\nu_{2}\right]_{j}=\left[W_{2}^{\top}\nu_{3}\right]_{j},j\in\mathcal{I}_{i}^{+}$
$\displaystyle\left.\begin{array}[]{ll}\left(u_{j}-\ell_{j}\right)\lambda_{j}-\mu_{j}-\tau_{j}&=\left[W_{2}^{\top}\nu_{3}\right]_{j}\\\
{\left[\nu_{2}\right]_{j}}&=u_{j}\lambda_{j}-\tau_{j}\end{array}\right\\}j\in\mathcal{I}$
$\displaystyle\lambda,\tau,\mu\geq 0.$

Thus, we can rewrite the dual problem as

$\displaystyle\underset{\nu,\psi,\lambda,\tau,\mu}{\max}-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\lambda_{j}u_{j}\ell_{j}+\psi^{\top}x-\epsilon\left\lVert\psi_{1}\right\rVert_{1}$
$\displaystyle\text{ s.t. }\quad\nu_{3}=-c$ $\displaystyle
W_{1}^{\top}\nu_{2}=-\psi$
$\displaystyle\left[\nu_{2}\right]_{j}=0,j\in\mathcal{I}_{i}^{-}$
$\displaystyle\left[\nu_{2}\right]_{j}=\left[W_{2}^{\top}\nu_{3}\right]_{j},j\in\mathcal{I}_{i}^{+}$
$\displaystyle\left.\begin{array}[]{ll}\left(u_{j}-\ell_{j}\right)\lambda_{j}-\mu_{j}-\tau_{j}&=\left[W_{2}^{\top}\nu_{3}\right]_{j}\\\
{\left[\nu_{2}\right]_{j}}&=u_{j}\lambda_{j}-\tau_{j}\end{array}\right\\}j\in\mathcal{I}$
$\displaystyle\lambda,\tau,\mu\geq 0.$

Note that the dual variable $\lambda$ corresponds to the upper bounds in the
ReLU relaxation, while $\mu$ and $\tau$ correspond to the lower bounds. By the
complementarity property, we know that at the optimal solution, these
variables will be zero if the ReLU constraint is non-tight or non-zero if the
ReLU constraint is tight. Since the upper and lower bounds cannot be tight
simultaneously, either $\lambda$ or $\mu+\tau$ must be zero. This means that
at the optimal solution to the dual problem, we can decompose
$[W_{2}^{\top}\nu_{3}]_{j}$ into positive and negative parts since
$(u_{j}-\ell_{j})\lambda_{j}\geq 0$ and $\tau_{j}+\mu_{j}\geq 0$ :

$\displaystyle(u_{j}-\ell_{j})\lambda_{j}=[W_{2}^{\top}\nu_{3}]_{j}^{+}$
$\displaystyle\tau_{j}+\mu_{j}=[W_{2}^{\top}\nu_{3}]_{j}^{-}$

combining this with the constraint $[\nu_{2}]_{j}=u_{j}\lambda_{j}-\tau_{j}$
leads to

$[\nu_{2}]_{j}=\frac{u_{j}}{u_{j}-\ell_{j}}[W_{2}^{\top}\nu_{3}]_{j}^{+}-\alpha_{j}[W_{2}^{\top}\nu_{3}]_{j}^{-},$

for $j\in\mathcal{I}$ and $0\leq\alpha_{j}\leq 1$. Hence, we have

$\lambda_{j}=\frac{u_{j}}{u_{j}-\ell_{j}}[\hat{\nu}_{2}]_{j}^{+}.$

Now, we denote $\hat{\nu}_{1}=-\psi$ to make our notation consistent, and
putting all of this together, the dual objective becomes

$\displaystyle-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\lambda_{j}u_{j}\ell_{j}+\psi^{\top}x-\epsilon|\psi_{1}|=-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\frac{u_{j}\ell_{j}}{u_{j}-\ell_{j}}[\hat{\nu}_{2}]_{j}^{+}-\hat{\nu}_{1}^{\top}x-\epsilon|[\hat{\nu}_{1}]_{1}|$
$\displaystyle=-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\ell_{j}[\nu_{2}]_{j}^{+}-\hat{\nu}_{1}^{\top}x-\epsilon|[\hat{\nu}_{1}]_{1}|,$

and the final dual problem:

$\begin{array}[]{ll}\underset{\nu,\hat{\nu}}{\max}&-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\ell_{j}[\nu_{2}]_{j}^{+}-\hat{\nu}_{1}^{\top}x-\epsilon|[\hat{\nu}_{1}]_{1}|\\\
\text{ s.t. }&\nu_{3}=-c\\\ &\hat{\nu_{2}}=W_{2}^{\top}\nu_{3}\\\
&[\nu_{2}]_{j}=0,\;j\in\mathcal{I}^{-}\\\
&[\nu_{2}]_{j}=\left[\hat{\nu}_{2}\right]_{j},\;j\in\mathcal{I}^{+}\\\
&[\nu_{2}]_{j}=\frac{u_{j}}{u_{j}-\ell_{j}}[\hat{\nu}_{2}]_{j}^{+}-\alpha_{j}[\hat{\nu}_{2}]_{j}^{-},\;j\in\mathcal{I}\\\
&\hat{\nu_{1}}=W_{1}^{\top}\nu_{2}.\end{array}$

∎

Further, we address here the problem of obtaining the upper and lower bounds
$u$ and $\ell$ for the pre-activations $\hat{z}$. Specifically, the following
proposition gives a closed-form solution.

######  Lemma 5.

Consider the neural network $f_{\theta}$ defined in Equation 10. Let $w_{1}$
be the first column of $W_{1}$. Then, for a data point $x$ and perturbation
budget $\epsilon$, we have the following element-wise bounds on the pre-
activation vector $\hat{z}_{2}$:

$\ell\leq\hat{z}_{2}\leq u,$

where

$\ell=W_{1}x+b_{1}-\epsilon|w_{1}|\;\;\text{and}\;\;u=W_{1}x+b_{1}+\epsilon|w_{1}|.$

###### Proof.

Given a data point $x$ and perturbation budget $\epsilon$, let
$\tilde{x}=x+\delta$ be the perturbed input to the network. First, we find an
upper bound to the pre-activations values $\hat{z}_{2}$:

$\hat{z}_{2}=W_{1}(x+\delta)+b_{1}=W_{1}x+b_{1}+W_{1}\delta.$

In particular, we want to solve the following optimisation problem for each
component of the pre-activation vector:

$u_{i}=\underset{\tilde{x}\in\mathcal{B}_{\epsilon}(x)}{\max}[\hat{z}_{2}]_{i}=[W_{1}x]_{i}+[b_{1}]_{i}+\underset{\tilde{x}\in\mathcal{B}_{\epsilon}(x)}{\max}[W_{1}\delta]_{i},$

where $u$ will be the vector containing element-wise upper bounds. Note that
$\delta=\beta e_{1}$, thus the optimisation problem can be rewritten as

$\underset{\tilde{x}\in\mathcal{B}_{\epsilon}(x)}{\max}[W_{1}\delta]_{i}=\underset{|\beta|\leq\epsilon}{\max}\beta\cdot[w_{1}]_{i}=\epsilon\cdot|[w_{1}]_{i}|,$

where $w_{1}$ is the first column of $W_{1}$. The vector of the upper bounds
will then be:

$u=W_{1}x+b_{1}+\epsilon|w_{1}|.$

Along the same lines, we can derive the vector of lower bounds $\ell$:

$l=W_{1}x+b_{1}-\epsilon|w_{1}|.$

∎

###  E.4 Proof of Lemma 2

We now consider the dual approximation $\widetilde{J_{\epsilon}}$ to the
optimisation problem in Equation 7. In what follows, we abuse notation and
denote

$\displaystyle\widetilde{J_{\epsilon}}\left(x,y\right)=\widetilde{J_{\epsilon}}\left(x,g_{\theta}(\operatorname{sgn}(y),\alpha)\right),$
(12)

where the right hand side is defined in Corollary 1.1 where we set $\alpha$ to
the dual feasible solution, and for the sake of clarity, we omit the
dependence on the network parameters $\theta$.

We are particularly interested in the data points for which
$J_{\epsilon}(x,y)\neq\widetilde{J_{\epsilon}}(x,y)$, i.e. when the certified
and adversarial training objectives differ. Below, we provide a necessary and
sufficient condition to have a mismatch between the two objectives.

###### Proof.

For the sake of clarity, we report here the definition of COAP objective from
Corollary 1.1.

$\displaystyle\widetilde{J_{\epsilon}}(x,y)=-\sum_{i=1}^{2}\nu_{i+1}^{\top}b_{i}+\sum_{j\in\mathcal{I}}\ell_{j}[\nu_{2}]_{j}^{+}-\hat{\nu}_{1}^{\top}x-\epsilon|[\hat{\nu}_{1}]_{1}|.$
(13)

Further, recall that the dual variables $\nu$ are given by the following
equations:

$\displaystyle\begin{array}[]{ll}&\nu_{3}=-c\\\
&\hat{\nu_{2}}=W_{2}^{\top}\nu_{3}\\\
&[\nu_{2}]_{j}=0,\;j\in\mathcal{I}^{-}\\\
&[\nu_{2}]_{j}=\left[\hat{\nu}_{2}\right]_{j},\;j\in\mathcal{I}^{+}\\\
&[\nu_{2}]_{j}=\frac{u_{j}}{u_{j}-\ell_{j}}[\hat{\nu}_{2}]_{j}^{+}-\alpha_{j}[\hat{\nu}_{2}]_{j}^{-},\;j\in\mathcal{I}\\\
&\hat{\nu_{1}}=W_{1}^{\top}\nu_{2},\\\ \end{array}$

where $\mathcal{I}^{-},\mathcal{I}^{+}$ and $\mathcal{I}$ denote the sets of
activations in the hidden layer where $\ell$ and $u$ are both negative, both
positive and span zero, respectively.

First, we consider the case when the neuron is always dead, i.e., $\ell<u<0$.
The dual variables are:

$\displaystyle\nu_{3}=-\operatorname{sgn}(y)$
$\displaystyle\hat{\nu}_{2}=-a\operatorname{sgn}(y)$ $\displaystyle\nu_{2}=0$
$\displaystyle\hat{\nu}_{1}=0.$

Hence, AT and COAP objectives are equal in this case:

$\widetilde{J_{\epsilon}}=\operatorname{sgn}(y)b=J_{\epsilon},$

where the last equality follows from Section E.2.

Next, we consider the case when the neuron is always active, i.e., $\
0<\ell<u$. The dual variables are:

$\displaystyle\nu_{3}=-\operatorname{sgn}(y)$
$\displaystyle\hat{\nu}_{2}=-a\operatorname{sgn}(y)$
$\displaystyle\nu_{2}=-a\operatorname{sgn}(y)$
$\displaystyle\hat{\nu}_{1}=-a\operatorname{sgn}(y)\cdot\theta,$

and the dual objective becomes

$\displaystyle\widetilde{J_{\epsilon}}$
$\displaystyle=-\nu_{3}^{\top}b-\hat{\nu}_{1}^{\top}x-\epsilon|[\hat{\nu}_{1}]_{1}|$
$\displaystyle=\operatorname{sgn}(y)\left(b+a(\theta^{\top}x)\right)-\epsilon|a\operatorname{sgn}(y)\theta_{1}|$
$\displaystyle=\begin{cases}\operatorname{sgn}(y)\left(b+a\ell\right)&\;\text{if}\;\;a\operatorname{sgn}(y)>0\\\
\operatorname{sgn}(y)\left(b+au\right)&\;\text{if}\;\;a\operatorname{sgn}(y)<0\\\
\end{cases}$ $\displaystyle=J_{\epsilon},$

where the last equality follows from the fact that $0<\ell<u$.

Finally, we consider the case when the neuron is in the activation set
$\mathcal{I}$, i.e., $\ell<0<u$. The dual variables are:

$\displaystyle\nu_{3}=-\operatorname{sgn}(y)$
$\displaystyle\hat{\nu}_{2}=-a\operatorname{sgn}(y)$
$\displaystyle\nu_{2}=~-a\operatorname{sgn}(y)\frac{u}{2\epsilon|\theta_{1}}|$
$\displaystyle\hat{\nu}_{1}=-a\operatorname{sgn}(y)~\frac{u}{2\epsilon|\theta_{1}|}\cdot\theta.$

Here we have two cases, when $\hat{\nu}_{2}>0$ we can rewrite the dual
objective as

$\widetilde{J_{\epsilon}}=\operatorname{sgn}(y)\left(b+au\right)=J_{\epsilon},$

and the two objectives coincide.

When $\nu_{2}<0$, we can rewrite the dual objective as

$\widetilde{J_{\epsilon}}=\operatorname{sgn}(y)\left(b+\frac{au\ell}{2\epsilon|\theta_{1}|}\right)\neq
J_{\epsilon}.$

Hence, the only case when COAP gradient differs from AT gradient is when
$\nu_{2}<0$ and the neuron belongs to the activation set $\mathcal{I}$.

We compute the partial derivative w.r.t. the signal parameter $\theta_{1}$ in
this case, by the chain rule we have:

$\displaystyle\frac{\partial}{\partial\theta_{1}}L\left(\operatorname{sgn}(y)\cdot\widetilde{J_{\epsilon}},y\right)$
$\displaystyle=\frac{\partial}{\partial\widetilde{J_{\epsilon}}}L\left(\operatorname{sgn}(y)\cdot\widetilde{J_{\epsilon}},y\right)\cdot\frac{\partial}{\partial\theta_{1}}\widetilde{J_{\epsilon}}$
$\displaystyle=\operatorname{sgn}(y)\left[\boldsymbol{\sigma}\left(\operatorname{sgn}(y)\cdot\widetilde{J_{\epsilon}}\right)-\mathbf{1}\\{y=1\\}\right]\cdot\frac{\partial}{\partial\theta_{1}}\widetilde{J_{\epsilon}}$
$\displaystyle=-\frac{a\operatorname{sgn}(y)\boldsymbol{\sigma}\left(-\widetilde{J_{\epsilon}}\right)}{2\epsilon}\left(\frac{\ell}{|\theta_{1}|}(x_{1}+\epsilon\operatorname{sgn}(\theta_{1}))+u\frac{x_{1}|\theta_{1}|-\theta^{\top}x\operatorname{sgn}(\theta_{1})}{\theta_{1}^{2}}\right).$

∎

###  E.5 Lower bound on the difference of Gaussian CDFs

######  Lemma 6.

Let $\Phi$ and $\phi$ be respectively the CDF and PDF of the standard Gaussian
distribution. Then, if $x<y<0$ we have

$\phi(0)\left(y-x+\frac{x^{3}}{6}\right)\leq\Phi(y)-\Phi(x).$

###### Proof.

First, we want to prove that $\frac{2x}{\sqrt{\pi}}$ is a lower bound for the
error function $\operatorname{erf}(x)$ when $x\leq 0$. That is, we want to
show that $f(x)\geq 0$ where $f:(-\infty,0]\to\mathbb{R}$ is the function
defined by

$f(x)=\operatorname{erf}(x)-\frac{2x}{\sqrt{\pi}}.$

Since $f$ is continuous and $f(x)\to\infty$ as $x\to-\infty$, $f$ must attain
an absolute minimimum on the interval $(-\infty,0]$. Now, differentiating we
have

$f^{\prime}(x)=\frac{2}{\sqrt{\pi}}\exp(-x^{2})-\frac{2}{\sqrt{\pi}},$

hence $f$ attains an absolute minimum at $0$ and we have $f(x)\geq f(0)=0$.
Next, we show that $\frac{2}{\sqrt{\pi}}(x-x^{3}/3)$ is an upper bound for
$\operatorname{erf}(x)$ when $x\leq 0$. Let $g:(-\infty,0]\to\mathbb{R}$ the
function defined by

$g(x)=\frac{2}{\sqrt{\pi}}(x-x^{3}/3)-\operatorname{erf}(x).$

Similarly, since $g$ is continuous and $g(x)\to\infty$ as $x\to-\infty$, $g$
must attain an absolute minimimum on the interval $(-\infty,0]$. Now,
differentiating we have

$g^{\prime}(x)=\frac{2}{\sqrt{\pi}}(1-x^{2}-\exp(-x^{2})),$

hence $g$ attains an absolute minimum at $0$ and we have $g(x)\geq g(0)=0$.
Now, since $a<b<0$ we can use the $\operatorname{erf}$ bounds derived above:

$\displaystyle\Phi(b)-\Phi(a)$
$\displaystyle=\frac{1}{2}\left(\operatorname{erf}(b/\sqrt{2})-\operatorname{erf}(a/\sqrt{2})\right)$
$\displaystyle\geq\frac{1}{\sqrt{\pi}}\left(\frac{b}{\sqrt{2}}-\frac{a}{\sqrt{2}}+\frac{a^{3}}{6\sqrt{2}}\right)$
$\displaystyle=\phi(0)\left(b-a+\frac{a^{3}}{6}\right),$

which concludes the proof. ∎

###  E.6 Proof of Lemma 4

###### Proof.

We begin by providing a lower bound on the difference of gaussian cdfs.
Applying Lemma 6 with $x=\alpha$ and $y=\beta$ we have

$\Phi(\beta)-\Phi(\alpha)\geq\left(\frac{2\epsilon}{r\sigma}-\frac{(\gamma+\epsilon)^{3}}{6\sigma^{3}r^{3}}\right)\phi(0),\;\;\alpha<\beta<0.$

Next, we can upper-bound $f$:

$\displaystyle f(r)$
$\displaystyle\leq\gamma^{2}-\epsilon^{2}-2\sigma^{2}r^{2}-\sigma
r\frac{(\gamma-3\epsilon)\phi(\beta)-(\gamma+\epsilon)\phi(\alpha)}{\left(\frac{2\epsilon}{\sigma
r}-\frac{(\gamma+\epsilon)^{3}}{6\sigma^{3}r^{3}}\right)\phi(0)}$
$\displaystyle\leq\gamma^{2}-\epsilon^{2}-2\sigma^{2}r^{2}-\sigma^{2}r^{2}\frac{(\gamma-3\epsilon)\phi(0)-(\gamma+\epsilon)\phi(\alpha)}{\left(2\epsilon-\frac{(\gamma+\epsilon)^{3}}{6r^{2}\sigma^{2}}\right)\phi(0)}$
$\displaystyle=\gamma^{2}-\epsilon^{2}-2\sigma^{2}r^{2}-\sigma^{2}r^{2}\frac{(\gamma-3\epsilon)-(\gamma+\epsilon)\exp(-\alpha^{2}/2)}{2\epsilon-\frac{(\gamma+\epsilon)^{3}}{6\sigma^{2}r^{2}}}.$

Now, we use the following upper-bound for the exponential function

$\exp(x)\leq 1+x-x^{2}/2,\;\;\forall x\leq 0,$

and substituting it back into our upper bound for $f$ we get

$f(r)\leq\gamma^{2}-\epsilon^{2}-2\sigma^{2}r^{2}-\sigma^{2}r^{2}\frac{(\gamma-3\epsilon)-(\gamma+\epsilon)(1-\frac{(\gamma+\epsilon)^{2}}{2r^{2}\sigma^{2}}+\frac{(\gamma+\epsilon)^{4}}{8r^{4}\sigma^{4}})}{2\epsilon-\frac{(\gamma+\epsilon)^{3}}{6r^{2}\sigma^{2}}},$

which can be further simplified as

$\displaystyle f(r)$
$\displaystyle\leq\gamma^{2}-\epsilon^{2}-2\sigma^{2}r^{2}-\sigma^{2}r^{2}\frac{(\gamma-3\epsilon)-(\gamma+\epsilon)(1-\frac{(\gamma+\epsilon)^{2}}{2r^{2}\sigma^{2}}+\frac{(\gamma+\epsilon)^{4}}{8r^{4}\sigma^{4}})}{2\epsilon-\frac{(\gamma+\epsilon)^{3}}{6r^{2}\sigma^{2}}}$
$\displaystyle=\frac{(\gamma-7\epsilon)(\gamma+\epsilon)^{4}+4r^{2}\sigma^{2}(\gamma+\epsilon)(\gamma^{2}-10\gamma\epsilon+13\epsilon^{2})}{4(\gamma+\epsilon)^{3}-48r^{2}\sigma^{2}\epsilon}$
$\displaystyle=u(r).$

Hence, we have that for $\epsilon>\frac{5+2\sqrt{3}}{13}\gamma$ and
$r>\sqrt{\max\left(\frac{(7\epsilon-\gamma)(\gamma+\epsilon)^{4}}{4\sigma^{2}(\gamma^{2}-10\gamma\epsilon+13\epsilon^{2})},\frac{(\gamma+\epsilon)^{3}}{12\sigma^{2}\epsilon}\right)}$
the upper bound is negative, i.e. $u(r)<0$. ∎