Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper presents a unified characterization of classifier robustness, which covers both the worst-case adversarial robustness and robustness to random perturbations. The authors mainly focus on the problem of estimating the “intermediate-p robustness” for general p. By leveraging the techniques for partition function estimation, they propose a MCMC method for estimating the intermediate-p robustness. Theoretical justifications of the consistency of the proposed estimator are provided, and empirical evaluations on MNIST and CIFAR-10 are given.
main_review: The unified view of classifier robustness is new and interesting to me. However, I have a hard time understanding when the intermediate-p robustness (1<p<+infinity) is useful, which is the focus of the paper. Although the paper presents a very brief argument in lines 126-129 regarding this, without specific examples or further evidence, I cannot see the significance of the considered problem. This is my major concern of the paper. If the authors can convince me the user cases of intermediate-p robustness, I would be willing to raise my score. 

Other minor comments are listed below:
1.	How to interpret the results of Table 1 and Table 2? What loss function is used?

2.	How many MCMC samples are needed for producing a good estimate? In other words, what is the sample efficiency of the proposed estimator? It would be nice if the authors can show the convergence curves.

3.	For worst-case adversarial robustness, a more common evaluation metric is robust accuracy (choose 0-1 loss as the loss function in Equation 1). It would be better to provide the robust accuracy for each classifier considered.

limitations_and_societal_impact: The authors addressed the limitations of their work, but do not discuss the societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a definition of adversarial robustness that generalization current definitions of robustness, i.e. the loss incurred by a hypothesis when the input is contaminated by samples drawn from a perturbation set. The definition is based on a an Lp functional over the perturbation space, and interestingly it comprises the uniformly at random and adversarial cases when p=1 and p=\inty, respectively. Subsequently, in order to approximate this quantity, the authors propose a MCMC sampling approach of the partition function of an alternative density. The authors demonstrate the proposed definition numerically for MNIST and CIFAR datasets, showing that their approach performs better than a naive MC sampling. Additionally, they show that if models are trained by minimizing this new notion of p-robustness, even while approximate, they result in better robustness across this spectrum.

main_review: This paper is very well written and interesting. Their definition is valuable and insightful, as it generalizes current notions of robustness and reconciles two ideas that are often treated differently: adversarial perturbations and random perturbations from some distribution (as in distribution shifts). The proposed estimator is intuitive, and the numerical results confirm their effectiveness. 

My only major comment regards their reflection approach to their HMC sampling process to remain within the perturbation constraint set, which they authors explain for the case of L_\infty perturbations. Can the authors clarify if this is also applicable to general Lp balls? More generally, must this constraint set be convex for this to work? This question is motivated by the case of more general perturbations, such as those in color, contrasts, etc.

Minor comments:
- d\delta missing in Eq 11
- d\theta missing in Eq 14 and 15
- It was not immediately clear to me what the first column ("Method") in Table 1 and 2 referred to. Maybe the authors can clarify in the text, or table caption, that this refers to the way the models are trained.
limitations_and_societal_impact: Adequately addressed
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to tackle robustness both to adversarial noise and to random noise. The authors motivates the use of the Lp norm of the loss for a given noise distribution as an interpolant between robustness to adversarial attacks and random noise. The approach is well sounded.
main_review: The paper is easy to read to follow. I enjoyed the HMC sampling part that I did not know before. The experiments are nice and justifies the efficiency of the HMC sampling.


Remarks:
- The recovered loss as $p\to\infty$ is not exactly the adversarial loss. The authors must be careful because it tends towards the essential supremum for the measure $\mu$ and not the maximum on the support of $\mu$. I can discuss with the authors if they are not familiar with it.
- The paper lacks a bit of rigor. "For $f$ a function" for instance is not well defined. Which space do they consider in the whole paper? Which problem they consider? What assumptions on the loss? etc. I really suggest the authors to work again on that point
- The algorithm proposed by the authors to compute the integral seems dereasonably complicated at first sight in comparison with the naive sampling: $\delta_1,\cdot \delta_n$ from $\mu$ and return $\left(\frac1n\sum l(h(x+\delta_i),y)^p\right)^{1/p}$. Although it is justified experimentally, If the estimator proposed by the authors has a smaller variance, the authors should prove it. The authors should also plot the time of computation, because one gradient computation is very costful.

Other interpolations/related work:

In the paper [1], the authors proposed an entropic regularization of the adversarial problem. One can remark this regularization can be interpreted as an interpolation between a random noise and adversarial noise too.


Rating:

For now, I rate the paper as weak reject. I really suggest the authors to work on the rigor of their paper. Please define all the objects, etc. It can only make a better paper. Moreover, I suggest the authors to give a provable justification for the use of the HMC method.


[1]Mixed Nash Equilibria in the Adversarial Examples Game. Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, Yann Chevaleyre. ICML2021
limitations_and_societal_impact: Understanding adversarial problems is a important topic, since it is a threat for ML systems in productions.
review_title: null

Meta-review: The paper presents a new notion of robustness that interpolates between random perturbations and adversarial perturbations. The authors also present a MCMC based approach to evaluate the proposed robustness notion. All the reviewers agreed that this is an interesting and insightful notion of robustness and the results presented are above the bar for NeurIPS. There were concerns raised about the significance of the proposed definition, but the author response in this direction has been satisfactory. The authors should take into account the reviewers' comments before preparing the final version.
Decision: Accept (Poster)