Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper seeks to theoretically formulate the problem of learning a classifier which is robust against unseen attacks—that is, a threat model which is not used at training time. The authors define a threat model as a set of allowed perturbations to an input, and distinguish a source threat model used for training versus a target threat model used for evaluation. They characterize the target threat model as "unseen" if it is a strict superset of the source threat model for all inputs. Then, the generalization gap between robust error on the training set using the source threat model and robust error on a test set using the target threat model can be decomposed into a standard sample generalization term and a new threat model generalization term. The authors show that the second term can be bounded if there is an "expansion function" which controls how much more "variation" the classifier exhibits on the target threat model as compared to the source threat model, and give examples of when such an expansion function exists or does not exist. Finally, the authors propose a method AT-VR which explicitly regularizes the variation on the source threat model, which according to their theory should improve generalization to unseen threat models. They show that it does empirically improve unseen threat model accuracy across various attacks and datasets.
strengths_and_weaknesses: Strengths:
 * The problem addressed—adversarial robustness against unseen threat models—is both difficult and understudied compared to other areas of adversarial robustness. The formulation proposed in this paper seems helpful to concretize the problem and provide directions for further research.
 * I particularly appreciated the formulation of the expansion function, which is empirically measurable and can help practitioners working on this problem to diagnose why their model may not be generalizing across threat models.
 * The empirical results seem strong—the proposed method AT-VR generally helps across many threat models and rarely hurts. I also appreciate the very extensive experiments with other threat models and alternative training methods in the appendix. 

Weaknesses:
 * While the theoretical bounds using variation and expansion functions give some intuition, they are probably vacuous for reasonable learning problems. Furthermore, none of the bounds on the expansion function apply to neural networks (at least to my understanding, correct me if I'm wrong).
questions:  * Is there any empirical explanation you can give for why the expansion function in practice is linear with low slope, even though your theory doesn't apply directly to neural networks? For instance, suppose you take the linear approximation of a trained network around each test point and apply Theorem 4.7 to get an approximate local expansion function based on the linear approximation, then take the average over the test points. Does this give you something similar to what you observe empirically in, e.g., Figure 2?
 * Can you compute the expansion function slopes for non $\ell_p$ threat models? For instance, it would be interesting to see what the expansion function looks like for $\ell_\infty$ to StAdv or vice versa. This would also potentially be a more compelling case for expansion functions since $\ell_p$ threat models are somewhat similar already (since one can bound any $\ell_p$ norm by a multiple of an $\ell_q$ norm). Instead, looking at two very different threat models like $\ell_\infty$ and StAdv or $\ell_2$ and StAdv would give more evidence that expansion functions exist between many threat models. Another interesting example would be measuring the expansion function between LPIPS-based attacks and $\ell_p$ or StAdv attacks.
 * What happens if you plug in the expansion function slope calculated empirically into Corollary 4.4? Does this give a reasonable estimate for the adversarial error on the target threat model? If not, what do you think accounts for the gap?

Small thing: on line 158, I think you can only conclude that $L_T(f) \geq L_S(f)$, not that it is strictly greater. For instance if $f$ outputs the constant uniform distribution over classes for every input, then $L_T(f) = L_S(f)$ for any $S, T$.
limitations: I think there are a couple of limitations that the authors did not discuss. While these limitations don't detract too much from the paper's significance, it would be good to mention and address them:
 * The method AT-VR seems to be much more expensive than regular adversarial training (it should take 3x the computation if I'm understanding correctly since one needs to compute gradients wrt three inputs instead of one for each attack step). I don't think the authors mention this.
 * As I mentioned above, the theoretical bounds on the expansion function are not directly applicable to neural networks. Furthermore, it's unclear if the empirical expansion functions predict empirical performance using the bounds in the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the model robustness extension to unforeseen perturbations. The main contribution of the paper is a generalization bound for unforeseen threat models with the knowledge of a source model. The paper further provides a training method for achieving better unforeseen robustness using the generalization bound.
strengths_and_weaknesses: Strengths: Achieving a generalization bound to unforeseen attacks is challenging and interesting. The paper provides both theoretical results and experimental results.

weaknesses: The theorems are not clear; The experimental results are weak; The comparisons are insufficient.
questions: Questions about theorems:

1. I don't fully understand the $\hat{L}_S(f)$. Is it the AT-VR loss in the paper?

2. How can theorem 4.2 guarantee that both \pho and \sigma_G are small enough to make the first term <<1?

3. The paper does not mention too much about the sample generalization gap, and the results are all on the threat model generalization gap. Is it possible that the threat model generalization gap is decreasing while the sample generalization gap is increasing?

4. The existence of the expansion function guarantee seems very weak.

Questions about experiments:

1. AT-VR seems much more computationally expensive than AT.

2. The paper needs to compare its method with state-of-art robust training. Only comparing to AT (2017) is not enough. 

3. The experimental results are weak. For example, the clean acc drops 10% compared to AT. Note that AT itself has a significant clean acc drop. This trade-off is not acceptable.

4. Why VR is applied on logits instead of the input of the fully-connected layers?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies a scenario where the threat model assumed by the defense during training (i.e. source threat model S) is different from the threat model used during test time (i.e. target threat model T). It assumes that the target threat model is unknown and is stronger than the source threat model (i.e. the target threat model T is a strict superset of the source threat model S). It formally defines the problem of learning and generalization with an unforeseen adversary. It derives a generalization bound that relates the generalization gap between source and target threat models to variation of the feature extractor, which measures the expected maximum difference between extracted features across a given threat model. Based on the generalization bound, it proposes adversarial training with variation regularization (AT-VR), which reduces the variation of the feature extractor across the source threat model during training. The experimental results demonstrate that AT-VR can lead to improved generalization to unforeseen attacks during test-time compared to standard adversarial training. 
strengths_and_weaknesses: I think this paper has the following strengths: 

1. It studies an important problem: generalizing the robustness to a stronger unknown target threat model during test time. Existing works usually assume that the threat model during test time is the same as the threat model during training time, which is not realistic. This paper makes a key contribution by formally defining the problem of learning and generalization with an unforeseen adversary. 

2. Under the framework for generalizability, it derives a generalization bound for generalization across threat models. The bound relates the generalization gap to a quantity defined as the variation. It shows that under certain conditions, this upper bound can be decreased while only using information about the source threat model. Based on the generalization bound, it proposes a learning algorithm AT-VR for unforeseen robustness. Empirically, it demonstrates that this technique can lead to improved robustness on unforeseen attacks across datasets such as CIFAR-10, CIFAR-100, and ImageNette over standard adversarial training. 

3. It is well-written and the related works are properly discussed. 

However, I think this paper has the following weaknesses: 

1. The source variation-based threat model generalization bound (corollary 4.4) relies on an assumption: an expansion function s from the source threat model S to the target threat model T exists. This assumption may be too strong. Although Theorem 4.7 shows that in the case of a linear feature extractor, a linear expansion function exists for any data distribution from a source $\ell_p$ adversary to a union of $\ell_p$ adversaries, it is unclear if such expansion functions exist for neural networks. The linear feature extractor with bounded condition number is too simple. It can consider a more complex case (e.g. two-layer neural networks) and check if the expansion function exists in such a case. 

2. In Table 1, it only considers one baseline standard adversarial training. I think it should add more baselines. For example, it can compare the proposed method AT-VR to the Perceptual Adversarial Training (PAT) (Laidlaw et al. 2021). Also, it can add the baseline of adversarial training against the target threat model as an "oracle" baseline. 

3. It doesn't discuss how to select the hyper-parameter $\lambda$. Note that the best hyper-parameters should not be selected using the test data. 

4. In Line 380-381, it states that "we hypothesize that this property also appears for ResNet-18 models because neural networks are piecewise linear". I think it should provide some empirical evidence to support this hypothesis.  
questions: 1. Could Theorem 4.7 be extended to non-linear cases? 

2. Could the authors add more baselines in Table 1? 

3. How to select the hyper-parameter $\lambda$?

4. Could the authors provide some empirical evidence to support the hypothesis stated in Line 380-381? 
limitations: The limitations and potential negative societal impact are properly addressed.
review_title: null

Meta-review: metareview: This paper seeks to theoretically formulate the problem of learning a classifier which is robust against unseen attacks. Reviewers generally liked the way authors formulated this understudied problem in adv robustness and found the paper well written. There were some questions and concerns regarding the usefulness of these results in reasonable learning problems as well as its numerical analysis. Given all, I think the paper is above the accept threshold. 
confidence: Certain
Decision: Accept