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: The authors introduce a notion of \emph{barely robust} learning. Their main results demonstrate the an equivalence with strongly robust learning by showing (Theorem 4) that if a concept is strongly robustly learnable, it is barely robustly learnable as well, and then by proposing an oracle-efficient algorithm (Theorem 1) that calls a barely robust learner in order to produce a strongly robust one. Their formal equivalence statement (Corollary I) shows that being strongly robustly learnable with respect to an adversarial perturbation set $\mathcal{U}$ is equivalent to being barely robustly learnable with respect to a larger perturbation set $\mathcal{U}^{-1}(\mathcal{U})$, and they further demonstrate (Theorem 6) that barely robust learnability w.r.t. $\mathcal{U}$ does not in general imply strong robust learnability. 


strengths_and_weaknesses: Originality:
Highly original; the authors have proposed the first algorithm that boosts the robustness of what they call barely robust learners, and provide a comprehensive characterization of their newly proposed notion as it relates to previously studied notions.

Quality:
Good. The theory is elegantly laid out, and comprehensively addresses the salient questions. The discussion provides a satisfying contextualization of the results. 

Clarity:
Generally quite good, although perhaps it would read more straightforwardly if relevant definitions were placed before they are required in theorem statements. (I believe there is a typo in line 151: a missing subscript t in the def. of $G_{h_t}(z)$.)  

Significance: 
The open question of whether one can boost the error of a barely robust learner without sacrificing robustness remains, it would seem, an impediment to greater significance. In the same vein, more insight into the possibility of currently known adversarial learning methods being barely robust would also be welcome.  


questions: See comments under Significance above. Any enlightenment on either of these aspects would greatly improve the paper. 
limitations: The authors have not discussed potential negative societal impact of their work, although it is hard to see what one might have to say here that is not totally banal.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper presents theoretical analysis over barely robust learner and strong robust learner.
strengths_and_weaknesses: Strong Points
----
1. Adversarial robustness analysis is an important problem in machine learning community.

Weak Points
----
1. I spent more than 8 hours to read the paper. However, at least for me, it is very hard to follow the analysis. For example, U^{-1} is heavily used in Section 1.1 while its description locates in Section 2. 
2. I didn't check the correctness of the theorems and proofs. I wonder if it is possible to add an empirical analysis to show that the proposed methods are effective? The termination rounds could be very large for real applications.
questions: Could we add an empirical analysis to show that the proposed methods are effective?
limitations: I suggest the authors to discuss how the users can adapt the proposed algorithms in real applications.
review_title: null

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 a new direction in adversarial training, on the distinctions between barely robust leaners and strongly robust learners. The paper provides theoretical results on whether we can make a barely robust classifier into a strongly robust classifier. The paper also provided two algorithms to guarantee a strongly robust learner. The authors also prove that for any distribution, there would exist a barely robust classifier and that classifier is not a strongly robust classifier.
strengths_and_weaknesses: Strengths:
1. The definition of a barely robust learner is solid and new.
2. The authors provide many theorems to explain the relationship between a barely robust classifier and a strongly robust classifier, including their equivalence under some conditions.
3. There are two algorithms that guarantee getting a strongly robust classifier.

Weaknesses:
1. It is still unclear if the barely robust classifier for $U^{-1}(U)$ and strongly robust classifier $U$ are equivalent, is it that important to train a strongly robust classifier? It is unclear why we would care about the definition of a strongly robust learner.
2. There are no numerical experiments to support the applications or benefits of a strongly robust classifier. 
3. There are no comparisons between existing literature in either theoretical or numerical results, so we don't understand what is the relationship between a strongly robust classifier with other related literature.
questions: 1. You mentioned that  $U^{-1}(U)$ is a ball with $2\gamma$ radius and $U$ is a ball with $\gamma$ radius. This statement and Colloray I sound contradicitng with you claim that "weaker relaxations of barely robust learning do not imply strongly robust learning" in line 33.
2. Is it possible to implement black-box oracle calls to A on real-world datasets?
3. 
limitations: Although the theoretical results are novel and interesting, the paper does not provide numerical experiments to support its findings. This makes me question the possibility of using the definition of the strongly robust learner or implementing the two algorithms in real-world applications. It would be more convincing if the authors can provide some numerical experiments even on small datasets, like MNIST.
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 studies how to achieve adversarially robust learning with weak robust learners. The investigation follows a quite natural agenda and gives quite complete answers. The contributions are three folds.

First, at the conceptual level, the paper propose the key definition of barely robust learning, and point out the importance to look at a larger perturbation set $U^{-1}(U)$. 

Second, the paper gives an oracle efficient reduction from adversarially robust learning to barely robust learning. This shows that barely robust learning with respect to $U^{-1}(U)$ is sufficient for adversarial robust learning. This is by Theorem 1 and Algorithm 1.

Third, the paper shows that adversarial robust learning implies barely robust learning with respect to $U^{-1}(U)$ (Theorem 4), but it can not be achieved if one only has barely robust learning with respect to $U$ (Theorem 6). This shows that barely robust learning with respect to $U^{-1}(U)$ is necessary for adversarially robust learning. 
strengths_and_weaknesses: I like the flow of writing in this paper, especially the introduction section. Although this is a purely theoretical paper, the pace makes its proposed questions and main contributions easy to understand. In particular, when I read the introduction, the first question coming to mind is, isn't boosting easier if the robust parameter $\beta$ is larger than 1/2? This is answered immediately in the paragraph "Landscape of boosting robustness." The second question coming to mind is, is the assumption of robust realizability more restrictive than the traditional concept of realizability. And the authors give examples to answer this question in the related work part. I also like the  discussion section (Section 5), which answers my concerns about the agnostic setting and computation efficiency. This part also propose several open questions.


questions: I am confident that I understand the theme and conclusions of the paper. But I only go through the algorithm and proof part, so it's hard for me to evaluate the novelty of the algorithm and the theoretical analysis. I think the concept of barely robustness is quite essential, but is the analysis somewhat similar to existing routines after one discover this concept? 
limitations: The proposed algorithm in the paper is more useful when the robust parameter $\beta$ is small, since existing results could not provide theoretical guarantees in this regime. However, experiments may be needed if the authors want to advertise their algorithm to be better than existing methods that are directly based on canonical results and already work for $\beta>1/2$.

I think the paper should put more space and content to discuss when the perturbation set $U^{-1}(U)$ is much larger than $U$, and when they are similar. The current paper only uses the $\ell_p$ ball examples, where requiring robustness with respect to $U^{-1}(U)$ is very reasonable (it's just a ball with twice radius). However, as looking at this larger perturbation set is one of the major novelty of the paper, the author should carefully explain for what $U$ this requirement is strong (which means boosting robustness is not easy, according to the theorems in the paper), and for what $U$ this requirement is weak (which means boosting robustness is easy).
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper mainly shows that strongly robust learnable w.r.t. $\mathcal{U}$ is equivalent to barely robust learable w.r.t. $\mathcal{U}^{-1}(\mathcal{U})$, bu giving an algorithm $\beta$-RoBoost to boost robustness of barely robust learners and an algorithm to return a barely robust classifier through calling the strongly robust learner.

This paper also shows that barely robust learable w.r.t. $\mathcal{U}$ is not sufficient for strongly robust learnable w.r.t. $\mathcal{U}$ by a counterexample. What's more, the paper also gives algorithms to boost robustness with unlabeled data.
strengths_and_weaknesses: Strengths:
- This paper shows a sufficient and necessary condition for strongly robust learning and gives a novelty method to boost robustness of barely robust learners. The theoretical results are quite solid.
- The results of this paper in significant since it provides another way to study the robustness.
- The paper gives some high-level strategies to help understanding the spirit in the algorithms and proofs.

Weaknesses:
- As discussed in the discussion part, verifying whether a classifier is robust on the perturbation set $\mathcal{U}^{-1}(\mathcal{U})$ is a key issue in the computational efficiency of the proposed algorithm, but **to the best of my knowledge, there is now no theoretiacl gurantee for precisely verifying robustness for a general perturbation set and a general hypothesis class**. As stated in [1], the popular method random smooth might fail in verifying the $\ell_\infty$ robustness for high-dimensional images. So the realizability of the proposed algorithm highly depends on the development of robust verification.

[1] Blum, Avrim, et al. "Random Smoothing Might be Unable to Certify $\ell_\infty$ Robustness for High-Dimensional Images." J. Mach. Learn. Res. 21 (2020): 211-1.
questions: In the proof of Theorem 6, the paper uses a randomized learner which do not need any data as input, and proves that it is $(\frac{1}{2},0,\delta)$-barely robust learnable. And the paper proves that the expected value of the **robust risk** w.r.t. the random choice of $\tilde{y}$ is $\frac{1}{2}$, but not to be $\frac{1}{2}$ with probability at least $1 - \delta$ over the choice of samples as in the definition of the barely robust learner. Although we can use concentration inequality to get a confidence, but it is over the random choice of $\tilde{y}$, so there seems to be a mismatch in the definition of the barely robust learner and the proof of Theorem 6.

In Corollary 2, the paper claims it is a stronger boosting guarantee, I wonder in what sense is it stronger than Thoerem 1? Is it falls on better sample complexity, or falls on weaker requirement on the barely robust learner, or others else?
limitations: The authors does.
review_title: null

Meta-review: metareview: This paper makes important theoretical, conceptual, and algorithmic contributions to the adversarial robustness literature. I recommend the authors carefully go over reviewer suggestions on expositional clarity. Authors are also encouraged to explicitly discuss the limitations of the proposed approach. In particular, they can provide more discussion on the comparison between U(x) and U^{-1}U(x) and state the need to develop robust verification methods in the paper’s context.
confidence: Certain
Decision: Accept