Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies the PAC learnability of adversarial robustness in the tolerant setting. The paper reveals a learnability result showing that VC hypothesis sets are tolerantly PAC learnable in the realizable case using a ``perturb-and-smooth'’ algorithm. As compared to previous non-tolerant results, their sample complexity has an exponential improvement on the dependence of VC dimension. The paper also reveals a learnability result in the agnostic setting through sample compression. 

strengths_and_weaknesses: Strengths:

* Well-written assumptions and theorems.
* New tolerant framework is considered.

Weaknesses:

The significance is limited. The major issue is that their tolerance framework is not justified.

On the one hand, they do not specify how to choose a reasonable *reference* perturbation type V(x) given an *actual* perturbation type U(x) in definition 4. More precisely, the choice of tolerance parameter \gamma in line 206 is unclear. I think this is very crucial and necessary in this framework. Consider the case where V(x)=0 and U(x) = B_{\gamma}(x). Then the inequality between line 195 and 196 tells that the algorithm can find a classifier with clean error smaller than the adversarial bayes error within ball B_{\gamma}(x), which is actually meaningless for any \gamma since we know that the clean bayes error must be less than the adversarial bayes error and the sample-efficient PAC learners for clean bayes classifier is known.

In line 298 - 301, they want to set gamma to be above some threshold. Using their parameters of \zeta=1, c =1000 and d=1000 in the provided example, the gamma is required to be larger than 1. It is hard to believe that such a large gamma is meaningful in terms of the tolerance of perbutation size.

On the other hand, they do not show negative results like "some tolerance is necessary otherwise adversarial robustness is not possible", which further limits the significance.

Their sample complexity such as that in Theorem 10 is independent of the actual perturbation size r for adversarial robustness. Their proposed algorithm does not train on the worst case perturbed samples. Instead, the algorithm only trains on the randomly perturbed samples, which I think is not useful for adversarial robustness. These facts suggest that such a tolerance framework seems not reliable.

questions: See the weaknesses.
limitations: The discussion was adequate.
review_title: null

final_score: rating: null
review_content: Hi,

after reading the other two reviews, I would like to describe my point of view and insist that this paper should be accepted.
I'm very familiar with the theoretical results in this field.
This paper makes a clean and nice improvement in the PAC model with adversarial examples.

I don't think that experiments are necessary for this paper.
Also, not every paper provides sharp upper and lower bounds. What should be considered is the contribution of the paper to the field, new ideas, and analysis.
Many questions in this field are open, we don't even know the right parameter characterizing this model 
(also under robust realizability assumption!), therefore we cannot hope for sharp results at this point.

I don't find good arguments in the other reviews for rejecting the paper.
I believe that this paper should be accepted, and at the least get the AC's attention.


review_title: Disagreeing with the other reviewers

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper introduces an algorithm called “tolerant perturb and smooth” and analyzes it with the lens of tolerant PAC learning. The analysis applies to the robustly realizable setting. This analysis is able to tighter sample complexity bounds than previous work.
strengths_and_weaknesses: 

	Pros:
		- I don’t have the expertise to check the proofs, but I think the proofs in the paper are non-trivial and are likely to be correct

	Cons:
		- I’m fairly confident that the algorithm TPAS algorithm does not work at all. I implemented the algorithm for linear models on MNIST and it got 5% adversarial test accuracy. That’s worse than random guessing! I didn’t even implement the real adversarial example algorithm that’s aware of the random smoothing, I just generated adversarial examples off a single instantiation of the model on clean examples, so presumably the true adversarial error rate is even worse. Most of what I say in the review is low confidence but I am confident that the algorithm simply does not work.
		- Similar algorithms that do work, as correctly discussed in the related work section, do things like train on more than one noisy sample per example, and use different aggregation metrics, rather than just the simple mean.
		- To be clear, I’m not saying that the PAC analysis in the paper is wrong, or that the paper over claims performance anywhere. It’s possible to have low sample complexity by converging rapidly (as a function of dataset size) to very bad performance. The analysis in the paper is also restricted to the robustly realizable setting, meaning the final performance should be good, but this also restricts the applicability of the work significantly. For example, it means the paper is not actually applicable to my linear MNIST experiment.
		- It’s unclear to me whether there is any interesting data distribution (ImageNet etc) which is known to have a model class that satisfies robust realizability. For MNIST and small max norm balls, robust realizability may be possible, though it’s not totally clear that the norm ball convolved with the true data distribution for one class does not overlap with the norm ball convolved with the true data distribution of another class. Certainly the norm balls centered on the finite MNIST test sets don’t overlap, for the size of norm balls commonly used in the literature. Small convolutional neural networks are able to memorize the (adversarial) test set, so maybe these satisfy robust realizability.
		- I also trained a small CNN using TPAS and it got ~1% accuracy against adversarial examples. Once again, this was with a non-adaptive attacker (not aware of the test time noise smoothing).
			- I’m assuming this result is still compatible with the claims in the paper, but I haven’t spent any time trying to work out how so.
		- Overall, I argue for rejection because I’m concerned that as presented, the paper would be misinterpreted as arguing that TPAS is an effective defense against adversarial examples. The adversarial example topic has repeatedly proved to be prone to false memes spreading rapidly, becoming ingrained, and requiring people working on the topic to waste a lot of time and effort arguing against misconceptions. This could potentially be addressed by substantially revising the paper to be extremely up front about the limitations of TPAS and explaining the interpretation of the PAC theory in a way that makes it clear that the PAC theory does not imply that TPAS would result in good performance or even better than chance performance on, say an ImageNet benchmark. Another way of stating this objection is that, while the paper does not over claim, I feel like it omits too much discussion of (very significant) limitations.
		- I have a second, weaker reason for arguing for rejection, which is simply that NeurIPS is a selective venue, publishing particularly interesting results rather than merely correct results. Due to the poor performance of the TPAS algorithm, I argue that theoretical analysis of the algorithm is not interesting enough to be ranked high enough for NeurIPS acceptance, regardless of the correctness of that analysis.

Comments on the dimensions:
- I don't know enough about PAC theory to assess originality or quality well.
- I argue that the work has poor clarity because it will appear to many readers to endorse TPAS as a defense against adversarial examples, when in fact I think it technically does not claim that this method will achieve good performance.
- I argue that the work has low significance because the algorithm analyzed does not work



One sentence I do think is mistaken: I think this sentence should be revised: “These works provide learning algorithms that guarantee low generalization error in the presence of adversarial perturbations in various settings.” Unless I’m mistaken, these algorithms guarantee that the generalization error is nearly optimal within the hypothesis space, but the optimal generalization error within the hypothesis space for many standard hypothesis spaces (like linear models, or some neural network) could be worse than random guessing. 
questions: Is there an argument that this work has higher significance than I've thought, despite the algorithm itself not working well? For example, is it a step on a path to performing an analysis of one of the methods from the related work section that works well?
limitations: My main objection to this paper is that I think it does not make the limitations clear enough to an audience that is interested in adversarial examples but not expert in PAC learning theory. I'm concerned that the paper comes across as proving that TPAS "works" as a defense when that's not the case and I think that's not technically what the paper is claiming.

One other limitation I didn't discuss above is Algorithm 1 uses an analytical expectation over x’, rather than a finite number of samples, so the algorithm cannot be implemented in practice for most interesting models. I see that this is discussed at line 135 but I think the discussion should be more prominent, I think the problem is worse than being “potentially expensive” for many models such as neural networks.
review_title: null

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 introduce adversarial robust learning based on tolerance (i.e., training with larger random perturbation), estimator smoothing and sample compression. It present a rigorous sample complexity analysis. This paper focuses solely on theoretical analysis, and doesn't provide any concrete algorithm or simulation result.
strengths_and_weaknesses: 1. Strength: the results are mathematically sound.
2. Weakness: despite the rigorous mathematical derivation, I am not sure how the presented PAC analysis result helps the community. One can directly apply the sample complexity analysis on the adversarial loss (say via Rademacher complexity). Does the presented result provide more insights or a better rate?
3. Weakness: the paper doesn't actually provide an executable algorithm, but only an existence results, i.e., the existence of measure mu, the existence of sample compression scheme. Whether the rate results pair with a computational feasible algorithm is unclear, and there is no simulation to demonstrate empirical performance/comparison.
4 Weakness: in conclusion, the paper neither provide a theoretical information limit result, nor an executable adversarial training algorithm.
questions: 1. How realistic is the assumption of that "P is V-robustly realizable"? what happens if we let gamma go to infinity?
2. Property 1, the equation should be the expectation of an indicator function.
3. Theorem 10 implicitly requires A_H to be an optimal PAC learning, which is not clearly mentioned. 
limitations: N.A.
review_title: null

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: Setting and contributions:
The authors suggest a new realistic setting of adversarially robust PAC learning (to test time attacks) in metric spaces, 
such that the learner is tested at inference time on a slightly bigger perturbation set that is controlled by a parameter (gamma>0) for his choice. We refer to it as the tolerance parameter.
Obviously, by choosing a smaller gamma, the perturbation set at test time is getting closer to the one on training time, which is a harder benchmark. As a result, there is a trade-off between sample complexity and competing with a better benchmark. 

The main results are two algorithms. 
The first one is in the robust realizable setting, with sample complexity that depends exponentially on the metric space dimension (doubling dimension) and linearly in the VC dimension. The algorithm is simple and efficient.

The second algorithm, for the agnostic setting, incorporates the idea of the first one (perturb and smooth) with a sample compression scheme argument, suitable for the model with tolerance. The sample complexity is improved exponentially (linear in the doubling dimension), due to the strong generalization guarantees of sample compression. 
strengths_and_weaknesses: This theoretical setting is natural, and well-motivated by empirical work on adversarial examples.

The results are satisfying, specifically exploiting the metric space assumption for removing the dual VC that pops up in the case of general perturbation sets.

I find the techniques simple and elegant.

Overall, I think that it is a nice idea for studying robustness.

questions: -What is the support of the distribution? Is it the clean examples, and for sampling from a perturbation set you first sample from a clean example?
More specifically, is it defined similarly to the previous papers on theoretical robust learning?

-Can you please give a short explanation of how you avoid the dual VC in Lemma 14? I know why it pops up in the case of arbitrary perturbation sets.
I read the proof, but not sure about the answer.

I would be happy to figure it out and recommend the paper for acceptance. 
limitations: -
review_title: null

Meta-review: metareview: The paper introduces an algorithm called “tolerant perturb and smooth” and analyzes it with the lens of tolerant PAC learning. The analysis applies to the robustly realizable setting and achieves tighter sample complexity bounds than previous work.

However, there were concerns about the significance. The major issue is that their tolerance framework is not justified.
From the discussion:
<<
On the one hand, they do not specify how to choose a reasonable reference perturbation type U(x) given an actual perturbation type U(x) in definition 4. More precisely, the choice of tolerance parameter \gamma in line 206 is unclear. I think this is very crucial and necessary in this framework. Consider the case where V(x)=0 and U(x) = B_{\gamma}(x). Then the inequality between line 195 and 196 tells that the algorithm can find a classifier that has clean error smaller than that of adversarial bayes error within ball B_{\gamma}(x), which is actually meaningless for any \gamma since we know that the clean Bayes error must be less than that of adversarial Bayes error and the sample-efficient PAC learners for clean Bayes classifier is known.

In line 298 - 301, they want to set gamma to be above some threshold. Using their parameters of \zeta=1, c =1000 and d=1000 in the provided example, the gamma is required to be larger than 1. It is hard to believe that such a large gamma is meaningful in terms of the tolerance of perturbation size.

On the other hand, they do not show negative results like "some tolerance is necessary otherwise adversarial robustness is not possible", which further limits the significance.

Their sample complexity such as that in Theorem 10 is independent of the actual permutation size r for adversarial robustness. Their proposed algorithm does not train on the worst-case perturbed samples. Instead, the algorithm only requires training on the randomly perturbed samples, which I feel is not useful for adversarial robustness. It will be surprising if such a tolerance framework is reliable based on these facts.
>>

The referees raised serious concerns regarding the efficacy and significance of the algorithm. Given the lengths to which they went in running independent experience, I take these reservations very seriously and cannot recommend acceptance at this stage.
confidence: Less certain
Decision: Reject