Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper addresses the problem of designing local robustness certification procedures for neural classifiers. The primary insight of the paper is that given an input x, instead of simply calculating the radius of the robust ball B centered at x, one should also consider calculating robustness radii at other points in the ball B. It is easy to see that the network is robust in the entire region defined by the union of B and the robust balls centered at these additional points. Moreover, if such additional points are suitably chosen, one can achieve a larger robustness radius at x.
The paper, in particular, focuses on local robustness certification via Randomized Smoothing. In order to choose suitable additional points for robustness certification, the authors formulate optimization problems for choosing up to two additional points to certify. These optimization problems are solved at inference time to choose the additional points to certify. Since the robustness radius calculation used by Randomized Smoothing requires computing expectations, special care is needed when solving these optimization problems via gradient descent. The paper presents two different approaches for solving the optimization problem so that the required gradients can be calculated.
Empirical evaluation is performed using MNIST, CIFAR-10, and Tiny-Imagenet datasets. The evaluation suggests that the proposed technique is indeed able to produce larger certifiable balls and improve upon the certified accuracy of randomized smoothing.
strengths_and_weaknesses: Strengths of the paper:
(1) The proposed idea to increase the size of the certified balls is original yet intuitive. Its a broadly applicable idea that can be applied to other local robustness certification procedures, apart from Randomized Smoothing.

(2) The empirical results provide compelling evidence that the idea could lead to certification gains in practice.

Weaknesses of the paper:
Though I really like the idea presented in the paper, the presentation and quality of writing in the paper needs significant improvement before the paper can be published. I list my main concerns below:

(1) The mathematical writing in the paper is very hard to follow. Often, the symbols are either not defined or not used in a careful manner. I could barely follow Sections 3.2 and 3.3. Though I believe I have a sense of what the authors are trying to say, the actual technical definitions and proofs were not helpful in understanding the material. For instance, consider Defn 3.3. I have no idea what its trying to say. What are s and r' there? Is s a vector quantity? If yes, then the rightmost term in Equation 6 involves a multiplication of two vector quantities. Is it supposed to be a dot product of two vectors? What is s anyway? Why is it of dimension R^(d-1) when the inputs are of dimension d? Line 128 says, "assuming the above definition is true". What does this mean? How can a definition be false? Does Defn 3.3 need to be a theorem instead? Similarly, consider the proof of Lemma 3.4. What are y_2 and y_3? What is k in equation (8)? I couldn't follow the proof at all and have no idea if Lemma 3.4 is indeed true or not.

(2) Related to the above point, even the descriptions of the mathematical statements are hard to follow. For instance, consider the first two paras of Section 3.3. Even after reading them multiple times, I was not able to figure what the authors were trying to say. My understanding is that the boundary treatments can sometimes allow larger robustness radius because the closest point on the red circle (referring to Figure 1) is outside the feasible bounded region, so one can consider points on the red circle that are farther away as being closest to the test input. However, the text in Section 3.3 did not help me in figuring this out. It would be very helpful, for instance, to explain the situation using the already existing Figure 1.

(4) Algorithm 1 needs to be more carefully written. Where are the input parameters c, \lambda, \Gamma used? Is Algorithm 2 called on line 3? Why not write it as Algorithm2(x',N,\sigma) instead of Model(x + ....)? In fact, writing it as Model(x + ....) is incorrect since line 3 is not executing the model at a particular input but instead executing Algorithm 2. There is no description of how step size \gamma is calculated on line 9 even though a paper is cited. And what is the justification for line 11? It would help to have a more detailed description of Algorithm 1 in Section 3.4.

(5) The presentation of the empirical results is also quite confusing. Although a lot of detail is provided, important high-level details are missing. For instance, I was not able to figure out how to interpret Figure 3. What does the x-axis show? What does Figure 5 report? Percentage Improvement in what quantity? Is it reporting percentage improvement in "certified proportion"? Also, why is y-axis of Figure 2 labeled "certified proportion"? Cohen et al. call it "certified accuracy" which is a much more informative name. If Figure 5 is indeed reporting median percentage improvement in certified accuracy, at what radius is the certified accuracy being calculated?

===============================  
Post one round of rebuttal:  
Changed *Contribution* from 3 to 4  
Changed *Rating* from 3 to 4 
  
Post second round of rebuttal:  
Changed *Presentation* from 1 to 2  
Changed *Rating* from 4 to 6 
questions: Apart from the questions above, below are some more questions and comments:
(1) Line 72,73 says that the certified radius formula (Equation 3) of Cohen at al. gives a lower bound on the certified radius. On the other hand, lines 36, 91, 95 etc state that this is the largest certifiable radius. Is it a lower bound or a tight bound? I believe its the latter but please provide clarification

(2) Line 75: runner -> runner-up

(3) Line 79: binomial -> binary?

(4) Defn 3.1 seems incomplete. First, what is the definition of B_P(x1,r1), B_P(x2,r2)? Second, is it not the case that x1 and x2 have to be in each other's certifiable regions for the definition to make sense? To me, it seems like Defn 3.1 is not really a definition, but it needs to be a theorem with a proof.

(5) Line 114: recast the certification problem -> recast the certification radius

(6) Line 123: r_n seems overloaded since its already used to denote the certified radius for point x_n. Should r_n instead be r''' or something?

(7) Line 122 and Defn 3.3: Questions about the meaning of S_n, s, and various questions about Defn 3.3 are mentioned above under "weaknesses of the paper".

(8) Proof of Lemma 3.4: Questions about the proof are mentioned under "weaknesses of the paper".

(9) Line 151: Why was the notation switched from r1 to L1?

(10) Line 164: x_n is defined as {x_1,n, x_2,n, ...}. On the other hand, in Equation (8), in y_2,j y_3,j, the j'th coordinate of points y2 and y3 are being referred. Please make the subscript order consistent.

(11) Questions about Algorithm 1 have already been mentioned earlier

(12) Equation 14: i should be replaced by k

(13) Equation 15: All the i's need to be replaced by k

(14) Line 225: How does increase in R affect the value of E1? Isn't E1 independent of R?

(15) Questions about Figure 2, 3, and 5 have already been mentioned earlier.

(16) In Table 1 reporting the average amount of time required for certifying a single input? How many samples are drawn while reporting the results for Cohen et al.? Is it the same number of samples as for the other approaches, i.e., 1000 samples?

(17) Cohen at al. already introduces significant overheads (due to sampling and evaluating the model on thousands of inputs). Would it not be a problem to add their overheads by one to two orders of magnitude as shown in Table 1?
limitations: The authors describe some limitations of their approach in Section 5 under the para labeled "Limitations". It would be nice to have some more discussion about the overheads introduced by the approach.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes to exploit the certified robustness of samples in the neighbourhood of a given data in order to enhance the certifiable radius of the given data. To be specific, the authors leverage the intersection of the certified regions of multiple neighbourhoods. Compared to the previous state-of-the-art method, the experimental results validate the effectiveness of the proposed method in enhancing certified robustness.
strengths_and_weaknesses: Strengths
+ The proposed method is interesting and novel. The method is (arguably) supported by theoretical analyses.
+ The authors conduct comprehensive experiments. The results on various datasets, different hyperparameters, and different transitivity approaches all support the claim that the proposed method can improve certified robustness.

Weaknesses
- It seems that the proposed method could be somewhat more time-consuming compared to previous state-of-theart method.


questions: - Could the authors provide any insights on how to accelerate the proposed method?
- I am a bit confused about the meaning of some part of the title — ‘Double Bubble, Toil and Trouble’. Could the authors provide some explanations about this part?

limitations: The authors have pointed out the limitations in details in the main paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper presents geometrically-informed certified robustness to improve the certified radii computed by randomized smoothing techniques. The paper presents three approaches for geometrically-informed certified robustness: transitivity, multiple (double) transitivity, and boundary treatment. The evaluation shows that the proposed approaches equipped with two optimization algorithms can outperform the baseline.
strengths_and_weaknesses: Overall, it is a paper with a novel and effective idea but needs improvement in writing. 

Strength:
The paper presents geometrically-informed certified robustness to improve the certified radii computed by randomized smoothing techniques. The paper identifies a hard problem and proposes simple yet effective approaches to tackle the problem. I like the idea of geometrically-informed certified robustness because the bound computed by randomized smoothing techniques is tight under assumptions that they over-approximated the worst-case behavior of the machine learning classifier **only** with respect to the constraints of E0[x] and E1[x]. In other words, other approaches ignore the underlying classifier's complex behavior (geometry). However, this paper uses additional information by choosing $x'$ with $E0[x']$ and $E1[x']$, i.e., the geometry around $x'$ to improve the certification. Ideally, if we choose a finite set of $x'$, we could approximate the geometry around $x$, yet this approximation is expensive and requires exponential computation.  

Weakness:
- The writing in sections 3 and 4 should be greatly improved:
  1. I appreciate that the paper provides three figures for illustration. However, it is important to clarify these circles, i.e., mark out x1, x2, x3. It would be better to show the computation of these 2D examples.
  2. Define notation before usage and the inconsistency in notations:
    * $r_2(x_2)$ in Eq 5; 
    * $x_3(s)$, $s$, and $r'$ in Eq 6; 
    * $j$ and $k$ in Eq 8 (Here, $j$ should be $\forall j$ and $k$ is a special dimension); 
    * $\hat{r_k}$ in Eq 13. What are $x_3', r_3'$ in definition 3.3? 
    * The notation of $y_{2,k}$ appears in the proof of Lemma 3.4, yet the definition appears later in the proof of Lemma 3.5. Moreover, the definition later of $x_n$ is wrong, should be $\{x_{n,1}, \ldots, x_{n,d}\}$. 
    * At the beginning of the proof of Lemma 3.5 until Eq 12, $x_i$ should be $z_i$.
    * $c$, $\lambda$, $\Gamma$ are not used in Algorithm 1.
    * $i$ should be $k$ in the second line of Eq 15.
  3. State the intuition of Eq 6. Maybe say x_1, x_2, x_3 should be in the same $R^{d-1}$ hyperplane? 
  4. In the proof of Lemma 3.4, mention that $\mathbf{y}_1$ is at the origin after translation and rotation. 
- The paper only presents the l_2 norm case as stated in section 5. However, it seems not easy to extend the multiple transitivities to other norms, e.g., l_1 and l_inf.  

Other comments:
1. Missing related works: 
  * The paper states, "Certified robustness has not, however, extended to rotational or translational modifications" on lines 68-69. However, there are already works [1,2] that handle the 2D and 3D image transformations.
  * Another recent paper [3] presents a different idea to improve the certified radius of randomized smoothing by incorporating another distribution.
2. It is interesting to explore the combination of the geometrically-informed certified robustness with other training methods [4,5] like [3] does.

[1] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, Bo Li, TSS: Transformation-Specific Smoothing for Robustness Certification

[2] Wenda Chu, Linyi Li, Bo Li. TPC: Transformation-Specific Smoothing for Point Cloud Models

[3] Linyi Li, Jiawei Zhang, Tao Xie, Bo Li, Double Sampling Randomized Smoothing

[4] Jeong, J. and Shin, J. Consistency regularization for certified robustness of smoothed classifiers

[5] Jeong, J., Park, S., Kim, M., Lee, H., Kim, D., and Shin, J. Smoothmix: Training confidence-calibrated smoothed classifiers for certified robustness.
questions: 1. The paper mentions "exponential growth in the number of hyperspheres that need to be solved" on lines 146-147. Then how about the results with small n like $n=4,5,6$?
2. Do the three approaches subsume Cohen et al.? If they do, please state the claim in the main paper and why Figure 4. has some cases won by Cohen et al.? If they do not, please discuss the reason or provide the counterexample.  
3. What is $r_1$ in Figure 3. 
4. What are the "Approx", "Approx Mod", "Actual", and "Actual Mod" in Figure 5?
5. What is the choice of the iteration $M$ across all experiments?
limitations: The paper only presents the geometrically informed certified robustness on the l_2 norm as stated in section 5. However, it is encouraged for authors to discuss other useful norms such as the l_1 and l_inf norms. Specifically, it is not easy to extend the multiple transitivities to other norms. 
Algorithm 1 needs M iterations, each requiring thousands of Monte-Carlo sampling.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors provide a method to enlarge the certification radii given by randomised smoothing based approaches. They use gradient based methods to find a points (and calculate their certification radii) in the proximity of the original input point, such that the combined information yields a larger certificate for the original input point. Two tricks are employed to be able to calculate the gradients yielding two methods: The ‘Full’ method, where the Gumble-Softmax is used to replace the argmax and the ‘Approximate’ method, which is based on reformulations and approximations.  The approaches are evaluate on MNIST, CIFAR-10, Tiny-Imagenet - the networks are based on Resnet18. 
strengths_and_weaknesses: The authors tackle an important problem, as certified robustness is an important research field. The ideas are interesting and the contributions are to the best of my knowledge novel. In the evaluation section, the authors give good intuition when explaining their results. The ideas are general and seem (at least partially) applicable to approaches certifying the robustness of geometric perturbations.

The experimental evaluation seems weak in the sense that the authors compare to [5], but not showcase how much their method would improve the results on some of the more recent papers published in this direction including MACER (https://arxiv.org/pdf/2001.02378.pdf), SmoothAdv (https://arxiv.org/pdf/1906.04584.pdf) or Consistency Smoothing (https://arxiv.org/pdf/2006.04062.pdf). Further, Section 3.2 and 3.3 are difficult to follow. The proof of Lemma 3.4 is not well explained and could hence not be checked for correctness. This is likely due to some minor confusion that can be easily clarified by the authors. More in the questions. Formalisation and maybe some pictorial illustrations might improve this section. Similarly for Lemma 3.5. Also, it remained unclear how the method would perform on challenging datasets including ImageNet. 

Regarding the related work: In line 52 and following, there is a misleading claim. The time and memory complexity are not the problem. For example interval bound propagation can be applied to analyse high dimensional inputs on large networks. The practical problem is the loss of precision linear relaxations suffer from. Further, the authors mention multiple times in the paper that “Certified robustness has not, however, extended to rotational or translational modifications …”. I encourage the authors to take a look at the following papers, the last 2 are randomised smoothing based: 

https://arxiv.org/pdf/1712.01785.pdf

https://dl.acm.org/doi/10.1145/3290354

https://papers.nips.cc/paper/2019/file/f7fa6aca028e7ff4ef62d75ed025fe76-Paper.pdf

https://arxiv.org/pdf/1912.09533.pdf

https://arxiv.org/abs/2002.12463

https://arxiv.org/pdf/2002.12398.pdf

Minor: In line 121, “the” appears twice in a row and $x_j$ is typed differently. 

*** 
After the authors response, i have increased the score. 
questions: - How would the improvements look like where more recent state of the art methods (as above) where to be used to train the network?
- What is the standard deviation between different training runs?  
- Eq. 6: what does $r’$ refer to? The same as in Eq. 5?
- Lemma 3.4: Is Lemma 3.4 optimal? Is $x_3$ here now fixed or variable? In Eq. 7, it seems as if $d_3$ and $r_3$ depend on $x_3$, whereas in Eq. 9 and Eq. 10 there seems to be a (further?) dependence of $y$ on $x$. 
- 152: To what does “feasible domain” refer to? 
- Did the authors consider to evaluate on ImageNet? 

limitations: The authors have mostly covered the limitations well. However, it remains unclear how scalable the method is to ImageNet.
review_title: null

Meta-review: metareview: The paper proposes a very simple idea that can improve one of the strongest robustness certificates. Most of the concerns were minor, and they were well addressed during the rebuttal phase. The reviewers were mostly happy with the current paper though shared a few remaining concerns, which could significantly improve the manuscript if properly addressed in the camera ready version. For instance, it will be great to see whether or not this idea can also improve the robustness certificates produced by different algorithms. The current performance gain still looks marginal, but it might be interesting if the same technique can bring in larger gains for different types of certificates.
confidence: Certain
Decision: Accept