Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary of the paper:
This work aims at proposing a new type of regularization based on the affinity of the samples in the training set which is used, that allows to design more robust neural networks. 3 ideas are combined to obtain a tractable training procedure. First, the authors assume that the data lay on a manifold and propose to be stable to an $\epsilon$-sausage of the manifold rather than the manifold itself. Then, the authors propose to neglect the correlation terms between different samples and to assume that the affinity matrix is diagonal - they however employ some "ghost" samples for computing the affinity. Finally, simple metrics (like hamming distances) are used to obtain a simple to compute regularization term. The authors demonstrate good performances against standard attack, on CIFAR-10.

Pros:
- Interestingly, some of the assumptions on the manifold look reasonable, and it is interesting to rather study a neural network with the distance induced by a manifold rather than with the Euclidean distance of the ambient space. Indeed, the natural setting of the stability is along the manifold, where any points outside the manifold is an outlier: this leads to a different notion of manifold.
- The performances seem good and to use standard approach, and seems fast (though no benchmark is done in the paper)

Cons:
- Unfortunately, in the current writing, I noticed sometimes a certain lack of rigor, which makes the paper difficult to read and the drawn conclusions difficult to understand.
- In my current understanding of the paper, the data manifold isn't really used and the method remains local, and employs solely the Euclidean metric, which sounds paradoxical given the promises of the paper: if two data points are in the same neighborhood, this information can *not* be used by the current algorithm.

Specific remark:
- I don't understand the path from "adversarial robustness" to the definition and proposition 4.1. Indeed, I thought the definition 4.1 was the standard notion of robustness (as used e.g., in https://storage.googleapis.com/pub-tools-public-publication-data/pdf/45227.pdf ) "We reframe the goal of learning with decouples from accuracy" thus sounds slightly wrong, because I believe this was done in previous works.
- Sec 5.2 needs a substantial rewriting: "by the curse of dim... grows" sounds really bad. I don't understand the equation right above eq. (7), what is L'? This is not introduced. "the curse of dimensionality implies data becomes more sparse" sounds really wrong. On the contrary, sparsity is an assumption to fight the curse of dimensionality. I think the idea can be understood as neglecting the cross term of the covariance matrix, under a local approximation. I find the final justification very informal, and I think there is a confusion between sparsity and high dimension.
- Sec 5.3 and 5.4 describe experimental protocols that include a lot of new hyper parameter. I'd be curious and happy to see the cross validation protocol and its results. For instance, it's unclear to me what is the conceptual difference between the 3 regularizition-distances proposed and why/how, in a joined manner, they affect the performances.
- As described in 5.5, the validity of the model indeed requires on a certain notion of invariance (or smoothness), which is linked  strongly to a manifold assumption, and the idea that, the l2 metric is important, is not new. In fact, it is somehow limited as translation is also a major variability and one could used the quotient distance related to this Lie group over the manifold of images. Furthermore, going beyond this type of explicit & analytic distance(eg l2 metric) is one of the purpose of graph-based regularisation, but according to this paper, this would require to understand the regularity of the data because there is no clear model of the manifold $\mathcal{M}$ of the data.
- The notion of regularity which is used here doesn't introduce more complex smoothness that what is used traditionally in the litterature of adversarial examples for neural network: it's almost purely an additive perturbation that relies on an euclidean distance.

Suggestion for improving this paper:
- I would try to find a manner to employ a non-diagonal approximation of the Laplacian or at least to verify this case is the appropriate one in practice. Indeed, if the data were sampled from the same low-dimensional manifold, then this assumption would be too strong.
- I believe it is important to clarify the experimental protocol and to clean the informal statements.
- I would also try to go beyond the Euclidean setting.
review_title: Interesting ideas that could be further developed.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes new regularizers for obtaining adversarially-robust models, inspired by the "manifold assumption" that data lies on a low-dimensional manifold. The first regularizer is based a sparsified Laplacian regularizer on the dataset along with random perturbations around each point, while the second is an approximation of the hamming distance between activation maps of a point and its local perturbations.

While the obtained results seem promising, the motivation is questionable, in the sense that the obtained regularizers simply encourage local robustness around each point with random perturbations in all directions, and thus do not really exploit anything about a possible manifold structure in the data. The authors simply point to the "sparsity" of the data in high-dimensions (from what I understand, this is in the sense of points being much further away from each other compared to the local generated perturbations) in order to reduce the laplacian regularizer to only edges between perturbations of the same point, which leads to a natural regularizer that looks like a simple surrogate for penalizing the lipschitz constant. The Hamming regularizer seems more interesting but also seems unrelated to the motivation of manifold assumption.

This makes lean towards rejection, and I encourage the authors to better motivate the proposed regularizers and further compare to previous works in theory and in practice.

more comments:
- introduction: the meaning of "sparse data" should be clarified
- proposition 5.1: I am not convinced that L and Lc converge to the same operator, as the underlying distributions are different, perhaps the authors mean that the limiting operators are close to each other in operator norm? a rigorous proof is desirable
- p.5 "By the curse of dimensionality ...": this should be clarified
- definition of H_alpha: please elaborate on what inputs are fed into this function.
- section 5.5 "the two properties converge": this is not clear
- Table 1: are all models in a given column evaluated using the same attack? why were these particular baselines chosen? I am not sure I understand what makes the comparison to Wong et al. a strength of the current approach.
- section 6.2 / Table 2: please clarify what "verified robustness" means. 
- table 2: are all numbers in a given row obtained for a single model with a fixed choice of hyperparameters? which metric are these optimized on?

** update after rebuttal **

Thank you for the detailed clarifications. I still find that the recommended method used in practice, which only encourages robustness to local random perturbations, is too disconnected from the motivation of manifold regularization, and will thus keep my score.
review_title: promising results but questionable motivation

final_score: rating: 4: Ok but not good enough - rejection
review_content: Strength:
1. The author introduced a regularization-based robust training method that can perform well on CIFAR-10.
2. The comparison in the experiment section contains many different aspects of robust training.

Weakness:
1. The perturbation of the $\epsilon$-neighborhood on page 4 is not described. Is it Gaussian? Or Uniform? For the Gaussian perturbation, there's another track of verifiable robustness by Cohen "Certified Adversarial Robustness via Randomized Smoothing" and a following-up method to train the robustness called "MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius". 
2. The biggest concern comes from the perturbation part as well. The author includes a local small perturbation and only considers this local information to compute the $L$ matrix, which used to be computed between all the samples. Since the model only considers the arbitrary fake neighbors, the model will have an un-accurate view of the overall manifold (of equation (2)). Otherwise, this sounds like a free-lunch theory. Can the author make a more clear statement that which is given up and which is beneficial? Also, when considering the data manifold, after perturbation, the manifold is almost surely corrupted. For example, if you consider $S^1\subset R^2$, when you perturb by any arbitrary noise, it will turn out to be a ring with dimension $2$ instead of $1$. So I doubt the local perturbation-based estimation will not recover the actual tangent vector, etc., of the manifold.
3. The benefit of this method is not well addressed. For example, compared with the attack-based robust training, does this method performs a faster training speed? How fast? Will this reduce the number of data that is required? Some more discussion on the benefit as well as the compromising will be appreciated.
4. One of the important matrices in this method is $L$. Is this matrix pre-computed or is this matrix computed in each iteration? Will this cause extra storage space?

Some minor comments:
1. The tables should be self-explainable. For example, highlight the SoTA or give a detailed description of evaluating which number is better. 
2. The numbering of equations is confusing. The (3)-(6) can be combined and the most important equation (section 5.4) contains no numbering. I would recommend the author to number those important equations. 
3. The equation in section 5.4, if expanded, it would be a norm on $||\cdot||_2$ as well as $||\cdot||_H$, which is also the robustness argument this paper is made. Can the author explained why this is different from just constrain those norm?
review_title: The author proposed a regularization-based robust training method. The results shows improvements over the very baseline, but not as good as the current SoTA.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work introduces manifold regularization as an approach for learning stable deep nets, towards the goal of adversarial robustness. Several regularizers are proposed: intrinsic, sparse Laplacian and Hamming regularizers. As the proposed method relies only on adding these regularization terms to the loss, it is more computationally efficient than methods that require computation of adversarial examples during training. The proposed method is evaluated on CIFAR-10 under $\ell_2$ and $\ell_{\infty}$ ball attacks and shown to be state-of-the-art in terms of verifiable robustness to $\ell_{\infty}$ attacks at $\epsilon = 8/255$.

Strengths:
- Clear, well-motivated approach
- Hamming regularizer seems to be novel
- State-of-the-art verifiable robustness

Weaknesses:
- Limited experimental evaluation:
  * Lack of comparison with more recent approaches; this could be done by using AutoAttack ("Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks", ICML 2020)
  * Results from a single epsilon budget and on a single dataset
  * Experiment results seem to be from only a single run
- No direct experimental comparison/validation of stability, which is the stated goal of the work

Overall, this work introduces some interesting and novel ideas, but is lacking in its experimental evaluation, most significantly, in evaluating the stated goal of stability, as opposed to robustness which was done in the experiments. In particular, as noted in the paper, stability can also be achieved by regularizing the Jacobian-norm of the network, which seems like a more direct approach to the goal and should therefore be compared with; indeed, the implementation of the standard manifold regularization term looks almost like a finite difference approximation to the Jacobian-norm.

Other comments:
- The recent work "MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius", ICLR 2020 also presents an attack-free approach based on randomized smoothing, albeit for achieving certified $\ell_2$ robustness.
- "Disentangling Adversarial Robustness and Generalization", CVPR 2019 suggests that generalization (i.e. on-manifold robustness) is somewhat independent of off-manifold adversarial robustness; the proposed method seems to be aimed at targeting the on-manifold case ("we only need $\epsilon$ stability around valid input points") - what about the off-manifold case? 
- Related to the previous point, the sampling procedure in Section 5.4 of picking perturbed points (using "random maximal perturbations") does not seem to restrict samples to be on the data manifold.

*** Post response comments ***

Thanks for the detailed responses and clarifications, especially regarding the manifold used. I suggest that the notion of $\epsilon$-manifold regularization is made clear upfront in the manuscript (e.g. in the introduction) to avoid misunderstanding.

The new results with the dense $\epsilon$-manifold regularizer obtaining 5% less accuracy suggests to me that the specific approximation scheme used is indeed responsible for at least part of the benefit, and it would be useful to understand precisely why this is so since this is the core-contribution of the paper. I also agree with the other reviewers that the overall method as implemented seems a bit disconnected from the core idea of manifold regularization, and rather appears to be a variant of stability training (Zheng et al. 2016). As such, I will be keeping my original rating; nonetheless, I want to again thank the authors for the interesting and vigorous discussion.
review_title: Interesting ideas but needs better experimental evaluation

Meta-review: The paper received borderline and negative reviews but has raised many questions and discussions, showing that the paper has some merit. Many concerns were however raised on various aspects of the paper such as mathematical rigor, clarity, and motivation of manifold regularization that is too disconnected from the robustness to local random perturbation which is encouraged by the method. The rebuttal addresses some of these comments and the reviewers have appreciated the detailed answer. Yet, it was not sufficient to change the reviewer's opinions.

In its current form, the paper is not ready for publication and the area chair agrees with most of the reviewer's comments. He recommends a reject, but encourage the authors to take into account the feedback from the reviewer before resubmitting to a future venue.
Decision: Reject