Venue: NeurIPS 2022 Conference

Reviews:

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: The paper considers realizable and agnostic semi-supervised PAC learning models. A common algorithm for robust semi-supervised learning is provided which first learns a partial concept class which predicts * (undefined) on points for which the concept may change prediction under an adversarial perturbation, using the labeled examples. This concept is used to extrapolate labels for the unlabeled examples on which an agnostic robust supervised learner is trained. Upper and lower bounds on the number of labeled examples needed are given in terms of the adversarial VC dimension, VC_U, in both realizable and agnostic settings. Further an application is provided, where the non-robust sample complexity is improved under a robust realizability assumption.
strengths_and_weaknesses: The paper shows a remarkable result for the number of labeled examples needed for robust semi-supervised learning - the results are somewhat surprising since finite VC_U is known to be not sufficient in the supervised setting (this is a strength).

Upper and lower bounds are provided in both realizable and agnostic settings. In the agnostic setting, the learner's goal is to have error const*OPT+epsilon since improvement over the supervised setting is not possible with OPT+epsilon.

Technically, the paper is an application of prior works on learning partial concept classes and agnostic robust supervised learning. The main novelty is combining the techniques.

It is not clear if one can say that VC_U is the correct sample complexity measure for the problem in all regimes of unlabeled sample size. It seems true in the sufficient unlabeled examples regime, so perhaps the stated results (e.g. in the abstract) should be qualified further.

Proof of Theorem 3.1 is not presented. The paragraph leading to it gives an explanation, but a formal proof should still ideally be included for completeness.
questions: Knowledge of supp(D_X) seems like a strong assumption. Are the authors aware of instances of this assumption in prior work?
Lines 253 vs 263: what does it mean that D_x is known? Is it the same as supp(D_x) is known?

What is 'labeled sampled complexity' (e.g. in Theorem 3.1)? Not defined in Sec 2. It seems like a bound on m_l in Definitions 2.2 and 2.4 but for what m_u (since definition is for pairs m_l,m_u)?

Similarly, in Theorem 5.2,5.3 what does m_u=\infty mean? Does it imply that m_l satisfies the lower bound for any (finite) m_u? Should be useful to add a remark in the context of Definitions 2.2 and 2.4.

In algorithm 1, h_1 is a partial concept class, right? How is the agnostic robust supervised learner applied to partially labeled sample S^u?

Typos:
155: exists
First para of Sec 2: definition of supp(D_X) should probably have an existential quantifier? \exists y\in Y s.t. D(x,y)>0?

limitations: I do not expect negative societal impact from this work.
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: The authors study semi-supervised learning for adversarially robust classification and claim upper bounds on labelled and unlabelled sample complexity of their learner. In particular, for the case when the data distribution is robustly realizable wrt (H, U) (i.e. when the robust loss is 0), they claim that their learner needs only a linear (in VC-dimension) number of labelled samples, as long as it's given a potentially exponential (in VC) number of unlabelled samples. More specifically, they show a linear dependence on a dimension that is defined in term of "robust shattering" with respect to the general perturbation sets U. It is known that this dimension can be significantly smaller than the VC-dimension. They also claim similar results for the agnostic case, and make additional remarks on special cases when their sample complexity can be improved further, and complement their upper bounds with corresponding lower bounds on the labeled and unlabeled samples.
strengths_and_weaknesses: The paper is sound and makes interesting new contributions.
questions: I think if we just want to show a linear dependence on VC-dimension for the number of labelled samples, we do not need to invoke the partial concepts paper? 
limitations: The authors have addressed limitations adequately.
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: The authors tackle the learning of an adversarially robust predictor in the semi-supervised PAC model. They study the sample complexity for labeled and unlabeled examples for PAC learning. Their main focus is to control sample complexity of labeled examples which are more expensive to obtain than unlabeled examples. The sample complexity of unlabeled examples matches with that of labeled examples in supervised learning. Their main contribution is to bound sample complexity of labeled examples by a different complexity measure $VC_{\mathcal{U}}$. They provide new bounds for the following cases (I am mentioning only the labeled complexity):
1. Realizable and known support of the marginal distribution: $\Theta(\frac{VC_{\mathcal{U}}}{\epsilon} + \frac{log \frac{1}{\delta}}{\epsilon})$. 
2. General realizable case: $\tilde{\mathcal{O}}(\frac{VC_{\mathcal{U}}}{\epsilon} + \frac{log \frac{1}{\delta}}{\epsilon})$. 
3. General agnostic case: $\tilde{\mathcal{O}}(\frac{VC_{\mathcal{U}}}{\epsilon^2} + \frac{log \frac{1}{\delta}}{\epsilon^2})$ with error $2 \eta + \epsilon$ or $\tilde{\mathcal{O}}(\frac{RS_{\mathcal{U}}}{\epsilon^2} + \frac{log \frac{1}{\delta}}{\epsilon^2})$ with error $\eta + \epsilon$. They also show that $(\frac{3}{2} - \gamma)\eta + \epsilon$ error is unavoidable if the learner has access to only $\mathcal{O}(VC_{\mathcal{U}})$ labeled examples.

On a high-level the analysis can be summarized in the following steps:
1. Given the class $\mathcal{H}$, construct the partial concept class $\mathcal{H}_\mathcal{U}^*$.
2. Execute the learning algorithm for partial concepts to learn hypothesis $h_1$ for partial concept class $\mathcal{H}_\mathcal{U}^*$ . Bound sample complexity in terms of $\mathcal{O}(VC_\mathcal{U})$.
3. Label the unlabeled data set using $h_1$ .
4. Execute the agnostic adversarially robust supervised PAC learner to learn hypothesis $h_2$. Provide bounds on robust error.

strengths_and_weaknesses: Strengths:
- The paper provides novel theoretical bounds for semi-supervised learning setting and is able to keep the labeled sample complexity down for the case when  $VC_\mathcal{U}$ is strictly smaller than $VC$.
- The paper is well written and theoretical results are presented in a manner which is easy to follow. In my opinion, the main contribution is in Definition 4.1 where they construct a partial concept class.

Weakness:
- The paper reads like an extension (although non-trivial) of ideas first mentioned in [2] and [39] to semi supervised learning setting. Once Definition 4.1 is established, the analysis directly borrows ideas from [2] and [39]. 
- The paper lacks some concrete examples for specific $\mathcal{H}$ and $\mathcal{U}$ when $VC_\mathcal{U}$ is strictly smaller than $VC$ and the gain in complexity is significant.
questions: I liked the way the paper is presented and written. I will rephrase the weaknesses mentioned in previous section as questions, so that authors can respond to them.

1. Consider that results in [2] and [39] are well-known. Could you specify particular places (in concepts or theoretical analysis) where contribution is novel and is independent of contribution in [2] and [39]?
2. Could you provide some useful examples for specific $\mathcal{H}$ and $\mathcal{U}$ when $VC_\mathcal{U}$ is strictly smaller than $VC$ and the gain in complexity is significant? 
limitations: The limitations have been adequately addressed.
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: The authors consider the problem of adversarial PAC learning in a semisupervised setting. 

+ they show that having access to marginal distribution can provide provable benefits for this setting for some concept classes
+ they give a semi-supervised learner that uses labeled samples to learn an accurate but non-robust hypothesis (using partial concept learning). 
+ They then show that one can use unlabeled data and label them with the learned hypothesis to come up with a larger labeled data from a distribution that is close to the actual labeled distribution. They then use the known results for adversarially robust pac learning on this data
+ their analysis shows provable benefits of unlabeled data for adversarial pac learning (for some hypothesis classes).
+ the analysis is extended to the agnostic setting
strengths_and_weaknesses: Strengths:

+ the main paper is written quite nicely
+ the results are interesting: they show provable benefits of unlabeled data for pac learning under adversarial perturbations
+ the idea of using the framework of partial concepts as well as labeling the unlabeled data is quite nice. Since this work builds on the existence of partial concept learners and robust pac learners, any future improvements will likely improve this result too. 
+ Because the work build on the two building blocks (partial concepts and adversarial learning), the analysis is rather simple, clean, and intuitive. I like that the authors do not try to overcomplicate things, offering a good ground for future advancements.

Weaknesses:

+ The work of M Darnstädt, HU Simon and B Szörényi on "Unlabeled data does provably help" provides some provable benefits of semisupervsed learning in the non-adversarial setting. I think it would make sense to mention this result especially since the reader may think that in the non-adversarial distribution-free setting there is no benefit in knowing the marginal or having unlabeled data. 
+ The work of H Ashtiani, V Pathak, R Urner  on "Black-box certification and learning under adversarial perturbations" provides some results on semi-supervised adversarial pac learning. It would help to discuss or compare the results.
questions: N/A
limitations: N/A
review_title: null

Meta-review: metareview: This submission provides novel results on the benefits of unlabelled data (through a semi-supervised learning framework) for adversarial robust PAC learning. The results are correct, novel and will be of substantial interest to the corresponding sub-community of NeurIPS. I therefore recommend acceptance.


Side note: the following publication studies SSL (PAC-type) sample complexity (upper and lower) bounds with the same algorithmic idea, and I believe should be acknowledged:

Ruth Urner, Shai Shalev-Shwartz, Shai Ben-David: Access to Unlabeled Data can Speed up Prediction Time. ICML 2011: 641-648
confidence: Certain
Decision: Accept