Heating up decision boundaries: isocapacitory saturation, adversarial scenarios and generalization bounds
Authors: Bogdan Georgiev
Lukas Franken
Mayukh Mukherjee
Venue: ICLR 2021 Poster (2021)
Keywords: Brownian motion
deep learning theory
decision boundary geometry
curvature estimates
generalization bounds
adversarial attacks/defenses

Abstract: In the present work we study classifiers' decision boundaries via Brownian motion processes in ambient data space and associated probabilistic techniques. Intuitively, our ideas correspond to placing a heat source at the decision boundary and observing how effectively the sample points warm up. We are largely motivated by the search for a soft measure that sheds further light on the decision boundary's geometry. En route, we  bridge aspects of potential theory and geometric analysis (Maz'ya 2011, Grigor'Yan and Saloff-Coste 2002) with active fields of ML research such as adversarial examples and generalization bounds. First, we focus on the geometric behavior of decision boundaries in the light of adversarial attack/defense mechanisms. Experimentally, we observe a certain capacitory trend over different adversarial defense strategies: decision boundaries locally become flatter as measured by isoperimetric inequalities (Ford et al 2019); however, our more sensitive heat-diffusion metrics  extend this analysis and further reveal that some non-trivial geometry invisible to plain distance-based methods is still preserved. Intuitively, we provide evidence that the decision boundaries nevertheless retain many persistent "wiggly and fuzzy" regions on a finer scale.
Second, we show how Brownian hitting probabilities translate to soft generalization bounds which are in turn connected to compression and noise stability (Arora et al 2018), and these bounds are significantly stronger if the decision boundary has controlled geometric features.

Published as a conference paper at ICLR 2021
HEATING UP DECISION BOUNDARIES: ISOCAPACITORY SATURATION, ADVERSARIAL SCENARIOS AND GENERALIZATION BOUNDS
Bogdan Georgiev
Lukas Franken
Fraunhofer IAIS, ML2R
Fraunhofer IAIS, ML2R, University of Cologne lukas ... frankene gmail com
bogdan. m. wen.grggieeegmiilll... com
Mayukh Mukherjee
IIT Bombay ma cheukherreee@gaaae com
ABSTRACT
In the present work we study classifiers' decision boundaries via Brownian motion processes in ambient data space and associated probabilistic techniques. Intuitively, our ideas correspond to placing heat source at the decision boundary and ob- serving how effectively the sample points warm up. We are largely motivated by the search for soft measure that sheds further light the decision bound- ary's s geometry. En route, we bridge aspects of potential theory and geometric analysis (Maz'y ya (2011); (Grigor' Yan & Saloff-Coste (2002)) with active fields of MI. research such as adversarial examples and generalization bounds. First, we focus the geometric behavior of decision boundaries in the light of adversarial attack/defense mechanisms, Experimentally, we observe certain capacitory trend over different adversarial defense strategies: decision boundaries locally become flatter as measured by isoperimetric inequalities (Ford et al.) (2019)); however, our more sensitive heat-diffusion metrics extend this analysis and further reveal that some non-trivial geometry invisible to plain distance-based methods is still pre- served. Intuitively, we provide evidence that the decision boundaries nevertheless retain many persistent "wiggly and fuzzy" regions a finer scale.
Second, we show how Brownian hitting probabilities translate soft generalization bounds which are in turn connected to compression and noise stability (Arora et al. (2018)). and these bounds are significantly stronger if the decision boundary has controlled geometric features.
INTRODUCTION AND BACKGROUND
The endeavor to understand certain geometric aspects of decision problems has lead to intense research statistical learning. These range from the study of data manifolds, through landscapes of loss functions to the delicate analysis of a classifier's decision boundary. In the present work we focus on the latter. So far, wealth of studies has analyzed the geometry of decision boundaries of deep neural networks (DNN), reaching profound implications in the fields of adversarial machine learning (adversarial examples), robustness, margin analysis and generalization. Inspired by recent isoperimetric results and curvature estimates (Ford et al. (2019); Moosavi-Deztooli et al. (2019); Fawzi al. (2016)), we attempt to provide some new aspects of decision boundary analysis by introducing and studying corresponding hiffusion-inspiree approach.
In this note the guiding idea is to place heat source at the classifier's decision boundary and estimate its size/shape in terms of the amount of heat the boundary is able to emit within given time (Fig. [ The goal to extract geometric information from the behavior of heat transmission. This technique of heat content seems well-known within capacity/potential theory and has led to variety of results in spectral analysis relating heat diffusion and geometry, Jorgenson Lang (200T); Grigor Yan
Saloff-Coste (2002); Maz' ya (001).. However, working with such heat diffusion directly in

---

Published as a conference paper at ICLR 2021
Figure I: Heating up planar decision boundary of a 5-layer MLP over time. The amounts of radiated heat reflect the geometry of the decision boundary: size, density, curvature.
terms of the corresponding differential equations is impractical. this end, we note that, due to Feynman-Kan Kac duality, the heat estimates are convertible to Brownian motion hitting probabilities. Thus we circumvent the need for solving intractable differential equations and instead are able to employ straightforward Monte-Carlo sampling scheme in the ambient data space (Section 3
Background on defense training We apply the above analysis in the context of adversarial ma- chine learning (Section 4) where studies the interaction between adversary and ML system. One of the goals of the subject is to design attack/defense training strategies improving the robustness of given MI. model - in the present work are interested in how adversarial/noiss defense training are reflected geometrically. Many different metrics to estimate robustness have been proposed: on one hand, there is adversarial robustness (the probability that error samples lic very near a given data point r); on the other hand, there is corruption robustmess (the probability of getting an error sample after perturbing given data point x with some specified noise). our context, heat diffusion naturally suggests capacitory robustness metric: this metric is built upon the probability that Brownian motion started at a given data point will hit error samples within a given time window. One can perceive this metric continuous paths and specified stopping time determined by boundary impact). In this perspective, our work is aligned with studies of other robustness metrics and curvature results (ef. Fawzi et al. (2016) for a "semi-random" projection robustness and relations to curvature). We study the capacitory metric on the well-known CIFARIO and MNIST datasets and observe that defense training techniques may either yield a certain (although not substantial) decrease (noise training) or fail to have significant effect on continuous Brownian attacks overall. Surprisingly, in both cases the studied capacitory metric does not converge to the corresponding value as in the case of a flat decision boundary. Due to our comparison statements and curvature considerations, this means that locally around clean data points the geometry is in general flattened out but may still retain complexity and substantial areas of (small) non- vanishing curvature. In other words, from the point of view of our heat diffusion metrics, decision boundaries locally exhibit non-flat behaviour.
combination of adversarial and noise robustness (Brownian motion has
Background on generalization estimates Finally, we observe that the collected heat/hitting- probability metries can further be used to obtain generalization bounds where, in nutshell, one evaluates the performance of a model on unseen data in terms of the performance over a given sampled data, the model's 's expressiveness, dimension, etc. In this regard, heat diffusion traits as an indicator of how noise-stable given model is this relates Brownian hitting bounds with recent compression-basee based generalization techniques in the spirit of Arora et al. (2018); Suzuki et al. (2018) 2020). More precisely, we proceed in two steps: first, we construct a "smaller" compressed model that almost equivalent the initial one in an appropriate heat-theoretic way; second, we obtain generalization estimates for the smaller model in terms of the decision boundary hitting probabilities (computed on the empirical dataset). Furthermore, the bounds are significantly improved under additional geometric assumptions on the decision boundary of the initial model.
view decision boundary
e
Additional related work The interplay between heat diffusion and geometry lies at the heart of many topics in geometric analysis and spectral theory (cf. Jorgenson & Lang (2001): Grigor Yan (200T) for a far reaching overview). Some direct applications of heat diffusion techniques to zero sets of eigenfunctions
seen, for example, in |Steinerberger (2014); Georgiev & Mukherjee (201 8a b). The literature on adversarial ML is vast: to name a few central works in the field, we refer to Dalvi et al. (2004); Biggio & Roli (2018) Szegedy al. (2014). Much effort has been invested in designing
2

---

Published as a conference paper at ICLR 2021
and understanding strategies that will render model robust to various attacks (e.g. Madry et al. (2018); (Crliii & Wagner (2017)). )) In particular, the geometry of decision boundaries has been the focus of many works in the subject leading to breakthroughs in curvature estimates, boundary flatness and robustness, schemes for detecting boundary complexity, proposing adversarial attacks/defenses and diffusion based techniques towards constructing decision boundary from partially pre-labelled
data (c.g. Ford et al. (2019); Fawzi et al. (2016) 2018 8); Dezfooli et al. (2018); Moosavi-Dezione
al. (2019); Karimi et al. (2019); Karimi& Tang (2020); He et al. (2018); (zllmm et al. (2008))
The theory of generalization bounds has formed a classical main line of ML and statistical inference
research [aanik] (1999). In this direction central questions address the generalization properties of
heavily over- parametrized deep neural network models. According to some classical VC-dimension results such models should overfit the data and generalize poorly. Extensive research effort has been invested in developing appropriate sharper techniques to explain generalization of DNN models: on one hand there are the methods based on norm estimation whose bounds are not explicitly using the number of the network's ' parameters (see Golowich et al. (2019); Neyshabur et al. (2015) 2018); Weil & Ma (2019)) Bartlett et al.] (2017), etc). On the other hand, recent results based on compression and VC-dimension can lead to sharper bounds (Arora et al. (2018); (Suzuki et al. [2018 2020
2 CONTRIBUTIONS, CONTEXT AND PAPER OUTLINE
An outline of our essential contributions is given as follows:
1. We analyze decision boundary geometries in terms of novel heat diffusion and Brownian motion techniques with thorough theoretical estimates on curvature and flattening.
2. We show, both theoretically and empirically (in terms of adversarial scenarios on state- of-art DNN models), that the proposed heat diffusion metrics detect the curvature of the boundary; they complement, and in some respects are more sensitive in comparison to previous methods of boundary analysis intuitively, our heat driven metrics are sharper on a finer scale and can detect scall-scale "wiggles and pockets". As an application, we are thus able to provide evidence that adversarial defenses lead to overall flatter boundaries but, surprisingly, the heat traits do not converge to the corresponding flat-case, and hence, finer-scale non-linear characteristics (e.g. "wiggles and pockets") are persistent.
3. Moreover, the preservation of "wiggles and pockets" " means that susceptibility to naive Brownian motion attacks is not significantly decreased via adversarial defense mechanisms.
4. Finally, we introduce a novel notion of compression based on heat diffusion and prove that stability of heat signature translates to compression properties and generalization capabilities.
In terms of context, the present note is well-aligned with works such as Ford et al. (2019): Dezfooli et al. (2018); |Fwzi et al. (2116 2018). Among other aspects, these works provide substantial analysis of the interplay between gcometry/curvature and adversarial robustness/defenses - in particular, we use some of the these tools (e.g. isoperimetric saturation) as benchmarks and sanity checks. However, in contrast, in our work we provide eenivaluv technique to address decision boundary geometry for which we provide an extensive theoretical and empirical evaluation with insights on the preservation of finer-scale traits. Intuitively, previous distance-bane -baed geometric methods could be considered as "coarser lens", whereas the present heat-diffusion tools appear to be much more sensitive. As a large-scale example, Brownian particles emanating from a point are able to distinguish between a decision boundary which is a hyperplane at distance and a decision boundary which is cylinder of radius d wrapping around the point. Our notion of compression is inspired by Arora dimension reduction
jet al. (2018). and establishes a connection between the algorithm with diffusion techniques. Furthermore. we bridge the proposed heat-theoretic techniques with generalization bounds in the spirit of Arora et al. (2018); (Suzuki et al. (2020). In particular, this shows that overall lower heat quantities at sample points imply better generalization traits. A step-wise road map of the present work is given below:
(Subsection 3.1 We start by discussing what heat diffusion is and how it is to be evaluated here we discuss that, via Feynman- Kac duality, one can essentially work with Brownian motion hitting probabilities.
(Subsections 3.2 and 3.3) We introduce the isocapacitory saturation 7 a theoretic metric that will be used to estimate boundary flatness. Moreover, here we emphasize the
3

---

Published as a conference paper at ICLR 2021
N
vut
pash
Figure 2: A planar 2-class dataset that alternates along a circle. (Left) A depiction of the planar circle-like dataset and the corresponding decision boundary of 5-layer MLP. (Center) Brownian paths starting at data point x and killed upon impacting the decision boundary/opposite class, (Right) Set-up of the local Brownian motion analysis with notation on radius r, dimension n and Brownian runtime t.
properties of such relations to curvature (Proposition 3.1) and the novel information obtained from heat theoretic methods in comparison to previous distance-based ones.
We compute т for certain geometric model cases such as hyperplanes, cones, wedges and "spiky" sets (Lemmas 3.2 and 3.3). This allows us later to evaluate how much a given geometry resembles these model cases.
(Subsection 3.4)
(Section 4 Next, are in a position evaluate and compare T for decision boundaries of DNNs. We experimentally illustrate the effect of adversarial defense mechanisms and noise robustness on (PGD/FGSM on MNIST and CIFAR-10).
(Section 5) We prove that heat transmission relates to generalization bounds (Propositions a.I 5.2) in particular, lower levels of heat at sample points yield sharper generalization bounds. Finally, we complete the discussion by informally stating our compression scheme.
(Appendix) Our methods leverage several tool sets extensively. For this reason goal in the main text to only collect and showcase the techniques and results. However, the thorough de-thpth analysis is provided in the Appendix where the reader can find all relevant proofs and further background and references.
MOTIVATION AND MAIN IDEAS
3.1 GEOMETRY SEEN THROUGH BROWNIAN MOTION AND DIFFUSION
Notation Let consider dataset X' {1r })) consisting of feature points 2; R and their corresponding labels E (1...., k). Let us suppose that la-le classifier f RR" - R labels a point æ E X' as arg max.c(1.M) [i] The decision boundary of f is given by N == {a e [=) has two or more equal coordinates) (cf. Fig. 2 Assuming f is sufficiently regular, one thinks of N as collection of hypersurfaces in R". Further, for given target label we define the target (error) set FY()) as the set of points on which the classifier's decision is different from y, i.e. F(y) := (a: E T arg max f [x)[f] y) (here remark that if arg max is set-valued with several coordinates obtaining the maximum value, then by convention is contained in E(y)). Clearly, if given data sample (Zo, Yo) E X' is correctly classified by f. then is outside of the error set (zoo). Finally, we note that the boundary E(y) coincides with Ely) N. and moreover, A is the union of the boundaries of E(y) for all labels
Feynman-Kac duality and hitting probabilities As mentioned in Section I we wish to study a heat diffusion process where we place heat source at the decision boundary Nr formally, this is given by heat equation with appropriate initial and boundary conditions (Appendix, Subsection A.2) Avoiding the impracticality of working with the differential equations directly, bring forward the theorem Feynman- Kac that relates the solution the diffusion process to hitting probabilities of Brownian motion (Appendix, Subsection A.3 By way of notation, for open set U C R let
4

---

Published as a conference paper at ICLR 2021
(2, t) denote the probability that Brownian particle starting at the point will enter U within time t. In other words,
du (z. t) = P 13 [0, (tto E U], xE
(1)
where w denotes a Brownian motion defined over the interval [o, that follows the standard Euclidean Wiener distribution. The amount of heat that point x receives from N within time t is comparable to the hitting probability that a Brownian particle starting at x will impact the boundary within time t (ef. Fig. 2 Provided that is correctly classified this is equivalent to the probability of impacting the decision boundary. In general, we evaluate WBy) (a, 1) (which we often denote by (1, () by minor abuse of notation) through direct sampling; however, in some model cases, e.g. E(y) being a half-space, spherical shell conical set, (ar, t) has concise closed form (Subsection 3.4 helow) that can be evaluated analytically. This allows us to easily measure deviations and compare the heat imprint of A particular model cases.
Local analysis and set-up As mentioned above our analysis is local. For each clean data point x consider ball rx) centered at x with radius and perform all computations there. In particular, a free Brownian motion starting at x and defined over a maximal time interval [0, 4] will on average travel a distance of ví (Appendix, Subsection A. This suggests to couple and the maximal Brownian running time via r = vnt (cf. Fig. 2). so that, not stopped by boundary impact, Brownian motion will, average, reach the sphere BB r)) by its maximal stopping time.
3.2 AN ISOPERIMETRIC AND ISOCAPACITORY PERSPECTIVE
Isoperimetric results Isoperimetric estimates will be the starting baseline (Ford et al. (2019) to detect low levels of curvature and boundary flatness. For some background in isoperimetric results we refer to (Appendix, Subsection A.4). Let us start by defining the relative error volume
p(x,)) r) Vol(E(y) n B(x,))
(2)
(x)(B(x,r))
We recall the so-called Gaussian isoperimetric inequality Borell (1755; Ford et al. (2019)
d r (w)
1 1/22
(3)
where x-1 denotes the inverse standard normal c.d.f. and where d == ((,,N,, denotes the median
distance with å varying normally and concentrated in the ball B(x,r), r). and d = 0 if μ 2 1/2. Here the isoperimetric result rigid in the sense that equality in (3) occurs only if E(y) is a half-space. In Ford et al. (2019) the authors demonstrate that defense training mechanisms lead to decision boundaries that saturate this isoperimetric inequality, i.c. in this isoperimetric sense, the decision boundary N becomes locally closer to being a flat hyperplane. We define the ratio between the LHS and RHS in eq. (3) as the isoperimetric saturation.
Isocapacitory results In our context of hitting probabilities (eq. (). results in potential theory allows us to prove isocapacitory bounds which are similar in spirit to isoperimetric bounds. More precisely one has:
p(z,r) r) cn (z, t),
where cn is an appropriate constant depending on the dimension n. and r /nt. nt. The proof relies on potential theory tools (capacity) and can be found in Appendix, Proposition A.3 Motivated by the above isoperimetric saturation results, one of our main goals is to study how compares to (zr, l). To this end we define the isocapacitory saturation
(xx 2)(2z t²
(5)
u(xrr)
The basic guiding heuristic is that high values of indicate that Ely) has very low volume in comparison to its boundary size and respective heat emission. This is the case whenever E(y) is a very thin region with well-spread boundary of large surface area e.g. set that resembles thin spikes entering the ball B(x, r). In contrast, lower values of T should indicate a saturation of the isocapacitory inequality 44) and imply that E(y) has volume that is more comparable to its heat emission e.g. thicker sets with tamer boundary. To quantify this intuition, we explicitly evaluate r for some model scenarios (Subsection 3.4
5

---

Published as a conference paper at ICLR 2021
3.3 THE NOVEL INFORMATION GIVEN BY HEAT DIFFUSION
Distances vs. hitting probabilities As discussed above, several works investigate decision bound- aries in terms of distance-based analysis (Ford et al. (2019); Fawzi et al. (2016); Karimi & Tang (2020): Karimi et al. (2019). We remark that our analysis based on hitting probabilities augments and extends the mentioned distance-based approaches. Although related, the two concepts are not equivalent. A guiding example is given by E1) being a dense collection of "thin needles" " (Appendix, Subsections A.4 A.55p in such a scenario the average distance to N is very small, as well as the chance a Brownian particle will hit N.. On the other hand, if N is a dense collection of hyperplanes, the average distance to N is again small, but Brownian motions almost surely will hit N. In this sense, evaluating hitting probabilities yields different perspective than is available from distance-based analysis and sheds further light on the size and shape of the decision boundary, particularly with regards to its capacity and curvature features.
Isoperimetric vs. isocapacitory saturation Another demonstration of the additional information obtained through is given by almost flat shapes in higher dimensions that saturate isoperimetric bounds (Appendix, Subsection A.44.. In these scenarios small geometric deformations can have a significant impact on r, and at the same time almost preserve isoperimetric bounds. In other words
provides an additional level of geometric sensitivity. We discuss this further in Section
The effect of curvature The interplay between curvature of the decision boundary and robustness has been well studied recently, e.g. FFwzi et al.] (2016); Moosavi-Dezfooll et al. (2019) where various forms of robustness (adversarial, semi-random and their ratio) have been estimated in terms of the decision boundary's is curvature. Intuitively, the differential geometric notion of curvature measures how a certain shape is bent. The precise definition of curvature involves taking second-ordes derivatives which is in most cases impractical. However, in context we show that the isocapacitory saturation r implies certain curvature bounds. These statements exploit relations between curvature and volume and lead to pointwise and integral curvature bounds. As illustration, we have:
Proposition 3.1 (Informal). Let (z. y) E X be data sample. Then, provided that the distance (xx, is kept fixed, larger values of T locally imply larger pointwise/integral curvature values.
A deeper analysis with formal statements and additional details are provided in Appendix, Subsection A.6 The advantages that curvature yields for some types of compression schemes and generalization bounds is also intenscly investigated in Appendix, Section B
3.4 MODEL DECISION BOUNDARIES; HYPERPLANES, WEDGES, CONES AND "SPIKY" SETS
Given a certain geometric shape, one is often faced with questions as to how flat or spherical the given geometry is. To this end, central technique in geometric analysis is comparing to certain model cases e.g. a sphere, plane, saddle, etc. After having introduced F and its basic traits we now evaluate it for several model cases (flat hyperplanes, wedges, cones, balls and "spiky" sets). Each of these model cases illustrates a distinguished 7 r-behaviour: from "tame" behaviour (hyperplanes, balls) to explosion (thin cylinders, "needles and spiky" sets). Hence, having comparisons these model cases and given an decision boundary, one can, quantify how far away is the given surface from being one of the models. We start by discussing the flat linear case:
Lemma 3.2. Let (I. y) be a data sample and suppose that Ely) forms half-space distance d from the given data point x E R.. Then
(_ d
Vol (B(rr)))
T(x,r) -xxr))220 2
(VE)
Vn(d,r) r)
where (() is the c.d.f. for the standard normal distribution, and V, (d,r) is the volume of the smaller n-dimensional solid spherical cap cut-off at distance d from the center of a ball of radius r.
The computation uses standard reflection principle techniques. Figure 3 depicts an experimental discussion on Lemma Another illuminating model is given by a "spiky" - thin cylinder, which is in some sense the other extreme. We have
Lemma 3.3 (Appendix, Subsection A.5). Suppose that Ely) is a cylinder of height and radius that enters the ball B(x,) r). Then 7 0o as P O.

---

Published as a conference paper at ICLR 2021
volume hidden
capacity hidden
140
140
120
120
100
102
80
Figure 3: A visual depiction of decision boundaries and saturation T for 5-layer MLP models with 20 and 100 hidden units trained over planar "circular" dataset (depicted in grey). For each data sample x the ball (xx, r) is selected so that the relative volume uuæ,, r) is 0.1. According to Lemma 3.2 flat decision boundary would correspond
T 3.32. (Left) The saturation exhibits bi-modal behaviour with peaks around the values 3 and 4.3. These correspond to data points squeezed between thin elongated regions that locally closely resemble the flat case, or tinier "pockets" with higher curvature, respectively. (Righr) The saturation is more closely concentrated around 4.3 and, accordingly, the decision boundary mainly consists smaller "pockets" of higher curvature.
Further comparison results for additional model cases are given in Appendix, Subsection A.5
4 ADVERSARIAL ATTACKS AND DEFENSES
Background and set-up We now analyze how strategies for improving adversarial and noise shift robustness affect the decision boundary's 's heat diffusion properties. In particular, we keep track of Brownian hitting probabilities v and the isocapacitory saturation т. On one hand, we can view 1/ capacitory robustness metric against continuous interpolation attacks given by Brownian noise (see also Section D]. On the other hand, Subsection 3.4 indicates how the behaviour of reveals deviation from the case of a flat or "spiky" and curvy decision boundary. Our empirical analysis uses the well-known CIFARIO and MNIST datasets (details, preprocessing and enhancements are given in Ap- pendix, Subsection C.5). For CIFARIO. 10, we used the -ide-ResNet-288- 10 (Zagoruyko & Komodakis (2016); Ford al. (2019) ) and ResNets with 32, 44 and 56 layers (He et al. (2016)). For MNIST, we selected LeNet-S and additional CNN architectures. Motivated by previous work (e.g. Ford et al. (2019)), we perform 3 types training: ordinary stochastic gradient descent (ADAM optimization), training with Gaussian noise data augmentation and training with adversarial defense strategies (FGSM and PGD methods, see also Appendix, Section C.4 for details and remarks on robustness). Detailed outline of the numeries behind Brownian motion sampling, issperimettic//socaaacttr saturation and relative volume sampling are given in Appendix, Subsection C.3
Analysis of results Recent results (Ford et al. (001);; Schmidt ct al. (017)) have shown qualitative differences between the adversarially robust boundaries of MNIST and CIFAR-10 10, which also impact the experimental findings in this work. In short, a robust decision boundary in the MNIST case less spiky in comparison CIFAR. For more details refer Appendix, Subsection
C.2 In Fig. 4 we collect the statistics of the WRN and LeNet models on CIFAR 10 and MNIST, respectively. On one hand, confirm previous results (Ford et al. (2019); Fawzi et al. (2016) implying the caatteingg-o-boundarr phenomenon: noisy and adversarial training appear to improve and saturate isoperimetric bounds. Furthermore, the ball B(x, r) realizing relative error volume μ of 1% is on average scaled up for adversarial and, especially. noisy training. On the other hand, an intriguing behaviour is observed for the decision boundary's heat diffusion traits. The isocapacitory saturation does not appear to concentrate around the value corresponding to flat hyperplane: defense training strategies, both FGSM and PGD-based, may not have a significant impact on the behaviour by forcing it to converge to the case of flat decision boundary (shown horizontal red punctured line). Put differently, the chance that a continuous Brownian perturbation will find an adversarial example (scaled to the appropriate ball B(x, r)) will not be significantly altered average (see Appendix, Subsection[C.7 for a visual reference). However, appears that noisy training consistently delivers lower values of -iituiiiively this is expected the decision boundary is adjusted in terms
7

---

Published as a conference paper at ICLR 2021
Set. of socapacitory bound
Radius with vol of
Set. Isoperimetric bound
1.0
GD
2.0
0.0
Widee-Reshet
0.7
0.8
0.5
0.0
1.30
LeNet-5 (MNIST)
2.5
1.00
0.55
1.5
10
0.55
0.5
Faturally trained
adversarially by (gamm)
advernanialy ipod)
Geussian data s. w.gmencation 0:41
Figure 4: Results for a Wide-ResNet 28-10 and a LeNet-5 trained on CIFARIO and MNIST, respec- tively. Different boxplots correspond to different training strategies: ordinary, adversarial, with noise or with a Brownian augmentation. Data collected over 1000 test data points, where each radius is selected that the relative isocapacitory saturation т, the radius realizing l = 1% and the isoperimetric saturation. Finally, red punctured horizontal lines indicate the corresponding values for flat decision boundaries.
volume μe equals 1%. Left-to-right the columns correspond the
of adding Gaussian "blobs", thus naturally being rounder. Geometrically, the sensitivity of small perturbations in almost flat surfaces (Subsection) 3.2) indicates that locally around clean (unperturbed) data points an amount of curvature and more complex geometry are still retained. Of course, this amount is not as large as to violate saturation of isoperimetric bounds and robustness comparability results in the sense Fawzi et al. (2016). For example, in the case CIFARIO simple geometric model surface that has similar --behaviour (as for the adversarial and noisy training) is given in (Appendix, Subsections A.4 ::3): considering data point æ, an almost flat decision boundary that concavely bent w.r.t. with approximate curvature of As 1/(12.3r). These observations reveal finer properties concerning decision boundary flattening due to defense training: in particular, noisy training appears flatten decision boundaries and slightly bend them concavely w.r.t. the clean data points. Further results for ResNet models and CNN are provided in (Appendix, Subsection C.7
Spiky sets and control on In Fig. 4 large outlying values of are filtered out. However, values of 7 larger than 10 can occupy up to 1.3% for ordinary training and 2.1%, 2.6% for adversarial, noisy training, respectively. It follows, that the geometry of high-dimensional decision boundaries does not admit too many high-curvature (see also Proposition 3.I] spiky regions of low volume and high heat emission (high surface area) in the sense of Subsections 3.2 However, it appears that defense training can increase the number of such spiky regions: one might explain such behaviour by seeing defense training able to agree and thus lead to a more degenerate (singular) geometry. Further, with respect to the initial analysis of Fig. 4 a natural question is whether one can control 7 along with the isoperimetric saturation ultimately, ly one hopes to design better decision boundaries (flatter, or appropriately curved al.] (2019)) eventually leading to more robustness. However, getting tight control on 7 could be a difficult task. It is, indeed, possible to obtain some basic grip on т: we trained LeNet-5 architecture on MNIST that exhibited significantly increased values and preserved isoperimetric saturation (statistics are shown as the rightmost boxplot in Fig. 4). Similar to many adversarial defenses, the training consisted augmenting the dataset with attacks given in this case by Brownian paths. However, it seems difficult to force to concentrate around the flat-case value, as well as to obtain competitive robustness the model. On one hand, this explained via the need to control heat diffusion through Brownian motion the mentioned naive method is not able to capture the hitting properties sufficiently well; on the other hand, as discussed above heat diffusion properties can be far more sensitive than isoperimetric saturation w.r.t. minor geometric perturbations.
bundle of additional geometric conditions that sometimes not
Moosavi-Dezfooli
8

---

Published as a conference paper at ICLR 2021
5 GENERALIZATION BOUNDS IN TERMS OF HITTING PROBABILITIES
Compression, noise stability and generalization Recent advances (Arora al. 2018); Suzuki et al. (2018) 2020) indicate that generalization can be related to compression and noise stability. The guiding strategy is: (I) a large DNN f that is stable against (layer-wise) noise injections admits an effective compression to a simpler model î which is almost equivalent to f. Intuitively, the noise stability absorbs the defects introduced by compression: (2) concentration results imply generalization bounds for f. Admittedly, the generalization estimate is obtained initially for the smaller model; however, is also possible to "transfer" the bound to f (see the discussion at the end of this Section).
In this context simple observation is that Brownian motion and its hitting probabilities can be related, respectively. to noise injection and margins of classification: small hitting probability of the decision boundary should indicate "margin-safety" and allow compress parameters of the model more aggressively. However, in contrast to injecting normal noise, Brownian motion, with stopping time given by boundary impacts, is more delicate and requires further analysis of the decision boundary. In the following we propose theoretical framework that, we hope, will augment and produce further insights into the interplay between noise stability and generalization bounds. The statements are inspired by the results in Arora et al. (2018); (uzuui et al. (2020) and we follow the notation therein. First, we propose several options for goodness of approximation (compression) in the sense of heat diffusion (Appendix, Subsection
B. We give the following definition:
Definition 1. Given a positive real number 1), classifier g is said to be an 1) -omoprressoon of if
We, (x; - 1 (x,,7 72) < 1
(7)
for all points x in the training sample, labels y and real numbers TV.
Now, as mentioned above we have the following generalization bounds for the compressed model: Proposition 5.1. Let us suppose that f is approximable by g in the sense of Desinition [ Here g E A, where A is a family of classifiers R= + IR parametrized by parameters assuming r discrete values. For classifier h, let On (z.y,t y,t) be the event that Brownian path starting at x hits Ey(y) within time t. Then t S t2
S T we have
(Valeer
Lo(g)= S PR.NiDD (C (x, (( (Cy(E, + (n
(8)
m
with probability least e gloor and Le denoting the expected loss over the true data distribution.
Taking 12 + in (8), one recovers the empirical loss fo(f) on the RHS. In other words, the generalization of the smaller model g is controlled by hitting probabilities of the initial model f and corrections related to family capacity. The next natural question is the construction of g. Inspired by techniques (cf. also Arora et al. 2018)) we are able to recover the following statement (thorough details are given in Appendix, Subsections B.5 B.6
neural network f where some flatness conditions on the layer decision boundaries are fulfilled, there exists an n-compression g in the sense of Def. 7 whose number of parameters is logarithmically smaller than f-
Proposition 5.2 (Informal). Considering fully connected
Finally, having the generalization estimates on the smaller model g it is natural attempt transferring those to the initial model f in Suzuki et al.] (2020) this is achieved via certain local Rademacher complexity and "peeling" techniques. However, we choose not to pursue these bounds in the present work and assume the perspective in |n/oora et al. (2018) that g, being almost equivalent to f. provides a reasonable indicator of generalization capabilities.
ACKNOWLEDGMENTS
We would like to thank our anonymous reviewers whose advice helped improve the quality of the presentation. We are indebted to Prof. Christian Bauckhage for his constant encouragement, support and fruitful discussions. We also sincerely thank Benjamin Wulff for maintaining the outstanding computation environment at Fraunhofer IAIS his support and coffee conversations played an essential role for our empirical analysis. In part, this work was supported by the Competence Center for Machine Learning Rhine-Rull (ML2R) which is funded by the Federal Ministry of Education and Research of Germany (grant no. 01 1S11 18038BB... We gratefully acknowledge this support.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In 35th International Conference on Machine Learning, ICML 2018, 2018. ISBN 9781510867963.
Peter L.
Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalizeed margin bounds for neural networks. In Advances in Neural Information Processing Systems, 2017.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Puttern Recognition, 2018. ISSN 00313203, doi: 10.101 (0.1016/j.patcoo.200 8.07 .2.0.2.
Christer Borell. The Brunn-Minkowski inequality in Gauss space. Inventiones Mathematicae, 1975. ISSN 00209910. doi: (0.1007/BF0142551
Yurii Dmitrievich Burago and Viktor Abramovich Zalgaller. Isoperimetric Inequalities for Various Definitions of Area. In Geometric Inequalities. Springer, 1988. doi: 10.1007/978-3-662-0777
3.
Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. In Proceedings IEEE Symposium on Security and Privacy, 2017. ISBN 9781509055326. doi:
10.1109/SP2017.49.
Ekin D. Cubuk, Barret Zoph. Dandelion Mane, Vijay Vasudevan, and Quoc V. Le. Autoaugment: Learning augmentation policies from data, 2018.
Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial classi- fication. In KDD-2004 Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004. ISBN 1581 138881. doi: 01555/1114522.01440000
Seyed Mohsen Moosavi Dezfooli, Alhussein Fawzi, Omar Fawzi, Pascal Frossard, and Stefano Soatto. Robustness of classifiers to universal perturbations: geometric perspective. 6th International Conference on Learning Representations, ICLR 2018 Conference Track Proceedings. 2018.
Alhussein Fawzi, Seyed Mohsen Moosavi-Dezfooli, and Pascal Frossard. Robustness of classifiers: From adversarial random noise. Advances in Neural Information Processing Systems, 2016.
Alhussein Fawzi, Seyed Mohsen Doosavi-Dezfoole and Pascal Frossard. The Robustness of Deep Networks: A Geometrical Perspective. IEEE Signal Processing Magazine, 2017. ISSN 10535888.
doi: 10.110//M5..007.2744965.
Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Analysis of classifiers' robustness adversarial
perturbations. Machine Learning, 2018. ISSN 15730565. doi: 10. 10.100775109944011-55633
Nicolas Ford, Justin Gilmer, Nicholas Carlini, and Ekin D. Cubuk. Adversarial examples are natural consequence of test error in noise. In 36th International Conference on Machine Learning, ICML 2019, 2019. ISBN 9781510836988.
Bogdan Georgiev and Mayukh Mukherjee. Nodal geometry, heat diffusion and Brownian motion. Analysis and PDE, 2018a. ISSN 1948206X. doi: 10.2140/apde.2018. 11.133.
Bogdan Georgiev and Mayukh Mukherjee. On maximizing the fundamental frequency of the complement of obstacle. Comptes Rendus Mathematique, 2018b. ISSN 1631073X. doi:
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Information and Inference: A Journal of the IMA, 2019. ISSN 2049-8764. doi: 10.1193//maiaa/aa2007
Alexander Grigor' Yan. Heat Kernels on Manifolds, Graphs and Fractals. In European Congress of Mathematics. 2001. doi: (007/978-3-03455 3-0-3---868--222221 2226822_22
Alexander Grigor' Yan and Laurent Saloff- Hitting probabilities for Brownian motion Riemannian manifolds. Journal des Mathematiques Pures et Appliquees, 2002. ISSN 00217824.
doi: 10. 10.1016/50021-7820 7824(001 001244-2.
10

---

Published as a conference paper at ICLR 2021
K. He, X. Zhang. S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Warren He, Bo Li, and Dawn Song. Decision boundary analysis of adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018 Conference Track Proceedings, 2018.
Jay Jorgenson and Serge Lang. The Ubiquitous Heat Kemel. In Mathematics Unlimited 2001 and Beyond. Springer, 2001. doi: 10. 10.1007/978-00 90009788-666--577--9-2989999
Hamid Karimi and Jiliang Tang. Decision boundary of deep neural networks:
Challenges and opportunities. In WSDM 2020 Proceedings of the 13th International Conference on Web Search and Data Mining, 2020. ISBN 7781445336223. doi: 10. 10.1145/33361911337211
Hamid Karimi, Tyler Derr, and Jiliang Tang. Characterizing the decision boundary of deep neural networks. ArXiv, abs/1912.1 1460, 2019.
John Kent. Eigenvalue expansions for diffusion hitting times. Zeitschrift für Wahrscheinlichkeits theorie und Verwandte Gebiete, 1980. ISSN 00443719. doi: 10. 10.10077BBF00538895.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998. ISSN 00189219. doi: 10.1109/5.726991
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018- Conference Track Proceedings, 2018.
Vladimir Maz' ya. Sobolev spaces with applications to elliptic partial differential equations. Springer, 2011. ISBN 978-3-642-15564-2
Seyed Mohsen Moosavi-Dezzooll, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- ness via curvature regularization, and vice versa. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Puttern Recognition, 2019. ISBN 9781728132938. doi:
Peter Mörters and Yuval Peres. Brownian motion. 2010. ISBN 9780511750487 doi: 10.1017/ CBO97805 1775049.
Norman Mu and Justin Gilmer. Mnist-c: A robustness benchmark for computer vision, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Journal of Machine Learning Research, 2015.
Behnam Neyshabur, Srinadh Bhojamapalli, and Nathan Srebro. A Pac- Pac-Bayesian approach to spectrally- normalized margin bounds for neural networks. In 6th International Conference on Learning Representations, ICLR 2018 Conference Track Proceedings, 2018.
Ludwig Schmidt, Aleksander Madry, Aleksandar Makelov, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 18ix:1700000088 2017.
Stefan Steinerberger. Lower Bounds on Nodal Sets of Eigenfunctions via the Heat Flow. Communi- cations in Partial Differrnniall Equations, 2014. ISSN 15324133. doi: 10.10800036053022.0144 942739.
Taiji Suzuki, Hiroshi Abe, Tomoya Murata, Shingo Horiuchi, Kotaro Ito, Tokuma Wachi, So Hirai, Masatoshi Yukishima, and Tomoaki Nishimura. Spectral-pruning: Compressing deep neural network via spectral analysis. ArXiv, abs/1808.0855 2018.
Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network. In International Conference on Learning Representations, 2020. URL https: :ttt:p:://pppeeeee //pperevvei
rKwH

---

Published as a conference paper at ICLR 2021
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representationss ICLR 2014 Conference Track Proceedings, 2014.
Arthur D. Szlam, Mauro Maggioni, Ronald R. Coifman. Regularization on graphs with function- adapted diffusion processes. Journal of Machine Learning Research, 9655: 2008.
URL http: wwtpp/pppppp.p..ptapt. sz am0 htm
Michael Taylor. Partial Differential Equations I: Qualitative Studies of Linear Equations. Springer, 2011. ISBN 9781441970480.
Vladimir N. Vapnik. An overview of statistical learning theory, 1999. ISSN 10459227.
G.N. Watson. A Treatise on the Theory of Bessel Functions. Cambridge University Press, 1944. ISBN 9780521093828.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Advances in Neural Information Processing Systems 32, pp. 9725-9736. Curran Associates, Inc., 2019.
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020. URL [RR[/tttppss//perrvviie
Sergey Zagoruyko and Nikos Komodakis. Wide Residual Networks. British Machine Vision Conference 2016, BMVC 2016, 2016. doi: 10.5244/C.30.87.
A APPENDIX A: HITTING ESTIMATES, SATURATION AND CURVATURE
A.1 BROWNIAN MOTION AND BESSEL PROCESSES
this Subsection we introduce some basic background on Brownian motion.
Definition 2 (Brownian motion). A real-valued stochastic process (w(t) : t 2 0} is called one one-dimensional Brownian motion started at x E R if the following hold:
(0) x,
the process has independent increments, that is, for 0 S t1 S ...t the increments w(t,) f(rr 2,...., m are independent random variables, .m
for t 2 0, h > O, the increments w(t + h) w() are normally distributed with expectation zero and variance h,
almost surely, the function w(l) continuous.
The process {w(t) 22 2) is called standard Brownian motion if
0.
Finally, if "......, Wi are independent one-dimensional Brownian motions started at -1,-.. Ty then the stochastic process w(t) (wi(t), ... (t)) is called n-dimensional Brownian motion started at x = (I1. (T.)
Remark A.1. The distribution of the standard 1-dimensional Brownian motion w(t) is normal with mean O and variance It follows that the RMSD (root mean squared displacement) of the standard n-dimensional Brownian motion is Vnt.
Sampling Brownian motion simulation prescribed directly by Definition Given a step size s, number of steps & we sample Brownian path as
w(k) = Σ sX,,
X,~ N(0,)).
(9)
1=0
12

---

Published as a conference paper at ICLR 2021
By Definition Var[w(t)] hence the sampling @ corresponds to running Brownian motion for time
ks²
(10)
In particular, the mean displacement of w is s nk. In accordance with the main text, Subsection 3.1
and Fig. 2 whenever we need sample Brownian motion contained within the ball (xx, r) for its lifespan [0, t). we will fix the number of steps & (usually, we set k = 400) and adjust the step size accordingly, so that r synk.
Estimating hitting probabilities A straightforward empirical way to estimate Brownian hitting probability P.. [34 [0. (()(())) E S] of a target set S is to evaluate the steps a(i), i o..... and check whether ((1) E S for some S. Of course, the precision of this computation depends on the number of sampled Brownian paths W, well as the step size and number of steps k. Formal statements on convergence and numerical stability could be obtained, e.g. by means of DiteettrationMMonte-eeo Carlo results (e.g. Proposition B.12 below); however, in practice, in experiments we mostly worked with the regime l = 10 which seemed an acceptable choice in terms of numeric stability and performance.
Explicit closed-fomm form computation of hitting probabilities a non-trivial task, though it is possible for some model cases (main text, Lemma B.2h. Dimension I is special, where have the so-called "reflection principle", which says that
sup w(s) 2 d = 2P (t) 2 d). OSesE
(11)
For proof of this basic statement we refer to Mörters & Peres 2010
However, in higher dimensions, there is no straightforward analog of the reflection principle, and calculating hitting probabilities of spheres leads one to the deep theory of Bessel processes. Let us consider Brownian particle (t) starting at the origin in R. and look at the real-valued random variable [f)[[ (in the literature, these are known as Bessel processes). We are interested in the probability of the particle hitting a sphere {a E IR" ||ж||| = r of radius r within time Curiously, it seems that there is no known closed formula for such a hitting probability. The only formula know of is in the form of a convergent series involving zeros of the Bessel function of the first kind, and appears in Kent (980)). For the reader interested in Kent's formula, we also refer to associated asymptotics of zeros of the Bessel function in Watson (1444).
The following heuristic is implicit in many of our calculations and motivates several of our definitions: the probability
sup [s)) 2r) Oceett
(12)
of Brownian particle hitting a sphere of radius r within time is dependent only the ratio r a consequence, given small >> 0 and a constant e, one can choose the constant in / car2 small enough (depending on 17) such that
I
sup
|((()|| 2 <
(13)
0
Roughly what this means is the following: for Brownian particle, the probability of hitting large and nearby object may be made arbitrarily small if the motion is not allowed to run sufficiently long.
A.2 HEAT DIFFUSION AND BROWNIAN MOTION DUALITY
Macroscopic vs microscopic There are roughly two broad viewpoints towards the understanding of diffusion: the "macroscopic" and the "microscopic". Macroscopically, the mechanism of diffusion can be thought of as creating a flux in the direction from greater to lesser concentration. If u (z, t) measures the intensity of the quantity undergoing diffusion, and the flux across the boundary of region Ω then in the simplest model one assumes that (up constant) J - Vu. Further, we have the identity
Ô u(I,t) dr = /f -. Vu ds,
(14)
Jan
13

---

Published as a conference paper at ICLR 2021
where v is the outward pointing unit normal vector to 0Ω. By applying the divergence theorem to (14). one immediately gets the heat equation 0, = Au. Here denotes the Laplace operator given by the sum of second derivatives: A Σ 0
Now, many real-life diffusion processes are the result of microscopic particles jittering around seemingly in random manner. This motivates the mieroscopic viewpoint, i.e., the modelling of heat diffusion via Brownian motion of particles. We posit that a particle located at x E IR" at time to will have the probability the (z, t) of being an open U RR" at time + L, where
[( p(l, v) dy.
te (z, ()
(15)
and p(l, 2t, y) is the fundamental solution of the heat equation, or more famously, the "heat kernel". In other words, p(t, x. y) solves the heat equation
{ ( A) uxr, ((xrt) 1) = 0, u1(2, 0) 8( y),
(16)
with the Dirac delta distribution the initial condition. Via Fourier transform, it easy establish that p(t, x. v) is given by
p(t, x. v)
(17)
(4nt)m/2*
This builds the bridge to pass between analytic statements on the side of the heat equation and probabilistic statements on the side of Brownian motion (see Grigor Yan (200T), ( The precise formulation this duality given by the celebrated Feynman-K Kac theorem discussed in Subsection A.3 below.
Heating up the decision boundary In our context we introduce the following heat diffusion process along the classifier's decision boundary N:
(a, - ( t) =0 ()x,0) =0, 0, Vo E R (Ee,)) 11 Vt > 0.
(18)
In other words (xx t) gives the heat quantity at the point at time t given that at the initial moment t = all points have heat quantity 0 and afterwards a constant heat source of intensity is applicd only at the decision boundary N. As remarked above this is the macroscopic picture: the mentioned Feynman-Kee -ac duality implies that (xx t) is also the hitting probability P. [ao E [O,t] E M].
A.3 THE FEYNMAN- KAC THEOREM
It is well-known that given reasonable initial condition u(xx, 0) f(x), one can find analytic solution to the heat equation via convolution with heat kernel,
e f(x) == ptt, x, f()).
This just follows from (16) by convolving directly. Now, via the duality of diffusion explained above, one expects a parallel statement on the Brownian motion side, one which computes the contribution of all the heat transferred over all Brownian paths reaching point at time t. It stands to reason that to accomplish this, one needs an integration theory defined over path spaces, which leads us the theory of Wiener measures. We describe the main idea behind Wiener measure briefly: consider particle undergoing a random motion IR (given by a continuous path w [0, oo) - RT) in the following manner: given la >> 4 and w(11) = x1, the probability density for the location of w((2) is
1
12
p(t. v. 01)
(1m(112 41) 4))
We posit that the motion of a random path for 1 S t S l2 is supposed to be independent of its past history. Thus, given 0 < t <... th. and Borel sets E, C R the probability that path starting at x = 0 at t = O, lies in E, at time t, is
p(ts tb Thi Tb-1) ... p(t1, 0) dæy ... dx1. Fx
14

---

Published as a conference paper at ICLR 2021
The aim is to construct countably-additive measure on the space of continuous paths that will capture the above property. The above heuristic was first put on a rigorous footing by Norbert Wiener.
Using the concept of Wiener measure, gets the probabilistic (microscopic) description of heat diffusion, which is the content the celebrated Feynman Kac theorem:
Proposition A.2. Let S Th be a domain, with or without boundary (it can be the full space TRe)). In case of boundary, we will work with the Laplacian with Dirichlet boundary conditions. Now, let I? (S2). Then for all Q O, we have that
e f(x) Ex (f (w(t)) on(w,t))
(19)
where w(t denotes an element of the probability space of Brownian paths starting at x, Bg the expectation with regards to the Wiener measure on that probability space, and
So(w, 1) = 11, if ifw(O, 1) CΩ
0, otherwise.
For more detailed discussion, see Georgiev & Mukherjee (0188).
A.4 ISOPERIMETRIC AND ISOCAPACITORY RESULTS
Isoperimetric bounds Isoperimetric inequalities relating the volume of a set to the surface area of its boundary have given rise to wealth of results Burago & Zalgaller (1988). Given set M with boundary θM, the basic pattern of isoperimetric inequalities is:
Vol(M) I C1 Area(OM)
(20)
where e₁ is an appropriate positive constant depending on the dimension n. many cases, equality (or saturation in the sense of almost equality) in (20) is characterized by rather special geometry. For example, classical isoperimetric results answer the question, which planar set with a given circumference possesses the largest area, with the answer being the disk. As discussed in the main text, isoperimetric considerations have recently lead to significant insights about decision boundaries of classifiers subject to adversarial defense training mechanisms Ford al. (2019) by revealing flattening phenomena and relations to robustness.
Isocapacitory bounds As mentioned in the main text, one can prove types of isocapacitory bounds that resemble the isoperimetric ones: roughly speaking, these replace the area term with suitable Brownian hitting probabilities. We have the following result (ef. also Georgiev & Mukherjee (2018))):
Proposition A.3. Let B(x,r) c R",, 2 3, and let E C B(a,r) denote an "obstacle", and consider a Brownian particle started from Then the relative volume of the obstacle is controlled by the hitting probability of the obstacle:
Vol(E) S cn (WE( 1)) =
(21)
Vol(B(r,
Here, Cy is positive constant whose value is dependent only provided the ratio be- tween 72 and is suitably bounded. In particular, in the regime p2 nit, we have that
On (T - 1) /T 1, 11) "² Here, T(8, represents the upper incomplete Gamma func- tion
((,,))== 1o c40-0 dt.
Proof.
Recall that the capacity (or more formally, the 2-capacity) of set K I² defined as
inf From Section 2.2.3, Maz ya 2011 we have the following "isocapacitory inequality"::
Cap(K)
(22)
J
Cap( F.) 2 w
2/'n n-2
n-2
(23)
15

---

Published as a conference paper at ICLR 2021
N+
No
N
x N_
T
Figure 5: Examples illustrating the interplay between isoperimetric and isocapacitory saturation in high dimensions. (Left) Slightly bending a flat decision boundary Ny causes significant changes with the isoperimetric inequality still being very close to optimal: .V. (resp. N leads increase (resp. decrease) (ef. also Fig. (6. (Right) Small "pockets" near the data sample æ can also cause large Brownian hitting probabilities (hence, large I values) with still well-saturated isoperimetric bounds.
where w,,
is the (n - dimeenssia surface area of S Now, we bring in the following estimate given by Theorem 3.7 of Grigor Yan & Saloff-Coste (202)):
2zz²/2 R/2 T( +
/''
(E(I,t) 2 Cap(E)
inf p(s, 2, ds. yEaR
(24)
Now, we have
(E(x,t) 2 2/"n 2=2
(n 2) m=2
inf
-=-y?
ds
(4Ts)
yEBE
2=2
(n 2) n=?
2 ds
w n
(4Ts)a/2
2/ W
n
(n 2)
C 22/2222- dz.
4 2 1/2
+2
After rearrangement the proposed claim follows.
Intuitively, it makes sense that if the volume of set is fixed, one can increase its hitting probability by "hammering" the set into a large thin sheet. However, it seems unlikely that after lumping the set reduce capacity/hitting probability any further. Moreover, isocapacitory
together (as in ball), bounds are saturated by the nabal..
It is also illustrative to compare the seemingly allied concepts of capacity and surface area. A main difference of capacity with surface area is the interaction of capacity with hitting probabilities. As an illustrative example, think of book which is open Clearly, all three have the same surface area, but the probability a Brownian particle striking them goes from the highest the lowest in the three cases respectively. It rather difficult make the heuristic precise in terms of capacity (at least from the definition). Capacity can be thought of as soft measure of how "spread out" or "opened-up" surface is, and highly dependent how the surface is embedded in the ambient space.
angle of 180", 909 455 respectively.
Isocapacitory vs isoperimetric saturation A main line of analysis in the present work addresses the interplay between isocapacitory and isoperimetric saturation. In our particular context of defense training mechanisms we observe saturation of isoperimetric bounds for the classifier's decision boundaries this implies that decision boundaries are not far from being flat. However, mentioned before, it turns out that isocapacitory saturation does not concentrate around the values corresponding hyperplanes (overall, it seems stay well below that value). In this sense, isocapacitory saturation
16

---

Published as a conference paper at ICLR 2021
Isocapacitory Saturation vs Isoperimetric Saturation
3.0
2.5
Isocapasitory Saturation
Saturation
2.0
1.5
1.0
Isoperimetric Saturation
0.5
10
15
20
25
Interpolation parameter
Figure 6: A continuation on Fig. Isocapacitory and isoperimetric saturation while slightly bending decision boundary (N_ and N in Fig. 5). this plot the decision boundary ,,,N,, a cap of larger sphere with radius R (set initially to 15r) in dimension 3072 (corresponding to CIFAR10). We interpolate between V_ and N44 first, by increasing the radius R_ converges to the flat No and, similarly, starting from No decrease R to get to N4. Along this interpolation process, plot the graphs of the isocapacitory and isoperimetric saturation. In particular, we observe at least 96% saturation of the isoperimetric bound whereas the isocapacitory bounds shows much more sensitive behaviour on this scale.
acts as finer sensitive measure of deviation from flatness. A simple model geometric scenario that provides similar behaviour is illustrated in Fig. and Fig.
A.5
MODEL CASES
We first begin with the proof Lemma 3.2
Proof. Let us select an orthonormal basis {ei,..., 6n) so that é coincides with the given hyper- plane's 's normal vector. A standard fact about n--dimensional Brownian motion is that the projections on the coordinate axes are again one-dimensional Brownian motions Mörters Peres (2010). Thus, projecting the re-dimensional Brownian motion onto e the hitting probability of the hyperplane is the same as the probability that one- mne-dimensional Brownian motion w(t) will pass a certain threshold d by time t. To compute this probability Remark A. Consequently, the RHS is equal to 20(-d/ The computation of p(x, r) follows by definition.
the reflection principle (11) in conjunction with
Here we note that the dimension n enters only in terms of the spherical cap volume. impression how behaves for different choices of in terms of the distance d is given in Fig. 7 In particular, one observes the well-known concentration of measure phenomenon and Levy's 's lemma: the volume of the spherical cap exhibits a very rapid decay as n becomes large. Moreover, experiments reveal curious phenomenon: there a threshold distance dg until which J z 2 and afterwards 7 explodes.
In Fig. g plot further interesting model cases where the enror set forms wedge (the region between two intersecting hyperplanes) or a cone.
Spiky sets As discussed in the main text, one observes high isocapacitory saturation T for the so-called "spiky" these are sets of relatively small volume and relatively large/dense boundary.
17

---

Published as a conference paper at ICLR 2021
Isocapacitory Saturation for a Hyperplane
250
50
Saturation
150
100
40
50
30
20
10
0
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
Distance from starting point to hyperplane
Figure 7: The isocapacitory saturation r of a flat error set. Given a point the computation takes flat decision hyperplane is given on the x-axis, while
place in Bix, r) with r The distance the y-axis gives т. Curve labeling indicates the respective dimension. There appears to be a threshold dividing between the regimes T 2 and T - oc.
Isocapacitory
Isocapacitory
Wedge
5.5
5.0
2.6
4.5
4.0
2.4
3.5
20
2.2
30
3.0
2.5
2.0
2.0
2.08
3.00
3,02
3.04
3.06
3.08
3.10
3.12
3.14
1.0
1.5
2.0
2.5
Openinng angle of Corn
Opening iig an angle of Wedge
Figure 8: Further model cases and plots the isocapacitory saturation т. (Left) Isocapacitory saturation of cone in terms of the opening angle (radians). (Righr) Isocapacitory saturation of wedge in terms of the opening angle (radians). Curve labels indicate the respective dimension. Again one observes concentration of measure the volume of the cone decreases 0 exponentially fast in terms of the dimension n: this is why we plot the opening angle around x in this case. Furthermore, cones and wedges with an opening angle of almost behave like hyperplanes in terms saturation.
18

---

Published as a conference paper at ICLR 2021
h
T
p
0
Figure 9: Cylindrical "spike" of height h and radius p inside the ball Bar,)).
Theoretically, guiding model case in this direction is given by Lemma 3.3 the main text, whose proof we now record.
Proof. Let Tp denote the p- tubular neighborhood a line segment of length inside R". Clearly, Tp = ((0, p) x [0, hl, where (0,, r) is a p-ball inside R=-1
By the well-known process of Steiner symmetrization in R", is clear that the expression for capacity in (22) will be minmmized by function that is "radially symmetric" around the central axis of the
tube p. that is fax v) f((==)) where x E B(0, p).yy y E [0, hj. Then, as we scale p Ap, where 0, Cap (Txp) 3= Cap (Tp) (which is seen directly from the definition 22 whereas the
volume scales as [Taal = 1- |Zpl-
C R the central axis of T, is pointing towards x, and Tp is touching the boundary of Bxx, r) To pass from capacity to hitting probability of the set Tpp we use that Grigor Yan & Saloff-Costt (202))
Now assume that the cylinder T, is inside the closed ball B r)
Cap(Tp)r2 C Vol(B(z,r)) S ST, (x,
(25)
Finally, using the definition of r and putting the above estimates together, one sees that in the time regime of O(r2), 7 scales like > 22)(mn-)), and hence, / 0o as X O.
See also Figure 8 for a visual discussion of the isocapacitory saturation for the model cases of wedges and cones.
A.6 CURVATURE ESTIMATES IN TERMS OF ISOCAPACITORY SATURATION
The geometric concept of curvature has rich history and plays a central role in differential geometry and geometric analysis. There are several notions of curvature in the literature, ranging from intrinsic notions like sectional, Ricci or scalar curvatures to extrinsic (that is, dependent on the embedding) notions like principal curvatures and mean curvature, which are encoded in the second fundamental form. In this note
somewhat "soft" definition of curvature, following previous work Fawzi et al. (2016); [Deffoll et al.] (2018). Suppose the decision boundary N₂ is sufficiently regular (C² enough for our purpose) and separates IR" into two components R2 == {f > 0} and R2 = 0), corresponding to binary classification (the construction in the multi-label case is analogous). For a given E N,, let (p) denote the radius of the largest sphere that is tangent to Ny at p. and fully contained in R, Then, one defines the curvature k. at p
<(p) = 1/ min (r (ri(p), r2(p))
(26)
See Fig. 10 for a geometric illustration. However, it turns out that most notions of curvature are quite subtle (see Fawzi al. (2016)) and this point, seemingly more cunbersome and intractable to
19

---

Published as a conference paper at ICLR 2021
(P(p)
(2l9)
Figure 10: "Soft" definition of curvature given by the inverse radius of the osculating sphere.
handle experimentally. We will take indirect approach, and attempt read off the effect of and on curvature via the isocapacitory saturation
Again, begin with the model cases: we first study the behaviour of curvature k if achieves its least possible value. We start by fixing some notation. As before let us consider a ball (xx, r) with an emror set E (xx,1 r) and boundary N ÖE (clearly our main case of interest is Evy) B(x, r)). Let us denote the the distance d = NV) and suppose the point E N realizes this distance, i.e. d(x, y) = To rule out some degenerate cases and ease the analysis we introduce the following assumption:
Assumption: The hypersurface N and the point æ are on different sides of the tangent hyperplane H' Ty, (cf. Fig. [T].
This assumption is also technically important, as otherwise low values of t will produced by annuli surrounding æ. With that in place, we have the following rigidity result:
Proposition A.4. Let us fix the distance d = N)) and suppose the assumption above holds. Then the least possible value of is attained only if the curvature of the hypersurface N O.
Proof. As above let H' be the tangent hyperplane at distance d from x, and let C' denote the (smaller) spherical cap formed by H n (ar, r). The proof relies on the following variational argument. A is not the same as H then N C C, with y E N n H We wish to argue then one can perturb N infinitesimally to decrease the value of T, so the only minimizer of the above expression has to H!" The basic idea is to cut out a small piece Pa around and paste it in the region of around ū (Fig.
We say that A has positive curvature at some point z the ball defining the curvature at = and point lic on different sides of N. The construction is as follows. Let S(x, s) be the (n 1))sphere centered at z with radius s. We consider two cases:
Case I: Let suppose that there exist $1 $2 and points E / such that the curvature of N at e E N n ((x, $1) greater than the curvature at e E N n S(x, 82). Let us, moreover, choose the infimum among such $1 and the supremum among such 82.
To define the mentioned piece Pv. we consider two small balls B(o, E), B(ū,e) (where < 82 - $1). and cut out ps E n BBv,e) such that 0 (E) \. B(v,e) congruent to N n B(ū,s) (this is possible due to the curvature assumptions at ū). Then, we define the new error set F' = PUps pa \p and the boundary A Ø" where pa represents the image of p. under the rigid motion and attached inside Biū E) (see Fig. [1]. It is now clear that [E] [E', but th (x,7) 7") < (2 7) for all T' O. The last inequality follows from the evaluation the explicit heat kernel that defines hitting probability v as stated by Feynman- Kac duality:
VE(x,T)- = [- (4nt)aa2 e
(H-w) dy dt
1 T { (4nt)u/2
(--p)
dy dt (x, (x,T).
follows from the definition of r that TE 2 TE.
Case H: If Case is not satisfied, then, similarly, choose two points v, 6, but instead of defining the piece P. by intersection with a small ball around e we select p., as "concavo-convex lens shape" domain, where the curvature the concave "inner side" of pv of the lens is greater than that on the
20

---

Published as a conference paper at ICLR 2021
E
P6
Pc H*
x
Figure 11: Moving the piece pr. the tip of the obstacle and reattaching it far away as pa reduces the hitting probability, but preserves volume.
convex outer side. As before, we attach a rigid motion image of inside B(ü,e). The rest of the argument similar Case
With reference to previous discussion of spikes, it heuristically makes sense that spike must have reasonably high curvature (it can have high curvature on the average, or is flat at most places, then have sharp needle like end where the curvature is very high). In the same setting as Proposition A.4 let us, morcover, for simplicity assume that N is the graph of function over the tangent hyperplane H* (Fig. III.
Proposition A.5. In the above setting let fix the value of d. Then, the maxinum curvature Kmax of N is sufficiently high (greater than some universal constant), then it satisfies
(
d
Kmax
(27)
where &e denotes the c.d.f. of the standard normal distribution. If a point attaining this maximum curvature within the half concentrie ball Bxx, r/22, then Emax satisfies the stronger estimate
T F
d)
d
1)
Fiax
Φ
(28)
Proof. Recalling the definition of the isocapacitory saturation т. we will bound the numerator (resp. denominator) of from above (resp. below). First, for the numerator e f) we will use basic monotonicity property of hitting probabilities stating that for two sets A C B one has (x, t) < ( t) this follows directly from the definition of vb Now, since E C C' where C is the smaller spherical cap of B r) n H1*, we have (E(( t) S Φ0(2, t). However, recalling the explicit form of dhe from Lemma 3.2 of the main text, we have
( 1) S $ (-v)
d
Vi
Second, to bound the denominator of - (i.e. Vol(F)), we observe that if Kmax large enough, by where w., denotes the volume of unit
definition F. contains ball of radius Kmax n-dimennional ball. That finally implies.
and Vol(F) Rhan
(ol(
Vi
Vol(E)
Vi
which proves 27
21

---

Published as a conference paper at ICLR 2021
If point of maximum curvature is inside concentric ball of radius r/2, then E contains ~ balls of radius which implies that Vol(E) 2 Kimax (r d)
Nanax (r-d)
We
Fimax
The rest of the proof is similar.
Now, we give curvature estimate which works in any regime, without any restrictions. The tradeoff is global average bound of the LP-type rather than pointwise estimates.
Proposition A.6. In the setting as above, let us fix the distance d = d)x.N), At each point of N let us denote by the maximal sectional curvature of N that point. The following estimate holds:
[ 2 (x,,r) r
(- V
(29)
TH
where V rd) denotes the volume of the smaller spherical cap at distance d, the constant wn denotes the volume of unit ball in R", and the function is an integral function of the curvature k over lines (defined in 37) below).
Proof. Again, we suitably bound the numerator and denominator of т. Starting with the numerator, as explained in Proposition A.3 have by monotonicity
d
(E( S 2Φ
(30)
To bound the denominator of 7 we proceed follows. Let A be the graph of the function g( In) where the variables Ij are taken from the hyperplane H* (Fig. 11 at distance d from x; the point which V touches this hyperplane is taken as the origin. Let Pe be a smooth cut-off function defined on the hyperplane such that y = 1 on the set S of all (xI," Ix-11 such that (( 1n B(x,r) r), and yp outside the e-tubular neighborhood of Finally, let Ge P.9.
Now we see that, letting a = ()1/2,
[ / ge(p. 0) p=-² dp d8.
-ol, S
Now, if n7 denotes the unit vector in the direction a fixed (p, 0), observing that (0) = 0, we have by the fundamental theorem of calculus
(e S aig. (Lpn, 0) di.
In turn, applying the fundamental theorem second time and observing that (g) 0, we have that
ge (p, S.' S. (stran 0) ds dl.
Putting everything together we get,
S gn-2 J. 0,0rge 0) ds dt pr- dp de.
(a r) Vol(E) < 1=
Now, we define the following integral quantity:
(p, ['' L. Iss (st 0) ds dt.
(31)
Noting that the maximum sectional curvature bounds the second derivatives, finally we have that (d, Vol(E) < || now all the above estimates together and let 0.
(32)
To obtain 29
22

---

Published as a conference paper at ICLR 2021
B APPENDIX B: GENERALIZZAIIN BOUNDS AND COMPRESSION SCHEMES
Background A main line of ML and statistical inference research addresses questions of general- ization. To set the stage start with notation. Let suppose that the dataset X' is sampled from a probability distribution D, i.e. (x, y) D. Following conventions from the literature Arora et al. (2018) define the expected margin loss of a classifier by
(f( (a.g)~ f() +
max k:j
f())
(33)
We use the notation L, to denote the expected empirical margin loss over the given data A. Finally, the generalization error is defined as L, L.g.
Quite roughly speaking, standard generalization results attempt to estimate the performance of the classifier on unseen samples (i.e. the full data distribution), thus yielding bounds of the form:
(n) < (1) + F(n, 72. J,X),
(34)
where F' is additional term that usually depends, e.g. on the size of X, the expressiveness of f and further margin information 72).
B.I COMPRESSION IN A HEAT DIFFUSION SENSE IMPLIES GENERALIZATION BOUNDS
We first state well-known concentration inequality due to Hoeffding which will find repeated use in the ensuing sections:
Proposition B.1 (Hoeffding's inequality), Let XI..... Xn be independent random variables taking values in the interval [0, 1], and let X [X + + Xn) be the empirical mean of these random
variables. Then we have:
P X
t) S 2nt
(35)
We now provide the proof of Proposition 5.1 of the main text.
Proof.
The strategy of proof follows well-known ofeak- concentration tech- niques in a spirit similar Arora et (2018).
Step 1. First, we show that for given as |X| + cc,
P P(a.))> (Cg(æ, y. v1)) - ((aa)~D (Cg(I,
(36)
where (z, (z, 7²) the event that a Brownian path starting at æ hits Ey(y) within time 72, The rate of convergence is determined through Chernoff concentration bounds.
Choose a E A, and let Ja be the corresponding classifier. Attached to each sample point zj. there is a Bernoulli random variable X, which takes the value if Cg., (Ir,, y, ?2) happens, and 0 otherwise. Then, the average X J Σド= Xj given by the average of m i.i.d. Bernoulli random variables each of whose expectations is given by ((aa))> Cg,, (x. y. 2)) Furthermore, we note that if data sample misclassified, then the Brownian particle almost surely will hit the error set. Combining this observation with the concentration estimate (35) above, we obtain
Lo(ga) < (( (C (Ir, 1,, Y)))
((e,)>~~ (Co, (I,, y, 72) +
(37)
with probability least 1 e- 2 m each classifier Ja has g parameters, each of which can take discrete values, we take / g
The estimate from the previous step should hold for every classifier in the family A with large probability. This is guaranteed by union bound and tuning the Chernoff bounds from the convergence rate. More precisely, there are r different choices a E A, and hence by taking the union of the estimate (37). one can say that
Step 2.
q logg
((aa))D (Cg, (0.9,72) S P P(nw))xxx (C,, (x,
(38)
m
23

---

Published as a conference paper at ICLR 2021
with probability at least - e logg over all E A.
Step 3. Finally one uses the fact that f is upproximable by at least one = 9a. for some ag in A.
Via Definition [ of the main text, one sees that
P(x.))>x (Cogg (2, y, 7)) S ((.)))x (C,(I, ()) +
which finally gives that with probability at least E logr, we have
Lo(g) S P(ayiia (Cy(e, + (v
q glogr
(39)
m
Remark B.2. As noted, a classifier f classifies a point x wrongly if and only if ( (a. t) = 1 for all time scales t. With this observation, and since (39) works for all real numbers 7, letting 7 - we have that with probability at least 1 - e g r.
(Volosr glogr m
Lo(g) & Lo(f) + +
This recovers a loss estimate which is similar the estimate in Theorem 2.1 of [1].
Indeed, one can consider (x.y))> (Cy(æ, (,, 7²) "soft" or probabilistic measure of classification with margin 7,
When defining the notion of a compression, instead of taking pointwise difference as in Definition 1 of AAroa et al. (2018), we would like to capture the idea that the decision boundary of a good compression should be "close enough" to the decision boundary of the original classifier. In our context, this implies that their "heat signatures" at the sample points should be close enough at all time scales. As noted in the main text, Definition i definitely of compression in a heat-diffusion sense. Another natural way is to consider the Brownian motion's running time and define good approximation as follows:
natural option to define goodness
Definition 3. Given positive real number n). classifier g is said to be 17 compreessioo w.r.t. hitting time of f if
(E) (2, S ( (2, (F,0) n))
(40)
for all points x in the training sample, labels and real numbers x2 2
Analogously, we have the following
Proposition B.3. Let us suppose that approximable by g in the sense of Definition 3 Here E A, where A is family of classifiers RR. + R parametrized by parameters assuming r discrete values. As before, for a classifier h, let Cn y,t be the event that a Brownian path starting hits (y) within time t. Then we have
(v
q glogr
Lo(g) < (Z.g)>D (Cgo (2, 72 7)) I PP (((r)))x(( (C,(2,8, +0
(41)
with probability at least 1 goggr
The proof proceeds similarly as above. Letting 72 + gives us
(0
(V gglorr
Lo(g) S ((eN)~ (Cf(z, -
(42)
m
Again, the first term on the RHS can be interpreted as the geometric margin of classification. In particular, if the classifier of separates points by a distance of ~ /nn,, then since the Brownian motion travels R5 Vraj hitting the error set will happen only if misclassification occurred, i.e. we have
( (Cy(I, (I) Io).)
(43)
24

---

Published as a conference paper at ICLR 2021
B.2 A SHARP VARIANT OF THE JOHNSON-LINDENSEEN LIIDENNSNNUNSSSS ALGORITHM
Several state-of-art compression schemes utilize a dimensionality reduction in the spirit of Johnson- Lindenstrauss (JL). Arora al. (2018). In this Subsection we discuss JL compression scheme that will later be coupled with and tuned by some heat-diffusion estimates. We begin by discussing a variant of JL (Alg.
Data: Original matrix A of dimension h1 x h2. 3 E (0, 1). Result: Stochastic compressed matrix A with O (log(h1 h2)/ Ba²) non-zero entries such that
TP [[IÁc Axl 2 al| ||| $ B. Start with matrix A. real number o;; while i < h1, j S h2 do
20 Let 2zj = with probability P. = Ba || 21y Let ā:g Ps
otherwise;
end
Return Å = (ax))-
Algorithm Compressing a matrix A E Blixha
Proposition B.4. Let A be a matrix of dimension h1 h2. Then, one can find compressed matrix Á such that
| Axll S a A|AA|||
with probability at least B, where the number of parameters of Å is (log(hrha)/Bon
A proof of Proposition B.4 in the spirit of classical JI. can be provided - however, here we introduce Bernoulli scheme which a minor modification of Algorithm 2 of Arora et al. (2018).
2n
Proof. Define the random variables žij which take the value 1 with probability Pij Ba || and the value 0 otherwise. Define âij
Saydeg One can now calculate that E (ā:;) = aij. Psy
and Var (Qiz) < 3 A|l Using the above, one can further calculate that E(Az) = Ax, and Var(Ar) - | Ba? By Chebyshev's inequality, this gives that
P [I
Ax|| 2 all |||A|||||0|]] < 3.
Now, the expected number of non zero entries in Á is Ev, Pij = påz An application of Chernoff bounds now gives that with high probability the number of non-zero entries is O (log(hrh2)/Ba²
B.3 HITTING PROBABILITY, CAPACITY SENSITIVITY AND COMPRESSION
As discussed in the main text, here we hitting probabilities associated to the decision boundary to define a concept "capacity sensitivity" of a neural net layer. The heuristic is, the less the capacity sensitivity of a layer, the greater the facility in compressing the layer one with fewer parameters. This goes in the spirit of current state-of art results on compression and generalization bounds (Arora al. (2018). Suzuki et al. (2018). Suzuki et al.) (2020)). In particular, in Arora et al.] (2018) the authors provide the notions of noise sensitivity and noise cushions motivated by Gaussian noise injections. Our first proposed definition for "heat-diffusion noise eushions" and capacity sensitivity goes follows:
Definition 4. Let N be distributed along a noise distribution N concentrated in ball ||n|| S no-- We define the capacity sensitivity S(x, Ag of layer A; at the point x as
EEy- WEe (1b( Ax(a + [|xr|())), (E, ((((()())))) AxT),
(44)
WE,, (o(A,z),
We denote the maximum and expected sensitivity respectively as Sth (A;it) = max S(x,Ari Arit), 5 (²a;it) Exax S(x, Ast).
(45)
25

---

Published as a conference paper at ICLR 2021
Now Algorithm 1 to investigate a method for compressing layer A, that the capacity properties are preserved.
Proposition B.5. Let a particular layer A, of the neural net be of dimension h xh2. Then, Algorithm 1 generates an approximation As with O (log(hrh2) Ba²) parameters for which we guarantee that (o) is proportional to v (E,(w) (o(()) up enror with probability 3 + 5TH (A.)//
Proof. Using the fact that (bE (0 .1) WEE(C) (A((( [|]]|])) 1), let As denote the event that
(1 (o(A.z),)) (Fy()) (t(A,)),t) (F (6(A,)),
WEE + (n)), (0
2 6.
) (6 (A,x)t,
For every fixed x E X, using 44) and Markov's inequality immediately implies
P [[As] < S(x, ARt)
(46)
Since Algorithm yields controlled distortion, we have that given error parameters a, 8, one gets Å. a stochastic approximation of A such that
P [|A(s)) A,(x)) 2 a ||A:llr ||=]|] S 3.
(47)
Here the reduced number of the parameters of Å is O
With that, we have
P [A =P ( [[A((t) - Ax)x
||| <
0 11)22
+P
[11A,(0)) - [
21 21)A4g (48)
A
a||A,||F|<d]
[A((z) - (x)
< [As] IP
a 2
S(x, 1; + B
This concludes the claim.
The above proposition may seem suboptimal and even somewhat of tautology, but we include all the details, because one way forward is now evidently clear. In particular, the step in (48) can be improved if we know that if the distance between two vectors and w is bounded above, then th, (z, t) &E, (w, t) is bounded above. In plain language, we would like to say the following: if two points are close, then the respective probabilities of Brownian particles starting from them and hitting Nf are also close. This is too much to expect in general, but can be accomplished when one places, in addition, certain nice assumptions on the decision boundary.
B.4 PROOF OF FIRST PART OF PROPOSITION 5.2 OF THE MAIN TEXT
We will break down the proof over three propositions, to illustrate the flow of ideas. The first the case of the hyperplane which we discussed to some extent above in our curvature analysis (see also Lemma 3.2 of the main text).
Proposition B.6. If the decision boundary Ny a hyperplane, then given 3,6, one can find an a for which the compression scheme of Algorithm 1 gives compression of a layer A₁ of dimension h x h2 to A, with O (hg) 3a²) parameters such that
PP [A,(()) A S [e]|=e||=]< 21 21-8 11-3. 3,
26

---

Published as a conference paper at ICLR 2021
and
WE, (A,,, t) WE, (A,a,) t)
S
with probability at least 3. Here O (d)) The choice of a made explicit by 50
below.
Proof. Let w, 2 E IR be two points such that ||0 2|| v It is clear that the maximum value of Wh, (ur, 1) - the, (2,1) is given by the probability that a Brownian particle starting from a point E I2" strikes a "slab" of thickness ó at distance d 5 from (a slab is tubular neighborhood of a hyperplane) within time t. Without loss of generality, assume that the point & at a distance from the hyperplane Ny. Then,
s (E, (w, (2, $2 (0
)- Vi
(-- vi
)
(-vi)
which implies that
VE, (ur, 1) (1)0)),(66 (2,
②b
d-5
Vf
2
(2,
+
d
vt
From the above calculation, we get that
[I,(x)) (
(A t) LE, (z)
④
d-o
vt
Sa =
52
-
(49)
[| |A
HE, (A,(z),t))
db
where
8= a ||<11
We wish to apply the above estimate in the regime = (dd). For the sake of specificity, let / = d. Now, given from (49) one can choose such that
[A.(x)) (x)))
0 = O.
al a||Ai1l ||]||
suffices to choose a such that when = c,
d-6
2
vF
1
e, where 6 = al|AA] F =||=||]
(50)
v8
Then,
P[AJSS S
Remark B.7. In the above calculation, the nonlinearity & can be introduced easily. Clearly, by the compression properties of Algorithm 1, we have that [](), A,(áz)] a || < aAl [| where is the Lipschitz constant associated to the nonlinearity 6. In particular, if Φ is the ReLU, then X = 1. This gives us that if (x)) A,(x)] S A|lAA|]
I ad = WE, (A)()),t) t) WE, (A) dE (Axx,t)
d-6
A((r)))) - A((xa))
vi
2
A ||
d
Vi
(51)
where
= [|]|A|||||1
27

---

Published as a conference paper at ICLR 2021
w
6
aj
Figure 12: Covering by cuboids of side length 6.
We mention in passing that the above proposition gives connection between our capacity sensitivity (1r, A; 1) and the noise sensitivity viy defined by Arora et al. (2018).
Now consider the of curved hypersurface, denoted by H (which is being thought of as the decision boundary Nf), which is "sandwiched" between two hyperplanes Hi and Нz. Assume that the hypersurface distance d from the point z, and the distance between Hz and H3 is L. Proposition B.8. In the above setting, all the conclusions of Proposition B.6 apply H.
Proof. We have that |WN,, (2, Va, (w. t)] is less than or equal to the maximum of the d+6+1 ②
v7 )..
5.) (-d=+t))
| o (-)t) (- 4+ |
quantities
d+t
d-6
Let M(d, 1) denote this maximum. As argued before, thw, (z, t) 2
d+1
That gives,
WE, ( (w,t) |W (2,1)
M(d,t) + (- d+1 vt
The rest of the argument is similar to the proof of Proposition B.6 and we skip the details.
Before moving on the case of controlled curvature, we need technical lemma. We state explicitly because it seems to that it could have potentially other applications.
Lemma B.9. Let p E RR,, and consider cuboid Q C. 12t with side lengths a1. .op Let g E Q be the unique point which attains d ||p - qll dist(p, Q). Lastly, assume that the line segment pa is perpendicular to the side of Q on which lies. Then
vo(p, 1) = =2 (=(_ 01
01 + d V8
II T
aj 2
x-221))
aj
+
(52)
V
Proof. The proof follows easily from the fact that in an n-dimensional Brownian motion, all the coordinates execute the standard 1-dimensional Brownian motion independently. and then by applying reflection principle. The ideas are very similar to the proof of Lemma 3.2 of the main text.
As an immediate application of Lemma B.9 we now show that the nice properties of the decision B.8above above also shared by hypersurfaces with
boundaries as mentioned in Propositions B.6 and B.8 controlled curvature.
Proposition B.10. Let H be a hypersurface which is diffeomorphic to a hyperplane, of curvature k (in the sense (26)) satisfying < R. Then the conclusion of Proposition B.6 applies H.
28

---

Published as a conference paper at ICLR 2021
Proof. Let 2 be point such that d == dist(z, H), and w be another point such that 8. Let E denote the misclassification region defined by H.
())(2,))
( - wr(w, 0) S (2),
where A denotes the region "sandwiched" between H and HT 6. As before, will ultimately use t in the regime ((d)). Now, given t, start by considering a ball Bzz, Ae), and let Ax, := An B2z (z))).). Here, A has been chosen that A, (z,t) t) comes arbitrarily close (z, We will now cover Ax, with N cubes Qj. = 1, ... . such that each cube Qj has sidelengths comparable to 6. Due the controlled curvature, we know that the cover has controlled multiplicity and
t).
N R,A. 1/8--1.
Since we know that
aa (2, S
Σ s0 (2,
suffices to prove that the RHS above is 0()). Via Lemma B.9 above, suffices to prove the following:
[ E E
dr = 0(a).
Now, we employ the following known trick:
( -2
c c- p dr du
-a
aa²
= e p dp
0
22(n/2,a)
where ((s, x)) denotes the usual lower incomplete Gamma function. From well-known asymptoties. it is now clear that for small enough a, the RHS is O(a).
B.5 COMPRESSION PARAMETERS: GENERAL CASE
Now we go for the full neural net compression, which essentially an iterated version of Proposition
B.5 Consider a neural net A consisting of m layers, and let A, denote the neural net A whose first j
layers have been compressed using the scheme in Algorithm at each level. By way of notation, let
A denote the jth layer of the original neural net (assumed to be of dimension h} h2), and A the jth layer of the compressed neural net. Then, we have the following
Proposition B.11. Given >> 0 and m parameter pairs (az, B,). we can find compression Am
TT
with
O (1og(h)43)/B,oz) parameters and associated parameters Pj such that
m
EEE (Ax,t) VE, (Amz,t)
> 5=1
PJ <E
with probability at least
Ty. where
[1 B.) -S(2-1, -S( 1=1
Tj
Proof. We see that
WE, (Ax,t) t)= th, (Am t) < WE, (Ax, the (A t) bE, (Aiz, ( ehe (A2z, t)
bhe, (A2x, wey (Aso, 1)) +... / (Am--1, - Me, (Am
12,,
29

---

Published as a conference paper at ICLR 2021
We will be compressing one individual layer at at time. At the first layer, start with the entry taken from the sample set.
Algorithm gives us a compression A' that satisfies, with given 01, 31 that
|| x A x1 I au &1 ||=|||]
with probability at least 13. Here the reduced number of parameters Å is O (log(1)))/Bgoo)) As result,
HE, WEE (A t) S pt,
where in the general situation (that is, without any additional assumption on the decision boundary 2)), Nj). P1 -'E, (o(A t)ō, with probability at least 1 S(x, A1; t)/ B1 (this via Proposition
B.5 via application of Markov's inequality).
Now that the first layer has been compressed, the entry data at the second layer is the vector Φ sc. Once again, we estimate that with given parameters 0z2, 32, Algorithm generates a contraction A² the second layer with satisfies (with probability least 1 92)
( ( 2 az A² 1
< \a22| ||
(Lipschitz-neess of the nonlinearity)
So, with probability at least (1 32) 31), we have that
[|A(()A²2)) A (0 - Aaz A [||4'x|| 0a || |=]]=]]]]
I AaallA4 || ||.A4||=<laa || + +all [-]]]]
= Aa + a |1)]| | || | |||||=]|
We have then
WE, (A1œ, 1) ME, (Azæ, 1) s P2:
where in the general situation, P2 = EE, (0(A2*)), 6)62 with probability at least (1 - (1)3:111-- - 32) S(#", A2; t)/8.. 82. Here á denotes the output at the jth layer of the compressed net.
It can be checked via induction that the above process iterated times gives that
|| ( 1)) A (0(#
('((0' (6(2)-1) X a
II i=1
(1
03)
II 1=1
|A |||/||
with probability at least II (1 -1- (.). That implies that
WE, WE, (A)-12,t) - (A,r,t) Sis
where in the general situation, Pj
bE, vE (0(A, t,) (1)A,
with probability at least
II (1-3)) - A5;1)/85.
Finally, this implies that
Whe, (Ax,t) WE, (Amet, 1)) S Σ Pjr
(53)
1=1
with probability at least
TJ
j=1
and the reduced number of parameters in the compressed net is
Σ o (log(H333//8,o3)
30

---

Published as a conference paper at ICLR 2021
B.6 COMPRESSION PARAMETERS: TAME DECISION BOUNDARY
We are left to indicate the proof of the second part of Proposition 5 from the main text. This follows in straightforward way following the proof of Proposition B. using the bounds in Propositions B.6 B.8 and B.T00at at every step, instead of the bounds in Proposition B.5 as we have done in the
above proof.
B.7 SECOND (ALTERNATIVE) DEFINITION OF CAPACITY SENSITIVITY
As an alternative working definition of noise sensitivity, we define the following: Definition 5.
( DE, (o(Az),
A;z,
(54)
VE, (o(Ar),
where the expectation is over r, E - and all Brownian paths n starting at the point ((A(r +
and ending inside Ff(y) within time t (the latter sits inside the path space starting 6 A(x + (n) and endowed with the Wiener measure). The random variable ( A(x + |=]]))) t) is defined as 1 the path "A strikes Es within time and if does not.
From the point of view of ML computation, Definition S has slight advantage over Definition 4 In
other words, it is computationally more efficient view of the following sampling scheme:
Proposition B.12. If fh...... ...: mm denote m sampled values of n and 751 Tij2,... Yike denote ls sampled Brownian paths starting at + | then
X
X 5
mk
where
X5t EE (Ā(A(x VE, (0) (Ar),t)
|| 13 )). ue, ()(Ax),
approximates S(x, A;t) well with high probability.
Proof. Begin by sampling m values ... 7m of and Brownian paths 7/1. 7/2,, .., Yyk starting from each such ø + || Attached to each such selection an independent random variable X5 (ø(Ar), t) which takes values in [0, 1]. For each j, we have that E (X (ō(x)), f))
S(x, A; E) (6(As Ax), 1). Let X denote the mean of all the random variables X5t, j j= 1,.., m, =
1. k. Now, can bring in Hoeffding's 's version of the Chernoff concentration bounds, which gives
us that
I X - S(z, A;t)] 2
(o,x)) (
T
2r ma
(55)
31

---

Published as a conference paper at ICLR 2021
C APPENDIX C: DATASETS, SAMPLING DETAILS, TRAINING DETAILS AND FURTHER EXPERIMENTS.
C.I TECHNICAL SETUP
The experimental section of the work conducted mainly CUDA 10.2 GPU-rack consisting of four NVIDA TITAN V units: this includes the model training as well as Brownian motion sampling and further statistics. The neural network framework of choice was Py 1.5. We provide the training as well as the sampling code for our experiments.
C.2 DATASETS
We worked with the well-known MNIST and CIFAR-10 datasets. The MNIST is a 784-dimensional dataset that consists of 60000 images of handwritten digits whose dimensions are (28, 28); 50000 images were used for training and 10000 for validation. CIFAR-I0 is collection of 60000 32-by-32 color images (i.e. 3072-dimensional dataset) corresponding to 10 different classes: airplanes, cars, birds, cats, deer, dogs, frogs, horses, ships and trucks; 50000 images were used for training and 10000 for validation.
As pointed out in the main text, adversarially robust decision boundaries exhibit fundamental dif- ferences between the MNIST and the CIFAR-I0 dataset. MNIST yields particularly simple robust boundaries stemming from it's almost binary nature as elaborated in [Schmidt et al. (2017) and confirmed in /Fordd al.] (2019). CIFAR-10 the other hand is notoriously vulnerable attacks, which is reflected in the quantities we measure. For our experiments this means that adversaria//noisy training flattens the surrounding boundary, i.e. saturates the isoperimetric bound, but nevertheless still exhibits spiky structure will be reflected in the measurements of the isocapacitory bounds. For MNIST on the other hand the approximately binary nature of the examples gives the decision boundary much less 'freedom', resulting in less distinct quantitative representation.
For some exploratory toy-examples (cf. Fig. Fig. Fig. 3 in the main text) we generated a planar dataset that alternates along circle of radius 5: for given ray through the origin we generate several points on the ray at approximately distance from the origin and assign them to class 0; then rotate the ray by small angle counter-clockwise, sample several points the rotated ray again approximately distance from the origin and this time assign them to class 1. Repeating this process we produce the mentioned 2-class dataset that alternates along the circle of radius and consists of 1250 points.
C.3 SAMPLING DETAILS
An evaluation of the isocapacitory saturation & is obtained by sampling 10000 Brownian paths with 400 steps. In light of the curse of dimensionality, this configuration seems adequate for our purposes: theoretically, by projecting Brownian motion along the normal directions of the decision boundary one sees that estimating hitting probabilities is essentially a lower dimensional problem, e.g. I-dimensional if the decision boundary is hyperplane; practically, our experiments were numerically stable w.r.t. resampling and sample-batch
Further, for each data point æ the relative error volume μ(x, r) is computed by sampling 10000 points uniformly in B(x, r). To compare with isoperimetric bounds (Subsection (.2) for each data point sample 1000 points, normally distributed N(x, r/ /T) and concentrated around in the ball B(x, r), and apply a PGD with 400 steps to obtain distance to the decision boundary A (a setup similar to Ford al. (2019)). As above, repetitive runs average reveal acceptable numeric stability to the order of 10
C.4 DEFENSE TRAINING: FGSM VS PGD
In the present work we are interested in how adversarial/noise defense training are reflected geometri- cally. To this end we study the application of two defense strategies FGSM and PGD.
Previous work Ford et al. (019)) indicates that FGSM-bascr training already leads to boundary flattening. However, in general it cannot be guaranteed that the FGSM-based adversarial training will
32

---

Published as a conference paper at ICLR 2021
provide appropriate levels of robustness (against strong adversaries, e.g. iterative attacks) recently, Wong et al. (2020) has shown that only with some proper designs (c.g. random start) the FGSM-based training will be robust. This indicates that if not taken carefully. FGSM-basee and stronger defense trainings (e.g. PGIDbased adversarial training in Madry et al. 2018)) can be very different in their resulting geometry of the decision boundary. Therefore, we opt for evaulating FGSM-based as the PGD-based defense in an attempt to reveal the relationship between the decision boundaries of truly robust model and the isocapacitory saturation values. Details are given in Fig. 4 and the accompanying analysis.
well
C.5 TRAINING DETAILS
Training on the CIFAR-10 dataset. All training procedures used standard techniques for data augmentation such as flips, horizontal shifts and crops and were normed with respect to data mean and standard deviation. The training of the Wide-ResNet followed the framework provided by [Cubuk] eet al. (2018) with weight decay 5e-4, batch size 128 and a decrease of the initial learning rate of 0.1 by factor 0.2 at epochs 60, 120 and 160. The ResNets were trained with weight decay le-4 respectively and step wise decrease of the learning rate 0.1 by factor 0.1 epochs 100 and 150.
Training on the MNIST dataset. We consider two models trained with various data augmentation techniques. We trained a LeNet-5 architecture LeCun al. (1998) over 50 epochs with a learning rate le-3 and weight decay 5e-4, batch size of 64, while optimizing cross entropy loss using root mean square propagation. The same procedure was implemented to train a basic convolutional neural network consisting of four convolutional and two subsequent linear layers. While LeNet-5 also uses convolutional layers, it additionally uses max max-pooling after each convolutional layer.
Training on the planar toy dataset. We experimented with several 5-layer MLP models (each layer containing 20, 40, 70 or 100 hidden units) on the mentioned planar dataset concentrated along the circle of radius 5 centered at the origin. Training followed straightforward ADAM optimization procedure with learning rate of 1.0e-5 and batch size of 128.
C.6 DATA MANIPULATIONS DURING TRAINING
To evaluate how various training methods affect the geometric properties of the decision boundary, for all models we conduct three major types of training: training clean data; data with layer of Gaussian perturbations with variance o² = 0.4; finally, training on data with additional adversarial defense methods, where for each training example
add an adversarially chosen example the dataset using the fast gradient sign method (FGSM). For LeNet-5 we also considered the effect of adversarial training, where the additional example is the result Brownian of random walk terminated upon collision with the decision boundary. See Fig. C.7 for a visual example of perturbations/attack with the described methods. The resulting accuracies evaluated on the clean datasets for all trained models are shown in tables I [ the the robustness LeNet-5 architectures. Figure C.7 exhibits the resulting for the trained model's accuracies on clean data, PGD attacks with = 0.5 and < 1.0, Gaussian perturbations and fog with
As an additional benchmark of the trained models, we evaluated
severity 4 according to the MNIST-C dataset Mu & Gilmer (001)).
C.7 IsocAPACITORY AND ISOPERIMETRIC RESULTS
Here summarize the observations indicated by the obtained geometric data. Besides the results
presented in the main text for models Wide-ResNer 28-10 10 and LcNet-5 (Fig. 44. we also considered
geometric properties for said Residual Networks (CIFAR-10) (see Fig. 13 with 32, 44 and 56
layers and a basic Convolutional Neural Network (MNIST) (see Fig. observations made in the main text.
The results admit to the
33

---

Published as a conference paper at ICLR 2021
Hitting probability
isocapacitory bound
with y of Isoperimetric bound
ResNet layers (CIFAR)
1.0
0.04
0.9
0.03
0.8
40
0.7
0.02
0.6
0.01
0.5
0.4
ResNet 44 layers (CIFAR)
0.05
80
1.0
0.04
0.9
3
0.03
0.8
0.7
0.02
0.6
20
0.5
0.00
ResNet 56 layers (CIFAR)
0.05
1.0
0.04
0.9
0.8
0.03
0.7
0.6
0.5
0.4
naturally trained
adversarially trained (fgsm)
augmentation 0.44
The statistics obtained from the Residual Networks with 32, 44 and 56 layers on the CIFARIO dataset. For this experiment we considered the Brownian particles with average displace- ment equal to the radius of sphere with relative volume 0.01, where μ is defined according to equation 2 in the main text. The considered quantities are (Left) the probability of a Brownian particle collide with the decision boundary, (Center Left) the isocapacitory bound, i.c. the ratio of said probability versus relative volume (Center Right) the radius of the obtained sphere equal the RMSD of the particle and (Right) the saturation of the isoperimetric bound. We observe consistent behavior of the shown quantities for all three models. The trend isoperimetric saturation (although, not concentrated as the case of WRN and LeNet-5, Fig, 4 as well the increase of distances r are present. Again the isocapacitory saturation does not appear to follow a distinguished concentration around the case of a flat decision boundary despite the overall increase flatness: here both noisy and adversarial training seem to deliver decrease in In fact, the heat imprint of the ordinarily trained model exhibits "flatter" behaviour terms of T.
Figure 13:
Table Summary of validation accuracies for Wide-ResNets 28-10 for various training methods on the CIFARIO data set. Architecture
Training Type
Accuracy
Wide-ResNet 28-10
naturally trained
94.64%
Wide-ResNet 28-10
trained on noise (a² 0.1)
91.22 %
Wide-ResNet 28-10
trained on noise (a2 0.4)
86.07 %
Wide-ResNet 28-10
adversarially trained (fgsm)
87.10% %
Wide-ResNet 28-10
adversarially trained (pgd)
85.05 %
34

---

Published as a conference paper at ICLR 2021
HitLing probebility
Sat. of Isocapacitory bound
Redius with rel vol of %
Sat. of Isoperimetric bound
0.040
Desic CNV (MNIST)
0.035
3.5
25
1.0
0.030
0.025
0.020
15
1.5
0.8
0.010
1.0
naturally trained
adversarially trained (fysm)
Gaussian data augmentation (a' 0.4)
Figure 14: Statistics for convolutional neural network with four convolutional and two linear layers applied to the MNIST dataset. This particular convolutional model shows that not every anchiteccure/taannnnnaaaaa
instance displays the distinguished trend in increasing the isoperimetric saturation however, even in this scenario the isoperimetric saturation is quite sharp. Similar to other experiments above, the isocapacitory saturation 7 the other hand does not concentrate such an extent.
Clean
PGD Allack
Geuasonn Pecturbation
Undiretted Allakk
972
dog
<hip
desr
plane
place
d8g
20
100
25
53
75
100
100
50
75
100
Confiderce
Confilence
Figure 15: Typical examples of the CIFAR-10 dataset used to train the models. From left right, the clean image, PGD adversarial example, a Gaussian perturbation (o² 0.4) and the terminal point of a Brownian random walk (undirected attack) immediately after colliding with the decision boundary are shown. The comparison between the PGD adversarial example and the right picture emphasize the degree to which spikes in the decision boundary deviate from the average distance between boundary and clean example.
Table 2: Summary of validation accuracies for the ResNets with 32, 44 and 56 layers for various training methods on the CIFAR10 data set.
Architecture
Training Type
Accuracy
Residual Network 32 layers
naturally trained
91.81%
Residual Network 32 layers
adversarially trained (fgsm)
86.13%
Residual Network layers
trained on noise (o2 0.4)
84.36%
Residual Network 44 layers
naturally trained
92.36%
Residual Network 44 layers
adversarially trained (fgsm)
88.20%
Residual Network 44 layers
trained on noise (o2 = 0.4)
84.09%
Residual Network 56 layers
naturally trained
92.77%
Residual Network 56 layers
adversarially trained (fgsm)
87.53%
Residual Network 56 layers
trained on noise (o² 0.4)
84.09%
35

---

Published as a conference paper at ICLR 2021
Accuracies for various training types during confounding methods
100
accuracy [%)]
60
naturally trained
adversarially trained (fgsm)
20
trained on noise (a? 0.4)
adversarially trained (Brownian)
Clean
PGD, 0.5
PGD, 1.0
Gaussian noise 0² 0.4
Fog corruption
Evaluation of the accuracies of the LeNet-5 (MNIST) models during a range of attacks. While for clean data all models exhibit almost similar accuracy, the adversarially trained models exhibit more robustness during various attacks. For all measures we see the worst performance of the models trained randomly chosen adversarial examples.
Figure 16:
Table Summary of validation accuracies for LeNet-5 and convolutional neural network with four convolutional and two linear layers for various training methods on the clean MNIST data set. Architecture
Training Type
Accuracy
LeNet-5
naturally trained
99.00%
LeNet-5
adversarially trained (fgsm)
98.99%
LeNet-5
adversarially trained (pgd)
98.55%
LeNet-5
adversarially trained (Brownian)
97.17%
LeNet-5
trained on noise (o² 0.4)
99.02%
CNN
naturally trained
98.99%
CNN
adversarially trained (fgsm)
98.65%
CNN
trained on noise (o2 = 0.4)
98.93%
36


Reviews:
[{"review_id": "tumesXDIXWw", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Title: HEATING UP DECISION BOUNDARIES: ISOCAPACITORY SATURATION, ADVERSARIAL SCENARIOS AND GENERALIZATION BOUNDS\n\nSummary of the paper:\n\nThe idea of the paper is to introduce a new view on the geometry of the decision boundary of a classifier. Just as we may speak of the \"margin\" as in large margin methods and the hinge loss, the paper introduces the idea of a heat diffusion from the decision boundary - the amount of heat diffused to the data points gives a more subtle notion of stability. What a creative idea. Even cooler, the authors show that we may utilise the Feynman-Kac duality to now cast this in terms of the probability of a random walk starting at the data to hit the decision boundary. This is appealing because it differentiates between being near to an e.g. long thin decision boundary which approaches from just one side, to being completely surrounded by the decision boundary - something not accounted for by distance to the boundary.\n\nMost of the paper is a really nice and gentle discussion of this idea. I gained some appreciation for the work even though it is extremely technical under the hood, and this is due to the nice writing in the main paper. To allow this the author's had to push their main result to the end of the paper (proposition 4.1) and leave the details to the appendix, but this is a fair trade-off in my opinion.\n\nIt is remarkable that in spite of the technicality involved, the authors manage to obtain proposition 4.1, an impressive first application of the new notions. \n\nThe appendices are dense, but still nicely written and enjoyable even for the relatively uninitiated such as myself.\n\nPros:\n\nThis paper stands out as genuinely creative and novel. It is written with an enjoyable style which will surely motivate many theoreticians to delve into the details. I only wish I had the time and talent to do so myself.\n\nWhile primarily theoretical and highly novel, the authors even include some thought provoking experimental results.\n\nCons:\n\nOne might argue whether the structure of the paper is ideal, but I would counter that the paper is extremely pleasant to read, and that it makes more sense to try to lure the reader into a curious mindset rather than bash them on the head with heavy details from the outset. Nicely done.\n\nRecommendation:\n\nI strongly recommend to accept this paper. Even if the details - which I have not checked - prove to have issues, the novelty of the work makes it a must-have in the portfolio of ideas included in the upcoming ICLR.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "nHKnaRqGBc1", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The contributions of the paper center on i) the introduction of diffusion-related tools for studying classifier decision boundaries; and ii) using those tools to connect decision boundary geometry, adversarial robustness, and generalization. The paper provides an analysis that provides insight into how curvature and local decision boundary geometry is influenced by adversarial defences, suggests a method for checking adversarial robustness, and then makes statements about model generalization based on geometric properties revealed by monte-carlo simulation of diffusions. \n\n\nStrengths:\n\nThe paper brings together beautiful areas of mathematics, probability, and random processes in an effort to characterize decision boundaries of DNNs and the behavior of DNNs on unseen examples, adversarial or otherwise. Curvature, heat diffusions, diffusion geometry, compression play a role. Feynman-Kac duality is leveraged to pass from the intractable analytical methods in the literature to stochastic simulations that can be undertaken by practitioners with data. The paper appears to make some novel links between generalization and decision boundary diffusion geometry, offers an apparently novel analysis of the impact of common adversarial defenses to Brownian adversaries, and at a minimum offers some new insights into how we might think about, and interpret, complex decision boundaries learned by neural nets or other nonlinear classifiers. The paper also follows up with experiments in the context of real applications and complex models. A series of Appendices provide technical details and experimental protocols.\n\n\nWeaknesses:\n\nThe breadth of topics, the range of tools, steps, and quantities seems to have left the authors without enough space to get it all across. While the Appendices provide valuable details, additional definitions and discussion, the main body of the paper lacks clarity, context, and sufficient organization to allow an average reader to follow, or even appreciate, some of the arguments and key contributions. This is potentially the main weakness of the paper. If this were a longer journal submission, it might even make sense to separate the work into two papers: one exploring adversarial learning, and another exploring generalization.\n\nThe introduction and motivation sections of the paper could be improved by explicitly stating at a high level what the paper is contributing, and what insights will come out of the analyses. For example, the abstract states: “This leads to new insights concerning the \"flattening-of-boundary\" phenomenon.” What insights are in store, specifically? Imagine the paper were to be selected for a popular pod-cast, or a 5-minute lightning oral presentation at a conference: how would you distill it down to the essential contributions, components, and logical steps required to arrive at the key results?\n\nAnother concern is that while adversarial defense training by studying hitting times is valuable, it feels slightly misplaced/incomplete because an adversary might (often?) follow geodesics/geometry to very quickly obtain an error sample in cases where diffusion distances are high (e.g. a dumbbell). So while it’s helpful to be able to say that a random walk has a low probability of becoming an error sample from a point x, it doesn’t necessarily give us a guarantee about a “determined” adversary, who isn’t constrained at all to follow random walks (“Brownian attacks”).\n\n\nRecommendation: \nOverall I recommend a borderline reject. The paper has some interesting ideas, and probably novel contributions, but needs revising for clarity and conciseness to be digestible or impactful. The paper needs to also be more specific about how the results relate to, leverage, and complement those in the literature/references. For example, the paper says in a few places that conclusions “agree with” reference [X]. Does this mean they have just rederived the same result, offering no additional insight? What is the significance of the agreement, and what does it provide to the community as a takeaway? It would be helpful to call out very concretely what is being contributed, and how it relates/differs relative to the literature.\n\n\nOther suggestions:\n\n- Perhaps clarify early on in the paper where the Brownian motion is happening. A reader might wonder: Is it in the ambient space? Is it on a graph? Is it on a manifold parameterized by some kind of intrinsic (or local) coordinates extracted from the model?\n\n- Discuss the significance and interpretation of Lemmas 2.2 and 2.3. Why are they introduced? What are they saying intuitively, and how are they going to support your arguments later? There’s very little text around them (maybe due to a space problem and some ruthless trimming to make it all fit!)\n\n- For the sake of completeness, define explicitly how you intend to handle ties in taking the argmax, and by extension, when defining E(y) (i.e. so that N is a subset of E(y)).\n\n- Section 4 seems to have lost sight of the overall desired result, by omitting how L(g) controls L(f). Apologies if I’ve missed something obvious, but it seems like the strategy to control generalization of f in terms of hitting times is to pass to the compressed version, and control that. So where’s the link between generalization of f and generalization of g? Does Def 1 say it? \n\n- Eq (7) -- \\phi_{E} should be introduced to make the definition self contained. Discuss why Def 1 is reasonable and what it means intuitively. The paper says it’s an “initial suggestion”. Why did you suggest this particular defn, over others?\n\n- pg. 4 “isocapacitory” results: the analogy abruptly jumps from heat diffusion to “charge” accumulation. Try to link the two and provide a transition (without the reader having to refer to the lengthy appendices).\n\n- It could be interesting to make a connection to heat diffusion classifiers (e.g. Szlam, \nRegularization on Graphs with Function-adapted Diffusion Processes, JMLR 2008), in which heat is instead diffused outward from the labels to classify new points, giving a potentially interesting characterization of the decision boundary (by construction). Maybe such methods can locally approximate more complex learning algorithms thereby providing global insight into their decision boundaries? \n\n\nUPDATE TO REVIEW FOLLOWING AUTHOR REVISIONS AND COMMENTS\n---------------------------------------------------------------------------------------------------\nI thank (and commend) the authors for their detailed, point-by-point responses.\nThe authors have made a good effort in their revisions to improve and clarify the exposition, and rectify the other comments made by the reviewers. The paper could still benefit from a deeper rewrite -- there's just so much that can be packed into a conference paper with limited real estate, and the authors are seeking to make several contributions under the umbrella of one submission (as the title suggests). So clarity suffers, and impact will suffer as a result. But, in my mind that shouldn't necessarily be a show stopper at this stage, in light of the revisions. I am therefore upgrading my recommendation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "g50cLA0o0yL", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an isocapacitory measure for analysing decision bound, in a way complementing the isoperimetric analysis proposed by Ford et al. 2019. The authors showed that the new measure captures different geometric properties of the decision boundary, potentially useful for adversarial training. The paper also proposed a new generalisation bound, although did not compare with other generalisation bounds.\n  \nThe paper contains a number of interesting ideas and experiments. In general, the combination of heat diffusion and geometric analysis in the context of machine learning seems an interesting angle worth exploring.\n\nThe paper in its current form is a bit difficult to read. The key ideas are not clearly separated from the existing work. Some math notations are not clearly defined. In particular, many definitions rely on globally defined constants such as r and t, which has not been made clear to the reader. \n\nBelow are some specific comments:\n\n- Equations 2-5 should be clear that r and t are constants in the definitions or inequalities. The assumption r=sqrt(nt) should be made explicit. This affects the definition of c_n in Equation 4.\n-  Equation 3 is incorrect. When mu is less than 0.5, the RHS is negative.\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VTc2Q458BNX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper under review introduces a number of geometric measures (isoperimetric, isocapacitory ratios that relate to Brownian motion or heat diffusion probabilities) that are applied to study neural network decision boundaries locally.  Specifically, the studies applying the measures to study adversarially trained NN empirically, and there are generalization and network compression bounds analytically proven that are derived that relate to Brownian motion probabilities.    Empirical observations on LeNet and Wide ResNet trained on MNIST and CIFAR showed adversarially trained or noise trained networks did exhibit curvature of the decision boundary, showing finer structure than previously known.\n\nThe paper is clear and the application of isoperimetric and isocapacitory measures appears novel, as well as the empirical finding of curvature (determined through the isocapacitory measure) of adversarially trained NNs provides some new insight into the shape of decision boundaries of NN for robustness.  I didn't find the empirical results very convincing: the isoperimetric / isocapacitory measures do not show a clear distinction for adversarially trained networks, which appears close to the ordinary trained networks.  Its not clear whether the training methods are not sufficient to produce a robust enough NN or the measures introduced do not adequately describe the adversarially trained nets.  All seem to exhibit curvature, but I'd assume the adversarially trained ones exhibit less curvature, which is not the case from the expt.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four reviewers have reviewed this paper and after rebuttal, they were overall positive about the proposed idea. We congratulate authors on the paper.
Decision: Accept (Poster)