Fantastic Generalization Measures are Nowhere to be Found
Authors: Michael Gastpar
Ido Nachum
Jonathan Shafer
Thomas Weinberger
Venue: ICLR 2024 poster (2024)
Keywords: overparametrization
generalization
Primary area: learning theory
TL;DR: We uncover some of the reasons behind the failure of many generalization measures to estimate the performance of overparametrized models.

Abstract: We study the notion of a generalization bound being _uniformly tight_, meaning that the difference between the bound and the population loss is small for all learning algorithms and all population distributions. Numerous generalization bounds have been proposed in the literature as potential explanations for the ability of neural networks to generalize in the overparameterized setting. 
However, in their paper "Fantastic Generalization Measures and Where to Find Them," Jiang et al. (2020) examine more than a dozen generalization bounds, and show empirically that none of them are uniformly tight. This raises the question of whether uniformly-tight generalization bounds are at all possible in the overparameterized setting. We consider two types of generalization bounds: (1) bounds that may depend on the training set and the learned hypothesis (e.g., margin bounds). We prove mathematically that no such bound can be uniformly tight in the overparameterized setting; (2) bounds that may in addition also depend on the learning algorithm (e.g., stability bounds). For these bounds, we show a trade-off between the algorithm's performance and the bound's tightness. Namely, if the algorithm achieves good accuracy on certain distributions, then no generalization bound can be uniformly tight for it in the overparameterized setting. We explain how these formal results can, in our view, inform research on  generalization bounds for neural networks, while stressing that other interpretations of these results are also possible.

Published as a conference paper at ICLR 2024
FANTASTIC GENERALIZATION MEASURES ARE NOWHERE TO BE FOUND
Michael Gastpar EPFI. mi chael gastppareepfl..h
Ido Nachum
University of Haifa
inachum@univ. hai acc i.
Jonathan Shafer
Thomas Weinberger
MIT shaferjo@mit.edu
EPFL thomas weinberrezeeppl.cco
ABSTRACT
We study the notion of generalization bound being uniformly tight, meaning that the difference between the bound and the population loss is small for all learning algorithms and all population distributions. Numerous generalization bounds have been proposed in the literature as potential explanations for the ability of neural networks to generalize in the overparameterized setting. However, in their paper "Fantastic Generalization Measures and Where to Find Them," " Jiang et al. (2020) examine more than dozen generalization bounds, and show empirically that none of them are uniformly tight. This raises the question of whether uniformly-tight generalization bounds are all possible in the overparameterized setting. We consider two types of generalization bounds: (1) bounds that may depend on the training and the learned hypothesis (e.g.. margin bounds). We prove mathemat- ically that no such bound can be uniformly tight in the overparameterized setting: (2) bounds that may addition also depend on the learning algorithm (c.g., sta- bility bounds). For these bounds, we show a trade-off between the algorithm's 's performance and the bound's tightness. Namely, if the algorithm achieves good accuracy on certain distributions, then no generalization bound can be uniformly tight for in the overparameterized setting. We explain how these formal results can, in our view, inform research generalization bounds for neural networks, while stressing that other interpretations of these results are also possible.
INTRODUCTION
There has been extensive research recent years aiming to understand generalization in neural networks. Principled mathematical approaches often focus proving generalization bounds, which bound the population risk from above by quantities depending on the training set and the trained vacuous', and model. Unfortunately, many known bounds of this type often very weak, generalization of they do not imply performance guarantees that could explain the strong real-world neural networks. Incidentally, there might be good reason for this: in this paper show that it is mathematically impossible for certain types of generalization bounds to be tight in a specific sense.
Generalization bounds the literature often take the following form:
LD Ls(A(S)) + C(A(S),)).
where S is the training set, A(S) is the hypothesis selected by the learning algorithm A, LD and Ls denote the population and empirical risk respectively. C' is some measure of complexity. and the inequality holds with high probability over the choice of S. For example, in their paper "Fantastic Generalization Measures and Where Find Them," " Jiang al. (2020) examine more than a dozen generalization bounds of this form that have been suggested in the literature.
A generalization hound vacuous if implies population loss better than guessing random labels.

---

Published as a conference paper at ICLR 2024
For generalization bound to be useful, it should ideally be right, meaning that the difference be- tween the two sides of Eq. (1) is small with high probability. Moreover, we shall call bound uniformly tight (Definition 7) if it is tight for every (distribution, algorithm)-pair.
In order to explain generalization deep neural networks, it is necessary that the bound be tight in the overparameterized setting, which roughly means that the number of parameters in the networks is much larger than the number of examples in the training set (Definition 2; further definitions appear in Sections these two criteria, it is natural to ask:
6). Given that essentially all known generalization bounds do not satisfy
Does there exist a generulization bound of the form of Eq. (1) that is uni- formly right in the overparameterized setting?
Question 1.
Obviously, one can always bound the population loss using a validation set. However, the upper bound in Eq. (1) depends only the hypothesis A(S) and the training set S, so using additional validation set does not technically satisfy the requirement of Question 1. Beyond technicalities, using a validation set conceptually very different from generalization bound. Using a validation set is post hoc measurement that provides little insight as to why a certain algorithm does or does not generalize. In contrast, a meaningful generalization bound (like the VC bound for example) provides scientific theory that predicts the behavior of learning algorithms in a wide range of conditions, and can inform the design of novel learning systems.
One might imagine that the generalization bounds for neural networks surveyed by Jiang et al. (2020) are not uniformly tight simply because the analyses in the proofs of these bounds are not optimal, and that more careful proof might establish tighter bound with better constants. Or perhaps, none of these measures yield uniformly-tight bounds for large neural networks, but in the future researchers might devise better complexity measures of the form of Eq. (1) that do. We show that obtaining a bound the form of Eq. (1) that is uniformly tight requires more assumptions than typically found in the current literature.
2
OUR CONTRIBUTIONS
Following is an overview of our contributions, which are also summarized in Table 1. Our results are stated using a notion of estimubility, which is presented informally Eq. (2) below (for formal definitions, see Definitions 3 and 4). All proofs appear in the appendices.
2.1 DISTRIBUTION- AND ALGORITHN-
GENERALIZATION BOUNDS
One central message of this paper is that the answer to Question is negative. The conclusion draw from this and further analysis is that generalization bounds can be uniformly tight in the overparameterized setting, but only under suitable assumptions on the population distribution or the learning algorithm. Arguably, many bounds in the literature are presented without assumptions of the type we show are necessary for uniform tightness - so their tightness for any specific use case is not guaranteed.
To reason about Question 1, we introduce the notion of estimability. Informally, a hypothesis class H. is estimable with accuracy if there exists estimator E such that for every algorithm A and every H-realizable distribution D, the inequality
(o(A (((9))-=(((SS),))))) ((A(S)))) <E
holds with high probability over the choice of 5 (see Definition 3). An immediate (but conceptually important) observation is that, in the realizable case, a uniformly tight generalization bound like Eq. (1) exists and only is estimable (Claim 1). Furthermore, if H not estimable then there exists no uniformly tight bound in Eq. (1) also for learning in the agnostic (non-realizable) setting.
"The VC bound does satisfy Question because it is vacuous in the overparameterized setting.
2

---

Published as a conference paper at ICLR 2024
Our negative results for the realizable setting are stronger than (i.e., they imply) negative results for the agnostic setting.
Engorithm-IIneepndeeen Independent Distribution Inriiion--ddeeddeeen
Algorithm-
Algorithn-Dependeri Distribution- Intriionnnddeeedeentt
Algorithn-Dependere Distribution- Deenndden-
X
Bounds not uniformly tight
Bounds can be tight
trade-off (see Figure 1)
Theorem 1:
In the overparameter- ized setting, any bound is not tight for a large fraction of (algorithm. distribution) combinations.
Theorem 3: In the overparameterized setting, for any specific algorithm there is a trade-off between population loss and estimability.
We suggest that future work focus on generalization bounds for spe- cific combinations of algorithms and distributions.
Theorem 2 (quantitative result): For sample size n S d/2, classes with VC dimension d are not timable for at least 49% of (algo- rithm, distribution) combinations.
Theorems 4 and 5 (quantitative results): A learning algorithm cannot simultane- ously perform well over the class of lin- car functions and be estimable.
Table 1: An overview: when can generalization bounds be tight the overparameterized setting?
Our first result shows that no hypothesis class H. is estimable in the overparameterized setting: Theorem (Informal Version of Theorem 2). Let H be a hypothesis class. If H has VC dimension d and the size of the training sel is at most d/2, then every estimator E. satisfying Eq. (2) has
8 2 1/8 o1).
We emphasize that the lower bound & 2 1/8 - o(1) Theorem 2 does not hold merely for a single ppttoooggcca' hard distribution. Rather, it holds for many ERMs over a sizable fraction of all H- realizable distributions.
We believe Theorem 2 is worthy of attention because it precludes uniform tightness in the overpa- rameterized setting for any generalization bound that depends solely on the training set, the learned hypothesis, and the hypothesis class. Determining which bounds in the literature neural networks fall within this category a matter of some debate. This category may arguably include some subset of the following bounds: VC bounds (Bartlett al., 2019), Rademacher bounds (Bartlett & Mendel- son, 2002), bounds based on the spectral norm (Pitas et al., 2017), Frobenius norm (Neyshabur et al., 2015b), path-norm (Neyshabur et al., 2015b), Fisher-Rao norm (Liang al., 2019), well PAC- measures (e.g., see the appendices of Jiang et al. (2020) and
Blyes-fsatness and sharpness-flatmnn Dziugaite et al. (2020)), and some compression bounds like Arora al. (2018). For further details on the aforementioned bounds, see Appendix B.I. We take an expansive position, arguing that the abovementioned bounds, when applied to large neural networks, fall within the framework of The- orem 2, and therefore are not uniformly tight; however, we acknowledge that other scholarly views (mentioned in Section 7) also have merit, and the reader is encouraged form an independent opinion on this matter.
2.2 ALGORITHMM- EEGORITII--DEPENDER DEPENDENT GENERALIZATION BOUNDS
An important facet of generalization not addressed by the formalism of Eq. (1) involves the choice of the training algorithm. The bound in Eq. (1) depends only on the training set S and the selected hypothesis A(S), and therefore it cannot capture certain beneficial aspects of the training algo- rithm. As simple example, consider the case of constant algorithm, that ignores the input S and
IIf a bound cannot be uniformly tight even just with respect to realizable distributions, then it definitely cannot be uniformly tight with respect all distributions (both realizable and not) in the more general agnostic setting. See Appendix for further details.
3

---

Published as a conference paper at ICLR 2024
always outputs specific fixed hypothesis hu E H. For such algorithm, choosing E such that E ())()) = (ho))) yields an excellent estimator of the population loss.*
Similarly, in the context of neural networks, it is possible that certain training algorithms like SGD perform 'implicit regularization', or satisfy various stability properties, etc. Therefore there might exist generalization bounds that are tight specifically for these algorithms. The work of Hardt et al. (2016) is a prominent example. We formalize this notion by considering generalization bounds of the form
Ld(A(S)) < (s((S)) C(A.S),
(3)
where the complexity C depends also the algorithm A. Eq. (3) leads to the following question:
Question 2.
For which algorithms does there exist a generalization bound of the form of Eq. (3) that is tight for all population distributions every overparameterized setting? ?
Question 2 prompts us to define algorithm- estimability (Definition 4) which is analogous to estimability (Eq. (2) and Definition 3), but involves an estimator EEA, S) that depends also on the learning algorithm. Our second result establishes a trade-off between learning performance and estimability:
Theorem (Informal Version of Theorem 3). Let H yd be a hypothesis class that is rich enough in certain technical sense." Then, for any learning algorithm A, at least one of the following conditions does not hold:
1. A learns a subset Ho = H with certain properties.'
2. A algorithm-depender estimable.
Theorem 3 states that if an algorithm learns well enough in the sense of Item 1, then the algorithm is not estimable, and this implies that there exists generalization bound for that algorithm that is tight across all population distributions.
Theorem 3 hinges the algorithm satisfying Item for a suitable choice of H and Ho- We emphasize that it known that this assumption can indeed be satisfied for some large neural network architectures when trained with SGD, For instance, the class of parity functions' is one suitable choice for H. It is well known that even simple fully-connected neural network is expressive enough to represent this class (e.g., Lemma 2 in Nachum & Yehudayoff, 2020). Furthermore, there exist specific network architectures that can provably learn suitable subset Ho of the class of parities using SGD (e.g., Theo- rem 1 in Abbe & Sandon, 2020).
Estimability
X
Learnability
Figure 1: Illustration of the trade-off implied by Theorem 3. 'I' represents perfect learning of Ho and perfect es- timation of A's accuracy. An algorithm cannot simultaneously perform well and be certain that it does so.
To illustrate the utility of Theorem 3, in Section 6.1 we conduct detailed mathematical study of classes H/ that are suitable for use in the theorem, and of the quantitative limitations the tightness of generalization bounds that these classes entail. Specifically, we show that an algo- rithm that can learn a suitable subset of the class parity functions is not estimable with æ 1/4 (see Theorem 5). More generally, we consider the class of linear functions over finite fields, which is gemeralization of parities, and show even stronger results. For example, for a field of size 11 (which corresponds
"This estimator works only for the constant algorithm that outputs It. its existence does not contradict Theorem 2.
'In Eq. (3) C' receives a complete description of the algorithm A. whereas in Eq. (1) it received A(S), which is the algorithm's output. Specifically, in Eq. (3), if A is deterministic then C' can compute the value A(S) using the inputs A and S.
"The precise details are specified in the formal version of Theorem 3.
NNaeely, the class of functions that an XOR of fixed subset of the input bits.
4

---

Published as a conference paper at ICLR 2024
to multiclass classification task with 11 labels), show that algorithm that learns suitable subclass is not estimable with E 0.45.
RELATED WORK
Here we address two works that also study cases where generalization bounds are vacuous. For further related works, see Appendix B.
The main theorems in Nagarajan & Kolter (2019c) (Theorem 3.1) and in Bartlett Long (2021) (Theorem 1) preclude the existence of tight algorithm-dependent generalization bounds in the over- parameterized setting. They show this only for bounds based on uniform convergence and for a lin- classifier (a single neuron). Also, Theorem 3.1 and Theorem 1 in Nagarajan & Kolter (2019c); Bartlett & Long (2021) consider the failure over a specific kind of distribution (Gaussian) and spe- cific type of SGD algorithm, and in the proof of Theorem 1, the authors different distribution for every sample.
While those results are technically incomparable ours, results in important ways: we show limitations for any kind of algorithm-depeenent generalization bound, for many algorithms, and for any architecture in the overparameterized setting while using the same distribution across all sample sizes, with concrete quantitative implications (see Section 6.
general and stronger
4 PRELIMINARIES
For our standard learning theory notation, see Appendix A.
Definition 1 (learnability). Let H be hypothesis class and let ID = (Di) set of H-realizable distributions. (H, D) (a, n,n) -learnale if there exists a (possibly randomized) algorithun A such that LD, (A)))) < a with probability at least 1- 3 over I =((( and S ~ Dj. We say that such an algorithm (a, B, n) -learss (H,ID).
Learning with neural networks is often considered example of an overparameterized setting: in most practical scenarios, the number of parameters of the network greatly exceeds the number of data points in the training set. Hence, for any given dataset of size n, there exist many different sets of weights (or hypotheses) that fit the data. This implies that in the absence of assumptions on the population distribution, the network will overfit in many scenarios. Since we study a general learning setting (the hypothesis class is not necessarily parametrized), we take the above implication as our definition an overparameterized setting:
Definition 2 (overparameterized setting). Let H. be hypothesis class, let T E N. let a, 2 0, and let (D.) be a finite collection of H-rrelizzable distributions. say that (H, TD) is an (a,3, 3, overparmeettr setting if (H, is not (a,B,1, (,,,,n))-earnaa leearnbbbe
For detailed discussion of how this definition compares to some common notions of overparam terization, see Appendix D.
5 BOUNDS THAT ARE ALGORITHM- AND DISTRIBUTION CANNOT BE UNIFORMLY TIGHT
To answer Question 1, we introduce the following framework:
Definition 3 (estimability). A hypothesis class H c y is ( with respect to loss function if there exists a function E H. x S IR such that for all algorithms A: (X x y)" H and all H-realizable distributions DD over X x it holds that
E(A(S), LLD(A()))))) <E
with probability at least 1-6 over S D We call such E an (c, -.estimatt of H.
Note that given an Algoritmm-independen and distribution crabbuttoonindependeen bound C, it is not hard to construct single (algorithm, distribution) pair that makes it vacuous. To illustrate this, consider
5

---

Published as a conference paper at ICLR 2024
the ERM defined Ac(S) arg min Le(h)-n C(,, S). Assume for simplicity that C' is generalization bound such that Eq. (1) holds with probability 1 for every H-realizable distribution D with labeling function lip. Then, with probability over S ~ D", LD (x)() Ls(Ac(()) C(Ac(5), & C(),,S), where the first inequality is Eq. (1) and the second follows from the construction of Ac-
Now assume that the setting is overparameterized (say with large a and B for a fixed n), i..., no algorithm can learn (with error a) the ground-truth labeling with probability at least 1-3 jointly over the uniform choice of the distributions, and n samples from the chosen distribution. This implies that for every algorithm A. there exists at least one distribution D' such that with probability at least 3, A fails to learn when S ~ (D')". Hence there exists a realizable distribution D' with deterministic labeling function hy such that, w.h.p., (D (Ac(S) a, which implies by the previous inequality that ((b S) a w.h.p. But then it holds w.h.p. that Chhp: S) >> 0= LD (hrr Ls (hp))) ) Hence the bound is w.h.p. not a-ttght for the pair (Angr D'), where Anp is the constant algorithm that always outputs lup..
The argument above considers the binary classification setting with the 0 loss and shows lack of tightness for single (algorithm, distribution) pair. In the next theorem, we consider arbitrary hypotheses classes (not necessarily binary) and show that any estimator is not tight for a large fraction of possible (algorithm, distribution) pairs.
Theorem 1. Let H be a hypothesis class, i be the 0 loss, D - (D be a finite collection of H-realizable distributions each associated with hypothesis h, and (H, (a.3, n) over- parameterized setting. For any h & H. lel An be an ERM algorithm that outputs h for any imput sample S consistent with h. Then, there exists a distribution DERM over ERMH (the set of all deterministic ERM algorithms over H.) such that for any estimator E of H. and for any e,y e [0, [0.1] at least one of the following conditions does not hold:
1. With probability at least - over I T [=T)( and S ~ DD.
| (A,, (S), LD, (An,, (S)) < c.
2. With probability at least 1 3 +++++ 7 over 1 - (((()))) S Dj, and Agnas ~ DENM, LD, (AD
E (AERM
<a-c.
In particular, is not (a/2, 3/2, (/2,3332,n)eetm esstimmbll..
Theorem 2 below is an application of Theorem 1 for VC classes. Theorem 2 shows that when Theorem is applied, we get substantial numerical values which highlight Theorem prevalence. Theorem 2. Let H be a hypothesis class of VC dimension d >> 1, and be the 0 - loss. Let X X be a set of size d shattered by Hx = (14))21 H. and let (D.) be the set of realizable distributions that correspond to Hx, where for all the marginal of D; on X is uniform over X. Let ERMHx be the set of all deterministic ERM algorithms for Hx. For any e Hx, let An, be an ERM algorithm that outputs h for any input sample S consistent with h. Then, for any estimator E of H. at least one of the following conditions does not hold:
1. With probability at least 1/2 over I I~ (=((((1 and S D),
d n I (LD, (Sh)
LD,
Ad
2. With probability at least 1/2-o(1) over
S D7, and AERM - (UERMH))
E (AERM (S),M((S) - LD, (AERM (S)) d-n
o())
4d
where U(RMH denotes the uniform distribution over ERM
In particular, H. is not ( d - (0), 1/) n) estimable for any n S d/2. The notation o(1)
denotes quantities that vanish as d goes to infinity.

---

Published as a conference paper at ICLR 2024
Theorem 2 states that any estimator E fails predict the performance of many ERM algorithms over many scenarios. If Item I does not hold, then E fails to estimate the success of algorithms An, in a situation where they perform very well (since by definition LD, (An, (S)) 0), despite the fact that these are very simple algorithms. If Item 2 does not hold, then E fails to estimate the performance of many ERM algorithms across many distributions, namely, on roughly 50% of (ERM, distribution) pairs.
5.1 DISCUSSION OF THEOREM? 2
Theorem 2 shows that bounds that depend solely on the training set, the learned hypothesis, and the hypothesis class cannot be uniformly tight in the overparameterized setting. More broadly, Jiang al. (2020) showed empirically that many published generalization bounds are in fact not tight. This is an empirical fact that calls for an explanation. Theorem 2 implies that algorithm- independent bounds being not-tight must be a very common phenomenon, in the sense that any bound that is tight on (a specific set of) simple cases, must be far from tight for many natural algorithms and distributions. Thus, Theorem 2 can at least partially explain the em- pirical findings of Jiang et al. (2020). To clarify, Theorem 2 does not imply that any specific bound is not tight for a specific (algorithm, distribution) pair, but it qualitatively matches the observation that lack of tightness is ubiquitous among geprrthmmindeepeneee
@ggorithm-independdee
bounds.
Many published generalization bounds are stated and proved without explicit restrictions on the set of distributions algorithms. Hence, these bounds are valid upper bounds on the population loss in all scenarios. Due to the limitations on estimability shown in Theorem 2, these bounds cannot fully distinguish between distributions for which the algorithm performs well and distributions for which it does not. Therefore, such bounds have no other option but to predict a large population error (making them loose for some cases in which the population error is not as large).
We emphasize that Theorem 2 shows that VC classes are not estimable, and hence do not admit tight generalization bounds, not merely over some pathological distribution, but in fairly simple setting. Let us elaborate: take dataset of natural images N (e.g., MNIST, CIFAR, etc.) and consider the uniform distribution over this set with a sample size n = W1/2. This is simple setting; we merely consider a small set of natural images. Still, Theorem 2 shows that without any assumption on the relation between the images and their labels, any estimator would not perform better than a random guess. That is, any estimator will fail over many ERMs (Item I and Item 2 in the theorem) with probability 1/2 over I ~ Ud([2T] and ~ DD to produce an estimate of the true error with an accuracy of 1/8. Hence, iestriutiioniineeenddde bounds can be loose even in simple setting.
6 ALGORITHN- BOUNDS ARE LIMITED BY LEARNABILITY- -ESILLTYYYYYSTIIIIILYYYY TRADE-OFF
To prove Theorem 2, we used constant algorithms, that is, algorithms that output the same hypothe- ses regardless of the input S. The true error of such algorithms is easy to estimate using the empirical error (by Hoeffding's 's inequality). Thus, it might be that adding the algorithm we use as a parameter for the estimator I might help. For example. Theorem 2 implies that sharpness based measures cannot precisely estimate the accuracy of a neural network for all algorithms. Yet. these measures might be good estimator when specifically considering SGD from random initialization.
estimability). A hypotheses class and a collection of algorithms (H, A) is (e, 8, n) -sstimable with respect to a loss function E if there exists a function E A + R such that for all algorithms A A and all realizable distributions D over X y holds
Definition 4 delggorrthm-dependeee
(E(A,S) L=((A())) <
with probability at least 1 - â over S ~ D= We call such E an algorittmmdeppnneet estimator H. If (H, (A)) is (e, ( neestmbbee, we say A is (e.d.in)e with respect to 'H and loss f.
The function E is now provided with a complete description of the algorithm used to generate hypothesis. Yet, the following theorem provides more subtle negative answer to Question 2 compared to Theorem 2. Learnability and estimability are mutually exclusive.
Theorem 3. Let H. Ho U Hi be a hypothesis class, let e be loss function, and let T To Ti be integers. Let D {D:)
To m be a set of H-realizable distributions such that Ta (D.) is
T
7

---

Published as a conference paper at ICLR 2024
realizable over Ho. and = (Di) T= is realizable over H1. Assume that (H, is (a,3,n) overparameterized setting, and furthermore assume:
< 1111111 1,,,-- where So Dia and S Di, lo ~ U(TTo) and I To + ((TT))
1) = 1- Then, for any learning algorithm A (possibly randomized), at least one of the following conditions does not hold:
1. A (e,0, Ho-
2. A is
2 ,0, n,, -e--immabelee with respect to H and loss E.
In particular, for any estimator E it holds (E(A,S) LD, LD, (A(S)) ae with probability of least nn over 1 [U(TT) and S ~ D7
As a concrete realization of Theorem with a simple set of parameters, we refer the reader to Theorem in Section 6.1 where we consider multiclass classification with labels and the 0-1 loss. We show that many algorithms are not (1/2 o(1), respect q, and already for g = 11, we get (0.45, 0.4, Note that (0.5, 0.5, n) the performance of random estimator that outputs random estimation uniformly at random from [0. 1].
eestimabae where o(1) is with
In the overparameterized setting, no algorithm can achieve low loss for all distributions D. this scenario, Theorem 3 shows that if learning algorithm has a bias towards some part of the hypothesis class, that is, learns the distributions in Do well (a bias towards Ho), then is necessarily not estimable, even when using complete knowledge of the algorithm being used. So the theorem shows a trade-off between learnability and estimabilty. To see more carefully why, consider the parameters a, 8, y. T, To, Ti to be fixed, as they not part of the algorithm A in question but parameters of the overparameterized setting at hand. Then, we observe an affine relation between the accuracy parameter and the accuracy parameter for estimating A. An affine relation also holds between the confidence parameter and the confidence parameter for estimating A. This is depicted in Figure 1. In conclusion, an algorithm cannot perform well and be certain of when it does.
In the following section, we illustrate Theorem 3 and show that it applies to a natural setting that includes neural networks.
6.1 QUANTITATIVE LIMITATIONS FOR ALGORITHM ALGORITHM-DEPENDENT BOUNDS
To illustrate our results, conclude our paper with case study of the hypothesis class of linear functionals Ling (d) over the vector space Fy where Fg is the finite field with q elements, with prime. For example, (in consists of all parity functions with input size d.
Lin, (d) (Fa)* {fa: Fg a Fd fa(x)
mod
important property of this class is presented in the following lemma: each two distinct functions in the class differ exactly on 8-1 fraction of elements in Fd.
Lemma 1. Each two distinct functions f.h h Ling (d) agree a fraction 1/q of the space and the
0 1 risk of the function h over samples from Dj o ((F))) is given by
0
h
(h)
1
h
For this class, consider the following set of algorithms:
Definition 5. Let Fd y E,, and H. Lin, (d). We say a learning algorithm A: (X' ))) H (possibly randomized) is an ERM algorithm with a linear bias if for every sample size n S d, associate (A, with linear subspace H., H of dimension such that if [S] and is consistent with some function in Hy, then A(S) Hn, We denote by Busin the set of all ERM algorithms with linear bias.
8

---

Published as a conference paper at ICLR 2024
Such choice of algorithms is natural with respect Theorem 3. They perform well on distributions that are associated with their linear bias. Such algorithms are not estimable, as the following theorem shows. For brevity, we let F(q. n) denote certain function computed from the rank distribution of a matrix composed of i...d. discrete random variables (see the appendix for precise statement).
Theorem 4. For every A & Astin and every d - 1, A is not (1/2 1/24, n) ( -e)-smmaael with respect to Ling (d) and the - loss where 1j = F(g,7) n). In particular, for q > 10, holds that 7 0.4, and generally, 17- 1/2 1/g o(1/g).
Theorem 4 shows that already for multiclass classification with g 11 labels (comparable the ten labels of MNIST and CIFAR datasets), with probability at most 0.6 we estimate the performance of an algorithm with an accuracy of 10/22 0.45. This is not much better than a random guess that estimates with an accuracy of 0.45 with probability 0.5. This holds since the loss of any algorithm in Atin either or 1/g = 0.9, as Lemma shows. So, we can always flip a coin, declare either O or 0.9, and be correct with probability 0.5. Finally, as q grows, our estimation can truly only be as good as a random guess.
When we consider the case of q 2 (parity functions) for Theorem 4, we get that the algorithms we consider are only (1/4, 0.025) -not estimable. To stengthen our results, the following theorem provides separate analysis that includes different technique from Theorem and that works specifically for q=
Theorem 5. For every A Atin (possibly randomized) and every n S d- A is not (0.23 0.14,)) estimable with respect to Ling (d) and the 0-1 loss. More so, for every deterministic A Aisn and every 6 S n s d, A is not (0.25, 0.32, n) estimable with respect to Ling (d) and the 0 1 loss.
It might appear that Theorems 4 and 5 unrelated practical overparameterized models because their setting is too artificial. However, as mentioned above, neural network can represent parities (e.g.. Lemma 2 in Nachum & Yehudayoff, 2020) and, in some specific cases, can learn parities using SGD (Abbe & Sandon, 2020). Hence, these theorems are relevant at least to some neural networks.
7 CONCLUSIONS
We have proved mathematically that specific types of generalization bounds are subject to specific limitation in precise formal sense. The interpretation of these formal results, and the extent to which they apply to existing generalization bounds in the literature on large neural networks, is matter of some debate. It is possible to argue that our results do not apply to various generalization bounds in the literature, e.g., because our definition of an overparameterized setting doesn't 't hold in or
cases of interest, because those bounds do not satisfy our definitions of iestrbuttioninnepeddeeen poorithm-iiddeeeddenne or for other reasons. Alternatively, one could argue that mniform-tightness is not an important property for a generalization bound, and that for specific practical cases of interest, it is easy to tell empirically whether a bound is tight or not when applying it to trained model. Below we outline our view, but we also acknowledge that a variety of scholarly positions exist. We encourage the reader to develop independent opinion this matter.
In our view, Theorems 2 and 3 point to two possibilities for obtaining uniformly tight generalization bounds in overparameterized settings. The first option is that when stating a generalization bound, the statement explicitly specifies a set of 'nice' or 'natural' population distributions for which the bound tight. Thus, the 'bad' population distributions on which the bound is not tight are clearly excluded from the set of distributions for which the bound is intended to work. The second op- tion for obtaining a tight generalization bound is to make explicit assumptions about the learning algorithm, which in particular imply that for any choice of classes H, Ho suitable for Theorem 3, the algorithm cannol learn Hy. We suggest that every proposal of generalization bound for the overparameterized setting explicitly include one of these two types of assumptions. Otherwise, if the setting is overparameterized, there provably exist pairs of learning algorithms and population distributions for which the bound applies and is valid, but is not tight. See Appendix C for further illustrations.
Explicitly stating the assumptions underlying generalization bounds is not only necessary for the bounds to be uniformly tight in the overparameterized setting, but can also promote more clarity within the scientific community, and guide future research.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
MG, IN and TW were supported in part by the Swiss National Science Foundations under Grant Nos. 200364 and 100020_185111 Part of this work was done while JS was at UC Berkeley, sup- ported by DARPA contract # HR001120C00P 120C0015 and the Simons Collaboration on The Theory of Algorithmic Fairness. Part of this work was done while JS was visiting the Technion Israel Insti- tute of Technology, hosted by Shay Moran. Views and opinions expressed are those of the authors only and do not necessarily reflect those of the Swiss National Science Foundations, DARPA, or the Simons Foundation.
REFERENCES
Emmanuel Abbe and Colin Sandon. On the universality of deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33, pp. 20061-20072. Curran Associates, Inc., 2020. URL https: htttps::/procceddngg.... neurips cc/ wttppppeee..eeeeeppppppeeeeeeeee (taps__ieee/pppp/2222000 pappreeeee11cccccpppeeeeeee
Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables, 2021.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer G. Dy and Andreas Krause (eds.), Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learming Research, pp. 263-263. PMLR, 2018. URL http: htttt::/pprcceeinngee mlr, wrwpsppsspeee..... / v800 aroral83. alb.. html.
Peter L Bartlett and Philip M Long. Failures of model-dependent generalization bounds for least- norm interpolation. The Journal of Machine Learning Research, 22(1)99977-911, 2021.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-493 2002.
Peter L. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear vc-dimension bounds for piecewise polynomial networks. Neural Comput., 1068))2159-2173, 1998. doi: 10.1 08997669830001701 http:::/ http://o.......11.......66666669
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normaliiie margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Peter L.
Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63): 2019. URL http: jmlr orgg pttppppappp/////pap 1 17-612 html.
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. Learners that use little information. In Algorithmic Learning Theory, pp. 25-55. PMLR, 2018.
Ian F Blake and Chris Studholme. Properties of random matrices and applications. Unpublished re- port available at https:/ /tt////www CS wtw.cc....too.... toronto. edw/ http://ccccccoigggg///////oc haaeiingggrrnommeeaeeeea report. pdf, 2006.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. CoRR, abs/1703. 2017. URL
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Ca- ballero, Linbo Wang. Ioannis Mitliagkas, and Daniel M Roy. In search of robust measures of generalization. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11723-11733. Curran Associates, Inc., 2020. URL https: htttpp:://proccedingg.ooo neurips http:/eewwr.isocceoppeeeeeeeeeee fflle// fi appp://00011//ddieeeeeaaaalllees
10

---

Published as a conference paper at ICLR 2024
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pp. 604-612 PMLR, 2021.
Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization enror bounds via Rényi-, f-divergences and maximal leakage. IEEE Transactions on Information Theory, 67(8):
4986-5004, 2021. doi: 2110099T.2202130555511
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neu- ral networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31 Conference Learning Theory, volume 75 of Proceedings of Machine Learning Re- seurch, pp. 297-299. PMLR, 06-09 Jul 2018. URL https: http:p:://ppoeeeeeee http///ooccciioeoooooooo ngs mlr .press/ 075/gollwiccoo iollooiwoooo ch 8a. html.
Mahdi Haghifam, Shay Moran, Daniel M. Roy, and Gintare Karolina Dziugiate. Understanding generalization via leave-one-out conditional mutual information. In 2022 IEEE International
Symposium on Information Theory (ISIT), pp. 2487-2492, 2022. doi: 10. 10991SIT55066.20222.... 9834400.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1225-1234. JMLR.org, 2016. URL http:
Wtt.tt::pprooceiiii... http://pooce....../e/ mlr. www.smrw......e.eeememm.mmm www.s/vvesvveee weress/v4B/aarat1...o hw../aaa......a.... html.
Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan, t generalization bounds for black-box learning algorithms. Advances in Neural Information Pro- cexsing Systems, 34:24670-24682, 2021.
Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evaluated cmi. Advances in Neural Information Processing Systems, 15:101 2022.
Ibrahim Issa, Amedeo Roberto Esposito, and Michael Gastpar. Strengthened cnormattion-theorede bounds on the generalization error. In 20/9 JEEE International Symposium on Information Theory doi: 10.1 10.11099/ST..221188889999 88499444
(ISIT), pp. 582-586, 2019.
Ibrahim Issa, Amedeo Roberto Esposito. and Michael Gastpar. Generalization error bounds for noisy, iterative algorithms via maximal leakage. In Gergely Neu and Lorenzo Rosasco (eds.). Pro- ceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 4952 4976. PMLR, 12-15 Jul 2023. URL https: / httpp:sss///rcpediiieepmm proceedings.
mlr. htl..prees/v1955. /0/////ss//aa html.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference Learning Representations, 2020. URL https:tp...... wwwp//wwwww..ww.eep/pppp net forum?id wtt.rruuwweeeee//ttttee/t B
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In Advances in Neural Information Processing Systems, pp. 4050-4060, 2017.
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geome- try, and complexity of neural networks. arXiv preprint 111.0507 2017.
Tengyuan uan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, ge- ometry, and complexity of neural networks. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 19, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pp. 888-896 PMLR, 2019. URL http:/ /ttpp/peeceeensseeeeeeeeeccss.ee mlr wwr.eppeeeeee..............e.... /v9 het//ianng1... html.
Wolfgang Maass. Neural nets with superlinear ve-dimension. Neural Comput., 6(5):877-8844 1994. doi: 10. 00.1122NEE00.199465577777 URL https:/ /tt:://ddoiii aloi.org//i. 1tt./....1111111111 neco. 1994. 6. 5.877.
11

---

Published as a conference paper at ICLR 2024
David A McAllester. Pac-bayesian model averaging. In COLT, volume 99, pp. 164-170. Citeseer, 1999.
Mehryar Mohri, Afshin Rostamizadch, and Ameet Talwalkar. Foundations of machine learning. adaptive computation and machine learning. MIT Press, 31:32, 2012.
Ido Nachum and Amir Ychudayoff. On symmetry and initialization for neural networks. In Yoshi- haru Kohayakawa and Flávio Keidi Miyazawa (eds.), LATIN 2020: Theoretical Informatics 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings, volume 12118 of Lecture Notes in Computer Science, pp- 401-412. Springer, 2020. doi: 10.1007/ 978 030 692 9
778-3-030--11792-99222 URL httts::/doi..rg/// 32.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalizzaionn bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv:1905. 13344, 2019a.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprini 1rXiv:1901.0100 2019b.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generaliza- tion in deep learning. Advances Neural Information Processing Systems, 32, 2019c.
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized opti- mization in deep neural networks. In Advances in Neural Information Processing Systems, pp. 2422-2430, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in ral networks. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.). Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pp. 1376-1401. JMLR.org, 2015b. URL http::/procceddigg. wwa.ggss......... mmlr.prees / v40 /et.saaassssasaeeeeaaaaaa html.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp- 1376-1401, Paris, France, 03-06 Jul 2015c. PMLR. URL htttppss//proceeddgg.. mmlr html.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. PAC-bayesian approach to normallze margin bounds for neural networks. In International Conference Learn- ing Representations, 2018 URL ht https: / wwwprevieeeeeeeeeee/eeeee n forum ? Sk2__WbC2
Behnam Neyshabur, Hanieh Sedghi, and Nathan Srebro. The role of over-parametrization in gener- alization of neural networks. In Advances in Neural Information Processing Systems, pp. 1119 1130, 2019.
Konstantinos Nikolakakis, Farzin Haddadpour, Amin Karbasi, and Dionysios Kalogerias. Beyond lipschitz: Sharp generalization and excess risk bounds for full-batch GD. In The Eleventh In- ternational Conference on Learning Representations, 2023. URL https: ptttpss:/openreviae oppnrevien.. net/forunts i d=poyi 9kg 6b.
Konstantinos Pitas, Mike Davies, and Piere Vandergheynst. Pac-bayesian margin bounds for volutional neural networks. arXiv preprint
2017.
Akito Sakurai. Tighter bounds of the ve-dimension three-layer networks. In Proceedings of the World Congress Neural Networks 1993, volume 3, pp. 540-543, 1993.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Theory of probability and its applications, pp. 1 1--30. Springer, 1971.
12

---

Published as a conference paper at ICLR 2024
Ziqiao Wang and Yongyi Mao. Tighter information-theone generalization bounds from supersam- ples. arXiv preprint arXiv:2302.02432, 2023.
Aolin Xu and Maxim Raginsky. Informition-theorriicc analysis of generalization capability of learn- ing algorithms. Advances in Neural Information Processing Systems, 30, 2017.
Peiyuan Zhang, Jiaye Teng, and Jingzhao Zhang. Lower generalization bounds for gd and sgd in smooth stochastic convex optimization. arXiv preprint arXiv:2303. 2023.
A NOTATION
Following is a summary of the standard learning theory notation used in this paper.
the set possible inputs (the domain)
y
the of possible labels distribution over X' x y
D
D x
the marginal distribution of D X
D
set of distributions over X y hypotheses class
H. = y
S ((11,)1) ..... (Fn, vn))
D
i.i.d. sample training set the set off all possible finite samples
(X' )/ 0 (X x))
A: (X x 3) y*
learning algorithm (possibly randomized)
A
set of learning algorithms loss function
x:Hx 2 x R
f0-1 (h, 2, 1x())=y
the 0-1 loss function
Ls (h) = Ei.1 (h,
the empirical loss of h on the sample S the population loss of with respect to distribution D the distribution the random variable (X, f(X)) where X ~ Dx
Lp (h) = E (a.))D (h,,
f Dx
U(?)
the uniform distribution over set ?
[m]]
the (1.
F
the finite field with & elements, where q is prime the set of all linear functionals over Fd
Ling (d)
(n n2,
the probability of nı times n2 random matrix with entries drawn i.i.d. uniformly at random from F to have rank r (see Lemma 2)
the Gaussian coefficient IT k-1
For simplicity, spaces we consider are finite.
Definition 6. distribution D realizable with respect to a hypothesis class H. if there exists e H such that LD (h) O.
Note: in the case of random algorithm A, define LD (A(S)) LD) (h) where Q(S)
the posterior distribution over y that A outputs. This fits the PAC-Bayes framework that upper bounds this quantity.
B FURTHER RELATED WORKS
B. EXAMPLES OF GENERALIZATION BOUNDS THAT ARE DISTRIUTION-NDEEENDDE AND L.GORITIM-INDEPENDORR
Our definition of estimator E captures the formalism of generalization bounds that distribution- iinputtiinn-neeeeddeettt and eegoritmm-indepedden Following are some bounds from the litera- ture that, in view, satisfy these independence requirements.
13

---

Published as a conference paper at ICLR 2024
1. VC bounds: Vapnik & Chervonenkis (1971); Bartlett et al. (1998; 2019). For class H of VC dimension d, the complexity measure
d+log(1/0) The complexity term depends solely on the hypothesis class (for fixed e, 6, and n).
2. Rademacher bounds: Mohri et al. (2012). (S) = - Susssppe Σi (I;) where
2ln(2/0) The com- a ~ [[=1)". This yields the complexity measure 2 Radæ 4v
plexity term measures how rich the hypothesis class H is with respect to S.
3. Norm-based and margin-based bounds: Liang et al. (2017); Neyshabur et al. (2015a); Nagarajan & Kolter (2019b); Pitas al. (2017); Bartlett & Mendelson (2002); Bartlett et al. (2017); Neyshabur et al. (2019); Golowich et al. (2018); Neyshabur et al. (2018; 2015c). Norm-based bounds typically consist of complexity term that depends the algorithm's 's output. For example, E/1 [Wife is the sum of the Frobenius norms of all the neural network layers. Margin- based bounds quantify measure of separation for the induced representation of the training set.
4. PAC-Bayes with a fixed prior: McAllester (1999). This yields the complexity measure D(QIP))+I((w/0) where P is fixed distribution (prior) over the hypothesis class and Q 2(n-1)
is the output distribution of randomized algorithm.
5. Sharpness-based measures: Nagarajan & Kolter (2019a); Neyshabur et al. (2017); Keskar et al. (2017). These measures (inspired by the PAC-Bayes framework) quantify how flat the solution generated by the algorithm is with respect to the empirical loss. For example, 1/0² where algorithm's 's output, W is random perturbation of w,, and fw is the hypothesis realized by the network's 's architecture with respect to W. C' depends both on A(S) and S. Such mea- sures received considerable attention as candidates to explain neural network generalization (see Dziugaite et al. 2020).
max (a Ew-NN(w.o Ls (fw (x)) 0.05). , w is a weight vector of the
In all these bounds, the explicit expression in the bound depends solely the hypothesis class, the selected hypothesis, and the training set. They do not explicitly depend on any property of the learning algorithm or the population distribution. Hence, in our view, they are subject Theorems and 2.
B.2 EXAMPLES OF GENERALIZATION BOUNDS THAT ARE DISTRIBUTION CONEBUUIIOO--NDEEEEENNN INDEPENDENT AND ALGORITHM -EEPENDENT
The following two works present -deeithm-deeendeett bounds.
Zhang et al. (2023): The paper studies convex optimization, so the results can hold only for a single neuron. Nevertheless, although it gives matching lower and upper bounds, the bounds match only asymptotically when n is very large so the scenario is far away from the overparameterized regime (which is the focus of interest for neural networks).
Nikolakakis et al. (2023): The paper suggests a new generalization bound that is an algorithm- dependent bound that does not include any distributional assumptions (it distribution- independent).
In our view, Theorem 3 implies that these bounds cannot be tight for all population distributions.
B.3 EXAMPLES OF GENERALIZATION BOUNDS THAT ARE DISTRIBUTIION-DEEENN AND AAGORITHM--EPENDDER
The following are information-theorrtie generalization bounds that are both algorithm and distribution-dependent (which we advocate for in this paper). However, bounds are sometimes hard to approximate numerically in tight manner (for example the bound in Theorem I in Xu & Ra- ginsky (2017)). On a high level, such bounds are part of the PAC Bayes framework; see proof for Theorem 8 in Bassily et al. (2018), which is equivalent to Theorem 1 in Xu & Raginsky (2017). Unfortunately, when the PAC- AUCCBayss/infommttonn -theorrtiitt eheeenrrfomaiion--coreeeeee bounds can be approximated in a tight manner such in Issa al. (2019); Esposito et al. (2021); Harutyunyan al. (2021); Hellström
14

---

Published as a conference paper at ICLR 2024
& Durisi (2022); Wang & Mao (2023); Dziugaite al. (2021); Haghifam et al. (2022); Issa et al. (2023), they do not reveal what properties the pair (distribution, algorithm) allowed for such success of learning and estimation (so the utility they offer is similar to that of validation set).
C EXAMPLE APPLICATIONS
Understanding how our formal results relate to generalization bounds in the literature on large neural networks, and their use in practical settings, a nontrivial question. In this appendix we illustrate our position via two examples, but we also recognize that other positions are possible.
C.I MARGIN BOUNDS
There are many margin- and norm-based bounds in the literature (see Appendix B.1). We start with toy example, illustrating why these bounds are not uniformly tight, and why we believe that Theorem applics to these types of bounds.
For simplicity, let the domain X' {x e g²; |0l|2 1) be the unit sphere in IRd, and consider half-space classifier with hypothesis class H = (h w E X²,, where hw =
For fixed sample size consider margin bound of the form f f()), where y is the minimum distance of a point in the training set from the learned decision boundary. f(y) is an upper bound on the difference between the population and empirical losses. f(>) is small only if y is large. We will show that f is not uniformly tight.
Indeed, consider population distribution D that has uniform marginal the domain X, with labels that are generated by a specific half-space ht E H. Consider an algorithm A that 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 D, with probability 1, A will output ht. 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 O, and therefore the empirical margin y will be close to 0 (even for sample size n that small compared the dimension d). Thus, f()) is large, but the generalization gap is O. Hence, the bound f(7) is not tight for the pair (D, A).
Note that f(7) is a quantity that depends only on the selected hypothesis and on the training set. Namely, this is a distribution- and gegorithm-indepenan stronger limitation, in the sense that it shows that there exist many (distribution, algorithm) pairs for which the bound is not tight, not just a single pair. The same holds for bounds of the form f([ [. where [W] is some norm-like function of the parameters of the learned classficr.
bound. Hence, Theorem 2 implies a
C.2 PAC-BAYES BOUNDS
The contributions of this paper can be illustrated by applying them, for example, to the landmark work of Dziugaite & Roy (2017). They presented PAC-Bayes bounds for neural networks that were the first generalization bounds to be non-vacuous in some real-world overparameterized settings. However, that paper did not state formal assumptions on the set of population distributions or the set of algorithms to which it intended apply. Therefore, our results imply the following for any fixed choice of a countable collection of priors as in the bound of Dziugaite & Roy (2017). First, by Theorem 2, the bounds is not tight for roughly half of all (distribution, algorithm) pairs. Second, by Theorem 3, for any specific learning algorithm, if the algorithm can learn a suitable set of functions Ho, then the bound is not tight on sizable collection of population distributions.
One way to understand the forgoing example is that the non vac-vuuuous numerical bound presented for the MNIST dataset by Dziugaite & Roy (2017) relies on implicit assumptions about the algorithm and the population distribution (for other tasks different priors would be required), such as: 'the population distribution satisfies that with high probability, SGD (on the specific network architecture of interest) finds flat global minimum point (with respect to the empirical loss) in the parameter space not too far away from the initialization point.' Or alternatively, 'SGD (on the specific network architecture of interest) cannot learn any collection of functions Ho that is suitable for Theorem 3.' Laid out explicitly in this manner, it becomes clear that these assumptions are not obviously true. This invites further research to understand for which population distributions and algorithms the
15

---

Published as a conference paper at ICLR 2024
assumptions hold, and whether there might exist more natural and compelling assumptions that suffice for obtaining bounds of comparable tightness.
D ON DEFINITIONS OF OVERPARAMETERIZATION
There are number of definitions of overparamettrrization that are common in the machine learn- ing literature, but there does not appear to be a single formal definition that is universally agreed upon. One contribution of this paper is that we offer an alternative formal definition of overparam- eterization that is close to well-known notions, and also enables proving meaningful mathematical theorems. In this appendix we discuss our definition and its connections to some common defini- tions.
Following are three common definitions. In these definitions, there is a learning task in which a machine learning system (e.g., a neural network) is trained using training set of labeled samples. The hypothesis class H is the collection of classification functions that the machine learning system can represent. We state these definition informally, in the sense some value is required to be large without specifying exact quantities.
Definition A. The number of independently-tunabll parameters in the machine learning system significantly larger than the number of samples in the training set. Namely, H {hr R$ and k >> n.
Definition B. The learning system can interpolate arbitrary data. Namely, H can realize any
labeling for any distinct 21....,Im. for some >>
Definition C. The size of the training set is smaller than the VC dimension, namely, VC(H) >> n.
For convenience, our definition of overparameterization is restated here. As before, one should think of H as the collection of classification functions that are realizable by learning system of interest.
Definition 2 (Restated). Let H be hypothesis class, let n,T E N, let a, B 2 O, and let D (D:Yen be finite collection of H-realizable distributions. We say that (H, D) is an 3,,3,m)- overparameterized setting if (H, TD) is not (ax, 3, (ox.3.n))learaaaale -learnable (as in Definition l).
Our definition is more general than Definitions A. B and C in that our definition is (typically) im- plied by the other definitions. This means that when we prove that a bound cannot be tight in the overparameterized setting according our definition, that in particular implies that it cannot be tight in any setting that is overparameterized according to the other definitions. This makes our impossibility results stronger.
The implications hold as follows:
Definition A = Definition C. This implication holds for many neural networks. It is well-known that large neural networks have large VC dimension. For instance, Theorem in Maass (1994) states that under mild assumptions, any neural network with at least 3 layers has VC dimension linear in the number of edges in the network. Maass (1994) showed this for networks with threshold activation functions and binary inputs, and Bartlett et al. (1998) note that "It is easy show that these results imply similar lower bounds" for networks with ReLU activation. A similar result holds also for networks with layers (Sakurai, 1993).
Definition B then the VC of H least m.
Definition C. If a class H can realize any labeling for some 3i,..., Zm
Definition C Definition 2. This implication is Item in the proof of Theorem on page 21.
Our definition does not merely generalize the common definitions listed above it generalizes them in desirable way. Definitions B and C pertains to case where the hypothesis class can express every possible labeling of the training set or of a shattered set. However, this seems a bit rigid. What if the network or hypothesis class can express every labeling except one? Or can express most but not all labelings? Intuitively, the network is still very much overparameterized, even if there some specific choices of labelings that it cannot express. The essence of overparameterization
exprr
16

---

Published as a conference paper at ICLR 2024
is that the network can express too many of the possible labelings not necessarily every single one of them. What is 'too many"? Our answer, as captured in Definition 2, is that a network is overparameterized (can express 'too many' labelings) if it can typically express many different labelings that are consistent with the training set but disagree on the test set, leading to poor expected performance on the test set.
In conclusion, Definition is natural, impossibility results for Definition 2 imply impossibility re- sults for the other definitions, and Definition 2 generalizes the other definitions in desirable way.
We end with two additional remarks concerning definitions of overparmettriation.
1. Note that Definition A also has the weakness that it is sometimes possible parameterize the same hypothesis class with varying numbers of parameters. For instance, a 1-layer fully-connected network with linear activations and a multi-layer fully-connected network with linear activations represent the same hypothesis class (both networks simply multiply the input vector by a matrix), but the number of parameters can be very different between these two networks.
2. A curious reader might wonder why do not use the definition of PAC learning in Defi- nition 2. That is, why not say that H. is an (a, B. n) -overaaaaeeterizze setting if H is not (,,8, n. --C--A--llee Working with such definition will yield quantitatively weaker results. For example, an analogue of Theorem I (that uses the aforementioned definition) will still prove that VC classes are not estimable, so any estimator fails for least one combination of an algorithm and a distribution; our definition yields the stronger result of Theorem 1, that the failure of each estimator is across many combinations of algorithms and distributions.
E EQUIVALENCE BETWEEN ESTIMABILITY AND EXISTENCE OF TIGHT GENERALIZATION BOUNDS
Definition 7 (Uniformly tight generalization bound). Let X and y be sets, let H. yd, let c, > and let n E N. Let C: H. x (X x y)" R. be a measure of complexity as in Eq. (1). We say that C yields an 6,,6,n))-uifon -unifformly tight generalization bound for H if for every algorithm A that always outputs hypothesis from H. and for every H-realizable distribution D.
PP PS (is(A(S) C(A())) - ( & Ls(A(S)) ((((8)))C(((SS))))) CC(A(S),)) (4)
Definition 7 captures generalization bounds that are tight in the realizable setting. More generally, we are interested in generalization bounds that are tight in the more realistic agnostic setting. How- ever, because we are interested in showing that certain types of generalization bounds cannot be tight, it suffices to show that they cannot be tight in the realizable case, in Definition 7.
We now show an equivalence (up to a factor of 2) between estimability (Definition 3) and the exis- tence of uniformly tight generalization bounds (Definition 7). From this equivalence, to show that certain generalization bounds cannot be tight, it suffices to show that a class is not estimable.
Claim 1. Let X and y be sets, let H E Y let c, 6, O and let n e N.
1. If there exists C: Hx (X x y) ~ R that yields an 8, (,,,,n))unifonn -n-uifoorlly tight generalization bound for H then H is (e, 8, 8,n))--stiimabll
2. I is (c,8,n) n) eestimable then there exists C: H x (X y)" + R. that yields a (2c, 5, n)- uniformly tight generalization bound for H.
Proof. For Item let C: H xX'))"" IR be a measure complexity that yields an (c, 6, n)- uniformly tight generalization bound for H. Let A be an algorithm that always outputs a hypothesis in H and let D be an H-realizable distribution. Then Eq. (4) holds. Define H x (X )) R
by
E(h [.s C(h,S).
17

---

Published as a conference paper at ICLR 2024
Plugging the definition of E into Eq. (4) yields
PS-D" [ (D((S))
- EE(A(S), 21
(5)
This shows that H. is (c, 6, n) esstmmale.
For Item assume that H. is (e, 6, restimaaaee and let E an estimator that witnesses this. Let A be an algorithm that always outputs hypothesis in H. and let D be an H-realizable distribution. By choice of E, Eq. (5) holds. Define C: H (X 3) R by
C(h,S) -Ls())))L +
Plugging C' into Eq. (5) yields that with probability at leat 1 over the sample S ~ D
(
C(h.
and also
(D((A(S) 2 ((A(S),)) -
- Ls(h) + C(h, S) 2c.
Hence, yields (2e, 6, unnuforfryy tight generalization bound for H.
F PROOFS OF THEOREM AND THEOREM 2
Theorem is a corollary of the more general Theorem I which shows that in the overparameterized setting, any estimator of the true loss will fail over many combinations of ERM algorithms and distributions.
Before the proof we present the type of distributions over ERM algorithms Theorem I applies for.
We remind the reader that an ERM algorithm is a function A (X x y)" y whose output is any consistent function with the sample S that belongs to H.
Definition 8 (Bayes-like Random ERM). H be a hypothesis class and (Di) a set of distributions. We say that the distribution DERM over ERM algorithms is Bayes-like if for any fixed it holds that
Σe hysh (D)
PDenM (AERM(
Σラ- PD, (S)
where h; is the labeling function associated with the distribution Dí. If AERMS DERM. we say AERM is Bayes-like Random ERM.
Reminder: All spaces we consider in the paper are finite so the definition of Bayes-like Random ERM a well-defined random variable over a finite sample space.
Clearly, any algorithm A chosen with non-zero probability over DERM is an ERM algorithm.
Theorem 1.
Let be a hypothesis class, be the 0- loss, {D,) T be a finite collection of H-rralizable distributions each associated with hypothesis h, and (H, (a, 3, n) over- parameterized setting. For any e Hx, let An. an ERM algorithm that outputs for any input sample S consistent with h. Then, for any Bayes-like distribution DERM over ERM algorithms and any estimator E of H at least one of the following conditions does not hold:
1. With probability at least 1 1- over 1~ (((() and DT.
| (An, (ol
LD, (S)) <
over u((T)) S Dj, and AgRM ~ DERM. 2. With probability at least 3-3 3- +
(AERM(S),S) LD, (AERM (A, <a-e,
In parficular, H. is not (a/2,8/22 estimable.
18

---

Published as a conference paper at ICLR 2024
Proof. To see why H. is not 8/2, essttmbbee if item 1 or item 2 do not hold, choose 3/2 and = a/2.
If item does not hold, it means there cxists algorithm An, and distribution D; such that
E (..
with probability greater than 8/2 over D; so H. is not (02,,8/2,n) -esttmmbble item 2 does hold, means there exists ERM algorithm AERAS and distribution D; such that
E (S), (Ar(( 20-6 a
with probability greater than 3/2 over D; so H. is not (a/2,, 3/2,, -esttmablle
Let AERM- DERM be Bayes-like Random F.R.M The key ingredient in our proof is show that the following two probability measures P, and Pg over (A x ))" x H are equal so Pi (S, h) (2(S, f)) for every pair (S,h) (Xx x x)) H.
Pi: the pair (S1, hr) is generated by choosing an index [-T[T], then S DD, and hy the labeling function associated with D,,
2. P2: the pair (ERM)))(())) is generated by choosing index 7 U[T], then S D and AERM D ERM independently.
Equalities (4) (8) and equalities (9) (14) show that Pi and Pg are indeed equal.
Pi Σ P(1=i)- P(I=i)- P(h h/ i, S)
(6)
P(T= =) ((())) =) P(h, M i)
T
T Σ
P(S 1) P(h, h|1 i)
1
Σ
P(S i)
(9)
T
hi=h
Σ
Po. (S)
(10)
$ huhh
The first equality holds by law of total probability, the second equality holds since hy is independent of given S. the third equality holds since is uniformly distributed, the fourth equality holds since P(hr h = i) is either 1 or 0, and the fifth equality holds by the definition of D,.
19

---

Published as a conference paper at ICLR 2024
P2(S, Σ P(S))) =) P(1-))-PSSS-)))))PAAaa(((( h/l j.
(11)
)=1
=
Σ ([]=j)- -)()) P(ARRM))) M|S)
(12)
111
T
= T j-1
Σ
P(S P(AERM (S)
(13)
1 T
Eah,N Pb, (s)
Σ
P(S]T= =j)
(14)
T j=1
Σ PD, (S)
1 Ei h,-h (5)
T
Σ j-1
Pp. (S)
(15)
T Σ/= PD. (8)
Σ (5)
(16)
T v: h/zh
The first equality holds by law of total probability, the second equality holds since Agnas (S) is independent / given S, the third equality holds since I uniformly distributed, the fourth equality holds by the definition of the distribution D PERM, and the fifth and sixth equalities are trivial.
Assume item in the theorem holds: I (An,(S), over / U[T] and S Dj. Since LD, (Ang (S)) O. have that E (An, (S) < with probability I- over I ~ [[[]] and S Dj.
LD, (An, (S)) e with probability 1-7
So, on the one hand, we have
(h, <E
with probability 1 - 7 over the probability measure P1.
Since we are in (a,3,n) (),,))-oo overrparameeterizze setting, then for any algorithm A have that LD, (A(S)) > a with probability at least /3 over / ~~ [T] and S ~~ D,.
So, on the other hand, have
LD, (AERM(()) a
with probability of at least 3 over I ~ u[T], S ~ D,, and AFRM ~ DERM-
Since P1- P2 we can combine the two statements above about P1 and P2 and have by the union bound that
[ (AERM (A)r)))))))
holds with probability of at least 3 7 over ~ [[][] S D1, and AERM DERM- So item 2 in the theorem cannot hold which concludes the proof.
We now use Theorem 1 and the definition of a Bayes-like random ERM to prove Theorem 2.
Theorem 2. Let H. be hypothesis class of VC dimension d >> 1, and be the 0 loss. Let X c X be a set of size d shattered by Hx = {hh]]²" 7L and let {Da) distributions that correspond
2n be the set of realizable Hx. where for all the marginal of on X is uniform over X. Let ERMH, be the set of all deterministic ERM algorithms for Hx. For any E Hx, let Ay be an ERM algorithm that outputs h for any imput sample S consistent with h. Then, for any estimator of H. at least one of the following conditions does not hold:
1. With probability at least 1/2 over I I=((((2)) and 5 D7.
E (An, (S), LD, (A,,) (An d-n n
4d
20

---

Published as a conference paper at ICLR 2024
2. With probability at least 1/2- over - S Dj, and AERM (E(MM)))))
E (AERM (AERM ($)) d o(1),
4d
where U(RMHHx denotes the uniform distribution over ERMxx
In particular, H. is not ( - 1/1)-(11111111. -estimabbl for any d/2. The notation o(1) denotes quantities that vanish as d goes to infinity.
Proof. The proof is an application of Theorem with the following two items:
1. D DERM = x[EMM is Bayes-like distribution over ERM algorithms for (D) (Di)
2. For any algorithm A, with probability 1 o1) over (=((())) and S DD, it holds that
LD, (A())) d- o(1).
2d
To apply Theorem we have from Item 2 that d-n o(1) and B 1- o(1) for any s d/2.
Proof for Item 1:
On the hand, PDEMS (AERMI(S) h) [[ consistent with S] for h that is consistent with S and PD (AERM(()= = h) = otherwise. This follows from the definition of (f
Σn h. (S) Σ/- (s) The summands in the
the other hand, for any fixed we have the quantity denominator are non-zero only for indices that correspond to functions h that are consistent with S. All such summands are equal since we have the same underlying distribution over the space X. Since all the functions (h₂ g are different, the sum the numerator contains one summand which equals any other summand in the denominator if is consistent with S and equals otherwise.
Combining the two statements above completes the proof:
PD (AERM(()) h)) -h)= Es hi-h (5)
Σ/ PD, (S)
Proof for Item 2:
Let be an ERM algorithm. We note that for every realizable over Hx that consists m distinct data points we have
E, (A(s)
m
(17)
2d
where I U[2"].
More so, for a fixed S that consist of m distinct data points, LDD, (A(S)) is random variable which sum of - i.i.d. Bernoulli random variables with parameter 1/2 that is divided by d. By Hoeffding's inequality,
P LDD (A(S)) < d-m d0.6
2d d exxp(-2d
<
exp
2d
which implies that for any S with |S| it holds that
d-n
P LD,
o(1) <o(1)
2d
21

---

Published as a conference paper at ICLR 2024
Then, with probability 1 o() over I I=((() and S~ Dj, it holds that
(A(())) d-
o (1).
2d
G PROOF OF THEOREM 3
We start with a remark.
Remark. The converse of Theorem is false. Over the same overparameterized setting as in The- orem 3, algorithm simalianeously not learn Hg well and be estimable. To see why, consider binary classification with the 0 - loss and take any algorithm A that (c, (l.aars Ho and define Aneg(S) *A(S) where is the hypothesis with opposite labels to h. Aneg does not (1 c, -lea- Ho and by the same arguments as in Theorem we get that it is also not a-c 12
1-8 f + Zn
n esttmabbe..
2
Proof of Theorem 3. If (H, D) (a, n,)ovr) parametrized setting and A (e, n)leeams (H, Do), then A does not a 1 -
8T
5Ta m learm D1). This stems from the following steps.
Ti
B s Es, LD, (A(8))20
To
T1
1s.1o Es (A(S))2o +
Es... 1 ro, (A(S))20
T
T
To
T
$
Es.Io
L (A(S))2c
Es. 1 Lon (A(9))2a
T
T
To
Ti
$
8
Es,1, LD,, (A(S))2a
T
T
To 8
Ti p (LDi, (A(S)) 2 a)
_ T T
The first inequality holds by the definition of the overparameterized setting. The first equality from the law of total expectation. The second inequality holds because decreasing a to only increase the probability that the indicator function outputs 1. The third inequality holds since A (c, 6, n)- learns (H, Do). The second cquality holds since the expectation of the indicator function equals the probability for the event the indicator function underscores to happen.
This yields that with probability least
5Th over In T1
To + U[Ti] and S DT,
Ti
LD, (A(S)) a.
Now we show that A is not ( n, lsstimable with respect to H and loss f. For that end, we use Theorem Angel & Spinka (2021). We denote as the coupling between So DD, and S ~ D", We have that with probability 7 over w, So S,. Now, for any estimator E, we get our claim through the following steps where B (So S1, I.D,, (A(So)) <,, LD,, (A(Si)) > a).
22

---

Published as a conference paper at ICLR 2024
E
LCCA (A(S6)))2 L (A(s)))
P(B)
E
1OCA..O-LDD (1(5))) ((AAS))-LO, (A(S.))
P(B")
E
(E (1(36)))23 ( (A(S:)))2241
w|
P(B) E. w|B ( LD,, (10 + ( (A(S1))
P(S. S1, Lio (A(S))) < <E, 2a))
3T
STo
7-
T
Ti
2m
The first equality holds by the law of total expectation for any event B. The first inequality holds since the expectations are over non-negative random variables. The second incquality holds since assigned B (Su S1, LD., (A(So)) LD,, (A(S))) > a} and when B occurs for have 5o) S1) and any such assignment of (AA, forces at least of the indicator functions to take value 1. The third inequality holds by the union bound.
The proof now concludes since
Ero (1,88~(((A.ssu) L(A.So)- (A(Sa)))2 E BB (o
and
Es, (I(A.S))-D,, (4(5 E. (o(AA (A(S1))/2
so at least one of the following items holds:
With probability at least over Io and So it holds that
(oA, LDt, (A(S)))) a-c
With probability at least y over In and S it holds that
(E)..))) LD., (A(S:)))
H FINITE FIELDS AND LIMITATIONS ON ESTIMABILITY IN MULTICLASS CLASSIFICATION
Let us first revise Def. from the main text, since it is preliminary for the proofs to follow:
Definition S. Let X = Fd. y F., and H. Lin, (d). We say a learning algorithm A: (X x x))) H (possibly randomized) is an ERM algorithm with a linear bias if for every sample size S d, we can associate (),)) with a linear subspace H. H. of dimension n such that if [S] and S is consistent with some function in Hr, then A(S) Hn- We denote by bain the set of all ERM algorithms with a linear bias.
g'
We restate the definition of linear functions and add further definitions:
Definition 9.
23

---

Published as a conference paper at ICLR 2024
Let q be prime and denote by Fg the finite field with elements. The hypothesis class of linear functionals Ling (d) over the vector space Fç is defined as
Fdd q fa(x) Ling (d) (F2)*= = [a: F =
aa.zn IG mod o)- E i-1
d
We partition Ling(d (d) into the linear subspaces Lin (d) {fa Ling(d) i) with (d)) gd and L (d, n) (Sa E Ling(d) (d) (01 = (Vjj [n 2....,
. d) :0;
0)}, where ( and ( q"
We denote by X Band the matrix obtained by stacking the inputs {a:]i-1 as rows.
We denote by ei the canonical basis vector with entry in position i and everywhere else.
Further, we denote by A c. Alin the class of ERMs that are biased towards Ling, (d, n.). In more detail: whenever A é B. receives sample S of size n and there exist hypotheses in Ling, n) consistent with the labels of S, A oulputs one of them. Otherwise A outputs an arbitrary hypothesis from Ling (d.
H.1 PROOF OF LEMMA 1
Lemma 1. Each two distinct functions J. Ling agree on a fraction 1/9 of the space and the
1 risk of the function over from y o (FF) is given by
0 h=
LD, (h) = 1 1/9
h
Proof. Denote the coefficient vectors of f. by af, as, respectively. Moreover, denote by X, _ X the subset of the domain on which f and h agree, i.e., the fraction over which they agree is (/ Then, for any given input & Fd. f(x) h(x) if and only if c.rr- === mod q where c: a mod q.
Now assume w.l.o.g. that the respective last entries of as and a are distinet (if not, perform an appropriate permutation). Then, the first entries of can be chosen arbitrarily and there are o d-1 distinct such choices. Thereafter, the last entry Ha is fixed to be Ga Za = q Σd1 & a, mod g. Note that for q prime such za IF always exists and is unique. In summary, we have that [Ka|= = x which together with |X| dd gives the first desired claim.
The second claim then simply follows from observing that UX( together with the fact that we using the 0 loss.
H.2
LEMMA
Lemma 2. The probability that an n4 ny matrix with coefficients drawn i.i.d. from 1}) has rank is given by
(1),
((11) (l(mn)))
(18)
1-0
where [K], :1
denote the so-called Gaussian coefficients.
In particular, the probability that an n, x matrix with coefficients drawn i...d. from (((0....... ........
1}) has full rank is given by
c1-1 [I bc2))
(21, (1, R2(ni n2,
(19)
1=0
where C1 (mi,n))))))))) and c2 max(mn
24

---

Published as a conference paper at ICLR 2024
Proof. The first statement is Corollary of (Blake & Studholme, 2006, Corollary 2.2).
The second statement can be inferred from the first, but also follows directly from the following simple iterative construction; assume w.l.og. that nι R2. Then, at each time t 0, ... 71 1 add one row to the matrix. Assuming that each entry of the matrix is sampled i.i.d. uniformly at random, the probability that time t the new is linearly independent of all previous rows is then given by 1 - g since there are q' possible linear combinations of t rows, and there are q" vectors of length 722 in total.
H.3 LEMMA
Lemma 3. Denote by X E EFuxutl the matrix obtained from X Fund by dropping all but the first + columns. Denote k == (aan(X") and assume that the labels of the samples S (X,y) v) are generated by some f (in i.e., f(X) where f gaadd F7 is understood to be applied row-wise. Then,
If the vector e1 is spanned by the rows of X there exist q g=+l-k functions in a n) consistent with S and no consistent function in all other classes Lin (d. n),
the vector is not spanned by the rows of X-, there exist q=-* functions consistent with S in each Li (d, (d,n). {O.....q 1-.. 13.
Proof. Let fa be linear functions parametrized by coefficient vectors [a] (......, az). Further, let a' F denote the truncated coefficient vectors of a over the first n coordinates. Assume first that e1 is spanned by the rows of X Then, only functions in (d, n2) can be consistent with S. This is because of c - aa' c y is uniquely determined for e [P if cs chosen such that encodes the linear combination of rows of X that yields e1. The preceding equation hence holds iff a1 i due to the assumption that f f (in Since the rank of X is k. its null space has dimension + 1 & and there exist q=*+1=k consistent functions in total because X (a+ b) = is also consistent for all null(X") assuming that the data was generated by fa-
Assume now that the rows of X do not span Xred Fy (xx((++1) and vector Wred E F& by retaining only k rank(X") linearly independent rows of X and the corresponding entries of y. Note that since the sample S is generated by some f (d, we have that X- if and only a' with the reduced system of equations in order to check for the consistency of a function fa-
Then, we can construct the reduced matrix
a' Dred- Hence is sufficient to work
Next, we append above the top of the matrix Xred the row and n k further canonical basis vectors cir....y fi... in order to obtain full rank matrix Xext. This is always possible because e1 is not spanned by assumption and furthermore there always exist at least vectors which are not spanned by the rows of X,ed-
k canonical basis
With this setup, one can then obtain for given X and function fr. Ling.m n) with m e (O...., . }} arbitrary and reduced coefficient vector h' [m hT Fa+1 by computing the unique solution of the fully determined system of equations
E1
Cis
m
m
(20)
h
Cip-x
Ured
X
red
for é Ey-* arbitrarily chosen. By construction, the function fr. with h [h', 1h',0,, ........0 00T will then be in Ling.m (d, n) and be consistent with the sample (X, y). Moreover, since 2 e F can be chosen freely, there g--h such functions in each class
j (O.....g
H.4 PROOF OF THEOREM 4
We consider the learning settings with realizable distributions over H' = Ho U H, where Ho := Lingo n) and Hi Lin, (d, The algorithms we consider come from Ag, the class of
25

---

Published as a conference paper at ICLR 2024
ERMs that are biased to Hu = Ling,o(d,n), that is, if there exists consistent hypothesis in Ho, the algorithm must choose one such hypothesis. As mentioned previously, it is sufficient to consider such ERMs in order show learnability and estimability results over the larger class of linearly constrained ERMS Alin due to a symmetry argument.
We first show in Lemma 4 that the learnability condition (condition 1 in Theorem 3) holds for Ho- In Lemma 5 we show that attempting to learn above Ht' corresponds to an overparameterized setting. then follows Theorem 4 then follows from an upper bound on the TV-distance which implies that condition 2 in Theorem 3 cannot hold, i.e., H' is not estimable. Since (in,(d) 2 H', this directly implies that Ling d) is also not estimable with the same parameters.
Lemma 4. Lin Lid,,o(d,n) n) is (0, 6, -lernable over Do (ffu(()) Ling,o(d, d, n)} with any Ae Ao for n [d and 5 Ek=o (1 (1-a"=n q²-"). (n, where Rg is defined as in Lemma 2.
Proof. For the analysis one can drop the columns 1, 2,n 3....d of X hypotheses in Ling,o(d, n) are invariant w.r.t. to these coordinates and it is sufficient for A to only check for consistency, Thereby obtain the reduced input matrix X' of dimensions n n.
Clearly, any A E An outputs the ground truth hypothesis w.p. 1 as soon as X' has full rank. On the other hand, once X' does not have full rank, A might output the wrong hypothesis depending on its preference, i.e., depending on which of the multiple consistent functions it outputs. It can be easily verified that any preference (be it deterministic or random) of amongst consistent hypotheses leads to the same error probability since the random variable that selects the labeling function is uniformly distributed.
Setting 0, we get by the law of total probability that Ling,o(d,n) is (0, 8, learnabbe by any Ao if
P((AERM(S) + f})
(21)
Σ (((AERM(S) SNX has rank 1:)) P(XX' has rank k))
(22)
Σ -
(23)
where for the last equality we used the following two facts:
Conditioned the event that rank( (X') k, A returns the ground truth with probability g²- This because P ((A(S) = S)] is uniform over all f Lin (d, n) consistent with and since there are -=* functions consistent with & linearly independent samples (see the argument in Lemma 3).
For controlling the probability of rank deficiency we used the result stated in Lemma 2.
(d, Lin (d. not (a.,3,n) lleaaaaleee with any A E Ag over DD { U(x) e o(d,,o(,,)) U (d, n)} for [d - 1] and any (a, 3) such that simultaneously (9-1 and < Ekso ((g n--1) -=11 1 + 2 gmn)) x Rg Rn, 1,
Lemma 5. Ling,o(d,0)
Proof. Note that learnability trivial for a 2 (1 1/4) --1 since this an upper bound for the risk of linear hypotheses according to Lemma 1. Hence we consider the case a < (q 1)/4. Then, by definition, (a, -ea.eaabbb is precluded for any algorithm that outputs linear hypothesis once < P((A(S) f)) since (A(S) f} implies LD, (A(S)) I-1 In the sequel we aim to derive P((A(S) # f}) for the case where A Ap-
Denote by X F F= the matrix obtained by dropping all but the first n columns of X. Denoting the events E, == (A(S) * f). Eg := {f e Lin,, n)) n) Eg t= (er spanned by the rows of X-) and FA, (X- has rank k), we have by the law of total prob-
26

---

Published as a conference paper at ICLR 2024
ability that for e {0.1},
P(Ei|E2, n Ea,x) = IP( F1 1 E2, n Es Pa,)) F2, n Fa,k)
(24)
P.E n Egn FA, ( E2, Fa,e))
(25)
= -PEE 2 n Eg n E. ) P(Ei ES PPE)) Ea,k)
(26)
We can quantify the terms appearing above as follows:
[[E]E2, Es n Es,A) = =1 111--=1-- - for i É {0, since we know from Lemma 3 that Eg n Ea,k implies that there are q=+1-k consistent functions in (d,,,(d,n)) n). As f is selected uniformly at random from Lin,, (d, the statement follows.
|(E n Eg n E 1 1- -mm because we know from Lemma 3 that Ej Ea,t implies that there are = consistent functions in each Lin,,((d,n) n)).
P(E F2,1 n F3 n EA,k) = since A will almost surely select a hypothesis from Lin,,o(d,)) n) even though f Lin (d, n) if e, is not spanned.
داب follows from the fact that X spans some k-dimensional row space uniformly at random and there are ge possible non-zero linear combinations of k linearly independent rows and g*+1 non-zero vectors length n + 1.
P(Eg|E4,)) = 1- P
Combining above facts we have that Lin,,o n) Ling, (d, is not (a, (.,,3, by A for g-1 and
B<)(E))=
EA,k)
(27)
2 Σ P(E2))
Σ
|(EElE22 Es Ea,1) P B(,.)
(28)
0
k=0
+P(Ej Eg, Eg Ea,k) P(E)(E .((s,)))
(29)
n
-1
Σ
(1 - (1---t--)
gr+t1 - + (1 - x²-)) (1
(30)
2 0=
gntl1
+ (1 g² $
(1 -
n-1
nn
(31)
g -
gu+11
1
Σ
(1 A-
2 1
g² -1
+ 2 g
Ry (n, n+ 1,k).
(32)
2
gn+l 11
k=0
Using Lemmas and 5, we are now ready prove Theorem 4:
Theorem 4. For every A E Alin and every d - 1, A is not ((g 1)/2q, 17. -estimabbe with respect to Ling (d) and the 0 - 1 loss where n= ER= -qa=-_ 2g n-1 - 1) qu+i_T + 2 g -==n] R2 n 1, k) - Σx-1 (1 "-))
k.). In particular, for q 10, it holds that > 0.4, and
generally, n = 2 (1/9))
Proof. For all product distributions appearing in this section assume that Dx = U(F)). Let D = (D.) be the set of Lin,dd,n) realizable distributions such that Bo (D.) is realiz- able over Lin,,odd, n),, and 11 (D, p is realizable over Lin (d, n)). As we are working with countable measures.
reealizale
1 , p P- [
(rv
(33)
2 2
27

---

Published as a conference paper at ICLR 2024
where P and Q denote the probability measures associated with the distributions Di, and D respectively, where In [[(") and 11 q" +[([q]]). First, we note that need only sum over samples S such that their corresponding input matrices span ej since Lemma 3 asserts that once e1 is not spanned, the number of consistent functions in both classes is the same. Since the measures P and Q are uniform both w.r.t to the inputs and the labeling functions, they both are proportional to the numbers of consistent functions (each multiplied by the same constant factor). Further, know from Lemma 3, that once é is spanned, the number of consistent functions in Lin (d, n) is non-zero iff S ~ f Dx with f Lin,,(d, n). Hence only one of P(S) and Q(S) can be non-zero at time. Therefore,
drv (Sv
Σ
(P(S) Q(S)
(34)
5:fe1 spanned]
Σ
P(S) +
Σ
Q(S)
(35)
(:(e1 spanned]
8:(e1 spanned)
(ffe spanned)).
(36)
According to the definitions in Theorem 3 we can hence pick
? = 1 - PP(( spanned))
(37)
n
-1
= 1 - Σ
gm -1 Rn 1,
(38)
k=
where we used of the fact that (P( (ranned)[(ran(( (rrnkknnnn = k))
Plugging in above y and values of ax 3, accordance to Lemmas 4 and into Theorem 3, we finally obtain that Lin,, n) u Li (d, n) is not (v, -estimabble if simultancously (a- c)/2 (q - 2) and
1+8
B
<
7
Ti
(39)
2
2
+
3
(40)
2
1
1-
Σ
x Rg 1,n,k)
(41)
2
qu+1 -1
k=U
1
[(g bmnn 29 km--)) g -1
+
Σl
gm-l -1 +2 --2-ttm p- x (n n 1,1)
(42)
2
k=0
n-1
Σ
(1 9 )) R.g (2, k,)
(43)
2
k-0
Σ
[( k-n 24 k-n- 1) g=-
+ 2 -0-----11 x01 x (n
(44)
k=0
(1-9tt1) R1 (n,
(45)
where we used the fact that To Ti = T/2.
To get the asymptotic result, we make use of the following two bounds:
9" 11
V/g-o(1/g) S gm0l -1 $ 1/9
(46)
Rg + 1,m) 2 1- 1(((/))
(47)
To see that equation 47 holds, recall from Lemma that R,, n n) (1 (1-9 --1 (1- 2)
Now assume towards induction that the partial product _., 11 - ) m 2 is in o(19))
1) is also in 1- - o(19)) since q m-1 E o(1/g). We have for the base case that π2 1-g q is in 1 o11/)), hence the claim follows.
Then, 1 (1 - o(1/)) (11 q m=1)
28

---

Published as a conference paper at ICLR 2024
Using above facts then lower bound equation 44 equation 45 by lower bounding the first sum by only considering the term for which = n. and upper bounding the sum in equation 45 by 1- (n, n, n) where (n, n, n) 2 1--1/1 1-1//-1---0 1tll/////////// o(1/q) due an induction argument similar as above.
Thereby we obtain that equation 44 equation 45 lower bounded by
1
(1 2/9 2/4-
1 (1-0(110)) -
-
[1
1 (1-111-
1/9 111111-0011) o(10))
(48)
2
1 -
(49)
We thereby proved non-estimability of algorithms A Aug with respect H. Lin (d) and distribu- tions families Do, DD, (defined at the beginning of the proof).
Finally, we extend this result to the class of all linearly biased ERMs in Agi via the following reduction:
Remark (Reduction). Without loss of generality, one can focus on the class As whenever proving learnability and estimability results about Aaii (see Definition 5). This follows from a reduction of non-estimabillty with algorithms A' e Aaiin to non-estimability with algorithms A Bu as informally discussed below.
First note that any linearly constrained ERM A E Aain is implicitly parametrized by some e Rdly q (0) and k. Fg such that is biased towards selecting hypotheses Jb (in,(d) such that Ee oz. bi= K. For example, in the case of A E As, we have a and 0.
Let us briefly recap the setup Theorem 4.
First, introduced the d dimensional function space Ling(d).
Based on n, we linearly mapped the space onto the n dimensional subspace Lin, n).
We assumed that A is biased to the n dimensional subspace of functions fo with O.
Finally, we showed learnability (with A) over the subspace Ho Lin,, n) and non- learnability over the subspace Ho U Hi, where Hi = Lin nd.
now sketch how for arbitrary A' a Auin with bias coefficients (α, one can find appropriate subspaces of Lin,(d) that admit essentially the same properties the ones studied in the proof of Theorem for A ho.
For W Fd some linear subspace define by (W) the space of linear functions over Fd with coefficients from W. Now consider the following setup: given a, i. as defined above, project Fdd onto an + dimensional subspace V such that Lin,(? (V) c Ling(d) (dd) via an appropriate linear map II such that is not in its kernel. Now define o' Io O and let Hi be the n dimensional subspace of V consisting of fanctions S' such that En+1 d. b, Similarly, define H', to be the set consisting of functions fo such that Ex+1 oi. b.
9
The reduction now boils down to the fact that showing learnability of H' and non-learnability of Hy U Hi (together with distribution families D/,Di consisting of distributions with uniform marginals over Fd and labelings from Hy H', respectively) with A' can be shown analogously to the setup (A, Ho. H1, DD from Theorem 4 via simple some adaptions of the steps involved in proving it. In some more (but not full) detail:
Since the linear spaces Lin,(d,n) and (V) (and their above mentioned subspuces) have the same cardinalities, it follows that all proofs based solely on counting functions subject to a fixed number of linear constraints carry over one-to-one.
Combining linear coefficients of two linear functions fax e (in, trivially yields an- other linear function fath Lin (d). Hence Lemma I applies.
29

---

Published as a conference paper at ICLR 2024
Any linear combination (modulo q) i..d. random variables uniform over Ey is again uni- form. This fact together with our assumption of i.i.d. uniform inputs means that Lemma carries over.
For deriving the numbers of consistent functions in Lemma we first "preprocess' the inputs via the mapping IIX with II as defined above. Recull that in the original setup this mapping simply amounted to truncating the input vectors.
One can also easily adapt Lemma since spanning e1 has the same probability as spanning any arbitrary fixed o'. The TV distance appearing in the final steps of showing Theorem is the same in both setups for the same reason.
I LIMITATIONS ON ESTIMABILITY IN BINARY CLASSIFICATION
Let us restate Theorem for convenience:
Theorem 5. For every Aain (possibly randomized) and every n d-11, is not 0,1,,.,,,) estimable with respect to Ling (d) and the 0- 1 loss. More so, for every deterministic A é Aisnn and every 6 n s A is not (0.25, 0.32, n)),,n))-e -sstmmabl with respect to Ling (d) and the loss.
1.1 PROOF OF THROREM 5 FOR A DETERMINISTIC
Proof. We consider the case q 2 and examine when estimability is not possible for any algorithm A Ao by bounding the accuracy of the optimal estimator E². The result once again carries over to the more general case A E Atin due the reduction argument described in the remark appearing at the end of the previous section.
Due to an argument analogous to the one in Lemma 3, we have that for n s d and rank(X) k, there are 2d-k consistent functions in Ling(d). By definition, in order to have (v. 17, n) -estimmbbbill E² can have failure probability at most 17(1 n) for given n,n.
Since for any given S, f is uniform over all consistent functions in Lin(d), the optimal estimator E² assigns 0 whenever k n,, since in this case any Ag outputs the ground truth almost surely.
Moreover, any estimator E= that is optimal for a fixed error level v must necessarily assign a value cu (0.5 v, 0.5] whenever & n, since then there are multiple consistent functions Ling and simultaneously P({A(S)= h)) for ground truth hypothesis h. To expand this, note that if g were assign any value in [0,0.5 =) while there exist 2 functions consistent with S, this would cause the fidelity terms F; := |E' (A.S)- LD,,LL,,,...... (A(SS) to exceed the threshold in m m-11 of the instances and only in single instance fall below This would obviously yield an increased overall error probability and hence be suboptimal. We can therefore assume w.l.o.g. that E² has o = 0.5.
Given that v = 0.25 and n < d, this estimator then fails (i.e. exceeds the error level v1) over {ff (X))s Ling,0 Ling, (dd n)) with probability
2
2 -1
P([E (A,S) LD (A(S)))
Σ
2 k-n-l
2 2
(1
(50)
2
2n+1
k=U
2* -1
x (2
(51)
2 -
2 k-
(52)
k=0
where the derivation is analogous to the one of / in Lemma 5.
On the other hand, for d, from a similar argument it follows that over (ʃ u(()) Lin)
given that rank(X) k. AA picks the ground truth with probability 2 and hence z² fails with
30

---

Published as a conference paper at ICLR 2024
probability
(A.5) LD((())))) 2dd R2(n,
(53)
k-0
Combining equation 52 with equation 53 obtain that for all d. over (d), the optimal estimator 2" fails with probability
P((2" (A.S) LD(A(S)))) = Σ 2 m- mn(n, k-0
(54)
where min d 1}. It can be easily verified that for fixed d, equation 54 is monotonically decreasing in n. Moreover, when fixing n d, equation 54 is increasing and exceeds 0.32 for all d2 6.
1.2 PROOF OF THEOREM 5 FOR A RANDOM
Proof. Assume w.l.o.g. that A randomly outputs consistent function in Ling,o whenever possible. Define E_ (rank(X-) n} n {ei spanned]. Over the class Ling(d, it follows from equation 46 together with the fact that R2(n, n, > 0.57 for all n 2 that
F(E.) > 0.57 0.5
(55)
where X- denotes the reduced nx x (n+ + 1) input matrix (recall that over Linz(d,)) ) sufficient to process the first coordinates of the inputs). But in this case, there exists exactly consistent function in each Linz,o n) and 2 1 (d, n). Due to argument similar to the one presented the know that upon observing E_, optimal estimator z" of the population risk assigns 0 since this yields the optimal accuracy. But then, E" exceeds the error level V 0.25 under the event {h- Ling,1 } for i denoting the ground truth labeling function. Since this event has probability 0.5, we can conclude that E² fails with probability at least 0.57 - 0.5 0.5 > 0.14. Since this implies that Ling, (d, n) Ling, (d, n) not (0.25, 0.14, essesmmmabl,, if follows that the superset Ling (d) is also not estimable with the same parameters.
preceding subsection,
31


Reviews:
[{"review_id": "JsozHtggWs", "reviewer": "Reviewer_jDS8", "summary": "This paper considers the problem of understanding the tightness of two general families of the generalization bounds in the literature. The first family is the class of complexity measures that depend on the output of the algorithm and the training set, the second class is the class of algorithms that depends on the “description of learning algorithm” and the training set. The main question of the paper is there a family of generalization bounds that are uniformly tight in the overparameterized setting?\n\nThe paper proposes some natural definitions such as “overparameterized setting”: They define the overparameterized setting as the setting that with a given number of samples, accuracy, and confidence, a realizable distribution with respect to a family of hypotheses is not learnable.\n\nThe main result of the paper is that for these two families of the generalization bounds we can't prove a generalization bound which provide \"uniformly\" tight bound.", "questions": "-- Definition of tightness can be improved: In many cases, we are interested in correlation of complexity measure and the actual generalization gap. It is not clear to me that the definition of tightness is the best possible.\n\n\n-- In Page 14, there is this paragraph which clearly is not about Negrea et al. (2020).  This paragraph is unrelated to this paper.\n\n“Negrea et al. (2020): The paper studies convex optimization, so the results can hold only for a single neuron. Nevertheless, although it gives matching lower and upper bounds, the bounds match only asymptotically when n is very large so the scenario is far away from the overparametrized regime (which is the focus of interest for neural networks).”\n\n-- what are the challenges to extend the results to agnostic settings?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think the main message of the paper probably is the most interesting part:\n\nWe need to develop an understanding of the formal assumptions on the algorithms and distributions under which a generalization bound can be tight. Otherwise, we can develop lower bounds as shown in this paper.", "weaknesses": "-- The main issue I found in the paper is that in many places the discussions are not precise. As an example the claim about cross-validation can be misleading: The authors claim that cross-validation approaches do not lead to algorithm design principles. It is not completely correct. For instance, the well-known algorithm of the one-inclusion graph [Haussler et al 1988] is based on the cross-validation analysis. \n\n[Haussler et al 1988] Haussler, David, Nick Littlestone, and Manfred K. Warmuth. \"Predicting [0, 1]-functions on randomly drawn points.\" Annual Workshop on Computational Learning Theory: Proceedings of the first annual workshop on Computational learning theory. Vol. 3. No. 05. 1988.\n\n\n-- Proof of Theorem 2 and failure of the generalization bound: I checked the proof and it seems that the proof implies that the generalization gap is large for algorithms with large population error. I think it is unsatisfactory as we are interested to show a generalization gap is small for \"good\" learning algorithms\n\n\n-- There are generalization bounds based on conditional mutual information which proven to be \"tight\" in the realizable scenario (For instance Haghifam et al 2022, Thm. 3.3.) It seems this class of generalization bound has not been discussed in this paper.\n\nHaghifam, Mahdi, et al. \"Understanding generalization via leave-one-out conditional mutual information.\" 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ghPVTW54x0", "reviewer": "Reviewer_iLzH", "summary": "This paper tackles the question of the tightness of existing generalisation bounds to any learning problem of interest. Authors provably show that bounds being algorithm and data-distribution independent cannot reach uniform tightness in the overparametrised setting. They also show that, as modern generalisation bounds are often algorithm-dependent (while still independent of the data distribution), it is impossible for this type of bound to reach tightness uniformly for all data-distribution. Those limits suggest for future work to focus on generalisation bounds exhibiting how data-distribution and algorithmic performances intricate.", "questions": "- I believe the notion of overparametrised setting should be explained more carefully and clarified. Indeed, in the introduction, authors precise that such a setting 'roughly means that the number of parameters in the networks is much larger than the number of examples in the training set' while Definition 2 does not even make intervene the notion of parametrised space. The link with neural nets should be explicited.\n- page 6 'analouge of Theorem 1' -> analogue\n- About the implications of Theorems 4 & 5, can you be more specific about the links with practical neural nets? I read Appendix D and I am wondering about the recommendation given at the end of the section: how is it possible for theoreticians to either 'exclude many distributions over linear functions' if one doesn't know which one to focus on? Second, how realistic is it, in terms of computational time, to verify that 'the neural network architecture with SGD cannot learn any large linear subspace of functions'? \n- From a broader perspective, I believe that some claims in the paper are more a matter of personal interpretation than scientific facts and should be reformulated. 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). On the contrary, there may be several interests to derive a generalisation bound, a practical one is deriving generalisation-driven learning algorithms who may have a practical performance tighter than the associated bound as in Dziugaite & Roy 2017, or again simply propose a certain measure of complexity as in Neyshabur et al. 2017 to check if, in a few concrete learning problems, this complexity measure is tailored to explain generalisation. To me, the sentence at the end of Appendix D: 'At the very least, for a generalization bound for a neural network architecture trained with SGD to be meaningful, it must satisfy either of the following items...' is misleading as you assimilate the notion of 'meaningful' to 'precisely explaining the tightness on a given situation'. From my understanding of your work, I would say that existing generalisation bounds are too generic to provide such a precise understanding and are only an intermediary step which has to be completed by a study of the intrications between the data distribution and a learning problem. \n   Similarly, the analysis of the bound of Dziugaite & Roy (2017) in section 2.3 would gain to be reworked. Indeed, the sentence 'the bound in Dziugaite & Roy (2017) relies on implicit assumptions about the algorithm and the population distribution' is simply not true as it relies on the McAllester's bound which does assume anything on the data distribution. However, the efficiency of their algorithm on MNIST is effectively not due to the PAC-Bayesian bound but to more subtle assumptions satisfied by the specific learning problem of interest and is not easily extendable to other learning problems. \n   Finally, claiming that 'explicitly stating the assumptions underlying generalization bounds is not only necessary for the bounds to be mathematically correct...' is utterly misleading as it suggests that existing bounds are mathematically false while they are only not able to ensure tightness of learning algorithms in many situations: a vacuous bound is not mathematically flawed!\n   To me it is necessary to rework those paragraphs in order for the paper to be published as they do not give a fair perspective on the existing literature.\n\n**Conclusion** My current score is linked to the writing of the few paragraphs I mentioned above, I believe they have to be re-written to give a fairer comparison with literature and to remove false claims. That being said, I would be happy to increase my score conditionally to such rewriting, as I think this work is of the highest interest for the generalisation literature.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This work, especially the introduction, is utterly well-written and organised, it has been a pleasure to read it.\n- The proposed results have the potential to be impacting for the whole generalisation field, as they suggest to give up the current shape of state-of-the-art generalisation bounds to direct future works on bounds focusing on the role of the data-distribution.", "weaknesses": "- I have no problems with results (although I did not read carefully the proofs). However, several paragraphs in this paper, not only provide unfair analysis of existing literature but also contains wrong claims concerning existing works. I strongly believe those paragraphs have to be re-written before acceptance, see the Questions section below for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "613vLvvTFC", "reviewer": "Reviewer_bL1w", "summary": "This paper provides various quantitative results that demonstrate that in an \"overparameterized setting\", generalization bounds cannot be tight unless they depend on the structure of the sampling distribution: if a generalization bound applies indiscriminately to all possible distributions, it cannot be tight for the result of a successful algorithm in the overparametrized setting (which is defined as a setting where there is not enough data for there to exist an algorithm which will perform ($\\alpha$-) well with high probability (1-$\\beta$) over a random draw of a realizable distribution. In a sense, the results can be interpreted as a quantitative version of the contrapositive of the fundamental lemma of statistical learning theory (which says that if a function class is estimable, it is learnable). \nSeveral results (including theorems 2 and 4) study specific toy settings where the overparmetrization can be more concretely described (e.g. the number of samples is less than VC dimension or the actual dimension of the space) and the statement holds thanks to an assumption that the marginal distribution over the input is uniform. These results are used to argue that the only type of generalization bounds that can correctly explain the success of Machine Learning models such as neural networks in the overparametrized setting must exhibit dependence on the sampling distribution. \n\n\n\nMore precisely\n\nTheorem 1 states that if we consider a function class associated to an classification problem with the 0-1 loss and a finite set of realizable distributions, as long as the problem is overparametrized (i.e., not reliably learnable over most distributions), then there exists an ERM algorithm whose error cannot be reliably estimated either.\n\nTheorem 2 shows that if the number of samples is less than the O(VC dimension) and the sampling distribution over the inputs is a uniform distribution over a finite set (which is shattered by the hypothesis set), then the class is not estimable. \n\nTheorem 3 shows that if a function class and a set of candidate ground truth distributions can be split into two parts, each realizable with respect to each other, and if the total variation distance between the resulting mixture distributions over the samples is not close to 1, then no estimator can work uniformly well for all algorithms with high probability. The proof heavily relies on the assumption that the total variation is not too high and a coupling argument from [2].\n\nTheorem 4 concerns the learning problem of learning linear maps over $F^d$ where $F$ is the finite field of size $q$. Here, similarly to Theorem 2, it is assumed that the inputs are drawn from a uniform distribution, which allows one to define the overparametrization more concretely ($n<<d$). One considers the class of algorithms which \"are biased towards a given set of subspaces\" (i.e. for all $n$, there exists a subspace of dimension $n$ such that the algorithm always outputs a consistent hypothesis from that space if there exists one).  This class is shown not to be estimable. The proof relies on several elegant combinatorial arguments together with existing results form [1] concerning the proportion of matrices over a finite field which have a given rank. \n\nTheorem 5 specifically improves the rate (in terms of the failure probabilities) for the case where $q=2$. \n\n\nReferences:\n\n[1] IAN F. BLAKE AND CHRIS STUDHOLME, PROPERTIES OF RANDOM MATRICES AND APPLICATIONS, 2006\n\n[2] Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables, 2021. (Arxiv)", "questions": "1. Does Theorem 1 only apply to a discrete state space? In the proof towards the end of Page 16, you write down $P_1(S,h)=P_2(S,h)$, which only makes sense if we are in the discrete setting. This should be clearly stated as an assumption in the theorem. \n\n\n2. Could you explain the symmetry argument from the remark on Page 21 a bit more carefully? I am having trouble fully understanding it. \n\n\n3. Why does the argument you rely on in the proof of Theorem 5 not work in general for Theorem 4?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Understanding generalization bounds at a fundamental level is an extremely important and popular topic, and this paper makes a nontrivial contribution in this direction. \n\n2. All the formal results and proofs are sound and reasonably well written. \n\n3. Some of the **proofs are nontrivial**, especially the **proof of Theorem 4**, which is quite impressive and relies on an ingenious splitting into many different situations depending on the rank of the design matrix and whether or not the first unit vector is in the span of its rows. **This is a solid maths paper.** \n\n4. The main claim of the paper, if appropriately toned down, is an interesting variation on known observations that may hitherto never been individually explained in such detail. This makes the paper highly worthy of publication. \n\n5. It is very nice that the relationship with existing works such as [5] is explained.", "weaknesses": "The paper makes sensational claims that lack nuance: in the main paper and in extensive discussions in the appendix, the paper uses the argument derived from Theorems 1 to 3 to explain that most existing generalization analyses are invalid or at least \"lacking\" since they \"do not take the distribution into account\". \n\nAs far as I am concerned, there are several serious problems with this claim which can be summarized as follows:\n\n1. The general argument is partially valid, but not as strongly as the authors claim:  it applies to any \"overparametrized bound that doesn't depend on the structure of the sampling distribution\". At an abstract level, this description very loosely \"can be argued or conjectured to apply to a large part of the existing literature. However, it doesn't strictly or objectively apply to almost any of the existing literature. \n\n2. The part of the paper's general argument which is valid is not completely novel. Although all the theoretical results appear novel and are indeed interesting, once they are compressed into the authors' high-level statement that \"a bound cannot be tight if it works uniformly over all distributions and the setting is overparametrized\", they no longer consist in a novel idea. Theorem 1 can be summarised as saying \"not learnable implies not estimable\", which is the contrapositive of the fundamental lemma of SLT which says that \"estimable function classes are learnable via empirical risk minimization\". The novel component of the results consists in turning this result into a quantitative version where a distribution over the set of realizable distributions is considered. \n\n3. 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]. \n\n\n\n\nMore detailed explanation of point 1 above:\n\nAll theorems presented rely on the assumption that the problem is \"in the overparametrized setting\", which is defined in a very strict way that goes very far beyond saying that the number of parameters is greater than the number of samples and makes the abstract message of the theorems (theorems 1 and 3) approach a tautology. By definition, the authors assume that there is not enough data to find an algorithm that will reliably estimate most sampling distributions considered. This is only a short step from directly assuming that \"any generalization bound which only relies on the sampling distribution is vacuous\". All the concrete examples given in Theorems 2 and 4 make use of unrealistic assumptions about the uniformity of the sampling distribution. \n\nI understand that this does not fully invalidate the authors' point because it does show that no bound that relies on a \"fixed\" hypothesis class definition can be uniformly tight for all distributions: the authors' argument that \"for a bound to be nonvacuous in the overparametrized regime, it must be dependent on the sampling distribution\" is correct, but I feel like the authors catastrophically overstate the extent to which this directly invalidates any of the existing literature. \n\nWhich bounds in the existing literature are really \"in the overparametrized setting\"? Which of them really \"do not depend on the sampling distribution\"?\n\n\nThe only example of existing bounds that I can think of where it is genuinely known for certain that one is in the overparametrized setting would be parameter counting bounds (e.g. [6]). As far as I understand, even early norm-based uniform convergence bounds such as those of [7,12] cannot technically be proved to be \"in the overparametrized setting\" except by directly showing that they are vacuous, which makes the argument circular.  Likewise, although the idea that existing bounds such as margin bounds (e.g. [7]) \"do not take the distribution into account\" makes some sense, it is not technically true since the margin depends on the data: the idea that generalization bounds for neural networks in the setting where there are more parameters than samples must rely on the sampling distribution can arguably be placed as early as 2017 with the advent of norm-based bounds (this is reflected in the text of the introduction of [7]).  Data dependency is also given an increasingly important role in many more modern results such as those of [8,9], which replace the product of spectral norms in the bound by an empirical analog, and later in [10,11], which rely on empirical estimates of the norms of the activations in their analysis. Understandably, none of these bounds are traditionally considered to be in the category of \"data dependent\" bounds (because the data-dependency isn't \"strong\" enough), but none of the theorems of the present paper actually apply to any of them. This means the argument in the paper, although valid at an abstract/intuitive level, should not be presented as mathematically invalidating almost any existing works. Beyond the above works, **the results in [3,4] (including the NTK literature)** certainly take data dependency to the next level and arguably **provide a genuinely satisfying answer to the issue touched on in the present work**. They should be discussed. Note also that basically any bound that relies on the rank of the weight matrices or a similar quantity such as the sparsity of the trained connections would be non trivially using the sampling distribution (Cf also [15])\n\n\nIn 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**.  The paper also similarly presents a **blanket dismissal of so-called \"Rademacher bounds\" on page 13**. Almost every bound, including actively distribution-dependent bounds such as [3,4] relies on Rademacher arguments in some part of the proof. Given the current nature of the reviewing process and the hype-driven personality of the community, publishing/highlighting the current version of the paper would put a lot of legitimate future research at high risk of being unfairly dismissed. Overall, the main paper and appendices B,C and D should be somewhat toned down.  \n\nIt would also be nice to describe the relationship between the current work and the benign overfitting literature [13,14]\n\n\n\n\n=====================Minor errors/issues of a mathematical/presentation nature=======\n\n\nStatement of Theorem 3 on Page 8: I think the authors meant to write $S_0~D^n_{I_{0}}$... before \"where $I_0=...$\" rather than the other way around. \n\nIn Lemma 1, the symbol represented by a small rhombus presumably refers to function composition but is not defined. \n\n\nIn the statement of Theorem 5, the fact that $q=2$ is not stated, though I believe it is an assumption in the Theorem.\n\n\nThe top of page 21 is not very well organized: the last component of the \"definition 8\", the definition of $A_{i}$ is problematic since it uses the words \"is biased towards selecting consistent hypotheses in $lin_{q,i}(d,n)$\" without explaining what it means (I know it can be inferred by analogy with definition 5 in the main paper, but it technically should still be defined more properly here). \n\nImportantly, the remark on page 21 only makes sense if one already has made an attempt at reading the proof of Theorem 4. It should be incorporated into the proof of Theorem 4 and explained more rigorously. \n\n\nThere are several minor issues with the proof of Lemma 3: firstly, in the first line, $f_a,f_b$ are defined as \"parity functions\", which seems to hint that we are working with the case $q=2$ (that is not the case). Furthermore, only $f_a$, not $f_b$, is used in that particular paragraph, though an arbitrary $f_b$ in the null space of $X^{-}$ is used in the next paragraph. The last sentence of the third paragraph takes some time to be digested: perhaps a quick mention of realizability can help the reader. \n\nIn the fourth paragraph of the proof of Lemma 3, I think writing \"there always exist **at least** $n+1-k$ canonical basis vectors which are not spanned...\" would be much better than the current \"there always exist in total $n+1-k$ canonical basis vectors which are not spanned...\", since this statement takes a bit of effort to mentally process and I think there can be more than $n+1-k$ vectors which are not spanned!\n\n\nIn the second line of Section G.4 on page 23, I think the authors meant to write $\\mathcal{H}_1$, not $\\mathcal{H}_0$. There should also be a better definition of $\\mathbb{A}_0$ in this part of the text (just a reminder would help, \"an algorithm is in $\\mathcal{A}_0$ if the following statement holds: \"if there exists a consistent hypothesis in $\\mathcal{H}_0$, the algorithm must chose one such hypothesis\".\n\n\nThe end of the proof of lemma 4 is badly organized: the last two paragraphs **should be swapped**, and the sentence \"the claim follows\" should follow as a separate last paragraph. \n\nOn page 24, in the paragraph that begins with the estimation of $\\mathbb{P}(E_3|E_{4,k})$, I think the authors meant $\\mathbb{P}(E_3|E_{4,k})=1-\\mathbb{P}(E_3^{c}|E_{4,k})$, not $\\mathbb{P}(E_3|E_{4,k})=1-\\mathbb{P}(E_3|E_{4,k}^{c})$.\n\n\nThe argument at the top of page 26 needs to be reformulated: \"which implies that $1-q^{-2} \\in 1-o(1/q)$ is not the right statement: the fact that $1-q^{-2} \\in 1-o(1/q)$ is not deduced from the previous statement, instead, it is the first statement in the induction case to show that the expression on the line above is in $1-o(1/q)$.\n\nOn page 26 (just like in the main paper), the statement of Theorem 5 should include the assumption that $q=2$. \n\n\nThe proof of Theorem 3 could be slightly improved: the sentence \"this yields what we wanted\" at the top of page 20 feels a bit abrupt since it has not yet been made clear that the statement below will be used to show that $\\mathcal{A}$ is not estimable. \n\nRight in the middle of page 20 in the proof of Theorem 3, the definition of the even $B$ is missing a $>\\alpha$ before the last curly bracket. \n\n===========Typos/very minor presentation comments=============\n\n\nThe table of notations should be substantially improved to include all the notations in the paper including $R_q(.,.,.)$, $Lin_q(d)$ etc.\n\n \nIn the appendix, the names of Theorems 1 and 2 have been interchanged (Theorem 2 in the appendix is actually Theorem 1), and Theorem 1 in the appendix is actually Theorem 2 (as can be seen from its introduction on page 18 which says, \"we now use Theorem 1 to show the following\") \n\n\nIn the Statement of Theorem 1 (referred to as \"theorem 2\") on page 16, there is an issue with the punctuation (,.)\n\n\nThere is a period missing at equation (8).\n\n\nIn page 22, proof of Lemma 2, the second part of the proof actually doesn't rely on the theorem from [1], so it is a shortcut. This is not clear from the formulation. At a minimum, the first sentence of the second paragraph could read \"the second statement can be inferred from the first, but also follows directly from a simple...\"\n\n\nIn the proof of Lemma 4 on page 23, first paragraph, there is an extra space after \"w.r.t.\". \nIn the proof of Lemma 4 on page 23,  \"be it deterministic of random\" should be \"be it deterministic or random\"\n\n\nThe paragraph starting with $\\mathbb{P}(E_1|E_{2,i}\\cup E^{c}_3\\cup E_{4,k})=1-q^{k-n-1}$ should be slightly reorganised to avoid the repeated use of \"since\". \n\nThere seems to be an extra space before equation (25) and there is a period missing at equation (30). \n\n\nAt the top of Page 25, there is an extra space between  $\\|$ and $P$ in equation (31).\n\n\nIn pages 26 and 27, there are plenty of equation numbers which are not in brackets. The corresponding \"\\ ref {}\" should be changed to \"~ \\ eqref { } \"\n\n\nIn the proof of Theorem 5 on page 27, there are plenty of \"$lin_{2,0}$ which should probably be $lin_{2,0}(d,n)$. \n\nThere is a period missing at the last equation of page 19.\n\nJust before the bullet points on page 20: \"at least one of the following items hold\" should be \"at least one of the following items holds\"\n\n\n=====================================\n\nReferences:\n\n[1] IAN F. BLAKE AND CHRIS STUDHOLME, PROPERTIES OF RANDOM MATRICES AND APPLICATIONS, 2006\n\n[2] Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables, 2021. (Arxiv)\n\n[3] C Wei, T Ma, Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin, ICML 2019.\n\n[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. \n\n[5] Vaishnavh Nagarajan, J. Zico Kolter, Uniform convergence may be unable to explain generalization in deep learning, NeurIPS 2019\n\n[6] Philip M. Long, Hanie Sedghi, Generalization bounds for deep convolutional neural networks, ICLR 2020\n\n[7] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. Spectrally-normalized margin bounds for neural networks, NeurIPS 2017.\n\n[8]  Wei and Ma, Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation, NeurIPS 2019\n\n[9] Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-bayesian generalization bounds for deep networks via generalizing noise-resilience, ICML 2019. \n\n[10] Antoine Ledent, Waleed Mustafa, Yunwen Lei, Marius Kloft, Norm-based generalisation bounds for multi-class convolutional neural networks, AAAI 2021.\n\n[11] Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, Roland Kwitt, On Measuring Excess Capacity in Neural Networks, NeurIPS 2023.\n\n[12] Size-Independent Sample Complexity of Neural Networks.  Noah Golowich, Alexander Rakhlin, Ohad Shamir, COLT 2018. \n\n[13] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, Alexander Tsigler,  Benign Overfitting in Linear Regression\n\n[14] Shamir, The Implicit Bias of Benign Overfitting, COLT 2022. \n\n[15 ] Tomer Galanti, Mengjia Xu, Liane Galanti, Tomaso Poggio ,  Norm-based Generalization Bounds for Compositionally Sparse Neural Networks", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2tssLv83R5", "reviewer": "Reviewer_Hb6n", "summary": "This paper presents several novel results regarding the non-existence of tight generalization bound in the over-parameterized setting. In particular, this paper proves that a tight generalization bound cannot exist without making assumption about the distribution of training data. In the case where no assumption is made about the learning algorithm, the authors show a much stronger version \"no free lunch\" that any generalization bound is not tight on a large number of (Algorithm, Distribution) pairs. And in the case where we are concerned with a specific algorithm family, then the authors show that there is a inherent trade-off between the tightness of generalization bound and the quality of the learned model.", "questions": "In addition to all of my concerns above, how is over-parameterization used in the argument between Definition 3 and Theorem 1?\n\nOverall, I feel that some restructuring is necessary for Sections 4-6. The claims in this paper are very interesting and impactful, but I find them to be unnecessarily difficult to understand.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I find the results of this paper be very impactful. Understanding generalization properties in the over-parameterized regime is of great interest in recent literature and this paper basically shows that such analysis is impossible (both theoretically and practically) without assuming specific properties about the data distribution. This in turn shows that great number of existing bounds in the literature are not useful and any future work should direct to data-dependent bounds.\n\nThe authors did a good job by putting their results into different cases that are intuitive on a high level. And I find Table 1 to be very clean.\n\nSection 2 is well-written and gets the main points across without being entangled with the details.\n\nThe proofs are generally clean and easy to understand", "weaknesses": "I find the formal results stated in Sections 5 and 6 to be extremely difficult to follow. While the informal statements in Section 2 are understandably vague, Sections 5 and 6 failed to clarify my confusions from Section 2. I think this is due to two issues:\n\n1. Section 4 did a poor job at explaining the formal notation. I feel that Definitions 1 and 2 are not particularly well-motivated (more on this later). And shoving everything else into the Appendix does not help either.\n\n2. Certain points in the intro were not explained properly in later sections. a) The term \"vacuous\" was never formally defined, b) the connection between tightness of generalization bound (eq 1) and the notion of estimability is also not discussed in depth (why are they equivalent? I know the argument is not hard, but this is provides important contexts for the main theorems).\n\n3. The theorem statements are pretty mouthful themselves and except for Theorem 2, the authors did not offer discussions that helps with parsing the theorem statements.\n\nNext, some *major gaps* I found in the paper:\n\n4. 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.\n\n5. 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.\n\n6. In the proof of Theorem 1, the authors did not show the existence of Bayes-like Random ERM.\n\nA few minor comments regarding the proofs (I did not check Appendix G or H):\n\nPage 18: the theorem statement is about Theorem 2, *not* 1.\n\nPage 19: the final sentence should start with \"the second equality holds\"\n\nPage 20: the result \"Theorem 1 in Angel & Spinka (2021)\" is just a standard fact on the existence of coupling, so it is better to just say that directly.\n\nPage 20: the big equation block looks atrocious, please left align the lines and use indentation to make the + sign on the second line more visible. \n\nPage 20: Please define what event $B$ is before that big equation block. Also in the definition of $B$, the final inequality $L_{D_{I_1}}(A(S_1)) \\ge \\alpha$ is missing its RHS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)