Smoothed Robustness Analysis: Bridging worst- and average-case robustness analyses via smoothed analysis
Authors: Thomas Rodrigues Crespo
Jun-nosuke Teramae
Venue: Accepted by TMLR ()

Abstract: The sensitivity to adversarial attacks and noise is a significant drawback of neural networks, and understanding and certifying their robustness has attracted much attention. Studies have attempted to bridge two extreme analyses of robustness; one is the worst-case analysis, which often gives too pessimistic certification, and the other is the average-case analysis, which often fails to give a tight guarantee of robustness. Among them, \textit{Randomized Smoothing} became prominent by certifying a worst-case region of a classifier under input noise. However, the method still suffers from several limitations, probably due to the lack of a larger underlying framework to locate it. Here, inspired by the \textit{Smoothed Analysis} of algorithmic complexity, which bridges the worst-case and average-case analyses of algorithms, we provide a theoretical framework for robustness analyses of classifiers, which contains \textit{Randomized Smoothing} as a special case. Using the framework, we also propose a novel robustness analysis that works even in the small noise regime and thus provides a more confident robustness certification than \textit{Randomized Smoothing}. To validate the approach, we evaluate the robustness of fully connected and convolutional neural networks on the MNIST and CIFAR-10 datasets, respectively, and find that it indeed improves both adversarial and noise robustness.

Published in Transactions on Machine Learning Research (04/2024)
Smoothed Robustness average-case robustness analyses via smoothed analysis
Analysis:
Bridging worst- and
Thomás Rodrigues Crespo
Graduate School of Informatics Kyoto University
Jun-nosuke Teramac
deramacehacs.ikytooo..cc
Graduate School Informalics
Kyoto University
Reviewed on OpenReview: https: openreview. net/ per//frmm?? id= BoguF
Abstract
The sensitivity to adversarial attacks and noise is significant. drawback of neural net- works, and understanding and certifying their robustness has attracted much attention. Studies have atlempted to bridge two extreme analyses of robust one is the worst-case analysis, which often gives too pessimistic certification, and the other is the average-case analysis, which often fails to give tight guarantee of robustness. Among them, Randomized Smoothing became prominent by certifying a worst-case region of classifier under input noise. However, the method still suffers from several limitations, probably due to the lack of larger underlying framework to locate it. Here, inspired by the Smoothed Analysis of al- gorithmic complexity, which bridges the worst-casc and average-case analyscs of algorithms, we provide & theoretical framework for robustness analyses of classifiers, which contains Randomized Smoothing as a special case. Using the framework, we also propose a novel robustness analysis that works even the small noise regime and thus provides a more con- fident robustness certification than Randomized Smoothing. To validate the approach, we evaluate the robustness of fully connected and convolutional neural networks the MNIST and CIFAR-10 datasets, respectively, and find that it indeed improves both adversarial and noise robustness.
1 Introduction
Deep learning has significantly advanced machine learning in various real-world tasks over the last decade. Despite its success, deep learning is not sufficiently robust to small input perturbations known adversarial perturbations (Segedy el. al. (2014) or intrinsic noise that can occur in the inputs. Besides research to improve the adversarial and noise robustness of neural networks, theoretical studies to quantify and certify robustness have also emerged to address the problem.
One extreme of robustness quantification of neural networks is adversarial robustness certification, which tries identify a set of inputs that the model is guarantced classify correctly. Thus, a larger set indicates more robust model. major example of this is Certified Radius, which is the radius of ball such that it is centered on correctly classified input and does not contain adversarial examples. Since this analysis provides safe region against any perturbation, it gives worst-case robustness of the model. However, the analysis may give a too pessimistic view of the real-world performance of the model, as the Certified Radius is often smaller than the spread of natural noise.
The other extreme robustness analysis using random input perturbations (Franceschi et al. 2018 Weng et al. 2019 Couellan 2021 Tit & Furon 2021 Anderson Sojoudi 2023). Since the average performance of classifier is given by its classification probability, which is difficult. to obtain, in practice analyzes

---

Published in Transactions on Machine Learning Research (04/2024)
its lower and upper bounds. Then, higher lower bound for larger variances indicates higher robustness to noise. In contrast. to Certified Radius, the expectation over all directions, which mitigates the effect of misclassification regions with small volume, gives a better measure of empirical performance. However, the analysis can be too optimistic since, for instance, it gives "infinite" robustness for lincar classifiers in binary classification because the misclassification probability is always below 0.5 for finile noise strength.
Given the above, approaches have attempted bridge those two extremes (Fawzi et al. 2016 Rice & Bair 2021 Robey et al., 2022), with Randomized Smoothing (Cohen et al., 2019) being the most prominent. In this analysis, one obtains Certified Radius of a smoothed classifier, a smoothed version of deterministic classifier given by injecting noise into the input. Namely, the robustness of the classifier is mcasured here by the radius of a ball around the imput, within which all points are classified correctly on average. As in average-case robustness, smoothing mitigates the effect of small regions. In addition, the analysis can scale to arbitrary neural networks. However, the analysis still has limitations. For instance, its Certified Radius scales with the variance of the input noise, resulting in vanishing it for small variances and information loss for larger variances Mohapatra el. al. (2021). It is also unclear whether the analysis can be placed in general theoretical framework and whether we can extend it based on the framework.
Here, to address these problems, we borrow an idea from studies of algorithmic complexity. Inspired by the Smoothed Analysis of algorithmic complexity, which bridges the worst-case and average-case analyses of algorithms (Spielman & Teng 2004), we provide a novel theoretical framework for the robustness analysis of classifiers. Smoothed Analysis aims to obtain a more faithful description of the empirical algorithmic time complexity compared to worst-case and average-case by obtaining the worst-case performance when subject to random perturbations, which is very similar to the protocol of Randomized Smoothing. However, applying the Smoothed Amalysis of algorithmic complexity to the robustness analysis of neural networks is not straightforward, because one needs to identify a suitable performance metric to which the analysis is applied. For this problem, we show that a loss function satisfying a certain condition can be a suitable performance metric for the analysis in the robustness sctting for classification tasks. We then show that Randomized Smoothing is a special case in the framework when the loss is the 0-1 loss. We call this robustness analysis framework Smoothed Robustness Analysis, SRA.
The above finding may imply that if we use loss function other than the 0-1 loss as the performance metric, SRA may solve the problem of Randomized Smoothing that the certified region vanishes for small noise variances. Motivated by this, we propose the use of the margin loss and show that it indeed provides a Certified Radius that not only does not vanish for small noise variances but is more confident since the variance of the margin decreases with the noise variance until it converges to the zero-noise margin. We refer to the proposed Certified Radius based on the SRA with the margin loss as Margin Smoothed Certified Rodius, MSCR.
As proof of concept for our approach, by deriving an explicit expression for the MSCR for K-Lipschitz classifiers, we used it as an objective that, when maximized, is expected to induce both adversarial and noise robustness to them. Experiments were conducted on the MNIST and CIFAR-10 datasets for 1-Lipschitz fully connected and convolutional neural networks, respectively, and their robustness against. adversarial perturbations, isotropic Gaussian noise, and progressive linear corruptions were quantified. We found that, under the considered scttings, the maximization of MSCR improves robustness to both adversarial and random noise for a simpler dataset (MNIST), and for more complex dalaset (CIFAR-10), it leads to an increase in noise robustness while maintaining similar clean accuracy and adversarial robustness.
1.1
Related works
1.1.1 Bridging adversarial and noise robustness
To incorporate adversarial and noise robustness, various studies have explored robustness spectra locating the worst- and the average-case analyses in its opposing ends. Fawzi et al. (2016) considered the expected distance to the decision boundary over randomly sampled input with dimensions between 1 and nam: which interpolate between the worst-case and random noise regimes. Rice & Bair (2021) proposed using the lg norm of smooth loss with respect to chosen measure as robustness metric. When the uniform ball is used as
2

---

Published in Transactions on Machine Learning Research (04/2024)
the measure, it gives the worst-case loss for q oo and the expected loss over the ball for q 1, interpolating between them through q. To address the lack of interpretability or impracticality of existing methods, Robey et al. (2022) introduced the probabilistically robust learning framework that interpolates between adversarial and average training by introducing the misclassification tolerance parameter p determining the stringency of the worst loss within a feasible region. For the 0-1 loss with a uniform distribution in the input, P = 0 corresponds to adversarial training, where the loss for one sample is zero only if there no adversarial example within uniform ball. In contrast, when p = 0.5, the framework achieves average-case robustness, where a training sample contributes to the loss only if its classification probability is less than 0.5.
1.1.2 Randomized smoothing
While the above works bridge the worst and the average cases as two ends of a spectrum, Randomized Smoothing explicitly uses one noise and one adversarial mechanism to bridge them. Randomized smoothing was first proposod by Lecuyer et al. (2019) within the realms of differential privacy as PixeIDP, providing radius certification of ( and le balls of smoothed classifiers by employing the Laplace and Gaussian distri- butions as input noise, respectively. In their seminal work, Cohen et al. (2019) proved a tight l2 certified radius for the case of Gaussian input noise and named the analysis Randomized Smoothing. In the analysis, a deterministic classifier that returns a 0-1 vector, with 1 in the correct class clement, becomes a probabilistic one called smoothed classifier, which returns the probability of each class by injecting noise into the input. Then, using the probabilities of the correct and largest incorrect classes, one can obtain the certified radius of this smoothed classifier, that is, the radius of a ball around the input within which all points are corroctly classified on average. In other words, it measures the worst-case robustness of an averaged, or smoothed, classifier.
Two significant properties make Randomized Smoothing attractive for robust certification. First, smooth- ing acts as in average-case robustness, mitigating the effect of close but small misclassification regions. Sec- ond, it is scalable to arbitrary NNs: While most certification methods rely on the architecture of the neural network, such as its Lipschitz constant for Lipschitz- based Certified Radius (Cisse et al., 2017; Tsuzuku et al. 2018 Weng et al., 2018 Leino et al. 2021), or its activation functions as in Certified Radius based on convex relaxation (Weng al. 2018 Wong & Kolter 2018), Randomized Smoothing depends only on the input noise distribution and the classification probability cstimation method.
1.1.3 Lipschitz-constraained NNs
Lipschitz-coonsrrained neural networks have been widely studied as a promising way to improve their ad- versarial robustness. Although expressiveness and scalability have been major concerns of the approach, significant advances have been made very recently. For expressiveness, studies revealed that these networks can in fact ensure their expressivity even under Lipschitz constraints (Anil al. 2019 Béthune et al. 2022).
For scaling, based on the approach of Faalyya et al. (2019), Araujo et al. (2023) and Wang & Manchester (202)) showed that rained networks can scale to tiny-imagenet, and Losch et al. (2023) and Hu et al. 22023) using the idea of Leino et al. (2021), succoeded in showing the scaling to tiny-imagenet and even to imagenet, respectively. Recently, Delattre et al.] (2024) connected Randomized Smoothing and Lipschitz margin using a 1-Lipschitz simplex mapping. They used the expected margin over the simplex mapping and showed improvements over usual Randomized Smoothing and margin certified radii. We adopted the 1-Lipschitz architecture obtain the estimated certified radius training time, and due to its stability by avoiding exploding and vanishing gradients.
1.1.4 Algorithm analysis: worst-case, average-case and smoothed
Analysis of algorillmss is field of computer science that focuses on comparing algorithmic performance (Cormen] 2009) to determine which algorithm performs the best under given performance metrics and constraints. One approach is the worst-case analysis, which provides the worst possible performance of an algorithm given certain constraints, such as input size. Thus, an algorithm with a good carst-case performance is guaranteed always perform better than one with worse worst-case. However, the worst-
3

---

Published in Transactions on Machine Learning Research (04/2024)
case analysis can be too pessimistic, since the worst-case may comprise instances that might be rare nonexistent in practice (Spielman & Teng 2009 Roughgarden 2021
In these cases, average-case amalysis provides a more realistic description by assigning a measure to the instance space and obtaining the performance metric as a weighted average (Ritter 2000). However, in practice, average-case analysis requires overly simplified distributions, such as the uniform distribution over all possible instances, which do not correspond to the real instance distribution and yields results that strongly depend on the chosen distribution (Roughgarden 2021
Smoothed Analysis is introduced to address the limitations of worst- and average-case analyses Spielman & TTng 2004). This approach consists in incorporating randomness in the algorithm, which leads to the so-called smoothed algorithm, and then applying & worst-case analysis. Unlike average-case analysis, the distribution used the averaging stage of Smoothed Analysis is preferable to have only a small variance around the state under ovaluation. Therefore, the analysis is expected to avoid biases about the real under- lying distribution by using small perturbations, similar to sensing noise random faults. While Smoothed Analysis has inspired several studies neural networks (Blum & Dunagan 2002 Haghtalab et al. 2020 Robey et al. 2022) its relation to robustness analysis has not been fully explored yet.
2 Smoothed Robustness Analysis: Smoothed Analysis for the robustness of classifiers
In this section, we provide how the "Smoothed Analysis of algorithms" can be applied to the robustness analysis of neural networks and show that the derived framework indeed includes adversarial, noise, and Randomized Smoothing robustness as special cases.
2.1 Smoothed Robustness Analysis
Since Smoothed Analysis is given the worst-case performance under random perturbations, to extend the framework to analyze the robustness of neural networks, we need to identify suitable performance metric that properly measures the performance the networks and is analytically or, at least, numerically tractable.
In the case classification tasks, let us first choose a noise distribution p(æ, 0) parametrized by an input æ and 0. Then, if the loss function (xx) satisfies the following condition with respect the given distribution, will see that it can be suitable performance metric for the smoothed analysis in the context of the robustness of the classifier.
Condition 1 (Constant I). There some constant I E R s.t. Ex'=p(mm00) [T(x') < I implies that Pelx: p) > 0.5 for all x E X, where Pa(a:; p) the probability of correct classification of x under the noise distribution p(x, 0).
In addition to choosing the noise distribution p(z, 0) and the loss function T(x) that satisfies the above condition, let us specify a region f2(x:) around the input æ. Then, we can provide the theorem that establishes the Smoothed Analysis for the robustness of classifiers.
Theorem (Smoothed Robustness Analysis). Let T(x) denote the marimal average loss within the region 2(x) C X around input x over the distribution p(ă:; 0), permmetrized by a E ((x)) and 0, i.e.,
T(x) = max Eg (T(='')))((((') SE((())
(1)
((x) <T, then no perturbation within ((x) causes misclassification on average.
Proof. The proof of the theorem directly follows from Condition [ since the worst proportion of misclassified samples must be less than half due to condition T(x) < Т, and thus the samples are correctly classified on average.
4

---

Published in Transactions on Machine Learning Research (04/2024)
We call the robustness analysis of the classifier based the above theorem Smoothed Robustness Analysis, (SRA) and define classifier to be Smoothed Robust on input with respect to the loss T(x) if it satisfies the above inequality T(x)= < I' for given (2(x) and p( O).
Depending on the choice of region (2) and noise distribution p(z: 0), this analysis yields the worst-, average- case, or a combination of both. Tf (2)x)) (ær) then the max operation restricted a itself, which gives the average-case. Conversely, if p( 0) ((),, then the expectation operator yields the pointwise value of the loss without smoothing effect, hence it gives the worst-case. The three different cases illustrated in Figure
One of the most practical applications of this analysis is robustness certification. While one can use the inequality T(x) < P to verily the robustness of a given classifier with respect to a given region R(xr) and distribution p(x; 0), the inequality can also be used inversely to obtain a region Q(x)) (e.g., a 4--ball) that satisfics the incquality for a given noise distribution. In other words, from the incquality one can find a Certified Radius such that imputs in the ball of the radius are always correctly classified on average under the noise distribution, that is Smoothed Robust. In the following, we will use this approach to show the relationship between the analysis and Randomized Smoothing, and to provide numerical calculations.
Figure 1: Illustrations of average-case (left), worst-case (center), and smoothed (right) robustness analyses. Different colors correspond different classes according to the classifier, and the dot located in the center is the input analyzed. For average-case, if the average loss smaller than given constant, it is correctly classified average. For worst-case, if the maximum of the loss inside the region is smaller than the constant, then it is safe inside the region. For the SRA, if the maximum of the average loss inside the region is smaller than the constant, then the classifier is safe inside the region on average, i.e., the smoothed classifier is safe there.
2.2 Randomized Smoothing as SRA with the 0-1 loss
One of the significant features of SRA is that can yield, in theory, a family of robustness analyses by changing the loss function T(x:), as long as the loss satisfies Condition and derive the constant T required for the condition.
Here, we show that Randomized Smoothing is special case of SRA where the loss T(x) is the 0-1 loss. The 0-1 loss is defined as
0, c = arg max (z)
Lu (ax, c)
(2)
1, otherwise
where (xx the ith component of the classification score vector and the correct class, Then we can show that the 0-1 loss satisfies the Condition 1
Thcorem 2. The 0-1 loss satisfies Condition with 0.5.
Proof. For an arbitrary noise distribution p(x, 0), it holds that Ex | (a,, (a',)) Pize p(-)) P-Po p(-), where (x p(-)) and Pe(x;:(-)) are the probability of incorrect and correct classification, respectively. Thus, Ex'~p(z) Lo (æ', c)) < 0.5 implies P.(x; p()) 0.5, which means r 0.5.
5

---

Published in Transactions on Machine Learning Research (04/2024)
Since the theorem justifies the use of the 0-1 loss Lu1 (a, c) as the loss T(x) of RSA, we can use the inequality Con (æ) = max 1 (Co1 (x') < 0.5 to obtain certified radius. However, because, shown in the above proof, Ba' Co1 (z', c)] is equal to the misclassification probability under given noise, i.e. misclassification probability of the smoothed classifier, this procodure means that one can obtain a certified radius based on worst-case analysis of the misclassification probability of the smoothed classifier. This is exactly the same the general idea of Randomized Smoothing (Cohen et al. 2019; Lecuyer et al., 2019)) For the case where the noise distribution p(æ, 0) is the Gaussian with variance oz and the region [2(x)) is the ball around the input, the radius is given (Cohen al. 2019
(oL,, 0z Φ (Pa) Φ
''mmaxx P.)
(3)
2
igt
where (-) is the inverse of the cumulative distribution function of the standard normal distribution.
3 Margin-based SRA: Smoothed Robustness Analysis with the margin loss
One major drawback of Randomized Smoothing is that the certified radius scales with the input noise variance, as in equation 3 meaning that for small variances the certified region vanishes. However, in the literature of smoothed analysis of algorithmic complexity, the smaller the variance of the perturbation, the better, which cannot be done by Randomized Smoothing. Recently, Delattre et al. (2024) succeeded in eliminating this scaling factor of the input variance by first noting that, for K-Lipschitz classifiers, the output variance is bounded by K² and then using the margin the probability vectors instead of the probability itself. This suggests that the margin might be suitable for SRA. In this section, we will show that this is indeed the case by proposing the use of the margin loss the loss T(x:) of RSA. We also derive closed-form estimate of the certified radius under the setting of K K-Lipschitz classifiers, which will use in numerical simulation given in the next section.
3.1 Margin Loss
The margin loss is defined as the difference between the largest output in incorrect classes and the output of the correct class,
LM (2x, c) om (x) oz(2))
(4)
where e denotes the correct class and m is the largest incorrect index, m = arg max 0; (x).
igte
Then, for the loss, we can prove the following proposition.
Proposition 3. If the output of classifier is continuous and symmetrically distributed under imput perturbation p, the margin loss sotisfies Condition 7 with r = 0 for the distribution.
Proof. This basically follows from the inequality for the smoothed margin EM c; p(-)) of continuous and symmetrically distributed outputs,
(M()),pp())) = Ex-=p((),)) o (x()) Me > med[max (x)) ifc
Pes
ifc
where Pe is the mean correct output, med|) refers the median. The full proof given in Appendix A.1
This proposition justifies our use of the margin loss as T(x) of RSA if the output of the classifier smoothed by the input noise is symmetric. We found this condition for the output to be adequate both empirically, as shown in Appendix [D.]] and theoretically, since independent rectified Gaussian random variables satisfy the Central Limit Theorem, as shown Appendix A.6 which mcans that their sum converges to a normal distribution, thus continuous and symmetrical. In the following, therefore, we assume that the output of the classifier satisfies the condition and apply the RSA based the margin loss to them.

---

Published in Transactions on Machine Learning Research (04/2024)
Let us assume that the classifier is Lp-Lipschitz. Then can prove the following theorem insisting that the radius
(s; (x,
(5)
aphp
is the certified radius in the sense of SRA with the margin loss, where (M p())) E [CM (x, c)] is the margin loss smoothed by the imput noise, and ap is constant depending on the norm (ap v2 and 2 for p and oo, respectively D The theorem given
Theorem Let the region ((x) be the 12-ball with radius esM p())..)). Then, (M(x))
maX =pt= c)] < 0 for any 6 s.t. ||0]| Ex((a aphp
Proof. The theorem follows from two propositions. The first. claims that the margin loss Cas of Ly- Lipschitz classifier is Lipschiip,, and the other says that the convolution of K-Lipschitz function with probability density function is also K-Lipschitz. The full proof is in Appendix A.2
Significantly, unlike the certified radius obtained from Randomized Smoothing (Eq. 3 the certified radius derived here for the margin-based RSA (Eq. 5), does not vanish even in the zero-variance limit of the noise distribution p(-). Rather, just converges the conventional certified radius of the classifier that is not perturbed by input noise,
(x) (x,
(6)
This property can make the obtained certified radius more confident by avoiding the information loss due to the larger variances required lo oblain meaningful certified radius under Randomized Smoothing. We refer to the certified radius obtained through the margin- based SRA, Eq. as Margin Smoothed Certified Radius (MSCR).
To proceed further and obtain closed-form expression of the MSCR, one needs specify the output distribution of the classifier. Assuming that the outputs can be approximated by multidimensional normal with independent elements yields the following approximation of LMr. (The derivation is in the Appendix
A.3
o + 2
(M1 12222 2 [of + 03) 1/2 +
112 (1+err)
(VO17 p2
)) Me- (7)
LM (I, 02 2
1 erf
exp
2m
2 + 03)
Here, Hos Pi and μe are the mean of the correct, the largest and the second largest incorrect outputs, respec- tively, and of and of are the variance of the largest and the second largest incorrect outputs, respectively. By putting the expression into Eq. 5 we obtain a closod-form expression of the MSCR.
Note that the above approximation similar to the one that Zheen et al. 2021 used to obtain the approxi- mation of the probability of the correct classification,
/2 fot) ).
1 1
Po (2 o
1 + erf
(8)
2
which gives lower bound the certified radius of the Randomized Smoothing,
Ox
④ (-1(P.)
------aaa P.))
P.))
Ox
① ( -1 Pc))
cul.12
2
ipf
2
(9)
Vo + oo 1) = 0x
=o - (P.) ~ 0 -1
Me 14 11l
Me M1
V0 of
We prove on Proposition
5
Appendix
A.2
that Op 27, where 1 == For p.q +00

---

Published in Transactions on Machine Learning Research (04/2024)
4 Proof of Concept
The properties of MSCR mentioned above may suggest that if one uses this certified radius, Eq. 5 as an objective function one can improve both adversarial and noise robustness compared to the certified radius of Randomizzd Smoothing, Eq. 3 and the conventional certified radius, Eq. G Here, show that this is indeed the case, we conduct numerical experiments as proof of concept of the proposed margin-based SRA.
4.1 Objective functions
Direct maximization of certified radius without any bounds degrades the clean accuracy of classifiers, due to the tradc-off between robustncss and accuracy. To avoid this problem, instead of directly maximizing the certified radius, we introduce hyperparameter d that controls the maximal contribution of the certified radius and try to minimize the hinge loss,
l,2 (x,,,,,,, ReLU(d- - e.j (0,
Hero, 6,12 (ar, c, 02, denotes the certified radius under classification loss (e.g., '01' or "M" for 0-1 or margin losses, respectively) under Gaussian input noise with variance of In our experiments, we minimized the hinge loss with MSCR,
fsMia (x,c,d,o2)) ReLUUd ESM.2 (z,,,,02) ReLU ( d++ La c, p(),
v2K
the MNIST handwritten digit (LeCun & Cortes 2010 and CIFAR-10 datasets
Krizhevsky
2009 for
1-Lipschitz fully connected and convolutional neural networks, respectively.
For comparison, we also implemented the hinge losses with MSCR but without smoothing, i.e., averaging over input noise, E, (x, c, of = 0) (MCR) and with the certified radius Randomized Smoothing cu1,12 (x, c, of) as the lower bound given in Eq. under the Zhen's approximation (we refer to it as Zhen loss). In addition to them, for completeness, we also used the Multiclass Hinge loss (MH) bыи (æ, c, d)
max(0, d
(o.(ar) (x))) that tries to maximize the difference from all incorrect ones (Anil al. 2019 Li el al.
expo)((r) that is the most widely used loss 2019b), the Softmax Cross-Entaan Pooss-E (SCE) fSCE (z, e) = - log Σ, expxo.(r)
for classifiers but neither enforces margin maximization nor acts on smoothed classifier, and the Smoothed Classifier Softmax Cross-Entrow (SC-SCE) fsC-SCE (z, c) = log Σ. exp))(())
exppe(a) We summarize these losses
in Table
To keep the networks 1-Lipschitz throughout the learning, used ReLU activation while keeping the weight matrices orthogonal. For the fully connected network, this means that the rows of the weight matrices are mutually orthogonal (A (Appendix C.2.1 and for convolutions, filters are mutually and 'internally' orthogonal (Appendix C.2.2 'Orthogonal weights" means that all their singular values are 1, which means that they are 1-Lipschitz in the 1g-norm sense. We used algorithmm that guarantee an approximate orthogonalization of weight matrices for every training step (Björck & Bowie 1971 Li et al. 2019b).
Further details of the experiments, including network architecture, hyperparameters, robust.nsss metrics, datasets, evaluation of output. statistics, as well qualitative overview of orthogonal convolutions are in Appendix C
4.2 Hyperparameter search
Figure shows the colormap of test data clean accuracy for MNIST experiments, area under the curve of certified radius curve AUCCR,,, through the margin (worst-case robustness), and area under the curve of noise accuracy AUCaN (average-case robustness) for different. combinations of hyperparameters d and o² on MSCR and Zhen losses.
First, these plots show the well-documented generalizatioo-rouusuess trade-off. For both losses, we can see that hyperparameter pairs with lower clean accuracy (darker areas in the first column) inversely
8

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Losses used in this work. Margin-baser based are the ones that explicitly try to maximize the margin Smoothed are the ones that use smoothed classifier. Acronyms are MSCR: Margin Smoothed Certified Radius loss (proposed here), Zhen: Zhen's loss (Randomized Smoothing), MCR: Margin Certified Radius loss (MSCR without smoothing), MH: Multiclass Hinge loss, SCE: Softmax Cross-Entropy, and SC-SCE: Smoothed Classifier Softmax
Loss
MSCR
Zhen
MCR
MH
SCE
SC-SCE
Margin-based Smoothed
X
/
X
X
X
Clean accuracy
Adversarial
Noise
44-
10-
60-
3.3
AUCos. (Margin)
2.3
MSCR
2.4
144
10-2
10
10
00
107
1094
16-1
10P
10
10-5
105
AUCoR (Margin)
Clean acnurary
AUCov
Zhen
10P
10
Figure Heatmap of clean accuracy, AUCCR,,, (margin), and AUGGN for MSCR and Zhen losses. For each column, the colormaps share the same maximum and minimum.
correlated with higher robustness (lighter areas in the sccond and third columns). Second, we point out that for the MSCR case the two parameters contribute to robustness in complementary ways: while a larger in general improves the adversarial robustness, by controlling the worst-case distance to the decision boundary, a larger of induces higher robustness to noise, since a classifier trained in this case learns to correctly classify on average even for stronger random perturbations. On the other hand, for Zhen loss, of seems be responsible for tuning the robustness, with little relation d. This dependence on o can be understood by Randomized Smoothing employing only of to quantify the robustness with no direct enforcement the non-smoothed worst-case.
In figure 3 we show the colormap of the AUCCR,, through Randomized Smoothing (Cohen et al.) 2019 Interestingly, different from figure 2 in which adversarial robustness with respect to the margin certified radius and noise robustness indicates different kinds of robustness, we see that indeed the Smoothed Robust- ness, as captured by Randomized Smoothing, bridges adversarial and noise robustness, with regions of higher robustness in between the regions of higher adversarial and noise robustness.
4.3 Robustness comparison
Since a highly robust classifier has lower clean accuracy, and vice versa, to compare the robustness improve- ment we restrict the parameter pairs with clean accuracy within a range Acc + A and select the ones with highest AUCoRi, for Randomized Smoothing certified radius, since we saw that it nicely merges worst- and average-case. In figures 4 and show the robustness curves from the robustness metrics described in

---

Published in Transactions on Machine Learning Research (04/2024)
MSCR
Zhen
30-
3.5
25-
201
Smoothed Robustness
2.0
10
1.0
6.72
10
10
10
10a
10
10
Figure 3: Heatmap of AU AUCR, of certified radius obtained through Randomized Smoothing Cohen el al. 2019 for MSCR and Zhen losses. The colormaps share the same maximum and minimum.
Appendix B for conditions 98.5 + 0.3 (i.c., non-clean accuracy degradation case) and 95.5 + 0.3 (i.c., clean
accuracy degradation case), respectively, for MNIST dataset.
MSCR id 1.0. 100.
Safe samples (%)
Safe samples (%)
Zhen (d' 15.0. o2 0.08)
MSCR (d- 0.11
20-
Zhen (d' 15.0. 0.08
a)
Certified radius (Margin)
b)
Certified radius (RS)
Correctly classifted (%)
183-
1.0.
Correctly classified (%)
MCN d 1.0
**-
15.0.
40-
MSCR 1.0. 0.13
MCR d-0
23
2ben 15.0. 0.00:
625.
6/2s 122 100
2,00
86
24
28
30
Inpul noise std (0₂)
d)
Linear corruption SSNR
Figure 4: Robustness comparison for MNIST dataset between MSCR, MCR. and Zhen losses for the highest AU AUCOR,, for Randomized Smoothing within 0..3 (%) clean accuracy. For (a) and (b) the vertical axis is the amount of safe samples, horizontal axis is the cortified radius for margin CR and Randomized Smoothing CR, respectively; For (c) and (d) the vertical axis the accuracy, and horizontal axis the perturbation intensity of Gaussian noise (c) and Linear image corruption (d). The dashed horizontal and vertical lines in (d) indicate the approximate 50% performance drop point humans from Jang al. (2021). Each curve is the average of three trainings, and the error bars are shown.
In Figure 4 we that the MSCR loss achieves the highest adversarial (a and b) and noise (c) robustness and linear corruption (d) robustness similar to the Zhen loss. Interestingly, while the usual non-smoothed margin loss (MCR) achieves higher adversarial robustness than does the Zhen loss (a and b), it has similar noise robustness (c) and worse lincar corruption robustness (d). The main takcaways here are, first, how even the MCR loss is more adversarially robust compared to the Zhen loss, both in terms of the margin and Randomized Smoothing certified radius. Second, smoothing the margin significantly improves its noise robustness, expected, and slightly improves its adversarial robustness. Third, even though the Zhen loss showed lower adversarial and noise robustness than did the MSCR, showed slightly better linear image corruption robust similar to what would expect human subjects to achieve. These differences
10

---

Published in Transactions on Machine Learning Research (04/2024)
MSCR (d 3,5,03
Safe samples (9%
MCR 3.5
Safe samples (%)
Zhan o5 0.161
MSCR (d (d.3.5.0 -
d.5
Zhen (d 30.0.0 0.16)
a)
b)
Certified radius (Margin)
Certified radius (RS)
Correctl classified (%)
100
MSCR (d' 0.00)
0.01)
Correctly classified (%)
100-
Zhon (d' 30.0. of 0.16)
07-
43
MSUR (a 3.5. 0.001
MCR d=
(5 30.00.0 0.16)
0.20
0.50
0.75
1.25
1550
1.7
1.00
80
00
2.
10
Input noise std (a,)
d)
Linear corruption SSNR
Figure 5: Robustness comparison for MNIST dataset between MSCR, MCR and Zhen losses for the highest AUCoR,,, for Randomized Smoothing within 9.3 (%) clean accuracy. For (a) and (b) the vertical axis is the amount of safe samples, horizontal axis is the certified radius for margin CR and Randomized Smoothing CR, respectively; For (c) and (d) the vertical axis is the accuracy, and horizontal axis the perturbation intensity of Gaussian noise (c) and Linear image corruption (d). The dashed horizontal and vertical lines in
(d) indicate the approximate 50% performance drop point in humans from Jang el al. (2021) Each curve is the average of three trainings, and the error bars are shown.
demonstrate that evaluating classifier's robustness is not trivial and that no single metric rules out classifier as the most robust one.
Now from figure 5 different from the previous case, we observe that MSCR and MCR losses behave more similarly, with an overall slight improvement robustness for the MSCR loss the noisy (c) and linear corruption (d) settings. In particular, the Zhen loss showed an improvement its noise (c) and Random- ized Smoothing (b) robustness, with the former surpassing the MSCR and MCR losses, at the expense of higher training variance, as shown by the error bars, and decreased margin robustness (a). For the sake of completeness, we show the curves obtained for the other losses continuous lines in Figure 0
The robustness obtained with these other losses (given similar clean accuracy) was, for all cases, lower than or similar to that obtained with MSCR (contimuous green) or MCR (dashed green) losses. Curiously, we found that the Multiclass Hinge loss (MH), widely used in the robustness literature, yields a performance similar to that of the SCE, which docs not enforce any kind of robustness. The SC-SCE loss is a simple alternative to probability-based losses (as in Randomized Smoothing); however, found that, at least under the 1-Lipschitz constraint, there is large decrease in clean accuracy, with best accuracy of 95.6%, making it an unsuitable choice.
4.4 CIFAR-10 experiments
For the MNIST experiments carried grid search over all losses' hyperparameters: however, due to computational constraints, we trained NNs on CIFAR-10 only for the MSCR, MCR and Zhen losses. Addi- tionally, instead of a grid search, we found the best, combination of hyperparameters by first picking values close to those from the 98.5 0.3 results and changing them to neighboring values. Because the architecture used was relatively small (Appendix C) and therefore of low capacity, we noticed that the clean accuracy did not exceed 64%, so we selected the hyperparameters for the best adversarial robustness with clean accuracy 62.5 + 0.2. The obtained accuracy curves in figure 7
11

---

Published in Transactions on Machine Learning Research (04/2024)
MSCR MCR
Safe samples (9%
Safe samples (%)
Zhen
MH
SC-SCE
MSCR
MCR
20
MH SCE
SC-SCB
a)
22
b)
Certified radius (Margin)
Certified radius (RS)
Correctl classified (%)
100
MSCR
Correctly classified (%)
100-
MSCR MCR
MCR
Zhea
MH
MH
SCE
SCE SC-SCE
0.20
0.50
0.75
1.20
1.50
1.70
3.00
80
14 05 Linear corruption SSNR
10
Input noise std (ax))
d)
Figure 6: Robustness comparison for between all losses described Section 4.1 for the highest AUCeR, for Randomized Smoothing within 95.5 + 0.3 (%) clean accuracy. For (a) and (b) the vertical axis is the amount of safe samples, horizontal axis is the certified radius for margin CR and Randomized Smoothing CR, respectively; For (c) and (d) the vertical axis is the accuracy, and horizontal axis the perturbation intensity of Gaussian noise (c) and Linear image corruption (d). The dashed horizontal and vertical lines in (d) indicate the approximate 50% performance drop point in humans from Jang el al. [2021) Each curve is the average of three trainings, and the error bars are shown.
From the two left plots we see that the curves for MSCR and MCR overlap for the margin certified radius but MSCR improved over MCR for noise robustness. This indicates that while the hyperparameter contributes to the margin, the of contributes to noise robustness. And indeed, we see improvement of MSCR under Randomized Smoothing robustness. On the other hand, Zhen loss obtained a much higher noise robustness (c), and a slightly better linear corruption robustness (d), but at the cost of lower adversarial robustness (a) and (b).
5 Discussion
Motivated by recent attempts in bridging worst- and average-case robustness analyses of classifiers, in the present work, we employed the smoothed analysis framework of complexity of algorithms to propose the Smoothed Robustness Analysis (SRA) framework, which includes Randomized Smoothing as a special case when the 0-1 loss is its performance metric (Sec. 2). Considering the argument from the smoothed analysis literature that the noise variance should be small, which cannot be achieved by the usual Randomized Smoothing, proposed the margin loss as more suitable performance metric for SRA and derived the Margin Smoothed Certified Radius (MSCR), which is expected to be a more reliable robustness certification as it does not vanish for small noise variances (Sec. 3). To validate the proposal, we conducted experiments to maximize the MSCR and showed improvements in both adversarial and noise robustness (Sec. 4 Here, we discuss the interpretations and limitations of the work and outline possible future directions.
5.1 Multiclass hinge losses
We proposed the margin loss defined by the difference between the largest incorrect and correct outputs as a suitable performance metric for SRA.. Because the margin provides simple proxy of the distance the decision boundary, it has been widely used in the context of margin maximization as regularization Tsuzuku et al. 2018 Zhang et al. 2021 Other works proposed the use of summation of all pairwise dif-
12

---

Published in Transactions on Machine Learning Research (04/2024)
MSCR (d-
MSCR 1.0. 0.0011
Safe samples (9%
MCR d 1.0
MCR d= 1.0
Zhen 4.0,0 4.0,05-0.00011
(d 4.0, 0z
Safe samplee 0
25
19
a)
b)
Certified radius (Margin)
Certified radius (RS)
Correctly classified (%)
MSCR (d (d-1.1.,00..0....dd 10
Correctly classified (%)
MCR d= 1.0
Zhon id - 4.0, of 0.0000
40-
MSUR 1.0. 0.001)
MCR d= 1.0
(d 4,0.00 0.00011
10
14 66
6o 10
66
62 04 de
do
10
c)
Input noise std (a,)
d)
Linear corruption SSNR
Figure 7: Robustness comparison between MSCR, MCR and Zhen losses for the highest AUCents for Rondomized Smoothing within 0.. (%) clean accuracy on CIFAR-1O.. For (a) and (b) the vertical axis is the amount of safe samples, horizontal axis is the certified radius for margin CR and Rondomized Smoothing CR, respectively; For (c) and (d) the vertical axis is the accuracy, and horizontal axis the perturbation intensity of Gaussian noise (c) and Linear image corruption (d). The dashed horizontal and vertical lines in (d) indicate the approximate 50% performance drop point in humans from Jang el al. 2021 Each curve is the average of three trainings, and the error bars are shown.
ferences between incorrect and correct outputs as the loss to improve the robustness of Lipschitz-connstraindd networks (Anil et al., 2019 Li et al. 2019b). Since, in our experiments, the networks trained with the latter (MH) showed lower robust.ess than those trained with the former (MCR) (fig. G). we discuss the reasons for this difference and possible future directions related to the use of other more suitable losses.
Both margin losses are part of a larger group of large margin losses from the support vector machine literature called multiclass hinge losses. Vaannk (1998) and Weston & Watkins (1999) independently proposed extending the binary hinge loss the multiclass case by taking the sum of pairwise differences between correct and incorrect outputs, in which the MH loss is special case. Until then, multiclass SVMs were treated CC- binary SVMs between all outputs, where |C| is the number of classes, which resulted in a larger computational overhead. Crammer & Singer (2001] then proposed a simplified multiclass hinge loss that depends only on the difference between the correct class output and the largest incorrect, i.e., the margin loss in our work.
To better understand the statistical learning properties of these losses, Zhang (0044) showed that these two losses are not Fisher consistent, i.e., in the infinite sample limit, the index of the largest output is not necessarily the index of the correct posterior classification probability of the Bayes classifier. More precisely, the MH loss is consistent if the probability of the correct output is greater than 0,5 or if the probability of the sccond largest is less than [C]: and the margin loss is consistent only if the probability of correct classification is greater than 0.5. This result is related to our finding that as long as the smoothed margin is negative, the probability of correct classification is greater than 0.5, but not determined otherwise.
1
Since this consistency is generally a desirable feature, Liu 2007 proposed using a modification of the margin loss to make it consistent by truncating the margin loss so that stops increasing at some value. The truncated margin loss can be written as the difference between the usual margin loss and shifted margin
loss byMs (xx c, d) = Ear(x, (z, e, d) (2, c, dd) ReLU(d + (z) - ox(x)) ReLU(-d + (om(z) (z(x)) and it has maximum of 2d when the margin for input is on (m)) (z) d. Wu & Liu 2007 used
13

---

Published in Transactions on Machine Learning Research (04/2024)
this loss to improve the accuracy of multiclass SVMs to ignore sample outliers, hence possible direction is to obtain an approximation of the smoothed truncated margin loss, similar to the one from the present work, and verify whether it helps in the robustness-accural trade-off by ignoring few samples that might contribute heavily to the loss.
A recent work by Delattre al. (024)) improves Randomized Smoothing CR by using the Lipschitz constant of the classifier together with the sparsemar function. Sparsemax was proposed by Martins et al. (2016) (almost everywhere) differentiable embedding on the simplex, like the softmax, but with most values zero, hence the sparse. They show that for the binary case, sparsemax is the "'hard' sigmoid",, i.., 0 valued, then linear, until it reaches 1. Subtracting this value from 1 for the binary case Icads to a truncated hinge loss, similar to the one in the SVM literature. Whether there is direct connection between them we leave for future investigations.
Here we add that, unlike Dogan et al. (2016). who empirically showed in several datasets that the MH loss, for the case of support vector machines, has better accuracy than other hinge losses, we found the margin found the MCR loss to significantly improve the overall
(MCR) loss to perform better. Interestingly, robustness compared to other usual losses, but also to be unstable if used on unconstrained NNs. Hence, it might be the best cost-perfor rest-perorraace option for improving robustness in Lipschitz-constrained NNs.
5.2
Robustness-accuracy trade-off
In Section 4.2 we showed that, by tuning the hyperparameters d and o² we achieve different degrees of adversarial and noise accuracy, respectively, at the cost. of clean accuracy. Although this robustness- accuracy trade-off has been widely demonstrated (e.g. Su et al., 2018 Cohen et al. 2019 Li et al.) 2019a to the best of our knowlodge, only Laugros et al.] (2019) showed evidence of adversarial and noise robustness corresponding to two different kinds of robustness, i.e., a model robust to AEs is not necessarily robust to random perturbations and vice versa. Using losses with parameters that explicitly account for these two robustness, provide additional evidence for the findings of Laugros et al. (2019).
We also point out that while early works defended that this trade-off is unavoidable Tsipras et al. 2019 Zhang et al. 2019), recent accounts favor the idea that this is a consequence of model limitations Stutz et al. 2019 Olfat & Aswanil 2020; Yang et al. 2020 Leino et al.) 2021 Li et al. 2022). More specifically,
recent works argue that enforcing a tight global Lipschitz constant (Richardson Weiss 2021) and proper
loss hyperparameter selection (Béthune et al., 2022 in Tipschitz-consstrained networks can suffice to avoid this trade-off. Given the 1-Lipschitzness of the networks in the present work and that methods for exact caleulation of Lipschitz constants of feedforward ReLU neural networks are known (Jordan & Dimakis 2020; Bhowmick et al. 2021), we leave for future work the computation of the constants of the trained networks to verify whether they correlate with the robustness-accuracy gap.
Despite intensive efforts, we still need a definitive solution to the problem of adversarial robustness. Recent works show evidence that top-down information about context and expectation improves general classification
robustness (Huang et al.) 2020 Alamia et al.) 2023). indicating that this might play central role in achieving the robustness observed in biological brains. From the neuroscience side, recent work by Guo et al. (2022) showed that robust networks are sensitive to ad adversarial attacks similar to those measured in primate brains, hypothesizing that an error correction mechanism might be involved. Thus, future works that address this trade-off should take into consideration this possible limitation of foedforward neural networks.
5.3 Relationship to 'intermediate-q' robustness
We mentioned how SRA connects to Randomized Smoothing in the case of the 01 loss. The work by Rice & Bair (2021) proposes a method to study 'intermediate-g robustness' that bridges these two cases based on the 1 noor of smooth loss f(x,c) c) over a measure μ(z) that depends on input x.
[[((,, ((la,,))lll)) = [ .c)
(10)
Their method considers the usual definition of losses as nonnegative scalar functions, so /((x''c) f(x', .c). When q - and ((z) is uniform ball, one obtains the worst-case, ie., the maximal loss within the ball.
14

---

Published in Transactions on Machine Learning Research (04/2024)
When q 1, this expression gives the average loss on the measure μlz)). The connection of SRA with this method is that the averaging step from SRA generates a smooth function [( c) = B being loss not necessarily smooth, and then SRA (for nonnegative losses) can be written in this norm approach as
(f)) (ãr, c)}, (xx,c)
((a()))) ((()) p(x) c()
(11)
The main difference between SRA and the method Rice & Bair 2021 is that while the former incorporates the worst and average cases as two axes, one controlled by the size of the worst-case region Q(x)) C and the other by the variance of the smoothing distribution p(z); the latter combines them as two extremes in a spectrum. Additionally, SRA characterizes the robustness of a classifier by stating whether is "safe" under choice of noise distribution and adversarial region given some loss. Then, robustness comparison is done by evaluating which classifier is safe for larger regions (e.g. larger certified radius) and input variances. The approach based on the l norm acts as a robustness metric, in which by choosing the norm and measure, in theory, a classifier with larger 4--nrrm is more robust.
5.4 Limitations and other future directions
Given the nature of this work as a first exposition of Smoothed Robustness Analysis, our experiments were limited only to 1-Lipschitz fully connected and convolutional neural networks under isotropic Gaussian noise, dealing with 12-norm radius certification. Future works with margin SRA, therefore, should consider other noise distributions and estimation methods of the smoothed margin that do not require the assumptions of symmetry and independence of outputs, thus allowing its application to NNs other than 1-Lipschitz. A lower bound on the margin certified radius that takes into account the complex relationship between pairwise margins, in line with the soft margin proposed by Fazlyab et al. (2023). is another possible direction.
Although we obtained improvements in noise robustness with MSCR compared to MCR on CIFAR-10 while maintaining its clean accuracy and adversarial robustness, the difference was more subtle than that for MNIST. We hypothesize that for larger CNNs that achieve higher clean accuracy smoothing more beneficial, since overparametrized models tend to have more complex geometries. Due to time constraints, we leave this open question.
Finally, since smoothed analysis was originally proposed to capture the algorithmic complexity observed in practice, another possible diroction to test the SRA as a mcasure of neural network complexity. Intuitively, when comparing multiple classifiers under the same loss given the same input region Omega and distribution rho, the one with the smallest average (over test samples) SRA has a decision boundary that better separates unseen data even under small noise, This might be related the notion of compression from information bottleneck (Shwartz-Ziv Ziv & Tishby| 2017), in which neural networks that correctly classify inputs with more noise better compress their relevant information, resulting in lower model complexity. SRA may contribute to clucidating the connection between robustness and complexity.
References
Andrea Alamia, Milad Mozafari, Bhavin Choksi, and Rufin VanRullen. On the role of feedback in image recognition under noise and adversarial attacks: A predictive coding perspective. Neural Networks, 157: 280 287, 2023.
Brendon G. Anderson and Somayeh Sojoudi. Data-Driven Certification of Neural Networks With Random Input Noise. IEEE Transactions on Control of Network Systems, 10(1):249 2009922600000 2023.
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. Proceedings of the 36th International Conference Machine Learning,, 2019.
Alexandre Araujo, Aaron Havens, Blaisc Delattre, Alexandre Allauzen, and Bin Hu. A Unified Algebraic Perspective on Lipschitz Neural Networks. 11th International Conference on Learning Representations, October 2023. arXiv:2303.03169 [cs].
15

---

Published in Transactions on Machine Learning Research (04/2024)
Reinaldo B. Arellano-Vall and Mare G. Genton. On the exact distribution of the maximum of absolutely continuous dependent random variables. Statistics & Probubility Lelters, 78(1):27-3)) 35, January 2008. ISSN 01677152. doi: 10.1016/j..sl..207.04... 20...0.........1........ URL https://Linnkinghub elsevier www.eeereccereeeeee/piiii.
501677152070016781
Rianne van den Berg, Lconard Hasenclever, Jakub M. Tomezak, and Max Welling. Sylvester Normaliz- ing Flows for Variational Inference. In Proceedings of the 34th Conference in Uncerlainly in Artificial Intelligence, 2019.
Aritra Bhowmick, Meenakshi D'Souza, and G. Srinivasa Raghavan. LipBaB: Computing Exact Lipschitz Constant of ReLU Networks. In Igor Farkaš, Paolo Masulli, Sebastian Otte, and Stefan Wermter (eds.); Artificial Neural Networks and Machine Learning ICANN 2021, pp. 151 162, 2021.
Patrick Billingsley. Probabilily and measure. Wiley series in probability and mathematical statistics. Wiley,
New York, 3rd ed edition, 1995.
A. Björck and C. Bowie. An Iterative Algorithm for Computing the Best Estimate of an Orthogonal Matrix. SIAM Journal on Numerical Analysis, 8(2):358-30) 364, 1971.
Avrim Blum and John Dunagan. Smoothed Analysis of the Perceptron Algorithm for Linear Programming.
In Proceedings of the 13th annual ACM-SIAM symposium on Discrete algorithms, pp. 10, 2002.
Louis Béthune, Thibaut Boissin, Mathieu Serrurier, Franck Mamalet, Corentin Friedrich, and Alberto González-Sane Sanz. Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural net- works. 36th Conference on Neural Information Processing Systems, 2022.
C. K. Chui. An introduction to wavelets. Number v. 1 in Wavelet Analysis and Its Applications. Academic Press, Boston, 1992. ISBN 978-0-12-17458844.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval Net- works: Improving Robustness to Adversarial Examples. Proceedings of the 34th International Conference on Machine Learning, 2017.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified Adversarial Robustness via Randomized Smoothing, Proceedings of the 36th International Conference on Machine Learning, 2019.
Thomas H. Cormen (ed.). Introduction to algorithms. MIT Press, Cambridge, Mass, 3rd ed edition, 2009.
Nicolas Couellan. Probabilistic robustness estimates for feed-forward neural networks. Newral Networks, 142:138-18 147, 2021.
Koby Crammer and Yoram Singer. On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines. Journal of Machine Learning Research, 2001.
Blaise Delattre, Alexandre Araujo, Quentin Bartheleny, and Alexandre Allauzen. The Lipschitz- Variance- Margin Tradeoff for Enhanced Randomized Smoothing. 12th International Conference on Learning Rep- resentations, February 2024. SIIV:22009.16888 [cs, stat].
Lipschitz-Variance-
Crun Dogan, Tobias Glasmachers, and Christian Igel. Unified View on Multi-class Support Vector Clas- sification. Journal of Machine Learning Research, 2016.
Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Robustness of classifiers: from adversarial to random noise. 30th Conference on Newral Information Processing Systems, 2016.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J Pappas. Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks. 33rd Conference on Neural Infor- mation Processing Systems, 2019.
Mahyar Fazlyab, Taha Entesari, Aniket Roy, and Rama Chellappa. Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization. 37th Conference on Neural Information Processing Systems, November 2023. arXiv:2310.0011 [os).
16

---

Published in Transactions on Machine Learning Research (04/2024)
Jean-Yves Franceschi, Alhussein Fawzi, and Omar Fawzi Robustness of classifiers to uniform Stell' and Gaussian noise. In Proceedings of the 21st. International Conference on Artificial Intelligence and Statistics, 2018.
Chong Guo, Michael J Lec, Guillaume Loclere, Joel Dapello, Yug Rao, Alcksander Madry, and James J DiCarlo. Adversarially trained neural represent ations may already be as robust as corresponding biological neural representations. Proceedings of the 39th International Conference on Machine Learning, 2022.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed Analysis of Online and Differentially Private Learning, 34th Conference Newral Information Processing Systems, 2020.
Kai Hu, Andy Zou, Zifan Wang, Klas Leino, and Matt Fredrikson. Unlocking Deterministic Robustness Certification on ImageNet. 37th Conference on Newral Information Processing Systems, October 2023. arXiv:2301.1244 [cs].
Yujia Huang, James Gornet, Sihui Dai, Zhiding Yu, Tan Nguyen, Doris Y Tsao, and Anima Anandkumar. Neural Networks with Recurrent Generative Foedback. 34th Conference on Neural Information Processing Systems, 2020.
Hojin Jang, Devin MeCormack, and Frank Tong. Noise-trained deep neural networks effectively predict human vision and its neural responses to challenging images. PLOS Biology, 19(12):c3001418, 2021.
Matt Jordan and Alexandros G. Dimakis. Exactly Computing the Local Lipschitz Constant of ReLU Net- works. 34th Conference on Neural Information Processing Systems, 2020.
Kautsky and Turcajov. matrix approach to discrete wavelets. C. K. Chui, Laura Montefusco, and Luigia Puccio (eds.), Wavelets: theory, algorithms, and applications, number v. in Wavelet Analysis and Its Applications, pp. 117-135. Academic Press, San Diego, 1994. ISBN 978-0-12-174576-2.
Diederik P. Kingma and Jimmmy Ba. Adam: A Method for Stochastic Optimization. 5th International Conference Leurning Represenlations, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alfred Laugros, Alice Caplier, and Matthieu Ospici. Are Adversarial Robustness and Common Perturbation Robustness Independent Attributes In 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW), 2019.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann. lecun com/exdb/mnist
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified Robustness to Adversarial Examples with Differential Privacy. In 2019 IEEE Symposium on Security and Privacy, pp. 656-672, 2019.
Klas Leino, Zifan Wang, and Maut Fredrikson. Globally-Robust Neural Networks. 38th International Con- ference on Machine Learning, June 2021. a2Xiv:2102.08452 [cs, stat].
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified Adversarial Robustness with Additive Noise. 33rd Conference on Newral Information Processing Systems, 2019a.
Binghui Li, Jikai Jin, Han Zhong, John E Hopcroft, and Liwei Wang. Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power. 36th Conference on Neural Information Processing Systems, 2022.
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger Grosse, and Jörn-Henrik Jacobsen. Prevent- ing Gradient Attenuation in Lipschitz Constrained Convolutional Networks. 33rd Conference on Neural Information. Processing Systems, 2019b.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Yuezun Li, Cong Zhang, Honggang Qi, and Siwei Lyu. AdaNI: Adaptive Noise Injection improve ad-
versarial robustness. Computer Vision and Image Underslanding, 238:103855, January 2024. ISSN
10773142. doi: 10.016/j.ciu.2233103555. URL https://Linkknghuubbenn herrgghuuelsseieeeee elsevier...... $10773142280028877
Yufeng Liu. Fisher Consistency of Multicalegory Support Vector Machines. Proceedings of the 11th International Conference on Artificial Intelligence and Statistics, 2007.
Max Losch, David Stutz, Bernt Schiele, and Mario Fritz. Certified Robust Models with Slack Control and Large Lipschitz Constants, September 2023. arXiv:2309.0616: [cs, stat].
Nya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. 5th Interna- lional Conference on Learning Represenlations, 2017.
Andre Martins, Ramon F Astudillo, and Andre Martins. From Softmax to Sparsemax: A Sparse Model Attention and Multi-Label Classification. Proceedings of the 33 rd International Conference on Machine Learning, 2016.
Laurent Meunier, Blaise J. Delattre, Alexandre Araujo, and Alexandre Allauzen. A Dynamical System Perspective for Lipschitz Neural Networks. Proceedings of the 39th International Conference Machine Learnäng, pp. 15484-15500, June 2022. ISSN: 2640-3498.
Jeet Mohapatra, Ching- Yun Ko, Tsui Wei, Weng, Sijia Liu, Pin-Yu Chen, and Luca Daniel. Hidden Cost Randomized Smoothing. In Proceedings of the 24th International Conference on Artificial Intelligence and Stalislics, 2021.
Jorge Navarro and Jorge M Arevalillo. On connections between skewed, weighted and distorted distribu- tions: applications to model extreme value distributions. TEST, 32(4):1307-1335, December 2023. ISSN 1133-0686, 1863-8260. doi: 10.1007/111448-033-00777 URL https://link.. http:///iiinnsssiiggrrrrree springer com/10.1007. 611749-023-008744
Matt Olfat and Anil Aswani. Average Margin Regularization for Classifiers. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 3194-3199, 2020.
Leslie Rice and Anna Bair. Robustness between the worst and average case. 35th Conference on Neural Information Processing Systems, pp. 12, 2021.
Fitan Richardson and Yair Weiss. A Bayes-optimal view adversarial examples. Journal of Machine Learning Research, 2021.
Klaus Ritter. Average-case analysis of numerical problems. Number 1733 in Lecture notes in mathematics. Springer, Berlin; New York, 2000.
Alexander Robey, Luiz F. O. Chamon, George J. Pappas, and Hamed Hassani. Probabilistically Robust Tearning: Balancing Average- and Worst-case Performance. Proceedings of the 39th International Confer- ence on Machine Learning, 2022.
Tim Roughgarden. Beyond the Worst- Case Analysis of Algorithms. Cambridge University Pross, Cambridge, 2021.
Ravid Shwarlz-Ziv and Naftali Tishby. Opening the Black Box of Deep Neural Networks via Information, April 2017. URL
arXiv:1703.008// [cs].
Sahil Singla and Soheil Feizi. Skew Orthogonal Convolutions. 38th International Conference on Machine Learning, June 2021. arXiv:2105.11417 [cs].
Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on CIFAR-10 and CIFAR- 100. 10th International Conference Learning Representations, March 2022. arXiv:2108.04082 [cs].
18

---

Published in Transactions on Machine Learning Research (04/2024)
Daniel A. Spielman and Shang- -aang--Haaaa Teng. Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Journal of the ACM, 2004.
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM, 52(10):76 84, 2009. ISSN 0001-0782, 1557-7317. doi: 2..115/1162764.116
David Stutz, Matthias Hein, and Bernt Schiele. Disentangling Adversarial Robustness and Generalization. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6969-6980 2019.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Yu Chen, and Yupeng Gao. Is Robustness the Cost of Accuracy? - A Comprehensive Study on the Robustness of 18 Deep Image Classification Models. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Compuler Vision ECCV 2018, volume 11216, pp. 644-666 661, 2018
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, February 2014. arXiv:1312.6199 [cs].
6199.
Karim Tit and Teddy Furon. Efficient Statistical Assessment of Neural Network Corruption Robustness. 35th Conference on Neural Information. Processing Systems (NeurIPS 2021), pp. 11, 2021.
Asher Trockman and J. Zico Kolter. Orthogonalizing Convolutional Layers with the Cayley Transform. 9th International Conference on Learning Representations, April 2021. arXiv:2104.07167 [cs, stat].
Yu-Lin Tsai, Chia-Y Yi Hsu, Chia-Mu Yu, and Pin-Yu Chen. Non-Singular Adversarial Robustness of Neural Networks. In 2021 TEFE International Conference on Acoustics, Speech and Signal Processing, pp- 3840- 3844, Toronto, ON, Canada, June 2021a. IEEE. ISBN 978-1-72817-605-5, doi: 10.1 10. D0.110//CAASSP3922.. 2021.9414325.
Yu-Lin Tsai, Chia-Mu Yu, Chia-Yi Hsu, and Pin-Yu Yu Chen. Formalizing Generalization and Adversarial Ro- bustness of Neural Networks to Weight Perturbations. 35th Conference Neural Information Processing Systems, 2021b.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness May Be Odds with Accuracy. Proceedings of the 37th International Conference on Machine Learning, 2019.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks. 32nd Conference on Neural Information Processing Systems, 2018
Vladimir Naumovich Vapnik. Statistical learning theory. Adaptive and learning systems for signal processing, communications, and control. Wiley, New York, 1998.
Ruigang Wang and Ian R Manchester. Direct Paramoterization of Lipschitz- Bounded Deep Networks. Pro- ceedings of the 40th International Conference on Machine Learning, 2023.
Tsui- Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Duane Boning, Inderjit S. Dhillon, and Luca Daniel. Towards Fast Computation of Certified Robustness for ReLU Networks. Proceedings of the 35th International Conference on Machine Learning, 2018
Tsui- Wei Weng, Pin-Yr Chen, Lam M Nguyen, Mark S Squillante, Akhilan Boopathy, Ivan Oseledets, and Luca Daniel. PROVEN: Verifying Robustness of Neural Networks with Probabilistic Approach.
Proceedings of the 36th International Conference on Machine Learning, pp. 10, 2019.
Jason Weston and Christopher Watkins. Support Voctor Machines for Multi-Class Pattern Recognition. In
The European Symposium on Artificial Neural Networks, 1999.
19

---

Published in Transactions on Machine Learning Research (04/2024)
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. Proceedings of the 35th International Conference on Machine Learning, 2018.
Anqi Wu, Sebastian Nowozin, Edward Meeds, Richard E. Turner, José Miguel Homandez-Lobatten and Alexander L.. Gaunt. Deterministic Variational Inference for Robust Bayesian Neural Networks. 7th International Conference on Learning Representations, 2019.
Yichao Wu and Yufeng Liu. Robust Truncated Hinge Loss Support Voctor Machines, Journal of the American Statistical Association, 102(479):974 983, 2007.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S Schoenholz, and Jeffrey Pennington. Dy- namical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks. Proceedings of the 35th International Conference on Machine Learning, 2018.
Xiaojun Xu, Linyi Li, and Bo Li. LOT: Layer-wise Orthogonal Training on Improving 8' (ell 2$ Certified Robustness, 36th Conference on Newral Information Processing Systems, 2022. arXiv:2210.1162) [cs, stat].
Yua Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaudhuri. A Closer Look at Accuracy vs. Robustness. 34th Conference on Neural Information Processing Systems, 2020.
Tan Yu, Jun Li, Yunfeng Cai, and Ping Li. Constructing Orthogonal Convolutions In An Explicit Manner. 10th International Conference on Learning Represenlations, 2022.
Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwci Wang. Towards Certifying Linf Robustness using Neural Networks with Linf-dist Neurons. Proceedings of the 38th International Conference on Machine Learning, pp. 12, 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Fric P Xing, Laurent El Ghaoui, and Michael T Jordan. Theoretically Principled Trade-off between Robustness and Accuracy. Proceedings of the 36th International Conference Machine Learning, 2019.
Tong Zhang. Statistical Analysis of Some Multi-Category Large Margin Classification Methods. Journal of Machine Learning Research, 2004.
Xingjian Zhen, Rudrasis Chakraborty, and Vikas Singh. Simpler Certified Radius Maximization by Propa- gating Covariances. Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp. 10, 2021.
A Proofs and derivations
A.1 Relation of smoothed margin and classification probability
Proposition 3. Let the output layer oxx) of classifier be continnous and symmetrically distributed, i.e., the marginal distribution of i-th dimension ox(x) is symmeeticcaly distributed. If Be' LM c)] 0, then the probabilily of correct classification Pa(a; p(-)) > 0.5.
Proof. We have the following inequality for the smoothed margin (xx(x,,;pp)) of continuous and symmet- rically distributed outputs,
(x e; p(-)) = Ex'npta.0 0)
|max o,(2') - Pe > med[mmx (x)) Me med (x(3)) - mæ)(o ifc
ifc
ifc
where Me is the mean correct output, med[.] refers the median, the inequality step holds in the case of
continuous symmetrically distributed outputs since the distribution of max (x) is positively skewed 2 which
s
We refer to Arellano-Vall Valle & Genton statistics
2008 Navarro Arevalillo 2023) for detailed account on analysis of order
20

---

Published in Transactions on Machine Learning Research (04/2024)
means that (x)-a((z0)) [max (xx)) isfe
med[max (z))), and Me med[o<(x)) since oz(x) is symmetrically sypee
distributed.
If the difference between the two medians is negative, then the probability of ox(x) max (z is greater
ifc
than 0.5. Therefore, if (xxxx,, O, the probability of correct classification is greater than 0.5. ]
A.2 Smoothed radius certification with margin function
Here we derive a certified radius of smoothed Ky-Tipschitz classifier based on the margin function. First show that the margin of such classifier is 2 Kp-Lipschitz, where g + = 1, then we use the result that the smoothed form of a scalar K K-Lipschitz function is also K-Lipschitz to arrive at the certified radius of a smoothed classifier e, (z; p(-) Lx (2.0:
27
Proposition 5. The margin function (xx e) of Ky-Lipschitz classifier with fixed e is 2 K Lipschitz, where 9 + 1 =1
Proof. To prove this proposition, we first need to show that the margin as a function the output o(z) is 2i-Lipschitz, then we finish the proof by using the composition of Lipschitz functions. First, the margin Cm (x, c) (x))=o((()) can be written as Lm (I,c) = Ve.m o(z). where vr,m is a vector with at position -1 at position c, and 0 elsewhere. Then, from the definition of Lipschitz continuity, we need to find an œ1, 22 E X that is proportional upper bound on (21, Las (22, c) = [ee., o(x1) - Ve,ma o(x2)) 21, to ||z| - =21lp-
Then the following inequality holds,
(cM((1,e)) La (ar, c)l |Ue.m 0((1)) Ue,mz -(x2)) I Ve,mar o(x1) Vemmu o(x2)
Do,mar (o(x1) o(x2))
(12)
S Memmr 11, ||((m)) - o(x2))lp
2 [[o(;)) - o(x2))lp:
where my arg argmaxx (I;) and M = arg max vic, m:) o(z:). The first inequality holds since, if mM mi. iE(1.2)
E
then v(c, m1) 0xx1) 2 r(c, m²) ) o(x2) 2 r(c, m1) o(x2), therefore lu(e, mn) o(x1) - v(c, m2) o(x2) S
le(c, mi) o(x1) - v(c, m1) ox22) (if mM my the indices 1 and 2 are exchanged). The second inequality is due to Holder's inequality Ifgl llflly ||lllp- where + =. We have the last equality because
|| [12 = (19 + 1 = (2 19) 2
Using inequality 12 and the fact that the classifier is Ki-Lisschitz, iee,, [|o(x)) (ikee)--a o(x2)llp S Kp || we finally have L (Z), Lm (02, c)) < 2 K₂ || æ2l1p
22 lp
Corollary 5.1 (Margin-based certified radius). For a correclly classified inpul x. = Lm((ae) is lower 29 K2
bound on the norm of the minimal perturbation ō E X required to make LM + + = 0. In other words, the classifier correctly classifies x to all perturbations
s.t. ||ō|| <E
To see this, we first note that (M( c) < 0 since x is correctly classified. Second, a minimal successful adversarial perturbation implies LM (x + 8,c) = O. By substituting both in the Lipschitz inequality we have LMr(,, e = -ar (x, < 2 K, || which implies that the minimal successful perturbation has norm || 2 (u( Conversely, any perturbation less than that lower bound is guaranteed to not result in misclassification.
K
To proceed, we need to prove that the smoothed form of a K K-Lipschitz function due the application of random noise is also K-Lipschitz. For this the following definition of smoothed function:
21

---

Published in Transactions on Machine Learning Research (04/2024)
Definition 1. The smoothed form of function F X Y by convolution with probability density function p(:: 0) parometrized by 0 is
F (x;;0) = /
dtp(t;0)F(zz - t).
B
Then we have the following proposition about the lipschitzness of smoothed scalar function: Proposition 6. Let F()) be Ky-Lipschitz scalar function of X. Then its smoothed form F(x; :; 0) is Ki-Liccchit, where the subscript p slands for the no-nor..
Proof.
1
F (x1;0) 0) (x>2; 0)
dtp(t; (F + F( + +8))
=
R"
dtp(t: 0) (F +t) F(x2 + +))l
Rm.
dtp(t; Kp | æ211p = Kp || æ2llp B
where the first inequality holds because the absolute value of an integral is always less than or equal to the integral of an absolute value, and the second inequality is because F(z) is Kp-Lipschitz.
Finally, using the previous results, we obtain certified radius of a smoothed classifier based on its smoothed margin.
Theorem 4. Let the smoothed margin Lm (x, C, o.) be defined according to Eq. and Eq. 1 If
LM (x, e, 2 < O, then LM (x + c,, < 0 v E R s.l. ||l|p < Ex (m, where Kp is the Lipschitz constant of the classifier and 1 + 1 =.
29 K2
Proof. From Proposition we know that the Lipschitz constant the margin function is 2 Kg Using Proposition 6 have that the smoothed margin is also 2 Kp-Lipschitz. Then, using the same argument s.t. Las (x + 6,c,
from Corollary 5.1 we have that the minimal perturbation
has norm ||0|, Lxx [x.00.00 Conversely, any perturbation less than that lower bound is guaranteed to not result in
K, misclassification on the smoothed classifier.
A.3 Closed-form estimate of smoothed margin
To obtain a closed-form estimate of the smoothed margin, we assume that the outputs follow multidimen-
sional normal with mean vector (1(o) and covariance matrix Σ(o) = (diag(var(o))) where diag(æ) denotes the diagonal matrix with the vector æ in the diagonal elements and var(o) is the variance vector of the output vector o.
For multivariate normal output o(x) we have the smoothed margin,
EM (x, c, 02) E Eapp(a)
max oi (æ) - o. (z) Eorp(o) ifc
max oi (2t) ifc
Me
x
(13)
Σ ic
opp (oi)
II
erf
(0: (0: Mig
V2a0,
do;
per
where the second line we took the expectation over the output instead of the input, and the indices are sorted in descending order, with 1 being the index of the largest mean among the incorrect outputs.
22

---

Published in Transactions on Machine Learning Research (04/2024)
We approximate the product of CDF to just the CDF of the largest mean among the ones involved in the product, which gives the following expression,
a²1
(11 112)²
Las (2,,
exp
+
111
erf
P1 - 122
v 2
(01
tz22
2 + x222)
2
(2 +
10|-1
0²:
(11 M2) 2 (0 012))
Mi
MI Mi
) Me
exp
1-ert erf
2T (01
+ 0,,
(2 +o,
1
Empirically, we found that using the terms involving the two largest means is enough to give close ap- proximation (Appendix D.2.. Then, by leaving the two terms, we arrive at the following expression as the smoothed margin,
LM (2,,,02)
o2
exp
(/1 22)2 2 [o} + o3))
+ M2
11
P2
1
P1 μ22
)) Me.
2x
2
(2 + 05)
A.4 Closed-form estimate of correct class probability
Just like the approximation of the smoothed margin, for the closed-form estimate correct class probability we make the assumption that the output vector o(z) follows multidimensional normal distribution with independent dimensions. This gives the following integral,
Pe (z, o (oc(x) (()) ] (0
III iffc
erf (0e- (00-11)
) doc.
(14)
V20;
By considering only the term of largest mean μ4 in the product, we have
Po (x, 2
1 + erf
Nr. Mn
2
12(00 + of)
A.5 ReLU moments
Let the preactivation of ReLU unit h ReLU(s) follow Gaussian distribution N(,, Then, à will follow rectified Gaussian distribution Ni,u,, o²) with density function
(h-
p(h: (= 8(h) + exp(
20
H(h)
where 4 (x) (z) erf [ is the cumulative distribution function of the standard normal distribution;
v2
((z) is the Dirac delta function, and H(x) is the Hcaviside step function. The expected value and variance of h ~ NR(H, o²) are denoted as follows:
A.5.1 Expected value of rectified Gaussian distributed variable
The expected value h of unit h ~ NR(U,, is
p(p 02) dh = exp(- (n-w)² 20
/
h = [==
dh
2TT
23

---

Published in Transactions on Machine Learning Research (04/2024)
Substituting A- 2,
h = /
(oz + exp(- 1
2 d2
exp(
0
expl
2
dz
2tT
22T
22T
11" exp(
2x
+
erf
H
v 2m
2
v20
where the second integral is the complementary cumulative distribution function - Φ (=#)
A.5.2 Variance of rectified Gaussian distributed variable
For the variance Var(h) = ER- En--Na(u. h?, we need the second moment on=-N(
on = /
(oz + 11) expl dz
V2T
(o²²² + 2 + 22 exp( - ))
de
22T
d²
exp(
de + 2po
4² exp(
25
+
2
erf
P
v 1m
/2T
2
V200
obtained substituting A- 2, and using the previous two integrals of the expected value. The integral with the 2² term is then calculated with integration by parts,
22
exp( 2 2
dz
20
exp(
2
+
2
exp
x²
dz
1m
22T
exp(
n²
0²
= =11
2n
+ erf
1
2m
2
/200
Adding the three terms yields the second moment of h,
BhnNNe(uo>>1131 = pu +
0²
1 + erf
(
[H)
H
)
2
/20
and its variance,
Var(h) = 0² # V2
)
1
eref erf
h(h 4))
2
A.6 CLT for independent rectified Gaussian random variables
In Section 3 to obtain the average classification condition constant for the margin loss we assumed the output layer to be symmetrically distributed, which we show in Appendix [D.] to be empirically satisfied. For wide enough layers this is the case, since for the case of independent, but not necessarily identically distributed, rectified Gaussian random variables, the Central Limit Theorem (CLT) applies, which we prove in this section.
24

---

Published in Transactions on Machine Learning Research (04/2024)
Proposition 7. Let h1...., An be sequence of independent rectified Gaussian random variables, where hy has mean hg and variance Var(ha) = o.. Then, the sum Σ h2 satisfies the CLT.
Proof. For the proof we use the following theorem and condition:
Assume sequence It .1,..., Zn of independent random variables, where the random variable 2i. has mean B[ra] = and variance of = [B[a]]- Then, the sum Σ 2/
Theorem 8 (Lindeberg theorem (Billingsley 1995
n o if the Lindeberg condition holds for all > Σ
converges normal distribution (00, s,),, where s
Condition (Lindeberg condition). Assume sequence 21....; 2n of n independent random voriables, where the random variable xy. has mean B[rx] and variance of = B[x]]] Then,
lim 1=000
xx = 0
(15)
22 /22|2e8n
k=
is the Lindebery condition, where s
Σ k=1
o
Let us consider a sequence hi....., hn of independent rectified Gaussian random variables, where hy has mean hy and variance Var(hæ) o. Without loss of generality, let of s of ... I of and 2h = he h that it satisfies [[xx] 0. We also define
arg max k
dR
(16)
Then, for all > O,
lim $2
dd <
lim
de
not
k=
k=
lim
ddd.i
n-000 no;
/2e|2Vne0
lim of [
xd
0,
where we used no? < s² for the first and Eq. 16 for the second inequality. The last limit is zero because (x(e) is a shifted rectified Gaussian distribution, which means that lim Pe(xy) and Pa(x)) rapidly x--22
decays for large zg, i.c., it decays exponentially while the x2 part of the intogrand grows quadratically. Therefore, Lindeberg's condition is satisfied, so the sum of independent but not necessarily identically dis- tributed rectified Gaussian random variables follows the CLT.
Robustness metrics
Since the motivation for SRA is that adversarial and noise robustness are distinct from each other, we measure the adversarial robustness through the margin certified radius and the noise robustness under isot
3rhhis change of variable shifts the of the sum without changing the variance and the second moment integral of
Eq.
25

---

Published in Transactions on Machine Learning Research (04/2024)
Gaussian imput noise. We also measure the Smoothed Robustness through the Randomized Smoothing certified radius. For the certified radius, we obtain the 'survival' curves for constant increments in the certified radius. For noise robustness, we measured the average accuracy for increments of input variance. For MNIST training. to visualize how both types of robustness changed for different pairs of loss hyperparameters (d. o in the MSCR and Zhen losses, we computed the area under the curve AUCcR,, of the survival curves of certified radius (Tsai et al. 2021bb Li et al. 2024), and similarly propose the area under the curve AUCoN of the noise accuracy curve. The AUC is simple and intuitive metric of overall robustness since AUCCR, is the average certified radius under lp attacks, and AUCaN is the expected standard deviation that causes the input to be misclassified on averag
While the previous three metries give information about both worst-, average-case and smoothed robustness, they do not tell how robust a classifier is in real-world scenarios, or how it compares to human subjects. Motivated by this, we implemented the linear image corruption method from Jang et al. (2021). In their work, they were interested in how robust Doep NNs are compared to humans image classification and proposed simple method of corrupting an image by building an image that is linear combination of the original times constant I' E [0, 1] and noise image times (1 (1-T), With this method, we not only compare the different trained NNs but also qualitatively determine how far they are from human robustncss, since one of the results from Jang et al. (2021) is that human subjects in general reached a 50% decrease in accuracy when the original image was about 25% of the final corrupted image.
B.1 Adversarial robustness
To assess the worst-case robustness, i.e., adversarial robustness, we computed the certified radius. The first is through the deterministic margin from Eq. the second through Randomized Smoothing with the CERTIFY algorithm by Cohen et al. (2019). For the latter, we used 10s samples, a = 0.001, and a = 0.25. After obtaining the certified radius for each correctly classified sample we obtained the certified radius curve the total number of samples with CR greater than a specific radius. From these curves we obtained their area under the curve AUCcR,,,
AUCCR, (Rees)) = 0.5Ac
Σ
(TotCR(X,eso (j 1) Ae) + Tot Ac)), /=0
where the summation is over the integer j and TotCR(Xtestiy Ae) is the total number of CR greater than radius j Ae.
B.2 Noise robustness
To evaluate the average-case robustness, i.e., robust to noise, we measured how the performance is gradually affected by increasing the standard deviation of an additive isotropic Gaussian noise. For each trained NN the following routine was carried to mcasure its noise robustness:
1. Measure the noise accuracy for zero variance (i.e., the clean accuracy) NoiseAco(Sresst 0z = 0) of all lest samples Xtest
2. Increase the input standard deviation o% by Ao, 0.2 for MNIST, or 0.2/2 for CIFAR-10
For each input, sample 100 noise v from NN o0 Inn), where I,, is the identity matrix with Ty diagonal elements, and n, is the inpul dimension
Calculate the accuracy for each of the noise samples and store its average NoiseAco(Z ow)
5. Repeat from step 2 until the average noise accuracy is less than 0.13 [c) plus small cutoff value, in this case 0.03)
SSunc for large input variances the noise accuracy converges divided by the number of classes, resort normal- ixation of the noise accuracy curve described in R.2
5On Appendix D.3 discuss how chose number samples
26

---

Published in Transactions on Machine Learning Research (04/2024)
To quantify the robustness to noise also employ the area under the curve AUC While for the survival curve of the certified radius there is a big enough radius that drops the accuracy to zero, yielding a finite AUC, for the noise accuracy the accuracy drops to around 1/|C), where |C| is the number of classes, so we cannot apply the AUC directly. Because of this, we normalize the noise accuracy so that maintains the same value for zero noise, but decreases the lowest accuracy from 1/|C| to O, which gives a finite AUC.
Then, we have the normalized noise accuracy NoiseAce' (Xieett Tzd) with σnjj = Arz
NoiseAcd (xttest (attstt;a.)) (1 0z NoisN On.j)
oz NoiseAAoo (xtssst where oj is [0,1] mapping, being 0 for j 0 and 1 for 00,
NoiscAco((81ett.) A min No k. Aox)
NoiseAcc(Srest, 0) min NoiseAca( k- Ao,) 0j =-
k
The meaning of this expression is that for og = 0 the accuracy remains the same, while the minimal accuracy becomes for o₂ > 0.
Then, using this normalized accuracy we can calculate the AUCGN as
AUCoN = 0.5Aoz
Σ
(NoiseAce (Brest, (j 11 Aox) + NoiseAcd [ Aox)).
1=0
The values of As and Ao, were picked in such a way that takes around 10 of these increments completely degrade the performance.
B.3 Linear corruption robustness
The linear image corruption from Jang et. al. (2021) allows simple way of controlling the quality of an image by adjust single parameter E [0, I]. where for = 1 we have the original image and for 0 there is complete loss of information. In their method, given image æ E [0, 255]"= and "gray" noisy image n, i.e., all pixels valued with 255/2 plus a small additive noise 8 ~ NO00 6/255), the final image to be presented is a linear combination
I= az + (1 a)
where the parameter a E [0, 1] can be interpreted as the signal-to-ssigall-lns--- to there is a pure signal and when there is pure noise. Then, by presenting images with different values of in 0.05 increments, they measured the reduction in classification performance in both human and NN classifiers.
ratio, which when equals
C Complete experimental settings
C.1 NN Architecture
For the MNIST experiments used multilayer perceptron with three hidden layers of 512 units each and ReLU activation, which due to its computational simplicity allowed for extensive evaluation of all losses considered in 4.1 their respective hyperparameters grid search, well as the variations in their robustness performance.
For the CNN architecture, we used four convolutional layers of output channel sizes (8, 8, 16, 16), kernel sizes 3, 4, and strides 2,, with a single fully connected layer of 512 units and ReLU activations in all
6Te code for all experiments can be found http:://ggthhahh.om/ooooooo
27

---

Published in Transactions on Machine Learning Research (04/2024)
layers. We adopted other architecture clements from Li et al. (0019)), such as not using pooling layers, since these are not norm-preserving, and in our case would result in a heavily skewed preactivation distribution, therefore not allowing the use of the moments of the ReLU. Like them, we also use 'invertible downsampling' to reduce the dimensionality, since striding is not norm-preserving. So, to have an operation equivalent to stride 2 one reshapes the previous layer by stacking each entry of a x non-overlapping patch, which multiplies the channel size by 4, hence decreasing the dimension of the posterior layer while preserving the norm.
C.2 ReLU moment propagation
In the estimates of the smoothed margin and probability of correct classification, we assumed independent normally distributed outputs. Orthogonal weights are required to mitigale the dependence of preactivations, which for wide layers approximately normal with mean 14 Wih- and covariance matrix Σ; O Wi] Var(h,-1). where Wi is the weight tensor of 1-th layer (i.c., the weight matrix and the convolutional kernel for the fully connected and convolutional cases, respectively), @ is the elementwise product, h is the mean of the (1-1)-th hidden layer and Var(h its variance, both of same shape as h In training with smoothed losses we implemented moment propagation (Wu et al. 2019) under ReLU activation functions.
Moment propagation consists of computing the mean vector 1i and covariance matrix Σ, of the preactivations 8t of the 1-th layer given by the mean activation of the previous hidden layer h4-1 and covariance cov h4-1; which in turn are estimated using M4-1 and E-- Although ReLU activation with normally distributed preactivation has simple closed forms for its mean and variance [ the covariance does not have closed form expression, thus requiring an approximation (Wu et al. 2011)). Fortunately, by using row-orthogonal weight matrices, which mitigate covariances, we do not need to worry about the covariances and need to compute only the mean and variance of ReLU layers.
C.2.1 Orthogonal weight matrices
We adopted the Björk orthogonalizaation algorithm (Böörck & Bowie 1971 to obtain orthogonal weight matrices. In the Björk orthogonalization there are two parameters, the order of the approximation p and the number of iterations q. By setting the order p = and starting with a matrix Ao = A the algorithm computes an approximate orthogonal matrix iteratively as
A A 1
1 2 AT Ab)
This sequence of operations, even though resulting in large overhead for more iterations, is amenable to backpropagation, where the entries of the (-th matrix A are updated, and easily implemented.
For the implementation of Björk orthogonatization we used the code from Anil et al. (2019) as base. However, different from their work, in which progressive orthogonalizatton is acceptable, i.e., increasing the iteration number to better approximate an orthogonal matrix as the training converges, and similar to Berg et al.) (2019), where they had to enforce orthogonality for their normalizing flows approach, we start the training with 30 iterations and every 10 epochs the layerwise number of iterations qı is decreased to the minimum W.ll
that satisfies -))(n=-1) E, i.e., the mean pairwise dot product between different rows of the weight matrix from 1-th layer obtained after the orthogonalization, Wi, should be less than s, my being the number of units in the I-th layer. We found that in general this mean is not less than 10 even for a large number of iterations, so we set e = 10-7 in all experiments.
C.2.2 Orthogonal convolutional layers
There exist several algorithms for building orthogonal convolutional layers (ingla et al.
2022 Singla & Feizi,
2021 Yu et al. 2022 Xu et al.) 2022 Trockman & Kolter 2021: Meunier et al. 2022). We used the imple-
mentation block convolution orthogonal parameterization from Li et al. (2019b) since it uses the Björck
We derive both in the Appendix A.5
28

---

Published in Transactions on Machine Learning Research (04/2024)
orthogonalization backbone, which we already had implemented. We show their algorithm in I with some minor modifications for conciseness, where G and Co are the layer's number of input and output channels, k is the kernel size, D is the block convolution R operator defined as [A_B] = --'=> -z==(A l B where A and B are mA X A and mB x Ag block matrices, A.j = for i & (0. Vj & (0, To generale symmetric projectors P and Q with rank [ Li el al. (2019b) used orthogonal square matrices M, and N and multiplied each row by a "masking" vector with the first [ entries equals to one and the others to zero.
Algorithm 1: Block Convolution Orthogonal Parametrization
Input: 6, x 6 orthogonal matrix HH)), 4 x [ orthogonal matrices M,,,.,), N:(Noo) for i from
to k - I, assuming C 2 Co
Result: Orthogonal Convolution Kernel W R
Initialize W as a 1 x 1 convolution with W [0,0] = H: for i from 1 to k-1 do P + M,M, ,N,N
Construct half-rank symmetric projectors;
PQ (I - PIQ
P(I - Q) (I- (I--
W < WO
end Output: W
This algorithm is a modification of the one proposed by Xiao et al. (2018) to allow the parameterization of the orthogonal matrices with unconstrained ones Ho, M,o0 and Noo that will have its values updated during training. However, unlike these works in that the goals of Xiao et al. (2018) and Li et al. (2019b) were to preserve the input and gradient norms, respectively, our reason for using orthogonal convolutions is to mitigate the covariance between units that emerges from the non-orthogonality.
To illustrate how non-orthogonality can be an issuc in our case, let us consider the case of filters of size 2 x 2 X Cin and stride 1. The first pixel in the first channel of the convolutional layer is the inner product of this filter and the first 2 x 2 x Gin pixels in the input. The second pixel of the first channel is the product between the filter and the x 2 x Oin pixels in the input after shifting one pixel to the right. Because there is an overlap of 2 x x Can input pixels, the covariance between these two pixels from the second layer is zero only if the first and second 2 1 Cin parts of the filter are orthogonal. Hence, non-orthogonal convolutions can create strong correlations between units, even with isotropic input noise, thus hindering the use of our closed-form estimates of moments of ReLU and smoothed losses.
To gain some insight into why this final block matrix is equivalent to an orthogonal convolutional layer, here we describe it qualitatively (for a rigorons and quantitative description, we refer the reader to (Kautsky & Turcajov 1994) and Li el al. (2019b)). The algorithm by Xiao el al. (001)) an extension to the 2D case of the one from Kautsky & Turcajov (1994), which in turn shows how to build ID discrete orthonormal wavelets. In terms of wavelet analysis (Kautsky & Turcajov 1994 Chui 1992), the output matrix W is an orthonormal 2D discrete wavelet, and the r-th rows of each submatrix W., correspond to the coefficients of one element of the orthonormal basis of the wavelet. By stacking each of these 1.2 rows in the order of the indices i and j, we have one filter of depth q; and size k.
For a wavelet to be orthonormal needs to have block autocorrelation - the 'non-flipped" convolution with itself- as the zero matrix for all values except at 'zero", i.c., when the wavelet 'overlaps' itself. To roughly sketch why this is the case, we first point out that all elements in its first column end with the projector Qu-1, while all elements in the last column end in Qx-1- When calculating the autocorrelation of this matrix, all the products of the first column entries with the transpose of the entries of the last columns result in the zero matrix, since Qk-1 and I - Qk 1 are orthogonal. Then, due to sequential convolutions with 2 x 2 block matrices, the columns from 2 to k - 1 have both entries that end in Qk-1 and I - Q Qk-1, but the columns s.t. 1 i k/2 always have the same number of Qx-1 entries as the column - has entries
8The intuition of the block convolution is that, just like the convoluitn between two functions 'flips" the function over each axis, it moves the 'flipped' block matrix on the left over the block matrix on the right, and each entry the resulting block matrix the sum of the matrix multiplication of the overlapping entries.
29

---

Published in Transactions on Machine Learning Research (04/2024)
I I- This kind of anti-symmetry in the distribution of projectors in W due to its generation from block convolutions of projectors, with directly neighboring elements having products of projections differing in only one projector, results in the autocorrelation of the matrix W having all entries 0, except the center one, that is the autocorrelation of the unshifted matrix.
C.3 Datasets
The MNIST datasel (LeCun & Cortes 2010 consists of 60000 training and 10000 test x8 and CIFAR-10 Krrizheskyy 2009) of 50000 training and 10000 test 32 x 32 x 3 8-bit images, labeled from 0 to 9 with the number reflecting the respective class of the image. The only pro-processing was the scaling of each pixel from the range 0-255 to 0-1 by dividing all input elements by 255.
C.4 Loss hyperparameters search
We used of E {0.001, 0.005, 0.01, 0.05, 0.1} for the SC-SCE loss. For the MCR and MH losses, we used E {0.5, 1,0, f0.01. 0.02, 0.04, 0.08, 0.16, 0.32, 0..08,0.1,,.222204661112222, 1.28, 1.75] and d E {5, 10, 15, 20, 25, 30). For the MSCR, over o E 10-1,01110000
4.0). For the Zhen loss we did a grid search over of e
(10-4,5x 10 100 1,-0,,100,,5000 3001, 100,,,,,,,,01011,1,0
100 ",0,,,, 200 1,x,,1011x1100010 5x 10-1, 100} and d E (0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 4.0).
C.5 Training
The weight update algorithm was Adam (Kingma & Ba 2017 with a learning rate of 0.01 and 0.005 for the MNIST and CIFAR-10 experiments, respectively, with the usual hyperparameters 31 = 0.9, f2 = 0.999, starting the weight updates only after 2000 steps of updating the adaptive parameters m and v for learning stability.
Finally, we found that using cosine anncaling as proposed by Loshchilov & Hutter (2017) with warm restarts resulted in generally better and faster convergences. We implemented the method described in their ap- pendix, so we will not go into details, but the method works by decaying the scale of the learning rate from to 0 in the first no epochs according to the cosine function and, after reaching the no-th epoch, the scaling goes back to and starts the decay again. When the scaling goes back to this is called a warm restart and helps avoid poor local minima and, to improve stability, the decay lakes more time in-between warm restarts, with n m ny epochs from the k-th to the (k: + 1)-th warm restart, where m is a constant integer greater than 1. By choosing no 20 and = in epoch 300 it finishes the third warm restart, with 160 epochs, which we found to result in stable training.
D Complementary experimental results
D.1 Approximate output normality
In Section 4.1 we assumed that the output layer is distributed according to multivariate normal distribution with independent outputs to obtain closed-form estimates of the smoothed margin and the probability of correct classification. Here we compare the values of the empirical smoothed margin and probability of correct classification with the ones obtained through numerical integration to show that for the case of orthogonal weight matrices with wide enough layers (512 units) this assumption is fairly satisfied.
We carried the numerical integration of the integral equations 13 and 14 used for the estimates with integrate. quardttequaadaae function from python's scipy package. The integration interval was selected to be ny 4o where j is the index of the output variable that the integration is taken, since smaller values would result in larger integration errors, while larger ones would increase the computational cost with small improvements in precision.
For the empirical evaluation, we obtained sample estimates of the probability of correct classification,
N
P' 02)
(m)
N
30

---

Published in Transactions on Machine Learning Research (04/2024)
where N = 10t the number of samples taken by forwarding different samples of input perturbation from isotropic Gaussian noise.
Both the sample and the numerical integration values were obtained by increments of Aœ, = 0.032 in the input standard deviation, using a NN with settings from Section C.5 after 30 training epochs. figure we see that the approximate output normality assumption is satisfied, given that the numerical and empirical values agree well.
Probebiity correct classifcarion
Mosss Aloolate (MAE)
88-
P zumerical sample
81- MAE
1000
Ioput varianoe o3
Figure 8: Comparison of correct classification probability Pe through numerical integration (continuous blue) and sample estimate (dashed green) for different values of input variance o?. The second axis shows the mean absolute error between the numerical and sample estimate values (dotted red). Each curve corresponds to the average over Lest samples after 30 epochs.
D.2 Closed-form approximations
In figure we present how close the approximations (dashed purple lines) of the smoothed margin (Eq. and probability correct classification (Eq. 8) are, respectively, to their integral equations 13 and 14 [continuous blue lines). We can see that, overall, the approximations are close to their numerical values, starting to diverge only for larger values of input variance. We also point out that the maximal mean absolute error occurs when half the samples are misclassified average, i.e., when Pa 0.5 and L on average.
Aeolute smoothed menginn JCM
Probubaltt corredd clesstication
Meaun Alsollte Error (MAFF
Mean Absolate Orror (MAE)
1G
0.22
1.8
04
14
014
munaicaa
8.10
mineinal Cul oppeectnation
01-
P. opposiiatioon
2.00
Input variance o
Ioput varianoo d7
Figure 9: Comparison of approximation (purple) and numerical integration (blue) values of probability of correct classification (left) and absolute smoothed margin (right) for increasing input variance. The second axis shows the mean absolute error between the numerical and approximation values (red line). Each curve corresponds to the average over test samples after 30 epochs, and we plot the absolute smoothed margin for better visualization, since as the variance increases, the signs of the SM start to change making the average SM close zero.
31

---

Published in Transactions on Machine Learning Research (04/2024)
D.3 Accuracy under noise
In Appendix B.2 we describe using 100 samples for the estimate of accuracy under noise. In figure 10 show that as the number of samples increases, the variance of the noise accuracy estimate decreases. For this plot we used input variance o₂ = 1, which is a large variance. For 100 samples, the error bar becomes close to 10000, and since 10000 is the size our test sample we used this value.
Mean noise accuracy (%)
30.5
30.2
10'
10a
10
10
Samples
Figure 10: Plot of the estimate noise accuracy for different number of samples. The error bars were computed over five estimates using the shown sample number.
32


Reviews:
[{"review_id": "urmAkStjA4", "reviewer": "Reviewer_qcjM", "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\n- The work introduces a novel framework that is well-motivated by smoothed analysis in algorithmic complexity\n- The margin loss-based robustness analysis offers a certified radius that doesn't scale with input noise variance and improves the robustness against adversarial and random noise attacks, which is empirically validated on MNIST \n- The paper nicely connects its proposed approach to existing research in RS literature \n\nWeaknesses:\n\n- The experimental evaluation is limited to 1-Lipschitz MLP with ReLU activations on the MNIST dataset and primarily focuses on l2-norm radius certification, limiting the generalizability to other architectures, datasets, and noise distributions. The paper mentions that CIFAR10 evaluation is left for future work, but I'm unsure why experimenting with additional datasets would be so difficult to be left for future work\n- The paper relies on assumptions of symmetry and independence of outputs for estimating the smoothed margin, which may not always hold true in real-world scenarios", "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 presents a novel framework for assessing classifier robustness, drawing inspiration from smoothed algorithmic complexity analysis to reconcile worst- and average-case scenarios. It proposes a margin loss-based method that provides a certified radius unaffected by input noise variance, thereby improving robustness. Experimental validation on 1-Lipschitz neural networks using the MNIST dataset shows that this approach enhances both adversarial and noise robustness compared to randomized smoothing, with a goal of nearing human-level performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the writing in the paper can be improved. The paper has a lot of technical discussion which may be easier for the reader to read if written slightly better. \n\n- All theorems/propositions and proofs are in the appendix. It would be better for readers if at least statements of the theorems or proofs were in the main paper. Provide concise statements of theorems or proofs in the main paper, with detailed proofs in the appendix.\n- Consider integrating lemma/thm statements within discussions, particularly in technical sections like 2.2, to highlight key conclusions.\n- Change the section 3 title to something more meaningful than \"methods\"\n- Only in section 2, subsubsections have section numbers (e.g., 2.2.1) but other sections do not. Make this consistent\n- Section 3.4, \"The loss used for the attack is the 6-th loss evaluated by Carlini & Wagner\", what's the 6-th loss?\n- Section 3.1, \"The computation of smoothed margin isn't trivial, since it involves a multi-dimensional integral over unknown distribution\", is this non-trivial or not possible?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fRZfSdLQb9", "reviewer": "Reviewer_augP", "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- Interesting combination of randomized smoothing and large-margin/Lipschitz based approaches for certified robustness.\n- The smoothed analysis inspired formulation of worst- and average-case robustness could be an impactful direction in defining more reasonable composite threat models for research\n- Comprehensive experiments for average- and worst-case robustness on MNIST and clear description of robustness evaluation.\n- Comparison to large-margin-only and randomized-smoothing-only losses.\n\nWeaknesses:\n- The paper is way too long; and the length is not distributed favorly. Introduction, related work, experimental setup are far too verbose, while the main part is difficult to follow due to the many abbreviations and unclear correspondence between abbreviations and equations.\n- In the abstract + intro, the relationship/jump from randomized smoothing to large-margin approaches is also unclear, creating a bit of a disconnect while reading.\n- The related work does not do a good job in pointing me to actually relevant and recent papers. There seem to be papers on the connection of large-margin and randomized smoothing [a] and there have been improved losses for large-margin methods (though not using 1-Lipschitz netoworks). [b] still gives a good overview in the related work section.\n\n[a] https://arxiv.org/pdf/2309.16883.pdf\n[b] https://arxiv.org/pdf/2309.06166.pdf\n\n- Which equation is actually the proposed MSCR? Equation (12)?\n- Assuming outputs are independently normally distributed seems like a strong assumption. The authors argue that this stems from the orthogonal weight matrices. But I am still missing a convincing experiment or reference.\n- The experimental setup is not convincing in my opinion. This has several reasons:\n-- The authors combine two methods for certified robustness, namely randomized smoothing and Lipschitz-based methods But evaluation does not include any certified evaluation (either following the randomized smoothing way which is not fully certified but with enough samples comes close enough, or Lipschitz-based which is fully certified but requires estimating the Lipschitz constant).\n-- The PGD evaluation only considers 5 restarts and PGD is fairly outdated on its own compared to AutoAttack or more recent ensemble attacks. Using only 5 samples for random noise also seems limiting.\n- Regarding the method, I am not sure if it is very appealing beyond MNIST. The 1-Lipschitz requirement might not scale to larger networks, thereby defeating the advantage of randomized smoothing which is model-independent. So it combines the worst of both worlds (hard to scale, e.g., [b] only recently managed results on TinyImageNet with Lipschitz methods and specific architectures) and the test-time computational overhead of randomized smoothing.\n\nConclusion:\nI am currently not convinced that this paper is a compelling read for TMLR readers. This is not only because the mentioned writing aspects, but also because of method limitations and ambiguities as well as limited evaluation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 authors propose a view on average- and worst-case robustness analysis based on smoothed analysis (from time complexity analysis of algorithms) and term this view smoothed robustness analysis. The key difference to prior work is the combination of worst- and average-case by taking the maximum (i.e., worst-case) of a smoothed (i.e., average-case) loss. They consider both margin and 0-1 losses. Using an assumption that output logits/probabilities are independently normal distributed and using orthogonal weights to obtain 1-Lipschitz networks. Experiments on MNIST show that this improves robustness over standard large margin or smoothed losses.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Address questions on paper and method limitations as outlined above; convincing experimental setup is particularly critical.\n- Address concerns about writing/length.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TvfBRvGVQP", "reviewer": "Reviewer_uodL", "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\nThe particular way the authors unify worst and average case analysis is novel, and the authors make an interesting connection to complexity theory. Also, the theoretical analysis in the paper is solid. The background sections of the paper (1 and 2) are quite comprehensive and detailed, and the methods are also carefully explained. Finally, the empirical results are nicely presented.\n\n**Weaknessess**\n\nThe paper has several areas for improvement in my view:\n\nEmpirical results\n* Experiments are only conducted on MNIST; I would encourage the authors to at least experiment on CIFAR-10 or a dataset of similar complexity to improve the paper's significance and strength of claims\n* It's unclear whether the robustness metrics introduced by the authors such as ASR and AMS can be compared to prior work. I would recommend using metrics proposed in prior literature when applicable.\n* Experiments are limited to Lipschitz-constrained NNs. This makes it difficult to make claims about the relative efficacy of the authors' proposed method to prior robustness methods which may not be limited to this architecture.\n* Similarly, experiments are only conducted on MLP networks. It would be ideal to consider CNN architectures as well, especially given that the authors consider an image dataset. This can help improve the empirical results.\n* Ideally, the authors can produce state-of-the-art results for smoothed robustness; this requires comparing the proposed method against state-of-the-art methods on well-performing architectures under standard robustness metrics.\n\nClarity\n* The paper is quite long (over 12 pages), which makes it difficult to grasp the key ideas and results in the paper quickly. I recommend reducing the length.\n* The authors frequently use acronyms to the point of confusion; indeed, a full page in the appendix is devoted to all the acronyms introduced. I would suggest reducing the number of acronyms if possible.\n* It would be good if the authors could better separate the theoretical assumptions and approximations (e.g. Eqn 12) from exact results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 proposes a new framework for analyzing the robustness of classifiers, called Smoothed Robustness Analysis (SRA), which combines worst-case and average-case analyses to provide a more comprehensive understanding of classifier robustness. In addition to proposing a new framework for analyzing classifier robustness, the paper also introduces a new margin loss-based function called Margin-based Cross-Entropy Robustness (MCR) loss. This loss function is designed to enhance robustness under the Smoothed Robustness Analysis (SRA) framework. The paper includes experimental results demonstrating the effectiveness of the MCR loss function on MNIST. Therefore, the contributions of this paper are twofold: first, it introduces a new framework for analyzing classifier robustness that bridges the gap between worst-case and average-case analyses, and second, it proposes a new margin loss-based function that enhances robustness under the SRA framework.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical**\n* Conducting experiments on a more complex dataset\n* Conducting experiments on other architectures (outside Lipschitz-constrained MLPs)\n* Conducting experiments against state-of-the-art methods with standard robustness metrics\n\n**Would strengthen**\n* Reducing the paper length\n* Reducing the number of acronyms\n* More cleanly separating the approximations from the exact theoretical results", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose the concept of smoothed analysis to bridge worst case and average case robustness of classifiers and derive theoretical connections between the smoothed analysis proposed and randomized smoothing approaches for certifiable robustness against adversarial examples. They provide both theoretical and empirical justification for this work. Hence, I recommend that the paper be accepted.
Decision: Accept (poster)