General Remark

Thank you for your comments and for engaging with our paper!

Estimability 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.

---

Weaknesses

Please define the symbols before using them, such as U(D).

The notation $U(D)$ is defined on l. 278.

Whether the algorithm is SGD, memorization or something else, this lower bound necessarily exists due to the choice of the distribution collection D.

This 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$.

The title of the article is "Which Algorithms Have Tight Generalization Bounds?", which clearly does not match the meaning expressed by this theorem.

The 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.

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.

The 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.

When the number of samples is large, it is evident that this lower bound will not hold.

Indeed, 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).

One 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})$?

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.

As 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).

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.

It 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.

The 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.

If 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.

In 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.

(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.)

---

Questions

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?

Yes, 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.

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à!

Note: 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.

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!

---

Limitations

Thanks 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.

Thank you for the significant effort and dedication! We feel that we might be getting a bit closer to clarifying the confusion, especially thanks to the specific example you gave in your response. Below we are respectfully answering the specific questions you asked us, and also addressing that specific example.

Is the estimability more focused on the construction of special distributions or the analysis of the properties of the algorithm itself?

Our framework of Estimability is focused on understanding the behavior of the pairs $(A, \mathbb{D})$ where $A$ is an algorithm and $\mathbb D$ is a collection of distributions. This behavior depends crucially on the properties of the algorithm $A$ itself, and not just on the distributions $\mathbb D$.

To see how estimability depends on the algorithm $A$, let’s revisit your own example, where you write “For example, I define four distributions $D_{i,j}$ …”. In that example, the domain is of size 2, $\\{x_1,x_2\\}$. Let’s consider the exact same example, but generalized to a larger domain of size $d$, $\\{x_1,x_2, …, x_d\\}$. The collection of distributions is $\mathbb{D} = \\{D_y: y \in \\{\pm1\\}^d \\}$, where each distribution is given by $D_y = U(\\{(x_i,y_i): i \in [d]\\})$. Now consider the constant algorithm $A$ that always outputs the function $h(x) \equiv 0$.

Suppose we take a domain size $d = 1000000$, and we take the sample size $m$ to be small compared to $d$, for instance $m = 200$. By Hoeffding’s Inequality (Thm K.3), we have that for any distribution $D$,

$\Pr[|L_S(A) - L_D(A)| \leq 0.1 ] \geq 0.9$.

This means that $A$ has a fairly tight generalization bound.

Consider the following easy yes/no questions:

Q.I. Do you agree that $A$ has a fairly tight generalization bound for $\mathbb{D}$ as described above?

Q.II Do you understand that according to Thm 3.1, there exist other learning algorithms that do not have tight generalization bounds for the exact same $d$, $m$, and $\mathbb{D}$ as above?

Q.III If you answered yes to the previous questions, do you understand now that estimability depends significantly on the algorithm, and not just on the distributions?

For any given algorithm, can we construct a special distribution to negate the estimability of it?

No, some algorithms are always estimable (as long as $m$ is not too small, e.g., $m \geq 200$). Examples include the constant algorithm $A$ discussed above, and the memorization algorithm (we are happy to provide more examples if desired).

what guiding significance does estimability and Th3.1 for us?

The guiding significance comes from analyzing the property of $\mathcal{F}$-interpolation for a specific algorithm, which captures the specific bias of the algorithm. We are happy to explain this further, but first we want to make sure that we are on the same page regarding Q.I,Q.II and Q.III.

---

2, The generalization bound for algorithm $A$ on distribution $D$ is $P_{S \sim D^N}\[|L_S(A(S))-L_D(A(S))| \leq \epsilon] \geq 1-\delta$ or $P_{S \sim D^N}[L_D(A(S)) \leq \epsilon] \geq 1-\delta$, based on the situation.

Your answer to this question is incorrect, and suggests that perhaps you are still somewhat confused about how generalization bounds are defined. Your equation $P_{S \sim D^N}[|L_S(A(S))-L_D(A(S))| \leq \epsilon] \geq 1-\delta$ means that the empirical error is close to the true error. That is sufficient for a generalization bound to be tight, but it is not a necessary condition. As we already noted in our previous answer, tight generalization bounds can also exist if the empirical error is far from the population error (and memorization is a simple example of that). For example, see Equation 3.4 on page 35 of Foundations of Machine Learning (the book can be easily found and viewed online). There are two key differences between that bound and yours:

1. A generalization bound provides an upper bound on the signed difference
   $L_D(A(S)) - L_S(A(S))$ rather than on the absolute value. Bounding the absolute difference would also yield a lower bound on the worst-case gap.

2. In your definition, $\epsilon$ represents a fixed, uniform bound on the deviation between true and empirical error across all samples. However, generalization bounds often involve complexity terms that depend on the sample $S$. For instance, in Equation 3.4, the Rademacher complexity term $\hat{R}_S(G)$ is itself a function of $S$, meaning the deviation between empirical and true error can vary substantially depending on $S$.

Respectfully, please recognize that without fully understanding the definitions in our paper, it will not be possible to understand the paper. This is true for generalization bounds (Eq. 1 in the paper), $\mathcal F$-interpolating, and other basic concepts. We greatly appreciate your dedication to understanding our paper, and we are grateful that you are actively engaging in a dialogue with us towards mutual understanding.

Thank you for your time spent discussing with us.

The following is our final remark regarding your main concern with Theorem 3.1, namely, the suggestion that the result is merely a property of the distribution class:

"If my understanding of the proof is correct, the Theorem comes from the poor properties between X_d and F, but not the algorithm itself (of course, it must be F-interpolating). In other words, when algorithms are considered in this setting (even if they are excellent, such as SGD or memorization)..."

This interpretation is incorrect for a key reason: memorization is not $F$-interpolating. In Theorem 3.1, being $F$-interpolating is not equivalent to merely interpolating the data (i.e., achieving zero empirical error); rather, it encodes a specific bias of the algorithm.

This distinction is crucial: the memorization algorithm has a tight generalization bound, whereas $F$-interpolating algorithms cannot — by construction. Thus, Theorem 3.1 cannot be attributed solely to the choice of distributions; it fundamentally involves the bias encoded by the class $F$ for which the algorithm is $F$-interpolating.

We hope this distinction is now clear :)

General

We are grateful for your positive feedback and the constructive suggestions provided. We have found your comments very valuable in refining our paper.

---

Weaknesses

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);

For 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).

Similarly, 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.

As 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.

[...] as for the former, I would like to see Appendix A.3 in the main text.

Thank 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.

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.

We 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.

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- orthogonal functions.

Related to deep learning, I think the paragraph starting near line 162 means to discuss stability of gradient descent (and variants) [...]

Thanks for pointing this out. We mean neural networks trained with standard optimizers (e.g. SGD,ADAM,…).

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.

Theorems 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.

Limitations

We 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: For VC classes, can the negative results of Theorems 3.1 and 3.2 be extended beyond $d^{0.5}$? A characterization of algorithms that admit distribution-free tight generalization bounds (such as the memorization algorithm). What combined properties of an algorithm and a distribution family admit tight generalization bounds?

---

Questions

Can you give some intuition around Remark 1.3? It seems to make a seemingly strong claim without any justification.

This 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.

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.

Thank 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!

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).

The abstract should include what is meant by stability of algorithms [...]

We will change in line 7 stable -> loss-stable

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 [...]

Thank you for catching this, will correct this.

Fact C.2, as in the main text, is not at all clear, particularly what the variance is with respect to. [...]

You are correct about the sampling process. We will make this more clear in the revision.

I think there are some inaccuracies in Example 1.4. [...]

Note 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.

In Example 1.4 and assumed $0-1$ loss

Thanks for catching this, you we will add the missing assumption of $0-1$ loss.

Example 1.6 and unique labels

Thank you for catching this. We had in mind the setting where the labels are deterministic given the input $x$, we will add this.

Typos:

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.

This 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)).

---

References

[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

Dear reviewer,

Now is time for the discussion with the authors. Can you please reply to their rebuttal, indicating if your issues were clarified and or answered? If that is not the case, please indicate why the answer was not satisfying.

Many thanks! Your AC

Thank you for your thoughtful suggestions, which closely engage with important considerations we had while structuring our presentation.

---

Presentation of the paper

The 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).

As 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.

---

Renaming “Facts” to “Theorems”, “Lemmas”, “Propositions”, “Corollaries”, or “Remarks”

Thank you for this suggestion, we can rename those to Propositions/Theorems.

---

Comparison with Gastpar (2024) et al., the numerical experiments, concluding discussion.

We 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:

• For VC classes, can the negative results of Theorems 3.1 and 3.2 be extended beyond $d^0.5$?
• A characterization of algorithms that admit distribution-free tight generalization bounds (such as the memorization algorithm).
• What combined properties of an algorithm and a distribution family admit tight generalization bounds?

---

Questions

Can you compare your approach to proving non-uniform generalization bounds directly?

We 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?

---

“I thought estimability is equal to having tight bounds”

This 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?

---

“\ldots some interesting algorithms might nonetheless perform well on a certain subset of distributions because they are very estimable on that distribution subset.“

This 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.

---

In Line 124, I would suggest to remove the tilde as a sign of approximation and specify the number.

We can change this to the more conservative $0.16$ for the revised version.

---

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?

Yes, this is correct, But moreover, this holds for large $\varepsilon$, namely, at least $1/4-o(1)$.

---

Line 158: “correct” notion of stability for understanding estimability”.

Note 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.

---

Line 216: “Hence, by Markov’s inequality, 99% of learning rules [...]“

Define $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}$.

---

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?”

This 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.

---

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?

This means concatenation, see definition in l. 337. Note that a set union would not account for duplicates amongst $S_1, S_2$.

---

Dear reviewer,

Now is time for the discussion with the authors. Can you please reply to their rebuttal, indicating if your issues were clarified and or answered? If that is not the case, please indicate why the answer was not satisfying.

Many thanks! Your AC

Dear reviewer,

Please respond to the author rebuttal as soon as possible - but at Aug 8, anytime on earth, at the latest. Please do not only submit the "Mandatory Acknowledgement", but also please respond with text to the author rebuttal. For example, explain why the author rebuttal convinced you, or why not.

Many thanks, Your AC.

We appreciate your positive outlook on our paper and your insightful comments!

---

“This paper is actually about empirical generalization bounds… As a result, it seems overparameterization will rely on distributional properties.”

We 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.

---

“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.”

We 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.

---

“Indeed, the assumption of loss stability is a distributional assumption.”

This 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.

---

“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?”

Yes, 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.

---

“One section that is missing is open problems.”

We appreciate this suggestion and will add a short discussion of open problems. Among the questions we plan to include:

• For VC classes, can the negative results of Theorems 3.1 and 3.2 be extended beyond d^0.5?
• A characterization of algorithms that admit distribution-free tight generalization bounds (such as the memorization algorithm).
• What combined properties of an algorithm and a distribution family admit tight generalization bounds?

---

“Another line of related work is testable learning... It would be nice to include a discussion.”

The 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.