Summary
This paper initiates the study of a new kind of PAC learning: probabilistically robust PAC learning. The authors show that the finiteness of the VC dimension of the function class is not sufficient to obtain a proper learning rule in this new PAC learning setup. However, they show that for Lipschitz losses that interpolate between the average and worst case, proper learning is possible given finite VC dimension. They also consider the settings of adversarially robust PAC learning and tolerant PAC learning; ultimately, this results in several extensions to previous works on these topics.
Strengths
**New problem setting.** This is a new problem. The authors consider several recent results in the robustness literature concerning robustness between the average and worst case, and they form a new definition of probabilistically robust PAC learning. I imagine that this is a direction that other may be interested in, and therefore this constitutes an interesting contribution.
**Non-proper learnability.** Perhaps the most interesting/surprising result here is that the finiteness of the VC dimension of the function class is not sufficient for proper $\rho$-probabilistic robust PAC learning. This implies that both probabilistic and adversarial robustness do not easily admit proper learning rules. This is somewhat surprising, given previous empirical results that find that probabilistic robustness does not come at the cost of degraded nominal performance with respect to an empirical risk minimizer. Building on this, it is also interesting that there do exist interpolation schemes that do admit proper learning rules given finite VC dimension. In this way, this paper is a first step toward characterizing a hierarchy of interpolating losses based on which ones admit proper learning rules. It would be interesting to know whether other interpolation methods, e.g., those in [Rice et al., 2021] and [Li et al., 2020] also engender proper learning rules.
**Technical rigor.** The paper seems technically sound to me. The proofs in the appendix are well-structured, and the array of tools used in the appendix may be of broader interest to the community.
Weaknesses
**Unevenness of the presentation.** There's a certain unevenness about the presentation of the main results. In general, the trend is that as one gets further into the paper, the results get harder to parse. This doesn't seem to be a function of the complexity of the results; rather, it seems as if less space was dedicated to fully explaining the results that appear later in the paper.
For instance, the results in Section 3 are outlined in detail. Theorem 3 tells us that there exists hypothesis classes for which $\rho$-probabilistically robust PAC learning is not possible, and the proof is sketched almost in full. However, by the time we reach Section 5, the results are stated with less explanation. The text becomes quite difficult to read because nearly every equation on pages 8-9 is inline. Definitions and theorems seem to be crammed in, and the paper ends without discussing the implications of the final theorem. I think that readibility would be greatly improved if the authors moved the proofs from Section 3 to the appendix, and (i) expanded more on the results later in the paper, (ii) broke up the texts by putting long equations on their own lines (i.e., not in-line), and (iii) adding a discussion section where the implications of the results are discussed. In its current form, the paper ends rather abruptly, and I think point (iii) would help to ameliorate this.
**Writing and notation.** I think that the presentation could be improved in several ways. Here are some points that occurred to me while reading the paper:
* It would also be helpful if the authors could use equation numbers.
* It's confusing that the authors introduce VC dimension and Rademacher complexity, but a definition arguably more central to this paper -- the definition of a *proper* learning rule -- was omitted.
* ERM seems to be used to denote "empirical risk minimization" (throughout) and "empirical risk minimizer" (line 95). I think it'd be worth picking one.
* What is $(\mathcal{X}\times\mathcal{Y})^\star$, i.e., what does the *\star* denote?
* Why is there a change in notation from $\mathcal{L}^{\mathcal{H}}$ to to $\mathcal{F}$ in Definition 2?
**Section 5.3.** When reading, I wasn't sure how Section 5.3 fit in with the rest of the paper. Whereas the other sections of the paper focus on proper learnability for probabilistic robustness and generalizations which interpolate between average and worst-case robustness, Section 5.3 seems to address questions that are somewhat different in spirit. I suppose one could argue that in the tolerance setting, reducing $\mathcal{G}$ to a singleton set containing the identify function would show that this paradigm can interpolate between the standard PAC model and robust variants, but this connection feels tenuous. Perhaps the authors could elaborate more on why this section fits in with this paper.
Questions
Is it fair to say that the fact that the probabilistic robustness loss function is non-Lipschitz is the reason behind Theorem 3.1. In other words, is Lipschitzness a necessary condition? My understand from Section 4 is that it is sufficient, but it may not be necessary.
**Overall assessment.** Overall, I do not see a strong reason for this paper not to be accepted. It studies a new problem and the insights are novel and interesting. There are some drawbacks regarding the presentation, but one imagines that these can be easily ironed out.
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.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.