Tight Generalization Bounds for Large-Margin Halfspaces

Thank you for your thorough review.

As other reviewers have said as well, there are definitions missing. Thank you for pointing it out, and for the given examples. In the final version of the paper, we will take special care to make sure that the notation is clear.

As for your questions, Page 1, line 17: What is $\mathbb{B}_2^d$? Is it the hypercube ${0,1}^d$ or is it a $d$-dimension ball?

By $\mathbb{B}_2^d$ we refer to the unit ball, in $d$ dimensions, with respect to the $\ell_2$-norm. So it is the Euclidian unit ball. We will make this more explicit in the final version of the paper.

Page 6, line 195: What is $\mathcal{X}$? I might have missed the definition but it doesn't seem to me that it was introduced anywhere. From the discussions in the paper, it seems to me that it is the set of all unit vectors satisfying $\langle w,x\rangle \leq c_\gamma$. Is this correct? If so, please explicitly say that.

You are correct, it is already explicitly stated on page 6, line 193-194, but phrased a bit convoluted. The sentence "which is the set..." is meant to define $\mathcal{X}$.

Page 7, line 224: Claims 2: I think that "with probability at least $1-\delta$" should be added to the claim, right?

Actually not. We can see that this is phrased in a slightly confusing way. line 224 refers to eq. (17) and (18) both holding simultaneously. Indeed these two equations hold with probability 1-delta. But what we are claiming here is that whenever (17) and (18) hold for some value of delta (delta appears in those two equations), then (16) also holds. The claim that (17) and (18) together imply (16) doesn't really need to know what the probability is that (17) and (18) hold. Of course, we eventually use the claim via union bound over the events in (17) and (18) to establish the claim in lines 195-197.

Page 8, line 243: Shouldn't "$p(z_i)$" rather depend on $(Aw)_i$? Perhaps it should be written $p((Aw)_i)$ to be more formal?

Yes, you are correct, p(z_i) does depend on (Aw)_i. We will make that more clear in the final version of the paper.

Page 8, line 254: (Minor comment:) The formatting/rendering of equation (19) is a bit weird.

We agree that the formatting is weird, we will try our best to make it less weird.

Thank you for the thorough review.

As for your questions: The proof relies on a sophisticated random discretization process involving a Johnson-Lindenstrauss transform and random snapping to a grid. While this is used as a proof technique, does it offer any algorithmic insights? Could a learning algorithm based on this discretization be practical or offer any advantages?

This is a very interesting question. We are aware of one previous work that has actually built on exactly this idea to develop a new learning algorithm. The paper "Replicable Learning of Large-Margin Halfspaces" from ICML'24 builds on the Gr\o nlund et al. proof technique, with JL + random snapping, to get a better learning algorithm. It seems highly likely that other applications exist.

"While one might argue that our improvement is small in magnitude, this finally pins down the exact generalization performance of a classic learning model". Could you elaborate on the importance of closing this final gap? Does it resolve any long-standing theoretical questions or open up new avenues of inquiry that were previously blocked by the discrepancy in the bounds?

Yes we believe it solves a long-standing open question. Proving generalisation bounds for large margin half spaces has been an active line of research at least since the first bounds by Bartlett and Shawe-Taylor in 1999. They considered the exact same setup and thus we believe it is fair to say that we close a line of research that has been going for 25+ years. As also mentioned in our reply to reviewers fuQC and kXmV, we believe our new technique may also be applicable to other learning problems now that we finally have a technique capable of proving completely tight bounds.

Thank you for the thorough review.

Thank you for suggesting the creation of additional conclusion and related work sections. We agree that the paper ends rather abruptly, and will strongly consider including a summarizing/concluding section in the final version. We were severely challenged by the page limit and went for giving as clear an overview of the proof structure as possible. As the (potential) final version for NeurIPS allows an additional page, we will prioritise a proper conclusion.

In the introduction of the paper, we aimed to give an overview on how the result improves over the most closely related prior works. Given an additional page, we will put emphasis on discussing related literature more broadly as suggested by the reviewer.

As for your questions, In lines 65-66 on page 3, the authors claim that “Furthermore, our proof of Theorem 2 brings several novel ideas that we hope may find further applications in generalization bounds”. What are the possible future research directions of this work? For example, could the tighter bound be applied to improve other theoretical results?

Do the techniques developed here have potential applications to other learning models beyond halfspaces?

We have one joint answer for the two questions (if we understand them correctly). As also mentioned in our response to reviewer kXmV, we believe our techniques also have a chance of improving known generalisation bounds for voting classifiers as the proofs there rely on the same random discretisation strategy and is lossy in the same way as the Gr\o nlund et al. paper. If the technique can indeed also be applied there, we see no reason why it shouldn't have other applications as well.

Additionally, thank you for pointing out typos and additional references, we will carefully go over each of the proposed references to make sure an expanded related works sections covers all necessary references.

Thank you for the thorough review.

We agree that omitting definitions makes the paper hard to follow, we will make sure to include definitions of $\mathbb{B}^d_2$ and $\mathcal{S}^{d-1}$ in the final version. We will also skim through the paper to make sure that there aren't other missing definitions.

As for the question: Do the authors believe some of the techniques adopted can be easily extended to other settings, or are they particularly tailored to the geometric nature of the large-margin halfspaces? Yes, we believe the techniques are general enough that they should have applications elsewhere. In particular, random discretizations have previously been used in generalisation bound proofs of e.g. voting classifiers as mentioned in the first line of Section 2.1 [Schapire et al. 1998]. For voting classifiers, a similar gap remains between the upper and lower bounds. We believe our technique is not as such tied to the geometry of half spaces, but instead gives a general way of performing a tighter analysis of random discretisation techniques via the use of Rademacher complexity. Of course, there would be many new problem specific details to work out, but we find the direction promising.