Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations

## Abstract

Abstract Training neural networks with high certified accuracy against adversarial examples remains an open problem despite significant efforts. While certification methods can effectively leverage tight convex relaxations for bound computation, in training, these methods perform worse than looser relaxations.
Prior work hypothesized that this is caused by the discontinuity and perturbation sensitivity of the loss surface induced by these tighter relaxations. In this work, we show theoretically that Gaussian Loss Smoothing can alleviate both of these issues.
We confirm this empirically by proposing a certified training method combining PGPE, an algorithm computing gradients of a smoothed loss, with different convex relaxations. When using this training method, we observe that tighter bounds indeed lead to strictly better networks that can outperform state-of-the-art methods on the same network.
While scaling PGPE-based training remains challenging due to high computational cost, our results clearly demonstrate the promise of Gaussian Loss Smoothing for training certifiably robust neural networks.

## 1 Introduction

The increased deployment of deep learning systems in mission-critical applications has made their provable trustworthiness and robustness against adversarial examples (Biggio et al., ; Szegedy et al., ) an important topic. As state-of-the-art neural network certification has converged to increasingly similar approaches (Zhang et al., ; Ferrari et al., ), the focus in the field is now shifting to specialized training methods that yield networks with high certified robustness while minimizing the loss of standard accuracy (Müller et al., ; Palma et al., ).

#### Certified Training

State-of-the-art certified training methods aim to optimize the network’s worst-case loss over an input region defined by an adversarial specification. However, as computing the exact worst-case loss is NP-complete (Katz et al., ), they typically utilize convex relaxations to compute over-approximations (Gowal et al., ; Singh et al., , ). Surprisingly, training methods based on the least precise relaxations (IBP) empirically yield the best performance (Shi et al., ), while tighter relaxations perform progressively worse (left-hand side of [Figure 1](#S1.F1)). Jovanović et al. () investigated this surprising phenomenon which they call the “Paradox of Certified Training”, both theoretically and empirically and found that tighter relaxations induce harder optimization problems. Specifically, they identify the *continuity* and *sensitivity* of the loss surface induced by a relaxation as key factors for the success of certified training, beyond its *tightness*. Indeed, *all* state-of-the-art methods are based on the imprecise but continuous and insensitive IBP bounds (Müller et al., ; Mao et al., ; Palma et al., ). However, while these IBP-based methods improve robustness, they induce severe regularization, significantly limiting the effective capacity and thus standard accuracy (Mao et al., ). Overall, this raises the following fundamental question:

Figure: Figure 1: Illustration of how Gaussian loss smoothing overcomes the paradox of certified training. We compare the certified accuracy [%] obtained by training with different relaxations using either the standard gradient (GRAD) or a gradient estimate computed on the smoothed loss surface (PGPE) with the tightness of the method.

*Can the paradox of certified training and thus the robustness-accuracy trade-off be overcome?*

#### This Work: Overcoming the Paradox

We investigate this question and show that applying *Gaussian Loss Smoothing* to certified training induces both continuity and infinite differentiability by smoothing the worst-case loss approximation with a Gaussian kernel. Leveraging this insight we propose the first backpropagation-free certified training method, recovering Gaussian Loss Smoothing in expectation, based on PGPE (Sehnke et al., ). We demonstrate empirically that using this method, tighter relaxations indeed lead to strictly better networks, thereby both confirming the importance of continuity and sensitivity in the paradox of certified training and overcoming it (right-hand side of [Figure 1](#S1.F1)).
Combining PGPE with the precise DeepPoly relaxation (Singh et al., ), we obtain strictly better results than IBP with gradient-based optimization across all settings and even outperform state-of-the-art methods on the same networks.
While scaling PGPE-based training remains challenging due to its high computational cost, we believe that our results clearly demonstrate the promise of Gaussian Loss Smoothing for certified training, suggesting fruitful directions for future work.

#### Main Contributions

Our core contributions are:

- •
We theoretically investigate the effect of Gaussian Loss Smoothing on the continuity and sensitivity of the approximate worst-case loss in certified training.
- •
Based on these insights, we propose a novel PGPE-based certified training method that achieves the tightness of DeepPoly bounds while ensuring continuity via Gaussian Loss Smoothing.
- •
We conduct a large-scale empirical evaluation of different convex relaxations under PGPE optimization, requiring over 100.000 GPU hours, and demonstrating the promise of Loss Smoothing based approaches.

## 2 Training for Certified Robustness

Below, we first introduce our notation and the setting of adversarial robustness before providing a background on (training for) certified robustness.

#### Notation

We denote vectors with bold lower-case letters ${\bm{a}}\in\mathbb{R}^{n}$, matrices with bold upper-case letters ${\bm{A}}\in\mathbb{R}^{n\times d}$, and sets with upper-case calligraphic letters $\mathcal{A}\subset\mathbb{R}$. All inequalities ${\bm{a}}\geq{\bm{b}}$ between vectors hold elementwise.

### 2.1 Adversarial Robustness

We consider a neural network ${\bm{f}}_{\bm{\theta}}({\bm{x}})\colon\mathcal{X}\to\mathbb{R}^{n}$, parameterized by the weights $\bm{\theta}$, that assigns a score to each class $i\in\mathcal{Y}$ given an input ${\bm{x}}\in\mathcal{X}$. This induces the classifier $F\colon\mathcal{X}\to\mathcal{Y}$ as $F({\bm{x}})\coloneqq\operatorname*{arg\,max}_{i}{\bm{f}}_{\bm{\theta}}({\bm{x}})_{i}$. We call $F$ locally robust for an input ${\bm{x}}\in\mathcal{X}$ if it predicts the same class $y\in\mathcal{Y}$ for all inputs in an $\epsilon$-neighborhood $\mathcal{B}^{\epsilon}_{p}(x)\coloneqq\{{\bm{x}}^{\prime}\in\mathcal{X}\mid\|{\bm{x}}-{\bm{x}}^{\prime}\|_{p}\leq\epsilon\}$. To prove that a classifier is locally robust, we thus have to show that $F({\bm{x}}^{\prime})=F({\bm{x}})=y,\forall{\bm{x}}^{\prime}\in\mathcal{B}$.

Local robustness is equivalent to the score of the target class $y$ being greater than that of all other classes for all relevant inputs, i.e., $\min_{{\bm{x}}^{\prime}\in\mathcal{B},i\neq y}f({\bm{x}}^{\prime})_{y}-f({\bm{x}}^{\prime})_{i}>0$.
As solving this neural network verification problem exactly is generally NP-complete (Katz et al., ), state-of-the-art neural network verifiers relax it to an efficiently solvable convex optimization problem (Brix et al., ). To this end, the non-linear activation functions are replaced with convex relaxations in their input-output space, allowing linear bounds of the following form on their output $f({\bm{x}})$ to be computed:

$$ ${\bm{A}}_{l}{\bm{x}}+{\bm{b}}_{l}\leq{\bm{f}}_{\bm{\theta}}({\bm{x}})\leq{\bm{A}}_{u}{\bm{x}}+{\bm{b}}_{u},$ $$

for some input region $\mathcal{B}^{\epsilon}_{p}(x)$. These bounds can in-turn be bounded concretely by ${\bm{l}}_{y}=\min_{{\bm{x}}\in\mathcal{B}}{\bm{A}}_{l_{i}}{\bm{x}}+{\bm{b}}_{l_{i}}\in\mathbb{R}$ and ${\bm{u}}_{y}$ analogously. Hence, we have ${\bm{l}}_{y}\leq{\bm{f}}({\bm{x}})\leq{\bm{u}}_{y}$.

#### Training for Robustness

To obtain (certifiably) robust neural networks, specialized training methods are required.
For a data distribution $({\bm{x}},t)\sim\mathcal{D}$, standard training optimizes the network parametrization $\bm{\theta}$ to minimize the expected cross-entropy loss:

$$ $\displaystyle\theta_{\text{std}}$ $\displaystyle=\operatorname*{arg\,min}_{\theta}\mathbb{E}_{\mathcal{D}}[\mathcal{L}_{\text{CE}}({\bm{f}}_{\bm{\theta}}({\bm{x}}),t)],\quad\text{with}$ (1) $\displaystyle\mathcal{L}_{\text{CE}}({\bm{y}},t)$ $\displaystyle=\ln\big{(}1+\sum_{i\neq t}\exp(y_{i}-y_{t})\big{)}.$ (2) $$

To train for robustness, we, instead, aim to minimize the expected *worst-case loss* for a given robustness specification, leading to a min-max optimization problem:

$$ $\theta_{\text{rob}}=\operatorname*{arg\,min}_{\theta}\mathbb{E}_{\mathcal{D}}\left[\max_{{\bm{x}}^{\prime}\in\mathcal{B}^{\epsilon}({\bm{x}})}\mathcal{L}_{\text{CE}}({\bm{f}}_{\bm{\theta}}({\bm{x}}^{\prime}),t)\right].$ (3) $$

As computing the worst-case loss by solving the inner maximization problem is generally intractable, it is commonly under- or over-approximated, yielding adversarial and certified training, respectively.

#### Adversarial Training

optimizes a lower bound on the inner optimization objective in [Equation 3](#S2.E3). To this end, it first computes concrete examples ${\bm{x}}^{\prime}\in\mathcal{B}^{\epsilon}({\bm{x}})$ that approximately maximize the loss term $\mathcal{L}_{\text{CE}}$ and then optimizes the network parameters $\bm{\theta}$ for these examples.
While networks trained this way typically exhibit good empirical robustness, they remain hard to formally certify and are sometimes vulnerable to stronger attacks (Tramèr et al., ; Croce & Hein, ).

#### Certified Training

typically optimizes an upper bound on the inner maximization objective in [Equation 3](#S2.E3). To this end, the robust cross-entropy loss $\mathcal{L}_{\text{CE,rob}}(\mathcal{B}^{\epsilon}({\bm{x}}),t)=\mathcal{L}_{\text{CE}}(\overline{{\bm{y}}}^{\Delta},t)$ is computed from an upper bound $\overline{{\bm{y}}}^{\Delta}$ on the logit differences ${\bm{y}}^{\Delta}:={\bm{y}}-y_{t}$ obtained via convex relaxations as described above and then plugged into the standard cross-entropy loss.

As this can induce strong over-regularization if the used convex relaxations are imprecise and thereby severely reduce the standard accuracy of the resulting models, current state-of-the-art certified training methods combine these bounds with adversarial training (Palma et al., ; Müller et al., ; Mao et al., ; Palma et al., ).
We now introduce the convex relaxations popular for neural networks.

### 2.2 Convex Relaxations

We now discuss four popular convex relaxations of different precision, which we investigate in this work.

#### IBP

Figure: Figure 2: IBP-relaxation of a ReLU with an input $v\in[l,u]$.

Interval bound propagation (Mirman et al., ; Gehr et al., ; Gowal et al., ) only considers elementwise, constant bounds of the form ${\bm{l}}\leq{\bm{v}}\leq{\bm{u}}$. Affine layers ${\bm{y}}={\bm{W}}{\bm{v}}+{\bm{b}}$ are thus also relaxed as

$$ $\tfrac{{\bm{W}}({\bm{l}}+{\bm{u}})-|{\bm{W}}|({\bm{u}}-{\bm{l}})}{2}+{\bm{b}}\leq{\bm{W}}{\bm{v}}+{\bm{b}}\leq\tfrac{{\bm{W}}({\bm{l}}+{\bm{u}})+|{\bm{W}}|({\bm{u}}-{\bm{l}})}{2}+{\bm{b}},$ $$

where $|\cdot|$ is the elementwise absolute value. ReLU functions are relaxed by their concrete lower and upper bounds $\operatorname*{ReLU}({\bm{l}})\leq\operatorname*{ReLU}({\bm{v}})\leq\operatorname*{ReLU}({\bm{u}})$, illustrated in [Figure 2](#S2.F2).

#### Hybrid Box (HBox)

The HBox relaxation is an instance of Hybrid Zonotope (Mirman et al., ) which combines the exact encoding of affine transformations from the DeepZ or Zonotope domain (Singh et al., ; Wong & Kolter, ; Weng et al., ; Wang et al., ) with the simple IBP relaxation of unstable ReLUs, illustrated in [Figure 2](#S2.F2). While less precise than DeepZ, HBox ensures constant instead of linear representation size in the network depth, making its computation much more efficient.

#### DeepPoly (DP)

Figure: Figure 3: DeepPoly relaxation of a ReLU with bounded inputs $v\in[l,u]$. The lower-bound slope $\lambda$ is chosen to minimize the area between the upper- and lower-bound in the input output space, resulting in the blue or green area.

DeepPoly, introduced by Singh et al. (), is mathematically identical to CROWN (Zhang et al., ) and based on recursively deriving linear bounds of the form

$$ ${\bm{A}}_{l}{\bm{x}}+{\bm{a}}_{l}\leq{\bm{v}}\leq{\bm{A}}_{u}{\bm{x}}+{\bm{a}}_{u}$ $$

on the outputs of every layer. While this allows affine layers to be handled exactly, ReLU layers ${\bm{y}}=\operatorname*{ReLU}({\bm{v}})$ are relaxed neuron-wise, using one of the two relaxations illustrated in [Figure 3](#S2.F3):

$$ $\bm{\lambda}{\bm{v}}\leq\operatorname*{ReLU}({\bm{v}})\leq({\bm{v}}-{\bm{l}})\frac{{\bm{u}}}{{\bm{u}}-{\bm{l}}},$ $$

where product and division are elementwise.
The lower-bound slope $\lambda=\mathds{1}_{|u|>|l|}$ is chosen depending on the input bounds $l$ and $u$ to minimize the area between the upper- and lower-bound in the input-output space. Crucially, a minor change in the input bounds can thus lead to a large change in output bounds when using the DeepPoly relaxation.

#### CROWN-IBP

To reduce the computational complexity of DeepPoly, CROWN-IBP (Zhang et al., ) uses the cheaper but less precise IBP bounds to compute the concrete upper- and lower-bounds ${\bm{u}}$ and ${\bm{l}}$ on ReLU inputs rquired to define the DeepPoly relaxation. To compute the final bounds on the network output DeepPoly is used. This reduces the computational complexity from quadratic to linear in the network depth. While, CROWN-IBP is not strictly more or less precise than either IBP or DeepPoly, its precision empirically lies between the two.

#### Relaxation Tightness

While we rarely have strict orders in tightness (only HBox is strictly tighter than IBP), we can compare the tightness of relaxations empirically given a network to analyze. Jovanović et al. () propose to measure the tightness of a relaxation as the AUC score of its certified accuracy over perturbation radius curve. This metric implies the following empirical tightness ordering IBP $<$ HBox $<$ CROWN-IBP $<$ DeepPoly (Jovanović et al., ), which agrees well with our intuition.

### 2.3 The Paradox of Certified Training

The robustness-accuracy trade-off dominating certified training describes how strongly we need to regularize for (certifiable) robustness at the cost of reduced standard accuracy. Intuitively, one would expect more precise relaxations to induce weaker regularisation and thus better standard and possibly also better certified accuracy. However, empirically the least precise relaxation, IBP, dominates the more precise methods, e.g., DeepPoly, with respect to both certified and standard accuracy (see the left-hand side of [Figure 1](#S1.F1)).
This is all the more surprising given that state-of-the-art certified training methods introduce artificial unsoundness into these IBP bounds to improve tightness at the cost of soundness to reduce regularisation and improve performance (Müller et al., ; Mao et al., ; Palma et al., ).

To explain this paradox, Jovanović et al. () show that these more precise relaxations induce loss landscapes suffering from discontinuities and high sensitivity, making it extraordinarily challenging for gradient-based optimization methods to find good optima. Thus the key challenge of certified training is to design a robust loss that combines tight bounds with a continous and smooth loss landscape.

Next, we discuss these challenges and show how to overcome them.

## 3 Gaussian Loss Smoothing for Certified Training

In this section, we first discuss Gaussian loss smoothing in policy gradient methods before showing how they can be applied to certified training. We defer the proofs to [App. A](#A1).

Figure: Figure 4: Illustration the PGPE algorithm: First we sample random perturbations around the central point from a Gaussian distribution with standard deviation $\sigma_{\textsc{PGPE}}$. Then we compute the loss difference between pairs of symmetric points. Finally, we estimate the gradient as a sum of sampled directions weighted by the magnitude of loss change in each direction.
Refer to caption: /html/2403.07095/assets/x1.png

### 3.1 Policy Gradients with Parameter-based Exploration

(PGPE) (Sehnke et al., ) is a gradient-free optimization algorithm that optimizes the Gaussian Smoothing loss $L_{\sigma}(\bm{\theta})\coloneqq\mathbb{E}_{\bm{\theta}^{\prime}\sim\mathcal{N}(\bm{\theta},\sigma^{2}\bm{I})}L({\bm{f}}_{\bm{\theta}^{\prime}})$, where the loss is not evaluated at a single parameterization of the network, but rather at a (normal) distribution of parameterizations.

To this end, PGPE samples weight perturbation $\bm{\epsilon}_{i}$ from $\mathcal{N}(0,\bm{\sigma}_{\textsc{PGPE}}^{2})$, and then evaluates the loss of the perturbed parametrizations $r^{+}_{i}=L(\bm{\theta}+\bm{\epsilon_{i}})$ and $r^{-}_{i}=L(\bm{\theta}-\bm{\epsilon}_{i})$.
These pairs of symmetric points are then used to compute gradient estimates with respect to both the mean of the weight distribution $\bm{\theta}$ and its standard deviation $\bm{\sigma}_{\textsc{PGPE}}$:

$$ $\displaystyle\nabla_{\theta}\hat{L}_{\sigma}(\theta)$ $\displaystyle\propto\sum_{i}\epsilon_{i}(r^{+}_{i}-r^{-}_{i}),$ $\displaystyle\nabla_{\sigma_{\textsc{PGPE}}}\hat{L}_{\sigma}(\theta)$ $\displaystyle\propto\sum_{i}\left(\frac{r^{+}_{i}+r^{-}_{i}}{2}-b\right)\left(\frac{\epsilon_{i}^{2}-(\sigma_{\textsc{PGPE}})_{i}^{2}}{(\sigma_{\textsc{PGPE}})_{i}}\right),$ $$

where $b$ is a baseline computed from the mean of all $2n$ samples $b=\frac{1}{2n}\sum_{i}(r^{+}_{i}+r^{-}_{i})$.
[Figure 4](#S3.F4) visualizes such a gradient estimate.
In training, these gradients can be used to both update the mean weights $\bm{\theta}$ and the main hyperparameter parameter of PGPE, the standard deviation $\bm{\sigma}_{\textsc{PGPE}}$.

Indeed, PGPE recovers an unbiased estimate of the gradients on the Gaussian smoothed, see:

###### Lemma 3.1 .

PGPE approximately minimizes the smoothed loss $L_{\sigma}(\theta)$ by sampling. In particular, the expectation of the PGPE update on $\theta$ is the true gradient of $L_{\sigma}(\theta)$, i.e., $\mathbb{E}\nabla_{\theta}\hat{L}_{\sigma}(\theta)=\nabla L_{\sigma}(\theta)$.

As *no* backward propagation is needed to compute these gradient estimates, PGPE is comparable to neuro-evolution algorithms. In this context it is among the best performing methods for supervised learning (Lange et al., ).

Figure: (a) Discontinuity.
Refer to caption: /html/2403.07095/assets/x2.png

###### Lemma 3.1 .

#### Open Challenges: Discontinuity and Sensitivity

We illustrate the key challenges causing the paradox of certified training ([Section 2.3](#S2.SS3)) on a toy network and loss in [Figure 5](#S3.F5).

On the left-hand side (original in [Figure 5(a)](#S3.F5.sf1)), we show the DeepPoly lower bound of the one-neuron network $y=\operatorname*{ReLU}(x+w)+1$ for $x\in[-1,1]$ over the parameter $w$.
As the original bound $l=1+\mathds{1}_{w>0}\cdot(w-1)$ is discontinuous at $w=0$, a gradient-based optimization method initialized at $w>0$ will decrease $w$ until it has moved through the discontinuity and past the local minimum.

The second key factor, sensitivity, can be interpreted as a combination of the number of local minima and the smoothness of the loss-landscape. Jovanović et al. () show that DeepPoly is more sensitive than IBP, making it more likely that gradient-based optimization methods will get stuck in a bad local minimum. We illustrate this with the toy function shown in [Figure 5(b)](#S3.F5.sf2). There the original function has a bad local minimum for $w\in[-1.5,0]$ that a gradient-based optimizer is likely to get stuck in.

We now discuss how Gaussian Loss Smoothing can address both of these challenges.

Figure: (a) $\sigma=0$ (original)
Refer to caption: /html/2403.07095/assets/x4.png

### 3.2 Gaussian Loss Smoothing for Certified Training

First, Gaussian Loss Smoothing (GLS) turns any discontinuous loss function (such as the one in [Figure 5(a)](#S3.F5.sf1)) into a continuous one that is differentiable everywhere. More formally:

###### Corollary 3.2 .

The loss surface under GLS is continuous, infinitely differentiable for any reasonably growing loss function $L(\theta)$.

Second, Gaussian Smoothing can help to overcome the sensitivity issue.
As we show in [Figure 5(b)](#S3.F5.sf2), depending on the standard deviation, the local minimum can be reduced or removed, and the loss landscape can be smoothed. However, the choice of standard deviation is crucial. While a too small standard deviation only has a minimal effect on loss smoothness and might not remove local minima, a too large standard deviation can oversmooth the loss, completely removing or misaligning minima. We again illustrate this in [Figure 5(b)](#S3.F5.sf2). There, a small standard deviation of $\sigma=0.2$ does not smooth out the local minimum while a large standard deviation ($\sigma=1.0$) severely misaligns the new global minimum with that of the original function.
We again formalize this result in the following corollary.

###### Corollary 3.3 .

The loss surface under GLS is $L$-smooth for any reasonably growing $L$-smooth loss function $L(\theta)$.

We conclude that GLS has the potential to mitigate the key issues, discontinuity and sensitivity, identified by Jovanović et al. () for tight bounding methods.

###### Corollary 3.2 .

###### Corollary 3.3 .

#### Emperical Confirmation

To empirically confirm these effects, we plot the original and smoothed loss landscape (along the direction of the DeepPoly gradient) of different relaxations for a CNN3 and different standard deviations in [Figure 6](#S3.F6). We normalize all losses by dividing them by their value for the unperturbed weights.

We observe that the original loss ([Figure 6(a)](#S3.F6.sf1)) is discontinuous and highly sensitive to perturbations for both CROWN-IBP and DeepPoly, consistent with the findings of Jovanović et al. ().
Only the imprecise IBP loss is continuous and smooth, explaining why the IBP loss is the basis for many successful certified training methods.
When the loss is smoothed with small standard deviations $\sigma=10^{-6}$ ([Figure 6(b)](#S3.F6.sf2)), the local minimum of the DeepPoly loss has a slightly reduced sharpness but is still present. In addition, both the losses for DeepPoly and CROWN-IBP are still highly sensitive. This indicates a too small $\sigma$.

When the standard deviation is increased to $\sigma=5\cdot 10^{-5}$ ([Figure 6(c)](#S3.F6.sf3)), the undesirable local minimum of the DeepPoly loss is removed completely, and both losses become much less sensitive to perturbations.
However, further increasing the standard deviation to $\sigma=5\cdot 10^{-4}$ ([Figure 6(d)](#S3.F6.sf4)),
leads to almost flat losses removing the minimum present in the underlying loss.

These results empirically confirm the observations in our toy setting and predicted by our theoretical analysis, showing that Gaussian Loss Smoothing (via PGPE) mitigates the discontinuity and sensitivity issues formulated by Jovanović et al. ().
Encouraged by these results, we now empirically evaluate the performance of PGPE-based certified training methods in the next section.

## 4 Experimental Evalaution

In this section, we rigorously evaluate the effect Gaussian Loss Smoothing via PGPE on the training characteristics of different bound computation methods.

First, we show in [Section 4.1](#S4.SS1) that the “Paradox of Certified Training” (Jovanović et al., ) can be overcome by smoothing the loss surface, i.e., that under Gaussian Loss Smoothing training with tighter bounds will generally lead to better certified and standard accuracy.

Second, we investigate how the hyperparameters of PGPE affect the properties of the induced loss surface and thus interact with the performance of the resulting certified training method in [Section 4.2](#S4.SS2).

Third and finally, we show in [Section 4.3](#S4.SS3) that the effects outlined above become even more pronounced as we scale to deeper networks.

#### Experimental Setup

We implement all certified training methods in PyTorch (Paszke et al., ) and conduct experiments on MNIST (LeCun et al., ) and CIFAR-10 (Krizhevsky et al., ) using $l_{\infty}$ perturbations and modified versions of the CNN3 and CNN5 architectures (see [Table 4](#A2.T4) in [App. B](#A2)). For more details regarding experimental setting including all hyperparameters see [App. B](#A2).

#### Standard Certified Training

For standard certified training using back-propagation (referred to below as GRAD for clarity), use similar hyperparameters as recent work in this domain (Shi et al., ; Müller et al., ; Mao et al., ) and initialize all models with Kaiming uniform (He et al., ). In particular, we also use the Adam optimizer (Kingma & Ba, ), follow their learning rate and $\epsilon$-annealing schedule, use the same batch size and gradient clipping threshold, and use the same ${\epsilon}$ for training and certification. In the case of SABR and STAPS we conduct an extensive optimization of their network-specific hyperparameters and only report the best one.

#### PGPE Training

We train our PGPE models using the multi-GPU, multi-actor implementation of evotorch (Toklu et al., ).
As PGPE training is computationally expensive, we initialize from a PGD-trained model. This can be seen as a warm-up stage as is common also for other certified training methods (Shi et al., ; Müller et al., ; Mao et al., ). We only use $\epsilon$-annealing for the larger perturbation magnitudes on both MNIST and CIFAR-10 and choose learning-rate schedules based on a brief initial evaluation of training stability. Unless indicated otherwise, we run the PGPE algorithm with a population size of $n_{ps}=256$ and an initial standard deviation for weight sampling of $\sigma_{\textsc{PGPE}}=10^{-3}$.

#### Certification

We use the state-of-the-art complete verification method MN-BaB (Ferrari et al., ) with the same settings as used by Müller et al. () for all networks independently of the training method. We note that this is in contrast to Jovanović et al. () who used the same method for training and verification. However, we aim to assess true robustness instead of certifiability with the same bounding method used during training.

#### Hardware

For PGPE training, we used between 2 and 8 V100s or L4s. For standard certified training and certification, we used single A6000s or A100s. See [Section B.5](#A2.SS5) for a detailed breakdown of the computational cost.

**Table 1: Comparison of the standard (Acc.) and certified (Cert. Acc.) accuracy for different certified training methods on the full MNIST and CIFAR-10. We use the state-of-the-art method MN-BaB (Ferrari et al., ) for certification.**
| Dataset | $\epsilon_{\infty}$ | Relaxation | Nat. Acc. [%] | Cert. Acc. [%] | Adv. Acc. [%] |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GRAD | PGPE | GRAD | PGPE | GRAD | PGPE |  |  |  |
| MNIST | 0.1 | PGD | 98.43 | - | 87.27 | - | 91.62 | - |
| IBP | 96.02 | 94.52 | 91.23 | 87.02 | 91.23 | 87.03 |  |  |
| SABR | 97.54 | 97.37 | 92.99 | 90.82 | 93.01 | 90.96 |  |  |
| STAPS | 97.48 | 96.31 | 93.53 | 89.39 | 93.53 | 89.41 |  |  |
| HBox | 94.79 | 96.12 | 88.18 | 90.57 | 88.18 | 90.58 |  |  |
| CROWN-IBP | 94.33 | 96.69 | 88.76 | 90.23 | 88.77 | 90.25 |  |  |
| DeepPoly | 95.95 | 97.44 | 90.04 | 91.53 | 90.08 | 91.79 |  |  |
| 0.3 | PGD | 96.08 | - | 75.14 | - | 77.44 | - |  |
| IBP | 91.02 | 89.16 | 77.23 | 74.00 | 77.27 | 74.08 |  |  |
| HBox | 83.75 | 86.58 | 57.86 | 70.52 | 57.92 | 70.66 |  |  |
| CROWN-IBP | 86.97 | 90.57 | 70.55 | 71.95 | 70.56 | 72.24 |  |  |
| DeepPoly | 77.87 | 91.05 | 47.28 | 74.28 | 47.36 | 74.98 |  |  |
| CIFAR 10 | 2/255 | PGD | 60.35 | - | 34.62 | - | 40.12 | - |
| IBP | 48.05 | 44.55 | 37.69 | 34.09 | 37.70 | 34.10 |  |  |
| CROWN-IBP | 44.49 | 51.19 | 35.75 | 37.51 | 35.75 | 37.65 |  |  |
| DeepPoly | 47.70 | 54.17 | 36.72 | 38.95 | 36.72 | 40.20 |  |  |
| 8/255 | PGD | 50.18 | - | 7.90 | - | 19.65 | - |  |
| IBP | 34.63 | 30.48 | 25.72 | 21.75 | 25.74 | 21.75 |  |  |
| CROWN-IBP | 31.60 | 32.36 | 22.66 | 21.40 | 22.66 | 21.42 |  |  |
| DeepPoly | 33.06 | 31.37 | 22.97 | 22.19 | 22.98 | 22.19 |  |  |

### 4.1 Overcoming the Paradox of Certified Training

In [Table 1](#S4.T1), we compare the performance of training with various convex relaxations using either backpropagation to calculate gradients directly (GRAD) or the PGPE algorithm to obtain estimates of the smoothed gradients.

#### GRAD Training

We train the same CNN3 on MNIST and CIFAR-10 at the established perturbation magnitudes using standard certified training with IBP, HBox, CROWN-IBP, and DeepPoly.
We observe that across all these settings IBP dominates the other methods both in terms of standard and certified accuracy, agreeing well with the paradox of certified training.
Among the remaining methods, HBox, CROWN-IBP, and DeepPoly tend to perform similarly with CROWN-IBP being significantly better at MNIST ${\epsilon}=0.3$, indicating that in the absence of continuity and for high sensitivity, tightness is less relevant.

#### PGPE Training

Training the same CNN3 in the same settings with PGPE we observe that the performance ranking changes significantly (see [Table 1](#S4.T1)).
Now, training with the loose IBP bounds performs strictly worse than training with the more precise DeepPoly bounds across all datasets and perturbation sizes.
In fact, the most precise DeepPoly bounds now yield the best certified accuracy across all settings, even outperforming GRAD-based training methods at low perturbation magnitudes.

Interestingly IBP still yields better certified accuracy at large perturbation magnitudes than HBox and CROWN-IBP, although at significantly worse natural accuracies. This is likely due to the fact that a more severe regularization is required in these settings.

These results suggest that we were indeed able to alleviate the sensitivity and discontinuity problems of more precise convex relaxations by leveraging Gaussian Loss Smoothing. As Gaussian Loss Smoothing via PGPE does not require differentiability, this points to future training methods based on even more precise bounds than DeepPoly, computed, e.g., via a branch and bound-based procedure.

We note, that while DeepPoly + PGPE outperforms DeepPoly + GRAD in almost all settings and sometimes by a wide margin, it does not beat the state-of-the-art GRAD training methods in most settings. We believe this to be due to three key factors:
First, PGPE computes a gradient approximation in an $\tfrac{n_{ps}}{2}$-dimensional subspace. Thus, computing high-dimensional gradient information requires a population size corresponding to twice the number of network parameters. This, however, is computationally intractable even for the small networks we consider given the high cost of evaluating DeepPoly. Thus we only obtain low-dimensional gradient approximates, which lead to slower training (as we show in [Table 2](#S4.T2) and [Figure 10](#A2.F10)).
Second, again due to the high cost of training with PGPE, we used relatively short training schedules and were unable to optimize hyperparameters for the different settings.
And third, PGPE-based certified training is less optimized, compared to standard certified training which has been extensively optimized over the past years (Shi et al., ; Müller et al., ; Palma et al., ).

### 4.2 Ablation Studies

**Table 2: Effect of the population size $n_{ps}$ on accuracy and training time with PGPE + DeepPoly training on CNN3.**
| Popsize | Nat. [%] | Cert. [%] | GPU h |
| --- | --- | --- | --- |
| Init | 97.14 | 94.02 | - |
| 64 | 97.22 | 94.07 | 88 |
| 128 | 97.22 | 94.13 | 160 |
| 256 | 97.30 | 94.19 | 304 |
| 512 | 97.27 | 94.22 | 596 |
| 1024 | 97.43 | 94.50 | 1192 |

Figure: Figure 7: Effect of the population size $n_{ps}$ on the induced loss surface in PGPE.
Refer to caption: /html/2403.07095/assets/x8.png

#### Population Size

While PGPE recovers Gaussian Loss Smoothing in expectation, the quality of the gradient approximation depends strongly on the population size $n_{ps}$.
In particular, a small population size $n_{ps}$ induces a high-variance estimate of the true smoothed loss, leading to noisy gradient estimates and thus slow learning or even stability issues. We illustrate this in [Figure 7](#S4.F7) where we show the loss surface along the gradient direction for different population sizes. We observe that for small population sizes the loss surface is indeed very noisy, only becoming visually smooth at $n_{ps}=512$.
Additionally, PGPE computes a gradient approximation in an $\tfrac{n_{ps}}{2}$-dimensional subspace, thus further increasing gradient variance if $n_{ps}$ is (too) small compared to the number of network parameters.

To assess the effect this has on the performance of PGPE training, we train the same CNN3 on MNIST using population sizes between $64$ and $1024$, presenting results in [Table 2](#S4.T2).
We observe that performance does indeed improve significantly with increasing population sizes (note the relative performance compared to initialization). This becomes even more pronounced when considering the training dynamics (see [Figure 10](#A2.F10)).
Unfortunately, the computational cost of PGPE is significant and scales linearly in the population size. We thus choose $n_{ps}=256$ for all of our main experiments, as this already leads to training times in excess of $3$ weeks on $8$ V100s for some experiments.

Figure: Figure 8: Effect of the standard deviation $\sigma_{\textsc{PGPE}}$ on the induced loss surface in PGPE at a small population sizes of $n_{ps}=32$.
Refer to caption: /html/2403.07095/assets/x9.png

#### Standard Deviation

The standard deviation $\sigma$ used for Gaussian Loss Smoothing has a significant impact on the resulting loss surface as we illustrated in [Figure 6](#S3.F6) and discussed in [Section 3](#S3). If $\sigma$ is chosen too small, the loss surface will still exhibit high sensitivity and gradients will only be meaningful very locally as discontinuities are barely smoothed. On the other hand, if $\sigma$ is chosen too large, the loss surface will become very flat and uninformative, preventing us from finding good solutions.

When estimating the smoothed loss in PGPE via sampling at moderate population sizes $n_{ps}$, the standard deviation $\sigma_{\textsc{PGPE}}$ additionally affects the variance of the loss and thus gradient estimate. We illustrate this in [Figure 8](#S4.F8), where we not only see the increasing large-scale smoothing effect discussed above but also an increasing level of small-scale noise induced by a large $\sigma_{\textsc{PGPE}}$ relative to the chosen population sizes $n_{ps}$.

To assess the effect this practically has on PGPE training, we train for 50 epochs with different standard deviations $\sigma_{\textsc{PGPE}}$ and present the results in [Figure 9](#S4.F9). As expected, we clearly observe that both too small and too large standard deviations lead to poor performance. However, and perhaps surprisingly, we find that training performance is relatively insensitive to the exact standard deviation as long as we are in the right order of magnitude between $10^{-}3$ and $10^{-}2$.

Figure: Figure 9: Train and Validation Losses after 50 epochs of training for different values of $\sigma_{\textsc{PGPE}}$.
Refer to caption: /html/2403.07095/assets/x10.png

### 4.3 Scaling to Deeper Networks

While the results presented so far are promising, they are obtained on relatively small networks. We now investigate how the effects of Gaussian Loss Smoothing via PGPE scale to deeper networks. In [Table 3](#S4.T3) we compare the performance of a CNN5 trained wigh PGPE + DeepPoly on MNIST at ${\epsilon}=0.1$ to a range of GRAD-based training methods including the state of the art SABR (Müller et al., ) and STAPS (Mao et al., ).

Encouragingly, we not only observe that PGPE training improves performance significantly for the same bound computation method but that PGPE + DeepPoly dominates all other methods, substantially improving even over state-of-the-art GRAD-based methods. This result agrees well with our expectation that bound tightness becomes increasingly important with network depth, as in particular box approximation errors grow exponentially with the number of layers (Shi et al., ; Müller et al., ; Mao et al., ).

**Table 3: Accuracies of a CNN5 on MNIST 0.1 depending on training method.**
| Training Method | Nat. [%] | Cert. [%] | Adv. [%] |
| --- | --- | --- | --- |
| IBP | 96.67 | 93.02 | 93.04 |
| SABR 0.1 | 98.60 | 94.87 | 94.95 |
| STAPS 0.2 | 98.60 | 94.98 | 95.03 |
| DeepPoly | 88.82 | 84.34 | 84.35 |
| DeepPoly-PGPE | 98.83 | 96.98 | 97.08 |

## 5 Limitations

Unfortunately, training with PGPE, in particular in combination with DeepPoly, is prohibitively computationally expensive, preventing us from experimenting with larger architectures. In fact, training our CNN5 already required over 3 weeks on 8 V100s ($>4000$ GPU hours translating to approximately $\$10\,000$). We thus believe it is both an essential but also extremely promising item for future work to investigate more computationally efficient approaches for Gaussian Loss Smoothing in certified training.

## 6 Conclusion

We show that Gaussian Loss Something can overcome the paradox of certified training by inducing a continuous and infinitely differentiable loss surface even for tight bound computation methods. To validate this empirically, we implement Gaussian Loss Smoothing via PGPE for certified training and demonstrate that, in this setting, tighter bounds lead to networks with strictly better performance. While our approach is computationally expensive, we believe it highlights a promising direction for future work and confirms the crucial importance of continuity and sensitivity in certified training.

## 7 Broader Impact

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

## Acknowledgements

This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement no. 101070617) and the SERI grant SAFEAI (Certified Safe, Fair and Robust Artificial Intelligence, contract no. MB22.00088). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commission. Neither the European Union nor the European Commission can be held responsible for them.

The work has received funding from the Swiss State Secretariat for Education, Research and Innovation (SERI).

This research was partially funded by the Ministry of Education and Science of Bulgaria (support for INSAIT, part of the Bulgarian National Roadmap for Research Infrastructure).

## Appendix A PGPE Optimizes Smoothed Loss

###### Lemma A.1 .

For any reasonably growing loss function $L(\theta)$ such that $|L(\theta)|\exp(-\theta^{2-\delta})=O(1)$ for some $0<\delta<2$, let its Gaussian smoothing be $L_{\sigma}(\theta)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,\sigma^{2})}L(\theta+\epsilon)$ for some $\sigma>0$. Then $L_{\sigma}(\theta)$ is continuous and infinitely differentiable.

###### Proof.

$L_{\sigma}(\theta)$ exists due to the growth bound on $L(\theta)$. Further,

$$ $\displaystyle\frac{L_{\sigma}(\theta+\Delta\theta)-L_{\sigma}(\theta)}{\Delta\theta}$ $\displaystyle=\frac{1}{\Delta\theta}\left[\mathbb{E}_{\epsilon_{1}\sim\mathcal{N}(\Delta\theta,\sigma^{2})}L(\theta+\epsilon_{1})-\mathbb{E}_{\epsilon_{2}\sim\mathcal{N}(0,\sigma^{2})}L(\theta+\epsilon_{2})\right]$ $\displaystyle=\int_{-\infty}^{\infty}\frac{1}{\Delta\theta}[P_{\epsilon_{1}}(x)-P_{\epsilon_{2}}(x)]L(\theta+x)dx$ $\displaystyle=\int_{-\infty}^{\infty}\nabla_{x}\left[\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp(-\frac{x^{2}}{2\sigma^{2}})\right]L(\theta+x)dx$ $\displaystyle=-\int_{-\infty}^{\infty}P_{\mathcal{N}(0,\sigma^{2})}(x)L(\theta+x)\cdot\frac{x}{\sigma^{2}}dx.$ $$

Since $|L(x)|\exp(-x^{2-\delta})=O(1)$, the above integral is finite,
thus $L_{\sigma}(\theta)$ has first-order derivative and continuous. Similarly, we can show that $L_{\sigma}(\theta)$ has higher-order derivatives and thus infinitely differentiable.
∎

###### Lemma A.2 .

If $L(\theta)$ is $L$-smooth, then $L_{\sigma}(\theta)$ is $L$-smooth as well.

###### Proof.

We cite this result from Starnes et al. ().
∎

###### Lemma A.3 .

PGPE approximately minimizes the smoothed loss $L_{\sigma}(\theta)$ by sampling. In particular, the expectation of the PGPE update on $\theta$ is the true gradient of $L_{\sigma}(\theta)$, i.e., $\mathbb{E}\nabla_{\theta}\hat{L}_{\sigma}(\theta)=\nabla L_{\sigma}(\theta)$.

###### Proof.

This follows from the design principle of PGPE. For more details, see Sehnke et al. ().
∎

###### Corollary A.4 .

The loss surface of PGPE is continuous, infinitely differentiable and more smooth than $L(\theta)$ for any reasonably growing loss function $L(\theta)$.

###### Proof.

This follows from [Lemma A.1](#A1.Thmtheorem1) and [Lemma 3.1](#S3.Thmtheorem1).
∎

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Lemma A.3 .

###### Proof.

###### Corollary A.4 .

###### Proof.

## Appendix B Additional Training Details

### B.1 Standard Certified Training

We train with the Adam optimizer (Kingma & Ba, ) with a starting learning rate of $5\times 10^{-5}$ for 70 epochs on MNIST and 160 epochs on CIFAR-10. We use the first 20 epochs on MNIST and 80 epochs on CIFAR-10 for $\epsilon$-annealing and we decay the learning rate by a factor of 0.2 after epochs 50 and 60 for MNIST and respectively 120 and 140 for CIFAR-10.

### B.2 PGPE Training

We use a training schedule of 150 epochs, with a batch size of 512 for MNIST and 128 for CIFAR-10. We train with a starting learning rate of 0.0003 and we decay it twice by a factor of 0.4 after the 110^th and 130^th epoch. We use the first 50 epochs for $\epsilon$-annealing only when training with the large value of $\epsilon$ for each dataset (MNIST $\epsilon$ = 0.3 and CIFAR-10 $\epsilon$ = 8/255).

### B.3 Architectures

In [Table 4](#A2.T4) we present the two network architectures used for all our experiments.

**Table 4: Network architectures of the convolutional networks for CIFAR-10 and MNIST. All layers listed below are followed by a ReLU activation layer. The output layer is omitted. ‘Conv c h$\times$w/s/p’ corresponds to a 2D convolution with c output channels, an h$\times$w kernel size, a stride of s in both dimensions, and an all-around zero padding of p.**
| CNN3 | CNN5 |
| --- | --- |
| Conv 8 5$\times$5/2/2 | Conv 16 5$\times$5/2/2 |
| Conv 8 4$\times$4/2/1 | Conv 16 4$\times$4/2/1 |
|  | Conv 32 4$\times$4/2/1 |
|  | FC 512 |

### B.4 Dataset and Augmentation

We use the MNIST (LeCun et al., ) and CIFAR-10 (Krizhevsky et al., ) datasets, all of which are freely available with no license specified.

The data preprocessing mostly follows Müller et al. (). For MNIST, we do not apply any preprocessing. For CIFAR-10, we normalize with the dataset mean and standard deviation (after calculating perturbation size) and augment with random horizontal flips. In addition, we apply random cropping to $32\times 32$ after applying a $2$ pixel padding at every margin for CIFAR-10.

### B.5 Training costs (Time and Resources)

In [Table 5](#A2.T5) we present a detailed analysis of the training costs of the PGPE method for all of our experimental settings.

**Table 5: Training costs and workload distribution across GPUs / actors for each train setting.**
| Datset | Architecture | Relaxation | GPUs | Num. Actors | Time/epoch (min) | GPU-h/epoch |
| --- | --- | --- | --- | --- | --- | --- |
| MNIST | CNN3 | IBP | 2 x L4 | 4 | 2.8 | 0.09 |
| SABR | 2 x L4 | 4 | 7.6 | 0.25 |  |  |
| STAPS | 2 x L4 | 4 | 17 | 0.57 |  |  |
| CROWN-IBP | 2 x L4 | 4 | 8.5 | 0.28 |  |  |
| HBox | 8 x L4 | 8 | 31 | 4.13 |  |  |
| DeepPoly | 8 x L4 | 8 | 27 | 3.60 |  |  |
| DeepPoly | 8 x V100 | 8 | 16 | 2.13 |  |  |
| CNN5 | DeepPoly | 8 x L4 | 8 | 312 | 41.6 |  |
| DeepPoly | 8 x V100 | 8 | 207 | 27.6 |  |  |
| CIFAR-10 | CNN3 | IBP | 2 x L4 | 4 | 6.9 | 0.23 |
| SABR | 4 x L4 | 8 | 14 | 0.93 |  |  |
| CROWN-IBP | 4 x L4 | 8 | 8.5 | 0.57 |  |  |
| DeepPoly | 8 x V100 | 8 | 29 | 3.87 |  |  |

### B.6 Train Dynamics

In [Figure 10](#A2.F10) we present the evolution of the Training Loss during training with different values for popsize $n_{ps}$. We observe significantly slower training as we decrease $n_{ps}$, confirming the theoretical prediction that using lower popsize decreases the quality of gradient estimations due to increased variance in the loss-sampling process.

Figure: Figure 10: Evolution of Train Loss during training with different values for popsize $n_{ps}$. Note that for $n_{ps}=64$ we trained with a lower learning rate because the value used in the other settings would make training unstable.
Refer to caption: /html/2403.07095/assets/x11.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - There is no comparison with CROWN-IBP in Table 3. Why?
- "We remark that scaling to CNN7 used by the SOTA methods is still infeasible due to the high computatinoal cost of evaluating DeepPoly" How about applying RGS to CROWN-IBP as it is cheaper than DeepPoly?
- What do the italic numbers mean in Table 3?
- DP-RGS appears first in L480, but never defined (seems like DP-RGS = DeepPoly-RGS).
soundness: 3
strengths: I think the following strength itself is enough for accept.
- The paradox of certified training is an important subject to study.
- The proposed method (GLS) is well-motivated and backed up by theoretical results.
- The empirical results on small perturbation settings in Table 3 are quite impressive.
summary: This paper proposes to use a method (Gaussian Loss Smoothing) to address the paradox of certified training which is caused by the discontinuity/non-smoothness/sensitivity issues of certifiable training with tighter convex relaxations. Moreover, the authors also use a gradient-based method called Randomized Gradient Smoothing (RGS) to scale GLS to larger models.
weaknesses: This paper is well-motivated, but has a minor weakness in the performance (on large perturbation) detailed as follows:
- Table 3 (Table 5 in Appendix) shows the results for small (large) perturbation settings. The results for large perturbation is not significant. IBP performs well for large perturbations and other tighter methods does well for small perturbations. This is because of the continuity, smoothness and sensitivity of the loss landscape. Thus, to check the effectiveness of GLS, I think it is crucial to check the result of tighter methods on large perturbation settings. However, setups (i) MNIST $\epsilon=0.3$ and (ii) CIFAR-10 $\epsilon=8/255$ show that 
GLS (or RGS) (i) does not show a significant performance gain (DP-RGS (IBP) vs MTL-IBP; 88.69 vs 88.68) or (ii) shows a worse performance (29.25 vs 29.62). This should be discussed in the main text (not in Appendix). I don't think the performance itself is a reason for a rejection, but it needs more discussion.
- In Table 1, "the more precise DeepPoly bounds now yield the best certified accuracy across all settings, even outperforming accuracy at low perturbation radii'', but not for the large perturbation (IBP vs DeepPoly-PGPE; 77.23 vs 74.28, 25.72 vs 22.19).
- In GRAD Training, "IBP dominates the other methods, confirming the paradox of certified training", but in the original paper of CROWN-IBP, CROWN-IBP outperforms IBP for a larger network (see their Table 2 https://arxiv.org/pdf/1906.06316). 
- (For a larger model,) IBP outperforms the other methods (e.g, CROWN-IBP, CAP) for large perturbation, not for small perturbation (e.g., see Table 1 in Lee et al. (2021)). This implies that the paradox plays more important role for a larger perturbation.



Please check the Questions part together. I think unclear presentation is also a weakness.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 1
questions: GLS appears to be related to Sharpness-Aware Minimization (SAM) [1], as both approaches aim to smooth the loss landscape for a more regular surface. It would be beneficial to include a discussion or a related work section to clarify this connection in the paper.

[1] Foret et al., “Sharpness-Aware Minimization for Efficiently Improving Generalization,” ICLR, 2021.
soundness: 2
strengths: GLS introduces novelty in using Gaussian smoothing across the loss landscapes, strongly problematic in certified training.
summary: The paper talks about the variation in certified training; though tighter relaxations sometimes reduce performance compared to looser bounds, it shows the authors introducing Gaussian Loss Smoothing as one of the methods for smoothing the loss landscape to reduce discontinuity and sensitivity—the major hurdles in certified training with tight relaxations.

They provide two ways of realizing the different realizations of GLS: first is PGPE, a gradient-free approach based on policy gradients with parameter-based exploration; second is RGS, which is described as a gradient-based approach using randomized gradient smoothing. Experimental results on several datasets illustrate that indeed the algorithm GLS outperforms current methods relying on tight relaxations; sometimes its performance is tested along with the DEEPPOLY relaxation.
weaknesses: ## Writing Style

- **Introduction**: In some respects, the introduction could be improved about adversarial certified robustness. It is abrupt and feels more work-related.
  
- **Transitions and Structure**: Transitions from one section to another are missing; hence, making the paper hard to follow. Statements such as, "While CROWN-IBP is not strictly more or less precise than either IBP or DEEPPOLY," necessarily need references or explanations.

- **Undefined Terms**: Terms such as "soundness" and "sensitivity" are undefined.

- **Results of experiments**: These are presented in a very untidy fashion.


## Related Work

- **Definitions**: Some more clear definitions can be provided, for instance, adversarial attack and adversarial robustness because the latter is different from certified robustness.
  
- **Redundant Subsections**: Sections 2.1 would seem to represent redundant subsections: "Training for Robustness" and "Adversarial Training."


## Theoretical Findings

- **Lack of Rigor**: Theoretical statements, like Theorem 3.1, are informal and not mathematically precise. References to results, including Stein's Lemma [2], could be good in the proof.
  
- **Flaw in Proofs in Lemmas**: 
In the proof of Lemma B.1 terminology and symbols that are important are not defined (for example, \(\delta \theta\), \(P_{\epsilon_1}\), \(P_{\epsilon_2}\), \(P_{\mathcal{N}(0, \sigma^2)}\)). The authors seem to take the limit $\delta \theta$ to $0$ but it is never stated anywhere in the proof and the integral of the derivative of the loss  $L^\prime$  should be a multi dimensional integral as the input space is multi dimensional.
In Lemma B.2's proof  the simplifications are excessive,  the structure of the proof is highly defective in many places and it needs a thorough revision. 



## Experimental Results

- **Lack of Detail**: Neither the dataset nor the architecture used in Figure 1 are specified.
  
- **Performance Gains**: Although the experimental results are somewhat improved, they are not very significant compared to previous methods; therefore, this added complexity is questionable in value. Presentation of the standard deviations over multiple runs would have given more robust conclusions since apparent gains are marginal.


# Major Concerns

1. **Theoretical Rigor**: The proofs are not rigorous; better structure and formalization are required. The use of Stein's Lemma might improve the underlying framework, giving credibility to the theoretical results.
  
2. **Marginal Gains and Complexity**: GLS brings in computational complexity especially with PGPE, while performance benefits are marginal.

3. **Readability and Clarity**: The writing style and the structure take away from clarity, making the paper difficult to follow.


[2] Stein, “Estimation of the Mean of a Multivariate Normal Distribution,” The Annals of Statistics, 1981.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 3
questions: 1. DeepPoly-GRAD achieves 90.04% certified accuracy on MNIST (0.1) in Table 1; in Table 2 this number is only 68.47%. Is this a typo? I don't believe that changing the model size can make such a big difference; plus, only DeepPoly-GRAD has such a huge drop in performance.
2. Is it correct that you are only changing the loss of training the model, but you are not changing the way of certifying the model?
soundness: 2
strengths: 1. The writing is fine. There is little difficulty understanding the paper.
summary: This paper proposes to use Gaussian Loss Smoothing (GLS) with certified training algorithm, such as IBP, CROWN, etc. The motivation is that a previous paper pointed out that methods other than IBP, though having tighter relaxation, suffer from discontinuity, non-smoothness, perturbation sensitivity. The authors argue that GLS can make the loss surface smoother using a theoretical result and some plots as evidence. The method is tested on MNIST, Cifar-10 and TinyImagenet.
weaknesses: 1. Contribution: This paper proposes to apply GLS to existing certified training methods such as IBP and DeepPoly, and one can use PGPE or RGS to compute the GLS. Note that, however, all of IBP, DeepPoly, GLS, PGPE and RGS are existing methods. Theorem 3.1 is a direct application of an existing result. So if I understand correctly, the only novelty of this submission is combining these things together, and thus the contribution is incremental.
2. Performance: How does the proposed method perform? From Table 1, it seems that the proposed method (PGPE) is not significantly better than the standard method (GRAD), if not worse. It is true that PGPE makes DeepPoly better than IBP, but the way it does that is to make IBP worse, not making DeepPoly better. On MNIST (0.3) and CIFAR-10 (8/255), the best PGPE method is worse than the best GRAD method. On the other two settings, it is only slightly better. For all settings, IBP-PGPE is worse than IBP-GRAD (standard). Thus, this result suggests that one probably should not use PGPE. There is no evidence that the proposed method works in practice.
3. Experimental results: Tables 1 and 3 seem contracting with each other. In Table 1, standard IBP on CIFAR-10 (2/255) has natural accuracy 48.05% and certified accuracy 37.69%; in Table 3, the two reported numbers are 54.92% and 45.36%. Probably this is because CNN5 is better than CNN3, but then what is the point of Table 1? Why not always use a bigger model (CNN7 seems even better). And why not compare with RGS in Table 1? I don't think there is anything preventing you from comparing with RGS in Table 1. The authors report DP-RGS to be the best method in Table 3, but since there are so many problems with the tables I do not trust this result.

Overall, this submission proposes to combine a bunch of existing methods, but the experiments show that this is even worse than the original methods. Thus, I recommend rejecting this submission.

Meta-review: The main claim of the paper is that issues arising in certified training can be alleviated by smoothing the loss surface in parameter space of a neural network by convolving it with a Gaussian distribution. 

Combining ideas of loss smoothing and convex relaxation is an interesting direction, and some of the experiments in the small perturbation setting are encouraging. However, there are several concerns pointed out by the reviewers regarding theoretical rigor, marginal gains in the experiments and incremental contributions. 

I recommend to reject the paper and encourage the authors to take the detailed comments of the reviewers into account for a resubmission.

Decision: Reject