Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The setting is robust learning to perturbations at test time (adversarial examples), where instead of minimizing the average loss, the goal is to minimize the loss of the class with the lowest accuracy.
That is, instead of a min-max problem, there is another maximization component over the classes.

This is motivated by an example that shows a larger variance in losses between classes than in the standard setting.

The authors suggest a method from online learning - exponential weight in the bandit setting (that is - Exp3). 
main_review: -I'm not sure what do you mean by saying that the adversary is "choosing the class". There is the magnitude of noise, and the adversary maximizes the average loss of the learner. It doesn't choose a specific class (although some might be more vulnerable than others)

-The error across classes is not perfectly uniform in the adversarial training process, but this is the case (sometimes) in the standard setting. What makes the adversarial training process different?

-In the suggested method, you can perform exponential weights with full information, I don't see the reason for using bandit feedback (and it is not explained).

-The technical novelty is only marginally novel and quite straightforward.

-What about the following baseline - you have the empirical error, so perform an ERM with that "penalize" more some classes.
[I guess the Hedge should work better]
summary_of_the_review: My vote is - reject.
I mentioned my concerns. It is possible that I did not assess the contributions correctly, I am willing to read the other reviews and reconsider my score if they convince me otherwise.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Observing that existing adversarially-trained classifiers have different class-wise model performance, this paper aims to protect the most vulnerable class against an adversary who can smartly pick which class to attack. Built upon on a classical Bandit algorithm and adversarial training method, it proposes an algorithm called “Class Focused Online Learning”, which adaptively reweights the class-wise loss function over the training epochs. In addition, the paper proves a convergence guarantee for the worst class loss and provides empirical evaluations of their method on benchmark datasets.

main_review: While the proposed method is intuitively reasonable for the main purpose of “protecting the weak”, I have several concerns regarding the motivation of the paper and the empirical results. 

1. In terms of the motivation, I do not see a strong motivation to protect the weakest class, given the fact that the average robust accuracy is less than 50%. That said, from the perspective of an adversary, arbitrary picking any class can suffice its attack goal. Perhaps, if we assume attacking difference class incurs a different benefit or cost for an attacker, there may exist a particular user case for protecting the weakest class.

2. The performance of the baseline methods presented in this paper is not the state-of-the-art in adversarial robustness literature. In particular, the baseline method (ERM) for CIFAR-10 presented in Table 2 only achieves around 0.74 in clean accuracy and 0.47 in robust accuracy, whereas the state-of-the-art clean accuracy and robust accuracy are over 0.85 and 0.55, respectively [1, 2]. Even the original method of TRADES [3] you implemented should achieve a much higher accuracy than what you presented in Table 2. 

[1] Uncovering the Limits of Adversarial Training against Norm-Bounded Adversarial Examples, Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, Pushmeet Kohli

[2] Reliable Evaluation of Adversarial Robustness with an Ensemble of Diverse Parameter-free Attacks, Francesco Croce, Matthias Hein

[3] Theoretically principled trade-off between robustness and accuracy, Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. 

3. Compared with Focused Online Learning (FOL), I do not see an obvious improvement of using your proposed CFOL method. Both the average clean and robust accuracies of CFOL are less than those of FOL by 0.04. Could you clarify why there is an average performance drop?

Other comments:
1. Theorem 1 provides a convergence guarantee for the worst class loss. Theoretically, if we have enough empirical samples, the proposed method should achieve a very small loss (correspondingly, a high accuracy) if T is sufficiently large. Can you clarify why the empirical results provided in Section 5 seem not reflect such theoretical claim?

summary_of_the_review: 
The proposed method combines an online learning algorithm and an adversarial training approach, which is intuitive and new. However, the motivation for protecting the weak in an adversarial setting is not well-explained and justified in my perspective. In addition, the baseline results presented in the paper are far below the state-of-the-art and there does not seem to be a clear advantage of the proposed method over existing approach. Therefore, I suggest a reject for this paper given the abovementioned concerns.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors present a method for maximizing minimum class-wise accuracy in the $\ell_p$-adversarial setting. The proposed method uses an online learning algorithm (exponential weights) to choose classes adversarially at train-time to sample examples from (in place of randomly choosing examples from the given data distribution). The authors find their algorithm can effectively increase the class-wise worst-case accuracy on a number of standard datasets (CIFAR-10/100, STL10) in the $\ell_\inf, \epsilon=8/255$ threat model.
main_review: Strengths:
- Easy to understand writing
- Straightforward, well-motivated method
- Experimental results correspond with claims
- Appropriate baselines
- Experimental results outperform baselines

Weaknesses:
Clarity: 
- "ERM" generally refers to algorithms that perform empirical risk minimization and adversarial training does not perform empirical risk minimization. Canonically ERM also refers to the standard training regime. The standard adv training regime should therefore not be referred to as ERM (this a problem throughout the text).
- Table 2/3: $\mathcal{A}$ canonically refers to an algorithm, so $\mathcal{A}_{\text{rob}}$ is confusing notation (one would assume it refers to a robust training algorithm); this should be renamed to another symbol and perhaps labels could be added to the table for further clarity.
- In Table 2/3 it would be good to cite the methods/name them as they are not standard acronyms people use.
- The writing can is often overly verbose or disorganized. For example, in the DRO section of the related work, other seemingly unrelated techniques are sandwiched between paragraphs specifically about DRO. Section 4 could also be considerably condensed (and renamed, as the section describes an experimental setup choice not an application of the algorithm).
- What do the bounds in Table 2/3 represent exactly?

Related work/baselines: 
- It would be good to compare with relevant DRO literature: in [0] the authors propose an online learning technique for optimizing worst-case subgroup error (one instantiation of this could be subgroups = labels). 

Small fixups:
- Missing space after (2)

[0] https://arxiv.org/abs/1911.08731
summary_of_the_review: The paper is easy to understand, presents a straightforward/well-motivated method, and backs claims with corresponding experimental results. The presented methods also outperform the baselines. However, the paper has relatively minor issues with clarity and incomplete related work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper points out that there could be applications where the worst class accuracy could be critical -- for example, the class with the worst class accuracy can be the main target for the attacks and that the difference between the worst robust test accuracy of a class and the average robust test accuracy can be large (also pointed out independently in Tian et al. (2021)). 

Motivated by this, the paper proposes a solution to use the Exponential-weight algorithm (Auer et al., 2002), where, as the empirical distribution is taken the adversarial distribution over classes, resulting in a method called Class Focused Online Learning (CFOL).
The proposed CFOL method is based on the Focused Online Learning (FOL) (Shalev-Shwartz & Wexler, 2016) method, which does not take the class label into account.

The authors show empirically that CFOL consistently improves the worst class accuracy on CIFAR-10, CIFAR-100, and STL10.
Moreover, the authors provide high probability convergence guarantees for the worst class accuracy.
main_review: # Strengths
- Although the proposed method builds on existing works (Shalev-Shwartz & Wexler, 2016; Auer et al., 2002), the novelty is relatively high: to my knowledge, there exists no AT method that focuses on the class with the worst accuracy, nor combines online learning for this purpose. 
- The paper is well written (best writing in my batch), precise, and I enjoyed reading it. I like that the authors (where convenient) first give intuition and then present the result, which helps to follow more easily. 
- It does a nice balance between theoretical analysis and empirical evaluation.
----
# Weaknesses
- The paper does a very nice trade-off between theory and empirical analysis. However, as a potential direction for improvement, the empirical evaluation could be more on par with AT literature, for example:
   - analysis with different radius of the ball, i.e. plots with varying $\epsilon$ 
   - how robust is the method to other attacks (e.g. AutoAttack), is the catastrophic overfitting improved, etc.
- The main result (Thm 1) is for an ensemble of size n, while (if I understood well) the experiments are with one model. The authors mention that a single model suffices, but if I am correct there are no results with an ensemble. Verifying Thm 1 empirically, e.g. showing how $n$ impacts final performances would connect better the result with the experiments. 
----
# Recommendations
- Since Tian et al. (2021) is a very recent work I do not take this into account for my rating, but other than that it might be helpful for the audience to include a comparison with it (either theoretical insight about advantages/disadvantages, or empirical comparison on CIFAR-10).
- The abstract leaves it somewhat unclear what is the online learning aspect of the method (included in the title), maybe adding a sentence would be nice. 
- Write the requirement $C \geq k \log k $ in Thm 1 more explicitly as a separate assumption before stating Thm 1.
- Typo: Fig.3 noteable $\rightarrow$ notable 
- Since the main empirical results use temporal ensembling (TE) add a detailed description of it in the App. for completeness

----
# Questions
1. Fig. 1: Does the robust test accuracy of clean training (left) follow a non-uniform trend across the classes? It would be interesting to see if this observation from Fig.1 is (not) a result of AT.
2. If I am correct, temporal ensembling (TE) is used for all methods. This raises the question if the proposed method works well only in this setup with TE, and for completeness, it would be nice to point out this to the readers. Could the authors provide results without TE on CIFAR-10?

summary_of_the_review: The paper has several advantages 
(i) points out an overlooked problem in AT (to my knowledge), 
(ii) proposes a novel method for the problem with guarantees
(iii) does a nice trade-off between theoretical analyses and empirical evaluation, and
(iv) it is well written.
There are two main directions for improvement theoretically and empirically, e.g. better connection between the theoretical result and the empirical analyses, more exhaustive empirical evaluation on par with AT literature. Nonetheless, I found the paper very interesting and I think it is relevant for the ICLR audience.
I am happy to raise my score if I misunderstood and the above comments are arguable, or if the authors provide improvements (see questions and comments above).
review_title: null

Meta-review: The paper looks at the worst-class adversarial error for multi-class classification problems. The question is given a certain level of adversarial error on average, is it possible that some classes have adversarial error significantly worse than average? And if so, is this a problem? I agree with the authors that there are applications where such an imbalance could be problematic; other than the examples provided by the authors I can also think of this being important from a point of view of fairness, depending on what exactly the class labels represent. The reviewers have raised the question of low accuracies reported in the empirical results compared to the state of the art on those datasets for adversarial learning. I share these concerns -- especially it's worth understanding whether more accurate models also have such an imbalance, or whether this imbalance is a result of incomplete training or models that are not representationally powerful enough. While I agree with the authors that 'state of the art' results' are not required for ICLR submissions, especially those making conceptual contriubtions, in this case I think further experiments may be needed in addition to addressing the other questions raised in the reviews. The authors acknowledge that they have made significant revisions in response to the reviews, but I think that would require a fresh review cycle.
Decision: Reject