Towards Large Certified Radius in Randomized Smoothing using
Quasiconcave Optimization

As mentioned earlier, several existing methods attempt to address the truncation effect. Some focus on training the base model to enlarge certified radii, while others use a different Gaussian kernel $\mathcal{G}(\sigma)$ for each image to construct $g$. We follow the later approach and propose an input-specific algorithm that finds the optimal $\mathcal{G}$ for most data points. Intuitively, for a data point $x$ of class $c_{A}$, if most neighboring points belong to the same class $c_{A}$, we can use $\mathcal{G}$ with a larger variance to convolute the data space of $f$. In contrast, if the neighborhood is full of different class samples, $\mathcal{G}$ needs a small variance to prevent misclassification. The proposed method draws inspiration from this concept and aims to optimize the selection of $\mathcal{G}(\sigma)$. Below, we will discuss some input-specific search algorithms that have been utilized in prior works. These algorithms contribute to the development of our approach.

DDRS (Alfarra et al. 2022) assumes that sigma-radius curves, $R(\sigma)=\sigma\cdot\Phi^{-1}(\underline{p_{A}}(\sigma))$, are concave and use gradient-based convex optimization along with some relaxation and approximation to find the optimal $\sigma$ value. However, in our experiments, almost all sigma-radius curves are not concave. We select $200$ images from CIFAR-10 dataset and compute the certified radii with respect to $\sigma$ for each image. Among these $200$ images, as least $189$ images do not satisfy concavity. Thus, the gradient-based convex optimization method may not work well in this task. Instead of depending on the assumption of concavity, Insta-RS (Chen et al. 2021) uses a multi-start searching algorithm to optimize $\sigma$. However, the multi-start procedure incurs high computational overhead. In our work, we observe an intriguing quasiconcave property on the sigma-radius curves, which helps us develop an effective and efficient algorithm to optimize sigma. In order to assess the generality of the quasiconcave property, we conducted evaluations on two datasets and four distinct models. Table 1 illustrates the generality of concavity and quasiconcavity of the sigma-radius curves. The table demonstrates that quasiconcavity is significantly more prevalent than concavity in real-world datasets. We will delve deeper into this table in Subsection 4.3.

This section lists the definition and two fundamental lemmas about quasiconcavity that will be used in designing our QCRS method. Quasiconcavity is a generalization of concavity, defined as follows:

In this paper, we mainly use strict quasiconcavity. Below, we list lemmas on strict quasiconcavity that we will use later.

We defer the proofs of these two lemmas to Appendix D.

In this section, we show quasiconcavity related to sigma-radius curves, i.e., $R(\sigma)$. First, we differentiate $R(\sigma)$:

Assume that $\sigma^{*}$ exists, where $\sigma^{*}=\text{arg max}_{\sigma}R(\sigma)$. Then, according to Lemma 2, strict quasiconcavity is established if the gradient $\nabla_{\sigma}\Phi^{-1}$ adheres to the subsequent upper and lower bounds:

Intuitively, it indicates that $\nabla_{\sigma}\Phi^{-1}$ has a negative lower bound when $\sigma<\sigma^{*}$ and a negative upper bound when $\sigma>\sigma^{*}$.

The computation of a classifier’s decision boundary is proven to be NP-hard, rendering the calculation of $\nabla_{\sigma}\Phi^{-1}$ impractical (Katz et al. 2017). Randomized smoothing employs a series of probabilistic approaches, such as MC sampling, to address this issue. Similarly, instead of evaluating $\nabla_{\sigma}\Phi^{-1}$, we define a probabilistic condition based on Lemma 2 to determine quasiconcavity of $R(\sigma)$:

Intuitively, if $\upsilon^{-}=\upsilon^{+}=1$, the condition states that the slope of the sigma-radius curve is positive on the left side of the optimal solution and negative on the right side. Note that this condition is weaker and more general than the concentration assumption used in (Li et al. 2022), which requires additional assumptions on the distribution of data points. It is also weaker than the concavity assumption used in DDRS (Alfarra et al. 2022). Since the ($\upsilon^{-},\upsilon^{+}$)-SQC condition is weak, we expect that more data points would satisfy this assumption. Thus, we conduct some experiments on CIFAR-10 and ImageNet, which are detailed in Appendix B. For each data point in CIFAR-10 and ImageNet, we first employ grid search to determine the optimal sigma $\sigma^{*}$. Subsequently, we uniformly sample 20 distinct sigma values and evaluate the ($\upsilon^{-},\upsilon^{+}$)-SQC condition. In terms of concavity, we evaluate the Hessian of these 20 points. The results are illustrated in Table 1. Taking the model with $\sigma=.25$ on CIFAR=10 as an example, we derive the following conclusions: 1) There are at most $98.17\%$ data points satisfy the ($1,1$)-SQC condition, while only a maximum of $6.7\%$ satisfy the concavity assumption; 2) Among these $98.17\%$ data points, their $\upsilon^{-}$ and $\upsilon^{+}$ are both within the interval $[0.8609,1]$ using $95\%$ confidence level, determined by the Clopper-Pearson interval. That is, these data points at least satisfy ($0.86,0.86$)-SQC condition. Notably, in our experiment, the mean values of $\upsilon^{-}$ and $\upsilon^{+}$ are greater than $0.99$; 3) If we set $\upsilon^{-}$ and $\upsilon^{+}$ to $0.99$, we can expect that $95\%$ of data points will achieve the optimal sigma, as the proposed method requires five iterations to converge ($0.99^{5}\approx 0.95$). We will discuss the convergence in the next section.

We assume that a data point satisfies ($\upsilon^{-},\upsilon^{+}$)-SQC condition, with the corresponding $\upsilon^{-}$ and $\upsilon^{+}$ being close to one. According to Lemma 2, if we detect that the gradient of a point is positive, we can assert that the unique optimal sigma is on its right hand side. Based on these rules, we design a time-efficient algorithm that can achieve optimal $\sigma$, shown in Algorithm 1. Algorithm 1 finds the optimal sigma efficiently based on binary search, and the sigma is the globally optimal solution, as demonstrated by Lemma 1. On the other hand, the sigma values within the non-certified interval $\{\sigma|R(\sigma)=0\}$ must not be the solution. The gradients $\nabla R(\sigma)$ are likely to be zero in the interval because the curve is a horizontal line with $R(\sigma)=0$ there. This leads to a gradient vanishing issue in Algorithm 1. To circumvent this issue, we utilize momentum $M$ to guide the optimization direction. Algorithm 1 guarantees to find the same optimal solution as grid search if the curve satisfies ($1,1$)-SQC condition. The time complexity is $N$ for grid search and $\log N$ for Algorithm 1, where $N$ is the number of points on the grid. Therefore, the proposed method is significantly faster than grid search, while both of them can achieve the same optimal $\sigma$.

Prior work utilizes backpropagation to compute gradients, which is time-consuming, and the computed gradient is unstable due to MC sampling. Therefore, we use forward passes to compute gradient, which takes the difference of two neighboring points. This is because we only care about the gradient sign rather than the exact value. On the last stage of Algorithm 1, we employ a rejection policy that compares the resulting $\sigma$ to the original $\sigma$ and returns the larger one.

The proposed method is time-efficient compared to Insta-RS (Chen et al. 2021) and DDRS (Alfarra et al. 2022). DDRS uses a low MC sampling number (one or eight) due to expansive computation and may obtain unstable gradients. To verify this, we analyze the value of gradient under different MC sampling number. The detailed results can be found in the Appendix H. The results reveal that the gradient values vary dramatically when using low MC sampling numbers. Thus, a low MC sampling number can not accurately estimate gradients, which would affect the gradient-based optimization. However, the proposed QCRS only uses the gradient sign, which is more stable than the gradient value. We observe that the sign of the gradient is consistent and hardly changes when the MC sampling number exceeds $500$.

The proposed QCRS enjoys a convergence guarantee with the convergence rate analyzed below.

Theorem 1 means the convergence rate of Algorithm 1 is $\mathcal{O}((\frac{1}{2})^{t})$. We defer the proof to Appendix D.

On the other hand, gradient-descent-based method requires much stricter assumptions, such as L-smoothness and $\mu$-strongly concavity, to guarantee convergence. When these conditions are satisfied, the convergence rate is as below (Nesterov 2018):

The convergence rate is $\mathcal{O}((\frac{L-\mu}{L+\mu})^{t})$, where $L$ and $\mu$ depend on the data points. Note that only a maximum of $6.7\%$ of data points satisfy the concavity assumption empirically, and even fewer data points satisfy L-smoothness and $\mu$-strongly concavity simultaneously. Thus, some concave optimization methods cannot converge to the optimal sigma values for most data points.

Fig. 2 compares the radius-accuracy curves for different methods on the CIFAR-10 dataset. In the figure, we also show the corresponding ACR, which is the area under the radius-accuracy curve. Table 2 presents the ACR of different methods and their runtime cost. The proposed QCRS outperforms the original randomized smoothing method (Cohen, Rosenfeld, and Kolter 2019) by significant margins: $48\%$, $18\%$, and $22\%$ for the models trained with $\sigma=\{0.12,0.25,0.50\}$, respectively. The main performance gain comes from reducing the truncation effect (the waterfall effect) on the radius-accuracy curve. We also compare QCRS to grid search. Since grid search is extremely computationally expensive, we only test the images with $id=0,50,100,...,9950$ in CIFAR-10. Despite using 24 points in the grid search, which costs approximately $24$ times more in runtime than QCRS, QCRS still outperforms grid search. This is due to QCRS being more time-efficient, which enables a broader and more accurate search region compared to grid search. Furthermore, QCRS guarantees to achieve the same optimal as grid search if the ($1,1$)-SQC condition holds. Regarding the computational cost, the proposed method only takes about $7\%$ additional inference time compared to the original Cohen method, as shown in Table 2.

We also compare the proposed QCRS with two state-of-the-art randomized smoothing methods, DSRS (Li et al. 2022) and DDRS (Alfarra et al. 2022). We follow their setting to evaluate the proposed method on CIFAR-10 for fair comparisons, and defer other minor comparisons and analyses to Appendix C. As Table 3 shows, for the certified accuracy under radius at $0.5$, DSRS and DDRS improve Cohen by $2.4\%$ and $7.3\%$, respectively. On the other hand, the proposed QCRS improves Cohen by $31.7\%$. Therefore, among the methods that boost certified radii, QCRS improves Cohen most effectively.

Fig. 3 shows the results on ImageNet. Following Cohen, only $500$ images with $id=0,100,200,...,49900$ in the validation set were used. We avoided using the $\sigma=1.0$ model as (Mohapatra et al. 2021) revealed that a large $\sigma$ leads to serious fairness concerns, necessitating a restriction on $\sigma$ in randomized smoothing. Additionally, we observed the similar fairness issue in (Mohapatra et al. 2021), to be discussed later. For the model with $\sigma=.25$, the proposed method improves ACR from $0.477$ to $0.541$, roughly $13.4\%$. Similarly, for the model with $\sigma=.50$, the proposed method improves ACR from $0.733$ to $0.805$, roughly $9.8\%$. In addition, the proposed method overcomes the truncation effect, providing a larger certified radius than Cohen. As for the grid search, similar to CIFAR-10, it is computationally expensive, so we set the number of searching points to be $11$ on ImageNet. As mentioned earlier, although the grid search can provide the optimal certified radius if the cost does not matter, its searching region and precision are limited in practical application. That is why the proposed method achieves a slightly superior ACR than the brute-force grid search method in Fig. 3, while the runtime is roughly 11 times faster than it.

The proposed method focuses on enhancing randomized smoothing while building the smoothed classifier. Thus, it is orthogonal to the approach that aims to boost certified radii during training stage. QCRS can incorporate with training-based methods. The most representative training-based method to enhance certified radius is MACER. We apply the proposed method to the models trained by MACER and observe significant improvement in terms of the certified radius. Fig. 4 illustrates the results of radius-accuracy curves, and Table 4 shows the detailed comparison. As Table 4 shows, for the model trained by $\sigma=.25$, Cohen achieves $0.423$ ACR, and MACER enhances this ACR to $0.518$, roughly $22.5\%$. Next, our proposed QCRS improves MACER ACR from $0.518$ to $0.715$, roughly $38\%$. Thus, QCRS and MACER together can significantly boost the original Cohen’s RS roughly $69\%$. Similarly, for the model trained by $\sigma=.50$, QCRS and MACER enhance Cohen’s RS from $0.534$ to $0.786$, approximately $+47.2\%$. Furthermore, Table 4 also includes the results of DDRS incorporating MACER. It can be observed that MACER has a positive impact on the performance of the inference-phase randomized smoothing methods. Among the methods evaluated, QCRS incorporating MACER achieves the state-of-the-art performance. On the other hand, QCRS and MACER improves Cohen to $0.512$ and $0.518$, respectively. That is, QCRS can enlarge the certified radius to the extent that MACER does, but it does not need any training procedure. As datasets become larger and larger today, re-training may be computationally prohibited. Thus, QCRS benefits from its efficient workflow that enlarges the certified radius with negligible cost.

We briefly analyze the computational cost compared to Cohen. The sigma searching region of Algorithm 1 is $0.5-0.12=0.38$. Because the convergence rate of Algorithm 1 is $\frac{\sigma_{max}-\sigma_{min}}{2^{t}}\geq|\sigma_{t}-\sigma^{*}|$, if $t\geq 6$, we can achieve $0.006$-optimal, i.e., $|\sigma-\sigma^{*}|<0.006$. As for the gradient computation, it requires $1,000$ forward propagations for each iteration. Thus, we roughly require additional $6,000$ forward propagations for each data point to achieve the optimal sigma value. The standard RS needs $100,000$ forward propagations, so the overhead of the proposed QCRS is approximately $6\%$. Empirically, we observe an approximately $7\%$ overhead as Table 2 illustrates.

We compare the computational cost of QCRS with those of DDRS (Alfarra et al. 2022), DSRS (Li et al. 2022), and Insta-RS (Chen et al. 2021). The DDRS method adopts the radius as its objective function and utilizes gradient descent to directly optimize the radius. This approach involves computing the gradient of the radius multiple times to update the sigma value, which requires performing multiple back propagations. As shown in Table 2, certifying an image using DDRS takes roughly $7.39$ seconds. This incurs an overhead of $14\%$, which is twice as high as the proposed QCRS method. As for DSRS, in our experiments, it incurs roughly $100\%$ overhead compared to Cohen. Finally, Insta-RS employs multi-start gradient descent, so its computational cost is the highest among the methods considered in this paper.

A consistent sigma may be required during deployment, presenting a limitation for input-specific RS. The memory bank strategy proposed by DDRS (Alfarra et al. 2022), compatible with our QCRS, can address this issue. It is crucial to understand QCRS still can apply a consistent sigma during deployment, and it does not undermine the soundness of certification, though it may limit its practical utility in real-world scenarios. Specifically, in binary scenarios, the proposed method enables the customization of an optimal sigma for specific classes, thereby effectively enhancing their certified radii. For further details, please see Appendix J.

As discussed in (Mohapatra et al. 2021), randomized smoothing suffers from fairness issue. The unbounded class in the data space dominates as $\sigma$ increases. We investigate the optimal $\sigma$ for each class in CIFAR-10. As Table 5 illustrates, class “cars” exhibits a larger optimal sigma value compared to the other classes. This discrepancy arises from the possibility that “cars” represents the unbounded class; thus, an increase in the sigma value leads to a continuous expansion of the radius. Exploring potential solutions to address this issue remains an intriguing direction.