Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes the anisotropic version of randomized smoothing. Evaluation metrics based on the volume of the certified region are proposed, allowing comparisons with the certified regions provided from isotropic randomized smoothing. Experimental results show the usefulness of introducing anisotropic randomized smoothing as it certifies larger regions.
main_review: Strength

This paper is fairly interesting and insightful as it sufficiently demonstrates the advantage of introducing anisotropic robustness certificates. Although section 4.2 and 4.3, the main derivations of the non-isometric certification, are directly based on Salman et al. 2019(a), it is useful and allows less restrictive certification geometry. The discussion and adoption of Alfarra et al. 2020 in maximizing the volume through proxy radius are also interesting. Section 7.3 is especially helpful as it delves into the root keys of the better performance over isotropic DD.


Weakness

The paper mentioned all prior works considered smoothing with isotropic distributions and hence certified isotropic ell_p-ball regions, but [*] admits non-isotropic certified radius bound via first-order certification. It will be helpful if the authors can include comparisons theoretically and empirically with this prior work, allowing a more fair evaluation of the significance of the paper.

Mohapatra, Jeet, Ching-Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. "Higher-Order Certification for Randomized Smoothing." Advances in Neural Information Processing Systems 33 (2020).


Minor error: There is a redundant 'the' in the first sentence of section 7.3.
summary_of_the_review: The paper contributes adequately to the community and provides enough details regarding the problem formulation and empirical performance-cost tradeoff. Including a more complete comparison with the literature will make it a stronger submission.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors extend the standard (isotropic) l_1/l_2 randomized smoothing certificate to anisotropic smoothing distributions (and anisotropic regions). They propose to maximize the volume of the certified region for each sample independently, using a memory procedure to preserve soundness.
main_review: The paper is well written, polished, and easy to follow. The anistropic part of the proposed approach is well-motivated, however the sample-wise part has several issues (see below) making it unsuitable to use in practice. Moreover, some of the theoretical results are not novel (see below).

Comments:
- The derivation of the certificate in term of the Lipschitz constant under the dual norm (Proposition 1, Theorem 1) is insightful. However, this result is already known in the literature in greater generality and should be properly cited. Specifically, Theorem 1 in [1] derives the local (\alpha,\beta)-Lipschitz constant over an open set. The special case of a scalar function is also discussed (see Eq. 3 in [1]) and it coincides with the result in Proposition 1 (if we are in the special case where the open set is R). The discussion of how to use such a Lipschitz constant for certification is also discussed in [1] (see section E.2).
- The authors already discuss a know issue of data-dependent classifiers which when not tackled can lead to certificates that are not sound. To address the issue they adapt the memory-based procedure introduced in Alfarra et al. While this procedure does make the certificate sound it has other problems.
  - First, by introducing memory the proposed anisotropic certificate (or in fact any method to compute a certified region) becomes completely irrelevant. Namely, for sample i construct any region R_i and define that the prediction in that region is some arbitrary C_i. Then run the post-processing certification step in Algorithm 1 (or similarly the procedure from Alfarra et al.). Since the obtained regions will not intersect with any certified regions in the memory M the procedure is still sound. This is true regardless of how the region R_i was constructed.
  - A second, and more important, issue is that the memory makes the certificate dependent on the order of the incoming test samples. This provides a new avenue for attack, i.e. the adversary can optimize the order of the test samples to decrease the utility of the final obtained smoothed classifier.
  - Finally, the success of this memory approach also somewhat depends on the "sparsity" of the test samples. Namely, by using a small test set since the samples are in a high-dimensional space the distance between them tends to be bigger than the (proxy) radii of the certified regions. However, in a real-world application we are likely to have many more test samples which would increase the number of intersections when running Algorithm 1.
  - Note, all of these issue also apply to Alfarra et al. and are simply inherited in this approach.
- Another issue with the proposed approach is the optimization procedure described in section C. The optimization suffers from issues such as: inconsistent estimation due to clamping and not using confidence bounds, sensitivity to initialization, high gradient variance, etc. These and other issues have been described in great detail in section C.2 in [2], focusing on Alfarra et al., although, given the similarity, the same issues are inherited in this approach.
- Relatedly, in [2] the authors show that input-dependent randomized smoothing suffers from the curse of dimensionality. A discussion of this issue and how it applies to the proposed certificate should be included.
- The derivations for the special cases of certifying ellipsoids and generalized cross polytopes are useful. Note that similar results are derived in [3] (see Theorem 5 for a weighted l_2 metric equivalent to a diagonal \Sigma, and also Theorem 3) albeit in a slightly different context. A discussion on how these two relate should be included.  
- The discussion of how to evaluate the anisotropic certificates and the formal definition of a "superior certificate" is appreciated. 
- The experiments are executed well.

Questions:
- Assuming that estimate of the Lipschitz constant L is tight is the certificate provided by Theorem 1 also tight? For the special case of l_2 certification with "\Sigma = \sigma^2 I" tightness is shown in previous work. Does it hold in general?
- Are there any benefits to training with anisotropic noise?

References:
1. Jordan and Dimakis. "Exactly Computing the Local Lipschitz Constant of ReLU networks"
2. Sukenik et al. "Intriguing Properties of Input-dependent Randomized Smoothing"
3. Yeom and Fredrikson. "Individual Fairness Revisited: Transferring Techniques from Adversarial Robustness"
summary_of_the_review: The paper is well written, polished, and easy to follow. The anistropic part of the proposed approach is well-motivated, however the sample-wise part has several issues (see main review) making it unsuitable to use in practice. Moreover, some of the theoretical results are not novel (see main review).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors discuss the extension of $\ell_{p}$-randomized smoothing to anisotropic counterparts.
In particular, they consider the extension of $\ell_{2}$-certificates from (hyper)spheres to (hyper)ellipsoids
by sampling anisotropic rather than isotropic Gaussian noise, as well as the extension of $\ell_{1}$-certificates to cross-polytopes by sampling scaled Uniform noise rather than unscaled noise.
Further, the authors discuss how these extended certificates can be compared to their base-counter parts to establish superiority (inclusion).
The introduced certification algorithm, ANCER, utilizes the idea of data-dependent randomized smoothing to find the anisotropic shape with maximal certification volume.
In experimental evaluation on Cifar-10 and Imagenet the authors show that the obtained certificates permit higher isotropic certificating radii than other methods in the per-sample optimization setting.
main_review: The paper is well written and easy to follow.
At the high-level the idea of anisotropic certificates is mathematical simple, yet interesting and, as shown in the evaluation, effective.

The mathematical ideas introduced in sections 4 and 5 mostly follow directly from prior work (as is acknowledged in footnote 2).
ANCER, presented in sections 6 and C, also seems straight forward and correct. However, I have concerns about the data dependent nature of the algorithm (see below).

The evaluation section is quite thorough and obtains SOTA results.
However, what is completely missing is a discussion of the inference/prediction procedure.

Based on this my main concerns are:
- The usefulness of data-dependence approach (see below) and whether comparison with non-data-dependent approaches is fair.
- The novelty of the approach: Many of the contributions are direct consequences or applications of other approaches.
  While normally, in the light of good results, I would not mind this, in the case of this publication I am unsure, due to my first concern, how good the results really are.

Furthermore, I am wondering whether ACR gains can be realized in the anisotropic setting without per-datapoint optimization (e.g. finding a anisotropic smoothing parameters offline on the training set, and subsequently using them in certification)?

Data Dependence:
Data-dependent randomized smoothing (DDRS) [1] has been shown to be unsound in its original form and was then patched by the addition of memory-based certification in the latest draft of [1] as well as in this paper.
While the memory-based approach seems to fix the unsoundness of DDRS when applied to perturbed versions of previously certified samples, I have a few questions regarding its suitability as a practical certified defense:
- Neither this paper nor [1] discuss inference/prediction (e.g., PREDICT in [2]). Can you elaborate on how a prediction procedure would look like, that (i) is consistent with the result of the memory-based certification and (ii) is efficient (i.e. does not need to compute the certification radius at inference time)?
- Can you clarify whether the order in which inputs are presented can influence the output of the model? If so, would the model have to include a history of all samples, predictions, and certified radii previously seen? Consequently, would any obtained guarantees only be valid for a model with the exact same history, hence preventing parallel application?
- Can you discuss the possibility of an attacker deliberately presenting inputs (e.g. in small pockets of one class in the decision landscape) that influence the model’s predictions on future inputs?

Depending on these questions, data-dependent and non-data-dependent approaches (e.g. [2]) seem to target very different settings. If this is the case, I believe a direct comparison and the claim to be SOTA to be unfair.  To avoid confusion in the field, this difference in setting and all its implications should be made abundantly clear.

Further, while I am very open to discuss these points and, depending on the answers, raise my score, I am unsure whether this is the right place to discuss these issues as they mostly concern the key contributions of [1], which has not yet been published in a peer reviewed format, potentially due to these very questions.

[1] Data Dependent Randomized Smoothing, Alfarra et al.; arXiv 2020/2021

[2] Certified Adversarial Robustness via Randomized Smoothing, Cohen et al.; ICML 2019


summary_of_the_review: The paper presents anisotropic robustness certificates, which seems to be technically correct and conceptually interesting.
While not stellar I believe the novelty and motivation are sufficient, given the results.
However, my reception of the results, and thereby the overall paper hinges on the data-dependent optimization procedure considered in the paper, of which I am currently not convinced.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors provide a technique for a data-dependent randomized smoothing that provides anisotropic certificates of robustness. This may be viewed as an extension of the work of Alfarra et al, where the certificates provided are axis-aligned cross-polytopes or ellipsoids; however surprisingly the proposed approach provides even tighter bounds than Alfarra's in the isotropic setting.
main_review: **Strengths:**

Randomized smoothing, being the most scalable of robustness certification techniques, is an important research direction, and this work significantly advances the state of the art, even in the isotropic setting. The proposed technique is clearly explained and the analysis to justify this approach is simpler than that of Cohen or Yang. While the problem setting is slightly different than prior arts (anisotropic vs isotropic), a natural and fair quantitative comparison approach is described. The most significant and surprising result of this work: that these isotropic certificates outperform even Alfarra's approach is given ample discussion, and empirically-supported justification. The experiments are thorough and fairly compare against prior work.

**Weaknesses:**

A primary pitfall of this work is that anisotropic certificates are not particularly well-motivated. The community-accepted threat model for adversarial attackers is typically isotropic, and probing the shape of the decision boundary is of dubious utility. If this were a primary goal, more efforts would be paid to considering anisotropic certificates that are not axis-aligned (i.e. Sigma and Lambda are not diagonal). Another downside to this work is that it relies heavily upon the approach of Alfarra. Importantly, this also means AnCer inherits the main inelegance of Alfarra's approach: the memory-based classifier. This raises serious concerns in that the certificates provided are dependent upon the order in which the model is queried. While this is perhaps borderline not-kosher, it has not been a concern in practice in prior works, but it would be nice to see some evidence of this claim here.

**Questions:**

- How does Ancer perform for non axis-aligned anisotropic regions? Searching over orthogonal matrices (for the rotation) in addition to the diagonal anisotropic components could drastically increase the number of optimization variables as well as complicate the optimization landscape. How does this affect performance in terms of both runtime and reported certificates?
- Are there examples for which the memory bank of the memory-based classifier is leveraged? In particular, how does the minimum distance between a pair of cross-class test data points compare to the bounds provided? 
- What insights does AnCer tell us about the shape of the decision boundary? 
summary_of_the_review: This approach advances the state of the art in an important line of work. A slightly nonstandard problem setting is considered, but even when comparing to the standard problem, AnCer improves upon prior works. The analysis is clean, the results surprising, and the experiments are thorough. I have no qualms recommending acceptance.
review_title: null

Meta-review: The paper proposes the anisotropic version of randomized smoothing. Evaluation metrics based on the volume of the certified region are proposed, allowing comparisons with the certified regions provided from isotropic randomized smoothing. Experimental results show the usefulness of introducing anisotropic randomized smoothing as it certifies larger regions.

Strengths:
+ The paper is well written, polished, and easy to follow.
+ The anisotropic part of the proposed approach is well-motivated.
+ The evaluation section is quite thorough and obtains SOTA results.

Weaknesses:
- The sample-wise (data dependent) part has several issues making it unsuitable to use in practice. The authors already discuss a know issue of data-dependent classifiers which when not tackled can lead to certificates that are not sound. To address the issue they adapt the memory-based procedure introduced in Alfarra et al. While this procedure does make the certificate sound it has other problems. For example, an issue is that the memory makes the certificate dependent on the order of the incoming test samples. This provides a new avenue for attack, i.e. the adversary can optimize the order of the test samples to decrease the utility of the final obtained smoothed classifier. In addition, the success of this memory approach also somewhat depends on the "sparsity" of the test samples. Namely, by using a small test set since the samples are in a high-dimensional space the distance between them tends to be bigger than the (proxy) radii of the certified regions. However, in a real-world application we are likely to have many more test samples which would increase the number of intersections when running Algorithm 1. Although the authors provide opposite empirical evidence on a specific dataset, it is not very clear how general it is for other datasets.

- Some of the theoretical results are not novel as they follow directly from prior work (as acknowledged in the paper). 

- Another issue with the proposed approach is the optimization procedure described in section C. The optimization suffers from issues such as: inconsistent estimation due to clamping and not using confidence bounds, sensitivity to initialization, high gradient variance, etc.
Decision: Reject