Venue: UAI 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept, e.g., novelty, outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: Q1 Summary and contributions: This paper improves existing randomized smoothing based approach by using different noise magnitude on different input data points. Intuitively, for points near decision boundary a smaller noise is preferred, while a larger noise can be used on other data to maximized certified radius. Existing works typically use a single noise sigma accords all data points and choose the best among them. This work proposes to apply different noise based on an optimization based scheme to maximize certification
Q3 Main strengths: 1. The idea of using input dependent randomized smoothing is novel and intriguing.
2. Empirically the proposed method tends to work well, with noticeable improvements on common benchmarks.
Q4 Main weakness: To guarantee soundness the proposed method needs to modify the classifier with memory - it must remember the data points it certified previously to guarantee the correctness of certification. This concept is a bit tricky and I need more explanations from the authors (see detailed comments below).


Q5 Detailed comments to the authors: The paper proposes an interesting idea of using data-dependent randomized smoothing. However the requirements of memory makes this approach quite tricky and I am skeptical about it. I am willing to hear from the authors before I give a strong recommendation for this paper:

1. A memory-based based classifier means that its performance will depend on the data it previously saw, and it also depends on the order data comes in.
2. It seems to me it will become harder and harder to certify when more points are in memory. If there are infinite number of data coming in, what is the asymptotic performance of the proposed method? Would certified accuracy drop to 0 asymptotically? And how does the order of data affect its asymptotic performance?
3. Following the methodology in this paper, conceptually, we can also discard all the remembered certifications in memory, and start fresh with a new classifier each time. Essentially this means we are using one fresh classifier for each example. Is it possible to do so and what is the implication?
4. Is it possible to achieve soundness without memory?
Q2(4) Quality of experiments (Optional): 4: Excellent: The experimental evaluation is comprehensive and the results are compelling.
Q7 Justification for your score: The paper proposes a novel and intriguing idea, however its main limitation is the memory based classifier requirement which is tricky and less practical.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area of AI or moderate to high impact on more than one area of AI, with good to excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations. 
review_content: Q1 Summary and contributions: In the context of certifiable robust deep neural networks, the authors present an extension that increases the certification radius for the construction of smooth classifiers.
More precisely, the authors propose a smoothing approach that allows the variance used in smoothing to be data dependent. They achieve this in a parameter-free approach, both for certification and training and show empirically that their improvements hold for several approaches on different datasets.

Q3 Main strengths: The paper presents a data-dependent approach that maximizes the certification radius for the construction of smooth classifiers. This extension allows for an increase in the certification radius by optimizing the radius on a fixed model. This approach can also be used for training. 

As this approach can be used after the model has been trained, it can also be used in combination with other approaches. 

The approach also does not make any assumptions on the model type, thus opening the possibility to extend the certification radius of other types of models.
Q4 Main weakness: Is the memory-based certification dependent on the order of the instances? Consider the right-most case from Fig. 2. Here you adjust R2 not collide with a pre-existing R1, however, if you shuffle the data, you would potentially find the case R2 before R1, which means this is a greedy approach. Does this have a significant impact?

Is there any particular reason why you opt for a constrained covariance matrix? More flexibility here could also increase the certification volume.

Q5 Detailed comments to the authors: On important aspect in deep learning is the robustness of the models against noise and/or adversarial attacks. Here the authors present an approach that expands the radius of certification, which can be very helpful for practitioners in a wide range of settings.

The paper presents an approach that is a natural extension and one that conceptually makes sense. Consider that SVMs are doing exactly the same thing during training. Instances far from the boundary are discarded during optimization and only relevant instances are kept (the support vectors). One could argue that instances far from the decision boundary should have naturally a larger certification radius. 

This approach could further be used to detect when instances could be problematic, as the covariance would be smaller, when closer to the decision boundaries.

The paper is well-written and technically sound, and I only have some questions raised in Q4. I'm also wondering whether the variance/covariance could be learned/predicted? It also seems to me like this approach is trying to indirectly estimate the distance to decision boundaries via smoothing, this could indicate further avenues for research especially for training.
Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: The paper is technically solid, and my only concerns are raised in Q4. The paper makes a natural extension that is useful in the area of robust DNNs.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area of AI or moderate to high impact on more than one area of AI, with good to excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations. 
review_content: Q1 Summary and contributions: In the context of randomized smoothing, the $\sigma$, a global parameter for generating Gaussian-noisy samples, is applied to derive the certification radius. This manuscript proposes to derive a local and sample dependent $\sigma_x$ by maximizing the radius w.r.t. the $\sigma$. This idea is well motivated and intuitive, since a related approach in [Zhai et al. 2020] optimizes the radius w.r.t. the model parameters. 
Q3 Main strengths: The proposed approach is well motivated. Considering the latest publications, esp. [Zhai et al 2022] and [Salman et al. 2019a], deriving the local $\sigma_x$ seems only an intuitive and natural step that would enrich the field of randomized smoothing. The paper is also really well written and easy to follow. 
Q4 Main weakness: What seems to be missing in the experimental section is the presentation of the (at least) computing time / complexity, since both DS and DS**2 requires additional gradient update in the input space, which could be fairly expensive. The authors may want to include this aspect in the final version. 
Q5 Detailed comments to the authors: Some further, but minor issues: 
1. From a reader perspective, I would also be interested in some analysis demonstrating how the local $\sigma_x$'s are actually improving the certification accuracy. For instance, the authors might be able to plot the empirical distribution of the local $\sigma_x$'s while marking the position of the global $\sigma$ that has been outperformed. This kind of analysis might also help eliminate the doubt that the local $\sigma_x$'s could be too small to be useful. 
2. The section on memory based certification might require some further investigation. If the middle scenario in Fig. 2 is true, I would say it is a direct proof that both R1 and R2 are too large and they should divide the distance between them equally. The proposed solution to alter the class of $x_2$ seems unnecessary to me. 
3. In line 3 and 4 of section 4.2., I assume the $\hat{x}$ should be $x'$ (or the other way around) to denote the adversarial samples? 
Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: I believe a local definition of the $\sigma$ in randomized smoothing is only natural and belongs in this subfield. Unless there has been an earlier work (of which I'm not aware) on exactly this idea, this paper should be accepted.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area of AI or moderate to high impact on more than one area of AI, with good to excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations. 
review_content: Q1 Summary and contributions: In randomized smoothing for certifiably robust DNNs, there is a trade-off between the certification radius characterizing the amount of random noise around input $x$ which will not change the predicted class, and the accuracy of the classifier.
Here, the authors propose a training algorithm-agnostic framework to modify the parameters of the smoothing distribution according to the data, to maximize the certification radius without reducing the accuracy of the classifier. 
Q3 Main strengths: The paper is very well written: it is clear and complete. Its objectives are well contextualized and precisely explained, and so are the contributions. Reading the article, it feels like the whole idea and implementation is self-evident (which, of course, is not the case), and that is to the honor of the authors.

The proposed method brings an interesting novelty to existing methods, without proposing a ground-breaking idea. 
The experiments are well designed, and the parameters are fully transparent to allow scrutiny and reproducibility. The results are clear, well analyzed, and support the claims. 
Q4 Main weakness: I did not identify strong weaknesses in this paper. It is solid all around.

While the results do support the claims with consistent improvement of the certified accuracy across all cases, the improvement is not very strong. The advantage of DS$^2$ over DS is even less significant. For this reason, I do not believe this paper is ground-breaking, but the contribution is relevant for the community.
Q5 Detailed comments to the authors: I have identified 2 small presentation details to correct:
1. In 3.4, in the Solver part, objective 2 is mentioned as "a natural solver for 2 is stochastic gradient" and later "this allows the gradient of 3 to enjoy [...] the gradient of 2". I suggest using (2) and (3) to clarify that you are referring to the equations.
2. In figure 7, the legend says "top figure" and "bottom" whereas it should be left and right.

I would be interested to know if the authors have thought about expanding the idea to a learning phase, where $\sigma^*$ would not be determined for each sample $x_i$ but able to predict it given any $x$. This assumes that the value of $\sigma^*$ can be somehow generalized over the input space, and would probably reduce the soundness of the guarantee. But it could remove the need of having the whole dataset for the preliminary step of Algorithm 2. Anyway, I'd like to know the authors' thoughts!


 
Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: This article is technically solid and very well written with a certain relevance for the community; however, I think that the potential impact is moderate.
review_title: null

Meta-review: Meta Review: All reviewers were unanimously in favor of accepting the work, recognizing its clarity of presentation, "novel and intriguing" methodology, and convincing experiments.  Reviewer bfhi brings up an interesting point about the method's order dependence and the asymptotic (data) limit, but I agree with the authors that they have appropriately addressed this.
Decision: Accept (Poster)