The Lipschitz-Variance-Margin Tradeoff for Enhanced Randomized Smoothing
Authors: Blaise Delattre
Alexandre Araujo
Quentin Barthélemy
Alexandre Allauzen
Venue: ICLR 2024 poster (2024)
Keywords: Lipschitz
randomized smoothing
margin
variance
deep learning
Primary area: societal considerations including fairness, safety, privacy
TL;DR: A study on the interplays between Lipschitz constant and randomized smoothing procedure.

Abstract: Real-life applications of deep neural networks are hindered by their unsteady predictions when faced with noisy inputs and adversarial attacks. The certified radius in this context is a crucial indicator of the robustness of models. However how to design an efficient classifier with an associated certified radius? Randomized smoothing provides a promising framework by relying on noise injection into the inputs to obtain a smoothed and robust classifier. In this paper, we first show that the variance introduced by the Monte-Carlo sampling in the randomized smoothing procedure estimate closely interacts with two other important properties of the classifier, \textit{i.e.} its Lipschitz constant and margin.  More precisely, our work emphasizes the dual impact of the Lipschitz constant of the base classifier, on both the smoothed classifier and the empirical variance. To increase the certified robust radius, we introduce a different way to convert logits to probability vectors for the base classifier to leverage the variance-margin trade-off. We leverage the use of Bernstein's concentration inequality along with enhanced Lipschitz bounds for randomized smoothing. Experimental results show a significant improvement in certified accuracy compared to current state-of-the-art methods. Our novel certification procedure allows us to use pre-trained models with randomized smoothing, effectively improving the current certification radius in a zero-shot manner.

Published as a conference paper at ICLR 2024
THE LIPSCHITZ- MARIINCE-MMRGGI TRADEOFF FOR ENHANCED RANDOMIZED SMOOTHING
Blaise Delattre Alexandre Araujo,, Quentin Barthélemy² and Alexandre Allauzen
1 Foxstream, Vaulx-en- Velin, France
2 Miles Team, LAMSADE, Université Paris-Dauphine, PSL University, Paris, France
3 ECE, New York University, NY, USA
ESPCI PSL, Paris, France
ABSTRACT
Real-life applications of deep neural networks are hindered by their unsteady pre- dictions when faced with noisy inputs and adversarial attacks. The certified radius in this context is a crucial indicator of the robustness of models. However how design an efficient classifier with an associated certified radius? Randomized smoothing provides a promising framework by relying on noise injection into the inputs to obtain a smoothed and robust classifier. this paper, we first show that the variance introduced by the Monte-Carlo sampling in the randomized smooth- ing procedure estimate closely interacts with two other important properties of the classifier, i.e. its Lipschitz constant and margin. More precisely, our work em- phasizes the dual impact the Lipschitz constant of the base classifier, on both the smoothed classifier and the empirical variance. To increase the certified robust radius, we introduce a different way to convert logits to probability vectors for the base classifier to leverage the variance-margin trade-off. We leverage the of Bernstein's ss concentration inequality along with enhanced Lipschitz bounds for randomized smoothing. Experimental results show significant improvement certified accuracy compared to current state-of-the-and art methods. Our novel certifi- cation procedure allows to use pre-trained models with randomized smoothing, effectively improving the current certification radius in a zero-shot manner.
INTRODUCTION
Deep neural networks are susceptible to adversarial attacks, which are small, carefully crafted pertur- bations that lead the model to make erroneous predictions (Szegedy et al. 2013). This vulnerability a critical concern in applications requiring high reliability and safety, such as autonomous vehicles and medical diagnostics. Various defense mechanisms, including certified defenses like Lipschitz continuity (Cisse et al. [017]] Tsuzuku et al., (2018) and randomized smoothing (RS) (Cohen et al.) 2019), have been proposed to mitigate these risks. Among the metries used to evaluate these de- fenses, the certified robust radius serves as an important measure for quantifying model resilience against adversarial perturbations (Tsuzuku et al., 2018). The certified robust radius measures the amount of perturbation that can be added to an input while keeping the stability of the decision y, as certified measure of robustness for an
i.e the label classification task. This essentially individual input. Similarly, the prediction margin (f(r), y) := max(0, (x) max fx (z)) acts as an indicator of the confidence of the base classifier assigning the label y to the input x. A larger prediction margin correlates with increased confidence in the prediction, even if the input incurs some perturbations.
The concept of Lipschitz continuity augments this framework by introducing the Lipschitz constant which bounds the sensitivity of the base classifier to input perturbations. A smaller Lipschitz con- stant signifies that the function base classifier exhibits slower variations in its output with respect to changes in its input: [= fxx)l < [[f))[]]]] Tsuzuku et al. (2018) & gathers these elements to provide bound on the certified robust radius that encompasses both the prediction margin and the
Lipschitz constant. This combined measure controls the trade-off between the classifier's 's prediction
margin and its sensitivity input changes. Upon the introduction of RS, Li et al. (0018: Lecuyer

---

Published as a conference paper at ICLR 2024
Tsuzuku al. (2018)
Lischitz constant
Lipschitz classifier
Margin
Deterministic certificate
Cohen et al. (2019)
Classifier
Smooth classifier
Risk shift Clopper-Pearson
Margin
Probabilistic certificate
LVM-RS (Ours)
Lipschitz constant
Simplex mapping
Smooth Lipschitz classilier
Empirical Bernstoin
Risk
Margin
Probabillistic certificate
Lipschitz classifier
Gaussian Poincaré
Empirical
inequality
variance
Figure 1: First. Tsuzuku al. (2018) proposes a deterministic certificate starting from a Lipschitz base subclassifier, followed by margin calculation and radius binding. Second, Cohen et al. (2019) introduces a base subclassifie to create a smoothed subclassifier. The risk factor a is then esti- mated using the Clopper-Pearses Pearson interval to provide a probabilistic certificate. Third, our method (the Lipschitz-Variane Sttriance-Marggnn Randomized Smoothing or LVM-RS) extends a smoothed classifier constructed with Lipschitz base classifier composed with map which transforms logit to proba- bility vector in simplex. The regularization the Lipschitz constant is motivated by the Gaussian- Poincaré incquality in Theorem [ inequality in Proposition
The empirical variance is applied to the Empirical Bernstein 2 to accommodate for the risk factor a, in the same flavor as in Levine et al. (2020). The pipeline also ends with probabilistic certificate, similar to the methodology used in Cohen et al. 2019)'s is certified approach.
et al. (2019); Cohen et al. (2019;; Salman et al. (2019): Levine et al. (2000) use the smoothed clas- sifier obtained by convolving Gaussian density with the base classifier. Salman al. (2019) proved that the smoothed classifier exhibits Lipschitz continuity which depends on the Gaussian variance. RS methods estimate smoothed classifier by injecting noise on the input. The resulting procedure is then probabilistic and approximate inference is carried out with Monte-Carlo (MC) methods. To account for the randomness introduced through MC, one can use an a-coverage confidence interval Slopper-Pearson as in (Cohen et al., [219 [Salman et al. 2211), or concentration inequality (Ho- effding's 's inequality) as (Lecuyer et al.) [019)]Lvinee Levine et al. 2020) the probability to not predict the good label i.e. control the risk induced by the randomness. A shift is thus necessary to lower- bound the prediction margin, thus yielding a more conservative but also more reliable estimate robust radius. In the last step of traditional classification, the decision usually relies on the arg max function. This can be seen as a map of the network's 's output, putting all the probability mass on one corner of the simplex. However, in the context of RS, there is detour: RS the smoothed classifier conducts an arg max map on the expectation the arg max applied to the base and deterministic classifier.
In this work, we revisit the whole decision process of RS to better leverage and disentangle the interplay of all these components. We propose to better leverage the margin-variance tradeoff with alternative simplex maps iee. function to map logits to probability vector. More importantly, we investigate how Lipschitz regularity impacts randomized smoothing techniques, emphasizing its effects on the certified robust radius. The regularity of the smoothed classifier depends on the Lip- schitz property of the base classifier and the variance of the Gaussian convolution which governs the induced level of smoothness. Therefore, our research in this domain encompasses following contributions:
We use the Crtussian-Poincart inequality to explain the impact of the Lipschitz constant of the base classifier on MC variance, which ultimately affects its reliability, Sec- tion 3.1 This motivates the use of the Empirical Bernstein inequality which integrates empirical variance to control risk o, Section 3.2
2

---

Published as a conference paper at ICLR 2024
We introduce the r-simplex for RS procedure which allows for better-suited margins and Lipschitz constant of smoothed classifier, see Section 3.3 We establish a novel limit on the Lipschitz constant for the smoothed classifier, detailing its reliance noise variance, simplex mass r, and the base classifier's Lipschitz constant, whilst clarifying the connec- tion between robustness certificates produced through Randomized Smoothing and the one from deterministic approaches as in Tsuzuku et al. (2018), see Section 3.4
We present the Lipschitz- Variance-Margin Randomized Smoothing (LVM-RS) procedure, presented in Figure which balances MC variance and decision margin and controlled the MC empirical variance through the different simplex maps. This procedure demonstrates state-of-the-an results on the CIFAR-JO and ImageNet datasets, see Section 3.5
BACKGROUND & RELATED WORK
The robustness of machine learning classifiers remains an active area of research, with various strate- gies being proposed and evaluated. In this section, we describe significant contributions in the do- mains of Lipschitz-based robust classifiers, randomized smoothing, and the role of margins in the robustness of classifiers.
2.1 NOTATION
Consider a d-diiennsional input data point x E X' C Rd and its associated label E E where Y encompasses distinct classes. The (c dddimensional simplex is defined as A A {D E R. 1 1'p 1,p 2 0}. and let _ + A denote the map onto this simplex. Usually, corresponds to the softmax hardmax map. For a logit vector RS, its map on A A is denoted by s(=). This map can use a temperature /. such that s'(=) == 8(z/t). For instance, the hardmax corresponds for the component value coordinate. This map can be obtained through softmax with low temperature - 0. A function f X' + I designated be formulated as F(x) == arg ma sx((())), ). resulting in the predicted label F(r). While F offers predictions for an input æ, it doesn't 't convey the confidence level associated with these predictions.
c). (1.....
s (=) Il arg max, =; which puts all the mass the maximum
the subclassifier before the map The main classifier can
The confidence level surrounding a classifier's decision boundary for a particular input x captured by the certified radius, denoted as R(ʃ, zz). This radius represents the maximum permissible level of perturbation, e, that can introduced input x without altering its classification output to remain consistent with its true label. A larger certified radius is indicative of classifier's robustness against input perturbations. Its formal expression in the context of the f--norm is:
R(f.x)= = min E 0 c), arg max fa(a + T) * $
where B2(0, = (r Rd ||T||2 S c).
The local Lipschitz constant w.r. the fo-morm of function f over an open set is defined as follows:
[f(x) f(x')l2
L(F = sup
(1)
| - x'112
zØzx
And if L(J exists and is finite, we say that ʃ is locally Lipschitz over B. If B X, we note L(S, x)) = T(J) and call it Lipschitz constant.
2.2 LIPSCHITZ CONTINUITY IN CLASSIFIER DESIGN
The concept of Lipschitz continuity has been recognized for its intrinsic value in designing robust classifiers. By ensuring that function possesses bounded Lipschitz constant, it can be ascertained that small perturbations in the input don't 't result in large variations in the output.
Proposition (Tsuzuku et al. (018)). Given a Lipschitz continuous subclassifier f for the tz-norm, O, X, and y as the label of x.. If the margin M (f()),)) v)
and given perturbation level
3

---

Published as a conference paper at ICLR 2024
at input meets the condition M(f(z), V2I(f)e, then for every such that ||||| S have arg max; fx( + + yy-
Reworking this proposition, the certified radius for subclassifier x, y can be expressed
Rí Ri x. = M(f(x).))
V2L(f)
This inherent property positions Lipschitz continuity as a strong defense mechanism against adver- sarial attacks. Recent efforts have focused on creating Lipschitz by design classifiers, incorporating
Lipschitz constraints either during the training phase via regularization or through specific architec-
tural designs Tsuzuku et al. (2018); Anil al. (2019); Trockman Kolter (2021): Singla & Feizi
2021bb; MMunier et al.] ;: Araujo et al. (2023); Wang & Manchester (2023) Some works
Araujo al., [222]] (Singla & Feizi 2021a Delattre et al. (023) provide soft Lipschitz constant
regularization of individual layers. Other works consider local Lipschitz around input points, Huang
et al. (202T); Muthukumar & Sulam (2023). However, there
trade-off' between the Lipschitz of the network and performance for the same level of margins, as depicted in |Béthune et al. (2022 Appendix N). Instead of constraining the Lipschitz constant by design, methods commonly found in RS strategies. have shown better overall performance to procure certified robustness as they allow regular neural network architecture to be used.
2.3 RANDOMIZED SMOOTHING
First introduced by Lecuyer et al. (2019) and later developed in Li (1,01) Cohen et al. (2019);
Salman et al. (2019) RS's central philosophy is to convolve the base classifier FF with a Gaussian distribution resulting in an smoothed classifier F with increased robustness against adversarial in- puts.
F(a) arg max maxxP=- (F(x 5) k) arg max (, (aadmax,, (f())
For hardmax, we define the smoothed sub-classifier f 7: + I2 as follows:
[x) == E5~A((0,21) [Ss. (f(x + 8))
and, in this article, F is generalized to any simplex map
(x) = arg max V5- [Sk (f(x + 8))l = arg max fa(x),
where s corresponds this context to the hardmax map on the simplex, applied to the base sub- classifier f through the RS process (Cohen al. 2019 Salman al. 2019 We note p f(x) and suppose p is sorted in decreasing order. Certified radius makes the mapping & fa intervene, where Φ represents the quantile function of the Gaussian distribution. We suppose here that the classifier F, gives the good answer, the certified radius writes as:
R2(p) = (p1) - + (p2))
(3)
In most RS approaches, the bound p2 S. P1 is used, it degrades the certified radius espe- cially when the smoothing noise is high. see Appendix B RS uses MC method to estimate by
n. -E= s(f(x + 64)). where are sampled from Gaussian distribution. As the RS method is probabilistic, there is risk a that the method returns the wrong answer (Cohen et al., 2019). Following Levine al. (2020), a confidence interval bound or concentration inequality is used to provide a (S, (Pa). at such that:
P pñ (ox
Pa (f,), < a,a,,
(4)
where Sn the sample variance. Then, the risk-corrected probabilities are obtained
p = (f: shift (fx), a, r...... . + shift (p2), a, n),... ........ p. + shift (pc) a)
Levine 2020) do simplex map but normalized outputs in [0, for another task.
4

---

Published as a conference paper at ICLR 2024
supposing that the (p sorted in decreasing order, P1 and Pa are used to compute the risk corrected radius (p) which holds with probability 1-a. a.
The drawback of RS is the sampling cost, MC error reduces with Vn with the number of samples. To tackle this issue the work Horváhh et al. (0022) leverages an ensemble of classifiers to reduce the variance and proposes an adaptive sampling procedure to verify whether a target-certifiet radius is reached or not. this work, we also aim to reduce the variance of the MC sampling.
2.4 MARGINS AND CLASSIFIER ROBUSTNESS
The margin, often described the distance between the decision boundary and the nearest data instance, serves as central component of classifier robustness. Larger margins are generally as- sociated with better generalization capabilities, a main principle behind algorithms such support vector machines. In the context of adversarial robustness, margins play critical role, with several studies highlighting the relationship between margins and resilience against adversarial perturba- tions. Efforts to optimize for larger margins, combined with other robustnes-enhanccng strategies, have shown promise strengthening classifier defenses. The work Béthuee al. (2022) explores the connection between margin maximization and Lipschitz continuity, and shows how both notions implement a tradeoff between accuracy and robustness.
While RS and Lipschitz continuity by design have been studied in their distinct capacities, recent research suggests an inherent synergy between them and the key role of margins. Our work focuses on the connection between RS and Lipschitz continuity to produce greater robustness.
THE LIPSCHITZ-VARIANCEE-N
TRADEOFF
In this section, we explain why the control of the Lipschitz constant in the subclassifier crucial to reduce the MC variance of RS. By applying Bernstein's 's inequality, we can decrease variance to improve the control of risk a, and further reduce variance, we employ a new simplex mapping on f, thus defining the LVM-RS procedure. Furthermore, we establish new bounds on the Lipschitz constant of the smoothed classifier w.r.t the Lipschitz constant of the subclassifier. In the following, we defer all proofs in the appendix.
3.1 Low LIPSCHITZ FOR LOW VARIANCE
The concept of Lipschitz continuity plays an important role in the sampling process, which is crucial for obtaining an accurate estimation of the smoothed classifier f. Specifically, by minimizing the local Lipschitz constant of a subclassifier s o f, one can reduce its variance. The following theorem illustrates this relationship for any
.i.....,y, Zn) repre- sent vector i.i.d Gaussian random variables with variance of. For any continuously differen- tiable function h R + IR, the variance is given by:
Theorem (Gaussian Poincaré inequality (Boucheron et al. 2013)). ). Let Z = (Zi....
v(h(Z)] & o² [VVb()))3]
We use the latter theorem to immediately derive:
Corollary 1. With same hypothesis Theorem 7 if exhibits Lipschitz continuity, we have that:
V(h(Z)] < 2² T(h)2.
Applying the above corollary to the classifiers {sEOS} which can be considered differentiable almost everywhere, it is evident that constraining the Lipschitz constant, T((* o f), leads diminished variance for 5% f. This, in turn, results in more precise estimation of [Es(( + 6))], cap- tured by Σ s(f(x + 5.)). Lowering the local Lipschitz constraints can significantly attenuate the variance and improve the certification results, but it can be too restrictive and cause drop in performance. To enforce low Lipsehitz and reduce performance loss, Cohen et al. (2019) proposed the injection of Gaussian noise during training, Salman et al. (2019) introduced SmoothAdv, which involves adversarial training of the smoothed classifier to reduce its local Lipschitz constant. The
5

---

Published as a conference paper at ICLR 2024
work of Pal & Sulam 2023) studied how the noisy training the sub classifier affects the per- formance and robustness of the smoothed classifier. Other noteworthy methods include those by Salman et al. 2220); Carlini al. (2023), which combine conventional classifier with denoiser diffusion model, ensuring that the resulting architecture remains invariant to Gaussian noise, thereby giving Lipschitz continuity the classifier and preserved performance.
3.2 STATISTICAL RISK MANAGEMENT FOR Low VARIANCE
To leverage low variance, one would need a confidence interval or an appropriate concentration inequality which variance plays a significant role.
The Clopper-Pearson binomial tailored confidence interval can be used to give an exact a coverage to determine shift. defined in Eq. 4 Cohen et al. (2019); Carlini al. (2023). paired with hardmax simplex map which generates series of Bernoulli trials during MC sampling.
Lecuyer et al. 2019) and Levine et al. (2020) smoothed scalar outputs between within [0, 1] and cannot use such interval, we use the same procedure as those works. They rely upon Hoeffding inequality, which also gives exact an a coverage. Another interesting inequality, similar to the Caussian-Poincaaré is the sub-uuuaae Gaussian inequality involving the Lipschtiz constant of s Massart f 2007). The issue here is that computing [(sg o f) is NP-hard for common neural networks and the Lipschitz constant inequalities have some limitations because they do not account for empirical variance. This is why we suggest employing the Empirical Bernstein's 's inequality when the variance is low manage the risk, 0, which does factor in the observed empirical variance, it has been mentioned by Lecuyer al. (211)).
bound overestimate the actual empirical variance. However, those
Proposition 2 (Empirical Bernstein's inequality (Maurer & Pontil 2009)). Let Zo. Zi...., Zn be i.dd random variables with values between 0 and 1. The risk level is denoted as E [0, 1J. Then with probability at least 1 a in vector Z = (Zi...., Zn). we have
1
28. log(2/a)
7log(2/a)
EZo
Z
(2))
3(n -1)
i=1
Here, (Z) represents the sample variance m(n-1) Eisteren (Z; 12,). Note that the bound is symmetric about EZo.
In our case, we use this inequality with Z; = (f + 5)). This inequality offers the flexibility to smooth various simplex maps and potentially select one better equipped than hardmax to address the margin-variance tradeoff. See Fig. for a comparison between Hoeffding's 's and Bernstein's 's inequalities.
3.3 HIGH MARGIN AND Low VARIANCE BY OPTIMAL MAPPING ON R- R-SIMPLEX
As all the mass is put on one class, hardmax map gives maximal margins on the simplex. However, it not Lipschitz continuous, and it can increase variance, as illustrated in Exam- ple C.I. Conversely, softmax map compresses the margins between classes but its 1-Lipschitz continuity prohibits variance amplifications. Martins & Astudillo (2016) introduced a novel sim- plex mapping. 1-Lipschitz and producing margins larger than softmax but lower than hardmax: sparsemax(z) arg minpeA=-1llp the softmax.
This map promotes sparse values in A c-1 compared to
In this work, we introduce the r-simplex A;- {p T 1 ppp=p,p200 0} simplex with total mass and the generalized sparsemax which a 1-Lipschitz mapping towards A;- following the same proof as in (Laha et al. 2018 Appendix A.5). This mapping is described in Algo. For r < r2, when most of the logit vectors f(x + 5,) are bounded by rı, the mapping to the simplex cc-1 with 1-Lipschitz simplex mapping is not going increase the margin associated to vectors Sry (f( 6:)). In this case, it is better map to the simplex A; of lower mass and enjoy tighter Lipschitz constant on or + 11 o fr. Conversely, when r2 2 Tı, one can benefit from larger margins Srg (f(x + 5z)) in comparison to margins on Sr, (f(x 6.)).

---

Published as a conference paper at ICLR 2024
In addition, we add temperature to simplex mappings: note s²x" the r-simplex map from R to A:- for a temperature t. Adjusting the temperature provides a means to interpolate between softmax and hardmax, or between sparsemax and hardmax. Tuning the temperature allows to find an optimized simplex map to answer the variance-margin trade-off, as illustrated in Fig.
3.4 NEW OPTIMAL LIPSCHITZ BOUNDS FOR RS
We derive enhanced bounds on the Lipschitz constant of the smoothed classifier / with the additional assumption that & o I or 8 o themselves are Lipschitz continuous. Note that one way to have s" o f or s f Lipschitz continuous of hardmax simplex map, whereas sparsemax is ideal as it is 1 1-Lipschitz continuous and conserves margin as long the latter is inferior simplex mass r.
have Lipschitz continuous as well. This is not the case
Theorem 2.
Let f X C IRd + Re subclassifier and f(x) Es-Ni0,021)1 (f(xr (f 6)) the associated smoothed classifier. Suppose that f is glement-wise Lipschitz continuous, then
{
{
L(fa) L(6 Ders
23 L( o sTa)
S min
V2TT²2 L(8h ((0%0))
(5)
Suppose that f is Lipschitz continuous, then
V L(s L nn
L(f) s L(s" frr
min
(6)
21(8' o 1)o
is noteworthy that Eq. 5) enhances the bound on T((fk) originally derived in Lemma of Salman al. (2019) for by factor of 2. This refinement on the bound was possible by supposing Lipschitz continuity on the base classifier f. Note that its Lipschitz constant can be arbitrarily high, so this assumption is quite light: the Lipschitz constant does not play into the derived bound. These improved bounds can be seamlessly incorporated into subsequent works, such as Pautov et al. 2022 Franco al. (2023); Chen al. 2024).
We observe that randomized smoothing and Lipschitz continuity exhibit a cross-effect on the Lips- chitz constant of f. We focus on an intermediate regime defined by a specific a and L(s f). where these effects interact in a manner that is mutually beneficial, exceeding the individual impacts of randomized smoothing or Lipschitz continuity alone.
Proposition 3. The optimal value o" that maximizes the gap between the bounds of Eq. 5 is:
giving L(fx)= I erf(Va/2) L(s) o f) S 0.79 L(s f).
(7)
1(8 e fm
Similarly, for Eq.
o² = L(s o fl giving L(ÿ S saf(v/(/)22) L(s
r
of.
(8)
For this choice a", L(8. o f) equals the RS bound (and is exactly the deterministic Lipschitz constant). Consequently, the combined use of Lipschitz continuity and randomized smoothing duces the Lipschitz constant bound of f by most 21%. In our framework, given either a Lipschitz constant (or o²), one can select the complementary o² (or Lipschitz constant) to maximize the syn- ergistic effects of randomized smoothing and inherent Lipschitz continuity. For this optimal choice, we obtain a certificate Eq. (2) that is approximately 26% larger than the maximum certification given by RS Lipschitz continuity alone.
All previous bounds are derived on the Lipschitz constant of which be used for radius R1- With regards to R2, have the following result the local Lipschitz constant of t f&. Theorem 3. Let f. .dd + A be the smoothed classifier, for input x X and B B2 (I, c), the local Lipschitz constant of 1-1 o f& is bounded by:
I. ( Pb. B3)
1 ( - - (-100)))))~000000))
max Pe (f(e) e(i)
exp
This result gives a local Lipschitz constant on e ball around r, in the same flavor as in Muthukumar & Sulam 2023).
7

---

Published as a conference paper at ICLR 2024
3.5 LVM-RS INFERENCE PROCEDURE
Given trained base subclassifier f. choose simplex mapping from set of simplex map S and temperature t E [flowers Supper]. defining an ensemble of classifiers {Fae)
Fg (a) arg max Es-x0.0 [& x + 6))] arg max for (z)
k
First we generate test sample of size nog, we obtain estimates Pst, using Bernstein's 's inequality we obtain the risk corrected Pgt and finally the risk corrected certified radius R2(D,)). We choose (s,,t.) arg max,, , (p()))) to maximize the certified radius. Then sampling of size n is per- formed and we evaluate an MC estimate of fa.- (z) which gives p and associated risk corrected p². We return prediction arg max; Pic and associated certified radius (r") Our approach summed up in Algo. []] addresses the trade-off between maximizing margins and reducing variances. The procedure SampleScores generates scores f( 5.) for ó; samples from N (O, o²1). This stands in contrast to methods like hardmax, which maximize margin at the cost of increased variance, and others like sparsemax and softmax, which prioritize reduced variance over margin maximization.
EXPERIMENTS
In addition to the two experiments below, conduct ablation study in Appendix
F
4.1 CERTIFIED ACCURACY WITH IMPROVED RS LIPSCHITZ BOUND
Table I: Certified accuracy CIFAR-10 for different levels of perturbation for RS, Lipschitz deterministic, and ours. The risk is taken as a = 1 and the number of samples n = 10*.
Certified accuracy (e)
Methods
Average time (s)
0.14
0.19
0.25
0.28
0.42
0.5
Lipschitz deterministic
40
33.57
27.18
24.59
13.65
9.15
0.004
Randomized smoothing
47.9
31.99
28.17
27.86
6.42
0.0
0.9
RS with new bound
52.56
46.17
39.09
35.08
21.9
13.53
0.9
To illustrate the gain of having a Lipschitz bound of smoothed classifier which includes information on the Lipschitz constant of sub classifier, simplex mass and variance o², we compare certified ac- curacies on the same by design 5-Lipschitz backbone Sandwhich Small from (Wang & Manchester 0.4 and using the same certified robust radius R4 in Eq. (2) We choose for the smoothing variance a* L(f) / as explained Section 3.4 Remark that the
2023). trained with noise injection
variance used for noise injection to train the 5-Lipschitz sub classifier is close to a* to mitigate a drop in performance on the smoothed classifier.
Lipschitz deterministic (using bound on L(f)), the RS (using bound on L(f)), and our approach (using bound on L(f)). For ours and RS, we r 3. Results are displayed in Table [ We see that our procedure gives better- certified accuracies than RS and Lipschitz deterministic taken alone, indeed both methodologies provide the same Lipschitz constant for f and f respectively, whereas our method provides an inferior Lipschitz bound on L(f). Note that better results from the random procedure should not be directly construed as an intrinsic superiority over the deterministic one, as the element of randomness introduces variability that must be accounted for in the evaluation and large sampling computational cost. However, gives a perspective over the performance of the theoretical Lipschitz smoothed classifier f.
Impact of Lipschitz constant We consider the three procedures:
Impact of simplex mass We note that to reduce the Lipschitz constant, one can not only increase the smoothing noise a as done traditionally in RS but also reduce r the total mass of the simplex. We plot the evolutions of certified accuracies for different simplex masses in Fig. with the same setting as above. We see that classical RS setting i.e. r = 1.0 one particular choice of robustness profile among many.
8

---

Published as a conference paper at ICLR 2024
Table 2: Best certified accuracies across E (0.25, (0.25,0.5,144 1.0) for different levels of perturbation 6,
on CIFAR-10, for n 10 samples and risk a 1e-3.
Best certified accuracy (e)
Methods
Average time (s)
0.0
0.25
0.5
0.75
1.0
Carlini et al. (023))
86.72
74.41
58.25
40.96
29.91
7.10
LVM-RS (ours)
88.49
76.21
60.22
43.76
32.35
7.11
Table 3: Best certified accuracies across E {0.25, 0.5, on ImageNet, for n 10 samples and risk a = 1e-3.
1.0) for different levels of perturbation
Best certified accuracy (e)
Methods
Average time (s)
0.0
0.5
1.0
1.5
2
Carlini et al. (2023)
79.88
69.57
51.55
36.04
25.53
14.01
6.46
LVM-RS (ours)
80.66
69.84
53.85
36.04
27.43
14.31
7.03
4.2 CERTIFIED ACCURACY WITH LVM-RS
In this experiment, we empirically validate the efficacy of our proposed inference procedure pre- sented in Algo. 2 highlighting its capability to improve randomized smoothing and achieve certified accuracy. Central to our approach the leveraging of the variance-margin tradeoff, which as we demonstrate, yields tate--of-the-art RS results. We further showcase how the procedure enhances the off-the-shelf state-of-the-art baseline model Carlini et al. (2023), which utilizes a vision trans- former coupled with denoiser for randomized smoothing. We use 50 temperatures ranging from fLower = 0.01, uupper = 50, and simplex maps S = (sparsemax, softmax, hardmaxx. The baseline consists of the ofate-of-the-ar art top performative model of Carlini al. (2023) which does smoothing of hardmax of base classifier and uses the Pearson- Pearson-Clopper confidence interval to control the risk
To compare the baseline with our method, certified accuracies are computed with R2 in the function of the level of perturbations c, for different noise levels {0.25, 0.5, 1). Results are presented in Figure for CIFAR-IO 10 and in Figure 6 for ImageNet. We see that our method increases results, especially the case of high a,, the case of a (0.5, 1.0) the overall certified accuracy curve in the function of the maximum perturbation is lifted towards higher accuracies. Results are presented in Table for CIFAR- 10 and in Table for ImageNet. Computation was performed on GPU V V100, reported average time is the computational cost of one input proceeds by RS and LVM-RS, we see that the computation gap between the two methods is narrow for CIFAR10 but is a bit wider for ImageNet. Detailed results are presented in Appendix G
5 CONCLUSION
In this paper, we demonstrate a significant connection between the variance of randomized smooth- ing and two critical properties of the subclassifier: its Lipschitz constant and its margin. We high- light the influence of the Lipschitz constant on both the smoothed classifier and the empirical vari- ance. To improve the certified robust radius, new simplex of mass r and simplex map are introduced for the subclassifier, which optimally manages the Lipschitz-variance seriiitz-vaianne-mmaatte margin trade-off. Along with this, we incorporate an advanced Lipschitz bound for the RS, resulting in improved certified accu- racy compared the prevailing methods. In addition, new certification procedure facilitates the use of pre-trained models in conjunction with randomized smoothing, leading to a direct improve- ment in the current certification radius. In future research, we plan integrate LVM-RS with margin maximization strategies and explore the choice of the simplex mass r.

---

Published as a conference paper at ICLR 2024
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In Inter- national Conference on Machine Learning, 2019.
Alexandre Araujo, Benjamin Negrevergne, Yann Chevaleyre, and Jamal Atif. On lipschitz regu- larization of convolutional layers using toeplitz matrix theory. AAAI Conference on Artificial Intelligence, 2021.
Alexandre Araujo, Aaron Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A unified algebraic perspective on lipschitz neural networks. In International Conference on Learning Representations, 2023.
Louis Béthune, Thibaut Boissin, Mathieu Serrurier, Franck Mamalet, Corentin Friedrich, and Al- berto González Sanz. Pay attention to your loss understanding misconceptions about lipschitz neural networks. In Advances in Newral Information Processing Systems, 2022.
Stéphane Boucheron, Gábor I Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford University Press, 2013.
Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslic Rice, Mingjie Sun, and Zico Kolter. (Certified!!) adversarial robustness for free! In International Conference on Learning Representations, 2023.
Huanran Chen, Yinpeng Dong. Shitong Shao, Zhongkai Hao, Xiao Yang, Hang Su, and Jun Zhu. Your diffusion model is secretly certifiably robust classifier. In arXiv, 2024.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parse- val Networks: Improving Robustness to Adversarial Examples. In International Conference on Machine Learning, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, 2019.
Blaise Delattre, Quentin Barthélemy, Alexandre Araujo, and Alexandre Allauzen. Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration. In International Conference on Machine Learning, 2023.
Nicola Franco, Daniel Korth, Jeanette Miriam Lorenz, Karsten Roscher, and Stephan Guennemann. Diffusion Denoised Smoothing for Certified and Adversarial Robust Nut-Of-Distribuus Detec- tion. In arXiv, 2023.
Miklós Z. Horváth, Mark Niklas Mueller, Marc Fischer, and Martin Vechev. Boosting randomized smoothing with variance reduced classifiers. In International Conference on Learning Represen- fations, 2022.
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training Cer- tifiably Robust Neural Networks with Efficient Local Lipschitz Bounds. In Advances in Neural Information Processing Systems, 2021.
Anirban Laha, Saneem Ahmed Chemmengath, Priyanka Agrawal, Mitesh Khapra, Karthik Sankara- narayanan, and Harish G Ramaswamy. On Controllable Sparse Alternatives to Softmax. In Advances in Neural Information Processing Systems, 2018.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEFE symposium on security and privacy (SP), 2019.
Alexander Levine, Sahil Singla, and Soheil Feizi. Certifiably robust interpretation in deep learning. In arXiv, 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-Order Adversarial Attack and Certifiable Robustness. In International Conference on Learning Representations, 2018.
10

---

Published as a conference paper at ICLR 2024
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International Conference on Machine Learning. 2016.
Pascal Massart. Concentration inequalities and model selection. In École d'été de probabilités de Saint-Flour, 2007.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. Conference on Learning Theory, 2009.
Laurent Meunier, Blaise Delattre, Alexandre Araujo, and Alexandre Allauzen. A dynamical system perspective for lipschitz neural networks. In International Conference on Machine Learning, 2022.
Ramehandran Muthukumar and Jeremias Sulam. Adversarial robustness of sparse local lipschitz predictors. SIAM Journal on Mathematics of Data Science, 5:920-948, 2023.
Ambar Pal and Jeremias Sulam. Understanding Noise-Augmented Training for Randomized Smoothing. Trunsactions on Machine Learning Research, 2023.
Mikhail Pautov, Olesya Kuznetsova, Nurislam Tursynbek, Aleksandr Petiushko, and Ivan Oseledets. Smoothed embeddings for certified few-shot learning. In Advances in Neural Information Pro- cessing Systems, 2022.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Ad- vances in Neural Information Processing Systems, 2019.
Hadi Salman, Mingjie Sun, Greg Yang. Ashish Kapoor, and J Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. Advances in Neural Information Processing Systems, 2020.
Sahil Singla and Soheil Feizi. Fantastic four: Differentiable and efficient bounds singular values of convolution layers. In International Conference on Learning Representations, 2021a.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In International Conference on Ma- chine Learning. 2021b.
Charles M. Stein.
Estimation of the mean of a multivariate normal distribution. The Annals of Statistics, 9(6):1135-113) 1981.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. International Conference on Learning Representations, 2013.
Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certi-
fication of perturbation invariance for deep neural networks. Advances in neural information processing systems, 2018.
Václav Voráček and Matthias Hein. Improving 11-Certified Robustness via Randomized Smoothing by Leveraging Box Constraints. In International Conference on Machine Learning, 2023.
Ruigang Wang and Ian Manchester. Direct parameterization of hipschitz-bunnder deep networks. In International Conference Machine Learning, 2023.
11

---

Published as a conference paper at ICLR 2024
A ACKNOWLEDGMENTS
This work was performed using HPC resources from GENCI- IDRIS (Grant 2023-AD011012114 and funded by the French National Research Agency (ANR SPEED-20-CE23-00255) This work received funding from the French Government via the program France 2030 ANR-23-PELA-0008 SHARP. We thank Yann Chevaleyre, Muni Sreenivas Pydi, Florian Le Bronnec, and Sylvain Delattre for their precious help on the D.1
B RELATION BETWEEN CERTIFIED RADII
Using the fact that p2 < 1 P1 into Eq. (3. Cohen al. (2019) Section 3.2.2) motivate the use of certificate Rg for statistical simplicity and saying that f(x 6) puts most of its weight on the top class:
Rs(p) = oΦ - S (2)
(pt)
For the Carlini al. (2023) architecture, is not an optimal choice: in the context of high variance a², the distribution of (()) tends be closer to uniform distribution. Thus, the difference between radii R2 and R3 increases, as shown in Table This effect has been noted in (Voráček & Hein, 2023
Table 4: Comparison two certified radii R2 and R3, and Total Variation distance to Uniform distribution (TVU), for different values of a. We took a subset of images from the ImageNet test set with n 10 a 0.001, and used Empirical Bernstein's 's inequality. the effect is not visible for 0.25, we see that the TVU decreases, the difference between the two radii increases well.
TVU
R2(p)
R3(p)
R2(p)
R3 (p)
0.25
0.998
5.89
5.89
0.00
0.30
0.996
4.68
4.48
0.20
0.35
0.989
3.68
3.21
0.47
0.40
0.986
2.49
1.97
0.52
0.50
0.976
1.28
0.59
0.69
0.60
0.95
0.56
0.00
0.56
12

---

Published as a conference paper at ICLR 2024
C SIMPLEX MAPPING
C.I EXAMPLE ON hardmax
Example. For a random variable defined over the interval [0, 1], with [[[] and a "small"
variance Var[X] = o² m = 3. we define new random variable as Y = =(() x
Then Var[Y] o will be much higher than Var[X] when o² is significantly smaller than 1-
Proof. Let us compute E[Y], since Y is an indicator random variable. we have: K[ = PP
1) P(X 2). Given X symmetric around 0.5, we find [[ 0.5. The variance of Y given by: V E - (E[Y))?. Since Y is an indicator variable, y Y. and therefore B| = E|y = 0.5. Thus, we have: V[Y] 0.5 0.25 0.25. To claim that V[Y] has much higher variance than V[X], we need to compare 0.25 to o². The statement would be true if o² substantially smaller than 0.25. Given that X is defined over [0. 1] and its mean is 0.5, the variance of could range between 0 and 0.25. Therefore, unless X has variance near this upper bound, V[Y] will indeed be much larger.
C.2 ALGGORITHM OF GENER ALIZED SPARSEMAX
Algorithm generalized sparsemax(2, r)
1: Sort 2 in decreasing order 2 2 ... 2 2c
2: Find <(z) such that
<(2) = max
k p k2k Σ
k=
5SA
3: Define
(Eisuce) 23) - 1:(2)
p(2)
4: return p such that p. max(2: p(=),0)
13

---

Published as a conference paper at ICLR 2024
D PROOFS FOR LIPSCHITZ BOUNDS FOR RS
D.1 PROOF OF THEOREM 2
For both parts the proof, we are going to use the following lemmas.
Lemma 1. (Stein's lemma Stein 1981 Lemma 2))
Let > O, let h R be measurable, and let h((z) Es-Nio.001/(2 + 8)). Then h is differentiable, and moreover,
Vh(x) = o² Es Es +8]]
Stein's lemma can be easily extended to Rdd R We note az h(r) the Jacobian matrix of h(x).
Lemma 2. Let a let h R2 + Re be measurable, and let h(x) Es-No,,02 +6]. Then difserentiable, and moreover,
@h(x) -o00 + +6) 6)
-
dz
Proof. We are not going to prove differentiability as it is the same argument as in the proof of Lemma I see (Stein 1981.
1
h(xx) (2To2
h(t) exp
||
11(
dt
20
θ
1
(2mo2)d/12
Rd dx
exp
20
|/2
$11?
h(t) dt
θ
1
(2no2)d12
dx
exp
20
|
$1?
h(t)
1
(2na2)d/2
o²
exp
2a²
|| t||
h(t) dt
with change of variable and definition of expectation, we get the result.
Lemma 3. For L 2 0, 2 0, let h IRd + [0, r] be defined as follows:
h(x)) = sign(x1) min 2T/aar |} +
where sign is the sign function with the convention sign(0) = 0. Then, is L-Lipschitz continuous.
Proof. To show that h is L-Lipschitz continuous, need to demonstrate that for all x, E gd.
[h(x)) h(y)) L|| yl12-
We write x (xI,..., R2) ..) and (31...., va). In the following cases, only the first coordinate is going to intervene. We consider three cases:
Case 1: æ1 = 0 and yı = 0.
In this case, sign(x) (m) ) 0, sign(y1) and h(y) M(x)) = 5 for any x.
Thus, [h(x:) h1)) 0 < L| r Uاا2-
Case 2: 31 # 0 and /1 0 (without loss of generality same as 21 and yı * 0).
In this case, h(z)) is given by:
r
h(x) = sign(x1) min(r: 2L [x1
2
14

---

Published as a conference paper at ICLR 2024
and hyy) is given by:
h(y) 7
2
Now, let's consider the difference [f(xx) h(y)l:
[b(x)) - -h(y) = sign(r)) min (z + 2 2
2
2//21] S r, then min((; 21/21 | =2L/z1 | and the expression becomes:
1
(2 +
-|ar L| y112
2
If 2L > then min (r, 21 } and the expression becomes:
r - L|21
Sign (z1)
sign
L||e vl12
2
In both cases, [1(x) h(y)l <
L| U|1.. therefore, in the case where æ1 # and = 0, [M(x)) h(y) is I-LLipschitz Same result goes for 21 and yn # 0.
Case 3: æ1 # 0 and y1 + O.
Without loss of generality, assume x1 2 1yal- Consider
[k(x) h(y)l = (ign(()) min 21/21 - sign(y1) min(r; 2L/3/13
Let's consider two sub-cases:
Sub-case 3a: If 2L/x1] < r, then min(r;2L/rii) = 21/r11.
Sub-case 3b: If 2T > r, then min 2T|/x11] = =r.
Similarly, for lur.. we have 2T.//l] 2T/bn if 2L/m1 S and min 2T/nn = if
2L|yi >r.
In both sub-cases, we can write:
1 22L 2Ly1 L|11 -111 S D|| 2112
[h(z) h(y)
Therefore, h is L-Lipschitz continuous.
Theorem (Ist part). Let f Rd - rl Lipschitz continuous classifier and f(xx)
|f 6)] the associated smoothed classifier. Then,
L(f) L(f)) erf
28
Proof. For ease of notation note T. I(f), interested in the following:
J(a, L)
sup mL(()=L zeRd
sup
|Vh(())l2=
sup ReL(h== zERd
sup
sup w VVh(().
First, we will derive an upper bound on J(a, L). Consider any x E Rd, any Lipschitz continuous
s.t Mxx) E r). and any v E Rd with |||||| = 1. Any d E Rdd can be decomposed as = 5- + 6, where 5 = (u 5)u and &L 1 v. Let 8' = 8- 8. That is, 8' is the reflection of the vector with respect to the hyperplane that is normal to If AO, o²I), then 8' NO r² because NO o) is radially symmetric. Moreover, v"8 - 8. Hence.
E 20 öh(x 8)] Es-A10,,22 8'1(z + 8')] -Es-N10.0211e" 8h(x 8')]
15

---

Published as a conference paper at ICLR 2024
Using the above, we have the following, using Stein's Lemma] T
1 =
v. Vh(a)=
0² Es-N(o /v 8h(x +
2x BB- 10" 5 + 6) - h(x + o')]]
Bs-N(o. 11 8 (h(z + 6) h(x 8')nl
20
(0)
1
Es~N
11 min 2L vz 8|H
20
(1))
E8-N(00
02 61 min (r. 61
2x
(192)
[|= min (r, 2T.
2x
where (i) follows from the Lipschitz assumption on and the fact that 8 || |2(o" 8)ell 2/ and that Ih(x +) h(x + 8')l s r, (ti) follows by choosing the canon- ical unit vector v = (1, .......)) .) because the previous expression does not depend on the direction of v, and (dit) follows by simply rewriting the expression in terms of 2.
Now, we will derive a lower bound on [o, L). For this, we choose a specific h E 10.r1 as h(x) = sign(w)) minfr. fr, + r/2,, with sign(0) O. Using Lemma 3 we have that h is L-Lipschitz. For this choice, note that We choose a specific x = and specific unit vector up = (1,0, .l,))...,.) 0). h(O) r/2 and v/ 51. Then,
[0, L) vh
20, 8h(0)
B BB- |6 min(r: 2T] +
20
E. E, (i, 21|²
20
Combining the upper and lower bounds, we have the following equality:
Jl L) = 2/2 20 -( [min {r|z], 2L
(10)
We will now compute the above expression exactly:
1
[min (r|=], 2]="]]
20²
1
=
2
exp
2L
222dd
20
V
202
-22
2g
2
exp
20
zdz
1
+00
1
-22
exp
2dz
20
2
20
1
-22
exp
2 dz
x²
V
2
20
2 TT |o|
2 V
|
r
e
+ e डदन
Lorf
V2
23 |o|
2 /
|
r
Lerf
23 Lo
16

---

Published as a conference paper at ICLR 2024
Remark 1. Jensen's inequality gives the following simple upper bound on [ L):
[o, L)
20² 000
-
1
[min (r|z).2L22)]
I min (a= 2, Ni /
S min (V2To22
Hence, J(a,I) I)) is no worse than the Lipschitz constant of the original classifier f, or its Gaussian smoothed counterpart without the Lipschitz assumption, the latter bound twice smaller than the previous original derivation in (Salman et al.) 2019 Appendix A).
Theorem (2nd part). Let f
Rd A Lipschitz continuous classifier and h(x)) (f= + 5)] the associated smoothed classifier. Then,
I(N) S erf 2
Proof. We also note here L = L(F) and use the same notation as in the previous proof. Here h: Rdd c--1, have consider bound the maximum singular value of the Jacobian,
V 2 h(r)u.
]o L) sup
sup h:L(h)=L wER4
sup 1 MER%:|u|=
Ox
As in the previous proof, we will derive an upper bound on Jo, L.). Consider any a E Rd, any T-Lipschitz continuous s.t h(x)) A and any v Rd with ||e|| 1, E RR with ||u]| =
8 8 + 8, where = (v" d)r and 8+ V. Let 8 = 8+ 8. That is, 8' is the reflection of the vector 8 with respect to the hyperplane that is normal to V. If 8 (O0 I²I). then 8' A((0, o2 because NN0,, 02) radially symmetric. Moreover, v
Any d Rd can be decomposed
- v² 8. Hence,
E8-N00,221100 8h(x + +6) TTT 1B + T = -E Th(( + 8T)T..
Using the above, we have the following, using extended Stein's Lemma
② h(x))
v Ox
o² Es-Nio.0") 1u" 8h(x + uu]
6(1(z + 6) - h(x + 8') Tu)] Es 2 T6
20
Es T [h/( 5) h(x + o')) Tull
20
(
1
Es_N (rn 2 81H
20
(i))
E Es 2/ min
20
(10)
E N mwnmmiinnnnn... m1inm
20
where (V) follows from the Lipschitz assumption on and the fact that || - 8'] ||2 =
12(l fyel = 2/2 5) and that (1h(x+))) 5()) u| = h( 8')) w|l S [
6) h(x 8') |||||||| rv2. (ii) follows by choosing the canonical unit vector = (1, 1........ 0) because the previous expression does not depend on the direction of u, and (iii) follows by simply rewriting the expression in terms of z.
Now, we will derive a lower bound on J(a L). For this, we choose a specific h E r] as hy (x) sign(21) min{ rry2 L[æ1|} + ry? 2. with sign(0) 0 and hx(x) 0 for i E c). Using Lemma 3 hy is T--Lipschitz and h, are O-Lipschitz for i E (2, thus h is T--Lipschitz
17

---

Published as a conference paper at ICLR 2024
specific and specific unit vectors u (1,0...... 8 (1,0,....) 0). For this choice, note that h (0) 2/2 and E 8 òj. Then,
J(o, L) n 0 h(0)a dr o² Bo~ 5h(6) (
20 Bs
[|0 2in(rv2,22[60111 +0
B m
202
Combining the upper and lower bounds, we have the following equality:
Jo, L)
2o² B
1
min (rV2)
(11)
We will now compute the above expression exactly:
1 E. (00
min
2/2=|, 2T.2
20
V2L
=2
exp
2L dz
20
V
2TT
20
V2L
1
VIL
-22
20
2m
exp
2
zdz
1
+00
1
-22
exp
zdz
20
2
20
VIL
VIL
1
-2²
1
exp
L dz
V
20
23 / |o|
23 \
|a
VIL
r
e ,1..
Lerf
+
2Lo
V2
||
23
V
2 /
Lerf
2La
Remark For h: Rd + -- Lipschitz classifier, Jensen's inequality gives the following simple upper bound on J(o, L):
J(a, L.
1
E (0.00
[in (1V2),,,22) /021
2g
<in
min
V
Hence, J(a, L) is no worse than the Lipschitz constant of the original classifier h, or its Gaussian smoothed counterpart without the Lipschitz assumption, the latter bound is v2, times bigger than the bi-class case with L(hx)-
D.2 PROOF OF PROPOSITION 3
Proposition. The optimal value o² that maximizes the gap between the bounds of Eq. (5) is:
giving L())) < erl( L(s - /) S 0.79 L(8 f)
L(s f)
Similarly, for Eq. T
0' = L(s o fl
giving L( < ( L(s" 0.79 f))
18

---

Published as a conference paper at ICLR 2024
with respect to Proof. For y 2 seek o² that maximizes the gap between the bounds of Eq. 5 a:
arg max o>0
min
7,
vrr
v 2TT
23/2
To find the value of o² that maximizes the given function, we'll determine the critical points. Let
g min
{T V2TT² yerl erf
23/22g
Let's start by setting the two functions inside the min function equal to each other and solving for a::
2
- 2
7/2
2v22
This is the point of intersection, hence the value of where the two functions inside the min change dominance. For that value, g ((Z2Z = y(1 - erf( v/x )).
Now, for < 7V2=" g(0) = 7 erf 22/2y0
Let's differentiate g in the this first region:
d
g'(o) = do
yorf
23/2370
2
7 2 /
exp
23/220
2t
exp
23/2na
The supremum is obtained for o - 0, and the associated limit value for g(o)
((7)
For the second region,
g(o)
V2na² 7 erf 24/2n0 Supremum is obtained for
7/2n"
22 is decreasing function of a. The associated limit value for g( is 7011((11f)) ( ))-
Finally, taking = L(s) o f), 0" LisTotV2 gives maximum value for g on all domain.
We get a similar result 0² = Li for L(s" f).
D.3 PROOF OF THEOREM 3
In the previous section, we derived new radius for the smoothed classifier h but usually RS ap- proaches use the Lipschitz constant of the function --1 o h and its associated certified radius.
Here suppose that h Rd A;-1, how does it changes the Lipschitz constant of क o h Lemma 4. Let h Rd + A be the smoothed classifier and 4-1 the gaussian guantile For an input x E X. the tn-norm of the gradient of tb o hy is bounded by:
function.
1 1 (x < exp (-2 Φ - -
Proof. In the manner the proof of Salman al. 2019). let assume that 1.
19

---

Published as a conference paper at ICLR 2024
sup |V o 1
v' '(ha(1))
VER*:||e||=1
(h)
sup vER*:||U|==1
0' (hx
Using that expression, we can derive an upper bound on the Lipschitz constant of O -1 hu.
The denominator (' ((-0((((x)))))) V2w exp (- ② (h=()))))))
By Stein's 's Lemma, we can express the numerator as
(z. Es~a(o,,)) lo 8h4 + 6)]
We need bound this quantity with the constraint that Mo pad hy hx()) E [0, sums following problem, with ha(2 + g(2):
sup VERt:|u/|=1
Eo-N(on [v" 5g(x)]
(12)
s.t g(x) E r) and Eo (g())) =
We can solve it for g' = g/r:
rEs-N(0n 6g'(x=)]
sup
s.t gx)x) E [0,1]
1] and Es [0(( = p/r.
We recognize problem solved in (Salman et 2019 Appendix A, Lemma 2), which has for solution
g" (=) == Thus the problem (12) has for solution g" g²(2) r - (p/r))
Plugging g" in the numerator we obtain
E5~A10,,) ōg" (6) = E E 12>0-1(0/m)
texp +² /2dt
V2TT_
1-0-11m/1 l(p/r)
Φ ( ( (-2
exp
2m
Finally,
|V o (x(2)lla & rexp (1-
-- -0-((xx())3))
To obtain the result for any o, we can apply the result hx (z/or and this implies that
o hx(2))12 < exp (-5 ( ((h(xx//)) - ((((t)))))
-
Using previous Lemma 4 we derive the following Theorem,
Theorem. Let h. Rdd - be the smoothed classifier and Φ-1 the gaussian quantile function. For impul x X, and B B2 (T())),e((i)) the Ez-norm of the local Lipschitz, constant of --1 by bounded by:
L (V
- hh,, B)+
exp (-2 (4 (p-1(p/r)2-- (0/)))-)000))))
max
o peB
20

---

Published as a conference paper at ICLR 2024
E LVM-RS ALGORITHM
Algorithm LVM-RS (f. no.
1: scores_ri, f (ampleeeooes((1t (o
// validation set, dimension X c certification set, dimension
2: scores.n SampleScores( (,,
3: for temperature E [flower, tupper]
4: for simplex map 8 E
5: Pst
no) // dimension 7: p ng E s. (scores.ni (i,;)) SS, *- (scores a, n)
Σi=1 s² (scores_nali.) - 6: (s.. arg max,, (2,).))
// dimension
8: return prediction arg max; P and certified radius R2(5")
We recall that RS produces the smoothed classifier f starting from sub classifier and for all X, it outputs certified radius R R(F, and prediction F(x) it guaranteed that for all x' B2 R), F(x')
The difference with the LVM-RS procedure that the choice of produced classifier F depends on input x. Starting from sub-classifier we generate an ensemble of smoothed classifiers { For an input
X, the LVM-RS procedure selects a classifier F {Fa}e that maximizes the margin-variance trade-off. We output for and F certified radius R R(F, .)) and prediction F(x) = y. it guaranteed that for all x' E B2(x, F(x') = ÿ.
21

---

Published as a conference paper at ICLR 2024
F ABLATION STUDY
This ablation study provides two comparisons:
A comparison between corrected certified radii produced by Hoeddfing's and Bernstein's
inequalities in Fig. 2
The Clopper-Pearson is not included as it is only applicable to bino-
mial values.
comparison between corrected certified radii produced by different simplex maps and temperatures in Fig
2.0
Bernstein's 's inequality
Hoeffding's inequality
Corrected certified radius
1.5
1.0
0.5
0.0
0.4
0.5
0.6
0.7
0.8
0.9
1.0
P1
Figure 2: Comparison between corrected certified radii R2(p) produced by Bernstein's and Ho- effding's inequalities, for random subset of 1000 images of ImageNet dataset using RS with smoothing noise a 1.0. We use the ViT-denoiser baseline from Carlini et al. (2023).
22

---

Published as a conference paper at ICLR 2024
1.15
sparsemax
softmax hardmax
1.14
Corrected certified radius
1.13
1.12
1.11
1.10
0.5
1.0
1.5
2.0
2.5
3.0
Temperature
Figure 3: Comparison of the effect corrected certified radii Ra(p) of the choice of the simplex map and associated temperature t. Simplex maps considered are 8 E (sparsemax, softmax, hardmax]. The base subclassifier the one from Carlini et al. (2023) and the corrected certified radii were generated with one image from ImageNet with smoothing variance 1.0. Radii are risk corrected with Empirical Bernstein inequality for risk a 1c-3 and 10 We see that by varying the temperature f, softmax and sparsemax can find a better solu- tion than hardmax to the variance-mare margin trade-off.
G FIGURES AND TABLES FOR EXPERIMENT 4.2
80
r=0.1
70
r=0.5
60
r-100
50
r-2.0
CA%
40
3=3.0
4.0
30
5-5.0
20
10:
0.1
0.2
0.3
0.4 E
0.5
0.6
0.7
0.8
Figure 4: Certified accuracies (C.A in %) with R, in function of levels of perturbation CIFAR- 10, for different simplex mass Number of samples is n 10a and risk a 1e-3. The case 1.0 corresponds to the regular RS setting.
23

---

Published as a conference paper at ICLR 2024
Baseline
(r-0
60
(a-05)
4C% (a-1
A0%
A0%
20
0.0
0.2
0.4
1.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.8
0.2
0.4
11.6
0.8
1.1
Figure 5: Certified accuracies (C.A in %) function of level of perturbations on CIFAR-10, for different noise levels {0.25, 0.5, 1}. Number of samples is 10 and risk 1e-3. Our method is compared to the baseline chosen as in Carlini et (2023).
100
Ours
80
(o20))5)
(o 0,5)
AC% (c=10)
AC%
AC%
0
0.0
15
2.5
0.0
20
2.5
0.0
1.0
2.0
Figure 6: Certified accuracies (C'A in %) in function of level of perturbations on ImageNet, for different noise levels {0.25, 0.5, 1). Number of samples 10 and risk 1e-3. Our method is compared to the baseline chosen as in Carlini et al. (2023).
Table 5: Certified accuracies comparison for different perturbation e values, for = 10 samples and a 1e-3. On ImageNet dataset. Here the haseline a ResNet- -50 from (Samman et (2019)
Certified accuracy (E)
Methods
0.14
0.2
0.3
0.4
0.5
0.6
0.7
0.8
Salman al. 2019
74.49
73.08
69.84
66.41
62,42
57.75
51.24
0.0
LVM-RS (ours)
76.77
74.99
71.26
67.55
63.43
58,59
51.39
0.0
24

---

Published as a conference paper at ICLR 2024
Table 6: Certified accuracy for a 0.25 on CIFAR-10, 10, for risk or le-3 and n = 10 samples.
Certified accuracy (e)
Methods
0.14
0.25
0.4
0.6
0.75
0.8
Carlini et al. 2023
86.72
80.73
77.47
74.41
71.15
65.01
58.25
51.15
40.96
37.6
0.0
LVM-RS (ours)
88.49
82.15
79.06
76.21
72.73
66.41
60.22
53.41
43.76
40.27
0.0
Table 7: Certified accuracy for o = 0.5 on CIFAR- 10, for risk = 1e-3 and n 10 samples.
Certified accuracy (E)
Methods
0.14
0.2
0.25
0.3
0.4
0.5
0.6
0.75
0.8
1.0
Carlini et al. 2023 74.11 79.79
67.99
65.22
62.89
60.38
55.67
50.43
45.59
39.26
37.11
29.91
LVM--S (ours)
73.45
70.41
68.04
65.8
60.71
55.48
50.07
43.13
40.83
32.35
Table 8:
Certified accuracy for a = 1 on CIFAR- 10, for risk a = 1e-3 and n = 10 samples.
Certified accuracy (E)
Methods
0.0
0.14
0.2
0.25
0.3
0.4
0.5
0.6
0.75
0.8
1.0
Carlini al. 2023
48.97
44.24
42.26
40.76
39.15
35.91
33.08
29.92
20.09
LYM-KS (ours)
63.72
57.99
55.54
53.4
51.23
47.19
43.19
39.76
34.27
32.35
25.71
Table Certified accuracy for 0.25 on ImageNet, for risk a 3e-3 and 10 samples.
Certified accuracy (s)
Methods
0.0
0.5
1.0
1.5
2
3
Carlini et al. (0023)
79.88
69.57
0.0
0.0
0.0
0.0
LVM-RS (ours)
80.66
69.84
0.0
0.0
0.0
0.0
Table 10: Certified accuracy for a 0.5 on ImageNet, for risk 1e-3 and
10 samples.
Certified accuracy (e)
Methods
0.0
0.5
1.0
1.5
2
3
Carlini et al. (2023)
74.37
64.56
51.55
36.04
0.0
0.0
LVM-RS (ours)
78.18
66.47
53.85
36.04
0.0
0.0
Table 11: Certified accuracy for on ImageNet, for risk = 1c-3 and 10 samples.
Certified accuracy (E)
Methods
0.0
0.5
1.0
1.5
Carlini et al. 2023)
57.06
49.05
39.74
32.33
25.53
14.01
LVM-RS (ours)
66.87
55.56
44.74
34.83
27.43
14.31
25


Reviews:
[{"review_id": "nuQpqxyes2", "reviewer": "Reviewer_2wVc", "summary": "This paper identifies a circular dependency between the regularity of the smoothed classifier, the Lipschitz of the base classifier and the variance of gaussian noise in randomized smoothing procedure. Then they propose the LVM-RS framework, given either a Lipschitz constant or variance, one can select the complementary variance or Lipschitiz constant to maximize the synergistic effect of RS and Lipschitz continuity. Experiments show superior performance of the proposed method comparing with RS or deterministic Lipschitz training alone.", "questions": "1. Is there a typo in Eq 4 where \\leq should be \\geq? Currently it contradicts table 1.\n\n2. In algorithm 1, how many temperature do we need? And how to find those temperature?\n\n3. How much computational cost that is induced by using multiple temperature? How sensitive the certified accuracy is with respect to the corrected margin?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper identifies an interesting circular dependency among each ingredient in the RS procedure, and propose a principled way to improve current certification radius in a zero-shot manner.\n\nIn general, the paper is well written and each statement seems to be well supported by proof, empirical evaluation and intuitive explanation. Especially Figure 1 did a great job in summarizing the contribution of this paper.\n\nExperiment results shows superior performance to the current state-of-the-art methods.", "weaknesses": "1. In terms of presentation, I feel the authors could add an overview paragraph for section 3. Sometimes I fail to connect each sub-sections. It may be good to map the flow of section 3 to Figure 1.\n\n2. It will be good to discuss the computational cost of LVM-RS comparing to RS and deterministic Lipschitz.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Bc8HcGvOP9", "reviewer": "Reviewer_12zu", "summary": "This paper studies methods to obtain improved randomized-smoothing (RS) certificates against $\\ell_2$ bounded adversarial attacks. The main contribution is to incorporate the lipschitz constant of the _base_ classifier $f$ into RS certificates to obtain improved bounds on the certified radius of the smoothed classifier $g$. Additionally, RS certificates hold with a probability $1 - \\alpha$, where $\\alpha$ is small. The auxiliary technical contribution of this paper is to utilize the variance of the output of $f$ to control $\\alpha$ better than prior work. Empirical evidence supports the theoretical results, demonstrating improved certificates over prior work.", "questions": "At a high level it would be good to,\n\n(1) clarify and augment the paper with additional technical details to complete the proofs and correct the typos (details above),\n\n(2) explain the precise mathematical details of the certification procedure from input to certificate (see details in weaknesses above), and\n\n(2) empirically ablate the two components of the proposed approach (see details above).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. RS is currently the state of the art certification method for obtaining certificates of robustness against $\\ell_p$ attacks. However, the interaction of the properties of the base classifier with the final certificate is not very well understood. This paper attempts an understanding of how the Lipschitz constant of the base classifier affects the final certificate — this is an interesting problem to study and is potentially very useful for the community. \n\n2. Further, the paper revisits computation of the confidence $\\alpha$ that the RS certificate hold with, and demonstrates how the variance of $f$ (the base classifier) can be used to improve $\\alpha$, via a better concentration inequality. Exploring improved concentration inequalities for RS is also a useful research direction.", "weaknesses": "1. Writing: The writing of the paper is quite wordy in many places, and confusing at times, leading to major issues in readability and clarity. Details:\n\n\t-\tAbstract: It is unclear what “variance introduced by RS”, “simplex projection”, “variance-margin tradeoff” mean. It is unclear what does bernstein’s inequality have to do with any of this. \n\n\t-\tIntroduction: Would be good to define prediction margin. All methods with certified radius deal with a way of controlling /estimating the Lipschitz constant of the network, it is unclear why is Tsuzuku et. al. specifically mentioned. The statements are also quite wordy here (“radius that encompasses … constant”), a simple $|f(x) - f(x + \\delta)| \\leq L ||\\delta||$ would suffice here.\n\t-\tFigure 1: What is radius binding, risk shift, simplex projection? “Risk” is used throughout the introduction without a definition. \n\t-\tP2: The circular dependency mentioned in paragraph 2 was not clear, what exactly is the circular dependency?\n\t-\tThe definition of R(f, x) is written in a very convoluted fashion, isn’t it simply $\\min_\\epsilon$ such that $\\exists$ adversarial example $\\in B(x, \\epsilon)$. The benefit of the written form of the definition is unclear. \n\t-\tThe correct earliest reference for Randomized Smoothing is not Cohen et al. 2019, please see the related work section in Cohen et al. 2019 for the correct references. \n\t-\tDefining the certified radius for the composition of $\\Phi^{-1}$ and $\\tilde f$ is confusing, since the radius is to be used for certifying $\\tilde f$, and not the composition. \n\t-\tSection 2.4: Margins and Robustness — This is again too wordy “promise in bolstering classifier defense”, “inherent synergy between them”, “our exploration dives deep into this nexus unravelling novel insights …”. The message again simply seems to be that greater margin = larger certified radius (at fixed L), and could be stated in a single line.\n\t-\tSection 3.1: Relation between certified Radii. The highlight of this section seems to be the last paragraph, that variance plays a crucial role in the RS certificates. It is unclear what does the rest of the section add to this message. Perhaps it would be better to simply stress this strong point, and detail Table 3.1.\n\t-\tTable 3.1 is hard to parse, could simply plotting the difference between R2 and R3 convey the message better?\n\n2. Technical Correctness: Related to the point above, there are several places where some additional steps / statements are needed to support the technical claims made in the paper: \n\t-\tP3, Proposition 1. Isn’t the condition for correct prediction simply that margin > 2 * Lipschitz Constant * perturbation radius? ( Assume class 1 is majority at x, class 2 is second highest, then $|f1(x) - f1(x + v)| \\leq L ||v|| = L \\epsilon$, and $|f2(x) - f2(x + v)| \\leq L epsilon$. Then, if $f1(x) - f2(x) > 2 L \\epsilon$, then $f1(x + v) > f2(x + v)$). Why is the constant $\\sqrt{2}$, instead of $2$? \n\t-\tAppendix P12, Proof of Proposition 3. \n\t\t-\tWhy is $u \\in R^c$ defined? Doesn’t seem to be used in the proof.  \n\t\t-\tAre there are several typos confusing $\\delta$ with $\\delta’$? For instance why is $E_\\delta [v^\\top \\delta h(x + \\delta)] = E_\\delta [v^\\top \\delta’ h(x + \\delta’)]$? The next step then replaces one of the $\\delta$ with $\\delta’$, which is unclear too.  \n\t\t-\t**Major 1**: Why is $v^T \\nabla \\tilde h(x) = (1/\\sigma^2) E[…]$? Expanding $v^T \\nabla \\tilde h(x)$ gives $v^T \\nabla \\tilde h(x) = E[v^T \\nabla h(x + \\delta)]$, it is unclear how to proceed from here.  \n\t\t-\tIn the step marked (i) in the proof, is there some typo? $|h(x + \\delta) - h(x + \\delta’)|$ is replaced by $\\min(1, 2L) |v^\\top \\delta|$, why is this true? Isn’t this bound $L ||\\delta - \\delta'||$?\n\t\t-\t**Major 2**: In the construction for the lower bound on $J$, $h_0 = (…) \\min (…, l(h)…)$, but how can the constructed classifier depend on its own lipschitz constant. Some clarity is needed on why one can do this, and why this classifier exists. \n\n\n3. Technical Clarity: There are several places where additional clarity would help the reader.\n\t-\tIt is unclear how one obtains (4) by using the bound mentioned in the paragraph preceding it. A few lines would be great for readers not familiar with the proof in Cohen et al. 2019.  \n\t-\tThe Gaussian Poincare inequality seems to be very similar to other well known concentration inequalities for functions of gaussian random variables. A brief contextualization would be great. For instance, how does this relate to the standard concentration inequality for Lipschitz functions of sub gaussian random variables: $P( |h(Z) - E h(Z)| > \\delta ) \\leq \\exp(-c \\delta^2 / L(h))$ (for a reference, see Theorem 5.2.2 in High Dimensional Probability by Roman Vershynin) \n\t-\tEq (5), where is alpha in the RHS? Specifically, it is unclear how the $p_1, p_2$ have any explicit dependence on $\\alpha$. I believe the dependence is that the number of samples n affects both alpha and $p_1, p_2$. But this is not clear at all by looking at (5). \n\n\t-\tRelated to the above point, now since the dependence was not specified in (5), it is unclear how $M_2$ is computed in the main algorithm Algorithm 1. Specifically, what is $\\bar M_2(p, \\alpha)$ on Line 6 of Algorithm 1, how does it relate to $s$, how does it relate to $t$? \n\t-\tWhat are the simplex projections being used in line 4, algorithm 1? The text mentions “for various projections … spanning softmax and sparsemax” — Which projections specifically?  \n\t-\tNow, in order to compute the margin $M_2$, I believe one needs to know the lipschitz constant of the classifier $s$ composed with $f$, how is this computed for each simplex projection chosen? \n\t-\tExperiments: How is the 1-Lipschitz backbone constructed. This should be detailed as it relates to the main contribution.  \n\t-\tExperiments: The effects of the change in the $\\alpha$ calculation vs the change in the certificate are unclear. In particular, what are the results when the $\\alpha$ calculation in this paper is used on top of Cohen et. al.? Similarly, what are the results when the Clopper-Pearson $\\alpha$ calculation are used on top of this paper’s certificate?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "0NKCLAeAF9", "reviewer": "Reviewer_ay9y", "summary": "In this paper authors study the interplay between randomized smoothing, Lipschitz bounds and margin of the classifier, to design a new robustness certification method with improved guarantees.  \nMore specifically, they show that when the Lipschitz constant of a base classifier $f$ is low, the robustness radius of the smoothed estimator $\\tilde f$ can be lower, and the variance of the associated estimators is also lower. Therefore, with the same cost (in $n$ the number of samples) a bigger certified radius can be estimated at risk level $\\alpha$.  \nThe robustness radii rely on a margin, typically the difference between the two highest logits. Author show that `argmax` might not be the best option, and that other options like `sparsemax` have better properties.\n\nFinally, the new certification method is tested and compared against randomized smoothing and Lipschitz-based certification, on Imagenet and Cifar-10 tasks.", "questions": "> Most of the randomized smoothing approaches simplify the margin $-\\max_{y\\neq k}\\hat f_k(x)\\geq -(1-\\hat f_y(x))$ (Cohen et al., 2019)\n\nCan you clarify where in the paper of Cohen? Are you referencing their choice $p_A=1-p_B$ in top of their p6 ?\n\n> For each combination of (s, t), we determine the risk-corrected margin $M_2(p_{st} , \\alpha)$.\n\nIs it statistically correct (w.r.t $\\alpha$) ? Since you perform multiple tests with the same scores $f(x+\\delta_i)$ ? \n\n### Sets and domains of functions\n\nIt is not always clear from context what are the definition of functions. For example:\n* $\\hat f$ is implicitly defined in top of page 4, I assumed you meant $\\hat f_k()$ in the argmax. So $\\hat f:\\mathcal{X}\\rightarrow\\mathbb{R}^c$\n* but $\\Phi$ is a scalar function (per its definition), so what is the meaning of $\\Phi^{-1}\\circ \\hat f$ ? Is it vectorized?\n* so, is $g$ a scalar or a vectorized function Eq (3) ? \n\nIn Sec 2.1 the notation $L()$ is defined as a maximum of gradient norm over $\\mathbb{R}^d$. But the gradient is only defined for scalar functions, not for multivariate functions (in which case it is a Jacobian, not a gradient). This makes sense to define $l(g)=\\max_k L(f_k)$. But, then, if $g$ is multivariate, how can you write $L(g)$ ? What does it mean?  \n\nI suggest to define clearly each notation, and specify the domain of each function, not in an implicit manner in the middle of a formula.\n\n### Runtime\n\nWhat is the runtime cost of your method compared to randomized smoothing?\n\n### Typo\n\nThe paper can be hard to read. In p6:\n\n> Cohen et al. (2019); Salman et al. (2019); Carlini et al. (2023) use argmax simplex projection they can use the Clopper-Pearson Bernouilli tailored confidence interval ... etc\n\nThis paragraph should be rewritten, the first two sentences are not grammatically correct.  \n\n> Proposition 2\n\nIs it a definition of the `shift` function in left hand side? Use `:=` notation like `\\vcentcolon=` if so. Otherwise, define it somewhere. Please add a discussion of what $Z_i$ is supposed to be in *your* context.  \n\n> Once the variance has been minimized via Lipschitz constant regularization and that we can leverage\nlow resulting empirical variance with Empirical Bernstein’s inequality a vital aspect for achieving\na significant certified radius is negotiating the margins-variance trade-off\n\nAdd punctuation.  \n\n> This is because the compensatory shift, incorporated\nto address the inherent risk, becomes minimal\n\nWhat does this sentence mean?\n\n> Equation (4)\n\n$R_2$ and $R_3$ inequality should be reversed.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "### Originality\n\nThe work takes a new look at an existing topic, by incorporating Lipschitz constraints into randomized smoothing. It borrows tools from different fields, like concentration inequalities, projections onto the simplex (argmax, softmax, sparsemax), and robustness certification against adversarial attacks.  \n\n### Clarity\n\nFig 1. helps a lot to the understanding.\n\n### Significance\n\nThe proposed algorithm LVM-RS can be seamlessly ingrated into existing frameworks, it is very general (with different temperatures and simplex projections), and not too expensive to run. The empirical results are convinving, since the new method improves upon both (i) Randomized Smoothing (ii) 1-Lipschitz networks of (Wang & Manchester, 2023).", "weaknesses": "I struggled a lot to understand the paper at times. There is a lack of details, and even with the help of the related literature (e.g. Cohen et al) I couldn't be sure of what the authors were trying to say. My questions are detailed below. Clarifications would benefit a lot to the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Xg7ojJaAv5", "reviewer": "Reviewer_W4Xb", "summary": "This work analyzes the certified radius that can be provided to off-the-shelf classifier that are also Lipschitz continuous. The authors use previous results (namely, that a certified radius can be derived deterministically for Lipschitz predictors, and that randomized smoothing provides probabilistic certified radius as well as Lipschitz smoothed predictors) to show that there exist an optimal way to determine the strength of randomized smoothing that should be applied to a Lipschitz function. In addition, the authors make the observation of changing  the mapping function to the probability simplex as well as better finite-sample concentration inequalities to derived slightly improved guarantees on popular benchmarks (CIFAR10 and ImageNet).", "questions": "**Major Points**\n\n* Throughout the paper, the authors refer to softmax (and other functions) as \"projections\" onto the probability simplex. The softmax is not a projection onto the simplex. In fact, this reviewer believes that the softmax is not a projection onto any set (is it?). Throughout the manuscript, the word \"projection\" is used in lieu of the term \"function\" or \"map\". \n\n* Randomized smoothing can provide a certified radius at varying levels, depending on the strength of the added noise. It is clear to me that leveraging the fact that $f$ is Lipschitz continuous allows the authors to find an optimal randomized smoothing strength, as indicated in Prop. 4. Such a smoothing strength results in a certified radius. What is unclear to me is, what can be done if one requires certification at a different radius? \n\n* page 3: The definition of $L(f)$ that the authors use require $f$ to be differentiable. This assumption is not necessary (as best as I can tell) for their results to hold (and indeed, not applicable to ReLU networks). So, just define $L(f)$ by its standard definition (without assuming differentiability).\n\n* The authors comment on some related works pertaining the analysis of Lipschitz-continuity for devising certified radii. There exist extensions of these ideas that refine the analysis to requiring only local Lipschitzness, as in [A], which lead to improvements on the certified radius. Can the authors comment on relations to that work, and on whether their results could apply in a local way as in [A] ?\n\n* page 4: the authors mention that \"these bounds are relevant for the composite classifier defined as $\\Phi^{-1} \\circ f$. However, I believe they mean the classifier $\\tilde{F}_s$, no? \n\n* The authors argue in Section 3.3 that different functions s(z) have different impacts in terms of the variance of s(Z) vs the variance in Z. This is quite obvious, and, respectfully, I find the Example 1 not useful/trivial. ii) It is unclear, however, how such a map should be chosen to be optimal. It seems to me (from their experimental section) that they simply compute different options based on different alternatives for s(z) and choose the one that results in larger empirical margin. Is this correct? Shouldn't one be able to provide a \"best\" choice for s(z)?\n\n* After Prop. 3, the authors mention that \"This refinement on the bound was possible by supposing Lipschitz continuity on the base classifier $f$. Note that its Lipschitz constant can be arbitrarily high, so this assumption is quite light\". What do the authors mean by \"light\" here?\n\n\nReferences:\n\n(A) Muthukumar et al, \"Adversarial Robustness of Sparse Local Lipschitz Predictors, SIAM Journal on Mathematics of Data Science, 5:4, 2023\n\n\n\n**Other points**:\n* page 1: the authors write that there's a \"circular dependency: the regularity of the smoothed classifier depends on the Lipschitz property of the base classifier and the variance of the Gaussian convolution which governs the induced level of smoothness.\" Yet, i don't see how this is a circular dependency.\n\n* page 3: what do the authors mean by \"furnished by $f$\"?\n\n* page 3: \"concerning the $\\ell_2$ norm\" -> \"w.r.t.... \"\n\n* page 3: In defining the margin of $f$ at $x$, it should be \"of $f$ at $(x,y)$\", since its definition uses the correct label $y$.\n\n* Prop. 1: The first sentence is incomplete. Please revise English usage.\n\n* The authors use the term \"sub-classifier\" to refer to the un-robustified function $f$, alas sometimes they refer to it as a \"classifier\" (as in Prop.3)\n\n* It might help the reader to make explicit what the final classifier is (which I believe is $\\argmax_{s,t} \\tilde{F}^t_s(x)$, no?)\n\n* In the conclusion: \"In this paper, we demonstrate a significant correlation between the variance of randomized smoothing and two critical properties of the base classifier\" I don't think the authors demonstrate any \"correlation\" between these things. Maybe they meant \"connection\"?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- While it has been known that randomized smoothing provides a Lipchitz continuous randomized classifier, with constant inversely proportional to the smoothing strength, it has been unclear what one can gain by incorporating the (natural) assumption that base (or sub) classifier is also Lipschitz. In my opinion, this is the main contribution of this paper, which is nice.", "weaknesses": "- The paper is at times verbose, and at times unclear. Some comments are exaggerated or incorrect (See below).\n- Nomenclature is often incorrect (see below).\n- In my view, the contributions of employing a better concentration inequality to provide tighter tail guarantees for finite samples is small, as is the fact of changing the function that maps the sub-classifier predictions to the probability simplex.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)