Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations
Authors: Stefan Balauca
Mark Niklas Mueller
Yuhao Mao
Maximilian Baader
Marc Fischer
Martin Vechev
Venue: Accepted by TMLR ()

Abstract: Training neural networks with high certified accuracy against adversarial examples remains an open challenge despite significant efforts. 
While certification methods can effectively leverage tight convex relaxations for bound computation, in training, these methods, perhaps surprisingly, can perform worse than looser relaxations. 
Prior work hypothesized that this phenomenon is caused by the discontinuity, non-smoothness, and perturbation sensitivity of the loss surface induced by tighter relaxations. 
In this work, we theoretically show that Gaussian Loss Smoothing (GLS) can alleviate these issues. 
We confirm this empirically by instantiating GLS with two variants: a zeroth-order optimization algorithm, called PGPE, which allows training with non-differentiable relaxations, and a first-order optimization algorithm, called RGS, which requires gradients of the relaxation but is much more efficient than PGPE. 
Extensive experiments show that when combined with tight relaxations, these methods surpass state-of-the-art methods when training on the same network architecture for many settings. 
Our results clearly demonstrate the promise of Gaussian Loss Smoothing for training certifiably robust neural networks and pave a path towards leveraging tighter relaxations for certified training.

Published in Transactions on Machine Learning Research (07/2025)
Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxations
Stefan Balauca INSAIT, Sofia University "St. Kliment Ohridski", Bulgaria
steforn.balaucaa@gmaa
Mark Niklas Müller
LogieStar.at
(work done while at ETH Züiiich)
Yuhao Mao
yuhao. moo ethe.ch ch
Department of Computer Science, ETH Zürich, Switzerland
Maximilian Baader
mbbadde mbaader@inff. etha.ch ch
Department of Computer Science, ETH Zürich, Switzerland
Marc Fischer
ware etw.e..eeethccc
Inveriant Labs
(work done while at ETH Zürich)
Martin Vechev
martin. sortin.vochev@inf..lee
Department of Computer Science, ETH Zürich, Switzerland
Reviewed on OpenReview: http:://opparreeeeerrre/////m/se
Abstract
Training neural networks with high certified accuracy against adversarial examples remains an open challenge despite significant efforts. While certification methods can effectively leverage tight convex relaxations for bound computation, in training, these methods, perhaps surprisingly, can perform worse than looser relaxations. Prior work hypothesized that this phenomenon caused by the discontinuity, non-smoothness, and perturbation sensitivity of the loss surface induced by tighter relaxations. In this work, we theoretically show that applying Gaussian Loss Smoothing (GLS) on the loss surface alleviate these issues. We confirm this empirically by instantiating GLS with two variants: zeroth-order optimization algorithm, called PGPE, which allows training with non-differentiable relaxations, and first-order optimization algorithm, called RGS, which requires gradients of the relaxation but much more efficient than PGPE. Extensive experiments show that when combined with tight relaxations, these methods surpass state-of-the-art methods when training on the same network architecture for many settings. Our results clearly demonstrate the promise of Gaussian Loss Smoothing for training certifiably robust neural networks and pave a path towards leveraging tighter relaxations for certified training.
1 Introduction
The increased deployment of deop learning systems in mission-critical applications has made their provable trustworthiness and robustness against adversarial examples (Biggio el. al. 2013 Szegedy et al. [004]] an important topic. As state-of-the-art
the-art neural network certification has converged to similar approaches (Zhagg ct al.) 2022 Ferrari al.) (022)), increasingly reducing the verification gap, the focus in the field is now shifting specialized training methods that yield networks with high certified robustness while minimizing
the loss of standard accuracy (Müller et. al. 2023
Mao et. al. 2023a
De Palma al. 2024).

---

Published in Transactions on Machine Learning Research (07/2025)
Relaxation
Tightness
GRAD [%]
PGPE [%]
RGS [%]]
IBP
0.55
91.23
Loss Smoothing
87.02
90.46
CROWN-IBP
1.68
88.76
90. 23
90.71
DEEPPOLY 2.93
90.04
91.53
91.88
Figure 1: Illustration of how Gaussian loss smoothing enables certified training with tight relaxations. We compare the Certified Accuracy [%] obtained by training a CNN3 network on MNIST < <= 0.1 with different. relaxations using either the standard gradient (GRAD, used as baseline) or a gradient estimate computed on the smoothed loss surface (PGPE and RGS) with the empirical lightness of the method. Using GRAD methods produces the best results with the least tight IBP relaxation, which is known as the paradox of certified training. However, using GLS-based optimization methods PGPE and RGS, we obtaín clear correlation between relaxation lightness and performance.
Certified Training Statc-of-the-art (SOTA) 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. 2017], they typically utilize convex relaxations to compute
over-aprrxximation of this loss (Gowal et a 2018 Singh et al. 2018 2019). Surprisingly, training mothods based on the least precise relaxations (IBP) empirically yield the best performance (Shi et al. 2021). while tighter relaxations perform progressively worse (left, Figure D. Jovanović et al. (2022) and (Lee et al., 2021 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 continuily, smoolhness, and sensitivily 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, smooth, and insensitive IBP bounds (Mäller et. al. 2023 Mao et al. 2023a De Palma et al.) 2024). However, while these IBP-based methods improve robustness, they induce severe regularization, significantly limiting the effective capacity and thus standard accuracy (Mao et al. 2023b
This raises the following fundamental question:
Can we enable certified training with tight conver relazations by addressing the discontinuity, non-smoothness, and perturbation sensitivily, thus obtaining a better aalustness-cccuracy trade-off?
This Work: Enabling Certified Training with Tight Convex Relaxations In this work we propose concept.ual path forward to overcoming the paradox by addressing the three issues identified by prior works. Our key insight is that the discontinuity, non-smoothness, and perturbation scnsitivity of the loss surface can be mitigated by smoothing the training loss with a Gaussian kernel over the network parameter search space. We refer to this approach as Gaussian Loss Smoothing (GLS). To instantiate GLS, we propose to augment certified training using two methods: (1) a gradient-free method based on Policy Gradients with Parameter- based Exploration (PGPE) (Sehnke et al., 2010 and (2) a gradient-based based method based on Randomized Gradient Smoothing (RGS) (Starnes el al.] 2023). While both methods approximale GLS which is intractable to compute exactly, they enjoy different benefits: (1) PGPE allows training with non-differentiable relaxations, while (2) RGS is much more efficient than PGPE. We note that the GLS principles, as well as the PGPE and RGS algorithms are independent of the training loss we choose to optimize, and therefore can be applied on top of any certified training method and any convex relaxation.
Using these GLS mothods, we empirically demonstrate that tighter relaxations can indoed load to strictly better networks, thereby confirming the importance of addressing discontinuily, non-smoothness, and perturbation sensitivity (right, Figure D. Critically, with the more precise DERPPOLY relaxation (Singh et al. 2019). we show that GLS methods achieve strictly better results than the less precise IBP. Moreover, we demonstrate that the advantages of GLS improve with increasing network depth, outperforming state-of-the-art methods applied for the same architecture in many settings, particularly when precision matters more. Our results demonstrate the promisc of GLS for training certifiably robust neural networks and pave a path towards leveraging lighter relaxations for certified training.
2

---

Published in Transactions on Machine Learning Research (07 (025))
Main Contributions Our core contributions are:
1. A theoretical investigation showing Gaussian Loss Smoothing (GLS) mitigates discontinuity, non- smoothness, and perturbation sensitivity of the loss surface in certified training with tight relaxations.
2. A PGPE-based adaptation of certified training that approximates GLS in zeroth-order optimization, enabling training with tight non-differentiable relaxations.
3. A RGS-based adaptation of certified training that approximates GLS in first-order optimization, requiring differentiable relaxations, but achieving speedup of up to 40x compared to PGPE.
4. A comprehensive empirical evaluation of different convex relaxations under GLS with the proposed methods, demonstrating the promise of CLS-based approaches.
2
Training for Certified Robustness
Below, we first introduce the sctting of adversarial robustness before providing a background on (training for) certified ness. For a detailed notation guide see A
2.1 Adversarial Robustness
We consider neural network fo(x): X' + R", parameterized by the weights 0, that assigns a score to each class i E y given an input æ E X. This induces the classifier F: X - 3 as F(x)= == arg max; fe (z); We call F locally robust for an imput x E X if it predicts the same class y E y for all inputs in an e-neighborhood B3 = (a' E X || x'Ilp S {}. To prove that a classifier locally robust, we thus have show that F F(x') = F(x) y, Vo' (x)
Adversarial Attacks and Empirical Robustness Disproving local robustness for given input x is done by finding an adversarial ezample x' E (x) such that F(z') * F(x). The procedure of searching for adversarial examples called adversarial ottack. The most common attack methods (Goodfellow al. 2015 Madry et al., 2018) use first-order gradient information to maximize the loss function associated with x'. When such a method fails to find an adversarial example, we say that the network is empirically robust for the given input æ and perturbation radius 6.
Robustness Guarantees Local robustness is equivalent to the log-probability of the target class being greater than that of all other classes for all relevant inputs, i.e.,
min [(r',, - f(x'); > 0. e'y
(1)
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. 2023). 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(x)) to be computed:
2017).
A + bi S fo(x) S A, + bu,
(2)
for some input region (x)). From these symbolic bounds we can obtain concrete numerical bounds, usually in a layer-wise fashion, as Iy min At, x + bi,, and uy analogously, for each layer j. Hence, for the last layer m we obtain bounds for the score associated with each class Im I f(x) S um, which can in turn be used to verify Equation [
To obtain (certifiably) robust neural networks, specialized training methods are required. For a data distribution tx) D, standard training optimizes the network parametrization O to minimize the expected cross- entropy loss 6std arg ming ED(Cce(fo(z)) fx)) t)] with Lce(y,t) In (1 + E exp(y, v)). 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: Grob = arg ming Ep imaxx'eB'aa 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.
(fe((((')) (,'),,)) t)). As computing
3

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
v2 1M
(a) IBP.
(b) DeepPoly.
Figure IBP and DEEPPOLY relazations of ReLU with bounded inputs []. For DEEPPOLY the lower-bound slope À is chosen to minimize the area. between the upper and lower bounds in the input-output. space, resulting in the blue green area.
Adversarial Training optimizes a lower bound on the inner optimization objective. To this end, it first computes concrete examples x' B (x) that approximately maximize the loss term Lee and then optimizes the network parameters 0 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
allacks (Tramèr et al. 2020: Croce & Hein 2020).
Certified Training typically optimizes an upper bound on the inner maximization objective. To this end, the robust cross-entropy loss LCE.rob (x)) ( t) is computed from an upper bound I on the logit differences y : y - Yt obtained via convex relaxations as described above and then plugged into the standard cross-cntropy 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-arl certified training methods combine these bounds with adversarial training (De Palma et al. 2022 Müller
.
ct al. 2023 Mao et al. 2023a: De Palma et al.) 2024).. Throughout this work we will focus on Certified Training and Robustness Guarantees only for the -ormm, i.e., (x) {x' || x'lloc S <). as this is the most common setting in the deterministic certified defences literature. In the following, we introduce some popular convex relaxations used for neural network verification and training.
2.2
Convex Relaxations
We now discuss four popular convex relaxations of different precision, investigated in this work.
IBP Interval bound propagation (Mirman et al. 2018 Gehr et al. 2018 Gowal et al. 2018) only considers elementwise, constant bounds of the form 1 S V u. Affine layers y We b are thus also relaxed
- b We Wo+bs
[| + b,
(3)
where ||| is the elementwise absolute value. ReLU functions are relaxed by their concrete lower and upper bounds ReLU(() < ReLU(w) < ReLU((), illustrated in Figure 2a
Hybrid Box (HBox) The HBox relaxation is an instance of Hybrid Zonotope Mirman et al. 2018 which combines the exact encoding of affine transformations from the DEEPZ or Zonolope domain (Siggh et al.
2018 Wong & Kolter 2018 Weng et al. 2018 Wang al., 2018) with the simple IBP relaxation of unstable ReLUs, illustrated Figure 2a While less precise than DEEFZ, HBox ensures constant instead of linear representation size in the network depth, making its computation much more efficient.
DecpPoly DEEPPOLY, introduced by Singh et al. 20099) is mathematically identical to CROWN Zhang el al. 2018 and based on recursively deriving linear bounds of the form
A + a S v < A, a.
(4)
the outputs of every layer. While this handles affine layers exactly, ReLU layers y ReLU(v) are relaxed neuron-wise, using one of the two relaxations illustrated in Figure 2b
Au < ReLU(u) < (v u
(5)
4

---

Published in Transactions on Machine Learning Research (07/2025)
where product and division are elementwise. The lower-bound slope À ||/>>1 is chosen depending the input bounds I and u to minimize the area between the upper and lower bounds in the input-out space for each neuron separately. 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 (Zaag et al. 2020 uses the cheaper but less precise IBP bounds to compute the concrete upper- and lower-bounds u and I on ReLU inputs required for the DEEPPOLY relaxation. To compute the final bounds on the network output DEEPPOLY usod. This reduces the computational complexity from quadratic to lincar in the network depth. While CROWN-IBP not strictly more less precise than either IBP or DEEPPOLY, its precision empirically lies between the two (Jovanović et. al. 2022
Relaxation Tightness While we rarely have strict orders in tightness (only HBox is strictly tighter than IBP), we can empirically compare the tightness of different relaxations given network to analyze. Jovanović et al. (2022) propose to mcasure the tightness of relaxation 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. 2022 which agrees well with our intuition.
2.3 The Paradox of Certified Training
When training networks for robustness with convex relaxations, higher robustness achieved by sacrificing standard accuracy. Usually, more precise relaxations induce less overapproximation and thus less regularization, potentially leading to better standard and certified accuracy. However, empirically the least precise relaxation, IBP, dominates the more precise methods, e-g., DREPPOLY, with respect to both certified and standard accuracy (see the left-hand side of Figure [ This is all the more surprising given that state-of-the-at 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 el. al. 2023 Mao et. al. 2023a
De Palma et al. 2024].
Jovanović et 2022) and Lee al. (2021) explained this paradox, by showing that these more precise
relaxations induce loss landscapes suffering from discontinuities, non-smoothness, and perturbation sensitivity (a proxy for difficulty optimize with gradients), making it extraordinarily challenging for madicet-bbssed optimization methods to find good optima. Thus the key challenge of certified training is to design robust loss that combines tight bounds with a continuous, smooth, and insensitive loss landscape. In $3 we discuss these challenges in more detail and show how to overcome them.
3 Gaussian Loss Smoothing (GLS) for Certified Training
In this section, we address the optimization issues identified in 22.3 -namely, discontinuity, non-smoothness, and sensitivity of the loss surface by proposing Gaussian Loss Smoothing (GLS). We first illustrate these issues with toy examples ($3.1). highlighting how smoothing improve loss landscapes. Then, formalize this intuition in $3. showing that GLSS yields continuous, smooth, and less non-convex loss surfaces. Finally, we instantiate GLS with two optimization algorithms, PGPE ($3.3) and RGS ($3.4), which enable effective training with light (and even non-differentiable) convex relaxations.
3.1 Open Challenges: Discontinuity, Non-smoothness and Sensitivity
Recall 2.3 where we discussed the key challenges of certified training with tighter relaxations, namely discontinuity, non-smoothness, and sensitivity of the loss surface. We now illustrate these key challenges on a toy network and loss in Figure
On the left-hand side (Original in Figure 3a we show the DEEPPOLY lower bound of the one-neuron network Re + w) + for x E [- over the parameter w. As the original bound | = 1 1+ 1w20 (w - 1) is discontinuous at w = 0, gradient-based optimization method initialized at w > O will decrease w until it has moved through the discontinuity and past the local minimum.
5

---

Published in Transactions on Machine Learning Research (07/ (025)
The second key factor, non-smoothness, is originally de- fined as the variation of loss values along the optimization trajectory. For brevity, we restrict this to the Lipschitz continuity of the loss function, as a Lipschitz continuous loss function has bounded variation of loss values. A function is called Lipschitz continuous if there exists a constant L such that [f(=) (((=)-((() [(y)] - L|le - yll for all x, y. As DEEPPOLY has discontimuities, it is not Lips- chitz continuous. We remark that Lipschitz continuity is particularly important for gradient-based optimization methods, as this controls the theoretical convergence of such methods.
Looe
Loos
Ocigial
022
0.5
4-
22
0-
1
Paramese Value (w)
Pacumeter Value (56)
(a) Discontinuity.
(b) Sensitivity.
Figure 3: Illustrating the effect of Gaussian Loss
Smoothing on the discontinuity (Ieft) and sensitiv- ity of loss functions (right).
The third key factor, sensitivity, can be interpretod as the difficulty to optimize with gradients. Jovanović et al.] (2022) show that DEEPPOLY is more sensitive than IBP, thus gradient-based optimization methods are more likely to get stuck in bad local minima. We illustrate this with the toy function shown in Figure 3b Here the original function has a bad local minimum for w E [-1.5,0) that gradient- based optimizer can get stuck in. To analyze the badness of a loss surface for gradient-based optimization, we measure the deviation from converity of the loss function, defined to be D(f) := (axx..yERM\EEjo.. ölf; æ, y, A/, where 8[f: x. y. A] : (1-N)) -1--))((11)1))))))0 ()))). I function has a non-positive deviation from convexity, it is convex, thus gradient-based based met can find global optimum. Since this directly measures non-convexity, intuitively, a function with smaller deviation from convexity is casier to optimize with gradicnt-based methods. We remark that sensitivity as defined in Jovanović et al. (2022) is different to the deviation from convexity, but the two are closely related in that both indicate how difficult it is to optimize a function with gradients.
3.2 Gaussian Loss Smoothing for Certified Training
We now discuss how Gaussian Loss Smoothing can address these challenges. The central result in this section is formalized in Theorem 3.1 (proof in IB.::
Theorem 3.1. Let the parameter O E Rd. Let the nonnegative loss function L(O): Rd + R have bounded growth, that is, I.(0) exp(-100[3-o) S M for some 8 < and M > 0. Then, the loss smoothed by an isotropic Gaussian (O, o2 defined as (0) := 1e + E), is infenitely differentiable. In addition, the devialion from converily of the smoothed loss never exceed that of the original loss, that is, D(T.,) S D(T.;; equality holds iff L is an affine function. Further, assuming 0 is in a compact set throughout optimization, Lo is also Lipschitz continuous.
Theorem 3.1 shows several desired qualities of GLS. First, it shows that GLS can turn any discontinuous loss function into a continuous one that is differentiable everywhere, as visualized in Figure Ba| Second, GLS can make the loss surface Lipschitz continuous if we optimize in a compact set, thus ensuring that the loss surface is smooth. Third, GLS can help overcome the sensitivity issue since it provably reduces the deviation from convexity as long as the loss function is not affine. As we show in Figure 3b depending on the standard deviation used for smoothing, the local minimum can be reduced or removed, and the loss landscape is thus more favorable. However, the choice of standard deviation is crucial. While 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 the minima. We again illustrate this in Figure 3b There, small standard deviation of a 0.5 works properly, while o == 0.25 does not smooth out the local minimum, and a 1.0 severely misaligns the new global minimum with that of the original function. Overall, GLS has the thcoretical potential to mitigate the key issues, discontinuity, non-smoothness, and sensitivily, for light convex relaxations (as identified by Jovanović et al. 2022 and Lee et al. 2021
Empirical Confirmation To empirically confirm that GLS can mitigate discontinuity, non-smoothnes. and sensitivity, we plot the original and smoothed loss landscape (along the direction of the DEEPPOLY gradient) of different relaxations for a CNNB and different standard deviations in Figure 4 We normalize all
Josses by dividing them by their value for the unperturbed weights and estimate the expectation under GLS with sampling.
6

---

Published in Transactions on Machine Learning Research (07 2205))
Lass
Toss
1osss
Lass
1.010
1.020
1.010
1.010
IBP
CROWN-IBP
1.005
1.005
1.005
1.005
DeepPoly
1.000
1.000
1.000
1,000
0.985
0,985
0.995
0.985
0.001
1.000
0.001
-1.001
0.008
0.001
-0,001
0.000
0.101
-0.001
0.000
0.001
Eg norm of perturbation | 2
E berm of perturbttion ||8|]]
borm perturtation ||AA||
norm perturbation ||
0 (original)
(b) x 10-6
(c) 5 x 10-5
(d) σ = 5 10
Figure 4: The original and Gaussian smoothed loss for different relaxations on a PGD-trained CNN3, evaluated along the direction of the DEEPPOLY gradient. Losses are normalized by dividing them by the values at O, i.., without perturbation. The smoothed loss is estimated with 128 samples and the corresponding confidence
interval is shown as shaded.
Max Finite Difference (Disontiniity)
Average Curvature Non-Smoothhee
Deviation from Convexity (Sensitivity)
300
80-
300-
DeepPoly CROWN-IPP
130
40
150
IBP
0-
0-
0-
1x 10-9
xx 10-9
5 10
x 10-9
5x 10-5
x 10
1x 10-
5x 10-5
Gx 10-
Smoothing constant (o)
Smoothing constant (o)
Smoothing constant (o)
Figure 5: Attenuation of undesirable properties of the loss landscape under increasing smoothing strength. We analyze the loss landscape of the same CNNB as in Figure
We observe that the original loss (Figure 4ap is discontinoous, non-smooth, and highly sensitive to perturbations for both CROWN-IBP and DEEPPOLY, consistent with the findings of Jovanović et al. (0022) and Lee et al. (2021). Only the imprecise IBP loss 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 = 10-6 (Figure 4b/, the local minimum of the DEEPPOLY loss has slightly reduced sharpness but is still present. In addition, both the losses for DEEPPOLY and CROWN-IBP are still highly sensitive. This indicates that a is too small. When the standard deviation is increased to a = 5 10-5 (Figure [c), the undesirable local minimum of the DEEPPOLY loss is removed completely, and both losses become much smoother and less sensitive to perturbations. However, further increasing the standard deviation to o = 5-10- (Figure 4d), we observe almost flat losses removing the minimum present in the underlying loss, indicating that the smoothing is too strong.
Lee
Moreover, in Figure 5 we present the evolution of three scores we used as proxies for measuring the three undesirable properties of the loss landscape as we increase the smoothing strength for the same CNN3 network and settings used in Figure 4 Namely, we compute:
the maximum magnitude of finite differences defined as max
fixth) as an approximation for h
the magnitude of the discontinuities in the loss function,
the average curvature of the loss function defined as the average magnitude of the second order derivative, estimated as E.,
as measure of non-smoothesss,
the deviation from convexity- D(f) as defined in $3.1 as a proxy for sensitivity,
where f(z) represents the normalized loss function w.r.t. the weight perturbation as depicted in Figure 4 and h is the stepsize used when sampling the loss function for making the plots, roughly equal to 1/50 of the gradient update for a single step of gradient descent.
We observe that smoothing significantly reduces all of these scores for DEEPPOly and CROWN-IBP, thus mitigating the optimization issues induced by the three undesirable properties.
These results empirically confirm the observations in our toy setting and predicted by our theoretical analysis, showing that GLS mitigates the issues related to the paradox of certified training.
7

---

Published in Transactions on Machine Learning Research (07/2025)
1. Sampling Perturbations
2. Evaluating Losses
3. Estimating Gradient
Parmmeeer
Perturbed Param. 0'
Loss Decrease
PGPE Estimate
True Gradient
Figure 6: Illustration of PGPE. (1) We sample random perturbations O' (orange circles) symmetrically around the current. parameters 0 (black diamond) from a Gaussian distribution (0, (2) For each pair of perturbations, we evaluate the loss and compute directional differences (green arrows, longer arrows represent larger differences).
(3) The PGPE gradient estimate (red arrow) is computed as a sum of all sampled directions weighted by the respective observed loss differences. The result an approximation of the true gradient of the smoothed loss function (blue arrow).
Next, in $3.3 and 3.4
show how to apply GLS using PGPE and RGS, respectively. Both PGPE and RGS being estimation-basee approximations of GLS, apart from the standard deviation (o), they also require the population size (Mps) as hyperparameter to estimate the gradient.
3.3 Policy Gradients with Parameter-based Exploration (PGPE)
PGPE (Sehnke et al. 2010 is gradient-free optimization algorithm that optimizes the Gaussian Smoothed loss L. (0) = NN L(0') using a zcroth-order method, where the loss is not evaluated at a single parameterization of the network, but rather at (normal) distribution of parameterizations.
PGPE samples n = 2 weight perturbations E; ~ (O, o²), and evaluates the loss on 0 + E;, and 0 - Ei. computing r:' = L(0 + E;) and r L(O - <;). These pairs of symmetric points are then used to compute gradient estimates with respect to both the mean of the weight distribution @ and its standard deviation or: (ol. x Er r and (.)
e² where = 2. E, (r+ +r7) is called bascline loss and is the average of loss values over all 2n samples. Figure 6 visualizes such a gradient estimate. The gradient ipproximations Vol. and V. (0) are used to update the mean weights O and the slandard deviation o, respectively. By design, PGPE approximately optimizes the Gaussian smoothed loss (Sehnke
E: ( -
a
ct al. 2010
As no backward propagation is needed compute these gradient estimates, PGPE is comparable to neuro- evolution algorithms. In this context, it is among the pert-rerfo methods for supervised learning (Lange ct al. ).23). This property also allows us to apply it for training with tighter, but non-differentiable bounding methods, such as a-CROWN (Xu et al. 2020
3.4 Randomized Gradient Smoothing (RGS)
While the loss smoothing induced by the sampling procedure of PGPE leads to provably continuous and infinitely differentiable loss surface, it can be costly to compute. To reduce the training costs, we propose to approximate GLS by RGS DDuhii et al. 2012). RGS approximates the gradient of the smoothed loss by sampling ups perturbations E, ~ N and then averaging the gradients of the loss function for the perturbed network weights 6;:
VOLo α 1 [VL(O++))
(6)
Tdp
While RGS, which approximates in first-order does not provably recover in expectation the gradient of the smoothed loss when the original function is discontinuous (sce BB.). Duchi et al. (2012) have shown its empirical effectiveness, even with a tiny sample size (Npe = 2). Therefore, we apply this alternative to study the performance of GLS in larger networks, RGS requires much fewer samples than PGPE and thus scales
8

---

Published in Transactions on Machine Learning Research (07/2025)
1. Sampling Perturbations
Evalnating Gradients
3. Averaging Gradients
Parameters
Perturhed Param.
Sample Grad f0
RGS Estimate
The Grudient
Figure 7: Illustration of RGS. (1) We sample random perturbations O' (orange circles) around the current. parameters 0 (black diamond) from a Gaussian distribution N(0,)). (2) For each perturbation, we evaluate the gradient (green arrows). (3) The RGS gradient estimate (red arrow) is computed the average of the sampled gradients. The result approximates the true gradient of the smoothed loss function (blue arrow).
better. Further, contrary to before, now a hyperparameter that needs to be tuned rather than learned. A comparison of training costs is included in F.6 where RGS is shown to be up 40 times faster than PGPE.
4 Experimental Evaluation
We now extensively evaluate the effect of GLS via PGPE and RGS on the training characteristics of different relaxation methods. First, we show in $4.2 that PGPE enables training with light relaxations, even when the relaxation is not differentiable. Second, we demonstrate in $1.4 that RGS scales GLS training to deeper networks, surpassing the performance of the SOTA methods on the same network architecture in many settings. The impact of different hyperparameters on the performance of the proposed methods is studied in $C and a comparison of PGPE and RGS is provided in $ D.2 Overall, our results show that GLS can enable certified training with tight relaxations.
4.1 Experimental Setup
We implement all certified training methods in PoTorch (Paszke et al. 2019 and conduct experiments on MNIST (LeCun et al. 2010), CIFAR-10 (Krizhevsky et al.) 20099 and TINYIMAGENET (Le & Yang 2015 using loo perturbations and versions of the CNN3 and CNN5 architectures (see Table in For more details on the experimental sctting including all hyperparameters, soe $F
Standard Certified Training For standard certified training using pack-proppaation (referred below GRAD for clarity), we use similar hyperparametors in the literature and initialize all models using the IBP initialization proposed by Shii el al. (2021). In particular, we also use the Adam optimizer (Kingmia &
Ba 2015), follow their learning rate and e-annealing schedule, use the same batch size and gradient clipping threshold, and use the same e for training and certification in all settings. For the state-of-the-art methods
SABR (Müller et al. ) STAPS (Mao et al., 2023a). and MTL-IBP (De Palma et al.) 2024). we conduct an extensive optimization of their network-specific hyperparameters and only report the best results.
PGPE Training As PGPE training is computationally expensive, we initialize from an adversarially trained (PGD, (aadry et al. 2018)) model. This can be as warm-up stage is common also for other certified training methods (Shi et al. 2021 Müller et al.) 2023 Mao et al.) 2023a). We only use e-anncaling for the larger perturbation maguiludes on both MNIST and CIFAR-10 and choose the learning rate based on stability at the beginning of the training. Unless indicated otherwise, we run the PGPE algorithm with a population size nps = 256 and an initial standard deviation for weight sampling of dpGrE = 10-3
RGS Training We train our RGS models using the same hyperparameters as for GRAD training. We use population size of nue and an initial standard deviation of Ø 10-3, As RGS does not dynamically adjust the standard deviation, we choose decay at the same time steps as the learning rate. More details about the hyperparameters used can be found in

---

Published in Transactions on Machine Learning Research (07/2025)
Table 1: Comparison of the Natural, Certified and Adversarial Accuracies of CNN3 networks trained using different convex relaxations on the MNIST and CIFAR-10 datasets for different perturbation sizes (Eoo). We compare GLS-based algorithms PGPE (Sehnke et al. 2010) and RGS (Duchi et al. 2012) with the baseline approach (gradients obtained directly by backpropagation GRAD). We use the state-of-the-art method
MN-BAB (Ferrari et al. 2022 for certification.
Convex Relaxation
Natural Accuracy
[6]
Certified Accuracy [%
Adversarial Accuracy [%]
Datasct
GRAD
PGPE
RGS
GRAD
PGPE
RGS
GRAD
PGPE
RGS
IBP
96.02
94.52
96.13
91.23
87.02
91.77
91.23
87.03
91.77
HBox
94.79
96.12
95.52
88.18
90.57
90.13
88.18
90.58
90.15
0.1
CROWN-IBP
94.33
96.69
96.74
88.76
90.23
91.05
88.77
90.25
91.10
DEEPPOLY
95.95
97.44
97.37
90.04
91.53
91.88
90.08
91.79
92.03
MNIST
IBP
91.02
89.16
91.99
77.23
74.00
77.07
77.27
74.08
77.15
HBox
83.75
86.58
83.81
57.86
70.52
G8.37
57.92
70.66
58.69
0.3
CROWN-IBP
86.97
90.57
88.86
70.55
71.95
71.91
70.56
72.24
71.94
DEEPPOLY
85.70
91.05
88.51
66.69
74.28
71.36
66.70
74.98
71.49
IBP 44.49
48.05
44.55
34.09
37.28
37.70
34.10
37.28
2/255
CROWN-IBP
51.19
53.74
35.75
37.51
41.00
35.75
37.65
DEEPPOtY
47.70
54.17
54.93
36.72 72
38.95
41.14
36.72
40.20
42.03
CIFAR-10
IBP
34.63
30.48
33.23
25.72
21.75
24.56
25.74
21.75
24.58
8/255
CROWN-IBP
31.60
32.36
35.17
22.66
21.40
23.92
22.66
21.42
24.18
DEEPPOLY
33.06
31.37
35.61
22.97
22.19
23.81
22.98
22.19
24.21
Certification We use the state-of-the-art complete verification method MN-BAB (Ferrari et al. 2022 with the same settings as used by Mūller et al. (2023) for all networks independently of the training mothod. We note that this is in contrast. to Jovanović al. (2022) who used the same relaxation for training and verification. By doing this, aim to assess true robustness regardless of the tightness of different relaxations.
4.2 GLS Enables Training with Tight Relaxations
We first compare the performance of training with various differentiable convex relaxations using cither standard backpropagation (GRAD) or GLS-based methods (PGPE and RGS). The result is shown in Table !I
GRAD Training We train the same CNNB 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, confirming the paradox of certified training. Specifically, HBox, CROWN-IBP, and DEEpPoLY tend to perform similarly, with CROWN-IBP being significantly better at MNIST = 0.3, indicating that when the loss is discontimouss non-smooth and sensitive, tightness of the training relaxation is less relevant.
PGPE Training Training the same CNN3 with PGPE in the same settings observe that the performance ranking changes significantly (see Table [] Now, training with IBP performs strictly worse than training with DEEPPOLY across all datasets and perturbation sizes. In fact, the more precise DEEPPOLY bounds now yield the best certified accuracy across all settings, even outperforming GRAD-based training methods at low perturbation radii. Interestingly, IBP still yields better certified accuracy at large perturbation radii than HBox and CROWN-IBP, although at significantly worse natural accuracics. This is likely because more severe regularization is required in these settings. For a more detailed discussion on the issue of certified training for large perturbations see
While DEEPPOLY + PGPE outperforms DEEPPOLY + GRAD in almost all scttings in Table 1 on the same network architecture, sometimes by a wide margin, it does not reach the general SOTA results of classic and heavily optimized GRAD training methods. We believe this is caused by three key factors: First, PGPE computes a gradient approximation would need the population size Mps to be twice the number of network parameters, which computationally intracable even for small networks. Thus, we only get low-dimensional gradient approximations, slowing
Pp din-iinnsionnal subspace. To cover the full parameter space, we 2
an
10

---

Published in Transactions on Machine Learning Research (07/2025)
down training (sce Table and Figure 9 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. Finally, PGsEE-ased certified training is less optimized, compared to standard certified training which has
been extensively optimized over the past years (Shi et al. 2021 Müller et al. 2023 De Palma et al. 2024).
RGS training When applying RGS training to the same CNN3 architecture, we observe that RGS significantly improves the performace of training with tighter relaxations in all settings. In particular, DEEPPOLY + RGS outperforms all other methods in the case of small perturbations, while IBP-GRAD is still the best method for large perturbations. We note that this is potentially because RGS, as a first-order approximation of GLS, does not necessarily enjoy the continuity that GLS brings. Still, the performance improvements point loward the potential of RGS to alleviate the issues of light relaxations, while also being able to scale to deeper networks, as we show in $..4
Takeaway: GT.S-based methods like PGPE and RGS enable effective training with tight convex relaxations, overcoming the paradox where looser bounds (e.g, IBP) typically outperform tighter ones. PGPE boosts certified accuracy with DeepPoly but is limited by its costly and imperfect gradient estimation, while RGS offers scalable improvements, especially for small perturbations, highlighting GLS's potential for stable and tight certified training.
4.3 PGPE enables non non-differentiable relaxations
Nexi, we show that PGPE has a unique benefit in that it allows training with non-differentiable relaxations, which we demonstrate by training with the non-differentiable a-CROWN relaxation. Since a-CROWN is even more expensive than DREPPOLY, we train it with a smaller version of CNN3 called CNN3-tiny and set the number of iterations in a-CROWN slope optimization to be merely 1. Table shows that training with G-CROWN-PGPE further improves the certified accuracy compared to training with DEEPPOLY-PGPE. This confirms that PGPE can be used to train with non-differentiable relaxations, resulting in even better trade-offs. We remark that PGPE is not limited to a-CROWN, but can be used with any non-differentiable relaxation, including those relying on branch and bound-basee procedures or multi-neuron constraints. Although these methods are computationally expensive and thus may be only applied in training small networks, they are partieularly useful in safely-critica applications such as aircraft control {Owen et. al.) 2019 embedded medical devices (Shoeb et al. 2009) where models are usually even smaller.
Table 2: Accuracies of CNN3- tiny on MNIST 0.1 trained with different algorithms.
Method
Nat. [%]
Cert. [%]]
Adv. [%6]
IBP-GRAD DEEPPOLY-GRAD
89.76
82.46
82. 18
91.27
82.04
82.05
DEEPPOLY-PGPP
91.94
85.00
85.04
a-CROWN.PGPE 92.15
85.15
85.17
4.4
RGS Scales GLS Training
We have demonstrated the empirical advantages of GLS instantiated with PGPE However, as PGPE is computationally expensive and limited to small models, more scalable methods are required to train larger networks. In this section, we extensively evaluate RGS, showing that its efficiency allows to scale to larger models, surpassing the performance of the SOTA methods on the same network architecture standard evaluation settings when 6oo is relatively small.
RGS overcomes the low-rank gradient and computational cost issues of PGPE: even with a small population size (hence low training costs), we obtain full-rank gradient approximations, enabling faster and better optimization and allowing us even scale our experiments to TINYIMAGENET. We analyze the results of training with RGS on the CNNS and CNNS-L (a wider version of CNNS) architectures and compare them with IBP and the SOTA GRAD-based methods (Mao et al., 2024] trained on CNN7 in Table 3 Encouragingly, RGS significantly boosts the performance of DEEPPOLY training. We observe that DEEPPOLY + RGS dominates all other methods, substantially improving even over state-of-the-art GRADebased methods with hyperparameters fine-tuned on CNN5 and CNN5-L. L. Further, the performance of DEEPPOLY + RGS on the small CNNS becomes comparable the performance of GRAD-IBP on the much larger CNN7 architecture used by recent SOTA methods, and the C L trained with DEEPPOLY-ROE exceeds the performance of CNN7 trained with IBP by large margin. These results agree well with our expectation that bound tightness becomes
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 3: Comparison between networks trained with DEEPPOLY-RGS, CROWN-IBP-RGS and SOTA GRAD methods on small perturbation settings. The best performance for each datasct and architecture is highlighted. Numbers in italic represent results for GRAD methods obtained on the SOTA CNN7 architecture, which is more than 10 times larger than the CNN5 and CNNS-L architectures.
Network (params.)
Nat. Acc.
Cert. Acc.
Adv. Acc.
Dataset
Method
[6
[%6]
[%]]
IBP
97.94
95.82
95.83
SABR
98.81
96.28
96.31
STAPS
98.74
96.05
96.09
CNNS (166K)
MTL-IBP
98.74
96.25
96.29
CROWN-IBP
98.19
95.42
95.42
CROWN-IBP-RGS
98.43
95.64
95.65
MNIST
DEEPPOLY
98.50
95.95
95.97
Coo 0.1
DEEPPOLY-RGS
98.97
97.15
97.16
CNN5-L
MTL-IBP
98.91
97.17
97.33
(1225M)
DEEPPOLY-RGS
99.21
97.61
97.76
CNN7
IBP
98.87
98.26
98.27
(13.3M)
TAPS
99.16
98.52
98.58
IBP
54.92
45.36
45.36
SABR
66.73
52.11
52.55
MTL-IBP
67.03
53.81
55.18
CNNS
CROWN-IBP
60.91
49.45
49.68
(281K)
CROWN-IBP-RGS
63.22
50.73
51,18
CIFAR-10
DEEPPOLY
65.43
53.16
54.10
2/255
DEEPPOLY-RGS
67.88
54.91
56.12
CNNS-L
MTL-IBP
70.60
56.36
59.05
(1.25M)
DEEPPOLY-RGS
72.64
59.34
61.23
CNN7
IBP
67.49
55.99
56.10
(17.2M)
MTL--BB
78.82
64-41
67.69
IBP
19.55
13.92
13.93
MTL-IBP
26.92
18.07
18.16
CNNS
CROWN-IBP-LF
21.91
16.43
16.43
TINYEMACEEET
(1.17M)
CROWN-IBP-LF-BR
22.97
16.89
16.89
Foo 1/255
DEEPPOLY-RGS
27.84
19.73
20.40
CNN7
IBP
26.77
19.82
19.84
(17.3M)
MTL-IBP
35.97
27.73
28.49
increasingly important with network depth, as overapproximation errors can grow exponentially with depth (Shi et al. 2021; Muller et al.) 2023 Mao et al.) 2023b). We remark that scaling DEEPPOLy-RGS to CNN7 used by the SOTA methods still infeasible due to the high computational cost of evaluating DEEPPOLY (RGS only doubles the cost!), but we show that RGS can still be used with the cheaper CROWN-IBP relaxation this architecture in Table in D.1
4.5 RGS Training in Large Perturbation Settings
In Table we provide experimental data for training CNN5 networks using DREPPOLY + RGS. We observe that while DEEPPOLY + RGS manages obtain similar natural accuracics with gradient-based IBP, the certified accuracies are significantly lower. This is likely because gain certifiability for the large epsilon settings the networks require stronger regularisation than the DEEPPOLY relaxation can provide.
This is in agreement with the findings of Mao et al. (2044), which after extensive hyperparameter tuning, show that IBP trained networks can obtain very close performance to SOTA methods in the large perturbation settings. For example, while the SOTA method, MTL-IBP, improves IBP by more than 10% for CIFAR-10, 2/255, merely improves IBP by 0.13% for CIFAR-10, c 8/255, representing a roughly 100x reduction in relative improvement. We observe a similar pattern our experiments with standard certified training methods CNNS. A more detailed discussion can be found in
12

---

Published in Transactions on Machine Learning Research (07/2025)
Table 4: Accuracies CNN5 depending on training method.
Dataset
Method
Nat. [%]]
Cert. [%]]
Adv. [%]]
IBP (used init)
94.95
87.71
87.80
SABR
97.78
88.26
89.33
MNIST
MTL-IBP
97.08
88.68
88.95
= 0.3
DREPPOLY-RGS
95.79
87.04
87.17
DEEPPOLY-RGS (IBP)
95.47
88.69
88.79
IBP (used init)
41.05
29.12
29.14
SABR
43.30
29.50
29.55
CIFAR-10
MTL-IBP
44.53
29.62
29.73
60o = 8/255
DEEPPOLY-RGS DEEPPOLY-RGS (IBP)
40.10
25.25
25.93
41.66
29.25
29.31
To verily that training with lighter relaxations can still yield improvements in the large perturbation settings, we initialize the CNN5 networks with IBP-trained weights and further train them with DEEPPOLY + RGS. The results are shown in Table 4 denoted by DEEPPOLY-RGE (IBP). We observe that training with DEEPPOLY RGS increases both natural and certified accuracies when compared to the IBP-trained initialization, with certified accuracy reaching similar level with MTL.-BBP on MNIST 0.3. However, on CIFAR-10 8/255, this is still weaker than the SOTA MTL-IBP, although it strictly improves over IBP. This demonstrates the ability of tighter relaxations to still improve training in the large perturbation settings, but more work is needed to surpass the performance of SOTA methods.
5 Discussion and Limitations
This work shows the promise of Gaussian Loss Smoothing (GLS) to enable certified training with tight relaxations. PGPE and RGS, our proposed methods implementing GLS, achieve strong performance empirically. However, there several limitations and challenges that need to be addressed in future work. First, GLS provably mitigates the discontinuity, non-smoothness, and perturbation sensitivity issues identified, but it is unknown whether these are all the factors contribuling the paradox of certified training. Future work should investigate other potential factors and how they can be addressed. Second, while our methods achieve strong performance, they are computationally expensive. Future work should focus on more computationally efficient smoothing approaches. Finally, we present a first step towards training with tight relaxations, but our methods could be further optimized, similar how IBP-based methods have been optimized over the years. Overall, our work opens up new direction for certified training using tight relaxations, and we hope it will inspire futurr work in this area.
6 Related Work
To guarantee robustness of neural networks, two main approaches have been proposed. Randomized smoothing
(Cohen et al.] 2019 Salman et al. 2019 2020 Jeong et al. 2021 Horváth et al. 2022 Vaishnavi et al. 2022:
Jeong et al. 2023 Sun et al. 2024 applies random pertur bation on the input and draw statistical robustness
guarantees on the smoothed classifier. To provide deterministic guaranteos, convex relaxations of the neural
network are commonly adopted (Mirman al. 2018 Wong al. 2018 Singh et al.) 2018
Zhang al. 2018
Singh et al. 2019). These methods are limited in completeness (Mirman et al. 2022
Baader et al.
2024
Mao et al. 2025 thus the most effective certification algorithms combine
wwwtnnchhan--boute with convex
relaxations to yield complete certification (Bunel et al. 2020 Xu et al. 2021 Wang et al.
2021 Ferrari
el al.
2022 However, these methods are computationally expensive and do not scale well to large networks.
Thus, neural networks tailored for certification have been widely studied (Gowal et al.] 2018
Balunvvćć &
Vechev 2020 Zhang et al. 2020; [Shi et al., [021] De Palma et al., [0222 Müller al., 2023 Mao al.
2023a De Palma al.) 2024).. Surprising phenomena, however, have been observed when training certified
models, where the performance of certified models trained with more accurate bounds may not exceed that.
13

---

Published in Transactions on Machine Learning Research (07/2025)
of models trained with less accurate bounds. While some reasons have been identified (Jovanovié et al. 2022 Lee et al. (021), it is not yet clear how to solve this issue. This work examines whether solving the identified optimization difficulties can help solve this problem.
7
Conclusion
This work shows that the three issues contributing to the paradox of certified training identified by prior works, namely discontinuily, non-smoothness, and perturbation sensitivity, can be mitigated by Gaussian Loss Smoothing (GLS), based on sound theoretical analyses. We instantiate GLS with two methods: Policy Gradients with Parameter-based Exploration (PGPE) and Randomized Gradient Smoothing (RGS). Empirically, we demonstrate that both improve training with light. relaxations, presenting solid step towards overcoming the paradox. Further, we show that both methods have unique advantages: PGPE allows training with non-differentiable relaxations, while RGS scales better. Our results confirm the importance of loss continuity, smoothness, and insensitivity in certified training, and pave the way for future work to leverage tighter relaxations for certified training.
Reproducibility Statement
We release the complete code used for our experiments at detailed description of the experimental setup and hyperparameters provided in F
A
Acknowledgements
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).
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 Europcan Commission. Neither the Europcan 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).
References
Maximilian Baader, Mark Niklas Mueller, Yuhao Mao, and Martin Vechev. Expressivity of reetoorsss under convex relaxations. In Proc. ICLR, 2024.
Mislav Balunović and Martin T. Vochev. Advorsarial training and provable defenses: Bridging the gap. In Proc. of ICLR, 2020.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Proc of ECML PKDD, 2013. doi: 10.1007 111007/978-3-442-00000
25.
Christopher Brix, Mark Niklas Müller, Stanley Bak, Taylor T. Johnson, and Changliu Liu. First three years of the international verification of neural networks competition (VNN-COMP). CoRR, Abs/2330.00581. 2023. doi: 10.48550/ ARXIV.2222 RTT.V/2211...2 2301.05815.
Rudy Bunel, Oliver Hinder, Srinadh Bhojanapalli, and Krishnamurthy Dvijotham. An efficient nonconvex reformulation of stagewise convex optimization problems. In Proc. of NewrIPS, 2020.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized sinothing. In Proc. of ICML, 2019.
14

---

Published in Transactions on Machine Learning Research (07/2025)
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In Proc. of TCML, 2020.
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M. Pawan Kumar, and Robert Stanforth. IBP regularization for verified adversarial robustness via aranch-and-bound. ArXiv preprint, 149/2206.14772, 2022.
Alessandro De Palma, Rudy R Bunel, Krishnamurthy Dj Dvijotham, M. Pawan Kumar, Robert Stanforth, and Alessio Lomuscio. Expressive losses for verified robustness via convex combinations. Tn Proc. of ICLR, 2024.
John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright, Randomized smoothing for stochastic optimiza- tion, 2012.
Claudio Ferrari, Mark Niklas Müller, Nikola Jovanović, and Martin T. Vechev. Complete verification via multi-neuron relaxation guided branch-and-bowe bound. In Proc. of ICLR, 2022.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving gencralization. arXiv preprint arXi:20010.044 2020.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. A12: safety and robustness certification of neural networks with abstract interpretation. In Proc. of SUP, 2018. doi:
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. Proc. of ICLR, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint, abs/1810.12715, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proc. of ICCV, 2015. doi: 10.1109/ICCO TC0.///CCV.20..1222 2015.123.
Miklós Z. Horváth, Mark Niklas Müller, Marc Fischer, and Martin T. Vechev. Boosting randomized smoothing with variance reduced classifiers. In ICLR. OpenReview.neg 2022.
Jongheon Jeong, Sejun Park, Minkyu Kim, Bleung-Chang Lee, Do-Guk Kim, and Jinwoo Shin. Smoothmix: Training confiddence-calibrateed smoothed classifiers for certified robustness. In NewrIPS, pp. 53-331688, 2021.
Jongheon Jeong, Seojin Kim, and Jinwoo Shin. Confidence-aware training of smoothed classifiers for certified robustness. AAAI, pp. 8005-8013. AAAI Press, 2023.
Nikola Jovanović, Mislav Bahunović, Maximilian Baader, and Martin T. Vechev. On the paradox of certified training, Trans. Mach. Learn. Res., 2022.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient. SMT solver for verifying deep neural networks. ArXiv preprint, abs/1702.01133, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), Proc. of ICLR, 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Robert Tjarko Lange, Yujin Tang, and Yingtao Tian. Neurocvobench: Benchmarking evolutionary optimizers for deep learning applications. In Proc. of NearIPS Dainsels and Benchmarks Truck, 2023.
Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. CS 231N, (7), 2015.
15

---

Published in Transactions on Machine Learning Research (07/2025)
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Lobs [Online]. Available: htlp://yann. http://yann.leun..com lecan. wecun.com/eeti com/erab//////////eo///eo hte//erbb//iiist,, 2010.
Sungyoon Lee, Woojin Lee, Jinseong Park, and Jaewook Lee. Towards better understanding of training certifiably robust. models against adversarial examples. In NewrIPS, pp- 953-964, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proc. of ICLR, 2018.
Yuhao Mao, Mark Niklas Mueller, Marc Fischer, and Martin Vechev. Connecting certified and adversarial training. In Proc. of NeurIPS, 2023a.
Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin T. Vechev. Understanding certified training with interval bound propagation. CoRR, abs/2306.10422 2023b. doi: (0.46550/ARXIV.22
Yuhao Mao, Stefan Balauca, and Martin Vechov. Ctbench: A library and benchmark for cortified training. arXiv preprinl (0.e:24060,4888, 2024.
Yuhao Mao, Yani Zhang, and Martin Vechev. On the expressiveness of URL
convex relaxations, 2025.
06816
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract. interpretation for provably robust neural networks. In Jennifer G. Dy and Andreas Krause (eds.), Proc. of ICML, 2018.
Matthew Mirman, Maximilian Baader, and Martin T. Vechev. The fundamental limits of neural networks for interval certified robustness. Trans. Mach. Learn. Res., 2022.
Mark Niklas Mülerr, Franziska Eckert, Mare Fischer, and Martin T. Vechev, Certified training: Small boxes are all you need. In Proc. of ICLR, 2023.
Michael P Owen, Adam Panken, Robert Moss, Luis Alvarcz, and Charles Loeper. Acas xu: Integrated collision avoidance and detect and avoid capability for uas. In 2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC), pp. 1-10. IEEE, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca. Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, pirf-peeformance deep learning library. In Proc. of NewrlPS, 2019.
Hadi Salman, Jerry Li, Nya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Proc. of NewrIPS, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J. Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. In NewrIPS, 2020.
Frank Schnke, Christian Osendorfer, Thomas Rücksticß, Alex Graves, Jan Peters, and Jürgen Schmidhuber. Sarameter-exploring policy gradients. Nearal Networks, 2010. doi: 10.101//JNEUNETT 22000. 12.0044
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast certified robust training with short warmup. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Proc. of NewrIPS, 2021.
Ali Shoeb, Dave Carlson, Eric Panken, and Timothy Denison. A micropower support vector machine based seizure detection architecture for embedded medical devices. In 2009 Annual International Conference of the IEEE Engineering in Medicine and Biology Society, pp. 1202-4205. IEEE, 2009.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev, Fast and effective robustness certification. In Proc. of NeurlPS, 2018
16

---

Published in Transactions on Machine Learning Research (07/2025)
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. An abstract domain for certifying neural networks. Proc. of POPL, 2019. doi: 4/1453249344.
Andrew Starnes, Anton Dereventsov, and Clayton Webster. Gaussian smoothing gradient descent for minimizing high-dimensional non-convex functions, 2023.
Chenhao Sun, Yuhao Mao, Mark Niklas Müller, and Martin T. Vechev. Average certified radius a poor metric for randomized smoothing. CoRR, abs/2410.06895, 2024.
Christian Szegedy, Wojciech Zaremba, Tlya Sutskever, Joan Bruna, Dumitru Erhan, Tan J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Proc. of ICLR, 2014.
Florian Tramér, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Proc. of NeurIPS, 2020.
Pratik Vaishnavi, Kevin Eykholt, and Amir Rahmati. Accelerating certified robustness training via knowledge transfer. In NewrIPS, 2022.
Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Proc. of NewrIPS, 2018.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsich, and J. Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In Proc. of NewrIPS, 2021.
Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane S. Boning, and Inderjit S. Dhillon. Towards fast computation of certified robustness for relu networks. In Proc. of ICML, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proc. of ICML, 2018.
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. Proc. of NewrIPS, 2018.
Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. arXiv preprint arXin:2011.1882 2020.
Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. In Proc. of ICLR, 2021.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neural wetwork robustness certification with general activation functions. In Proc. of NewrlPS, 2018
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane S. Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. Proc. of ICLR, 2020.
Huan Zhang, Shiqi Wang. Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsich, and J. Zico Kolter. General cutting planes for bound-propagation--eeed neural network verification. ArXio preprind, Abs/2228.005740 2022.
17

---

Published in Transactions on Machine Learning Research (07 (025)
A
Notation
We use the following notation throughout this work:
x E C Rd: Input vector to the neural network, assumed lie an input domain X.
y= [l....,m]. n): Set of class labels for n-class classification task.
fo(x) E :": Neural network output (logits) for imput a, parameterized by weights 0.
F(x) arg max; fo(x);; Induced classifier assigning input æ the class with the highest logit.
(p))) (a' X | z'Ipp S c): Closed bp-ball of radius centered at æ, representing the set of admissible perturbations.
t) Eife exp(y: n) Cross-cntropy loss expressed in terms of the logit differences. u, Lower and upper bounds on intermediate or output activations, typically obtained via convex relaxations.
A,, by and Au, b.: Coefficients defining affine lower and upper bounds on fe(æ) over the perturbation region.
y Me Logit difference vector between logits y and the target class yt-
y Upper bound on the logit differencos, used to compute the robust loss in certified training.
0 E RR; Parameter vector of the model.
L(O): gd I: Original (possibly non-smooth or discontinuous) loss function.
N(0, I) W(0, 0²): Isotropic Gaussian distribution with zero mean and standard deviation a (scalar).
N(O, oI); Anisotropic Gaussian distribution with zero mean and standard deviation o (vector).
e~ c~,,(0,02)), Gaussian noise vector used for smoothing.
(0) = Le L( e): Gaussian smoothed version of the loss.
D(f): Deviation from convexity function f, defined as D(f) max [f(x + (1 A)y) >z x)f()))
L-Lipschitz continuity: A function f is Lipschitz continuous if 3L > 0 s.t. [f(x) - f(y) L|( yl for
all x.
ReLU(-): Rectified Linear Unit activation function.
100: Indicator function that is 1 if and otherwise.
((+h))- h
f(x); Finite difference approximation used to estimate discontinuity magnitude.
f(x-h) 2 f()+h), Sccond-order finite difference used to estimate curvature (non-smoothness).
b²
o, OrGPE, dRaS: Standard deviation of Gaussian used in GLS. A vector in the case of PGPE, a scalar hyperparameter for RGS.
Nps: Population size used in sampling- based GLS estimators (e.g., PGPE, RGS).
Unless otherwise noted, we focus on robustness with respect to the lo norm, i.c., B (x) (x' X' ||ær 2'1oo {)).
18

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
B
Theoretical Power of GLS
B.1 Proofs
Throughout proof, will denote the probability density function of the Gaussian distribution N/O, o² Po (x)). A ball of radius r is defined B(r)= = (ær ||=||| S <r.. Without explicit mention, the norms are T22 norm.
Lemma B.1. Assume the eristence of the smoothed loss function. Gaussion Loss Smoothing is equivalent to
performing convolution of the loss function with Gaussian kernel, that is, Lo (o = [[ +L (0).
Proof. Remember that (0) == Be [(0 + 6). Let x = O + and use Po(E) Po (-(-)) due to symmetry, we have
L (0) 11
-/1 I(0 + ())po(Edde
Jed L(0 + =))o
| Po ())(d)
(7)
JRd
[L* (0).
Proposition B.2. Assume the nonnegative loss function L(0): RR + R have bounded growth, that is, I((0) exp(-10) s M for some 5 and M 0. Then, La erists and infinitely differentiable.
Proof. We prove existence of Lo first. Equation 7 shows that this is equivalent prove the convergence of the integral. Given fixed 0, Po (0 x)) exp( 2 ||= 01l²), thus Ea, B1, Mi >> O, such that pa ax) S an exp(-3; ||||² (2) when ||>||| > M1. Therefore,
J R.)B(M))) Po L<))d
{ a1 (xp(--11|=]) [1=]) (<x)d
(R(M((M))
J a exp(__),11 M cxp() - 2-15 ddx
$ ai exp(-311|<11 + ||>||| | 2-6 )dk.
JRMBB(M)
Further, 332 > M2 2 Mj, such that exp(- [ + 2| < exp( exp(-82llx((8/)) when Therefore,
|
> M2.
J Po 1 (x)))
< aM
exp(-3illar) + | 2- - dak
(20BB(M))
(EEA exp( (
5 SaiM
19

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Note that exp(-&a||z))) decays faster than || and (LLNB(M, [T] is bounded. Thus, Ve 0, 3M3 2 M2, such that (gn Po Lx))d < c. Therefore, Lo exists.
Now we turn to its derivative. Using Lemma B.1 and (f*g) (f*g') we know that any n-th (partial)
derivative of Lg is L* ă. where )(m) x is shorthand for the related variables. Since n-th partial derivative of a Gaussian pdf is a polynomial (Hermite polynomials) times a Gaussian pdf, we can bound it similarly to under appropriate on, 01,31,40 M1.
a(") pe with o1 exp( 91 [|=]|?) Bini
what we have done before, as we can still bound Therefore, Lo is infinitely differentiable.
Lemma B.3. f is continuously differentiable, then f Lipschitz continuous within a compact set.
Proof. Since f has continuous first-order derivative, it suffices show that the first-order gradients are bounded. This is trivial as continuous function is bounded within any compact set.
Proposition B.4. Assume J * g exists, where g probability densily function. Then, the devialion from converity of f g is smaller than equal to the deviation from converity of f, that is, D(f 9) S D(f). Equality holds iff f is an affine function.
Proof.
8lf * gg:.,y,, f g(Ax (1 A)y) Af g(()) - (1 A)f * g(v)
f [f(Xx + +1- z) Af(00 2) (1 1-)a((y =))
gd
/ 81f;x - 2, 2, Alo(z)dzz
8ffix, | g(2)dz
max =.y0R4-XEj0.1
D(f) [ g(2)dz
D(f),
where we used the fact that g is a probability density function, thus Jge g(2)d2 1. The above equality holds iff olf; x. y, A] constant function. Therefore, DJ * g) maxx o * g æ. y, A] D(f). Note that to take equality, it is necessary that 8 g; xc y: A] DJJ) for some ar, y, X, thus 8[J; y, A| still has to be a constant function. On the other hand, if ff x. y, X] is constant function, then oif * gi x, y, Xj = D(f) for all x. U, X, thus D(f g) = D(f). Therefore, D(f
= D(f) iff ōlf: x. y. A] is a constant function.
Now we show that æz y, A] is a constant function iff f is an affine function. If ʃ is an affine function, then f x, y, ^| = [Ax + (1 - A)y) - >f(x) - (1 - )))(() = O, thus o[f; x. y, >] is a constant function. On constant function, then 3C such that 8[f; x. y, A] = for all x, y, Let y = 0, then C f(0) - ((0) 0, thus s(xæ (1 A)y) (z)) (1 A))(y) for all a. y, A. This mcans is affine function.
the other hand, if 6ff; xx y. X]
R. have bounded growth, that. is, L(0) exp(-1011=6) < M for some 8 < 2 and M > 0. Then, the loss smoothed by isotropic Gaussian, N(0 I)),, defined as (0) == Fe-NN(..=-) + c), is infinitely differentiable. In addition, the deviation from converity of the smoothed loss never exceed that of the original loss, that is, D(Lo) < D(L); equality holds iff L is an affine function. Further, assuming is in a compact set throughout optimization, T. is also Läpschitz continuous.
Thcorem 3.1. Let the parameter 0 Rdd. Let the nonnegative loss function L(0) : Rd
Proof. By Proposition B.2, Lo exists and is infinitely diffcrentiable. Further, by Lemma B.1 and Propo- sition B.4 (La) S D(L; equality holds iff L an affine function. Assuming 0 is in a compact set, by Lemma B33 Lag is Lipschitz continuous.
20

---

Published in Transactions on Machine Learning Research (07 (07/2025)
DEEPPOLY Loss
ups 512
Aps 128
7ps 32
raw
0.001
0.000
0.001
fo-norm of weight perturbation ||
Figure 8: Effect of the population size Aps on the smoothness of the induced loss surface in PGPE. Note that the 5 plots have been spaced by artificially adding offsets the y-axis. This should not be regarded as quantitative plot ordering the magnitude of the loss, but rather qualitative comparison of the smoothness induced by sampling with different population sizes.
B.2 Alignment of Local and Global Minima under Gaussian Loss Smoothing
Without loss of generality, we consider a quantized function f(x) = -'= [a (a E [be, b++1)), where is the threshold function and -oo = by S b1 S ... I bn & ba+1 +00. The global minimum of this function is min, 0g achieved by [b.,, 41 where i* E arg min; a, Now, the derivative of its Gaussian smoothod loss is (x) Ei=(( a:-1) ((-1))((;-))) ") where p the p.d.f. of the standard normal distribution. One may immediately find that the minimum of the smoothed loss is scale-invariant: the minimum of fex(cz) with b scaled by is the same the minimum of (x). Therefore, if we increase to smoothen fixed function, shallower minima with smaller widths will be smoothed out one by one. Taking to co, we find that the derivative converges to zero, making the smoothed loss a constant function.
+00.
We use the same quantized function to study the effect smoothing has on the alignment of minimum points. As observed before, when we take a oo, the derivative on the whole domain converges to zero, so every point becomes a minimum, therefore we fail get proper alignment. On the other hand, by taking o zero, the factor p( (x=²) becomes Dirac delta function 5(x by), thus every point except the boundary points becomes local minimum, and we get the aligument. of global minima. Based on these intuitions, one can pick a a such that narrow local minima get smoothed out, and wide local minima are left close to their original locations, thus the optimization process can be guided towards the global minimum.
B.3 Properties of Randomized Gradient Smoothing
Discontinuity Considering again the quantized function defined in (B.2) observe that the derivative of the original function is zero almost everywhere, so the smoothed gradient estimated by RGS will also be zero. This means that RGS may fail to find the minimum of certain discontinuous functions in general. However, in practice we rarely work with quantized loss functions we used for the analysis; instead, we can model the discontinuous loss function as h(x)) = ((x) + g(x), where (x) is discontinuous like the quantized function and g(x) is continuous. thus the RGS algorithm will converge to the same locations when optimizing as when optimizing g. If the expect RGS to find a good minimun of h.
this case, the derivative of h is equal to the derivative of g almost everywhere, and
minima of y and h are sufficiently aligned,
Higher Dimensions In higher dimensions, however, the behavior of RGS becomes unpredictable, as not every discontinuous function h can be decomposed into a continuous function g and a quantized function f (c.g. h(1, 22) 21 sign (æ2) consists two plane sections soparated by discontinuity along the z -axis).. In this case, the equivalent loss landscape that the RGS algorithm is optimizing strongly dependent on the optimization path and the starting point and therefore cannot. be defined.
21

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
C Ablation Studies
C.1 Population Size
While PGPE recovers Gaussian Loss Smoothing in expectation, the quality of the gradient approximation depends strongly the population size ups- In particular, a small population size Ups induces a high-variance estimate of the true smoothed loss, leading to noisy gradient estimates and thus slow learning even stability issues. We illustrate this in Figure g 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 "ps = 512. Additionally, PGPE computes gradient approximation in an "gg -i-dimensional subspace, thus further increasing gradient variance Ups is (too) small compared to the number of network parameters.
2
027 Low
Table 5: Effect of the population size Ups on accuracy and training time with PGPE + DEEPPOLY training CNN3.
250
Popsize
Nat. [%]
Cert. [%]
GPU h
Init
97.14
94.02
025
100
Epuech
64
97.22
94.07
88
128
97.22
94.13
Figure 9: Evolution of Train Loss during training with different values for popsize ups. Note that for Rps = 64 we trained with a lower learning rate because the value used in the other settings would make training unstable.
256
97.30
94.19
304
512
97.27
94.22
596
1024
97.43
94.50
1192
To assess the effect this has on the performance of PGPE training, we train the same CNNB on MNIST using population sizes between 64 and 1024, presenting results in Table 5 We observe that performance does indeed improve significantly with increasing population sizes (note the relative performance compared initialization). This becomes even more pronounced when considering the training dynamics (see Figure g Unfortunately, the computational cost of PGPE is significant and scales linearly in the population size. We thus choose 7ps 256 for all of our main experiments, this already leads to training times of more than week on 8 T.4 GPUs for some experiments.
Train Dynamics when varying population size In Figure we present the evolution of the Training Loss during training with different values for popsize Rps- We observe significantly slower training we decrease Taa, confirming the theoretical prediction that using lower popsize decreases the quality of gradient estimations due to increased variance in the -ass-salling process.
C.2 Standard Deviation
The standard deviation a used for Gaussian Loss Smoothing has a significant impact on the resulting loss surface as we illustrated in Figure ! and discussed in $3 If a 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, a 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 Nps. the standard deviation øPGPE additionally affects the variance of the loss and thus gradient estimate. We illustrate this in Figure 10 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 dPGPE relative to the chosen population sizes nps-
To assess the effect this practically has on PGPE training. we train for 50 epochs with different standard deviations dPGPE and present the results in Figure [I As expected, we clearly observe that both too small and too large standard deviations lead to poor performance. However, and perhaps surprisingly, find that
22

---

Published in Transactions on Machine Learning Research (07 (07/2025)
training performance is relatively insensitive to the exact standard deviation as long are in the right order of magnitude between 10 and 10-2.
DEEPPOLY Loss
Loss
10-1
1.21
Train Loss
x 10
0.5
Val Loss
DSW
1.22
-0.001
0.000
0.001
0.4
Ey-nrrm weight perturbation ||>/|||
10
10
10-3
10-2
10-1
PGPE standard deviation PprE
Figure 10: Effect the standard deviation оPСРE on the induced loss surface in PGPE small population sizes of Ups 32.
Figure 11: Train and Validation Losses after 50 epochs of training for different values of OPGPE.
C.3 Train Dynamics Comparison
Training Loss
Baseline (GRAD)
0.4
GLS (RGS)
0.2
0.0
0
10
20
30
40
50
60
70
Train Epoch
Figure 12: Evolution of training loss when training CNN5 on MNIST = 0.1 using the DEEPPOLY convex relaxation with standard backpropagation (GRAD) and with GLS-based RGS.
we show the differences between the training dynamics of GRAD-DeepPoly (Baseline) and RGS-DeepPoly for our CNN5 models trained MNIST 0.1. We can observe that using RGS obtain lower losses even from the e-annealing phase (first 20 epochs), resulting in a better training quality and better model after training is done.
In Figure 12
D Additional Experimental Data
D.1 Training CROWN-IBP-RG. CNN7
While DEEPPOLY-RGS is too computationally extensive for scaling to CNN7, with CROWN-IBP to prove that the advantages of GLS scale even to SOTA architectures. We present the results of training CNN7 with CROWN-IBP-RGS in Table [ We observe that RGS significantly increases the performance of CROWN-IBP when applied on CNN7 without BatchNorm layers, but the improvement is less pronounced when using BatchNorm layers.
RGS in combination
In order accomodate the use of BatchNorm layers with RGS, we compute the estimated gradients by using the Narm statistics independently for each sample of perturbed weights. To obtain the test statistics,
23

---

Published in Transactions on Machine Learning Research (07 (07/2025)
reset the rumning stats to the population statisties for the mean trained network after each epoch, following the advice of Mao et al. (2024). While this approach is the most straightforward, it might not be the most. effective way to use BatchNorm layers with RGS, and we leave the exploration of more sophisticated methods for future work.
Table 6: Comparison between CNN7 networks trained with CROWN-IBP-RG' and SOTA GRAD methods small perturbation settings
Nat. Acc.
Cert. Acc.
Adv. Acc. [%]
Dataset
Network
Method
[%]
[%]]
IBP
98.87
98.26
98.27
CNN7 with BN
CROWN-IBP
99.10
98.13
98.22
CROWN-IBP-RGS
99.11
98.05
98.09
MNIST Coo 0.1
TAPS
99.16
98.52
98.58
IBP
98.50
97.40
97.42
CNN7 BN
CROWN-IBP
98.83
97.94
97.94
CROWN-IBP-RGS
99.19
98.09
98.18
IBP
67.49
55.99
56.10
CROWN-IBP
70.90
58.80
59.93
with BN
CROWN-IBP-RGS
70.82
59.04
60.19
CIFAR-10 Coo 2/255
MTL-IBP
78.82
64.41
67.69
IBP
63.13
52.09
52.27
CNN7 no BN
CROWN-IBP
67.82
55.36
56.62
CROWN-IBP-RGS 68.46
56.30
57.37
Finally, the results showcase that the promise using GL.S for certified training with tighter relaxations also scales to SOTA architectures.
D.2 Comparison between RGS and PGPE on CNN3 and CNN3-tiny
In Table 7 we provide additional experimental data comparing the performance of PGPE and RGS on CNN3 and
In the case of CNN3, we observe that RGS and PGPE obtain similar performance on MNIST 0.1, but RGS is actually significantly better on CIFAR 2/255 (note that both are better than IBP and DEEPPOLY trained with Adam). We hypothesize that this might be due to: (1) on CIFAR-10 the CNN3 network has more parameters than on MNIST 5k 7k due to different input sizes), thus the parameter space is larger; (2) we train for the same number of epochs on both datasets with PGPE, but standard certified training has shown networks
CIFAR-10 to converge slower than MNIST. As result, since PGPE trains slower due to the low-rank gradient problem, CIFAR-10 makes this worse, and insufficient training outweighs the theoretical benefit. These claims are further supported by our results for CNN3 CNN3-tiny trained on MNIST where we observe that PGPE is significantly better than RGS, likely due to the smaller parameter space and faster convergence of the training.
D.3 Comparison of GLS and Sharpness-Awan Aware Minimization (SAM)
The gradient computation by perturbing the network weights used in PGPE and RGS has some similarities with the Awarpness-Aware Minimization (SAM, Foret et al. (2220) algorithm. However, the SAM algotithm is fundamentally different to GLS. This is because GLS takes the expectation of neighborhood loss rather than the worst case loss; in fact, SAM is closer to adversarial training with FGSM (Goodfellow et al.] 2015) rather Ihan GLS. In particular, SAM does not resolve the discontinuity problem, while GLS provably solves it (Theorem 3.1.. To see this, consider the threshold function [(x > 0) and an initial zo = 0.1. Any single- point- gradient based methods (including SAM) will only get zero gradient, and thus cannot optimize Therefore, while it likely that GLS has the benefit of reduced sharpness as well, GLS enjoys fundamentally different. benefits to SAM.
24

---

Published in Transactions on Machine Learning Research (07/2025)
Table 7: Comparison of PGPE and RGS on CNN3
Dataset
Network (params.)
Method
Nat. [%]
Cert. [%]
Adv. [%]
IBP-GRAD
89.76
82.46
82.48
MNIST
DESPPOLY-CRAD
89.24
68.47
68.57
ChNB-tiny (1.1k)
Coo 0.1
DEEPPOLY-PGPE
91.94
85.00
85.04
DEEPPOLY-RGS
91.33
82.66
82.68
IRP-GRAD
96.02
91.23
91.23
MNIST
DEEPPOLY-GRAD
95.95
90.04
90.08
CNN3 (5.2k)
0.1
DEEPPOLY-PGPE
97.44
91.53
91.79
DEEPPOLY-RGS
97.37
91.88
92.03
IBP-CRAD
48.05
37.69
37.70
C-FAR-10
DEsPPOLY-GRAL
47.70
36.72
36.72
CNN3 (6.8k)
6oo = 2/255
DesPPoYYPPGPE
54.17
38.95
40.20
DESPPOLY-RGS
54.93
41.14
42.03
confirm this empirically, we apply SAM to IBP and DEEPPOLY training. Specifically, we update the parameters with gradients computed based on the adversarially perturbed network w' V W We train with IBP and DEEPPOLY on MNIST 0.1 with the same CNN3 architecture used in the paper. The results are shown in Table 8 all networks certified with MN-BaB.
Table 8: Comparison of GLS methods with SAM. CNN3 networks trained on MNIST e 0.1.
Method
Nat. [%]
Cert.
[%
IBP-GRAD
96.02
91.23
IBP-SAM p 0.1
96.08
90.20
IBP-SAM 0.01
96.32
93.32
IBP-SAM 0.001
95.80
91.73
CHEPPOLY-GRAL DEEPPOLY-SAN / 0.1
95.95
90.04
94.22
88.39
DEEPPOLY-SAR SAM P 0.01
96.93
92.34
DEEPPOLY-SAM P 0.001
96.95
90.91
DEEPPOLY-PGPP
97.44
91.53
DERPPOLY-RGS
97.37
91.88
We observe that for correctly chosen hyperparameter (p 0.01), SAM does indeed improve performance for IBP and DP. While SAM performs better than PGPE for this very shallow network, as expected from our previous theoretical analysis, it does not address the paradox. In particular, IBP-SAM still performs better than DP-SAM uniformly for every choice of p. While combining SAM with PGPE or other certified training methods might thus constitute an interesting future direction, it does not explain the reranking of approximation methods (DREPPOLY-PGPP) PGPE. We therefore conclude that the sharpness aware aspect of PGPE is not (solely) responsible for its effectiveness in resolving the paradox of certified training.
IBP-PGPE vs IBP-SAM DEEPPOLY-SAMI we observe for
E
Additional Discussion
E.1
Discussion on the regularization induced by IBP for large preturbations
In $4.4 we show that RGS improves the performance of light relaxations surpassing the SOTA methods on the same architecture for the setting of small perturbations. However, this improvement is not as substantial in the case of large perturbations. Based on our experimental intuitions and the findings of prior works (Mao) et al.) 2024 2023b)), we hypothesize that the regularization induced by training with IBP bounds boosts the network's i certifiability in the case of large perturbations. We note that the L regularization has been
25

---

Published in Transactions on Machine Learning Research (07/2025)
sufficiently tuned by Mao et al. (2024) for MTL-IBP, thus only increasing L1 regularization strength cannot achieve the kind of regularization needed for certifiability. Therefore, we speculate that large leads to much more unstable neurons, leading to exponential growth of certification difficulty. Thus, for large e, strong (and maybe unnecossary to robustness) rogularization is roquired to further reduce certification difficulty. Note that the effects of this IBP regularization are more complex than just limiting the magnitude of the weights, as described by Mao et al. (2023b).
E.2 Discussion on the relation between GLS and Randomized Smoothing
While Gaussian Loss Smoothing (GLS) and Randomized Smoothing (RS) (Cohen et al. 2019 both involve Gaussian noise, they differ fundamentally in purpose and mechanism. RS applies smoothing in the input space, typically training on noisy inputs to enable probabilistic certification inference time. This can be seen form of data augmentation and requires specialized training tailored to the target noise level.
In contrast, GLSS applies smoothing in the parameter (weight.) space, modifying the loss landscape to improve optimization especially in the presence of discontinuities introduced by tight convex relaxations. As such, GLS is more closely related to classical smoothing methods used for gradient estimation and optimization in non-smooth settings.
Importantly, the certifications provided by RS are probabilistic and require substantial runtime sampling (e.g., 100+ forward passes per input), whereas method yields deterministic certificates based on convex bounds. Although GLS-based training can be more computationally intensive during optimization, inference is straightforward and efficient, requiring no changes to the trained model.
F
Additional Training Details
F.1 Standard Certified Training
We train with the Adam optimizer (Kingmn & Ba 2015) with a starting learning rate of 5 x 10-5 for 70 epochs on MNIST and 160 epochs on CIFAR-I0 and TINYIMAGENET. We use the first 20 epochs on MNIST and 80 epochs CIFAR-10 and TINYIMAGENET for e-annealing, with the first epoch having CIFAR-10 and TINYIMAGENET. We decay the learning rate by factor of 0.2 after epochs 50 and 60 for MNIST and respectively 120 and 140 for CIFAR-10 and TINYIMAGENET. For certified training on MNIST and CIFAR-10, we use the IBP initialization proposed by Shi et al. (2021). For PGD training and for certified training on TINYIMAGENT ET we use the Kaiming uniform initialization
0 for
(He et al. 2015
F.2 PGPE Training
We use 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 110th and th epoch. We use the first 50 epochs for e-annealing only when training with the large value for each datasct (MNIST c c 0.3 and CIFAR-10 e 8/255). Due time constraints, we start all training rounds from models trained with the PGD loss in a standard gradient-based setting.
Training with non-differentiable bounding methods In addition, for training with a-CROWN + PGPE, we use the same training schodule and hyperparameters as for standard PGPE training. For the slope oplimization procedure of a-CROWN, we initialize all slopes with the value of 0.5 and we conduct only one optimization step with step size 0.5 for each batch, resulting in all slopes having a value of either 0.0 or 1.0. In this way, we obtain a boost in tightness when compared to standard DecpPoly, while increasing the computational cost only by a factor of 2. Slope optimization with multiple steps and smaller step sizes can further increase the tightness of the relaxation, but at the cost. of increased computational complexity.
26

---

Published in Transactions on Machine Learning Research (07 (07))
F.3 RGS Training
We use the same training schedules and hyperparameters Standard Certified Training. In addition, we use population size of Ups = 2 for all experiments, and an initial standard deviation of ORGS = 10-3 for all experiments. We decay the standard deviation used for sampling gradients by a factor of 0.4 at the same training steps as the learning rate. We use the same initialization schemes as for standard certified training, unless specified otherwise.
F.4 Architectures
In Table we present the network architectures used for all our experiments.
Table 9: 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 e hxw/s/p' corresponds 2D convolution with e output channels, an hxw kernel size, a stride of s in both dimensions and an all-around zero padding of p.
CNN3-tiny
CNN3
CNN5
CNN5-L
CONV 2 5x5/2/2 CoNv 5x5/2/2
CONV 16 5x5/2/2
CONV 64 5x5/2/2
CONV 2 4x4/2/1
CONv 8 4x4/2/1
CONv 16 4x4/2/1
CONV 64 4x4/2/1
CONV 32 4x4/2/1
CONV 128 4x4/2/1
FC 512
FC 512
F.5 Dataset and Augmentation
We use the MNIST LeCun al. 2010). CIFAR-10 KKrzhevsky et al. 2009 and TINYIMAGENET (Le & Yang 2015) dalasets for our experiments. All are open-source and freely available with unspecified license. The data preprocessing mostly follows De Palma et al. (024)) For MNIST, we do not apply any preprocessing. For CIFAR-10 and TINYIMAGENET, we normalize with the dataset mean and standard deviation and augment with random horizontal flips. We apply random cropping to 32 x 32 after applying a 2-pixel zero padding at every margin for CIFAR-10, and random cropping to 64 x 64 after applying 4-pixel zero padding at every margin for TINYIMAGENET. We train on the corresponding train set and certify on the validation set,
adopted in the literature Shi et al. 2021 Müller et al. 2023 Mao et al. 2023a
De Palma et al. 2024
F.6 Training costs (Time and Resources)
Theoretical Costs of GLS The theoretical costs of any GLS-based method scales linearly with the population size pps used to obtain gradient estimates. Tn the case of PGPF, we need to use large population size (e.g. ppp 256), which makes the algorithm very costly: we need to compute the loss via forward pass Nps times. Estimating the gradient after computing the losses is negligible, so the total time complexity of one epoch is OOpps F), where F would be the time taken by the standard certified training algorithm to only compute the forward pass in one epoch. For RGS, there's no need to use large population sizes (nps = works well enough), so the total training time our experiments is just nps = times larger than normal certified training (includes both forward and backward passes because we use backpropagation to obtain gradients).
Experimental Costs For PGPE and RGS training, used between 2 and 8 NVIDIA L4-24GB NVIDIA A100-40GB GPUs. For standard certified training and for certification of all models we used single L4 GPUs.
In Table 10 we present a detailed analysis the training costs of the PGPE and RGS methods for all of our experimental sottings (Note that the cost DEEPPOLY-PGPE for CNN5 was estimated based on training for only epoch). Table I1 we present the training costs for the baseline standard certified training methods for comparison.
27

---

Published in Transactions on Machine Learning Research (07 (075)
Table 10: Training costs and workload distribution across GPUs / actors for each train setting.
Num. Actors
Time/epoch
GPU-h/ epoch
Datset
Network
Method
GPUs
(min)
DEErPOLY-PGPE aCROWN-PGPE
x 8 L4
1.73
CNN3- tiny
8
44
5.86
IBP-PGPE
2 x L4
4
2.8
0.09
CROWN-IBP-PGPE
x L4
4
8.5
0.28
MNIST
CNN3
HBox-PGPE
x L4
31
4.13
DEEPPOLY-PGPE
8 x L4
27
3.60
DREPPoIY-PGPE (est.)
8 x TA
R 300
R 40
CNNS
DEEPPOLY-RGS
8
7.5
CNN5-L
DEEPPOLY-RGS
8 A100
4.68
IBP-PGPE
x L4
6.9
0.23
CNN3
CROWN-IBP-PGPE
4 x L4
8.5
0.57
DEErPoLx-PGPE
8 x L4
42
5.6
CIFAR-10
DEEPPoLY-PGPE (est.) DEEPPOtY-RGS
8 x L4
RJ 360
AV 48
CNNS
x L.4
16
2.2
CNN5-L
DEEPPOLY-RGS
x A.00
4.4
TINYIMAGENET
CNNS
DEEPPOIY-RGS
x A100
5.5
Table 11: Training times of CNN5 on 1xL4 GPU with standard autograd training depending training method.
Train Time
Dataset
Method
(1xL4 gpu)
PGD
15m
IBP
10m
MNIST
SABR
20m
STAPS
25m
MTL-IBP
40m
PGD
1h30m
IBP
1h00m
CIFAR-10
SABR
2h00m
STAPS
2h30m
MTL-IBP
3h10m
PGD
3h15m
TNNTIMGENNT
IBP
2h20m
MTL-IBP
4h20m
28


Reviews:
[{"review_id": "ux9NmY3Dcd", "reviewer": "Reviewer_GxFb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nGLS is well-motivated and the *general* ideas are presented clearly. The authors have provided a theoretical foundation for GLS and evaluated the performance empirically across multiple benchmarks.\n\n**Weaknesses:**\n\n- Certain parts of the paper (especially technical explanations and notations) could be written more clearly. (please see suggestions)\n- Outdated Literature:The paper does not reference publications from 2024 or 2025, making the paper appear somewhat dated. Mentioning  recent developments would better situate the contribution within the current state of the field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers addresses the challenges associated with training neural networks using tight convex relaxations for certified robustness. It is known that the discontinuity, non-smoothness, and sensitivity of the loss surface are key factors in the performance of the certified training. The authors propose Gaussian Loss Smoothing (GLS) as a general framework to mitigate these issues. The contributions include \n1. they provide theoretical justification for how GLS can smooth the loss function and reduces the deviation from convexity.\n2. Algorithms: proposed PGPE and RGS implmenetations of GLS.\n3. Empirical evaluations: They compared the GLS with other baseline methods on a variety of datasets and models (although the general architecture is limited to CNN)\n\nOverall, the paper demonstrates the potential of GLS as an effective enhancement to existing convex relaxation-based training methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are few suggestions and questions that I appreciate it if the author could address them:\n\n**Questions**:\n1. When defining the $\\epsilon$-neighborhood, what norm (i.e., what value of $p$) is used in the paper?\n2. In the equation immediately following (1), define the index $i$.\n3. Table 1 Terminology: Please clarify the $\\epsilon_{\\infty}$. Also, instead of abbreviations \"Nat.\", \"Cert.\", and \"Adv.\" I recommend the authors to use the full words.\n4. Is GRAD essentially the baseline method, i.e., it applies the relaxation without GLS as in their original papers?\n5. What is the added computational complexity and training overhead of incorporating GLS?\n6. How does GLS influence the convergence rate of the training process? It would be helpful if the authors could include training loss curves with and without GLS for one model, to compare convergence dynamics.\n\n**Minor Suggestions**:\n1. The current title suggests that certified training is enabled by the proposed method. However, since convex relaxations already allow for certified training, and GLS improves their effectiveness, a term like *Improves* or *Enhances* may better reflect the contribution than *Enables*.\n2. It would help readers if the authors explicitly state that GLS is not an independent relaxation technique, but rather complements existing convex relaxations to enhance their performance.\n3. Introducing a notation table or a brief subsection summarizing the key mathematical symbols.\n4. In the second paragraph of Section 3.3, the first sentence could be rephrased to clarify that PGPE samples *n* weight perturbations.", "broader_impact_concerns": "No concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0xmXJlQA7V", "reviewer": "Reviewer_h2Ty", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Quality\n### Strengths\n- Well-designed project. Begins with a clear idea, provides framework, does theoretical analysis, and then does experimentation. The theoretical analysis maps very nicely onto discontinuity, non-smoothness, and sensitivity as defined.\n- Experimental design is very thorough. I particularly appreciate the inclusion of adversarial accuracy, which feels honest and thorough\n- Results show improvement over baselines\n- Good discussion comparing the results, though it could be more structured\n### Weaknesses\n- Would like to see more visualization/intuition built about what the empirical results tell us about the three properties\n- Could be more upfront about the novelty of the paper in particular. From what I understand it is novel, but at times it's difficult to distinguish the paper's claims and the prior work, particularly wrt PGPE and RGS. Once we go through the longer subsections in Sec 3 it's clearer, but earlier language could be toned down. \n\n## Clarity\n### Strengths\n- Overall very well-written. I do not have a deep theoretical ML background, so while I limited in my ability to critically evaluate this paper's situation in existing literature or the soundness of its framework, it does make its own framework intuitive and easy to understand\n- Results section has useful structure, being claims-driven and signposted \n- There's a lot of theory, but I found it possible to follow. The figures and explanations really help build intuition and visualize, which is crucial \n### Weaknesses\n- Fig. 5 should be visualized differently, as it feels crucial for building intuition but is hard to understand \n- Results section, though well-signposted, is somewhat verbose. It becomes hard to keep everything straight. With a few reads it's not so bad, but it may help to ease the burden on less-informed readers by calling out key points more.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses what it calls the Paradox of Certified Training, where certified robust training of neural networks on tighter (i.e. theoretically better) convex relaxations often leads to empirically worse performance. It identifies three key properties that cause this poor performance: discontinuities, non-smoothness, and sensitivity in the tighter relaxations. It aims to solve these by using Gaussian Loss Smoothing (GLS), i.e. applying a Gaussian kernel to the loss. \n\nThe overall contributions are four-fold: theoretical analysis of GLS, a zeroth-order training method based on PGPE with GLS, a first-order training method based on RGS with GLS, and evaluation results comparing to baselines. \n\nThe paper goes in detail through preliminaries about training for certified robustness, then explanation and investigation of GLS itself and how it handles discontinuities, non-smoothness (Lipschitz continuity), and sensitivity. It then lays out results comparing convex relaxations of varying tightness with and without GLS on multiple datasets and with both optimization methods. It primarily shows performance that outdoes loose relaxations, with less empirical investigation into the three properties.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "d3htR3bfoh", "reviewer": "Reviewer_TWPN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) Strong theoretical findings (Theorem 3.1), solved the issues found by the works of the previous researchers.\n2) Empirical Confirmation through various settings.\n\nEven though I am not an expert in this field, according to their statements, this paper seems to have great potential in machine learning society. Even though I don't have strong confidence in my decision, I'd like to lean toward acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the challenge of training neural networks with high certified accuracy against adversarial examples. It notes that while tight convex relaxations are beneficial for certification, they can surprisingly underperform looser relaxations during training. Previously researchers hypothesized this is due to the loss surface's discontinuity, non-smoothness, and perturbation sensitivity caused by tighter relaxations. \n\nTo mitigate these issues, the paper theoretically proposes and empirically validates Gaussian Loss Smoothing (GLS). They introduce two GLS-based training methods: PGPE (zeroth-order, for non-differentiable relaxations) and RGS (first-order, more efficient). Extensive experiments demonstrate that these methods, when combined with tight relaxations, outperform state-of-the-art techniques on the same network architecture across various settings. The findings highlight the potential of GLS for training certifiably robust neural networks and suggest a direction for effectively utilizing tighter relaxations in certified training.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) The table 1 seems misleading. It marked the original gradient based methods as red, and marked theirs as blue. It makes the reader feel it has been always improved, but it seems like the certified accuracy gets lower for IBP, and they still marked it as blue to make it feel improved. I hope the authors change the design of the table a bit.\n\n2) Has there really been no prior approach that utilized smoothing by adding noise? Looking at the authors' paper, it seems like a relatively old field, dating back to around 2018, and smoothing by adding noise to polish the landscape is a fairly common technique in the machine learning community. It's quite interesting that there haven't been attempts to combine these. Could you please conduct a more thorough investigation and provide a confirmation? That would greatly help with the decision. Also, could you include related works on smoothing?\n\nFor example, compared to 'Certified Adversarial Robustness via Randomized Smoothing', what is the main difference?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)