Robustness of classifiers: from adversarial to random noise

Introduction

State-of-the-art classifiers, especially deep networks, have shown impressive classification performance on many challenging benchmarks in visual tasks and speech processing . An equally important property of a classifier that is often overlooked is its robustness in noisy regimes, when data samples are perturbed by noise. The robustness of a classifier is especially fundamental when it is deployed in real-world, uncontrolled, and possibly hostile environments. In these cases, it is crucial that classifiers exhibit good robustness properties. In other words, a sufficiently small perturbation of a datapoint should ideally not result in altering the estimated label of a classifier. State-of-the-art deep neural networks have recently been shown to be very unstable to worst-case perturbations of the data (or equivalently, adversarial perturbations) . In particular, despite the excellent classification performances of these classifiers, well-sought perturbations of the data can easily cause misclassification, since data points often lie very close to the decision boundary of the classifier. Despite the importance of this result, the worst-case noise regime that is studied in only represents a very specific type of noise. It furthermore requires the full knowledge of the classification model, which may be a hard assumption in practice.

In this paper, we precisely quantify the robustness of nonlinear classifiers in two practical noise regimes, namely random and semi-random noise regimes. In the random noise regime, datapoints are perturbed by noise with random direction in the input space. The semi-random regime generalizes this model to random subspaces of arbitrary dimension, where a worst-case perturbation is sought within the subspace. In both cases, we derive bounds that precisely describe the robustness of classifiers in function of the curvature of the decision boundary. We summarize our contributions as follows:

In the random regime, we show that the robustness of classifiers behaves as $\sqrt{d}$ times the distance from the datapoint to the classification boundary (where $d$ denotes the dimension of the data) provided the curvature of the decision boundary is sufficiently small. This result highlights the blessing of dimensionality for classification tasks, as it implies that robustness to random noise in high dimensional classification problems can be achieved, even at datapoints that are very close to the decision boundary.

This quantification notably extends to the general semi-random regime, where we show that the robustness precisely behaves as $\sqrt{\nicefrac{{d}}{{m}}}$ times the distance to boundary, with $m$ the dimension of the subspace. This result shows in particular that, even when $m$ is chosen as a small fraction of the dimension $d$, it is still possible to find small perturbations that cause data misclassification.

We empirically show that our theoretical estimates are very accurately satisfied by state-of-the-art deep neural networks on various sets of data. This in turn suggests quantitative insights on the curvature of the decision boundary that we support experimentally through the visualization and estimation on two-dimensional sections of the boundary.

The robustness of classifiers to noise has been the subject of intense research. The robustness properties of SVM classifiers have been studied in for example, and robust optimization approaches for constructing robust classifiers have been proposed to minimize the worst possible empirical error under noise disturbance . More recently, following the recent results on the instability of deep neural networks to worst-case perturbations , several works have provided explanations of the phenomenon , and designed more robust networks . In , the authors provide an interesting empirical analysis of the adversarial instability, and show that adversarial examples are not isolated points, but rather occupy dense regions of the pixel space. In , state-of-the-art classifiers are shown to be vulnerable to geometrically constrained adversarial examples. Our work differs from these works, as we provide a theoretical study of the robustness of classifiers to random and semi-random noise in terms of the robustness to adversarial noise. In , a formal relation between the robustness to random noise, and the worst-case robustness is established in the case of linear classifiers. Our result therefore generalizes in many aspects, as we study general nonlinear classifiers, and robustness to semi-random noise. Finally, it should be noted that the authors in conjecture that the “high linearity” of classification models explains their instability to adversarial perturbations. The objective and approach we follow here is however different, as we study theoretical relations between the robustness to random, semi-random and adversarial noise.

Definitions and notations

Note that $\boldsymbol{r}_{\mathcal{S}}^{*}(\boldsymbol{x}_{0})$ can be equivalently written

In the remainder of the paper, the goal is to establish relations between the robustness in the random and semi-random regimes on the one hand, and the robustness to adversarial perturbations $\|\boldsymbol{r}^{*}(\boldsymbol{x}_{0})\|_{2}$ on the other hand. We recall that the latter quantity captures the distance from $\boldsymbol{x}_{0}$ to the classifier boundary, and is therefore a key quantity in the analysis of robustness.

In the following analysis, we fix $\boldsymbol{x}_{0}$ to be a datapoint classified as $\hat{k}(\boldsymbol{x}_{0})$. To simplify the notation, we remove the explicit dependence on $\boldsymbol{x}_{0}$ in our notations (e.g., we use $\boldsymbol{r}^{*}_{\mathcal{S}}$ instead of $\boldsymbol{r}^{*}_{\mathcal{S}}(\boldsymbol{x}_{0})$ and $\hat{k}$ instead of $\hat{k}(\boldsymbol{x}_{0})$), and it should be implicitly understood that all our quantities pertain to the fixed datapoint $\boldsymbol{x}_{0}$.

Robustness of affine classifiers

The following result shows a precise relation between the robustness to semi-random noise, $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$ and the robustness to adversarial perturbations, $\|\boldsymbol{r}^{*}\|_{2}$.

The following inequalities hold between the robustness to semi-random noise $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$, and the robustness to adversarial perturbations $\|\boldsymbol{r}^{*}\|_{2}$:

with probability exceeding $1-2(L+1)\delta$.

The proof can be found in the appendix. Our upper and lower bounds depend on the functions $\zeta_{1}(m,\delta)$ and $\zeta_{2}(m,\delta)$ that control the inequality constants (for $m$, $\delta$ fixed). It should be noted that $\zeta_{1}(m,\delta)$ and $\zeta_{2}(m,\delta)$ are independent of the data dimension $d$. Fig. 1 shows the plots of $\zeta_{1}(m,\delta)$ and $\zeta_{2}(m,\delta)$ as functions of $m$, for a fixed $\delta$. It should be noted that for sufficiently large $m$, $\zeta_{1}(m,\delta)$ and $\zeta_{2}(m,\delta)$ are very close to $1$ (e.g., $\zeta_{1}(m,\delta)$ and $\zeta_{2}(m,\delta)$ belong to the interval $[0.8,1.3]$ for $m\geq 250$ in the settings of Fig. 1). The interval $[\zeta_{1}(m,\delta),\zeta_{2}(m,\delta)]$ is however (unavoidably) larger when $m=1$.

The result in Theorem 1 shows that in the random and semi-random noise regimes, the robustness to noise is precisely related to $\|\boldsymbol{r}^{*}\|_{2}$ by a factor of $\sqrt{\nicefrac{{d}}{{m}}}$. Specifically, in the random noise regime ($m=1$), the magnitude of the noise required to misclassify the datapoint behaves as $\Theta(\sqrt{d}\|\boldsymbol{r}^{*}\|_{2})$ with high probability, with constants in the interval $[\zeta_{1}(1,\delta),\zeta_{2}(1,\delta)]$. Our results therefore show that, in high dimensional classification settings, affine classifiers can be robust to random noise, even if the datapoint lies very closely to the decision boundary (i.e., $\|\boldsymbol{r}^{*}\|_{2}$ is small). In the semi-random noise regime with $m$ sufficiently large (e.g., $m\geq 250$), we have $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}\approx\sqrt{\nicefrac{{d}}{{m}}}\|\boldsymbol{r}^{*}\|_{2}$ with high probability, as the constants $\zeta_{1}(m,\delta)\approx\zeta_{2}(m,\delta)\approx 1$ for sufficiently large $m$. Our bounds therefore “interpolate” between the random noise regime, which behaves as $\sqrt{d}\|\boldsymbol{r}^{*}\|_{2}$, and the worst-case noise $\|\boldsymbol{r}^{*}\|_{2}$. More importantly, the square root dependence is also notable here, as it shows that the semi-random robustness can remain small even in regimes where $m$ is chosen to be a very small fraction of $d$. For example, choosing a small subspace of dimension $m=0.01d$ results in semi-random robustness of $10\|\boldsymbol{r}^{*}\|_{2}$ with high probability, which might still not be perceptible in complex visual tasks. Hence, for semi-random noise that is mostly random and only mildly adversarial (i.e., the subspace dimension is small), affine classifiers remain vulnerable to such noise.

Robustness of general classifiers

We now consider the general case where $f$ is a nonlinear classifier. We derive relations between the random and semi-random robustness $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$ and worst-case robustness $\|\boldsymbol{r}^{*}\|_{2}$ using properties of the classifier’s boundary. Let $i$ and $j$ be two arbitrary classes; we define the pairwise boundary $\mathscr{B}_{i,j}$ as the boundary of the binary classifier where only classes $i$ and $j$ are considered. Formally, the decision boundary $\mathscr{B}_{i,j}$ reads as follows:

We assume for the purpose of this analysis that the boundary $\mathscr{B}_{i,j}$ is smooth. We are now interested in the geometric properties of the boundary, namely its curvature. There are many notions of curvature that one can define on hypersurfaces . In the simple case of a curve in a two-dimensional space, the curvature is defined as the inverse of the radius of the so-called oscullating circle. One way to define curvature for high-dimensional hypersurfaces is by taking normal sections of the hypersurface, and looking at the curvature of the resulting planar curve (see Fig. 4). We however introduce a notion of curvature that is specifically suited to the analysis of the decision boundary of a classifier. Informally, our curvature captures the global bending of the decision boundary by inscribing balls in the regions separated by the decision boundary.

We now formally define this notion of curvature. For a given $\boldsymbol{p}\in\mathscr{B}_{i,j}$, we define $q_{i\;\|\;j}(\boldsymbol{p})$ to be the radius of the largest open ball included in the region $\mathcal{R}_{i}$ that intersects with $\mathscr{B}_{i,j}$ at $\boldsymbol{p}$; i.e.,

It should further be noted that the definition in Eq. (6) is not symmetric in $i$ and $j$; i.e., $q_{i\;\|\;j}(\boldsymbol{p})\neq q_{j\;\|\;i}(\boldsymbol{p})$ as the radius of the largest ball one can inscribe in both regions need not be equal. We therefore define the following symmetric quantity $q_{i,j}(\boldsymbol{p})$, where the worst-case ball inscribed in any of the two regions is considered:

This definition describes the curvature of the decision boundary locally at $\boldsymbol{p}$ by fitting the largest ball included in one of the regions. To measure the global curvature, the worst-case radius is taken over all points on the decision boundary, i.e.,

The curvature $\kappa(\mathscr{B}_{i,j})$ is simply defined as the inverse of the worst-case radius over all points $\boldsymbol{p}$ on the decision boundary.

In the case of affine classifiers, we have $\kappa(\mathscr{B}_{i,j})=0$, as it is possible to inscribe balls of infinite radius inside each region of the space. When the classification boundary is a union of (sufficiently distant) spheres with equal radius $R$ (see Fig. 3), the curvature $\kappa(\mathscr{B}_{i,j})=\nicefrac{{1}}{{R}}$. In general, the quantity $\kappa(\mathscr{B}_{i,j})$ provides an intuitive way of describing the nonlinearity of the decision boundary by fitting balls inside the classification regions.

In the following section, we show a precise characterization of the robustness to semi-random and random noise of nonlinear classifiers in terms of the curvature of the decision boundaries $\kappa(\mathscr{B}_{i,j})$.

2 Robustness to random and semi-random noise

We now establish bounds on the robustness to random and semi-random noise in the binary classification case. Let $\boldsymbol{x}_{0}$ be a datapoint classified as $\hat{k}=\hat{k}(\boldsymbol{x}_{0})$. We first study the binary classification problem, where only classes $\hat{k}$ and $k\in\{1,\dots,L\}\backslash\{\hat{k}\}$ are considered. To simplify the notation, we let $\mathscr{B}_{k}:=\mathscr{B}_{k,\hat{k}}$ be the decision boundary between classes $k$ and $\hat{k}$. In the case of the binary classification problem where classes $k$ and $\hat{k}$ are considered, the semi-random robustness and adversarial (or worst-case) robustness defined in Eq. (2) can be re-written as follows:

For a randomly chosen subspace, $\|\boldsymbol{r}_{\mathcal{S}}^{k}\|_{2}$ is the random or semi-random robustness of the classifier, in the setting where only the two classes $k$ and $\hat{k}$ are considered. Likewise, $\|\boldsymbol{r}^{k}\|_{2}$ denotes the worst-case robustness in this setting. It should be noted that the global quantities $\boldsymbol{r}_{\mathcal{S}}^{*}$ and $\boldsymbol{r}^{*}$ are obtained from $\boldsymbol{r}_{\mathcal{S}}^{k}$ and $\boldsymbol{r}^{k}$ by taking the vectors with minimum norm over all classes $k$.

The following result gives upper and lower bounds on the ratio $\frac{\|\boldsymbol{r}^{k}_{\mathcal{S}}\|_{2}}{\|\boldsymbol{r}^{k}\|_{2}}$ in function of the curvature of the boundary separating class $k$ and $\hat{k}$.

the following inequality holds between the semi-random robustness $\|\boldsymbol{r}^{k}_{\mathcal{S}}\|_{2}$ and the adversarial robustness $\|\boldsymbol{r}^{k}\|_{2}$:

with probability larger than $1-4\delta$. We recall that $\zeta_{1}(m,\delta)$ and $\zeta_{2}(m,\delta)$ are defined in Eq. (3, 4). The constants are $C=0.2,C_{1}=0.625,C_{2}=2.25$.

The proof can be found in the appendix. This result shows that the bounds relating the robustness to random and semi-random noise to the worst-case robustness can be extended to nonlinear classifiers, provided the curvature of the boundary $\kappa(\mathscr{B}_{k})$ is sufficiently small. In the case of linear classifiers, we have $\kappa(\mathscr{B}_{k})=0$, and we recover the result for affine classifiers from Theorem 1.

To extend this result to multi-class classification, special care has to be taken. In particular, if $k$ denotes a class that has no boundary with class $\hat{k}$, we have $\|\boldsymbol{r}^{k}\|_{2}=\infty$, and the previous curvature condition cannot be satisfied. It is therefore crucial to exclude such classes that have no boundary in common with class $\hat{k}$, or more generally, boundaries that are far from class $\hat{k}$. We define the set $A$ of excluded classes $k$ where $\|\boldsymbol{r}^{k}\|_{2}$ is large

Note that $A$ is independent of $\mathcal{S}$, and depends only on $d$, $m$ and $\delta$. Moreover, the constants in (11) were chosen for simplicity of exposition.

Assuming a curvature constraint only on the close enough classes, the following result establishes a simplified relation between $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$ and $\|\boldsymbol{r}^{*}\|_{2}$.

with probability larger than $1-4(L+2)\delta$.

Under the curvature condition in (12) on the boundaries between $\hat{k}$ and classes in $A^{c}$, our result shows that the robustness to random and semi-random noise exhibits the same behavior that has been observed earlier for linear classifiers in Theorem 1. In particular, $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$ is precisely related to the adversarial robustness $\|\boldsymbol{r}^{*}\|_{2}$ by a factor of $\sqrt{\nicefrac{{d}}{{m}}}$. In the random regime ($m=1$), this factor becomes $\sqrt{d}$, and shows that in high dimensional classification problems, classifiers with sufficiently flat boundaries are much more robust to random noise than to adversarial noise. More precisely, the addition of a sufficiently small random noise does not change the label of the image, even if the image lies very closely to the decision boundary (i.e., $\|\boldsymbol{r}^{*}\|_{2}$ is small). However, in the semi-random regime where an adversarial perturbation is found on a randomly chosen subspace of dimension $m$, the $\sqrt{\nicefrac{{d}}{{m}}}$ factor that relates $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$ to $\|\boldsymbol{r}^{*}\|_{2}$ shows that robustness to semi-random noise might not be achieved even if $m$ is chosen to be a tiny fraction of $d$ (e.g., $m=0.01d$). In other words, if a classifier is highly vulnerable to adversarial perturbations, then it is also vulnerable to noise that is overwhelmingly random and only mildly adversarial (i.e. worst-case noise sought in a random subspace of low dimensionality $m$).

It is important to note that the curvature condition in (12) is not an assumption on the curvature of the global decision boundary, but rather an assumption on the decision boundaries between pairs of classes. The distinction here is significant, as junction points where two decision boundaries meet might actually have a very large (or infinite) curvature (even in linear classification settings), and the curvature condition in (12) typically does not hold for this global curvature definition. We refer to our experimental section for a visualization of this phenomenon.

Experiments

We now evaluate the robustness of different image classifiers to random and semi-random perturbations, and assess the accuracy of our bounds on various datasets and state-of-the-art classifiers. Specifically, our theoretical results show that the robustness $\|\boldsymbol{r}^{*}_{\mathcal{S}}(\boldsymbol{x})\|_{2}$ of classifiers satisfying the curvature property precisely behaves as $\sqrt{\nicefrac{{d}}{{m}}}\|\boldsymbol{r}^{*}(\boldsymbol{x})\|_{2}$. We first check the accuracy of these results in different classification settings. For a given classifier $f$ and subspace dimension $m$, we define

where $\mathcal{S}$ is chosen randomly for each sample $\boldsymbol{x}$ and $\mathscr{D}$ denotes the test set. This quantity provides indication to the accuracy of our $\sqrt{\nicefrac{{d}}{{m}}}\|\boldsymbol{r}^{*}(\boldsymbol{x})\|_{2}$ estimate of the robustness, and should ideally be equal to $1$ (for sufficiently large $m$). Since $\beta$ is a random quantity (because of $\mathcal{S}$), we report both its mean and standard deviation for different networks in Table 1. It should be noted that finding $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$ and $\|\boldsymbol{r}^{*}\|_{2}$ involves solving the optimization problem in (1). We have used a similar approach to to find subspace minimal perturbations. For each network, we estimate the expectation by averaging $\beta(f;m)$ on 1000 random samples, with $\mathcal{S}$ also chosen randomly for each sample.

Observe that $\beta$ is suprisingly close to 1, even when $m$ is a small fraction of $d$. This shows that our quantitative analysis provide very accurate estimates of the robustness to semi-random noise. We visualize the robustness to random noise, semi-random noise (with $m=10$) and worst-case perturbations on a sample image in Fig. 5. While random noise is clearly perceptible due to the $\sqrt{d}\approx 400$ factor, semi-random noise becomes much less perceptible even with a relatively small value of $m=10$, thanks to the $\nicefrac{{1}}{{\sqrt{m}}}$ factor that attenuates the required noise to misclassify the datapoint. It should be noted that the robustness of neural networks to adversarial perturbations has previously been observed empirically in , but we provide here a quantitative and generic explanation for this phenomenon.

The high accuracy of our bounds for different state-of-the-art classifiers, and different datasets suggest that the decision boundaries of these classifiers have limited curvature $\kappa(\mathscr{B}_{k})$, as this is a key assumption of our theoretical findings. To support the validity of this curvature hypothesis in practice, we visualize two-dimensional sections of the classifiers’ boundary in Fig. 6 in three different settings. Note that we have opted here for a visualization strategy rather than the numerical estimation of $\kappa(\mathscr{B})$, as the latter quantity is difficult to approximate in practice in high dimensional problems. In Fig. 6, $\boldsymbol{x}_{0}$ is chosen randomly from the test set for each data set, and the decision boundaries are shown in the plane spanned by $\boldsymbol{r}^{*}$ and $\boldsymbol{r}^{*}_{\mathcal{S}}$, where $\mathcal{S}$ is a random direction (i.e., $m=1$). Different colors on the boundary correspond to boundaries with different classes. It can be observed that the curvature of the boundary is very small except at “junction” points where the boundary of two different classes intersect. Our curvature assumption in Eq. (12), which only assumes a bound on the curvature of the decision boundary between pairs of classes ${\hat{k}(\boldsymbol{x}_{0})}$ and $k$ (but not on the global decision boundary that contains junctions with high curvature) is therefore adequate to the decision boundaries of state-of-the-art classifiers according to Fig. 6. Interestingly, the assumption in Corollary 1 is satisfied by taking $\kappa$ to be an empirical estimate of the curvature of the planar curves in Fig. 6 (a) for the dimension of the subspace being a very small fraction of $d$; e.g., $m=10^{-3}d$. While not reflecting the curvature $\kappa(\mathscr{B}_{k})$ that drives the assumption of our theoretical analysis, this result still seems to suggest that the curvature assumption holds in practice, and that the curvature of such classifiers is therefore very small. It should be noted that a related empirical observation was made in ; our work however provides a precise quantitative analysis on the relation between the curvature and the robustness in the semi-random noise regime.

We now show a simple demonstration of the vulnerability of classifiers to semi-random noise in Fig. 7, where a structured message is hidden in the image and causes data misclassification. Specifically, we consider $\mathcal{S}$ to be the span of random translated and scaled versions of words “NIPS”, “SPAIN” and “2016” in an image, such that $\lfloor\nicefrac{{d}}{{m}}\rfloor=228$. The resulting perturbations in the subspace are therefore linear combinations of these words with different intensities.This example departs somehow from the theoretical framework of this paper, where random subspaces were considered. However, this empirical example suggests that the theoretical findings in this paper seem to approximately hold when the subspace $\mathcal{S}$ have statistics that are close to a random subspace. The perturbed image $\boldsymbol{x}_{0}+\boldsymbol{r}_{\mathcal{S}}^{*}$ shown in Fig. 7 (c) is clearly indistinguishable from Fig. 7 (a). This shows that imperceptibly small structured messages can be added to an image causing data misclassification.

Conclusion

In this work, we precisely characterized the robustness of classifiers in a novel semi-random noise regime that generalizes the random noise regime. Specifically, our bounds relate the robustness in this regime to the robustness to adversarial perturbations. Our bounds depend on the curvature of the decision boundary, the data dimension, and the dimension of the subspace to which the perturbation belongs. Our results show, in particular, that when the decision boundary has a small curvature, classifiers are robust to random noise in high dimensional classification problems (even if the robustness to adversarial perturbations is relatively small). Moreover, for semi-random noise that is mostly random and only mildly adversarial (i.e., the subspace dimension is small), our results show that state-of-the-art classifiers remain vulnerable to such perturbations. To improve the robustness to semi-random noise, our analysis encourages to impose geometric constraints on the curvature of the decision boundary, as we have shown the existence of an intimate relation between the robustness of classifiers and the curvature of the decision boundary.

We would like to thank the anonymous reviewers for their helpful comments. We thank Omar Fawzi and Louis Merlin for the fruitful discussions. We also gratefully acknowledge the support of NVIDIA Corporation with the donation of the Tesla K40 GPU used for this research. This work has been partly supported by the Hasler Foundation, Switzerland, in the framework of the CORA project.

References

Appendix

with $\beta_{1}(\delta,m)=\max((1/e)\delta^{2/m},1-\sqrt{2(1-\delta^{2/m})}$, and $\beta_{2}(\delta,m)=1+2\sqrt{\frac{\ln(1/\delta)}{m}}+\frac{2\ln(1/\delta)}{m}$.

Note first that the upper bound of Lemma 1 can be bounded as follows:

using $1+x\leq\exp(x)$. We find $\beta$ such that $\beta^{m/2}\exp\left(\frac{(1-\beta)m}{2}\right)\leq\delta$, or equivalently, $\beta\exp\left(1-\beta\right)\leq\delta^{2/m}$. It is easy to see that when $\beta=\frac{1}{e}\delta^{2/m}$, the inequality holds. Note however that $\frac{1}{e}\delta^{2/m}$ does not converge to $1$ as $m\rightarrow\infty$. We therefore need to derive a tighter bound for this regime. Using the inequality $\beta\exp(1-\beta)\leq 1-\frac{1}{2}(1-\beta)^{2}$ for $0\leq\beta\leq 1$, it follows that the inequality $\beta\exp(1-\beta)\leq\delta^{2/m}$ holds for $\beta=1-\sqrt{2(1-\delta^{2/m})}$. In this case, we have $1-\sqrt{2(1-\delta^{2/m})}\rightarrow 1$, as $m\rightarrow\infty$. We take our lower bound to be the max of both derived bounds (the latter is more appropriate for large $m$, whereas the former is tighter for small $m$).

We now prove our main theorem that we recall as follows:

with probability exceeding $1-2(L+1)\delta$.

For the linear case, $\boldsymbol{r}^{*}$ and $\boldsymbol{r}_{\mathcal{S}}^{*}$ can be computed in closed form. We recall that, for any subspace $\mathcal{S}$, we have

Let $k\neq\hat{k}(\boldsymbol{x}_{0})$. Define, for the sake of readability

Using the multi-class extension in Lemma 3, we conclude that

Assume that, for all $k\in\{1,\dots,L]\}\backslash\{\hat{k}(\boldsymbol{x}_{0})\}$

A.2 Proof of Theorem 2 and Corollary 1 (nonlinear classifiers)

First, we present an important geometric lemma and then use it to bound $\|\boldsymbol{r}^{*}_{\mathcal{S}}\|_{2}$. For the sake of the general readability of the section, some auxiliary results are given in Section A.3.

In the following result, we show that, when the curvature of a planar curve is constant and sufficiently small, the distance between a point $\boldsymbol{x}$ and the curve at a specific direction $\theta$ is well approximated by the distance between $\boldsymbol{x}$ and a straight line (see Fig. 8 for an illustration).

Let $\gamma$ be a planar curve of constant curvature $\kappa$. We denote by $r$ the distance between a point $\boldsymbol{x}$ and the curve $\gamma$. Denote moreover by $\mathcal{T}$ the tangent to $\gamma$ at the closest point to $\boldsymbol{x}$ (see Fig. 8). Let $\theta$ be the angle between $\boldsymbol{u}$ and $\boldsymbol{v}$ as depicted in Fig. 8. We assume that $r\kappa<1$. We have

We can set $C_{1}=0.625$ and $C_{2}=2.25$.

We consider two distinct cases for the curve $\gamma$. In the case where $\gamma$ is concave-shaped (Fig. 8, right figure), we have

and the upper bound in Eq. (33) directly holds. We therefore focus on the case where $\gamma$ is convex-shaped as illustrated in the left figure of Fig. 8. Define $R:=\nicefrac{{1}}{{\kappa}}$, one can write using simple geometric inspection

where $r^{\prime}=\|\boldsymbol{x}_{\gamma}-\boldsymbol{x}\|_{2}$. The discriminant of the second order equation (with variable $r^{\prime}$) is equal to

We have $\Delta\geq 0$ as $\theta$ satisfies the two assumptions $\tan^{2}(\theta)\leq 0.2R/r$ and $r/R<1$. The smallest solution of this second order equation is given as follows

Using some simple algebraic manipulations, we obtain

Using the inequality in Lemma 73 together with the two assumptions, we get

With simple trigonometric identities, the above expression can be simplified to

Since $\sin^{2}({\theta})\tan^{2}({\theta})=\tan^{2}({\theta})-\sin^{2}({\theta})$, we have

According to the assumptions $r/R<1$, therefore

Since $r/\cos(\theta)=\|\boldsymbol{u}\|_{2}$, one can finally conclude on the upper bound

When the curve is convex shaped (Fig. 8 left), we have $\|\boldsymbol{x}_{\gamma}-\boldsymbol{x}\|_{2}\geq\|\boldsymbol{u}\|_{2}$, and the desired lower bound holds. We focus therefore on the case where $\gamma$ has a concave shape, and coincides with with $\gamma_{2}$ (see Fig. 8 right). The following equation holds using simple geometric arguments

where $r^{\prime}=\|\boldsymbol{x}_{\gamma}-\boldsymbol{x}\|_{2}$. Solving this second order equation gives

After some algebraic manipulations, we get

Using the inequality in Lemma 74, together with the fact that $r\kappa<1$, we obtain

Using simple trigonometric identities, the above expression is simplified to

Since $\sin^{2}({\theta})\tan^{2}({\theta})=\tan^{2}({\theta})-\sin^{2}({\theta})$, we have

Using again the assumption $r/R<1$, we obtain

Since $r/\cos(\theta)=\|\boldsymbol{u}\|_{2}$, one can rewrite it as

We now use the previous lemma to bound the semi-random robustness of the classifier, i.e. $\|\boldsymbol{r}_{\mathcal{S}}^{k}\|_{2}$, to the worst-case robustness $\|\boldsymbol{r}^{k}\|_{2}$ in the case where the curvature is sufficiently small.

with probability larger than $1-4\delta$. The constants can be taken $C=0.2,C_{1}=0.625,C_{2}=2.25$.

Observe that the worst-case perturbation along any subspace $\mathcal{S}$ that reaches the ball $\mathcal{B}$ is larger than the perturbation along $\mathcal{S}$ that reaches the region $\mathcal{R}_{k}$, as $\mathcal{B}\subseteq\mathcal{R}_{k}$. Therefore, any upper bound derived when the boundary is the sphere of radius $1/\kappa$; i.e., $\mathscr{B}_{k}=\partial\mathcal{B}$ is also a valid upper bound for boundary $\mathscr{B}_{k}$ (see Fig. 9 (a)). It is therefore sufficient to derive an upper bound in the worst case scenario where the boundary $\mathscr{B}_{k}=\partial\mathcal{B}$, and we consider this case for the remainder of the proof of the upper bound.

We now consider the linear classifier whose boundary is tangent to $\mathscr{B}_{k}$ at $\boldsymbol{x}^{*}$. For the random subspace $\mathcal{S}$, we denote by $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{T}}$ the worst-case subspace perturbation for this linear classifier. We then focus on the intersection between the boundary $\mathscr{B}_{k}$ and the two-dimensional plane $\mathcal{U}$ spanned by the vectors $\boldsymbol{r}^{k}$ and $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{T}}$. This normal section of the boundary cuts the ball $\mathcal{B}$ through its center as the tangent spaces of the decision boundary and the ball coincide. See Fig. 9 for a clarifying figure of this two-dimensional cross-section. We define the angle $\hat{\theta}$ as denoted in Fig. 9, such that $\cos(\hat{\theta})=\frac{\|\boldsymbol{r}^{k}\|_{2}}{\|\boldsymbol{r}^{\mathcal{T}}_{\mathcal{S}}\|_{2}}$.

We apply our result on linear classifiers in Theorem 1 for the tangent classifier. We have

with probability exceeding $1-2\delta$. Hence, using $\tan^{2}(\hat{\theta})\leq(\cos^{2}(\hat{\theta}))^{-1}$ and the assumption of the theorem, we deduce that

with probability exceeding $1-2\delta$. Note moreover that

Hence, the assumptions of Lemma 4 hold with probability larger than $1-2\delta$. Using the notations of Fig. 9, we therefore obtain from Lemma 4

with probability larger than $1-2\delta$.

Observe that $\|\boldsymbol{x}_{\gamma}-\boldsymbol{x}_{0}\|_{2}\geq\|\boldsymbol{r}_{\mathcal{S}}^{k}\|_{2}$, and that $\tan^{2}(\hat{\theta})\leq\frac{\|\boldsymbol{r}_{\mathcal{S}}^{T}\|_{2}^{2}}{\|\boldsymbol{r}^{k}\|_{2}^{2}}$. Hence, we obtain by re-writing Eq. (54)

Using the inequality in Eq. (53), we obtain

which concludes the proof of the upper bound. ∎

We now consider the ball $\mathcal{B}^{\prime}$ of center $\boldsymbol{z}^{*}$ and radius $1/\kappa=\|\boldsymbol{z}^{*}-\boldsymbol{x}^{*}\|_{2}$ that is included in the region $\mathcal{R}_{\hat{k}(\boldsymbol{x}_{0})}$. Since the ball $\mathcal{B}^{\prime}$ is, by definition, included in the region $\mathcal{R}_{\hat{k}(\boldsymbol{x}_{0})}$, the worst-case scenario for the lower bound on $\|\boldsymbol{r}_{\mathcal{S}}^{k}\|_{2}$ occurs whenever the decision boundary $\mathscr{B}_{k}$ coincides with the ball $\mathcal{B}^{\prime}$ (see Fig. 10 (a)). We consider this case in the remainder of the proof.

To derive the lower bound, we consider the cross-section $\mathcal{U}^{\prime}$ spanned by the vectors $\boldsymbol{r}_{\mathcal{S}}^{k}$ and $\boldsymbol{r}^{k}$ (Fig. 10 (b)). We have $\|\boldsymbol{r}^{k}\|_{2}\kappa<1$; using the lower bound of Lemma 4, we obtain

for any $\mathcal{S}$. Observe moreover that

Let $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{T}}$ denote the worst-case perturbation belonging to subspace $\mathcal{S}$ for the linear classifier $\mathcal{T}_{x^{*}}\mathscr{B}_{k}$. It is not hard to see that $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{T}}$ is collinear to $\boldsymbol{r}_{\mathcal{S}}^{k}$ (see Lemma 6 for a proof). Hence, we have $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{T}}=\boldsymbol{x}_{\mathcal{T}}-\boldsymbol{x}_{0}$. By applying our result on linear classifiers in Theorem 1 for the tangent classifier $\mathcal{T}_{x^{*}}\mathscr{B}_{k}$, we have:

which concludes the proof of the lower bound.

The goal is now to extend the previous result, derived for binary classifiers, to the multiclass classification case. To do so, we show the following lemma.

Let $p=\arg\min_{i}\|\boldsymbol{r}^{i}\|_{2}$. Define the deterministic set

Assume that, for all $k\in A^{c}$, we have

The first probability can be bounded as follows:

The second probability can also be bounded in the following way

Observe that, for $k\in A$, we have $\|\boldsymbol{r}_{\mathcal{S}}^{k}\|_{2}\geq\|\boldsymbol{r}^{k}\|_{2}\geq 1.45\sqrt{\zeta_{2}(m,\delta)}\sqrt{\frac{d}{m}}\|\boldsymbol{r}^{*}\|_{2}$. Hence, we conclude that

with probability larger than $1-4(L+2)\delta$.

Using Theorem 2, we have that for all $k\notin A$, the result in Eq. (52) holds. We simplify the result with the assumption $\kappa(\mathscr{B}_{k})\|\boldsymbol{r}\|_{2}\leq\frac{0.2}{\zeta_{2}(m,\delta)}\frac{m}{d}$. Hence, the bounds of Theorem 2 are given as follows

By using Lemma 5, together with the fact that $t=\delta$, we obtain

A.3 Useful results

Assuming the center of the ball $\mathcal{B}$ is the origin, the points on the sphere $\partial\mathcal{B}$ satisfy equation: $\|\boldsymbol{x}\|_{2}=R$, where $R$ denotes the radius. Hence, the perturbation $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{B}}$ is given by

By equating the gradient of Lagrangian of the above constrained optimization problem to zero, we obtain the following necessary optimality condition

from which we conclude that $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{B}}$ is collinear to $\mathbf{P}_{\mathcal{S}}\boldsymbol{x}_{0}$.

It should further be noted that $\boldsymbol{r}_{\mathcal{S}}^{\mathcal{T}}$ can be computed in closed form, and is collinear to $\mathbf{P}_{\mathcal{S}}(\boldsymbol{x}^{*}-\boldsymbol{x}_{0})$, which is itself collinear to $\boldsymbol{x}_{0}$, as the the center of the ball was assumed to be the origin. This concludes the proof. ∎