Figure 1 - Landscape of $f^y$ for a region around an input point in a 2D toy dataset (blue corresponds to higher confidence in the true class), as well as the boundaries of the optimized isotropic and anisotropic certificates for $l_1$ (a and b) and $l_2$ (c and d) norm.
Randomized smoothing has recently emerged as a scalable technique for obtaining provably robust classifiers. It achieves this by taking a base classifier $f$ and building a smooth classifier $g$ defined as $g(x)=\text{argmax}i\: \mathbb{P}{\epsilon\sim \mathcal{D}}[f(x+\epsilon)=i]$ for a distribution $\mathcal{D}$, which is then guaranteed to satisfy $g(x)=g(x+\delta), \forall \delta \in \mathcal{R}$ where $\mathcal{R}$ is a certification region that depends on $f$, $x$ and $\mathcal{D}$. For example, if $\mathcal{D} = \mathcal{N}(0, \sigma^2 I)$ Cohen et al. in [1] showed that $\mathcal{R}$ is an $\ell_2$-ball whose radius is determined by $f$, $x$ and $\sigma$.
While previous works have extended these results to other $\ell_p$-norm regions by studying different smoothing distributions [2], they have focused on smoothing and certifying regions that are isotropic nature, i.e. regions that display full radial norm-symmetry with respect to the input point. But the following question arises:
Should we care about obtaining anisotropic certificates?
The first consideration to have in mind is that the goal of certification approaches is to find the largest safe region $\mathcal{R}$ around a sample input $x$ such that, given its true label $y$, $y = \text{argmax}_i\: f^i(x) = \text{argmax}_i\: f^i(x + \delta), \, \forall \delta \in \mathcal{R}$. While most previous works within the randomized smoothing literature have focused on the smoothing aspect by using a fixed distribution, recent randomized smoothing approaches have explored this idea of largest safe region around each input by explicitly optimizing the certified $\ell_p$-ball around said input [3].
Notice that even optimal isotropic $\ell_p$ certificates are worst-case with respect to that $\ell_p$-norm, as they avoid adversary regions by limiting the certified regions to the closest $\ell_p$ adversaries. This means such approaches can only enjoy radii that are at most the distance to the closest decision boundaries. However, decision boundaries of general classifiers are complex, non-linear, and non-radially distributed with respect to a generic input sample [4]. This is evidenced by the fact that, within a reasonably small $\ell_p$-ball around an input, there are often only a small set of adversary directions [5, 6]. For further intuition on this, take as an example the decision boundaries in Figure 1.
As such, while $\ell_p$-norm certificates are useful and important to reason about worst-case performance, they:
Figure 2 shows two conceptual examples of optimal isotropic certificates. While the one on top can be considered useful due to the fact that it borders a large adversary region which is reflected in the certified region, the degenerate example at the bottom illustrates the problem with the worst-case nature of $\ell_p$ certificates. The small optimal isotropic region is not informative in terms of the safe regions around the input, since it provides an underestimation of the safe regions around the input due to the peak corresponding to another class.
Figure 2 - Conceptual examples; (top) a case where the optimal worst-case isotropic certificate borders the decision boundary of the classifier. (bottom) a degenerate case in which the isotropic certificate is uninformative as most of the region around the input is safe with the exception of a small peak corresponding to another class.
To illustrate these ideas, consider the decision boundaries of a base classifier $f$ trained on a toy 2-dimensional, radially separable (with respect to the origin) binary classification dataset, and two different input test samples $x$ and labels $y$ (see Figure 1). Figures 1 (a) and 1 (b) compare an isotropic cross-polytope (of the form $\|\delta\|_1 \leq r$) with an anisotropic generalized cross-polytope (of the form $\|\mathbf{A}\delta\|_1 \leq r$), while Figures 1 (c) and 1 (d) compare an isotropic $\ell_2$-ball (of the form $\|\delta\|_2 \leq r$) with an anisotropic ellipsoid (of the form $\|\mathbf{A}\delta\|_2 \leq r$). It should be noted that the regions presented in these and the following figures were obtained by running optimization procedures that maximize the area of each of the regions, and can thus be considered optimal.
Notice that in Figures 1 (a) and 1 (c), due to the curvature of the classification boundary (shown in white), the optimal certification region is isotropic in nature, which is evidenced by the similarities of the optimal isotropic and anisotropic certificates. On the other hand, in Figures 1 (b) and 1 (d), the location of the decision boundary allows for the anisotropic certified regions to be considerably larger than their isotropic counterparts, as they are not as constrained by the closest decision boundary, i.e. the worst-case performance.
This is further highlighted in higher dimensions, as shown in Figure 3 in which a CIFAR10 dataset point is considered (image with size $32\times 32\times 3$). To perform the 2D analysis presented in the figure, and following [7], we compute the Hessian of $f^y$ with respect to $x$, where $y$ is the true label for $x$ s.t. $y = \text{argmax}_i f^i(x)$. In addition to the Hessian, we compute its eigenvector decomposition, yielding the eigenvectors $\{ν_i\}, \, i\in\{1,\dots,3072\}$ ordered in descending order of the absolute value of the respective eigenvalues.
Figure 3 - Illustration of the landscape of $f^y$ for points around an input point $x$, and two projections of optimized isotropic and anisotropic $\ell_2$ certified regions on a CIFAR-10 dataset example to a subset of two eigenvectors of the Hessian of $f^y$ (blue regions correspond to a higher confidence in $y$).
Figure 3 (a) shows the projection of the landscape of $f^y$ in the highest curvature directions, i.e. $\nu_1$ and $\nu_2$. Note that the isotropic certification, much as in Figure 1 (c), in these 2 dimensions is nearly optimal when compared to the anisotropic region. However, if one takes the same projection with respect to the eigenvectors with the lowest and highest eigenvalues, i.e. $\nu_1$ and $\nu_{3072}$, the advantages of the anisotropic certification become clear as shown in Figure 3 (b).
Figure 4 - CIFAR-10 examples (top) and practically indistinguishable changes to those examples (bottom) that are not inside the optimized isotropic certified region, but are covered by the optimized anisotropic one.
As observed from the previous examples, anisotropic certification reasons more closely about the shape of the decision boundaries, allowing for further insights into constant prediction (safe) directions. Figure 4 presents a series of test set images $x$, as well as practically indistinguishable $x + \delta$ images which are not inside the optimal certified isotropic $\ell_2$-balls for each input sample, yet, are within the anisotropic certified regions.
Figure 5 - CIFAR-10 examples (top) and $\ell_2$ optimized isotropic (middle) and anisotropic (bottom) parameters that define the certified regions.
Anisotropic certification allows us to extract other insights from the safe regions too. For example, in the anisotropic ellipsoid case the directions aligned with the major axes of the ellipsoid $\|\mathbf{A}\delta\|_2 = r$ (i.e., locations where $\mathbf{A}^{-1}$ is large) are, by definition, expected to be less sensitive to perturbations compared to the minor axes directions. To visualize this concept, Figure 5 shows CIFAR-10 images (top) along with their corresponding optimal isotropic (middle) and anisotropic (bottom) parameters. Note the richness of information provided by the anisotropic parameters when compared to the $\ell_2$ worst-case, isotropic ones. Interestingly, pixel locations where the intensity of $\mathbf{A}^{-1}$ is large (higher intensity in Figure 5) are generally the ones corresponding least with the underlying true class and overlapping more with background pixels.