Fantastic Generalization Measures are Nowhere to be Found

After carefully reading your review, we would like to confirm (or clarify) our understanding before providing our response in full detail.

Is there an agreed-upon definition of overparametrization in the literature? So we can refer to it in our answers. If not, how would you mathematically define overparametrization? How would you define such a concept over non-parametrized spaces? Please note that Section 4 gives the motivation for our definition.

In addition to all of my concerns above, how is over-parameterization used in the argument between Definition 3 and Theorem 1?

We are not sure we understood your question. Are you asking for a high-level idea about how overparametrization is being used in the proof of Theorem 1? If not, can you please clarify/rephrase your question?

Regarding (6) and Definition 7 (Bayes-like Random ERM), we missed mentioning in our paper that all spaces we consider are finite. With this in mind, the definition of Bayes-like Random ERM is a well-defined random variable over a finite sample space. Does this answer your query?

I am talking about the paragraph between the statements of Definition 3 and Theorem 1. This is in the middle of page 6.

Thank you for the pointer. After careful re-reading, we polished the paragraph further and added more details, which now hopefully makes it easier to parse:

Note that given an algorithm-independent and distribution-independent bound $C$, it is not hard to construct a single (algorithm, distribution) pair that makes it vacuous. To illustrate this, consider the ERM defined as $\mathcal A_C(S):=\arg\min_{h\in \mathcal H: \: L_S(h)=0} C(h,S)$. Assume that $C$ is a valid generalization measure, i.e., (1) holds almost surely for every $\mathcal H$ realizable distribution $\mathcal D$ with labeling function $h_\mathcal D$. Then, by construction, $L_{\mathcal D(\mathcal A_C(S))} < L_S(\mathcal A_C(S)) + C(\mathcal A_C(S),S)\leq C(h_\mathcal D,S)$ almost surely over $S\sim \mathcal D^n$.

Now assume that the setting is overparametrized (say with large $\alpha$ and $\beta$ for a fixed $n$), i.e., no algorithm can learn (with error $\alpha$) the ground truth labeling w.p. at least $1- \beta$ jointly over the uniform choice of the distributions, and $n$ samples from the chosen distribution. This implies that for every algorithm $\mathcal A$, there exists at least one distribution $\mathcal D’$ such that $\mathcal A$ cannot learn w.p. at least $\beta$ over $S \sim \mathcal D’^n$. Hence there exists a realizable distribution $\mathcal D'$ with deterministic labeling function $h_{\mathcal D'}$ such that w.h.p. $L_{\mathcal D'}(\mathcal A_C(S))> \alpha$ which implies by the above inequality $C(h_{\mathcal D'},S)>\alpha$ w.h.p. But then it holds w.h.p. that $C(h_{\mathcal D'},S)\gg L_{\mathcal D'}(h_{D'}) - L_S(h_{D'})= 0$ and hence the bound is w.h.p. not $\alpha$-tight (in the sense of Eq. 2) for the pair $(\mathcal A_{h_{\mathcal D'}},\mathcal D')$, where $\mathcal A_{h_{\mathcal D'}}$ is the constant algorithm that always outputs $h_{\mathcal D'}$.

In particular, we removed the use of the no-free-lunch theorem and made the connection to the overparametrized setting more direct. Does this clarify things? If not, which step causes confusion?

Can you add this comment immediately following Definition 7?

Yes, will add this comment. Thank you for helping us improve the paper!

Thank you for the pointer. After careful re-reading, we polished the paragraph further and added more details, which now hopefully makes it easier to parse:

Thank you for the revised argument. While I feel the writing has improved, I am still somewhat confused. Namely, what is this "labeling function" and what is its significance? Also, shouldn't $\alpha$ and $\beta$ be small?

And regarding rest of your response. They are very thorough, but I did not ask for those clarifications. I believe that I understood your arguments reasonably well, and your response does not seem to change that impression (up to whatever I have forgotten between now and when I wrote the review). However, I expended considerable efforts into understanding your paper. Therefore, I am asking you to revise the paper in way that is easier to read for future readers. You have not done that thus far.

I would like you remind you that you can submit a revised paper. I am afraid that I will have to lower my score if I am still not seeing a revision incorporating suggestions from me and other reviewers. I will write what I personally what to see as a reply to one of your top-level response.

The definition of over-parameterizaton (Definition 2) in this paper is not standard and my impression is that they are phrased to make the proofs simpler. While Definition 2 does intuitively fit the idea of over-parameterization, I feel strongly that the author should add: a) detailed discussions on why this definition is consistent with the standard setting in the literature, b) examples.

Please see the global discussion regarding overparametrization.

Similar to the previous point, in Theorem 3, the condition on TV distance is unmotivated and seems to only exist to make the problem easier.

Theorem 3 gives a sufficient condition for non-estimability. Our proof essentially boils down to the fact that samples drawn from two different distributions – with labelings that disagree over a significant fraction of the space – “look the same” or “are easily confusable” for samples of size $n$, with reasonably large probability. If then the algorithm can learn over one of the distributions, but fails to learn over the other one (both of these items are part of the assumptions of the Theorem), any estimator must be loose. In the above context, the TV distance between these two distributions is a natural measure for the “confusability” of (the samples from) these two distributions.

As mentioned, this technique only yields a sufficient condition, so in theory it might be that it cannot yield meaningful numerical values of non-estimability. This is why we show in Theorem 4 that this is not the case (showcased for linear functions, together with ERMs with linear bias): we get essentially the strongest possible result already for $q=11$: that is, no estimator can have confidence much higher than a random guess, if it is supposed to do better than the trivial error level (see the discussion under Thm. 4).

what is this "labeling function" and what is its significance?

The data distributions $\mathcal D$ are characterized by their joint distribution over inputs $x \in \mathcal X$ and labels $y \in \mathcal Y$. We assume that the marginal distribution of the labels $y$ is $h \circ \mathcal D_{\mathcal X}$, i.e., the marginal input distribution composed with a deterministic labeling function $h: \mathcal X \rightarrow \mathcal Y$.

The labeling fcts. play a crucial role for how strongly overparametrized a setting is, since the ‘richness’ of the labeling functions $\\{h_i\\}_i\subset \mathcal H$ corresponding to the distribution family $\mathbb D = \\{\mathcal D_i \\}_i$ plays an important role in how hard it is to learn over $(\mathcal H,\mathbb D)$.

shouldn't $\alpha$ and $\beta$ be small?

In our example we assume for simplicity that they are both large. This corresponds to a ‘strongly overparametrized’ setting, i.e., the impossibility to learn even with loose accuracy and low confidence. With this assumption, we get in the above toy example a strong non-estimability result. But the above example works for any $\alpha,\beta$. Had we assumed $\alpha,\beta$ to be small, we would only get a weak non-estimability result (as one should expect).

I would like to thank the authors for their detailed new revision. I believe that my concerns regarding the definition of over-parameterization is largely resolved. So I will bump the score up to 8.

However, I did not closely track your discussion with Reviewer bL1w. While it seems that all reviewers including me think that this paper is interesting, Reviewer bL1w did raise some good points on how the results could be applied to the existing generalization bounds in the literature. Because I did not fully digest those discussions to tell whether the new Appendix C offers a comprehensive answer, I will also lower my confidence to to 3.

Thank you for your detailed feedback, which includes much appreciated comments regarding the fine details in the appendix.

Before addressing your questions in detail, we would like to first clarify a few high-level points.

It seems to us that some of your questions stem from a disconnect of our definition of ‘distribution-dependent’ and the one you have in mind. For example in your third point, you mention:

There are plenty of papers that actively take the sampling distribution into account in their analysis and are not even cited here. The most obvious examples would be [3] and the NTK literature [4].

However, the bounds in these works only take into account the training set and the output hypothesis, but not the properties of the distributions themselves. By ‘distribution dependent’ bound we mean (throughout the paper) that the bound takes into account some property of the underlying data distribution (e.g., boundedness, information about the moments, smoothness…). However, note that receiving a training sample does not qualify a bound for being distribution dependent.

Relatedly, you are asking:

In the current version of the paper, on page 13, margin bounds are presented as part of examples of bounds that are "distribution independent", which is quite disputable.

All bounds we mention in Appendix B do not assume anything about the algorithm being considered or the underlying distribution. Hence they fall within the setting of Theorem 1. If you disagree, can you lay out your argument based on one paper from that list? For example, why is this disputable over the margin-based bounds? They are just a function of the training set and the output hypothesis.

Does this clarify some of your questions regarding distribution dependence?

Further, you are asking:

Which bounds in the existing literature are really "in the overparametrized setting"?

We are not sure what you mean when you call a bound being in the overparametrized setting – overparametrization is a quantifier of a learning task, not of a generalization bound.

Since ‘overparametrized’ means (roughly speaking) not having enough training samples to learn over all distributions, and none of these bounds specifically exclude this regime, all our results apply to all of the distribution-independent bounds that we cite, once one is situated in this learning setting.

Does this answer your question? If not, could you please expand on this point?

Example 2

About the main result in [4]: Generalization bound $\leq \widetilde{O}\sqrt{\frac{y^\top H^{-1}y}{n}}$. Where would you classify this example? Does Theorem 3 apply to it? It seems highly likely that such a bound is not vacuous in practice, and almost impossible to determine whether your definition of "overparametrization" holds in this case.

in the main paper, you make strong claims that almost all existing research is invalid or trivial because your theorems prove that those bounds are necessarily vacuous.

To be clear, we do not claim that "almost all existing research is invalid or trivial". We claim that many published bounds are not uniformly tight, meaning that there exist (distribution, algorithm) pairs for which the bound will not be tight (in fact, we show there are many such pairs). This does not mean that exisiting research is "invalid", "trivial", or "vacuous". We are showing a specific type of limitation for bounds that are distribution and algorithm independent.

However, existing results are complicated to interpret and your theorems rely on strong assumptions which are impossible to verify in practice.

You can't go back and forth between vagueness and precision to your own advantage. For instance, regarding overparametrization, it not fair to, as you do, first write in the paper that it is commonly accepted that "most real world problems are in the overparametrized setting" and use this justify saying that all of your theorems apply to those papers, and then, when challenged by another reviewer about your own definition of overparametrization, argue that you can do anything you want any way because the concept has not been rigorously defined in the community in a strict mathematical sense yet (which is true). In most real life scenarios, the only thing that is really clear about overparametrization is that the number of parameters is greater than the number of samples, a much weaker condition.

Following your comments, we have written a detailed and careful answer explaining why our results in Theorem 1 and 2 apply to deep learning settings. Kindly read this explanation in General Answer 1: Our Definition of Overparametrization above (including the part Why Theorems 1 and 2 Apply to Generalization Bounds For Deep Learning). As we explain there, our results in Theorem 1 and 2 basically require only two assumptions:

1. Distribution and algorithm independent generalization bound. Namely, the generalization bound of interest does not explicitly state which population distributions it applies to, and does not rely on the specifics of the training algorithm.
2. This is a deep learning setting, so in particular the number of edges in the neural network is much larger than the sample size.

Both of these are straightforward assumptions that can readily be verified. While we agree that "existing results are complicated to interpret" in various ways, checking these two assumptions does not require any complicated interpretation. One can simply read the statement of the generalization bound of interest to see if it is stated for a general population distribution and a general algorithm, and check that the neural network has a number of edges much larger than the sample size. That's pretty much all that is needed for Theorems 1 and 2 to apply.

Margin Bounds

You raise the question of whether our negative results in Theorems 1 and 2 apply to margin bounds. We assert that they do indeed apply. We will explain this both via a concrete example, and then in a more general discussion.

Example: A Margin Bound That Is Not Uniformly Tight

To follow up on the specific example you mentioned in your comment above, let the domain $\mathcal{X} = \\{x \in \mathbb{R}^d: ~ \\|x\\|_2 = 1\\}$ be the unit sphere in $\mathbb{R}^d$. Consider a half-space classifier, and a margin bound of the form $f(|W|, \gamma)$ as you described, such that $f$ (an upper bound on the difference between the population and empirical loss) is small only if the margin $\gamma$ is large. We will show that $f$ is not uniformly tight.

Indeed, consider a population distribution $\mathcal{D}$ that has (say) a uniform marginal on the domain $\mathcal{X}$, with labels that are generated by a specific half space $h^*$ (e.g., the half space that passes through the origin and is perpendicular to the $x_0$ axis). Consider an algorithm $A$ the has a bias towards $h^*$, in the sense that it will output $h^*$ whenever the training set is consistent with $h^*$.

In this case, given samples from $\mathcal{D}$, with probability $1$, $A$ will output $h^*$. Hence, the population loss and the empirical loss are the same (they are both exactly 0). Because the marginal of the population distribution on the domain is uniform, the population margin is 0, and therefore the empirical margin $\gamma$ will be close to $0$ (even for a training set that is small compared to the dimension $d$). Thus, $f(|W|, \gamma)$ is large, but the generalization gap is 0. Hence, the bound $f(|W|, \gamma)$ is not tight for the pair $(\mathcal{D}, A)$.

Note that our results in the paper are stronger, in the sense that they show that there exist many (distribution, algorithm) pairs for which the bound is not tight, not just one.

General Case: Why Margin Bounds Are Not Uniformly Tight

More generally, in margin bounds the difference between the empirical and population loss is bounded by a quantity $f = f(|W|, \gamma)$. This quantity $f$ is strictly a function of the selected hypothesis and of the training sample. As such, a bound of this kind satisfies the algorithm- and distribution-independence requirements of Theorem 1. If the bound is applied to a neural network that has a lot more edges than the size of the training set, then this is an overparamterized setting (as we explain in detail in General Answer 1: Our Definition of Overparametrization), and therefore Theorem 1 implies that the bound $f$ will not be uniformly tight. This is a dry logical consequence of Theorem 1.

We agree with the observation that the quantities $|W|$ and $\gamma$ depend in nontrivial ways on the population distribution and on the training algorithm, and that therefore the quantity $f(|W|, \gamma)$ depends indirectly on the on the population distribution and on the training algorithm. This is not a problem, because this is always true: a bound that depends on the selected hypothesis and on the training sample must always depend indirectly on the training algorithm and on the population distribution. That does not detract from the applicability of Theorem 1.

Thanks for your comment.

From this comment, I think we are getting closer to understanding each other. It seems that we agree on the strict mathematical facts, but not on the implications in terms of how you informally explain your results: I think the problem lies in our different opinions regarding how bad it is to not be "uniformly tight".

I agree from your example that theorem applies there (assuming "overparametrization", which again, in this example, is NOT implied by the statement that there are more parameters than training samples), but the distributions for which the bound is vacuous will not be the "interesting" distributions towards which margin parameter is biased. For instance, if the margin is close to 1, it means the data has to lie approximately in two diametrically opposite points, and the bound can be very tight. It doesn't mean that there don't exist many distributions for which the bound is not tight, but they can be identified as unfavorable distributions by seeing that the margin is not close to 1. The art of learning theory in its current ("distribution-independent") form is to formulate the problem in a feature space where this analogy holds for real life observed empirical distributions.

Again, I think your results are worthy of publication if the informal statements which accompany them are very substantially toned down (in the above example, it is interesting to know that there are many distributions for which the margin will not be that high and the bound will not be tight). Your paper reads as if the existing approaches are invalidated by your results. For the above reasons (please read my more detailed comments in the main thread), this is not the case at all. Most of the statements you make in sections C and D can be interpreted as misleading when taking all those facts into account. For instance, saying that "alex has no specific description of $\mathcal{H}_0$ and "Alex's analysis is lacking" are both disputable statements: it is disputable whether "Alex" in fact has a way of telling if we are likely to be in $\mathcal{H}_0$ based on an empirical observation (of a high margin or low intrinsic dimension), and it is disputable whether Alex knows he is in an overparametrized setting.

Also, you say "This story highlights our point in Theorems 1 and 2, which is that bounds that do not explicitly depend on the learning algorithm must be vacuous for many algorithms, and in particular are likely to be vacuous for SGD or any specific algorithm of interest." This is only true for certain distributions (it is not true of "SGD" in general): further, this is known (in less precise terms than the ones in your theorems): the bounds are only intended to work on data which is "natural" enough to make the margin/other parameters behave sufficiently favorably. Saying that your theorem implies that these existing results are vacuous for many distributions is like saying that a truly (explicitly) distribution dependent algorithm is vacuous/false when the distribution does not satisfy the prescribed condition. In both cases, this is hardly as much of a cause for concern as you hint.

As I said in my review, the current version is dismissive of much of the literature in a way which is not fully justified and is very likely to mislead the reader and the community. You ought to upload a significant revision that substantially tones down your statements (I know it will take a lot of work, but I think it's necessary). I don't think you results are quite as far reaching as you claim in the first version of the paper, but they are still very interesting. If (and only if) you can describe them in a way that will not mislead the readers, they will become highly worthy of publication and greatly benefit the community. If you stick to the current version, I will have to lower my score.

After carefully reading your review, we would like to confirm (or clarify) our understanding before providing our response in full detail.

We will be happy to reach a common understanding regarding the interpretation of our theorems.

For example:

For instance, author claims in section 5.1 that 'Most published generalization bounds do not restrict the set of distributions or algorithms the bound should apply for. Hence, they should work in all scenarios.' This is not true, having a bound holding for any distribution does not imply that the bound will be tight on all situations (and this is precisely what your work is proving).

We think the confusion stems from ‘should work’ which you interpret as ’should be tight’. Is that correct? We meant ‘should work’ = ‘should hold’.

So we suggest changing our text as follows:

Most published generalization bounds do not restrict the set of distributions or algorithms the bound should apply for. Hence, they should upper bound the risk in all scenarios. Because these bounds do not distinguish between distributions that an algorithm performs well on and distributions that it does not, such bounds have no other option but to declare the largest true error possible (and become vacuous).

Does this clear things up in this example?

Is there an agreed-upon definition of overparametrization in the literature? So we can refer to it in our answers. If not, how would you mathematically define overparametrization? How would you define such a concept over non-parametrized spaces? Please note that Section 4 gives the motivation for our definition.

After carefully reading your review, we would like to confirm (or clarify) our understanding before providing our response in full detail.

Thank you for the reference [Haussler et al 1988]! We were not familiar with it. Can you refer us to the location of your claim about cross-validation? After searching the paper, the word ‘validation’ does not appear there. Regardless, your point makes sense. To avoid being imprecise, we will change the term cross-validation (which is indeed an umbrella term for several methods) to using a validation set (the holdout method - the simplest form of cross-validation), which is the staple for tuning the hyperparameters of neural networks.

Do you find the above now a precise statement?

I agree that there is no agreed-upon definition of overparametrization, except perhaps having a larger number of parameters than samples. It is legitimate that you want to introduce your own definition, and the definition you introduce is somewhat natural.

However, this doesn't change anything to the fact that your argument that "all existing results must be vacuous since they are typically applied to the overparamterized setting" is incorrect. I am still not at all convinced you have invalidated nearly any of the existing literature. The "universally accepted fact" that the settings currently studied are "in the overparametrized regime" is based on a vague understanding of the concept (probably mostly about counting parameters).

As I already tried to explain in my review, a lot of existing research provides bounds in a way that constructs custom function classes which indirectly take properties of the sampling distribution into account. For instance, if a bound depends on the classification margin, then to show that it is "in the overparametrized setting'", you would need to show that the set of all functions which can achieve such a high margin is "large enough'' to qualify as "overparametrized"'. This is especially hard because the concept of the margin and the corresponding function class have been defined to further the opposite cause.

I will answer the other points in more detail in the thread of my review.

Like my peers, I have no clear definition of what the 'overparametrised setting' should be. However, please note that in my review, I never went against this notion as I mainly asked for more explanation.

Like Rev. Hb6n, I would like expand on Definition 2.

First of all you said in you previous answer that it is possible to take as $\mathbb{D}$ the class of all possible distribution realisable by a neural network architecture. However your definition holds only for finite families and is justified by the fact you draw uniformly over all distribution over $\mathbb{D}$. How do you generalise your definition to infinite (possibly uncountable) classes of distribution?

Furthermore, I did not grasp the link between the intuitive notion of overparametrisation (number of weights far greater than the dataset size) and Def. 2.

Indeed, let us take a neural network with a single neuron aiming to solve a classification task. Assume that it is possible, as you claim, to take $\mathbb{D}$ to be the set of all possible distributions related to this classification task. Then, I would say intuitively (please correct me if I am wrong) that for $\alpha$ small enough and $\beta$ large enough, we cannot hope, even for a large $n$, for a single neuron to generalise well on any distribution in $\mathbb{D}$. Therefore this single neuron architecture would be $(\alpha,\beta,n)$ overparametrised with respect to $\mathbb{D}$, which goes against the intuitive notion mentioned above.

Did I miss something?

I am not aware of a formal definition of over-parameterization that is universal among the literature. But I do believe that there is an agreed-upon intuition that an over-parameterized function class would have enough capacity to perfectly fit to "arbitrary data." Some papers also require a "large number" of solutions that perfectly fit any particular dataset. Often, people use the rule-of-thumb that $d \gg n$, which $d$ is the number of parameters, but this only makes sense when the function class is linear. One paper that discusses over-parameterization in great details is [1], and of course there are other approaches.

From my reading of this paper, it is not immediately clear whether Definition 2 in this paper fits the intuitive notion that an over-parameterized should "interpolate" any dataset of certain size. However, the author already addressed this concern in Theorem 2, where their definition implies that the size of training data is almost half the VC-dim of the function class. One easy fix to this issue is to simply bring a sketch of this argument to Section 4.

Alternatively, I am thinking one could also appeal to the Rademacher complexity. For binary classification problem, a function class $\\{ f(\theta; \cdot) : \theta \in \Theta\\}$ would be intuitively over-paremeterized over a set $\\{x_i\\}_{i=1}^n$ if for any iid Bernoulli r.v. $\epsilon_i$, there exists $\theta$ so that $\epsilon_i f(\theta; x_i) \ge 1$ for all $i$. I think it is equally valid, and perhaps to easier for the readers to understand, if the authors show that Definition 2 implies this statement.

[1] Belkin, Mikhail. "Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation." Acta Numerica 30, 2021.

Dear Rev. Hb6n,

Concerning your remark 'I want to point out that the correct direction should Definition IV $\rightarrow$ Definition III because your definition should cover the existing intuitive notion of over-parameterization', I believe that the authors are right on this one.

Indeed, their contributions are negative results, as they prove it is impossible for two assertions to hold simultaneously (with high probability). Thus, a deep net satisfying Definition III is overparametrised in the sense of Definition IV and thus, is also concerned by the negative results of this work.

That being said, it is indeed worth notifying that, as Definition IV does not imply Definition I, the former may not be enough to prove sharp positive results on deep nets satisfying the latter.

Hope this helps!

First, I want to point out that the correct direction should Definition IV $\Rightarrow$ Definition III because your definition should cover the existing intuitive notion of over-parameterization.

Back to the important part, now it is clear to me that our (mostly) philosophical debate is hitting diminishing return. I fact, I do not think most of the debate were necessary because many reviewers (e.g. iLzH and me) are not against your line of reasoning in the first place. Personally, I am mainly asking for additional clarification and examples to support your results. In other words, I am more worried that this paper as currently written would not convince other readers, especially those who only take a cursory look at the statements.

I recommend that you incorporate the key points in our discussions into a revision. While you made some good points, they are mostly made without complete contexts and scattered over many threads (whose total length probably exceeds a full paper). Now is time turn our debates into something organized and concrete.

Here are the two key points I want to see in the revision:

1. A thorough discussion of why your definition of over-parameterization is consistent with the intuitive notions current used in the literature. This needs to include specific example such as the content you had written above. And you need to explain why this new definition is more useful than the existing notions.

2. As reviewer bL1w noted, the statements of Theorem 1 and 3 are not particularly clear on their exact implications. I personally think the theorems are fine, but evidently they are not clear to some. Therefore, I would like to see a few examples on how your results would apply to some existing generalization bounds in the literature.

3. I agree with reviewer bL1w that your response are not consistent regarding the formality and preciseness of the concepts such as "over-parameterization" and "distribution-independence". Therefore, in the revision, you must be careful with how exact your definition and explanations are.

I will defer any updates to my assessment of this paper until I read the revised version. And I will make clear that I will lower the scores if the revision is not addressing the concerns as I laid-out above.

Why Theorems 1 and 2 Apply to Generalization Bounds For Deep Learning

Some reviewers have questioned our view that "most real world problems are in the overparametrized setting" (as Reviewer bL1w15 puts it), or that the limitations we prove in Theorems 1 and 2 on the tightness of generalization bounds apply to actual generalization bounds in the literature. The applicability of Theorems 1 and 2 to deep learning is actually a fairly straightforward and objective mathematical fact, as we explain in this section.

Fix a reasonable sample size $n$, a deep neural network $N$, and a training algorithm for that network (e.g., SGD). Take any generalization bound B. There are two possibilities:

1. The bound B explicitly states that it only applies to a specific subset of all possible population distributions or to a specific learning algorithm, and employs these restrictions in its proof. (In this case, we are happy, because these are the types of bounds we are advocating for. [Note that Theorem 3 might still imply some limitations for the bound.])
2. The bound B does not explicitly state which population distributions it applies to, and does not rely on the specifics of the training algorithm.

The limitations we prove in Theorems 1 and 2 apply to any bound B that falls in the second category. The literature contains many such bounds, we can provide a long list. The following explains why Theorems 1 and 2 apply to any bound B of the second type.

Because the bound B does not explicitly state any limitations on the set of population distributions that it applies to, in particular this means that B must hold (i.e., be a valid upper bound on the population loss) for all the distributions in $\mathbb{D}$, the collection of all distributions that are realizable by the network N. Because the bound B does not make any specific assumptions on the training algorithm, in particular it must hold (i.e., be a valid upper bound on the population loss) for any of the algorithms $A_h$ and the ERM algorithms mentioned in Theorem 1.

Now, as discussed in the previous sections, it is well known (from [Maa94], [BMM98], [Sak93], etc.) that in a large neural network like N, the VC dimension is roughly linear in the number of edges in the network. In deep learning, the number of edges in the network is much larger than the sample size $n$, and therefore, Definition III of overparameterization (mentioned above) holds. The implication Definition III $\implies$ Definition IV above entails that we are in the overparamterized setting as in Definition 2 in the paper (in other words, using a sample of size $n$ it is not possible to learn all the distributions in $\mathbb{D}$). Hence, the assumptions of Theorem 1 are met, and therefore Theorem 1 implies that the bound B is not uniformly tight.

To recap, we have used only two assumptions:

• The bound B falls in category 2 above.
• This is a deep learning setting, so in particular the number of edges in the network N is much larger than the sample size $n$.

These two assumptions are straightforward and easy to verify. Hence, Theorem 1 applies to many bounds in the deep learning literature. (A similar reasoning applies also to Theorem 2.)

$~$

$~$

• [Maa94] W. Maass. Neural nets with superlinear VC-dimension. Neural Computation, 6(5):877- 884, 1994.
• [BMM98] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC-dimension bounds for piecewise polynomial networks. Neural Computation, 10(8):2159–2173, Nov 1998.
• [Sak93] A. Sakurai. Tighter bounds on the VC-dimension of three-layer networks. In World Congress on Neural Networks, volume 3, pages 540- 543, Hillsdale, NJ, 1993. Erlbaum.

I think there are still severe misunderstandings regarding the actual nature of most generalization bounds in the learning theory literature.

You say: "definition I (more parameters than samples) implies Definition II (Small VC dimension)"

As I have tried to explain in my previous comments, this is only true if the function class considered is the class of all neural networks with a particular architecture. This excludes almost all "recent" (after 2015) works, including the ones you mention in your paper. In other words, your comment only applies in the case of very old results such as those in the three references you cite in your comment [Maa94, BMM98, Sak93]. In most recent results, for instance those in [7,11], there is a restriction on the norms of the weights matrices, which means your definition of overparametrization is now different and much harder to check, and it's questionable whether what people mean when they say that "neural networks are typically overparametrized" implies this.

For the sake of illustration, consider an extremely simplified scenario: the input $x\in\mathbb{R}^d$ for a very large dimensionality $d$. This is a 1 layer equivalent of the bounds in [11]. A basic result says that the generalization of a linear classifier $w\in\mathbb{R}^d$ with $\|w\|\leq R$ for some constant $R$ scales like $O\left(\sqrt{\frac{R^2}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}\right).$ There is no dependence on the dimension/number of parameters here. However, for your definition of "overparametrization" to hold, it must be the case that $(\mathcal{H}_R,\mathbb{D})$ is not learnable, where $\mathcal{H}_R$ is the function class defined by the set of weights $w\in\mathbb{R}^d$. This condition is much harder to check.

This is not just a remote example: nearly all works in modern learning theory of neural networks involve and utilize subtle constraints on the norms of the weight matrices, which makes the situation similar. That doesn't mean that your work is not worthy of interest: it is still interesting to say that whether or not norm based bounds are tied is a problem which is fundamentally related to whether the abstract function class defined is small enough to make the problem no longer overparametrized. However, it does make your paper's current version misleading in its statements: even for simple examples such as the bounds in [7], you should not be saying things like "alex's analysis is lacking" or "likely to be vacuous for SGD or any specific algorithm of interest" (this is how you describe [7]), because there is no strong evidence that this is true.

References

[1] IAN F. BLAKE AND CHRIS STUDHOLME, PROPERTIES OF RANDOM MATRICES AND APPLICATIONS, 2006

[2] Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables, 2021. (Arxiv)

[3] C Wei, T Ma, Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin, ICML 2019.

[4] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang, Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks, ICML 2019.

[5] Vaishnavh Nagarajan, J. Zico Kolter, Uniform convergence may be unable to explain generalization in deep learning, NeurIPS 2019

[6] Philip M. Long, Hanie Sedghi, Generalization bounds for deep convolutional neural networks, ICLR 2020

[7] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. Spectrally-normalized margin bounds for neural networks, NeurIPS 2017.

[8] Wei and Ma, Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation, NeurIPS 2019

[9] Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-bayesian generalization bounds for deep networks via generalizing noise-resilience, ICML 2019.

[10] Antoine Ledent, Waleed Mustafa, Yunwen Lei, Marius Kloft, Norm-based generalisation bounds for multi-class convolutional neural networks, AAAI 2021.

[11] Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, Roland Kwitt, On Measuring Excess Capacity in Neural Networks, NeurIPS 2023.

[12] Size-Independent Sample Complexity of Neural Networks. Noah Golowich, Alexander Rakhlin, Ohad Shamir, COLT 2018.

[13] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, Alexander Tsigler, Benign Overfitting in Linear Regression

[14] Shamir, The Implicit Bias of Benign Overfitting, COLT 2022.

[15 ] Tomer Galanti, Mengjia Xu, Liane Galanti, Tomaso Poggio , Norm-based Generalization Bounds for Compositionally Sparse Neural Networks

[Maa94] W. Maass. Neural nets with superlinear VC-dimension. Neural Computation, 6(5):877- 884, 1994.

[BMM98] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear VC-dimension bounds for piecewise polynomial networks. Neural Computation, 10(8):2159–2173, Nov 1998.

[Sak93] A. Sakurai. Tighter bounds on the VC-dimension of three-layer networks. In World Congress on Neural Networks, volume 3, pages 540- 543, Hillsdale, NJ, 1993. Erlbaum.

Dear Reviewer bL1w,

Thank you for your detailed comment. Just to confirm: did you see the response titled Example: A Margin Bound That Is Not Uniformly Tight and General Case: Why Margin Bounds Are Not Uniformly Tight that we wrote in your review thread? (We simply want to be completely sure that we are all on the same page before responding further.)

Dear Reviewer bL1w,

$~$

Thanks again for your dedicated and thoughtful engagement with our paper.

You wrote "I think we are getting closer to understanding each other. It seems that we agree on the strict mathematical facts, but not on the implications in terms of how you informally explain your results." We generally agree with this characterization. At least the majority of the differences between our views focus on matters of interpretation.

We are open to revising the interpretation of the results offered in the paper, with the hope of reaching a formulation that everyone feels comfortable with. It is also possible that, in the interest of scientific prudence and precision, the paper should focus on presenting the mathematical facts, and should simply include less interpretational language. This would allow the reader (and the community) to reach their own conclusions, without requiring ICLR to endorse any specific views.

$~$

Before we embark on making substantial changes, we wanted to ask two questions:

$~$

1. Can you identify which locations in the paper are in your view most in need of revision? We understand that you take issue with Appendices C and D. Are there any additional specific portions of the paper that you would suggest that we focus our attention on?

$~$

2. We have carefully read the concerns that you and the other reviewers have raised regarding the narrative surrounding our results. We know of various aspects of our interpretation that you find misleading or incorrect. But we are less certain as to what your preferred interpretation of our results would be. In your view, what is the best, most balanced interpretation of these results that you would like to see us expand upon in our revision? Please do not feel obligated to answer this question (as it is of course our duty as authors to explain our work). However, any pointers that summarize what you view as the best interpretation of the results would be very welcome and appreciated.

General Answer 3: New Revision of The Paper

We have uploaded a new revision of the paper that incorporates a lot of the feedback that the reviewers have provided. To accommodate an easy review of the changes, the main changes are highlighted in blue in the new PDF.

The changes include:

• Changed: Significant change of language concerning the consequences and interpretation of our formal results. The new language is aiming to be more scientifically prudent, and to clearly separate matters of objective mathematical fact from matters that are open for debate, on which the reader might want to form an independent opinion.
• Removed: The previous revision contained two appendices that some reviewers felt were misleading. These were former appendix C ("On Optimistic Application of Distribution- and Algorithm-independent Bounds"), and former appendix D (the discussion about "Alex"). We have removed these appendices to avoid any possibility of misleading the reader.
• Added: New Appendix C.1, containing a discussion of Margin Bounds.
• Added: New Appendix D, containing a discussion of our definition of overparameterization, including a comparison to alternative definitions.

Additionally, we have reorganized some parts of the text, and have improved some of the proofs.

We are looking forward to hearing your feedback on the this revision.