Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work highlights the existence of imbalanced gradients as a phenomenon that may hinder optimization of gradient-based adversarial attacks and, thus, give a false sense of robustness. Imbalanced gradients may occur as the attack objective consists of the difference of two terms (typically, the outputs of the network on two different classes). When the gradients of these two terms have opposite directions, the attack optimization may get easily stuck in a suboptimal local optimum, thus decreasing the attack effectiveness.
To overcome this issue, the authors propose a simple variant that can also be applied to existing attacks, based on following the gradient of each term in the objective iteratively, rather than considering their combination.

The paper addresses an important issue in adversarial machine learning, i.e., the security evaluation of a defense. In fact, the performance of many proposed defenses has been overestimated due to the weakness of attacks used in the evaluation. One of the causes of this is the inability of gradient-based attacks to correctly perform the optimization.

The paper provides an exhaustive analysis and formulation of the problem of imbalanced gradients, for which also a heuristic metric is provided. This phenomenon is then evaluated on a set of state-of-the-art defenses and attacks. 

The authors propose an attack variant inspired from PGD and MT attacks, using the difference of class logits as the objective (i.e., the so-called margin loss). Then, the optimization algorithm works as follows. For each restart, in the first half of the optimization process, only one of the two terms of the margin loss is alternatively used, while in the second half, the whole margin loss is used. The attack formulation and algorithm are clear.
It is important to remark that rather than proposing a new attack framework, the authors actually only propose an optimization variant of the existing PGD and MT attacks and run these attacks with the proposed changes. As correctly stated by the authors, indeed, their proposal can be viewed as an initialization strategy for adversarial attacks (rather than a completely novel attack).

Experiments are reproducible and consider many state-of-the-art attack algorithms and defenses. However, the comparison with other attacks does not seem totally fair. The same hyperparameters (step size, number of iterations and restarts) are used for PGD, C&W and MD attacks (same also for ODI, MT and MDMT), and default hyperparameters are used for the AutoAttack framework. This is problematic, as each attack should be tuned independently, and the choice of hyperparameters should be justified (a common criterion for hyperparameter tuning may be selected, and a grid-search over the attack hyperparameters should be conducted). As shown in many other papers, the attack hyperparameters play a key role in correctly optimizing the attack objective (even single data points can require different hyperparameter tuning).

Another limitation of this work is that it is restricted solely to WideResNet architectures and CIFAR10.

Furthermore, the computational efficiency of the attack is not discussed. Although it is not a primary aspect, it should at least be mentioned when it is compared to other attacks, since it is potentially slower as it might require more iterations and restarts. To be fair, attacks should be even compared under the same complexity (e.g., number of queries to the target model).

In the last column of Table 1, the performance difference between MDMT and PGD is reported. However, this could lead to an overestimation of the attack performance: for a fair evaluation, the MDMT attack should be compared to the stronger attack available at the state of the art, according to the experimental evaluation conducted by the authors, and not to PGD (which has been shown to perform worse than more recent attacks in many papers – e.g., AutoAttack).

review_title: Review for Imbalanced Gradients: A New Cause of Overestimated Adversarial Robustness

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper identified the issue of Imbalanced Gradient, verified through some recent defense methods. Motivated by such an issue, a marginal decomposition (MD) attack is proposed to offer a stronger robustness measure. In general, the paper is well written, and the studied problem is interesting. The MD perspective explains why label smoothing may provide insufficient robustness.

My comments are listed below. 

1)  In Sec. 3.2, why are the first K/2 iterations used to maximize the individual margin term and then update the entire loss? What will happen if the scheduling is the opposite: updating the entire loss at the first K/2 iterations, then individual terms？Some ablation studies or explanation should be provided.

2) Does the proposed stronger attack offer a stronger min-max defense? Suppose that the ordinary PGD attack is replaced by an MD attack during min-max training, will it offer better overall robustness? The general question to ask is: In addition to root cause analysis on the ineffectiveness of some existing defense methods, what are the additional benefits of the newly proposed MD attack?

3) Does it seem that the MD attack has to run over more iterations than the PGD attack, leading to extensive computation cost?

4) What is the possible effect of the MD attack on the generated perturbation pattern? In the black-box setting, will the MD attack be more query-efficient than a commonly-used PGD black-box attack?


Post-rebuttal:

I am mostly satisfied with the authors' response. After reading other reviewers' comments, I shared a similar concern on the marginal contribution. However, the newly added black-box result is a good addition to the paper. Thus, I keep my original rating toward the positive side. 


review_title: Review report 

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper introduces and analyses the possibility that the effectiveness of PGD-based adversarial attacks might be reduced by imbalanced gradients between the terms of the margin losses commonly used. As a remedy, it also proposed a new scheme for PGD attack, where for the first half of the iterations a single-term loss is optimized, before falling back on the the usual margin loss. The authors test the hypothesis of imbalanced gradients, introducing a new metric, GIR, and the newly proposed attack in two versions, MD and MDMT, on several defenses based on adversarial training.

Pros
1. Understanding why some adversarial defenses make some versions of PGD (e.g. with cross-entropy or margin loss) overestimate, sometimes even largely, robustness is an interesting direction, and the proposed explanation of imbalanced gradients is, as far as I know, novel.
2. The proposed attacks are effective against many defenses.

Cons
1. It is not clear what the proposed metric Gradient Imbalance Ratio (GIR) captures and how it is connected the scheme of MD. In fact, the GIR values for JARN-AT1, Sense and MMA, which are not robust, especially against MD, are smaller than for MART and similar to those for UAT, which are instead robust and little or not affected by gradient imbalance according to the results of the MD attacks. Moreover, FeaScatter and MART have similar GIR, but the improvement of MDMT compared to standard PGD is >31% for the former but only around 5% for the latter.
2. In the comparison with other methods (Table 1) the results of AA seem worse than reported in the latest version of (Croce & Hein, 2020), which report lower values of robust accuracy than MDMT for the same defenses. Also, when considering only individual attacks, it'd make sense to include FAB, as in Sec. 4.3 and Appendix C the authors state that it is the most effective in AA and partially avoids the problem of imbalanced gradients.
3. In the MD attack, the first half of the iterations have step size set to $2\cdot \epsilon$, which is than decreased in the second stage. This seems similar to what Auto-PGD does.

Overall, the hypothesis the imbalanced gradients might be a cause of overestimation of robustness is reasonable and worth exploration, but the metric proposed by the authors does not clearly capture this, and the attacks which should overcome that issue are not clearly better than existing methods.

---
Update after rebuttal

I thank the authors for the response. After reading it, the revised version and the other reviews, the concerns expressed in the initial review are still valid.

Then, I keep the initial score.
review_title: Interesting hypothesis to be validated, more thorough comparison needed

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper explores constructing adversarial examples in classification, in order to create better robustness metrics for general classifiers. An attack is defined as an epsilon-perturbation of the learned parameters which create a model whose performance is much degraded. The premise of this paper is to use gradient imbalance as a way of creating perturbation targets, which are claimed (and shown numerically) to better fool networks that are trained to withstand more traditional attacks, and can be used to create more robust models in general.

I think the premise is well-motivated, and the results look promising. However, I am having quite a bit of trouble understanding the main method. From the margin loss given, $l(x,y) = z_{\max}-z$, which seems similar to the loss in logistic regression, with gradient  $\nabla \ell(x,y) = yx^T(1-\sigma(yx^T\theta)$. (It is not entirely clear what $z_{\max}$ and $z$ correspond to in the general case.) I am not clear as to why we would expect label balance, e.g. why would $1 = \sigma(yx^T\theta)$? It is also not clear why, when one term dominates the other, that it is a form of nonrobustness. 

Alternatively, the interpretation may be that a particular training sample is affecting the model more than the others. That would seem like a more reasonable metric of fallibility, but I don't think that's what the authors intend.

Overall, I do think the paper can be improved if written more clearly, with terms and concepts defined. I guessed that $\Pi$ is projection, and other terms like imbalance ratio are buried in text and hard to find. But, I find the method overall simple and elegant, so with continued discussions with the authors to clarify what exactly is happening, I would raise my score. 
review_title: Didn't quite understand the method, but it looks promising

Meta-review: The paper identifies a subtle gradient problem in adversarial robustness-- imbalanced gradients, which can cause create a false sense of adversarial robustness. The paper provides insights into this problem and proposes a margin decomposition based solution for the PGD attack.

Pros:
- Novel insights into why some adversarial defenses may make some versions of PGD overestimate robustness.
- Proposes a method that is motivated by such findings of imbalanced gradients.
- The proposed attacks are shown effective across a wide range of defenses.

Cons:
- The proposed gradient imbalance ratio could be better motivated: i.e. how is it connected to the scheme of margin decomposition?
- Limited novelty in the attacks: i.e. variant of the existing PGD and MT attacks with some proposed changes.
- Various concerns with experiments (i.e. stepsize tuning, choice of hyperparameters).

Overall, the reviewers felt that there were some interesting ideas and directions presented in the paper; however, the reviewers also felt that the contribution was of marginal significance and more confidence in the various components (i.e. how the proposed metrics measure the imbalanced gradient effect and various concerns in the experiments) would have made the paper more convincing.
Decision: Reject