Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary: The authors propose to use the worst-case population loss (with bounded Wasserstein distance) over noisy inputs as a robustness metric. They provide a tractable upper
bound serving as a robustness certificate by exploiting the duality. The smoothness
of the loss function ensures the problem easy to optimize even for non-smooth
neural networks (since these are smoothed by expectation over noisy inputs). They show experiments on a variety of datasets and models to verify that in terms of empirical accuracies, their approach exceeds the state-of-the-art certified/heuristic methods in defending adversarial examples.


##########################################################################

Reasons for score: 

Though the problem setting is not very accurately motivated, I liked the fact that the authors showed distribution dependent guarantees on robustness. It is still unclear to me though why adversarial noise is expected to be within some bounded Wasserstein distance from the probability distribution of the data. Also, their method seems incremental over Sinha et. al's work. Computational experiments look promising. 

##########################################################################

Pros: 

- the authors show a concave upper bound on the loss function and minimize that, 
- they show that their method of "noisy adversarial learning" (NAL) has a convergence rate O(1/\sqrt{T}), which is similar to Sinha et al. (2018), but NAL does not need to replace the non-smooth layer ReLU with Sigmoid or ELU to guarantee robustness.
- improved performance in experiments

##########################################################################

Cons: 

1. The authors say that "It is found that when fed with the perturbed instance x (within a L2 ball centered at x_0), a smoothed classifier g(x) = E_z[f(x + z)] with z \sim N (0, \sigma^2 I) can provably return the same label as $g(x_0)$ does.  However, we think such a robustness guarantee cannot ensure g(x0) to be correctly classified as y, resulting in unsatisfying performance in practice." I think there is a language error in this description, but if I understand correctly what the authors are trying to say, the smoothed classifiers are unsatisfying in performance -- however, aren't adversarial perturbations very specific, and therefore, smoothing should actually give more robustness to the model?  

2. "Instead, we evaluate robustness as the worst case loss over the distribution of noisy inputs" - wouldn't the worst-case distribution simply place all the probability mass over the most adversarial example in the neighborhood? 

3. "our approach does not require \ell to be smooth, and thus can be applied to
arbitrary neural networks." -- isn't the smoothness simply coming from the expected loss over distributions "close" to the input distribution? (This is clear later, since they bound the "possible probability distributions" by Wasserstein distances, but very confusing in the introduction.)

4. How loose/tight is the upper bound in Theorem 3? If \gamma*p is large, then the guarantee is almost meaningless.
 
##########################################################################

Questions during rebuttal period: 

 
Please address and clarify the cons above 

 
#########################################################################

Typos: 

"The smoothness of the loss function ensures the problem easy to optimize even for non-smooth
neural networks."  -- grammar

The authors use "P" in the introduction before defining it. \mathcal{P} should be defined as the set of distributions at a bounded distance from P_0!! 

Grammatical error: "But such a question remains open in the randomized regime, where randomized
smoothing can be considered as a contributing effort"

"Our work view the robustness" --> "views" 

"right-hand side take the expectation" --> "takes"
review_title: Promising idea, writing needs work

final_score: rating: 3: Clear rejection
review_content: This paper proposes smoothing the classifier in the distributional robust learning framework by adding random noise to the input. The smoothed distributional robust framework is used to gain robustness against adversarial perturbations in settings where the classifier is originally non-smooth and then smoothed via the additive noise. While the proposed idea can be potentially useful for training adversarially-robust classifiers over non-smooth function spaces, the paper's theoretical formulation seems to reduce to original non-smoothed distributional robust optimization. Theorem 2 also seems incorrect and its proof suffers from several mistakes.  

To see the main issue with the paper's problem formulation, note that Theorem 1 results in the adversarial loss function \phi_{\gamma}= E_Z[ max_x{...} ] which first maximizes over x\in \mathcal{X} (inner operation) and then takes expectation over Z (outer operation). This sequence is also the case in Equation (6) and is the basis of the theoretical and numerical analysis throughout the paper. However, one can see that this objective E_Z[ max_x{...} ] simply reduces to max_x{...} with no expectation over Z. This is because as long as the support set \mathcal{X} is unconstrained, which is the case in Algorithm 1 applying no projections on X, the maximization solution for x+z will be the same given any outcome Z=z. This is a direct consequence of maximizing a strongly-concave objective in \phi_{\gamma} that has a unique maximizer. In fact, I think the opposite order max_x{ E_Z[...] } which hasn't been analyzed in the paper will lead to a properly smoothed optimization problem. I, therefore, suggest redoing the analysis for the properly-ordered max_x{ E_Z[...] }.

Furthermore, Theorem 2 seems incorrect and the constant 2M in the theorem's upper-bound should be replaced with a function of both M and \sigma. In the theorem's proof, Equation (17) implicitly assumes that \sigma=1, whereas this assumption has not been mentioned in the theorem. Also, the step from Equation (22) to (23) mistakenly substitutes 1 with M and obtains a constant 2M instead of M+1, while there are no assumptions on M>1. The theorem needs to be revised since the current version is incorrect. Because of the above issues, I don't recommend this paper for acceptance in its current form. The paper should be revised to resolve these major issues. 
review_title: Official Review

final_score: rating: 2: Strong rejection
review_content: The authors use some of the theory from optimal transport to certify the degree of robustness of an image classifier to adversarial perturbation. The theoretical contributions of the work, however, are largely already present, or easily deduced from results that are either already published or available online in a pre-published format. For theorem I have given a brief overview.  My score reflects a strong concern over the degree of originality of the results presented, particularly considering the authors cite some of the papers in which these results can already be found. I welcome the authors and other reviewers to draw my attention to any contributions in the paper I may have overlooked by mistake.

### Theorem 1
In essence Theorem 1 corresponds to weak Kantorovich duality for the robust optimal transport problem. The best reference for strong Kantorovich duality in this setting is [Blanchet & Murthy (2019)](https://doi.org/10.1287/moor.2018.0936) and the result is easily deduced from Section 2.2.1. More closely the result can also be deduced from Proposition 1 of [Sinha et al. (2017)](https://arxiv.org/abs/1710.10571),  [Kuhn et al. (2019)](https://pubsonline.informs.org/doi/10.1287/educ.2019.0198) also have a variety of results on this topic. Theorem 1 of  [Cranko et al. (2020)](https://arxiv.org/pdf/2002.04197.pdf) additionally qualifies the tightness of the upper bound and relaxes a number of assumptions of some of the aforementioned papers. There are a number of other, related papers by some of the authors mentioned that I have left out. 

### Theorem 2
Theorem 2 is not particularly surprising. In the proof the authors implicitly assume $\ell(\theta,\cdot)$ is twice differentiable and bounded (for all $\theta$). The addition of Gaussian noise is an additional complication, but it does not change things too much. The theorem is unsurprising because if it were not true it would lead to an absurd contradiction with the boundedness assumption.  The strong concavity result in the following corollary is also observed by [Sinha et al. (2017)](https://arxiv.org/abs/1710.10571) (at the bottom of page 2).

### Theorem 3
Theorem 3 was already proven in a significantly more general setting by [Blanchet & Murthy (2019)](https://doi.org/10.1287/moor.2018.0936)  (Theorem 1). Furthermore I am not convinced of the correctness of the proof since there appears to be an assumption that $\gamma$ is sufficiently larger for $\ell(\theta; x) - \gamma c(x,x_0)$ to be strongly concave. And I cannot even find an assumption that at this point $c(\cdot, x_0)$  is assumed so much as convex for a choice of $x_0\in\mathcal{X}$. 


review_title: Concerning issues of novelty

final_score: rating: 2: Strong rejection
review_content: This paper studies the problem of certified robustness in adversarial learning. In a nutshell, they apply the randomized smoothing technique to the distributional robustness certificate proposed by Sinha et al. (2018), thereby relaxing the smoothness assumption required therein so that the ReLU network can be applied. Based on this new formulation, they derive the upper bound on the worst-case population loss and develop an algorithm with convergence guarantees. The results on tested on MNIST, CIFAR-10 and Tiny ImageNet.

The topic is definitely important and the authors did a good job of explaining their framework. Nevertheless, unfortunately, I think the proposed methodology seems rather straightforward and does not provide many new insights into this area. Besides, there are numerous careless flaws in the paper.

1. Theorem 1 appears to be a standard result in distributional robust optimization and it is unfortunate that the authors did not recognize it. See, for example, Kuhn et al. (2019) (https://arxiv.org/abs/1908.08729).

2. Theorem 2 and Corollary 1 appear to be a standard result in randomized smoothing. Besides, the proof is not rigorous -- it takes for granted that the $\hat\ell$ is twice differentiable.

3. The statement of Theorem 3 contains an obvious typo. The left side and the right side are no different from each other -- the only difference is the integration variable: one is $\hat{x}$ and the other is $x'$.

That is to say, all three major theoretical results are either straightforward corollary from existing results or contain flaws. 

4. The algorithm proposed in Section 3.2 is problematic. In particular, in equation (6) and Alg.1 line 3-6, when $\cal X$ is a normed vector space, the value of the inner supremum does not depend on $z_{ij}$ simply via a change of variable from $x+z_{ij}$ to $x$. I think the correct version should be 
$$
  \frac{1}{n} \sum_{i=1}^n \sup_{x\in\cal X} [ \frac{1}{s}\sum_{j=1}^s \ell(\theta;x+z_{ij}) - \gamma c(x,x_0^i) ].
$$

5. As for the numerical experiment, it is unclear to me how $\gamma$ is chosen, and in particular, does such choice make the inner supremum of (6) a strongly concave problem?

Given these many issues that are not easy to fix, I would encourage the authors to carefully revise their manuscript and resubmit to another conference.

review_title: A randomized smoothing distributional robust certificate

Meta-review: The authors present a framework for deriving distributional robustness certificates for smoothed classifiers under perturbations of the input distribution bounded under the Wasserstein metric. 

Several authors raised concerns regarding the correctness of results presented in the initial version of the paper. While these were addressed during the rebuttal, the reviewers remain concerned about the novelty of the work relative to prior work, in particular the following papers:
https://arxiv.org/abs/1908.08729
https://arxiv.org/pdf/2002.04197.pdf
https://doi.org/10.1287/moor.2018.0936
and the author responses during the rebuttal did not sufficiently address these concerns.

Hence, I recommend rejection.

Decision: Reject