On Agnostic PAC Learning in the Small Error Regime

We thank the reviewer for carefully reading the paper and for their detailed feedback. We address their points in turn.

The authors mention that a feature of their algorithm is that it does not need to know in advance. Is this true for prior work on this model as well?

We thank the reviewer for raising this important point. Previous algorithms in the literature are indeed also oblivious to the knowledge of $\tau$. Our intent with our original description was to clarify that our improved algorithm preserves this desirable feature, but is clear that we should have explicitly stated that many previous algorithms do so as well. We will update the next version of the paper to clarify this point.

The main drawback of this paper in my opinion is its very dense writing style, which at times makes it a bit hard to read. I recommend the authors spacing out mathematical definitions and nonstandard notation introduced throughout the analysis. ... Throughout the paper, the grammar is occasionally slightly odd (e.g, the 1st sentence ending abruptly). I suggest the authors revising the writing, and as mentioned earlier, even more so in terms of the math.

We admit that there is certainly room for improvement in the readability of the paper, as also noted by reviewers 1ZdR and e2wi. We found the paper somewhat difficult to write, including especially Section 3, owing to the technicality involved in the analysis as well as the page limit of the submission. Should the paper be accepted to the conference, we will be sure to use the additional page of the camera ready version to improve the spacing and presentation of notation throughout the paper, at the reviewer’s suggestion. We also intend to include additional intuition and motivation in Section 3, as well as to include the algorithm’s full pseudocode in the main body of the paper. (As opposed to merely in the appendix, where it has currently been deferred.) We believe these various modifications will make the section considerably less dense and more legible for the reader. We thank the reviewer for raising this important point.

Line 64: what is $n$? Should probably be fixed to $m$.

Correct, we will be sure to update this in the next version of the paper.

The abstract formatting here on openreview has a bug (does not exit math mode appropriately), should be fixed.

We thank the reviewer for bringing this to our attention. We will fix this mistake once we are permitted to update the abstract on OpenReview (unfortunately, we currently cannot).

I thanks the authors for their response. Having read it as well as the other reviews, I remain positive toward recommending the acceptance of the paper.

We appreciate the reviewer’s time and thoughtful assessment of our paper. Below, we respond to the reviewer’s questions in order:

Algorithm Complexity: The final "best-of-both-worlds" algorithm is quite intricate, involving a three-way sample split, multiple recursive splitting schemes via Algorithm 2, two independent voting classifiers, a tie-breaker ERM, and a final model selection step on a hold-out set. A high-level block diagram illustrating this data flow could significantly improve the reader's ability to grasp the overall architecture of the learner. and Intuition Behind Constants: The proof sketch explains that the final 2.1τ term comes from adding the bounds of two different error events, one contributing roughly 1.1τ and the other τ. A bit more intuition in the main text about why the tie-breaking scheme leads to this specific decomposition would be beneficial.

We thank the reviewer for suggesting the idea of a block diagram to provide a high-level overview of the steps in our final algorithm. Should the paper be accepted to the conference, we will try to find space for it in the final version of the paper (currently it is in Appendix B removed from the main due to space constraints). We will also try to include additional intuition explaining where the factors $1.1\tau$ and $\tau$ come from.

We thank the reviewer for the great question. We take them in order.

The tie-breaker ERM is trained on a "hard" subset of data where the primary classifiers disagree or lack confidence. The analysis shows that this ERM still achieves an error close to the optimal h* on this conditional distribution. Could you provide more intuition for why a standard ERM, known to be suboptimal, performs so well on what seems to be a more difficult data distribution?

Answer:
First a high-level explanation and then a more formal explanation. The ERM performance on the "hard" subset is actually as one would expect for ERM. However, the probability of it being asked to make a tie-break is small, thus the overall probability of the tie-breaker both being called and failing ends up being smaller than the overall probability of an ERM failing when trained just on the "plain" data.

More formally (omitting the $\ln{\left(1/\delta \right)}$ factor in the following sketch): The probability of either $\hat{\mathcal{A}}\_{t\_{1}}$ or $\hat{\mathcal{A}}\_{t_{2}}$ failing to classify with a good margin (more than $11/243$ of their voters being incorrect) is $p:= 1.1\tau+O(\sqrt{\tau\frac{d}{m}}+\frac{d}{m})=O(\tau+\frac{d}{m})$, and thus the ERM deciding the tie-break $h_{tie}$ will be trained on $\Theta(p m)$ samples.

Now let $E\_{\lnot margin}$ be the event that either $\hat{\mathcal{A}}\_{t_{1}}$ or $\hat{\mathcal{A}}\_{t_{2}}$ fails to classify with a good margin, i.e., the case where the tie-breaker is used, so $E_{\lnot margin}$ has probability $p$. Since, $h_{tie}$ is trained on $\Theta(pm)$ examples from the conditional distribution $\mathbf{P}[\cdot| E_{\lnot margin} ]$ it has error $\mathcal{L}\_{\mathbf{P}[\cdot| E_{\lnot margin} ]}(h_{tie})= \inf_{h\in\mathcal{H}} \mathcal{L}\_{\mathbf{P}[\cdot| E_{\lnot margin} ]}(h)+O\left(\sqrt{\frac{d}{pn}}\right)= \mathcal{L}\_{\mathbf{P}[\cdot| E_{\lnot margin} ]} (h^\*)+O\left(\sqrt{\frac{d}{pn}}\right),$ where we use that $h^{*}$ is not a minimizer of the conditional distribution, so we can use it as an upper bound (we are here using the agnostic learning gaurantee of ERM, see for instance [1] Theorem 6.7).

Now, by the law of conditional probability, we have that the probability of the event that either $\hat{\mathcal{A}}\_{t_{1}}$ or $\hat{\mathcal{A}}\_{t_{2}}$ has small margin, i.e., $E_{\lnot margin}$ happens, and the tie-breaker ERM $h_{tie}$ fails is

where the second-to-last inequality follows from $\mathcal{L}\_{\mathbf{P}[\cdot| E_{\lnot margin} ]}(h^\*)= \frac{\mathbf{P}\_{(x,y)}[E_{\lnot margin},h^\*(x)\not=y]}{\mathbf{P}\_{(x,y)}[E_{\lnot margin}]}\leq\frac{\mathbf{P}\_{(x,y)}[h^\*(x)\not=y]}{\mathbf{P}\_{(x,y)}[E_{\lnot margin}]}=\frac{\mathbf{P}\_{(x,y)}[h^\*(x)\not=y]}{p}$ and the last inequality from $p=O\left(\tau \frac{d}{m}\right)$.

[1] Shalev-Shwartz, S., Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms.

The switch from 3 recursive calls in the initial approach (Section 3.1) to 27 calls in the improved approach (Algorithm 2) is a critical step in the analysis. Is there a deeper principle behind the number 27, or is it simply "a number large enough for the probability math to work out"? How sensitive is the final constant of 2.1 to this choice?

Answer 2 The choice of more than $3$ recursive calls is to improve the constant coming from the event contributing $15 \tau$ in the simple analysis down to $2.1 \tau$, as it enables splitting the error into two events: (1) the event where both classifiers $\hat{\mathcal{A}}\_{t_{1}}$ and $\hat{\mathcal{A}}\_{t_{2}}$ fail with a large margin, and (2) the event where one of the classifiers fails with a small margin, and the tie-breaker is called and fails.

From this split, we have to be able to say that the probability of one of the classifiers failing with a small margin (more than $11/243$ voters being incorrect) is small (that is, the probability $p$ in the answer to Question 1 should be of the order stated in Question 1). Without going into too much detail, this requires a more fine-grained analysis of the margin error of the recursive algorithm $\mathcal{A}_{t}$ - basically we want the number of recursive calls to be such that, given an margin error of $11/243$, one of the recursive calls fails with this margin and some of the voters in the remaining classifiers also fail - which a larger number of recursive calls guarantees.

The number 27, as foreseen by the reviewer, was chosen somewhat arbitrarily (just large enough). The general trade-off for a larger number of recursive calls is that the constant in front of the error term of order $1.1\tau$ in the current version of the paper becomes smaller, but at the cost of a larger constant in the $O\left(\sqrt{\tau\frac{d}{n}}+\frac{d}{n}\right)$ term in the final bound. Implying that we could not just choose the number of splits arbitrarily large to get $1.1\tau$ down to $o(1) \tau$, so we chose $27$ as it allowed for a constant fairly close to $1$.

The final learner uses a hold-out set to select between your proposed algorithm and the one from Hanneke et al. cite_start. This is a standard and effective method. Did you explore possibilities for a more deeply integrated "single" algorithm that smoothly handles all regimes of τ without explicit model selection?

Answer: We thought a bit about this; however, we did not figure out a better approach than the hold-out set method presented in the paper.

We thank the reviewer for carefully reading the paper and for their thoughtful feedback.

Regarding the readability of Section 3, we admit that there is certainly room for improvement. We found this section particularly challenging to write, due to the technicality involved in the analysis as well as the page limit of the submission. Should the paper be accepted to the conference, we will be sure to use the additional page of the camera ready version to provide additional intuition and motivation in Section 3, at the reviewer’s suggestion, as well as to include the algorithm’s full pseudocode in the main body of the paper. (As opposed to merely in the appendix, where it has currently been deferred.) We believe these various modifications will make the section considerably less dense and more legible for the reader. We thank the reviewer for raising this important point.

We will also examine replacing some concrete numbers in the analysis with additional variables, while being careful not to unintentionally exacerbate the previous issue by introducing additional notation for the reader to keep in mind.

We thank the reviewer for carefully reading the paper and for their detailed feedback. We now address their questions in turn.

Did ideas from the stability literature influence your approach? Are there other high-level connections between this problem/approach and stable algorithms? (For example, work on subsampling?) Are there plausible technical connections between this problem (which isn't overtly about algorithmic stability) and the stable algorithms/learning theory literature?

Great questions. The reinterpretation/restatement of our algorithm is correct, and the “stability” perspective is an interesting manner of interpreting the engine behind the algorithm’s success. In particular, the majority votes (i.e., each algorithm trained on $S_1$ and $S_2$) intuitively serve the dual purposes of “covering each other's mistakes” and of providing a “certainty score” for their predictions (i.e., given by the number of constituent voters which agree with the majority). This certainty score allows the algorithm to identify difficult or uncertain points, for which the third classifier can break the tie.

Unfortunately, we cannot currently demonstrate that our approach is necessary stable in the sense of [1], owing to the fact that the classifiers in the majority vote (trained on $S_1$ and $S_2$), have overlapping samples, meaning that all such classifiers could conceivably change by altering even one example in $S_1$ or $S_2$. Furthermore, the tiebreak classifier trained on $S_3$ could then also change, despite the fact that an example in $S_3$ was not altered.

That said, we do believe that it is intuitively fair to think of our algorithm as a technique for stabilizing the alternative, which is ERM. We admit that we were not explicitly motivated by ideas from the stability literature, but we appreciate the reviewer bringing our attention to these intriguing connections. We will update the next version of the paper with a remark describing these previous points.

I believe the biggest weakness of this paper is the writing (clarity), which may detract from the community's ability to build on the technical contributions of this paper. This seems to stem from the submission page limit, trying to put fully rigorous arguments in the main body proof sketch (section 3), and not having enough intuition-explaining paragraphs in the proof sketch.

We thank the reviewer for the concrete suggestions for improving the readability of Section 3, and we admit that there is certainly room for improvement. We found this section particularly challenging to write, due to the technicality involved in the analysis as well as the page limit. Should the paper be accepted to the conference, we will most definitely use the additional page of the camera ready version to include the full algorithm pseudocode in the main body of the paper (as the reviewer suggests) and to generally improve the motivation, intuition, and pacing of Section 3.

We also thank the reviewer for the various minor comments/edits which they aptly noted – we will be sure to correct them in the next version of the paper.

[1] Stability and Generalization Olivier Bousquet, André Elisseeff, 2002.

Thanks to the authors for the rebuttal. Having read the other reviews and the authors' rebuttals, I have no further questions, and I continue to recommend my original evaluation.

The authors responded positively to ideas suggesting improving the clarity of the paper. This is great. In addition, I assume the authors will make a reasonable effort to ensuring their talks/posters/etc. are also clear, as they did with this submission.