Towards Certified Probabilistic Robustness with High Accuracy

My main concerns are raised in the Questions section.

But some minor details:

• in section 2 it was stated initially that h outputed a label. And yet later on in the same paragraph this was changed to logits. Precision/consistency is required
• writing G_x = arg max h(x) for example needs to make it very clear what the argument is they're searching over (vector index of logit output here)
• It is claimed in the introduction that randomised smoothing suffers from "significant accuracy loss". This is a broad statement to make as for example one can vary the variance of the added noise in order to vary the certified robust radius achieved (and also the impact on accuracy)
• In equation (2) it is not clear what the random variable (more importantly its distribution) is for the inner Probability
• near end of section 2 ... "solution expects efficiency" should be "solution exhibits efficiency"?
• in (1) it seems to be defining an adversarial example as a pair of points x1 and x2. Yet later on single points are referred to as adversarial examples. The definition (1) is a bit misleading

Broadly my concerns relate to - the nature of the experimental comparisons constructed (and some scepticism about the associated results); non-standard evaluation measures for certification (not looking at the relationship between certification sizes and accuracy); and a writing style that makes the nature of the contributions difficult to parse (and a framing that is potentially disguising the similarities between the developed works and prior techniques - see the point about P > 0.5 below).

I also wonder if, given that one of the stated contributions is that it doesn't introduce "strong noise" (what exactly is strong noise?) at training time, that perhaps the evaluation metrics don't properly capture the areas that the paper has identified as being where the authors had made contributions.

I apologise that the following weaknesses are broadly chronological, rather than highlighting points in terms of their importance:

• Abstract doesn't include any performance metrics, which is something I'd suggest as a way to better establish the validity of your work from the start.
• Notation is odd. Equation 1 for example - eqn 1 is only a correct definition of an adversarial example if the distance condition is established. But the distance condition isn't a necessary part of things.
• The framing of the problem is also odd. "Unlike deterministic robustness, probabilistic robustness allows a small number of exceptions within the vicinity of a sample to have different labels". Mechanisms like Lecuyer / Li / Cohen / Cullen (who use randomised smoothing) can even have the majority of points within the vicinity of a sample to have a different label, just as long as the there is a majority of classes in the region with the greatest concentration of the probability density function. More broadly, the language is at times quite difficult to parse - there's nothing technically wrong with the writing, but the way it has been written makes the content difficult to parse, and disguises the nature of the contributions.
• I'm well versed in this field and Figure 1's caption is completely bamboozling. As far as I understand it, this is completely interchangeable to Lecuyer / Li / Cohen / Cullen - in that if the system is a binary classifier, then the minimum condition for constructing a certification is that the class probability (or expectation) is greater than 0.5.
• I'm concerned about the nature of the comparisons. Table 1 considers $\ell_\infty$ norm perturbations - but Cohen's randomised smoothing for example (the RS row) is for guarding against $\ell_2$ norm perturbations.
• Also the reliance on certified accuracy alone is odd - the certification literature typically considers the relationship between the size of the achievable certifications and the accuracy. What is being done here is essentially just a slice of that, and I don't believe it is fully representative of the dynamics that one would expect to see.
• Figure 2 has no Y axis label.
• If I understand the style considerations of ICLR, having two items side by side isn't in the spirit of the style guide. I'm specifically referring to Table 4 and Figure 2 being aligned in one block on page 8.
• How do the metrics from Table 4 change with dataset size? I'm also more than a little sceptical that every measure of inference time is 2.7 x 10^x for varying X except for your technique. Moreover, if I'm reading your Table 4 correctly, you have a 27 second inference time for most techniques, and a 72 hour inference time for Randomised Smoothing. Based upon performing experiments with Cohen et.al's code (your RS technique) on a RTX 1080 I am absolutely confident in saying that there is absolutely no way that this is correct for MNIST.
• Relating to table 4, in text you state that IBP requires the least inference time - except that's not true at all, given that most techniques require 27 seconds at inference time. Moreover, based upon my own experience with IBP I also must express a great degree of scepticism about these performance metrics for IBP. These results also call into question the fairness of the comparisons - a point which is complimentary to a point I make further on in this weaknesses section regarding the transparency of the architectures chosen.
• The code github link doesn't point to an appropriate repository - either submit it using an anonymous code submission platform, put it in the supplementary materials, or just state that you're going to publish the code on acceptance.
• I'd suggest that Cifar-10 and Cifar-100 are semantically similar enough that I wouldn't necessarily count them as 2 distinct datasets for comparison. Ideally I'd like to see Imagenet or TinyImagenet used, although I can appreciate with the hardware used by the authors such a dataset may be beyond their technical capacity.
• Unless I have misremembered things, there wasn't a great deal of specificity regarding how the architectures of each technique were chosen. The authors state "we report the experimental results according to the most suited architecture" - but most suited by what measure? How was this chosen, and what architectures were actually used for each technique in Table 4? Table 5 summarises the architectural features, but not their applicability.
• There's quite a reliance on statements without specificity - things like "strong noise" or "the hyperparameter \lambda must be reasonable".
• Algorithm 1, line 12 - according to this there's no dependency on the index i, so $\sigma_i = \sigma_j$ by definition, which then begets the question of why sigma is even indexed?
• The actual mechanism for achieving certification is also remarkably opaque.

For a paper that talks about training time modifications to improve certification performance, it's also odd that there's no consideration of Salman or MACER, which have already established training time modifications for improved certification. Their exclusion is surprising.

• The novelty of the paper, aside from the variance training objective, is unclear. In particular, the suggested inference method (selecting the majority decision among sampled points) seems to just be randomized smoothing. Further, it is unclear how the certification approach compares to similar methods (Baluta et al. 2021, Zhang et al. 2023). I would suggest that the authors add an explicit related work section to clarify these points (as well as contextualize the work more thoroughly).
• The experimental methodology may not be completely fair as the baselines are using different neural networks (Table 5). I’m not entirely sure why the methods could not be compared using the same neural network (see question below).
• The correctness of the certification algorithm (performing left and right tests after each new sample) is unclear to me; in particular there is no proof provided for Thm B.2.

(Baluta et al. 2021) "Scalable quantitative verification for deep neural networks." 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)

(Zhang et al. 2023) “Proa: A probabilistic robustness assessment against functional perturbations”. Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 154-170). Cham: Springer Nature Switzerland

• The comparison in Table 1 using the proposed robustness metric is misleading. The guarantees provided by deterministic methods are fundamentally different from probabilistic ones. The probabilistic guarantees for local robustness with $\kappa=0.01$ are quite weak for high-dimensional inputs (going from $\kappa=0.01$ to $0.0001$ can be hard). If the authors insist on making such a comparison, then I would suggest doing the following: (i) Count the total number of images within each adversarial region and then sum it across all images in the test set. Report the fraction of images correctly classified by each model, or
  (ii) Show how the robustness scores and inference speed for different values of $\kappa$ vary as $\kappa$ approaches 0.

• Main mathematical details are not rigorously presented: (i) Proposition B.1 and Theorem B.2 are entirely stated in English which makes it quite vague, it should be possible to state these results formally, (ii) it must be possible to define the metrics in Table 8 more formally compared to just using indicator functions on statements in English, and (iii) sequential sampling seems to be important for the efficiency of the proposed method but it is never described in detail and its impact on the formal guarantees is unclear.