Which Algorithms Have Tight Generalization Bounds?
Authors: Michael Gastpar
Ido Nachum
Jonathan Shafer
Thomas Weinberger
Venue: NeurIPS 2025 spotlight ()
Keywords: learning theory
Primary area: theory
TL;DR: We present conditions that preclude the existence of tight generalization bounds versus a stability condition that guarantees this.

Abstract: We study which machine learning algorithms have tight generalization bounds with respect to a given collection of population distributions. Our results build on and extend the recent work of Gastpar et al. (2023). First, we present conditions that preclude the existence of tight generalization bounds. Specifically, we show that algorithms that have certain inductive biases that cause them to be unstable do not admit tight generalization bounds. Next, we show that algorithms that are sufficiently loss-stable do have tight generalization bounds.  We conclude with a simple characterization that relates the existence of tight generalization bounds to the conditional variance of the algorithm's loss.

Which Algorithms
Have Tight Generalization Bounds?
Michael Gastpar
Ido Nachum University of Haifa
Jonathan Shafer MIT
EPFL
michael. waa.eell.ggttpp@pp...oo
inachumQuniv www.mniiiiaaiaaaaamm www.aa.a..................
shaferjo@mit.cm edu
Thomas Weinberger EPFL.
thomas. weinberger@epfl..co ch
Abstract
We study which machine learning algorithms have tight. generalization bounds with respect to given collection of population distributions. Our results build on and extend the recent work of Gastpar et al. (2024). First, we present conditions that preclude the existence of tight generalization bounds. Specifically, we show that algorithms that have certain inductive biases that cause them to be unstable do not admit tight generalization bounds. Next, show that algorithms that are sufficiently loss-stable do have tight generalization bounds. We conclude with a simple characterization that relates the existence of tight generalization bounds to the conditional variance of the algorithm's loss.
Introduction
Generalization bounds the heart of learning theory, and they play central role in attempts to mathematically explain the behavior of contemporary supervised machine learning systems. A generalization bound is an upper bound of the form
(D(A
where A(S) is the hypothesis output by learning algorithm A when executed with training set S, and (D(+) represents the loss with respect to the population distribution D. The term b is typically an expression of the form
b +((A H),
(2)
where Ls(+) is the empirical loss, H is a hypothesis class, and c(S, A(S), H) 'complexity" term, such as the VC dimension or a spectral norm, etc.
We say that generalization bound is valid if for every population distribution D, Eq. (1) holds with high probability; we say that a valid bound is uniformly tight (Definition 2.4) if for every population distribution, with high probability the difference between the two sides of Eq. (1) is small.
Bounding the loss using a generalization bound is quite different from using a validation set. Technically, generalization bound does not use additional samples beyond the training S. And while a validation set provides a single post-hoc measurement of the population loss after training is complete, a good generalization bound can provide insight into why a learning algorithm performs well, and can offer guidance for model selection and the development of new learning algorithms. For generalization bound to be useful in this
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

way, it is important that the bound be tight, so that it can distinguish cases with small population loss from cases with larger loss.
Unfortunately, experimental works have shown that many of the generalization bounds of the form of Eq. (2) that have been proposed in the literature vacuous! when applied to contemporary learning algorithms such as deep neural networks (Jiang et al., 2020; Dziugaite et al., 2020; Viallard et al., 2024, Section 4.4).
Gastpar, Nachum, Shafer, and Weinberger (2024) offered a partial theoretical explanation for this empirical finding. They considered generalization bound as in Eq. (2), namely, bounds that depend only on the training set, the selected hypothesis, and the hypothesis class. They proved that any such bound cannot be uniformly tight in certain regime (that is typical in practice) where the number of samples is insufficient for uniform convergence." Therefore, they recommended focusing generalization bounds involving expressions of the form c(S, A(S), H. A, ID), i.e., bounds that depend on, or are tailored for, a specific learning algorithm A and specific collection DD of population distributions.
This raises the following natural question about generalization bounds that are tailored for specific pair (A,
Question 1. For which pairs of algorithms and distribution collections do there crist tight generalization bounds?
A variant of this question was addressed in Theorems 3, 4 and 5 of Gastpar et al. (2024), but the general case remains open. In this paper we continue investigating this question, and present conditions that are necessary, sufficient, necessary and sulficient for the existence of light generalization bounds for given learning algorithm and distribution collection.
1.1 Setting
Following Gastpar et al. (2024), study the existence of tight generalization bounds using a notion estimability.
Definition 1.1 (Estimability). Let X' and y be sets, let E N, let
A: (X >))m y
be a learning rule, and let A Y) ) be collection of distributions. An estimator function
E: (X x +R.
Let e, 5, E [0.1] We say that A uniformly estimable. (or worst-case estimable) with respect to distributions D with precision and confidence using samples if there exists an estimator E such that
DD PS-D= [|=(s) (D S 21
We say that A is estimable on average with respect to distributions D with precision e and confidence using m samples if there erists an estimator E such that
PD- LD(S))))(AAS)) < 2 1-
(More briefly, we say that (A, is (e, m) uniiormmyy estimable, or (s, 5, -e)sstmmable average.)
The connection between estimability and tight generalization bounds is as follows.
Using the notation of Definition 1.1, if (A, is (E, 5, m)-estimable average, then there erists a genernlization bound b(S) (that may depend on and DB) that is 25-tight on average, namely
Proposition 1.2.
PD--UD) (bS)) 25 < LD(A(S)) < b(S)) b(S)) 21
(3)
AA bound is vacuous if it is of the form P(L)(A(S)) < bj 2 where 8 2 or (for the 0-1 loss) b > 1. Namely, it is true statement that provides guarantees the performance of the algorithu.
"They actually showed stronger result, that such bounds are not tight in an average-case sense for many (algorithms,, distribution) pairs.

---

Indeed, the generalization bound is simply b(5) E(S)+E, where E is the estimator witnessing the estimability of (A.D).
In the other direction, if (A,D) is not (e, 6, mm--stimabll on average, then there erists no generalization bound that satisfies Eq. (3), and in particulor no generalization bound con be uniformly tight with precision 28 (as in Definition 2.4).
Using these definitions, the Question 1 be rephrased, follows:
Which general and useful conditions are necessary, sufficient, or necessary and sufficient for tuple (A, DD) to be m))m estimable, or (e, -esasmmbblll on average?
Question 2.
We are specifically interested in addressing Question 2 in settings where the number of samples is not sufficient guarantee learning in general (in the sense of the VC theorem and uniform convergence for example), because most contemporary machine learning algorithms (such as deep neural networks) are used in such settings.
1.2 A Simple But Crucial Distinction
To understand our work, is necessary to keep in mind the following simple distinction:
Learnability and estimability are not the same.
Learning means that an algorithm achieves low population loss; estimability means that an algorithm has tight gencralization bound.
Some algorithun do not learn well, but they are very estimable (e.g., constant algorithms, as in Example 1.5 below). And if the number of samples is too small to allow learning, some interesting algorithms might nonetheless perform well on a certain subset of distributions and also be very estimable.
In the other direction, some algorithms learn well in practice (e.g., achieve low population loss on a distribution of interest), but are nonetheless not estimable for a larger collection D.3 And the number of samples sufficient for learning perfectly, there might nonetheless be some algorithms that are not perfectly estimable (Example 1.4).
Lastly, in some cases there is a learnabiltyy-ssiinbbllyy trade-off (see Example 1.8). And while empirical risk minimization is in some sense the optimal learning algorithm, the empirical loss can be far from the best estimator (see Example 1.6).
1.3 Our Results
We investigate which algorithms and collections of distributions estimable. As show in Example 1.8 below, ostimability a delicate phenomenon. In particular, changing the sample size by just small constant number can in some cases drastically change the set of (E, estimability parameters that are achievable. This means that identifying a simple and tight characterization that precisely determines the number of samples necessary and sufficient. for estimability can be difficult undertaking.
In this paper, present conditions that preclude estimability, conditions that guarantee estimability, and a condition that is both necessary and sufficient for estimability.
Our first result is condition that precludes estimability for algorithms that have an inductive bias towards certain subscts of VC classes, showing connection between estimability and central notion from traditional learning theory.
Theorem (Informal version of Theorem 3.1). Let C {=1)* be a hypothesis class with VC dimension large enough, and let m S vd/10. Then there exists a subset. F C and corresponding realizable distributions D such that any learning rule that has an inductive bias towards is not (1/4- - o(1), 1/6, -estimable on averuge over D.
3This is why it is important that generalization bounds for neural networks explicitly specify for which collection B they intended to be tight
3

---

Note that the theorem prechudes estimability on average, and so in particular it precludes worst-case estimability. The proof of Theorem 3.1 uses the Haanson-Lindenstranse lemma (Theorem K.1), the probabilistic method, and a technical lemma (Lemma H.1) concerning the estimability of nearly-orthoogoal functions.
To the best of our knowledge, this paper is the first to provide a rigorous and general mathematical formulation showing that any finite VC class admits inestimable algorithms. This is somewhat surprising because it mcans, for instance, that for any neural network architecture, there are some training algorithms for which one will not be able derive tight generalization bounds (even if the distribution is realizable!). We believe this is meaningful contribution.
Our next inestimability result is as follows.
Theorem (Informal version of Theorem 3.2). Let H. S {+1}* be a collection of roughly 2 functions and corresponding realizable distributions D. Then any learning rule that has an inductive bias towards H is not (1/4-o(1)) ~ 1/6, m---etimaale average over D.
Theorem 3.2 is partially stronger than Theorem 3.1 in the sense that it shows inestimabillty for every algorithm that has an inductive bias towards a class of nearly-orthogone functions, whereas Theorem 3.1 only shows the existence of subclass with this property. On the other hand, Theorem 3.1 is stronger than Theorem 3.2 in the sense that if Theorem 3.2 is applied to show inestimability for subclasses of VC class, then it yields inestimability only for m & 0 (V7). whereas Theorem 3.1 obtains inestimability for all m <v(va).
To show Theorem 3.2, we prove a concentration inequality using the duality of linear programs (Lemma I.1,, and then invoke the technical lemma (Lemma H.1).
Remark 1.3. Theorems 3.1 and 3.2 are stated for the case of binary labels, but they immediately imply inestimability also for regression and multi-clas. classífication.
One way to interpret Thcorems 3.1 and 3.2 is to consider scenario where one derives a now generalization bound for a given algorithm, without making explicit distributional assumptions (as is the case for many published generalization bounds), and having a sample size within the regime of our theorems. Such bounds are generally formulated as high probability upper bounds on the population loss. Note that the lack of distributional assumptions means that the bound has to hold (be a valid upper bound) for all distributions, including the families of distributions that appear in our theorems.
But this means, in the light of our theorems, that the considered bound is necessarily very weak for many distributions unless one satisfies at least one of the following items:
1. Exclude in advance all families of distributions with nearly-orthogonal labeling functions, and use this fact in the derivation of the generalization bound.
2. Mathematically show that the algorithm is not biased towards any set of nearly- orghognn functions.
The intuition behind Theorem 3.2 is that having an inductive bias towards collection H of nearly-orthogonal functions makes the algorithm very unstable small changes in the training set will cause the algorithm to shift between hypotheses in H. which are all
'Additionally the quantity hidden by the o(1) notation is smaller in Theorem 3.2 by quadratic factor (order 1/m vs. 1/vm).
5 "The limitation & 0(V2) when using Theorem 3.2 follows from the tightness of the Johnson- Lindenstrauss (JL) lemma. By the JL lemma, taking a collection F of 2" orthogonal functions on high dimensional domain, we project F using random projection and obtain a collection F' of 2" functions that are s-orthogonal defined
domain of dimension log (2"") _ In particular, let H be class with VC dimension d. We want to project F onto an H-shattered set of size with @(1/m). This yields d = m/(O(1/m)) e (m²). The tightness of JL. implies that this construction cannot be improved.
'It is known that there exist at least some neural network architectures which, when trained with SGD, are capable of learning orthogonal functions (such as parities). See Theorem 1 in Abbe and Sandon (2020).

---

very different from one another. This motivates our next result, which shows that stable algorithms are estimable, as follows.
Theorem (Informal version of Theorem 4.3). Let A be an algorithm that is sufficiently stable with respect to a collection of distributions TD (in sense of loss stability or hypothesis stability similar to Rogers and Wagner, 1978, or Kearns and Ron, 1999). Then (A, D) is estimable.
Seeing as there are many definitions of stability in the literature, Theorem 4.3 makes nontrivial conceptual contribution by identifying the "correct" notion of stability for under- standing estimability. Other notions of stability, such as leave-one-out stability (Bousquet & Elisseeff, 2002), do not capture estimability as well, we discuss in Section 4.
An additional motivation for Theorem 4.3 the intuition that contemporary machine learning algorithms (like deep neural networks trained with gradient descent) might indeed be sufficiently stable. If so, Theorem 4.3 would apply, meaning that it possible to obtain tight generalization bounds for deep neural networks based the stability property. To substantiate this intuition, we conduct simple preliminary experiments to estimate the the stability of neural networks in practice. Our empirical findings, presented in Section L, suggest that neural networks are indeed quite stable.
Finally, in Section 5, we present a necessary and sufficient condition for estimability based on the conditional variance of the algorithm's 's loss. This characterization formalized in terms of & estimability, which is asymptotically equivalent to average case estimability via Markov's inequality.
Proposition (Propasition 5.2). A is (e, esstimmabll in &2 with respect to ID if and only if ((vr(()(A(S))) [S] s.
1.4 Examples
We present a few simple examples to showcase the richness of the estimability setting. In this section s, 8 E (0, 1), X' is a set, m E N is a sample size, A: (X' x {=1})" + [=1]** is learning rule, S ((z), vi),..., (fm. 8m)) is a training set, and L denotes the 0-1 loss.
Example 1.4 (Perfect Icarnability does not imply perfect ostimability). Let X' = [0, let D = A(X x {1)) be the set of all distributions of labeled examples (z. where X and y 1. The collection ID is perfectly learnable, that is, there exists a learning algorithm that always achieves 0 population loss (namely, the learning algorithm that always outputs the constant function h(x)) = 1).
Nonetheless, not every learning algorithm is worst-case estimable with respect to ID. Indeed, consider the algorithm that on input S outputs the hypothesis
h(x) = {
-1 +1 otherwisc.
For any distribution D E D. LD((((S) - Dx DD on X. Hence, estimating the loss of A is equivalent to task of support size estimation, which is difficult. Concretely, for any finite set T S X, let Dr = U(T x (1)). Lot E be any estimator, and consider an experiment where with probability 1/2, we sample a set T X of size [T = m² chosen uniformly at random, and set D = Dr, and with probability 1/2 we set D Du U(X (1)). Consider the probability
Fm F)),, where Dx is the marginal of
1
p= P=Psm - LD(A(S)) 2m
Let E be the event where (xI,,.., .........,...................... Tm) m1 m. In the case where D = Dr, Claim K.2 implies that PP[F] 2 1/e. And in the case where D Du, [P(F] 1. Hence, both cases, with probability at least 1/e, the estimator receives sample of m distinct points chosen independently and uniformly from X, and cannot distinguish between these two cases. However, LD (A(S)) = O, whereas LD, (A(S)) _ - when É occurs. This implies that p 2 1/2e, and so () is not (2.,, m))mmiioooommmm estimable for any 8 < 1/2e.
Some algorithms are very estimable but are not good learning algorithms, as the following three examples.
5

---

Example 1.5 (Constant algorithms are estimable). Let m 2 log(1/0)/e². Let ho : X' - {+1} be a function, and let A be the constant learning algorithm such that A(S) = hg for all S. Then by Hoeffding's inequality, A is (s. 6, m)-uniformly estimable with respect to the set of all distributions D = A(X x (+1}), with estimator E(S) = [.s(ho).
M
For some algorithms, the empirical loss is not a good estimator, yet the algorithm is still estimable.
Example 1.6 (Memorization). Let ((log(1/0)/e) I m - {(e[[T1), and consider the algorithm A that imput S, outputs the hypothesis
h(x) = { -1 otherwise.
{y} = (m i [m] A x; = =x}
For each function f: X x {+1}, let Dj = U(f(2, f(z)) : z E X1), and let = (D/ : f e
(+1)²). Note that A always has empirical loss, which can be far from the population loss. Nonetheless, (A, (3) is (e, Juniforllyy estimable, using E(S) = H E [m] y: = 111 /m/ O
Example 1.7 (Most learning rules are estimable). Let d |X] oc, let F (+1)*; and for each f E F, let Dj- = U(((z, f(x)) : I E xX). Let A be the set of all mappings (X x {+1))** + {+1}*; and consider a mapping A chosen uniformly from the set A. So for every fixed f E F and every fixed sample S of size m consistent with f. A(S) is a function that was chosen uniformly from F. By Hoeffding's inequality,
vʃ VSEFVS supp(Dr)) PANULL) [LD)
2 6
2e 2dc² -2dc"
In particular,
P PA-T(A)---UE))---10)) LD, (A(5))
2 E S 2e
2e-2de² 2de2
Hence, by Markov's inequality, 99% of learning rules A AA satisfy that (D/ is (c, 200e-2de2 2dc² -m)-estimable on average.
In both cases, the algorithms are estimable because their loss is guaranteed to be high, namely, the algorithms are poor learners.
Finally, ERM algorithms for learning parity functions are a particularly instructive case. They demonstrate two important phenomena: (1) Estimability can be very delicate matter, in the sense that changing the sample size by a small additive constant can make all the difference (e.g., any ERM for parities is very estimable with m d + 10 samples, but not very estimable with m = d): (2) when the sample size is not sufficient for learning all the distributions in the collection ID, there can be trade-off between learning performance and estimability. Algorithms with no inductive bias will perform equally poorly for all distributions, and this makes them estimable. In contrast, algorithms that have an inductive bias towards subset D' CD can perform well on D', and this can make them less estimable.
Example 1.8 (Parity functions). Let d E N be large enough, X' = (F2)², and let H (fu: : w E X3 S (F2)* & be the class of parity functions such that fu( = =iejd Wi 24. Let D= (Dy}sen with D, = U(fxx, let
E x)).. For a learning rule A and sample size m,
p(m) PDDUDD [bD = =].
SM(D)"
For sample size m 2 d + 10, any FRM algorithm for H satisfies p(m) 2 0.999, meaning it learns IDD well, and hence is (0, 10-3,,4 dd 10)-estimable on average.
Similarly, for smaller sample sizes, any ERM for H satisfics p(d) 2 0.61, and p(d - 1) 2 0.38. However, ERM algorithms differ in their degree of estimability for smaller sample sizes. Concretely, there exist ERM algorithus such that for any 6 < m S d there exists a collection Dm for which the algorithm is not (0.25, 0.32, m) -estimableeeee on average. In contrast, for the same hard collections D., ERM algorithms without an inductive bias perform poorly on all distributions for small m, so they are significantly more estimable.
'The quantitative statements in this example follow from the results in Gastpar et al., 2024, see Section D for discussion.

---

1.5 Related Works
The works of Nagarajan and Kolter (2019, Theorem 3.1) and Bartlett and Long (2021, Theorem 1) also study cases where generalization bounds fall short of estimating the performance of learning algorithms (while Negrea et al., 2020 provide a response to these claims). They preclude tight algorihhm-dependent generalization bounds only for uniform convergence and linear classifiers. Their theorems consider specific distributions (Gaussian in Nagarajan and Kolter, 2019, different distribution per sample in Bartlett and Long, 2021) and specific types of SGD. In contrast, our work uses the same marginal distribution across all sample sizes, and applies to many algorithms and distributions.
We now mention a few of the ggoorthmm-dependen generalization bounds in the literature. Zhang, Teng, and Zhang (2023) study convex optimization, so their results apply only to a single neuron. While providing matching lower and upper bounds, these bounds match only asymptotically when the sample size n is very large, far from the overparameterizee regime relevant for neural networks. Nikolakakis, Haddadpour, Karbasi, and Kalogerias (2023) proposes generalization bounds for algorithms satisfying a certain symmetry property (e.g., full-batch gradient descent) when using smooth losses. These bounds are algorithm-dependdent but distribution-free making no distributional assumptions.
There are number of information-Lheorelll generalization bounds that are both algorithm and distribution dereddnd,, such as Theorem 1 of Xu and Raginsky, 2017. However, such bounds are sometimes difficult to approximate numerically in tight manner. These bounds are part of the PAC-Bayes framework." 8 Unfortunately, when these PAC-Bayes or information- theoretic bounds can be approximated in tight manner," 9 they do not reveal what properties of the (distribution, algorithm) pair allowed for such success in learning and estimation. The works of Haghifam, Moran, Roy, and Dziugiate (2022b) and Rammal, Achille, Golatkar, Diggavi, and Soatto (2022) use the notion of leave-one-out conditional mutual information to derive generalization bounds, which provide another characterization of VC classes and yield non-vacuous generalization bounds for neural nerworks.
Bartlett et al. (2020) establish that benign overfitting in linear regression with Gaussian covariates requires strong control over the data covariance; a line of work initiated by Rubinfeld and Vasilyan (2023) studies learner tester pairs, where the learner is guaranteed to succeed whenever the distribution is accepted by the tester. These works, like ours, shine light from various angles on the crucial role of distributional assumptions in achieving generalization guarantees.
For a detailed comparison to Gast el. al. (2024), and further related works, see Appendix A.
2 Preliminaries
All the proofs for theorems appearing in the next section appear in the appendix.
Definition 2.1. For m N and sets X and y, a learning rule function A : (X' x )m yx We will also consider learning rules with voriable-size input, i.e., A: (X x y)" y
In this paper we informally use the terms 'learning algorithm' and flaaningg rule' interchange- ably. Both words refer to a function, ignoring considerations of computability. All learning algorithms in this paper are deterministic." 10
Notation 2.2. For a set It we write A(S)) to denote the collection of all probability measures over measurable space (R,F), where F is some fixed a oallgebra that is implicitly understood. We wrile U(2) to denote the uniform distribution over Ω2
Definition 2.3. Let m E N, let X, y be sets, let h (Zm. vm)) E (X' x y)m, and let D E x The empirical loss of
X y, let S
*See proof for Theeorem 8 in Bassily et al. (2018), which is equivalent to Theorem 1 in Xu and Raginsky (2017). "Such as in Issa al. (2019), Issa al. (2023), Esposito et al. (2021), Harutyunyan al. (2021), Dziugaite et al. (2021), Haghifam et al. (2022a), Hellström and Durisi (2022), and Wang and Mao (2023).
Seeee Section B for a discussion on how our results can be extended to randomized algorithms.

---

with respect to S is (h) = t/2 Eig(ml ((h(zs) & vc). The population loss of h with respect to D is LD (h) PP (x.0)= [1(x) vl.
Definition 2.4 (Uniformly tight generalization bound for algorithm). Let e,6 [0, 1], let X' and y be sels, let m E E,, let A: (X' x 3) - y be a learning rule, and let b: (& x )) - [0, be a genemlization bound (that may depend A). We soy that b is uniformly tight for A with precision ε and confidence if for any distribution D E A(X x }))
N,
PSwD (MS) - S I.D(A(S)) S ((S) 2 1
Notation 2.5. Let X be a set, let C {=1}** be a hypothesis class, and let 8 E (X x {+1))*. We denote Fs = {f F =s
The following definition captures the notion of a learning rule having an inductive bias towards particular set of hypotheses.
Definition 2.6. Let m E N, let X be a set, and let F F {+1]} be a hypothesis class. We say that a learning rule A (X x {+1))" [+1]* is F-interpolaling A(S) Fs for every somple S (X (+1))² such that Fs + Ø.
Remark 2.7. The property of F-interpolation is similar to the more common property of proper empirical risk minimization (proper ERM) for F. However, F-interpolation slightly weeker requirement. Specifieally, if S is not F-realizable (f.e., Fs = (3), then an F-interpolating learning rule may output any function in {+13*, whereas proper learning rule for FF must always output function from F.
Definition 2.8. Let 2 0, let X be a set, and let F [+1]+ be a hypothesis class. We say lhat F is 8-orthogonal with respect to X, denoled F Le,x, if every distincl S.y E F salisfy
[=-uxx][((x)(()]]]] S.
For simplicity, we write F Le when X is understood from contert.
Proposition 2.9. Let E > 0 and let F S {+1}* be e-orthogonal. Then for any distinct F,
1
< S (f -
2
1 f(r)((1)
Proof. P Pa-u(())((a) g(x)] = (1 g(x))] = ELWU(X))
2
2 - (en
3 Conditions that Preclude Estimability
We present two conditions that preclude estimability.
3.1 Inestimability for VC Classes
Theorem 3.1. There erists do as follows. For any integer d 2 do, let X be set, let H. C [+1]x such that VC(H) d, and let m N such that m < dd/10. Then there exists subset F H and a collection IB S A(X x {+1}) of F-realizable distributions such that for any F-interpolating learning rule A and for any estimator E (X x {+1)) [0, 1] that may depend on and A,
[[(S)) LD(((()) 2
1
P PD- S
(4)
2d'/4
6
We note that some of the constants appearing in the theorem were chosen for simplicity, and may be slightly improved.
8

---

3.2 Inestimability for Nearly-Orthogonal Functions
Theorem 3.2. Let m E N, let X be a sel, and let. A (X x (+13) learning rule. Assume that A F-interpolating for a set F S {=1]x* where X' S X, F
{+1]2 be
100m² I |221 < 00, F E11111000 11/1000m and |F| = 2 +1. Then there crists a collection of
F-realizable distribulions DD C A(X" x {+11)) such that for any eslimalor function E: (X x {+1))* - -00,1 1] that may depend on DD and A,
1
PDWUD) SND T
(E(S) ((S))LD(A(S)))) 2
2 0.16.
4000m
We note that here too, the constants appearing the theorem were chosen for simplicity, and might be improved.
4 Sufficient Conditions for Estimability
In Examples 1.5 and 1.6 we saw that the constant algorithm and the memorization algorithm very estimable. These algorithms are also very stable. Indeed, they always output the same (or essentially the same) hypothesis." 11 In the other direction, Theorem 3.2 shows that certain algorithms that are very unstable, are not estimable. This suggests that stability might play an important role in determining the estimability of an algorithm.
One notion of algorithmic stability that is common in the literature is leave-onc-out stability (Bousquet & Elisseeff, 2002). However, it is casy to see that the memorization algorithm, which is estimable and is (intuitively) very stable, does not satisfy their definition of stability. Therefore, we use the following alternative definitions of algorithmic stability, which are similar to Rogers and Wagner (1978) and Kearns and Ron (1999).
Definition 4.1. Let m, k E N, m, a. 3 E 1]. Let X be a set, let A: (X x (+1))*
{+1}* be learning rule, and let D S A(X x {=1}). We say that A is (a, B, m. k) -hypothesis stable with respect to ID if
VD E D::
P
di (A(S)), o S2) S Sa 3,
SIND==
SanDa
where Dx is the marginal of D on X, (jstp( = PA~P [fx) * g(x)], and o denotes concatenation.
Definition 4.2. In the notation of Definition 4.1, we say that A is (a. 3, m, kl-loss stable with respect to DD vD E D: P Lo(A(S)))- Lo(AAS o S2)) S a 2 1 1-3. B.
Let A be a learning rule that is (an, BI, m, k)-hypothesis stable or loss stable with respect to (as in Definitions 4.1 and 4.2). Then (A. is (s an + + = Bu + 31. (...m)-unii mn)-unfforlly estimable.
Theorem 4.3. Let N and og, 30 E (0,1) such that k 2 (ollog(1//o//at)
Hence, stability is sufficient condition for estimability. We remark that it is not necessary condition. For instance, a learning rule selected at random as in Example 1.7 most likely is estimable (because has high loss for any distribution), but not hypothesis stable (since for each possible input sample, it outputs a different hypothesis that was chosen at random). To see that loss stability is also not necessary for estimability, fix a degenerate distribution DD such that D((x", 1)) = 1 for some x", and consider an algorithm A that for samples of size m outputs the constant hypothesis hy(x) 1, and for samples of size m outputs the constant hypothesis (z = O. A is perfectly estimable with respect to (D), but it is not loss stable.
One might object that Theorem 4.3 is of limited utility, because it is hard to check whether given algorithm is hypothesis stable or loss stable. Our response to this criticism is that in practice, it is quite casy to check whether an algorithm is loss (or hypothesis) stable with respect to a particular population distribution and indeed we do so in our experiments (see Section L).
"The memorization algorithm always outputs the function M(z) = -1, except that it alters h in small number of locations to fit the training set.
9

---

The process for estimating loss stability is simple: take a set S of m ii.d. labeled samples from the population distribution. Randomly choose a subset S' of size m k. Execute the learning algorithm twice, once with training set S to produce hypothesis h, and another time with training set S' to produce a hypothesis M' Use an additional validation set to estimate the difference in population loss between h and h'. Repeating this process number of times and taking an average gives a good estimate of the (m, k--loss stability. similar process can be used to estimate hypothesis stability. Simply measure the disagreement between h and h' on the validation set (note that in this case, the validation set can be unlabeled, which is an advantage when labeling data is expensive).
5 A Simple Characterization
The following definition is a variant of Definition 1.1. Such variant allows us to have simple characterization estimability in Proposition 5.2. Namely, to understand whether an algorithm is estimable with respect to a set of distributions, one can examine the quantity Ep-u(D))s~- (aar)))sssss(((((AAAAAA [var(LD(A(S)) 5)].
Definition 5.1. Let D be set of distributions and let A be a learning algorithm. We say that A is (E,m) eesttmaablll in lz with respect to D, if there exists an estimotor E such that
Ep-u ((E())(Ess))))))))))))()) (L))))))) S
We remark that for bounded loss functions, Definition 1.1 using Markov's inequality, Furthermore, although the characterization the following theorem is simple, it might provide a technical condition that will be useful for future work.
move between Definition 5.1 and
Proposition 5.2. A is (c, -estimablee in l2 with respect to ID if and only if
v = (va.))))ssso__a((/(o(o(
5) S.
Conceptually, one can think of the quantity in the case of discrete random variables as follows. A distribution D is samples uniformly from DD, and then a sample S is taken i.i.d. from D. This defines joint distribution (D,S). For every fixed sample 8;
0g = var(L =) 5) E (L E[LIS = =|)² 18=s]
where L, (D((S)) Finally, is the average v v= P[S s] U.. The same idea applics to general random variables with the appropriate modifications.
The proof of Proposition 5.2 appears in Appendix C.
Directions for Future Work
Some interesting questions for future work include:
1. Theorems 3.1 and 3.2 imply limitations for cstimability when the sample is of size S <(vV) m m respectively, where d is the VC dimension of the class of labeling functions (see Footnote 5). Is it possible to obtain similar inestimability results also for larger m??
2. Are there simple conditions that are necessary and sufficient for an algorithm to have tight generalization bounds for all distributions (as in Example 1.5)?
3. Are there simple conditions that are necessary and sufficient for a pair (A,D) of an algorithu and distribution family to have tight generalization bounds?
Acknowledgments and Disclosure of Funding
MG was supported in part by the Swiss National Science Foundation under Grant 200364. JS was supported in part by NSF CNS-2154149, an Amazon Research Award, and by Vinod Vaikuntanathan's Simons Investigator Award. TW was supported in part by the Swiss National Science Foundation under Grant 182517.
10

---

References
Abbe, E., & Sandon, C. (2020). On the universality of deep learning. Tn H. Larochelle, M. Ran- zato, R. Hadsell, M. Balcan, & H. Lin (Eds.), Advances in newral information process- ing systems (pp.
Vol. 33). Curran Associates, Inc. https:/ https://procceedings. neurips.. cc paper files paper//ppp///e// / 2020 / file <Teeffe5992b3998caaaeeeeeeee Paper.pdf
Achlioptas, D. (2003). Database-friendly random projections: Johnson Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4), 671 687. https:
/ //doi.org// /0016/00022200 (030000055 100025-4
Aminian, G., Cohen, S. N., & Szpruch, L. (2023). Mean-field analysis of generalization errors.
20..2233..110 11623 Bartlett, P. T..,& & Long, P. M. (2021). Failures of model-dependent generalization bounds for least-norm interpolation. The Journal of Machine Learning Research, 22(1), 9297-9311.
CoRR, abs/2306. 1108.11623 123. https:/ /dtp::///oorrggg// wogilorg/110 A....4855//RAAA
Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48), 30063 30070. Bassily, R., Moran, S., Nachum, I., Shafer, J., & Yehudayoff, A. (2018). Learners that use little information. Algorithmic Learning Theory, 25 55.
Blake, I. F., & Studholme, C. (2006). Properties of random matrices and applications. wwww.cs.toronto...oo hwt..:..tooooooooooooooo htt///cvs/ccodi cttss//o//g////// rrandom caaninrrprotttto pdf Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. The Journal of Machine
Unpublished report.
coodig/random
Learning Research, 2, 499-526.
Boyd, S. P., & Vandenberghe, L.. (2014). Conver optimization. Cambridge University Press. https:/ /toss//doooor/////// 10. (017/CBO978801110
Chen, Z. Cao, Y., Gu, Q. & Zhang, T. (2020). A generalized neural tangent kernel anal- ysis for two-layer neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, & H. Lin (Eds.), Advances in neural information processing systems 33: Annuall conference on neural information processing systems 2020, neurips 2020, december 6-12, 2020, virtual. https://proceedingg pproocedinggnnnurips..cm crtppssrce/pppr////////// html
/paper/////////ee / /2220 /hash/
Dziugaite, G. K., Drouin, A., Neal, B., Rajkumar, N., Caballero, E., Wang, L., Mitliagkas, I., & Roy, D. M. (2020). In search of robust measures of generalization. In H. Larochelle, M. Ranzato, Hadsoll, M. Balcan, & H. Lin (Eds.), Advances in neural information processing systems 33: Annual conference on newral information processing systems 2020, neurips 2020, december 6-12, 2020, virtual. https:/ pttpp/eedings.euurpppa. (ares008baaaa11e775999777777
paper/ /2020/222///// hash Dziugaite, G. K., Hsu, K., Gharbieh, W., Arpino, G., & Roy, D. (2021). On the role of data in pac- bayes bounds. International Conference on Artificial Intelligence and Statistics, 104-612.
bbstract.htmm
Elisseeff, A., Evgeniou, T., & Pontil, M. (2005). Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(3), 55-79. hotp://jmmrr hww.allrrrppppprss.///eoo /v6/ clissceff05a.htm
Esposito, A. R., Gastpar, M., & Issa, I. (2021). Generalization error bounds via Rényi-, f-divergences and maximal leakage. IEEE Transactions on Information Theory, 67(8), 4986 5004. https://doi.org. ort.iioorg11.1109999 10.1109/TTTT /IT 2022. 13085198
Gastpar, M., Nachum, I., Shafer, J., & Weinberger, T. (2024). Fantastic generalization measures are nowhere to be found. The 12th International Conference on Learning Representations, ICLR 2024. https://openrevice /openrviiwwwwweccooooooeeee net pdffidd=Nm..oott Grimmett, G., & Stirzaker, D. (2020). Probability and random processes. Oxford university press.
Haghifam, M., Moran, S., Roy, D. M., & Dziugiate, G. K. (2022a). Understanding general- ization via leavo-one-out conditional mutual information. 2022 IEEE International Symposium on Information Theory (ISIT), 2487-2492. https://doi.. wtw.ooog//..110000 0011006666622..983334
Haghifam, M., Moran, S., Roy, D. M., & Dziugiate, G. K. (2022b). Understanding general- ization via leave-one-out conditional mutual information. 2022 IEEE International Symposium on Information Theory (ISIT), 2487 2492.
11

---

Harutyunyan, H., Raginsky, M., Ver Steeg, G., & Galstyan, A. (2021). Information-theorett generalization bounds for black-box learning algorithms. Advances in Neural Infor- mation Processing Systems, 34,
Hellström, F., & Durisi, G. (2022). A new family of generalization bounds using samplewise evaluated cmi. Advances in Neural Information Processing Systems, 35, 10108-10121. Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 13 30. lttps::/ htttps//doi.org, 10.2307 /2282222222 Issa, I., Esposito, A. R., & Gastpar, M. (2019). Strengthened information-theoreti bounds on the generalization error. 2019 IEEE International Symposium Information Theory (ISIT), 582-586. https:/ /ttps:/ddiiiie moriiooo//10.1111 10.//1..11/IIITT.T.1 WwS.S........... 2019.884993
Issa, I., Esposito, A. R.,, & Gastpar, M. (2023). Generalization error bounds for noisy, iterative algorithms via maximal leakage. In G. Neu & L. Rosasco (Fds.). Proceedings of thirly sirth conference on learning theory (pp. /pooceddigg..mli wwt.ssmmm....rsss.... prress/vlB /v19//199//// 195/issa223a html
Vol. 195). PMLR. hitps:
Jiang, Y., Neyshabur, B., Mobahi, H., Krishnan, D., & Bengio, S. (2020). Fantastic gener- alization measures and where to find them. The 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. https:// httpss//ppeneeiew..eee..
Johnson, W. B., & Lindenstrauss, J. (1984). Extensions of Lipschitz mappings into a Hilbert space. Conference on Modern Analysis and Probability, 26, 189-206, https: //doi. org/ / 19./1...90///// /co00//o/////// 0234773440
Kearns, M. J., & Ron, D. (1999). Algorithmic stability and sanity-check bounds for leave- one-out prossvvaldationn Neural Comput., 11 (6), 1427-1453. sutps://oii.or 10.
1162/08997609930006333
Loi, Y., Jin, R.,, & Ying, Y. (2022). Stability and gencralization analysis of gradient methods for shallow neural networks. ArXiv, abs/2209, 092998. https///api.emmaniccchhooo org/ eec/ooouslD:22233000
Nagarajan, V., & Kolter, J. Z. (2019). Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32.
Negrea, J., Dziugaite, G. K., & Roy, D. (2020). In defense of uniform convergence: Gen eralization via derandomization with an application to interpolating predictors. International Conference on Machine Learning, 7263-7272
Nikolakakis, K., Haddadpour, F., Karbasi, A., & Kalogerias, D. (2023). Beyond lipschitz: Sharp genoralization and excess risk bounds for full-batch GD. The Eleventh Inter- national Conference on Learning Representations. https:/ http:////peeeeii.eeee.e// fformm? id=p0yi9K4E56b
Nishikawa, N., Suzuki, T., Nitanda, A., & Wu, D. (2022). Two-layer neural network on infinite dimensional data: Global optimization guarantee in the mean-field regime. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, & A. Oh (Eds.), Advances in neural information processing systems 35: Annual conference on newral information processing systems 2022, neurips 2022, new orleans, la, usa, november 28- december 9, 2022. http::/paaee http://pppprs.ii..co wttprrsniips.ccpppeeeee..e. happppappCCCCC files/paper/ /2222 /hash/ 22155b177c44333000bb3330000 3ccee300000ccc54000AAA5aa- Abstsss----stttt--sseee-e Conference.html
Nitanda, A., WU, D., & Suzuki, T. (2021). Particle dual averaging: Optimization of mean field neural network with global convergence rate analysis. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, & J. W. Vaughan (Eds.), Advances in neural information processing systems 34: Annual conference on neural informalion processing systems 2021, neurips 2021, december 6- 6-14, 2021, virtual (pp. 19608 19621). https:// proceedings... wwwssseerippcoo hccpppprr////// 2021 hash/ aaahh/a34eeddbbblle Abstract.
Rammal, M. R., Achille, A., Golatkar, A., Diggavi, S., & Soatto, S. (2022). On leave-one-out conditional mutual information for generalization. Advances in Neurol Information Processing Systems, 35, 10179-10190.
Rogers, W. H., & Wagner, T. J. (1978). A finite sample distribution-free performance bound for local discrimination rules. The Annals of Stalistics, 506-5 -14.
Rubinfeld, R., & Vasilyan, A. (2023). Testing distributional assumptions of learning algo- rithms. In B. Saha & R. A. Servedio (Eds.), Proceedings of the 55th annual ACM
12

---

symposium on theory of computing, STOC 2023, orlando, fl, use, june 20-23, 2023 (pp. 1643 (143).656).... ACM. https://doi.org/ 10. 035///34444665551111 Viallard, P., Emonet, R., Habrard, A., Morvant, E.,, & Zantedeschi, V. (2024). Leveraging pac-bayes theory and gibbs distributions for generalization bounds with complexity measures. In S. Dasgupta, S. Mandt, & Y. Li (Eds.), International conference on artificial intelligence and statistics, 2-4 may 2024, palau congressos, valencia, spain (pp. 3007 3015, Vol. 238). PMLR. https:/ / proceedings. mlr. press / v238/ / viallard24a.httn html
Wang, Z., & Mao, Y. (2023). Tighter information- generalization bounds from supersamples. arXiv preprint arXiv:2302.02..
Xu, A., & Raginsky, M. (2017). Information- learning algorithms. Advances in Neural Information Processing Systems, 30.
analysis of generalization capability of
Zhang, P., Teng, J., & Zhang, J. (2023). Lower generalization bounds for gd and sgd in smooth stochastic convex optimization. arXiv preprint arxiv:2303. 10758.
13

---

Technical Appendices and Supplementary Material
A Further Discussion of Related Works
A.1 Comparison to Gastpar et al. (2024)
The estimability setting studied in paper was introduced by Gastpar, Nachum, Shafer, and Weinberger 2. In Theorem 3 of their paper, they show a limitation on estimability trade-off) for algorithm-dependent bounds that is fairly abstract and involves a total variation condition that might be hard to check in many cases. In contrast, Theorems 3.1 and 3.2 involve very concrete combinatorial and geometric conditions (VC dimension, orthogonal functions). Theorems and 5 in their paper are more concrete, but they hold only for exactly orthogonal functions with strict algebraic structure (parity functions). In contrast, our Theorem 3.2 applics generally to any nearly-orthogonal function class (including classes that are exactly-orthogone as a special case).
(a learnabilty--ssimmbill
Unlike Gastpar et al. (2024), our work also presents positive results (Theorem 4.3 and Propo- sition 5.2), showing cases where generalization bounds for specific algorithms can be tight (even if, e.g., uniform convergence does not hold). The conceptual connections between estimability, stability and conditional variance appearing in those results was not present in Gastpar et al. (2024).
Finally, our techniques also differ from those of Gastpar et al. (2024). We use the Johnson Lindenstrauss lemma, our technical lemma (Lermaa H.1), and the duality of linear program- ming expanding the arsenal of tools readily available for the study of estimability.
In summary, our work builds upon the foundation laid by Gastpar et al. (2024), but we make several important contributions that go beyond their results.
A.2 Stability
In Definitions 4.1 and 4.2, we formalize simple stability conditions that guarantce the existence of tight generalization bounds, as we show in Theorem 4.3. There are many definitions of stability the literature, and it is important to appreciate that Theorem 4.3 makes a nontrivial conceptual contribution by identifying the "correct" notion of stability for understanding estimability.
Definitions 4.1 and 4.2 are similar to the definition of hypothesis stability and loss stability in Kearns and Ron (1999), Elisseefff Evgenion, and Pontil (2005), and Rogers and Wagner (1978). Lei, Jin, and Ying (2022) use another similar definition for stability and utilize it to derive generalization bounds for GD and SGD.
In contrast, our definitions of stability are also reminiscent of the replace-one stability in Bousquet and Elisseeff (2002), but as we explain in Section 4, our definitions overcome an important linitation present in their definition. In particular, the memorization algorithm (Example 1.6), which is very estimable, is not stable according to the definition of stability of Bousquet and Elisseeff (2002), but it is stable according to our definitions.
A.3 Neural Tangent Kernel and Mean-Field Theory
There are many works that study generalization using the neural tangent kernel (NTK) or mean-field theory (MFT) approach. 12 To the best of our knowledge, these works do not provide general necessary or sufficient conditions for generalization bounds be tight, which is the focus of our work. Additionally, they study generalization bounds for fairly specific families of algorithms such as gradient descent (or idealized versions thereol), while our work applies to a broader and more general class of algorithms.
E.g. Aminian et al. (2023), Chen et al. (2020), Nishikawa et al. (2022), and Nitanda et al. (2021).
We note that Theorems and 3.2 apply to learning algorithms that achieve 0 training error. Because this property is satisfied by many contemporary learning algorithms (even if the labels are random), we do not view this as significant limitation on the generality of our results. This assumption is not essential, and it could easily be relaxed in future work.
14

---

B On Extending Our Results to Randomized Algorithms
For simplicity, in this paper we focus on deterministic learning rules. However, we recognize that the topic of randomized learning algorithms is very important, sceing as most algorithms used in practice today are randomized.
The estimability framework explored in this paper can be extended to handle randomized a algorithmss as well, and in fact the original work of Gastpar et al. (2024) already contains some initial treatment of randomized algorithms.
We expect that the results presented in this paper can be extended to randomized algorithms, and that the essence of the results remains mostly unchanged.
The first step in such an extension would be to clearly define what estimability means for randomized learning algorithms. A definition that one might initially consider is one where the estimator knows the randomness used by the algorithm, and must output number that with high probability close to the true population loss of the randomized algorithm. This definition is not very interesting, because a setting in which the estimator knows the randomness used by the randomized algorithm is equivalent to the setting of a deterministic algorithm, which is already covered by the results in this paper. Nonetheless, it is good to keep this definition in mind, because it means that our results for deterministic algorithms already apply as-is to randomized algorithms (like SGD) once the randomly chosen seed is fixed, which might be a simple and satisfactory approach for many purposes (SGD with fixed random seed typically performs well for most purposes SGD with fresh randomly-chosen seed).
Perhaps the more "correct" and interesting definition of estimability for randomized learning algorithms is one where the estimator knows the training set, but does not know the randomness used by the learning algorithm, and it is required to output a number that is close with high probability to the expected population loss of the randomized algorithm when executed with this training set (where the expectation is over the randomness of the algorithm). ). In this setting, we believe the essence of our results carries through, with an important conceptual difference: using randomness, one can always engineer a learning algorithm that is estimable, essentially by adding noise to the output of the algorithm. As the noise in the algorithm's output increases, the expected 0-1 loss of the algorithm becomes closer to 1/2, and so the algorithm becomes estimable with a trivial estimator that simply always outputs the number 1/2. (With intermediate amounts of noise, a number between and 1/2 will be optimal).
Consequently, for randomized algorithms, our lower bounds in Theorems 3.1 and 3.2 can no longer be staled as absolute limitations estimability. Rather there is now trade-off between the performance of the algorithm and its estimability. As one adds more noise, the algorithm becomes more estimable, but its performance degrades. Thus, the corresponding theorems for randomized algorithm would state that no algorithm can simultaneously make good predictions for some large set of labeling functions and also be estimable.
On the other hand, the upper bound in Theorem 4.3 that states that stable algorithms are estimable remains basically unchanged for randomized algorithms.
To summarize, under a suitable definition of estimability for randomized algorithms, we expect that results would not change much, though the statement (and proof) of the lower bounds would be somewhat more complex. We leave this work to future research.
C Proof of Proposition 5.2
Proof of Proposition 5.2. The result that the minimum mean-square error (MMSE) estimator corresponds to the conditional expectation is a well-established theorem in probability theory (sce, for instance, Scction 7.9 in Grimmett and Stirzaker (2020)). For the sake of completenoss, we present a proof of this result.
We will use the following simple claim.
Claim C.1. Let Ci ..., Cki Pi. Pk IR such that Ek= P. then
15

---

k
argmin FER
pi (x - c;)² 2 Σ
Pi Cj.
1=1
The claim follows by taking the derivative of E Ps - (x ci)² with respect to a which
yields the equation:
15=12p((< a) = 0 that implies - Pic, since Σ P== 1.
The following shows that the estimator (*) E (A(((((S)) 5] is optimal and the inequality follows from Claim C.1. Let I be any estimator for A.
E BD- [(E(S) - [=(A
Σ P(S)
Σ (LO(S()))(A E(S))²
DED
E
P(DIS) - E(S))²
DED
[LD(A(())) Σ P(D)S)LD(A(S1I) 27
2
Σ P(DIS)
DED
DED
= P(D[S) (ID(A(S) ( (S))
DDE
=
-ED-U(D),. S.
- -
This means that is square loss (E, cestmmabbeee with respect to if and only if g- can achieve accuracy. It achieves such accuracy if and only if E [var(Lo(A(S)) ()) s e. This follows by the following equalities that complete the proof.
E (va((L S)] = E E (LD(A(S)) ( E|LL(A(())))) |s]
E
((D()) - (LD((A(S)) S))²
DED
P(D[S) LD(A(S)) - Σ PIDIS)LD(A(SMI)
E
DED
DED
E
P(DIS) ((()))(()))))()) ((DD)))L((4S))
DED
Ep.uUD) -
D Details for Example 1.8
For sample size m 2 d+ 10, any ERM algorithm for H. satisfies p(m) 2 0.999, meaning it learns D well, and hence (0, 10 -,0 d 10)-estimable on average. This holds because for an ERM to output the ground truth, it is clearly sulficient. that only single sample-consistent function exists in the concept class (the ground truth). Similarly, in the event that there are t > 1 campse-consistent functions, the success probability is given by 1/t due to the uniform prior over ground truth distributions. Parity functions are fully characterized by their coefficient vector [......, w.]. Since the labels are a bilinear function in the inputs æ and coefficients w, one can obtain w from m 2 linearly independent samples a; by solving the linear system of equation y Xw with design matrix X E {0, mmd More generally, X having rank d - k is equivalent to the event of having / == 2 sample-consistent functions (coefficient vectors) since every additional linearly independent row rules out half of all parity functions. Now assume X consists of all ii.d. Ber(!/) entries and y contains
16

---

the labels of all samples. The probability of zero population loss can now be obtained from the law of total probability with the probabilities of rank deficiency computed according to Corollary 2.2 in Blake and Studholme (2006).
Similar calculations show that for smaller sample sizes, any ERM for H. satisfies p(d) 2 0.61, and p(d - 1) 2 0.38. An application of Theorem in Gastpar et al. (2024) shows that there exist ERM algorithms such that for any 6 < m S d there exists a collection Dm for which the algorithm is not (0.25, 0.32, m)-estimable on average. These algorithms have an inductive bias towards subset FF S H, such that they perform well for distributions labeled by function from F, and perform poorly for target functions from the complement of F.
E Proof of Theorem 3.1
Recall the definition of nearly-orthogonal functions (Definition 2.8). The proof of Theorem uses corollary of the Johnson Lindenstrauss lemma (Theorem K.1), which states that random vectors a high dimensional space are nearly orthogonal, as follows. 14
Claim E.1. Let E (0,1/2), and let d, E N such that
n S exp((de /54).
Let Let ((==)a) be the uniform distribution over functions [d] + {=1), and consider random sequence F of functions Fi,..., Fn sampled independently from U. Then
P Froe [ Le,dd 2 0.99.
Proof of Claim E. If n there is nothing to prove, so we assume 2 2. Let R ~ U( be a x n matrix with entries in {=1} chosen independently and uniformly at random. In particular, for cach i [n], the i-th column of is vector of d numbers in {+1} chosen independently and uniformly at random. Hence, using e1..... Cn to denote the standard basis of IR", we identify the vector Re, which is the i-th column of R, with the random function Pr: [d] + {+1}.
Recall that for vectors u, V E Rd,
|| x1 = (u
U. v) = || - 2 (u, v) + 1|0122
80
(u, v) ||u| 2 + ||0113
||u 2
2
Invoking Theorem K.1 with s n, 8 = 7, V = =fe,....ee.! C R", and d, n, E as in the claim statement implies that
Vi.j [m],
1
P R-
(1- 1 Re;
1
Rej || S (1
n
(6)
vā
Hence, with probability at least 1/n0 2 1/2" 2 0.99 over the choice of F, every distinct i.j E [n] satisly
BE-uU (F()) = 7
Σ (x) DElu
= 1/4 (Re Rey)
1
(Identifying F, with Re;)
Res 123 + Re,
112
|Re; Reil13
(By Eq. (5))
2d
Re;
Re
2
v
5,
(By Eq. (6))
as desired.
1tit is also possible to prove similar claim by directly using concentration of measure (e.g., Hoeffding's inequality), without using the Johnson-Lindenstee Lindenstrauss lemma.
17

---

Proof of Theorem 3.1. Fix an H-shattered set Xa C & with cardinality [&a = d, and for Xxt), Note that the distributions Dy are H-realizable. We will show that there exists a collection D = (Df FFF that satisfies Eq. (4), where F S (=13X² is set of k = n + functions.
each f: Xa + {=1] let Dj- = U(((z,
Consider the following experiment:
1. Sample sequence of functions G = (G1..... G+) independently and uniformly at random from {=1]xx,
2. Sample a function F uniformly from G.
3. Sample sequence of points X = (X Xm) independently and uniformly random from Ns. (X is sampled independently of (G, F).)
4. For each
[m], let Y, F(X)), let -Yi..... Mn), and let s (I),, (Xm:
(Xm: (Xm: Ym)).
Let P be the joint distribution of (G, S)Y. Consider the following events:
& = =fG Le,go) } for == = 2// By Claim E.1 and the choice of k, P(E1) 2 0.99 for d large enough.
& = (I
= =m}. By Claim K.2 and the choice of m, P(E2) 2 0.99.
& = [IGs| chosen independently of F. Hence, the probability that a function G, agrees with F on the m distinct samples in X (i.e., the probability that G,(X,) F(X,) for all [m], given E2) is = 2 2-m, The functions in are chosen independently, so the number T of functions in G \ {F} that agree with F on distinct samples has binomial (k 1.p). So
= 2]. P(Es E2 2 1/e. To see this, note that each function G; E G' {F} is
distribution
P[T 1| (k- 1) p. p)--2 x)*-2
k-2
2 1-
(VD 1: 1 p2 e -P/(1-P))
= 1/e.
Let 3 = = E3. Combining the above bounds yields
P(E) = P(& Ex)
2 P(E)) P(EF)
2 P(& (2))P(() P(ET)
2 0.99 1/e 0.01 > 1/3.
By an averaging argument, this implies that there exists C {+1} such that Le,ta for e = 2/41/4 /4 and
P(Gss = 2 2|
(7)
Fix this F, and let be an F-interpolating learning rule. From the technical lemma (Lemma H.1), there exists collection of F-realizable distributions D C A(Xa {+1}) such that for any estimator I (X' - - [0, 1] that may depend on and A,
E
1
P SmDD
Po-upyl|ss [F]|= = 2]
4
SND"
1
(By Eq. (7))
2
6'
as desired.
15We choose do E N to be the universal constant such that this inequality holds for integers d 2 do and all vd/10.
18

---

F Proof of Theorem 3.2
Proof of Theorem 3.2. We take ID - (D; F} function f E F, let S ~ (Dy.).", and consider the random variable Z = Fs. We bound the expectation and variance of Z, and then show lower bound on the probability that Z E (2.3).
where Dj - U(( : I E x)). Fix
Let S = ((X1, Yi...... (Xm. Ym)) and X = [Xi...., Xmt, and let E denote the event in which X = m (i.c., S is collision-froe). For cach f E F, let z = I( E [m] : f(X,) = Y,),
so that Z = Σ EeEF Zz.
EF' Sm(D,,)m
12 E] = E
Σ Z5 E
FEF
=1+ Σ
PiViE E [m] f(X,) = Y, F]
(Zr = 1)
fer 1+1
1
1
$ 11+ 2m
1/2
+
(By Proposition 2.9)
2
1000m
S 1 1/10000 2.002.
(8)
1
E S~(D,,)m
[2 E]
2 1+ 2m
(By Proposition 2.9)
2 2
1000m
2 1 + e 11/500
(1 - x 2 e #11-))))
E
[Z2 E =E E
Σ 2j
Σ Zg
E
(~(DDo)
FEF
9EF
E
1+ Σ 21
1 Σ Z
E'
12
FEr
TET
148
98
E 1+2 Σ 2 Σ
Σ
E
FEF
fEF gEf
J+S
1+1" 341"
E 1+3 Σ 2 +
Σ
2zZg
E
PEF
(9EF((P) 549
J
1 3 (E|Z) E - 1) +
Σ
E
Z
E
(10)
{EEFW
ffg
Σ
E
E
Σ
Pl E [m] : f(x;) =xxx))==((( E
f.gEA\(83 549
1.9E((1"))
f+9
< 2mm.
(1
3
(By Claim J.1)
4
1000m
19

---

3 1000m
S 3/ 3/1000
(11)
Combining Eqs. (8) (11) yields
Var Z E E
B[Z² E] (E|Z E))
Σ 1 + 2/1000 + e3322000 - (1+e- (1+0-1/500) 2
< 1.02.
By Lemma I.1,
PIz [2,3) E] 2 1 Var[Z E
2 0.49.
2
Claim K.2 and x 2 100m² imply that P > 0.99. Hence,
PIZ [2. 2 P PiZ E (2.3) E] 2 0.99 0.49 2 0.48.
(12)
Finally, invoking our technical lemma (Lemma H.1) yiclds
1
1 4000m
> PIZ (2, 2 0.16,
P F~U(F) S~(DF))
[E(S) LD, 4
as desired.
G Proof of Theorem 4.3
Proof. (A,D) is (a, B, m.,kk,,kphpooo hy-hhhhssssss stable, then in particular (A, is also (a, 3, m, m,k)) k)- loss stable. Hence, it suffices prove the claim for the of loss stability. We construct uniform estimator E as follows. Given a sample E 2 for = (X' x (+1}), let 8 050 = S be the partition of such that S E z=-k and S2 zh. Take E(S) = Ls, (A(S:)). By the triangle inequality,
((S) - Lo((()) $ - LD
so
LD(A(S))) > = ( 0g V
P (S>D=|[E(S) - (L
-
01
< PI| Lss (A(S)))-I IDD(A())) > og]
P((LD(((SS)) - (o((()) ai
S B1 8,
where the final step follows from Hoeffding's inequality, the choice of k, and the stability of A.
H Technical Lemma for Inestimability
Lemma H.1. Let m e N, let > 0, let X be a finite set, let S {+13* such that F E Le,x and let A: (X' x (=1)"" + ++1] be an F-interpolating learning rule. For each f let D, U(((z, x X)), and for each & E N. let
Ph = P F~U(F) [|Fsl = kj. S~(PF)" m
Then for any estimator E: (X' x {+1}) - 10 that may depend on A,
PP F~U(F)
[((S) T.D. (A())) 2 S~(Dp)"
2 Σ
Pk
4
k
KE
(2
20

---

Proof. Consider the following experiment:
1. Sample sequence of points X (Xi,..., Xm) independently and uniformly at random from X.
2. Sample a function F uniformly from F, independently of X.
3. For each i [m]], let Y; F(X)), let (Yi,..., Mm), and let S
(I),. (Xmm: Xm)).
Let P be the joint distribution of F,, Fix k E (2.....,158 .IF),, and let s s= ( v1 ), (Ims Um)) E (X x (+1))"
with x= = (II...., Im) and y = (11 (y1,..., ymm such that |rg k. Denote Fs = {fi.....
Then for any i,j E [b), i J:
P(S= = s F F= fi) = P(X = x F= = fi) =P(X F = fz)
(X1F)
= =P( =
fj).
(13)
So,
P(F = = = 8) P(S = 8 F= fi) P(F = fi) P(S =)
P(S = 8 F = [1) P(F fi)
(By Eq. (13), F ~ U(F)
P(S s)
PF = 15=)).
(14)
Seeing as P(F F. S = =) = this implies that for all ie (b). P(F = S4 1 = 8) 1/k.
Because A is F-interpolating, A(s) F.. Without loss of generality, denote A(s) = f1. From FE LaN and Proposition 2.9, LD, (fy) 2 1/2 - - = 2a for all i,j E [k], i + j. Hence,
((LD)(((S) = 0 S = 8) P(F A(S) 15=))
(F, A(s) F.) (A(s) = fi)
=P(F= = f1 |5
=1/k;
(15)
and
((LD)(A(S)) 2a S 8) =P(F + A(S) 15
= P(F E
S 5=s) s)
(k: - 1)/k.
(16)
Hence, for any 17 E R,
1
P((ID,(ASS)) - 1/ 2 a S S= 2 k
(17)
We conclude that for any estimator E: (X' x (=1}) mh R
P([LD, (A(S)) - E(S) a)
2 Σ ((IL))(A(S)) - E(S) a A IFsl =
kE 1E(2....1PT)
Σ
Σ
P(ILD, -(S) a S= 8) P(S 8)
(F
Σ
Σ
P(ILDs 1n 2 S = 8) P(S = 8) HER
inf
bE (2......FF)
E
Σ
P(S s)
(By Eq. (17))
kE (2....... s: [T
= Σ
P([Fsl = k)
as desired.
21

---

I Concentration Bound via Linear Programming
Lemma 1.1. Let n E N, Umax E R. Let be a random variable taking values in [nd] such that μ = [[Z] E [2, 2 + and Var[2] I Vmax- Then PIZ E {2.3}]
Umax We prove this concentration of measure bound using the duality of linear programs (see Section 7.4.1 in Boyd and Vandenberghe, 2014 for an exposition of this approach).
and VarlZ" Var 2]. Furthermore, Piz E (2.3)] = PiZ' E {2 μ. 3 - p.l- We show a lower bound on PIZ' E (2 v. p}] across all distribution of with the above moment constraints.
Proof. Let Z' = Z μ. Z' is random variable with E|Z
Indeed, let X be random variable taking values in Var[X] S Umax such that P[X {2 3. [h] is minimal. In particular, the distribution of X is solution to the following minimization problem.
n with [[X] = 0 and
min P(X E {2 - 3. p+] Dx
s.t.
[[ = 0
Var[X] S Umax
The mininization problem can be formulated linear program with variables pa P[X = k- for each k E [n].
min P2 + P3 Dx
s.t.
21
kE[n]
Pp 2
KE(n]
Σ
(k: /1) 2 0
KE(n]
Σ RE(M)
Pk (μ1 - k) 20
E Pk (k- - 2 2
Umax
RE(M]
Vl E [n] Pk 2 0.
This linear program can be represented as
min (0. .0.
s.t.
1
-1
-1
P1
1 - 1
2 - /
11
1
Pn
(1 2
2
(n
Umax
2 0.
Recall the symmetric duality
min x
max of
s.t.
s.t.
Ax >
AT
x 2 0
y 2
22

---

Hence, the dual linear program is
max (1, -,,00, Umax) y
s.t.
1 p 1
-(1 p)2
1 -1 2 p 2
- - )1)
U1
1 -1 P
3
-3 - 11)
U/
-1
1 1 -(n n)
y 220 0.
A direct calculation shows that the vector
y" = a1,0,a,0.2).
1 4-1
1
a
1
feasible solution for the dual program for any μ [2, v2 + 1]. The value of the dual program at y" is u = 1 Umax/2. The weak duality theorem for linear programs implies that lower bound on the value of the primal problem. Hence,
min P(X (2 n4, 14) 2
This implics that Piz& E (2,3)] 2 u, as desired.
J Agreement Between Nearly-Orthogonal Functions
Claim J.1. Let > 0, let X be sel, and let S.g, h - {+1} such that (.g, e lex- Then P ( g(x) h(x)] s 32
Proof. Denote
a = P Pa)U(x) [f(x) = g(x) M(x)
b = P [f(z) # g(r) A(x)
c = PaNU(x) [f(x) = g(z) # M(x)
d = Pa-u(x))(() + g(z) * A(z)
From h3 E Lex and Proposition 2.9,
E
a + b+b P (9(z) = h(x)l <
+
2
2
a c = P [f(x) = g(x)] <
+ &
2
1
+ P M(x))
+
2
2
Adding these inequalities yields
3
38
3a + b
<
2
2
From the identity a + b+
1
38
2a < - 2
+
2
< + 3: 3, as desired.
23

---

K Miscellaneous Lemmas
The following result from Achlioptas (2003) variant of a lemma of Johnson and Linden- strauss (1984).
Theorem K.1 (Johnson Lindenstrauss). Let n, s E N, let e, O, and let C R be set with cardinality [V] n. Let d E N such that
4 d 8/22 In(n).
Let R be a d x random matris such that each entry chosen independently and uniformly at random from {+1}. Let fn R IRd be given by fn(u) (1/va) Rv. Then
1
R~U(((11jax)) VV. (1- v11 S [1 [n(v) (1 + e) -012
2
n
Claim K.2 (Converse to Birthday Paradox). Let d.m E N, and let B E (0. If
(1) d m S min { (V 3 2
then P Px~(U(<4)* [|X] m| B.
Proof. We use the incquality 1 2 c 2=1((1_0), which holds for 1.
1
2 d
Fx~ [|X] m] =
1
1
d
m- 1
k
m- 1
Σ
exp
exp
d
-
k
k
k=0
2 m-1
m²
exp
Σ
h:
2
exp
d
d
k=0
where (+) follows from S d/2. Solving exp
(
m?
d
yields the desired bound.
Thcorem K.3 (Hoeffding, 1963). Let a, b, p ER and m E N. Let Zi,..., Zm a sequence of i.i.d. real-valued random variables and let 7 m Li=1 Zi. Assume that B[Z] μ4, and for every i E [m], Fla < Z: < bj = 1. Then, for any
> 0,
-2m [b a)
Z Z - a > e) < 2cxp
L Experiments
L.1 Motivation and Setup
Here, examine if there are practical algorithms that admit loss stability even hypothesis stability with substantial numerical values. To this end, we conduct experiments over simple neural work architecture across four datasets: MNIST, FashionMNISTT, CIFAR1O, and CIFAR10 with random labels (figures 1-4, respectively). Throughout all experiments, we employ one- hidden-layer perceptrons with 512 hidden neurons. We train the models using stochastic gradient descent (SGD) with momentum factor of 0.9 and a batch size of 1000, optimizing the cross-entropy loss. For every data set, we train the models across learning rates 0.1, 0.035. and 0.01. We average all the curves over 10 random seeds (tied for the pairs of networks) and plot the standard deviation for all the curves.
16 Except for CIFAR1O, we present the results only for learning rate 0.1 and 0.01 to prevent clutter. The qualitative results are consistent across all datasets; that is, the curves of learning rate 0.035 lie between the curves of learning rate 0.1 and 0.01.
24

---

The training procedure is as follows: we train two models in tandem, starting from the same random initialization. The first model is provided with the full training set, whereas the second model has k == 100 data points removed from its training set. These points are drawn uniformly random before the beginning of the training, and fixed thereafter. After each epoch, we evaluate the training accuracy, test accuracy and hypothesis stability, L.e., the agreement between the two models (which we calculate across the test set).
We set our main focus on the agreement of the models since the most amenable way to show loss stability might be by way of proving hypothesis stability. The latter can perhaps be mathematically proven in the case of neural networks by analyzing the stability of the training dynamics under two slightly different training sets.
L.2 Results
Across all experiments, the training and test accuracy of the model pairs essentially identical throughout the training process. This suggests that at least simple models are loss stable across vision tasks. In order to reduce visual clutter, we hence only plot training and test accuracy of the first model (which has access to the full training set), respectively.
We observe higher agreement for simpler data sets and smaller learning rates. For example, the learning rate has a considerable effect on agreement for CIFAR10 (= 0.65 for learning rate 0.1 vs R 0.8 for learning rate 0.01).
The key takeaway from Figures through 4 is that the agreement. is consistently higher than the test accuracy. This relationship ensures that when applying the estimation procedure outlined in Theorem 4.3, we can avoid vacuous predictions of perfect accuracy. In the scenarios presented, the estimated accuracy will always be bounded away from 1, as it can be expressed test error + agreement). For instance, with a learning rate of 0.01, the maximum estimated accuracies are: 98% for MNIST (compared to 97.5% test accuracy), 90% for FashionMNIST (87% test accuracy), 72% for CIFAR10 (32% test accuracy), and 65% for CIFAR10 with random labels (10% test accuracy). These results illustrate a strong correlation between stability estimation and data complexity.
We repeat the same experiments, modifying the width of the hidden layer to investigate its impact stability. The results, summarized in Table 1, reveal strong positíve correlation between network width and stability. This effect is particularly pronounced for more complex tasks, such as CIFAR10 and CIFARIO with random labels. For instance, in the CIFAR10 random labels setting with a learning rate of 0.01, increasing the width from 256 to 1024 neurons improves agreement from 32% 50%, highlighting the stabilizing effect of greater network width.
25

---

Accuracy and Agreement by Learning
1.00
0.95
Accuracy Agreementt
0.90
Learning train accuracy test accuracy agreement
Rate train accuracy accuracy
0.75
agreement
Epochs
Figure MNIST
Accuracy and Agreement Learning Rate
1.00
0.95
0.90
Accuracy Agreement
Learning Rate 0.1
Learning Rate 0.01 accuracy
0.70
accuracy Lest accuracy agreement
Lest accuracy agreement
0.65
20
60
80
100
Epochs
Figure 2: MNSH
26

---

Accuracy and Agreement by Learning Rate
1.0
0.9
Accuracy Agrremment
0.7
0.5
Learning Rate
Learning Rate 0.035 cen train accuracy accuracy agreement
Learning Rate 0.03
train accuracy accuracy
train accuracy
accuracy agreement
0.3
agreement
20
40
60
100
Epochs
Figure 3: CIFAR10
Accuracy and Agreement by Learning Rate
1.0
Accuraty Agruementt
0.6
0.4
Learning Rate ...... train accuracy accuracy agreement
Learning 0.03
.....
train accuracy accuracy agreement
50
75
100
125
150
175
200
Epochs
Figure 4: CIFAR10 with random labels
27

---

MNIST
FMNIST
CIFARIO
CIFARIO RAND
#N
Ir
Agree
#N
Ir
Agrec
#N
Ir
Agree
#N
Ir
Agree
256
0.1
99%
256
0.1
92%
256
0.1
62%
256
0.1
21%
256
0.01
99.5%
256
0.01
97%
256
0.01
71%
256
0.01
32%
512
0.1
99%
512
0.1
94%
512
0.1
67%
512
0.1
30%
512
0.01
99.5%
512
0.01
97%
512
0.01
80%
512
0.01
41%
1024
0.1
99%
1024
0.1
95%
1024
0.1
76%
1024
0.1
39%
1024
0.01
99.5%
1024
0.01
98%
1024
0.01
85%
1024
0.01
50%
Table 1: Agreement percentages across datasets with varying number of neurons in the
hidden layer (#N) and learning rates (Ir). The setup the same in L.1 except for the number of training epochs, which is {50, 150, 150, 300} for (MNIST, FMNIST, CIFAR10, CIFAR10 random), respectively. scenarios where agreement has not yet reached saturation, agreement is positively correlated with the width of the network.
28

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, rescarch ethics, and socictal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes] [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper the relevant information is Not Available.
Please provide short (1 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and ils final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their ovaluation. While "[Yes] is generally preferable to *[No] it is perfectly acceptable to answer '[No] provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive' or "we were unable to find the license for the dataset we used"). In general, answering "[No] or '[NA] is not grounds for rejection. While the questions are phrased in a binary way, we acknowledge that the true answer often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This is a theory paper and we present all our results informally for better readability before the formal results in later sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: no limitations.
Guidelines:
29

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g,, independence assumplions, noiseless settings, model well-specfficatonn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach only tested few datascts with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
Tf applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
All proofs are in the appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs the paper should numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims
30

---

and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We run simple experiments and we explicitly mention all hyperparamcters to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e-g.; the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
cither make possible for others to replicate the model
While NeurIPS does not require relcasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily clear how to reproduce that algorithm.
algorithm, the paper should make it
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g,, large language model), then there should either be a way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental matorial?
Answer: [No]
Justification: the experiments are elementary; nevertheless, if reviewers wish to see the code, we provide it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurTPS code and data submission guidelines (https:/nnips.cc/pubii) guides/Codde Saleess/CoodSSmmmmiiooooolll for more details.
31

---

While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e-g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines /gte//ggdds////ee Saaidd/s/CodSubmmsiiiooooo
(https::/nips.cc/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw dala, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much ion possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyperparametors, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
All the experimental details appear in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance the experiments?
Answer:
[Yes]
Justification: There are error bars in all our figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/tess /tsst split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar the standard deviation or the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported tables or plots, The authors should explain in the text how they calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Answer: [No]
Justification:
Very simple experiments executed on laplop, special resources needed.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpss//eeupppccc//// htt///bb/////hhhuuuuieeeees
Answer: [Yes]
Justification: This is theory paper so there are no ethical concerns for potential harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification:
Purely thcoretical work.
Guidelines:
The answer NA means that there is societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
33

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance) fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, there a direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe saleguards that have been put place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA].
Justification:
Purely theoretical work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions access the model or implementing safety filters.
Datascts that have been scraped from the Internet could pose safcty risks. The authors should describe how they avoided relcasing unsafe images.
We recognize that providing effective sa safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA].
Justification:
No external resources used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The hoth should state which version of the asset used and, if possible, include a URL.
34

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datascts, paperswithcodc.com, com/datasots datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
Tf this information is not available online, the authors are encouraged to reach out the assct's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documen- lation provided alongside the assets?
Answer: [NA].
Justification:
No new assets introduced.
Guidelines:
The answer NA mcans that the paper does not release new assets.
Researchers should communicate the details of the dataset //////////ooo//// as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
This is theory paper with no crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Docs the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/reviens based on the requirements of your country or institution) were obtained?
Answer: [NA]
35

---

Justification:
This is theory paper with no crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiv- alent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration not required.
Answer: [NA]
Justification:
No use of LLMs as mentioned above.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to LLM policy (https:/ httpss//eerripccc/eee// /eaec//ooofeees///ee /205)/LLMM) for what should or should not be described.
36


Reviews:
[{"review_id": "AYmJLFEGSY", "reviewer": "Reviewer_14LB", "summary": "The paper is concerned with deriving *tight* generalization bounds for learning algorithms that are *non-uniform* w.r.t. to distribution — that is, the authors study for which pairs of algorithms and sets of distributions, the algorithm has a tight generalization bound (on the specified distributions). The core studied property to achieve this goal is that of *estimability* of an algorithm $\\mathcal{A}$, first defined by (Gastpar et al; 2024), that roughly means that there exists an $\\varepsilon$-accurate $\\delta$-confident estimator for the population loss achieved by $\\mathcal{A}$, using $m$-samples from the distribution belonging to the specified set of distributions. A simple immediate consequence of this definition is that all *estimable* algorithms that satisfy some generalization bound will satisfy it in $\\varepsilon$-tight manner with $\\delta$ confidence.\n\nThe main contribution that sets this paper apart from existing work is that it estabilshes connections between *estimability* and standard concepts in statistical learning theory, such as the variance of estimator, loss-stability, VC dimension. They also provide several simple examples that delve into what is estimability and how it is very different from learnability. The paper is a very interesting read and will be of interest to the community. I do have some remarks regarding, what is in my opinion, an unusual organization.", "questions": "* Can you compare your approach to proving non-uniform generalization bounds directly? I assume this would not yield tightness, but possible could lead to new smaller bounds (that might or might not be tight).\n* In Line 85 you state: “And if the number of samples is too small to allow learning, some\ninteresting algorithms might nonetheless perform well on a certain subset of distributions and also be very estimable”. Is this technically correct statement? I thought estimability is equal to having tight bounds, shouldn’t then the sentence state that “\\ldots some interesting algorithms might nonetheless perform well on a certain subset of distributions because they are very estimable on that distribution subset.“ \n* In Line 124, I would suggest to remove the tilde as a sign of approximation and specify the number $0.16$.\n* In Line 144 you say “necessarily very weak for many distributions”. Could you please specify in what sense weak? I assume it means that no bound can be better than $1/4$-tight, correct?\n* In Line 158 you state that: ”Seeing as there are many definitions of stability in the literature, Theorem 4.3 makes a nontrivial conceptual contribution by identifying the “correct” notion of stability for under-standing estimability”. Without pointing to a later argument made in Sec 4 (which indirectly mentions the memorization Example 1.6), this reads as very strong statement. I think it would be good to back this statement here a bit more, or perhaps leave it for later.\n* In Line 216: “Hence, by Markov’s inequality, 99% of learning rules ...“ where is the 99\\% coming from? Is this in the theorem?\n* l321: “using a similiar technique” — You mean that if you use similiar technique as in Theorem 3.1 you will get 1/6 instead of 0.16? If you want to keep this statement, I would suggest specifying what is the technique based on (or perhaps just apply it and state Theorem 3.2 with the better result).\n* Definition 4.1 -> What is the notation of $S_1\\circ S_2$? I cannot find it introduced anywhere, is this the union of the sets?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: The paper presents very interesting results, which significantly extend the previous results on estimability, the proofs in the appendices appear to be correct from a quick read through. \n\nWeaknesses:\nIn my subjective opinion, the presentation of the paper would benefit from a better organization of the text. Here are some of my observations that I hope might be helpful:\n\nAt the moment the majority of the paper is an introduction giving informal results (esp Sec 1.3 and 1.4), which takes 7 pages. On one hand, this makes the results easier to understand, but on the other hand, makes the reader always searching in the appendices and Sec 2 and 3 for concrete details. Most of the actual theory results are presented on 1.5 pages at the end (Sec 2 and 3). The actual Theorem 3.1 and 3.2 are not too difficult to understand in the full statement — It might be worth a though of trying to shorten the informal Sec 1 significantly and instead present more important details in Sec 2 and 3. For example, I find the presentation of “Fact C.2” very brief and I think it would deserve more explanation in the main text.\n\nI would also very strongly suggest to present “Facts” instead as “Theorems”, “Lemmas”, “Propositions”, “Corollaries”, or “Remarks” — I know some of these are simple consequences of definitions but still. Another remark I have is that there is actually quite a bit of important detail in the appendix that is not mentioned in the paper at all, for example the comparison with Gastpar (2024) et al. or the numerical experiments. There is also no concluding discussion, which might be due to lack of space, but would be very useful to have in this kind of paper to have some hints about interesting future directions etc.\n\nOverall, I really like this paper and found it a fascinating read, but the organization feels rushed. I trust the authors to know the best way to improve it (e.g. the decision about the length of informal/formal presentation of the main results)", "was_revised": true, "final_justification": "I decided to keep my score. I really like the paper and found it an original and interesting read. I have minor remarks regarding the clarity of organization of the paper and the fact that the topic is non-standard might make the contribution less clear-cut. Overall, I am slightly leaning towards accepting the paper.", "rebuttal": "Thank you for your thoughtful suggestions, which closely engage with important considerations we had while structuring our presentation.\n\n--- \n\n**Presentation of the paper**\n\nThe current version of the paper is informed by our previous experiences presenting this work. Unfortunately, the topic of estimability appears to meet with an unusually large amount of confusion, misunderstandings, and misconceptions. Readers often conflate learnability, generalization, and estimability, and this leads them to variously insist that all our results are obviously true and are already known, or are obviously false and contradict known results, etc. For instance, some readers claim that their favorite generalization bound is universally tight for all algorithms and all distributions (which is provably false), while others claim that classic no-free-lunch theorems have already shown long ago that generalization bounds cannot be tight for all algorithms and distributions (also untrue).\n\nAs a consequence, we have chosen to provide a very careful and methodical introduction that emphasizes the basic concepts and questions. We also included Section 1.2 (“learnability and estimability are not the same”), and lots of examples in Section 1.4. We find that this reduces (but does not eliminate) the confusion about the basic questions and value of our work, and increases the number of people who understand that estimability is an interesting and important topic of study that is not subsumed by basic existing results (like the VC theorem, etc.). This is a precondition for readers to be willing to listen to and engage with our specific results.\n\n---\n\n >Renaming “Facts” to “Theorems”, “Lemmas”, “Propositions”, “Corollaries”, or “Remarks”\n\nThank you for this suggestion, we can rename those to Propositions/Theorems.\n\n---\n\n> Comparison with Gastpar (2024) et al., the numerical experiments, concluding discussion.\n\nWe appreciate this suggestion and will add parts of the comparison to Gastpar et al. and a short discussion of limitations and open problems in the camera-ready version, for which we will have one extra page. Among the questions we plan to include:\n* For VC classes, can the negative results of Theorems 3.1 and 3.2 be extended beyond $d^0.5$?\n* A characterization of algorithms that admit distribution-free tight generalization bounds (such as the memorization algorithm). \n* What combined properties of an algorithm and a distribution family admit tight generalization bounds?\n\n---\n\n# Questions\n\n> Can you compare your approach to proving non-uniform generalization bounds directly?\n\n\nWe don’t quite see a connection between our work and non-uniform generalization bounds. Could you please elaborate more, and then maybe things will click for us?\n\n---\n\n> “I thought estimability is equal to having tight bounds”\n \nThis is correct. By the algorithm $A$ “performing well”, we mean that it learns well (across some subset $\\mathbb D$), not that some associated generalization bound is tight (across $\\mathbb D$), which you perhaps had in mind? Could you please clarify this for us? \n\n---\n\n>“\\ldots some interesting algorithms might nonetheless perform well on a certain subset of distributions because they are very estimable on that distribution subset.“\n\nThis is incorrect. Algorithms can be very estimable but can perform poorly across many or all scenarios. See the memorization example, which is globally estimable yet performs badly on all distributions except ones that are close to the zero function; see also Example 1.7: the algorithms we draw randomly are perfectly estimable yet perform poorly across all scenarios.\n\n---\n\n> In Line 124, I would suggest to remove the tilde as a sign of approximation and specify the number.\n\nWe can change this to the more conservative $0.16$ for the revised version.\n\n---\n\n> In Line 144 you say “necessarily very weak for many distributions”. Could you please specify in what sense weak? I assume it means that no bound can be better than $\\varepsilon$-tight, correct?\n\n\nYes, this is correct, But moreover, this holds for large $\\varepsilon$, namely, at least $1/4-o(1)$.\n\n---\n\n> Line 158: “correct” notion of stability for understanding estimability”.\n\nNote that we do point to Sec. 4 in the sentence right after (l. 161). We can change it and point to Sec. 4 already at the end of sentence from l. 158 to make things more clear.\n\n---\n\n> Line 216: “Hence, by Markov’s inequality, 99% of learning rules [...]“ \n\nDefine $I_{A,f,S} = \\mathbf{1}[|L\\_{\\mathcal{D}_f}(A(S)) - \\frac{1}{2}| \\geq \\varepsilon]$ and $P_A = \\mathbb{E}\\_{f, S}[I\\_{A,f,S}]$ where $\\mathbf{1}(\\cdot)$ is the indicator function. Then, by assumption $\\mathbb{E}\\_A[P_A] \\leq 2e^{-2d\\varepsilon^2}$ and by Markov's Inequality $\\mathbb{P}_A(P_A \\geq 200e^{-2d\\varepsilon^2}) \\leq \\frac{1}{100}$.\n\n---\n\n> l321: “using a similiar technique” “You mean that if you use similiar technique as in Theorem 3.1 you will get 1/6 instead of 0.16?” \n\nThis is correct. In eq. 12 and below (see the appendix of the full paper), we consider for simplicity the event $\\{Z \\in \\{2,3\\}\\}$ (where $Z$ is the number of consistent hypotheses), already yielding $0.16$. However, we could have invoked Lemma H.1 with all $\\mathbb P(\\{Z = k\\})$ for all $k \\ge 2$ which would give the only slightly larger $1/6$. We will add a note at the end of appendix F for clarification.\n\n---\n\n> Definition 4.1 -> What is the notation of $S_1 \\circ S_2$? I cannot find it introduced anywhere, is this the union of the sets?\n\n\nThis means concatenation, see definition in l. 337. Note that a set union would not account for duplicates amongst $S_1, S_2$.\n\n---"}, {"review_id": "H2762zqPhZ", "reviewer": "Reviewer_o2fY", "summary": "This paper investigates the conditions under which a learning algorithm A admits tight generalization bounds. It introduces the concept of \"estimability\": a learning algorithm A is estimable if there exists an estimator E such that, with high probability, \n|E(S) - L_D(A(S))| ≤ epsilon.\n\nThe paper provides several negative results showing when tight bounds cannot exist. Theorems 3.1 and 3.2 show that algorithms with \"inductive biases\" toward subsets of VC classes with the number of samples smaller than sqrt(d)/10 or toward nearly-orthogonal functions do not admit tight generalization guarantees. \n\nOn the positive side, the authors show that stable algorithms are estimable (Theorem 4.3), providing a sufficient condition for when tight bounds can exist. They also provide a simple characterization linking estimability directly to the conditional variance of the algorithm's loss, stating that an algorithm is estimable if and only if E[Var(L_D(A(S))|S)] ≤epsilon", "questions": "see above", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is actually about empirical generalization bounds, i.e., ones that can be evaluated knowing only the training data rather than relying on unknown constants/functionals of the data distribution. This makes the results more practically relevant. As a result, it seems overparameterization will rely on distributional properties. One question is that the celebrated result of Bartlett et al already shows that one needs to have a control on covariance matrix of the data distribution in order to reason about benign overfitting. I think it is indeed connected to this paper. Indeed, the assumption of loss stability is a distributional assumption. One question is how does the sufficient condition compare to other parts of the paper? Is that true that verifying E[Var(L_D(A(S))|S)] ≤ epsilon requires the distributional knowledge?\n\nOne section that is missing is open problems. I think posing questions like the required number of samples to estimate the generalization gap, whether the gap between the two negative results can be closed, or whether distribution-free sufficient conditions exist would strengthen the paper.\n\nAnother line of related work is testable learning. In this line of work, the goal is to bridge the gap between learning on particular distribution and worst-case perspective in PAC learning. It would be nice to include a discussion on this line of work.\nGollakota, Aravind, Adam R. Klivans, and Pravesh K. Kothari. \"A moment-matching approach to testable learning and a new characterization of rademacher complexity.\" Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023.\n\nIn general, I think this paper is interesting and has some important findings.", "was_revised": true, "final_justification": "My view on the paper is still the same. I think they frame an interesting questions and the results are interesting.", "rebuttal": "We appreciate your positive outlook on our paper and your insightful comments!\n\n---\n\n> “This paper is actually about empirical generalization bounds… As a result, it seems overparameterization will rely on distributional properties.”\n\nWe agree with this interpretation. Our focus is indeed on empirical generalization bounds, i.e., bounds that can be computed based solely on the training data, which makes the notion of estimability directly applicable in practice. Our results show that tight empirical generalization necessarily requires assumptions about the distribution, just as benign overfitting does, as in your comment below.\n\n---\n\n>“The celebrated result of Bartlett et al. already shows that one needs to control the covariance matrix... I think it is indeed connected to this paper.”\n\n\nWe agree that there is a conceptual connection. The result of Bartlett et al. establishes that benign overfitting in linear regression with Gaussian covariates requires strong control over the data covariance. While their setting is restricted to linear regression over infinite-dimensional Gaussian data, they do speculate on extensions to neural networks in Section 4 of their paper. It remains unclear whether such covariance control is necessary for understanding generalization in deep learning (or other overparametrized models), but their results, like ours, emphasize the importance of distributional assumptions for achieving tight generalization bounds. We will mention this connection in our paper.\n\n---\n\n>“Indeed, the assumption of loss stability is a distributional assumption.”\n\nThis is only partially accurate. Loss stability, as used in our paper, is a property of a particular (algorithm, set of distributions) pair. It is not purely a distributional assumption. For example, fixing a restricted class of distributions, some algorithms may exhibit stability while others do not. Notably, our paper includes an example, the memorization algorithm, that is estimable and exhibits stability uniformly across all distributions.\n\n---\n\n> “How does the sufficient condition compare to other parts of the paper? Is it true that verifying \\mathbb{E}[\\operatorname{Var}(L_D(A(S)) \\mid S)] \\leq \\varepsilon requires distributional knowledge?”\n\nYes, the variance-based characterization involves an expectation over a prespecified collection of distributions, one that is assumed to reflect prior knowledge about the problem setting (e.g., Gaussianity, bounded support, etc). The goal is not to be distribution-free, but to identify for a given algorithm what distributional conditions admit tight empirical bounds.\n\n---\n\n>“One section that is missing is open problems.”\n\nWe appreciate this suggestion and will add a short discussion of open problems. Among the questions we plan to include:\n* For VC classes, can the negative results of Theorems 3.1 and 3.2 be extended beyond d^0.5?\n* A characterization of algorithms that admit distribution-free tight generalization bounds (such as the memorization algorithm). \n* What combined properties of an algorithm and a distribution family admit tight generalization bounds?\n\n---\n\n>“Another line of related work is testable learning... It would be nice to include a discussion.”\n\nThe paper you suggested may relate nicely to our work, and maybe some future directions. Our results discuss under what distributional assumptions tight generalization bounds exist, and their work might help test/validate whether such assumptions hold. It is interesting to see if the two perspectives can be combined! We will mention this in our paper."}, {"review_id": "ORmtt3yyH4", "reviewer": "Reviewer_cuUd", "summary": "This work addresses the question of *estimability* of learning algorithms, i.e. for which learning algorithms there may exist an estimator that is close to the population risk with high probability. It presents conditions that preclude the existence of generalization bounds for certain interpolating algorithms, and sufficient conditions for estimability, in terms of the algorithm's *stability*.", "questions": "Can you give some intuition around Remark 1.3? It seems to make a seemingly strong claim without any justification.\n\n**Suggestions:**\n \nThe paper is reasonably self-contained, but the ordering of sections needs to be improved. Particularly, the notation in Section 2 needs to come before Section 1.1, else it becomes very hard to comprehend there onwards. Section 1.5 on related works also needs to be moved up, maybe right after Section 1.1. I am also not sure why the informal and formal versions of the theorems are both included in the main text &ndash; with Section 2 moved up, it should be sufficient to just keep the formal forms of the theorems (perhaps with informal descriptions alongside).\n \nThe abstract should include what is meant by stability of algorithms, because without that, it is hard to understand what the results are about &ndash; something like *loss-instability* would be good. The abstract also mentions that the paper is concluded with a discussion relating the existence of tight bounds with variance of algorithm's loss. That's not the case for this submission &ndash; the relevant discussion is at the end of Section 1.3. Kindly amend the abstract to accurately indicate the location of this discussion.\n \nFact C.2, as in the main text, is not at all clear, particularly what the variance is with respect to. Reading the supplementary material, my understanding is that the sampling process is $\\mathcal{D}\\sim\\mathbb{D} \\rightarrow S\\sim \\mathcal{D}^m$, and the expectation is w.r.t. marginal over $S$ and variance w.r.t. $\\mathcal{D}|S$; correct me if I'm wrong. Please clarify that.\n \nI think there are some inaccuracies in Example 1.4. Specifically, $T\\sim U(\\mathcal{X})^{m^2}$ implies sampling with replacement, as does Claim K.2, which uses a similar notation (also the reference to Birthday Paradox). However, the proof of Claim K.2 seems to assume a set of $k$ ($=m^2$ in Example 1.4) *distinct* points, i.e. sampling without replacement. This can be easily fixed by considering sampling $T$ without replacement, and fixing the notations; I don't see the example breaking down with this change. In Example 1.4, there is also a mention of $L_{\\mathcal{D}}(A(S)) = \\mathcal{D}_{\\mathcal{X}}(\\{x_1, \\ldots, x_m\\})$, which is the case under $0/1$ loss, as is also assumed in some other places, but is not mentioned anywhere before Definition 2.3.\n \nIn Example 1.6, I don't think \"$A$ always has $0$ empirical loss\", because the definition of the outputted hypothesis seems to imply that for inputs with *unique labels*, we have the hypothesis memorizing the label, but for those with non-unique labels, i.e. $(x,-1), (x,+1) \\in S$, the hypothesis predicts $-1$. For such inputs, we will have non-zero empirical risk. I don't see any distributional assumptions precluding such training sets.\n \n**Typos:**\n \nIn Fact 1.2, my understanding is that if $(A, \\mathbb{D})$ is $(\\epsilon, \\ldots)$-estimable, then the generalization bound is $2\\epsilon$-tight, *not* $\\epsilon$-tight.\n \nIn Example 1.6, first condition can omit \"$\\exists y:$\" part since that is understood.\n \nIn Example 1.7, the description of the algorithm is mentioned twice consecutively: 1. \"consider a mapping $A$ chosen uniformly from the set $\\mathcal{A}$\", and 2. \"$A(S)$ is a function that was chosen uniformly from $\\mathcal{F}$\".", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**  Strengths **\n \nThis work addresses an important challenge in understanding generalization and deriving generalization bounds, an area where progress has been slow in recent years &ndash; particularly for neural networks. The paper is well-written with the examples in Section 1.4 covering various scenarios, highlighting the nuanced differences between learnability and estimability. The theorems presented are novel, to the best of my knowledge, and have a fairly general scope.\n \n** Weaknesses **\n \nSince the authors repeatedly emphasize the case of deep learning, there should be a discussion dedicated to the hypothesis class parameterized by NNs (eg. their VC dimension) and of gradient descent (and, perhaps, other related optimization algorithms); as for the former, I would like to see Appendix A.3 in the main text. There should also be a discussion on how the theorems apply to deep learning, even if in a weak sense, as near line 517 discussing other works. Related to deep learning, I think the paragraph starting near line 162 means to discuss stability of *gradient descent* (and variants), since that is the algorithm, while the neural network parameterizes the hypothesis class.\n \nOne concern I have is that Theorems 3.1 and 3.2 are not sufficiently general, unlike Theorem 4.3. I'm not even sure what the applications of these theorems are.\n \nIt is strange that the authors couldn't think of any limitations of their work; I would urge the authors to add a paragraph on the same. Given the slow progress in this research area in recent areas, I think adding some future directions, which I am sure are plenty, would be helpful for the community.", "was_revised": true, "final_justification": "authors answered all my concerns", "rebuttal": "# General\n\nWe are grateful for your positive feedback and the constructive suggestions provided. We have found your comments very valuable in refining our paper.\n\n---\n\n# Weaknesses\n\n> Since the authors repeatedly emphasize the case of deep learning, there should be a discussion dedicated to the hypothesis class parameterized by NNs (eg. their VC dimension) and of gradient descent (and, perhaps, other related optimization algorithms); \n\nFor lower bounds on the VC dimension of some deep neural network architectures one could for example consult [1]. Such bounds together with our Theorem 3.1 imply the existence of some optimizers for which any generalization bound must be loose across many distributions (see our discussion in lines 117-119).\n\nSimilarly, Theorem 3.2 has direct implications for NNs trained with SGD, provided that we know that this algorithm interpolates some class $\\mathcal F$ which is $\\varepsilon$-almost orthogonal. As mentioned in our footnote 6, there are settings for which this is provably the case.\n\nAs one can see, the applicability to deep learning with SGD hinges on the knowledge about which functions SGD $\\mathcal F$-interpolates. Understanding the behavior of SGD is an active field of research and is beyond the scope of the current paper.\n\n> [...] as for the former, I would like to see Appendix A.3 in the main text.\n \nThank you for your suggestion. We will try to include more details about these works in the main text of the camera-ready version, if space permits.\n\n> There should also be a discussion on how the theorems apply to deep learning, even if in a weak sense, as near line 517 discussing other works. \n\nWe refer to this in line 143. If one derives a new generalization bound for neural networks, the very least that needs to be verified for it to be non-vacuous is to check either of the following items.\n\n1. Exclude in advance all families of distributions with nearly-orthogonal labeling functions, and use this fact in the derivation of the generalization bound.\n2. Mathematically show that the algorithm is not biased towards any set of nearly-\northogonal functions.\n\n> Related to deep learning, I think the paragraph starting near line 162 means to discuss stability of gradient descent (and variants) [...]\n\nThanks for pointing this out. We mean neural networks trained with standard optimizers (e.g. SGD,ADAM,…).\n\n> One concern I have is that Theorems 3.1 and 3.2 are not sufficiently general, unlike Theorem 4.3. I'm not even sure what the applications of these theorems are.\n\nTheorems 3.1 and 3.2 can be instantiated so that one can rule out the existence of tight generalization bounds in many scenarios encountered in practical machine learning. As we explain in our paper, on line 143. See our above discussion on application to deep learning.\n\n> Limitations\n\nWe appreciate this suggestion and will add a discussion of limitations and open problems in the camera-ready version, for which we will have one extra page. Among the questions we plan to include:\nFor VC classes, can the negative results of Theorems 3.1 and 3.2 be extended beyond $d^{0.5}$?\nA characterization of algorithms that admit distribution-free tight generalization bounds (such as the memorization algorithm). \nWhat combined properties of an algorithm and a distribution family admit tight generalization bounds?\n\n---\n\n# Questions\n\n> Can you give some intuition around Remark 1.3? It seems to make a seemingly strong claim without any justification.\n\nThis is a simple consequence of the fact that binary classification is a special case of both regression and multi-class classification. Note that since our Theorems 3.1 and 3.2 are negative results, proving them for the special case (binary classification) in particular implies the same negative results for the more general cases.\n\n> Ordering of sections needs to be improved. Particularly, the notation in Section 2 needs to come before Section 1.1, else it becomes very hard to comprehend there onwards. Section 1.5 on related works also needs to be moved up, maybe right after Section 1.1. \n\nThank you for the suggestion. We understand your concern, but we feel that placing the full technical preliminaries section early on would disrupt the narrative flow. Introducing concepts gradually, alongside motivating examples, before formalizing definitions allows us to better engage the reader and build intuition. We hope this structural choice is not a significant issue, as it does not affect the core content of the paper. That said, we’d be glad to revisit the paper’s organization during the discussion period to find a structure that best serves the reader. We welcome your thoughts on this!\n\n> I am also not sure why the informal and formal versions of the theorems are both included in the main text – with Section 2 moved up, it should be sufficient to just keep the formal forms of the theorems (perhaps with informal descriptions alongside).\n\n\n> The abstract should include what is meant by stability of algorithms [...]\n\nWe will change in line 7 stable -> loss-stable\n\n> The abstract also mentions that the paper is concluded with a discussion relating the existence of tight bounds with variance of algorithm's loss. That's not the case for this submission [...]\n\nThank you for catching this, will correct this.\n\n> Fact C.2, as in the main text, is not at all clear, particularly what the variance is with respect to. [...]\n\nYou are correct about the sampling process. We will make this more clear in the revision.\n\n> I think there are some inaccuracies in Example 1.4. [...]\n\nNote that $\\mathcal X$ is the interval $[0,1]$, hence $T$ contains all distinct points almost surely. You are technically correct with mentioning collisions but we think that it is better to suppress the “almost surely” in this non-technical part of the paper.\n\n> In Example 1.4 and assumed $0-1$ loss\n\nThanks for catching this, you we will add the missing assumption of $0-1$ loss.\n\n> Example 1.6 and unique labels\n\nThank you for catching this. We had in mind the setting where the labels are deterministic given the input $x$, we will add this.\n\nTypos:\n\n> In Fact 1.2, my understanding is that if $(A, \\mathbb{D})$ is $(\\epsilon, \\ldots)$-estimable, then the generalization bound is $2\\epsilon$-tight, not $\\epsilon$-tight.\n\nThis is incorrect, perhaps you had in mind the case where on the right side of (3) there can also be a $+ \\varepsilon$, which we do not allow (see (1)).\n\n---\n\n# References\n\n[1] Harvey, N., Liaw, C. & Mehrabian, A.. (2017): Nearly-tight VC-dimension bounds for piecewise linear neural networks. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1064-1068"}, {"review_id": "S6hHYUlkGN", "reviewer": "Reviewer_9bW1", "summary": "This paper study the tight generalization bound under the definition 'Estimability'. And give some examples, the conditions lead to estimability and preclude estimability.", "questions": "See weakness. \n\nI would like the author to further explain the significance and meaning of these theorems and how these theorems can guide us in determining which algorithms have tight generalization bounds?", "limitations": "There is no section 'conculsion and limitation' in the paper, but there is no moral issue in this article.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "(1): $I\\ think\\ the\\ writing\\ of\\ this\\ paper\\ is\\ bad.$ The introduction is nearly 7 pages long, while the main text is hastily concluded in less than 3 pages, to the point that the experiment had to be placed in the appendix. As an article dominated by theory, I think the author has used too much space to informally present the theoretical results.  Additionally, please define the symbols before using them, such as $U(D)$.\n\n(2): $I\\ cannot\\ agree\\ with\\ the\\ author\\ on\\ the\\ significance\\ of\\ the\\ theorems\\ presented.$ \n\n$Theorem\\ 3.1\\ and\\ 3.2$: In the theorem, the reason for such a lower bound is mainly due to the choice of the distribution collection $D$, and it has nothing to do with the properties of the algorithm itself. Whether the algorithm is SGD, memorizaiton or something else, this lower bound necessarily exists due to the choice of the distribution collection $D$. The title of the article is \"Which Algorithms Have Tight Generalization Bounds?\", which clearly does not match the meaning expressed by this theorem. \n\nMoreover,  the theorem requires the restriction of the number of samples $m$, which further limits the significance of the theorem. It is clear that when the number of samples is small, the generalization performance of the algorithm on complex distributions will not be good, making the conclusion of the theorem somewhat obvious. When the number of samples is large, it is evident that this lower bound will not hold. And the author also does not further discuss the potential impact of $m$ on various algorithms.\n\nIn summary, the establishment of these two theorems primarily relies on factors external to the algorithms themselves, which does not align with the previous examples and the main theme of this paper.\n\n$Theorem\\ 4.3$:  The assumption of this theorem is too strict. The author assume the algorithm to have good stability for any distribution in theorem 4.3, then the theorem 4.3 under this assumption can be understood as: algorithms with good generalization to any distribution have a tight generalization bound, this conclusion obviously has no guiding significance in the real world, this is almost just a simple extension of the classic conclusion. We need to know which algorithms have good generalization rather than simply adding it as the assumptions.", "was_revised": true, "final_justification": "I couldn't agree with author on the importance of th3.1, I ultimately believe that the theorem 3.1 paid too little attention to the properties of the algorithm itself, leading to a decrease in its importance. So, I think 3 is fairness for author.\n\nHowever, the theory itself is correct, and different people may see it with different meanings and importance.\n\nSo I won't oppose or recommend this paper.", "rebuttal": "# General Remark\n\nThank you for your comments and for engaging with our paper! \n\nEstimability can sometimes be confusing, and from your comments it appears that there might have been some misunderstandings about the definitions and setting. Concepts such as **estimability**, **generalization**, **stability**, and **learning** are all closely related and can be easily confused, but correctly distinguishing between them is crucial for understanding this paper. We'd be grateful if you could carefully read our response, and follow up with questions about anything that may be unclear! Hopefully, this will help us understand each other better.\n\n---\n\n# Weaknesses\n\n> Please define the symbols before using them, such as U(D).\n\nThe notation $U(D)$ is defined on l. 278.\n\n> Whether the algorithm is SGD, memorization or something else, this lower bound necessarily exists due to the choice of the distribution collection D.\n\nThis comment touches a key issue for understanding our contributions. These lower bounds do **not** hold for all algorithms — the assumption that the algorithm is $\\mathcal F$-interpolating is crucial. In particular, these lower bounds do not hold for memorization algorithms. As discussed in Example 1.6, a memorization algorithm is estimable for any positive $\\varepsilon$, whereas the lower bounds in Thms 3.1 and 3.2 show that other algorithms are not estimable for any $\\varepsilon$ significantly below $1/4$.\n\n> The title of the article is \"Which Algorithms Have Tight Generalization Bounds?\", which clearly does not match the meaning expressed by this theorem.\n\nThe lower bounds in Thms 3.1 and 3.2 apply to certain algorithms but not to others. They hold for algorithms that are suitably $\\mathcal F$-interpolating (e.g., algorithms that are unstable) — showing that those algorithms don’t have tight generalization bounds. In contrast, Thm 4.3 shows that sufficiently stable algorithms *do* have tight generalization bounds. So, the title accurately reflects the central question of the paper.\n\n> The theorem requires the restriction of the number of samples $m$, which further limits the significance of the theorem. It is clear that when the number of samples is small, the generalization performance of the algorithm on complex distributions will not be good, making the conclusion of the theorem somewhat obvious.\n\nThe comment talks about “generalization performance”, but the theorem is about estimability, not performance. There is a crucial distinction (in Section 1.2) between **learning** (i.e., low population loss / test set loss) vs. **estimability**, and this comment appears to be conflating the two. When the sample size $m$ is small, then indeed the performance (test set accuracy) will be poor for most distributions. But that does *not* imply that the algorithm is not estimable. For instance, if $m$ is a small constant and the distribution is labeled by functions from a class with VC dimension $d$, then as $d \\to \\infty$, the performance of the algorithm becomes very poor (it will have high loss on the test set). However, if the algorithm is stable (e.g., memorization) then it can nonetheless have *excellent* estimability and tight generalization bounds, even though $m$ is a small constant and $d \\to \\infty$. In conclusion, the lower bound on estimability does not simply follow from $m$ being small, and our result is **not** obvious.\n\n> When the number of samples is large, it is evident that this lower bound will not hold. \n\nIndeed, Thm 3.1 holds when the number $m$ of samples is small compared to the VC dimension of the set $F$ of possible labeling functions for the population distribution. But this is not a limitation of the theorem — it is simply a basic fact of learning theory that when the number of samples $m$ is large compared to the VC dimension, then *every* algorithm has tight generalization bounds (with respect to a fixed and known marginal distribution, as in Thm 3.1). \n\nOne might desire a theorem that shows a lower bound also for $m$ that is large compared to the VC dimension $d$, but such a theorem would be false — any true theorem must have $m$ small compared to $d$. In our case we show a result for $m = O(\\sqrt{d})$. It is an interesting open question whether this can be pushed further, e.g., can one show a similar result for $m = O(d^{0.9})$?\n\n> In summary, the establishment of these two theorems primarily relies on factors external to the algorithms themselves, which does not align with the previous examples and the main theme of this paper.\n\nAs explained earlier, the lower bounds do **not** apply to all algorithms. The idea that the bounds depend only on external factors, not on the algorithm, is simply untrue. Together with our upper bound, these results are a clear step towards understanding which algorithms have tight generalization bounds: unstable (e.g., \\$\\mathcal F\\$-interpolating) algorithms do not, whereas stable ones do (regardless of performance).\n\n> The assumption of this theorem is too strict. The author assume the algorithm to have good stability for any distribution in theorem 4.3, then the theorem 4.3 under this assumption can be understood as: algorithms with good generalization to any distribution have a tight generalization bound, this conclusion obviously has no guiding significance [...] We need to know which algorithms have good generalization rather than simply adding it as the assumptions.\n\nIt is important to appreciate that **stability** and **generalization** are different things. When referring to “algorithms with good generalization”, does this comment mean algorithms where the empirical error is close to the population error? If so please notice that the memorization algorithm with respect to the uniform distribution does not have good generalization in that sense: the empirical error is always 0, while the population error can be arbitrary (e.g., close to 1). However, the memorization algorithm has excellent **loss stability** with respect to the uniform distribution, and therefore Thm 4.3 implies that it has tight generalization bounds with respect to the uniform distribution. So memorization is an example of an algorithm that *is* stable but does *not* have good generalization in that sense. \n\nThe distinction goes in the other direction too: consider an algorithm $A$ that always outputs hypotheses from some set $\\mathcal G$ such that $\\mathsf{VC}(\\mathcal{G})$ is small compared to the sample size $m$ (but the distributions $\\mathbb{D}$ can be arbitrary). Then $A$ is **not** stable (it can swing wildly between different hypotheses in $\\mathcal G$), but it does have good generalization, and it does have tight generalization bounds. \n\nIf instead “good generalization” in this comment means algorithms with low population loss, then observe that again, that is very different from stability. For instance, Example 1.7 implies that if we fix an algorithm chosen at random from the set of all mappings from training sets to hypotheses, then with high probability that algorithm will not have good performance on the test set (it will have high population loss) but it will have good loss stability and therefore it will have tight generalization bounds.\n\nIn conclusion, **stability** and **generalization** are distinct notions, and neither of them implies the other. Nonetheless, what Thm 4.3 shows is that stability implies the existence of tight generalization bounds, which we believe is a very worthwhile observation.\n\n(It’s interesting to note that our experiments in Appendix L show that empirically SGD has fairly good hypothesis stability for certain natural distributions. This suggests that it might be possible to prove tight generalization bounds for SGD for certain natural distributions. That would be a meaningful and nontrivial result.)\n\n---\n\n# Questions\n\n> I would like the author to further explain the significance and meaning of these theorems and how these theorems can guide us in determining which algorithms have tight generalization bounds?\n\nYes, thank you for asking this. Understanding how our results can be used to determine which algorithms have tight generalization bounds is a very important part of appreciating the value of this paper. Let's walk through this step by step, discussing both our lower bounds and our upper bound. \n\n**Lower bounds.** These bounds show that if an algorithm satisfies a condition called $\\mathcal F$-*interpolating* for some suitable class $\\mathcal F$, then it does not have tight generalization bounds. Let's look at Thm 3.2, because it is a bit more concrete. Fix an algorithm $A$ and a sample size $m$, and fix some collection of orthogonal functions $\\mathcal F$ of size roughly $2^m$ (e.g., $\\mathcal F$ can be a subset of all linear functions $\\mathbb{F}_2^d \\to \\mathbb{F}_2$ for $d > m$). Now comes the pivotal step: show that $A$ is $\\mathcal F$-interpolating, which means that whenever the training set is consistent with some function from $\\mathcal F$, then $A$ outputs a function from $\\mathcal F$. If you can do that, you are done — Thm 3.2 states that no tight generalization bound exists for $A$. Voilà!\n\nNote: as we discuss in Footnote 6, Abbe and Sandon (2020) show that SGD can in particular be interpolating for orthogonal functions, so this recipe can be applied to real-world algorithms too. \n\n**Upper bound.** For example, consider a variant of $k$-nearest neighbors: for input $x$, the algorithm $A$ selects one of the $k$ nearest neighbors of $x$ in the training set uniformly at random, and outputs its label. If fewer than $k/100$ points change in the training set, then the population loss of $A$ changes by ≤ 0.01 — for any distribution! So $A$ is $(0.01, 0, m, k/100)$-loss stable. By Thm 4.3, $A$ has a tight generalization bound for all distributions. Ta-da!\n\n---\n\n# Limitations\n\nThanks for pointing this out. We will use the 10th page in the camera-ready version to add sections on limitations and on directions for future work."}]

Author rebuttal:

Meta-review: (a) The authors study the question which algorithms admit tight generalization bounds. 

(b) Strenghts: the topic is timely, with the open question why deep learning generalizes well. 

(c) Weaknesses: the presentation is rather unconvential, but this is chosen in order to introduce the topic well to the reader. 

(d) Accept. The paper is interesting to the community. 

(e) With one reviewer there has been a substantial debate about the importance and relevance of some of the theorems. Many clarifications have been made by the authors, and in the end, it seems to be that a lot of this hinges on subjectivity.
Decision: Accept (spotlight)