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 considers the issue of certifiably-robust machine learning
predictors in the 'randomized smoothing' framework of Cohen et al. (take a
classifier $g$; add isotropic gaussian noise to the input to generate a
distribution over predictions $g(x + \varepsilon)$, and let $f$ denote the
predictor that selects the most probable output; prove robustness guarantees
about $f$ using Neyman-Pearson), but with the additional consideration that the
base classifier $g$ is invariant to certain transformations. The authors focus
on the case where the input to $g$ is a batch of physical data $\mathbf{X} \in
\mathbb{R}^{N \times D}$ in $\mathbb{R}^D$ (e.g., point clouds, molecular data, ...), and
the group actions are rigid motions acting on the rows of $\mathbf{X}$ and
permutations of the rows. To make the randomized smoothing approach
computational, probabilities are estimated in a Monte-Carlo fashion and
robustness guarantees are probabilistic; the authors extend the same
computational procedures to the 'invariant $g$' setting by arguing that for the
specific invariances they consider, the randomized smoothing procedure also
yields an invariant classifier $f$, and that the certification procedure on a
new test input can be done efficiently (minimization over the group action for
this family of invariances can be done simply in closed form, e.g. mean
subtraction, orthogonal procrustes). These extensions give exact (the authors
use 'tight') certificates for translation invariance, meaning that the
robustness guarantee matches the lower bound given by Neyman-Pearson; for more
general transformations there is some looseness, and the authors provide
theoretical studies of the gap in the case of 2D rotations and experiments
which show that the gap is often small (but there is extra Monte Carlo
complexity/error associated with the tight certificate approach here that makes
some experimental results contrary to what one would expect).


strengths_and_weaknesses: 
## Strengths

- Invariant models for computing with point cloud data are becoming more and
  more prevalent, and understanding issues of robustness with these models and
  their connection to certified robustness seems timely. This paper seems to
  initiate this line of work.
- The paper is well-written, with ample details on background material,
  derivations, and technical points. The appendices are extensive and catalogue
  conceptual/computational aspects of the experiments.
- It seems to be a useful methodological contribution to show that it is
  'enough' in some practical cases to use the simple post-processing approach
  to certification, even if it is not Neyman-Pearson-exact (although see some
  caveats below).

## Weaknesses

- The contributions here seem somewhat narrow -- it would be better if theory
  and experiments relevant to the case of 3D rotations were presented, given
  that this seems to be most important for the applications used as motivation
  (point cloud nets, molecular prediction, ...). Most of the experiments are
  used to motivate the idea that the 'post-processing' invariance approach is
  comparable to the tight certificates approach for 2D rotations; one would
  like to see that this continues to hold in 3D.
- It seems strange that the tight certificates approach does not yield superior
  accuracy in Figure 6. 
- The theorems and derivations throughout the paper are presented in a
  formalism-heavy way that often belies significant underlying conceptual
  simplicity. I think the clarity of the paper could be improved as a whole by
  also mentioning some of these simple conceptual intuitions: for example, 
  eventually the post-processing approach that is argued to be sufficient
  (Theorem 2) is quite intuitive (it might be nice to have an Algorithm
  environment somewhere that summarizes exactly what approach the authors are
  ultimately proposing that one takes away from the paper, to have a useful
  methodological contribution -- with all the competing approaches it is easy
  to get a bit lost reading through); the proof of Theorem 3 essentially only
  depends on rotation invariance of the gaussian distribution; the 'canonical
  representation' formalism from definition 3 (is this a standard term?) and
  its instantiations throughout section 6 seem to be understandable in terms of
  whether or not you can quotient $\mathbb{R}^{N \times D}$ in a sufficiently nice
  sense by the action of the symmetry group; the observation discussed in the
  paragraph at line 217 can probably be explained using some classical insights
  from invariant theory. 
- It seems that generalizing this to images will be infeasible in general,
  given that invariances one is interested in here act on the image plane
  rather than on the image values, which means that the analogue of Theorem 3
  will not transfer. (c.f. Section 7) More generally, one imagines it would be
  challenging to extend this approach to any similar 'homogeneous space'
  setting of the invariant group action.

## Minor Issues

- Line 45: it seems perhaps premature to call a method from 2019 "classic".
- Line 84: spurious period
- Line 91: should this line 'First, one can use the fact that ...' state
  $f(\mathbf{X}) = y^\ast$ rather than $\mathbf{X'}$? The discussion below
  seems to demand that this is true.
- Line 92: I would recommend stating the restriction to binary classification
  outside of a footnote, as it is done systematically throughout the paper. 
  In appendix F, it would make sense to reference the general version of the
  Neyman-Pearson calculation proved in [27] for general values of the
  probabilities -- I imagine the current omission won't bother a reader who is
  familiar with randomized smoothing, but I found it necessary to do the
  calculation myself and then reference what was shown in [27] to convince
  myself that something wasn't being omitted here.
- Equation (5): why is there a slash through the bottom line on the $\geq$
  symbol? I do not understand this result.

questions: - I would appreciate some clarifications on the contributions and the
  relationship to prior work. The contributions claimed at line 40 are quite
  narrow -- is this also the first work that takes up the systematic study of
  randomized smoothing combined with invariant classifiers? The section in the
  related work at line 52 seems to suggest this is the case, but doesn't claim
  it directly. 

- The expressions in Theorem 7 seem a bit too complex to easily parse, even
  when looking at the full details in the appendix -- one is curious whether
  some pathological behavior emerges for 'strange' values of $\mathbf{X}$,
  $\mathbf{X}'$, and $\boldsymbol{\Delta}$; whether there is a 'typical'
  setting (random? incoherent?) where it is possible to get more insight into
  the result's predictions; etc. If the authors can point to any details in the
  appendices that help interpret these issues + could be integrated into the
  main body, this could help.


limitations: Yes. The authors provide a concrete Limitations and Broader Impact section
(Section 7).
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 paper develops a number of robustness certificates for models applied on spatial data (e.g. point-clouds). It builds upon prior work on using randomized smoothing to derive provable robustness certificates for models in a black box manner, and extends the scope of certificates by leveraging information about model invariances to create what the authors call "gray-box certificates". For example, if a model is known to be translation invariant, then any input that can be moved to a region covered by a certified to receive a specific output, will also receive the same output under the model.
Using this approach, the paper introduces certificates leveraging invariances to Euclidean isometries (translations, rotations, reflections) and and permutations. It proves that the certificates for translation and certain rotation transformations are tight and conducts empirical experiments to support the findings as well.
strengths_and_weaknesses: ### Strengths
- Robustness certificates are usually used to prove that certain invariances hold for a model. Using a-priori knowledge about invariances to increase the scope of provable (derived) robustness is an interesting avenue.
- The paper conducts a solid theoretical analysis and further supports its conclusions using empirical evidence.

### Weaknesses
- The applicability of the work might be somewhat limited, because it is difficult to construct models that are provably robust to certain input transformations, and not just weakly invariant due to training. The certificates developed in the paper only hold when strict invariance can be assumed. 
- There are some clarity issues, especially regarding the different types of certificates. There are a number of different certificates (black-box, gray-box, post-processing, pre-processing, tight), and it's difficult to keep track of their meanings relationships. The different types of certificates should be clearly defined (ideally already in the intro, at least roughly) and delineated. For instance, it's not clear to me what the role of the pre-processing certificates is? Are they more than post-processing certificates proven to be tight?
- A central quantity in the theoretical analysis is the probability $p_{X', y^\ast}$ (line 92) of predicting the target class under randomized smoothing, which is used to bound classification probabilities. However, in the original randomized smoothing work, this quantity is compared to the probability of the next most likely class, which is absent from the analysis here. As far as I can see the workaround is to assume that $p_{X', y^\ast} > 0.5$, though this seems like an overly strict assumption in a multi-class scenario. Wouldn't comparing $p_{X', y^\ast}$ against the next most likely probability allow for deriving tighter bounds? Or is the analysis limited to binary classification? Footnote 2 seems to suggest something like that, but the definition of g only mentions a general label set $\mathbb{Y}$. Please clarify this.
questions: - In theorem 6, shouldn't g have the property of being rotation instead of translation invariant?
- I am not an expert in the spatial-data domain, so I am not sure how realistic for instance attacks using point translations or rotations are, it might be worth to discuss the threat-model or other ways in which such transformations might enter the test data in more detail.
- Could you clarify why the set of invariance transformations need to form a group?
limitations: The limitations of the paper seem to be sufficiently addressed.
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: This paper proposes an approach, leveraging the invariance property of the base classifier to enhance the randomized smoothing certificate. 
strengths_and_weaknesses: Strength:
1. The paper is quite complete.
2. The presentation is good.

Weaknesses:
1. The contribution of this paper is a bit incremental. Specifically, Theorem1,2,5 are obvious to me.
2. The significance of invariance-aware randomized smoothing is limited. The neural network classifiers that satisfy invariance are extremely rare, so the author needs to construct invariant versions of PointNet and DGCNN via some tricks. 
questions: 1. Is Eq. (91) in Lemma 14 (appendix) wrong? It might be a typo. I think the left-hand side is the same as the right-hand side.
2. Is group averaging (line 222) a common technique for improving classification performance, or just for the invariance property in the field of 2D/3D point cloud classification?
3. This paper should include more discussions on the connection to [Li et al., 2021], which is also an important work on transformation-specific smoothing

[Li et al., 2021] Tss: Transformation-specific smoothing for robustness certification, CCS 2021.
limitations: The contribution of this paper is limited since invariant models are rarely studied for some reasons (might be the poor performance or the limited generalization ability?).
review_title: null

Meta-review: metareview: The paper presents the first study in the literature about the interplay of model invariance and robustness certification. While the approach is novel, the techniques are usual and the scope of the invariances considered are a bit narrow, which makes the paper somewhat borderline. Nevertheless, all reviewers recommend acceptance.
confidence: Less certain
Decision: Accept