Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers a threat model where an attacker attacks a subset of the test data of a classification system. To develop a defense, the formulate the learning problem for the classier as a min-max optimization where the loss is minimized over the most adversarial subset of a particular cardinality. The authors show that the inner optimization that requires a subset selection (for a given $\theta$) us NP-hard. To solve this efficiently, they leverage a stochastic distorted greedy algorithm by (Harshaw et. al. 2019) and is able to give an approximation guarantee for the overall adversarial learning function for a particular class of loss functions. The authors then conduct a suite of experiments to showcase the effectiveness of their approach against existing defenses in the threat model they consider.
strength_and_weaknesses: ### Things I liked

- The paper addresses an interesting problem, clearly explains the difficult of the problem and proposes a solution with guarantees when certain assumptions hold.

- The authors conduct a reasonable set of experiments and provide logical choices of the baselines, attack methods, etc.

- The mix max over the hyper-parameter choice is nice little trick.

### Things that need clarification / improvement

- The empirical results are weak in several aspects. 
  - The proposed method, ROGET, mostly outperforms other defenses (which are designed for the entire test-set) on clean test-data accuracy. It is at times the worst performing method of perturbed test data. There are also sentences like "Tuning ρ would easily improve the robustness, as shown in additional experiments in Appendix H" which surprises me on why would the authors not show their best results as part of the main paper?
  - If there is some knowledge about the true subset selection strategy at validation time, other methods (designed for all test attacks) outperforms ROGET.
  - As the amount of test data poisoned grows, the accuracy gains become minimal.

- Given the inner optimization is itself a difficult problem that admits an approximation, the authors should highlight the time/resource costs incurred by their defense vs. existing defenses. Beyond accuracy, this is an important metric to consider.

- There is no clear association between the assumptions made in proofs and the function used in practice. For example, is categorical-cross entropy a Polyak-Lojasiewicz Loss function? If not, the approximation guarantees do not hold here. This disrupts the flow of the paper somewhat.
clarity,_quality,_novelty_and_reproducibility: The paper addresses an interesting setting and seems reproducible. The theoretical development of the work is nice, but empirical results are weak.
summary_of_the_review: See above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers a new type of adversary that chooses to only perturb a subset of data. The authors propose a defensive strategy that is formulated as a minimax problem that involves a worst-case subset selection procedure. This paper uses a greedy algorithm to realize the worst-case subset selection. The empirical results demonstrate the proposed method can gain the best overall accuracy on the selected adversarial data and unselected benign data in most scenarios. 
strength_and_weaknesses: Strength
+ The new attack setting that adversarially selects a subset as an adversarial set is interesting and novel. The experimental results show that previous adversarial training methods are vulnerable to this adversarial subset attack. The proposed method can achieve the best performance even under the adaptive attack (subset selection with worst-case hyperparameter setup).
+ The proposed iterative greedy algorithm is well motivated by the theorem. The proposed method is compatible with variants of adversarial training methods.

Weaknesses (Questions)
- It could be better to show the results of the proposed method with variants of adversarial loss such as ROGET with TRADES loss to validate the compatibility of the proposed method.
- I have a concern regarding the adversarial subset attack. The adversary can choose to adversarially perturb those incorrectly-predicted data. This seems to be a realistic attack and could be viewed as the lower bound of the robust accuracy under the adversarial subset attack. It would be better to present the results of this type of attack.

clarity,_quality,_novelty_and_reproducibility: This paper is well-written and organized. The proposed method is theoretically motivated and novel. The authors provide the training details and the algorithm, which can help people to reproduce.
summary_of_the_review: This paper investigates a novel attack where the adversary only chooses to perturb a subset. The authors propose a defensive method that makes the model robust against adversarial subset attacks.  This paper is well-written and novel. Thus, I would like to accept this paper though I have some minor questions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Defending against all perturbed instances is the target of the most current defense mechanisms, and yet in practice only a subset of instances might be selected by the attacker. This paper aims at a new defense mechanism to minimize the worst case loss across all subsets. To solve this optimization problem, the authors design a group of algorithms that admits approximation guarantees for both convex and non-convex (under Polyak-Lojasiewicz condition) objectives. The paper also gives some theoretical analysis of the proposed method. In experiments, the paper shows that the proposed method outperforms SOTA methods on both FMNIST and CIFAR-10.
strength_and_weaknesses: Strength:
- The paper is clearly motivated.
- The paper is well written and easy to follow.

Comments:
- I am a bit worried about the empirical significance.
   1) As in both Table 1 and Table 2, the proposed method is not the best performer in terms of perturbed robustness. 
   2) As in Table 18-20, on CIFAR-100 the proposed method, although achieved second best in most cases, the gap to the best performer is pretty large around 5% in terms of overall accuracy. I have concerns about the scalability issue, that is the proposed method only perform well on small datasets? Does it have the ability of scaling to harder dataset, e.g., Tiny-ImageNet?
- I would suggest the authors to provide more related work. I checked the appendix, however, I didn't see the related work of worst-class problem and its application in adversarial robustness. The authors are also suggested to compare with those in Table 3.
- Fig 5 shows the percentage of instances chosen for perturbation, from 5% to 25%, I would suggest to extend axis all the way to 100%, to clearly show the transition power point of the proposed method. If possible, comparing more figures over different datasets would be even more interesting.
clarity,_quality,_novelty_and_reproducibility: The selected-subset robustness problem is important to the community and the proposed method looks new to me.
summary_of_the_review: The paper is well-motivated. However, I have concerns on the empirical significance, which makes the paper marginally below the threshold.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper tackles the robust training problem of neural networks. In usual scenarios, the adversary chooses a single data point and perturbs it to be misclassified. On the other hand, the adversary in this study chooses a subset of data points and perturbs them to be misclassified. The goal is to minimize the average loss for all the perturbed and non-perturbed data points. The authors present an algorithm that alternately finds a subset to be perturbed via the greedy algorithm and minimizes the average loss via SGD. This algorithm is validated to be perform well both theoretically and empirically.
strength_and_weaknesses: Strengths:
Since deep neural networks are practically used in our society, everyone acknowledges the importance of robust training of neural networks. However, as the authors say, the existing frameworks for robust training are too pessimistic, and often sacrifice its average performance for non-perturbed data. To overcome this issue, this paper considers a setting in which the adversary can perturb a small subset of data points. The proposed algorithm is an alternating method with greedy subset selection and loss minimization, which is not so surprising, but its performance is supported by theory.

Weaknesses:
Although the problem setting is novel and the algorithmic idea is nice, the theoretical and empirical results are not so outstanding. 
On the theory side, the main theorem (Theorem 4) is not always meaningful. Theorem 2 states that $\lambda R(\theta)$ must be large to make the submodularity ratio $\gamma^*$ sufficiently large. On the other hand, if $\lambda R(\theta)$ is large, then $\kappa$ becomes small, and then $[1 - (e^{-\gamma^*}+\delta) / \kappa]^{-1}$ might be negative, which makes Theorem 4 meaningless. However, the problem is motivated by practice and I do not think the theoretical weakness is so problematic.
As the experimental results show, the proposed algorithm does not always outperform the existing algorithms. However, I think the authors sufficiently discuss the advantages of the proposed algorithm.
It would be better to revise the proofs since they contain small mistakes such as:
- $q \mu \beta \frac{|S \cup k|}{|S|}$ in the inequality (32) should be multiplied by $L_\phi$.
- $\sum_{i \in S \cup k}$ should be added before the last $\mu$ in (35).
- $q \mu \beta$ in the inequality (36) should be multiplied by $L_\phi$.
- $-\delta$ in the numerator should be replaced by $+\delta$ and $+\delta$ in the denominator should be replaced by $-\delta$ in the right-hand side of (63).
clarity,_quality,_novelty_and_reproducibility: Clarity: The main concept of this paper is clearly written. The details of the theoretical derivations contain several mistakes as mentioned above.
Quality: The presentation quality is very good. The experimental results are clearly illustrated.
Novelty: The problem setting in which the adversary perturb a subset is novel and practically useful.
Reproducibility: The authors provide the full proofs and the codes for reproducing the experiments.
summary_of_the_review: This paper proposes a new robust training framework and an algorithm with a theoretical performance guarantee. The concept is novel and practically useful, but the theoretical results are not so strong and the proposed algorithms do not always outperform the existing algorithms.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors introduce an interesting new setting in the context of adversarial robustness, in which the attacker is only allowed to perturb a subset of the data samples, but not all. This weakening of the attacker leaves the possibility of maintaining better overall accuracy but a challenge remains in that the subset to be selected by the attacker is a priori unknown. The authors cast this training problem as a min-max game involving worst-case subset selection along with optimization of model parameters, rendering the problem NP-hard. To tackle this, they first show that, for a given learner's model, the objective can be expressed as a difference between a weakly submodular and a modular function. They then use this property to propose an iterative approximation algorithm. Experiments show that the proposed method obtains better overall accuracy compared to several state-of-the-art defense methods for different adversarial subset selection techniques.

This is an interesting, novel setting; it is also very interesting to see that the inherent optimization can be cast into a combinatorial framework that comes with guarantees. That said, the reviewers found many aspects of the paper lacking, and have provided extensive feedback to the authors on how to improve their paper. I will list a few here:

1) The NP-hardness proof is wrong; the reduction should be inverted. 
2) Baselines are indeed not optimized for the overall accuracy. However, baselines could be slightly modified targeting for the overall accuracy to make a fair comparison.
3) Theoretical assumptions are strong and could be weakened
4) Given attack examples are only 10% of the test set, ROGET seems to improve accuracy on the 90% clean dataset and appear better on overall accuracy (as we scale robust accuracy down in this calculation). This does not really showcase ROGET as a good defense; rather it capitalizes on the 90% clean examples to improve the overall accuracy.
5) ROGET may not provide a stable top-performance solution. When , if just looking at overall accuracy, as authors suggested, RFGSM-AT consistently outperforms ROGET(PGD) on CIFAR10, while TRADES outperforms ROGET(AdvGAN) on FMNIST over overall accuracy that considering white-box attack. Moreover, tuning rho is tricky and leads to more complicated cases. The best rho on different datasets changes in scale, e.g.,  on CIFAR10 and  on FMNIST, and the performance gap between different  settings, e.g.,  and  on FMNIST, making it less effective to provide a stable top-performance solution.
6)  SOTA architectures and attacks should be used (e.g., TRADES-trained WideResNet as architecture and AA as white-box attack).
justification_for_why_not_higher_score: Please see above.
justification_for_why_not_lower_score: NA
Decision: Reject