We sincerely thank the reviewer for their thoughtful and constructive comments. We truly appreciate the time and effort spent on evaluating our work. The questions and suggestions raised have helped us clarify our contributions. Below, we respond to each point in detail and provide additional insights or empirical evidence.

1. Main questions

Q1: How the introduced bounds behave under different data geometries or partitioning strategies?

We thank the reviewer for this insightful question. Analyzing the effect of data geometry and partitioning strategies is indeed challenging, particularly in high-dimensional settings with unknown data distributions. To address this, we designed two controlled ablation studies using a synthetic mixture model, described in detail as follows:

• Mixture model (MM): each sample $(x,y)$ is generated by
  • Randomly pick an index $z \sim cat(\theta)$, a categorical distribution with parameter $\theta =(1/K, ..., 1/K) \in R^K$
  • Generate $x \sim Normal(\mu_z, \nu)$, a normal distribution with mean $\mu_z = (0, \pi*z) \in R^2$ and variance $\nu$
  • Return class label $y= 1$ if $z$ is odd, and $y=0$ otherwise
• The uncertainty term $Unc(\Gamma)=C\sqrt{\hat{u}\alpha \ln\gamma } + g_2$ is computed from a sample set $S$, with $K=100, \gamma=0.04^{-1/\alpha}$ and $\delta=0.01$ while varying $\alpha$. This term is the main part in Bound (3) that reflects the role of $\Gamma$.

Exploring different partitioning strategies:

We considered three types of partitions $\Gamma$:

• T1: A uniform grid partition that divides the data space into equally sized regions. However, this strategy may not align with the actual data distribution, potentially resulting in regions with highly imbalanced probability measures.
• T2: A partition formed by uniformly generating $K$ centroids to define the regions. Like T1, this method may not capture the underlying structure of the data.
• T3: A partition where the centroids $\mu_1, ..., \mu_K$ of the mixture components are fixed as region centers. This approach tends to yield more balanced regions, where $P(\mathcal{Z}_i) \approx P(\mathcal{Z}_j)$ for all $i, j$, for small variances.

To evaluate the quality of these partitions, we generated 100,000 i.i.d. samples $S$ from the MM (with $\nu = 1$) and computed $Unc(\Gamma)$ for varying $\alpha$. The results are as follows:

Among the three strategies, T1 resulted in the highest uncertainty, while T3 consistently produced the lowest. These findings suggest that partitions leading to balanced local measures (such as T3) are more favorable, while those poorly aligned with the data distribution (T1, T2) lead to higher uncertainty. This empirical evidence supports our theoretical discussion on the importance of selecting meaningful partitions.

Exploring data geometries: We further examine how the geometry of the data distribution influences the uncertainty term. To this end, we consider a mixture model with varying variances $\nu \in \\{10^0, 10^2, 10^4\\}$, while fixing the partition $\Gamma$ as T3, as described earlier. Notably, increasing $\nu$ to $10^4$ significantly alters the geometry of the mixture model compared to the case $\nu = 1$. The corresponding uncertainty values are reported below.

These results demonstrate that $Unc(\Gamma)$ can vary considerably depending on the geometry induced by the data distribution. When the partition $\Gamma$ does not align well with the data, the resulting local regions may have highly imbalanced probability measures. In such cases, the uncertainty can be large.

Q2: Other data augmentation techniques?

Thank you for the thoughtful question. To further investigate the impact of different data augmentation techniques, we conducted an additional set of experiments using Brightness adjustment as an alternative augmentation method. Specifically, we applied the adjust_brightness transform from Torchvision, varying the brightness factor between 1.4 and 2.5, and then computed Bound (4) accordingly. The results are presented below.

We observed that Bound (4) exhibits behavior similar to that in the case of Gaussian noise: for most models, it shows a strong correlation with the test error. An exception occurs with DenseNet161 and DenseNet201, where a relatively large brightness factor was needed to recover the superior performance of DenseNet161.

Overall, these findings suggest that our bound responds consistently across different augmentation techniques.

Q3: Can the proposed bounds be compared to existing generalization bounds?

We sincerely thank the reviewer for this thoughtful suggestion. However, we would like to respectfully clarify that a direct numerical comparison between our bound and existing generalization bounds (e.g. PAC-Bayes or compression-based) can be inherently problematic and potentially misleading. As discussed in our response to Question Q7 from Reviewer 8XVE (see above), such comparisons may not be entirely fair due to fundamental differences in assumptions, applicability, and the way these bounds are computed.

We also note that many existing bounds, aside from PAC-Bayes, typically require access to a validation set to approximate quantities that are not directly computable from the training data. In contrast, our bound is fully computable using the training data alone. This further complicates direct comparisons and may introduce additional biases.

That said, we did carry out an additional comparison with robustness-based bounds proposed in [1, 2], which are also model-dependent. In this comparison, we applied our bound under the mild setting used in Table 2, while for [1, 2], we used $\delta = 0.05$ (corresponding to 95% confidence) and utilized the ImageNet validation set to approximate the intractable components. The results across 17 models are summarized below.

Our findings show that our bound outperforms the existing robustness-based bounds in most cases, despite not relying on the validation set. This highlights the practical advantages and potential of our bound.

[1] Robustness implies generalization via data-dependent generalization bounds. In ICML, 2022.

[2] Gentle local robustness implies generalization. Machine Learning, 2025.

2. Other comments:

C1: the influence of $\alpha$ on $Unc(\Gamma)$ reported in Figure 2 (left) seems to contradict the explanation given in l.258

Line 258 mentions the certainty $1-\gamma^{-\alpha} -\delta$. Hence, there should be no contradiction.

C2: The conclusions drawn in Section 4.2 regarding the data augmentation-based bound (l.316-319) appear to apply to the results in Table 2 as well

Thank you for the observation. We agree that there are a few cases where a model with a smaller test error may have a larger bound compared to another model. These instances highlight some limitations of our bound.

Dear Reviewer TCVt

We sincerely thank the reviewer for the thoughtful comments and valuable suggestions. Below, we address the remaining concerns.

Q1: it would be helpful to clarify why this particular setup was chosen.

We used this mixture model as an intuitive example. The main reason is that one can choose some partitions which are easily verified to be bad or good, in terms of the balanced probability measures in local regions. For instance, partition T3 seems to be perfect. Furthermore, one can easily see the data geometry induced by such a mixture model.

Q3: Isn't there a way to adapt the PAC-Bayes framework to make the comparison possible? For example by applying Markov’s inequality (to obtain a high-probability bound on a single model) or using a posterior distribution concentrated around the final model $h$.

Thank you for your understanding. In fact, derandomizing PAC-Bayes bounds remains a challenging problem. While some prior work [3] has attempted this, such approaches typically impose additional assumptions, e.g., requiring the training algorithm to be deterministic. These assumptions do not align well with modern deep learning practices, which often involve inherently stochastic algorithms.

Regarding the use of Markov's inequality: although it can be employed to convert an expectation $\mathbb{E}_g [F(P, g)]$ into a probability bound of the form $\Pr_g(F(P, g) \ge a) \le \frac{1}{a} \mathbb{E}_g[F(P, g)]$, the resulting probability is over the randomness of $g$. This differs fundamentally from the traditional PAC setting, where the probability is taken over the sampling of the dataset $S$, i.e., $\Pr_S(F(P, h) \ge a)$.

Aside from recent work on LLMs [4,5], we are not aware of any method that allows for a direct and fair comparison between our bounds and PAC-Bayes bounds.

On robustness-based bounds: We see two main limitations in prior work. First, the bound in [1] involves a robustness term defined as the worst-case difference between the losses of two samples within the same local region. As shown in [2], this term becomes vacuous for imperfect classifiers, a behavior we also observed empirically—e.g., for ImageNet models, the robustness term often equals 1. Second, the bound in [2] adopts a slightly looser uncertainty term compared to ours. Together, these factors explain why the robustness-based bounds tend to be weaker than ours, as reflected in our reported results.

[1] Robustness implies generalization via data-dependent generalization bounds. In ICML, 2022.

[2] Gentle local robustness implies generalization. Machine Learning, 2025.

[3] A general framework for the practical disintegration of pac-bayesian bounds. Machine Learning, 2024.

[4] Non-vacuous generalization bounds for large language models. In ICML, 2024.

[5] Unlocking tokens as data points for generalization bounds on larger language models. In NeurIPS, 2024.

C2: This is helpful to know and, in my opinion, should be stated explicitly in the paper

Sure, we will add it in the revised version. We sincerely thank the reviewer for helpful suggestions.

We sincerely thank the reviewer for their positive evaluation and valuable suggestions. We truly appreciate the time and effort spent on evaluating our work. The questions and suggestions raised have helped us clarify our contributions. Below, we respond to each point in detail.

1. Main questions

Q1: please consider the follow on work to your citation [30] ... I would want a rebuttal to their argumentation

We'd like to thank you very much for reminding us on the writing. We'll rephrase it appropriately. Some of our arguments appear in lines 117--156.

Q2: For Table 2, why do you have Acc@1 and test error where test error is just 100-acc@1?

We included both columns to enable an easy verification with the source from Pytorch. Otherwise, using "test error" only may confuse the readers.

Q3: As for Table 3, why do we need Gaussian noise on the training images? How do the computed bounds alter as a function of the sigma chosen.

Bound (4) needs a transformation for the training set. We used Gaussian noises as a simple transformation.

Figure 3 shows how the bound (for some models) can change when $\sigma$ changes.

Q4: Bound is so large as to be useless, can we infer anything useful from the bound is there at least a correlation between bound size and test error? Can we plot this maybe in Figure 3c?

We thank the reviewer for the insightful question.

We would like to kindly clarify that Bound (3) demonstrates strong alignment with test error in many cases, as evidenced in Table 2, and exhibits a clear correlation between its value and test error, as shown below:

Regarding Bound (4) (reported in Table 3), we acknowledge that it is not designed to provide a tight estimate of the test error. This bound is introduced to highlight certain aspects of model behavior, particularly under perturbations or rare conditions. Because it is evaluated on perturbed samples, it is naturally expected to be looser than Bound (3). This increase is consistent with the well-known challenges of robustness and adversarial vulnerability in neural networks.

We agree that visualizing this correlation could be helpful and will be happy to include an additional plot to illustrate the relationship between bound values and test error.

Q5: How choosing K and $\alpha$ with a grid search on the training set still allows the bound to hold at the nominal ninety five percent confidence.

We'd like to remind that the confidence in Theorem 3.2 is $1-\gamma^{-\alpha} -\delta$. In our experiments, we chose $\gamma = 0.04^{-1/\alpha}$ and hence $\gamma^{-\alpha} = 0.04$ for any given $\alpha$. Therefore, with $\delta=0.01$, the confidence is $1-\gamma^{-\alpha} -\delta = 0.95$.

Q6: How the input space partition is built. State the feature representation used for clustering, the distance metric, the clustering algorithm, the random seed strategy, and report any sensitivity the final bound has to these choices.

We've already described the details in Appendix C, page 20. The sensitivity w.r.t. the partition can be observed from 6th column in Table 2. It also can be observed from Figures 1 and 2, where each standard deviation was computed from 5 different partitions.

Q7: Provide a direct numerical comparison on a smaller network where a known PAC Bayes or compression bound can be computed so readers can see the quantitative improvement your method offers.

We sincerely thank the reviewer for the thoughtful suggestion. However, we would like to respectfully clarify that providing a direct numerical comparison between our bound and existing PAC-Bayes or compression bounds is inherently problematic and may lead to biased conclusions. The reasons are as follows:

• Our bound directly estimates the expected error $F(P, h)$ of a specific model $h$, and can be computed exactly from an i.i.d. training set with bounded loss, without requiring any modification to the model or additional assumptions. In contrast, under the same conditions, existing PAC-Bayes or compression bounds are generally not computable in exact form. While this setting may appear to favor our bound, we argue that it is representative of practical scenarios where one wants to assess the reliability of a trained model.
• Many classical PAC-Bayes bounds [1, 2] aim to estimate $E_g[F(P, g)]$, which captures the expected error over a hypothesis distribution rather than a particular trained model. While useful for understanding properties of the learning algorithm or hypothesis class, this quantity is not guaranteed to reflect the actual error of the final trained model $h$. As such, a bound on $E_g[F(P, g)]$ does not necessarily imply an upper bound on $F(P, h)$, making direct comparison with our bound inherently unequal.
• Existing derandomization techniques for PAC-Bayes bounds [3] often rely on restrictive conditions, such as requiring the training algorithm to be deterministic. These assumptions are not reflective of common practice in modern deep learning, which typically relies on stochastic algorithms.
• Some recent PAC-Bayes bounds [4, 5] that do target $F(P, h)$ require significant model compression followed by fine-tuning. In these cases, the bound applies to the compressed model $h'$, which may differ substantially from the original model $h$. This makes it incompatible with our setting, where we estimate the true error of the actual model $h$ as trained. Applying our bound to a compressed model $h'$ would introduce bias favoring PAC-Bayes approaches and would not fairly represent the quality of the original model, since compression may significantly degrade performance [4].

For these reasons, we chose not to include PAC-Bayes or compression bounds in our experimental comparisons.

To directly address the reviewer's suggestion, we computed our bound for MobileNet. The results (in %) for two variants trained by PyTorch are as follows:

For the same MobileNet architecture, [2] reported the best PAC-Bayes bound as 96.5%, which is notably looser than ours. Meanwhile, [1] achieved a bound of 40.9% for a compressed MobileViT, relying heavily on compression and quantization techniques, along with a validation set to estimate a data-dependent prior.

These observations highlight the advantages of our bound, especially in avoiding reliance on additional components like validation sets or compression, while still yielding tighter estimates.

[1] Pac-bayes compression bounds so tight that they can explain generalization. In NeurIPS, 2022.

[2] Non-vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach. ICLR, 2019.

[3] A general framework for the practical disintegration of pac-bayesian bounds. Machine Learning, 2024.

[4] Non-vacuous generalization bounds for large language models. In ICML, 2024.

[5] Unlocking tokens as data points for generalization bounds on larger language models. In NeurIPS, 2024.

Q8: Why the Gaussian noise robustness bound does not track test error for certain RegNet and ViT models?

We'd like to thank the reviewer for insightful comment. Table (4) presents bound (4) which does not recover the better performance of RegNet and ViT in some cases. We hypothesized that the noises may not be significant enough.

To verify our hypothesis, we increase the variance $\sigma$ of the Gaussian noises and then measured the bounds again. The results (in %) are as follows.

We observe that a suitable variance will recover the better performance of a model. Nonetheless, each architecture may require a different $\sigma$. The reason for this behavior may come from the special property of the network architecture. A careful observation about Tables 2 and 3 suggests that within one architecture (e.g. ResNet) our bounds strongly correlate with the test error. However, our bounds may not perfectly correlate with the test error when comparing across architectures (e.g., ResNet and SwinTransformer).

Q9: Suggest concrete analytical refinements for shrinking the gap between the reported bound and the true error.

We've already discussed some ideas in lines 335--342.

2. Other comments:

C1: The numerical bounds remain loose

Thank you for this insightful comment. We fully agree with the reviewer that, despite certain strengths, Bound (3) remains loose in many cases. This highlights a clear opportunity for future improvements and refinement.

We'd like to gently emphasize that our bounds, while suboptimal, represent a meaningful step forward in bridging the long-standing gap between theoretical guarantees and practical performance in deep learning. To the best of our knowledge, no existing theory can provide non-vacuous guarantees for the large-scale ImageNet models used in our experiments without significantly altering the models themselves.

We sincerely thank the reviewer for their thoughtful and constructive comments. We truly appreciate the time and effort spent on evaluating our work. The questions and suggestions raised have helped us clarify our contributions and better position our results. Below, we respond to each point in detail and provide additional insights, empirical evidence, and clarifications where needed.

1. Main questions

Q1: How does the need to calculate C from (1), (3) and (4) affects the applicability of your bounds in general case?

Thank you for this thoughtful question. We would like to clarify that the constant $C$ in our bounds can be computed easily for many commonly used loss functions, particularly when the target function is bounded. This includes:

• Classification problems with $L$ classes:
  • For the 0-1 loss, $C = 1$
  • For the absolute loss and squared loss, $C = 2$, assuming predictions and labels are represented by one-hot vectors
• Regression problems where outputs are bounded by a constant $A$:
  • For the absolute loss, $C = 2A$
  • For the squared loss, $C = 4A^2$

These cases cover many standard supervised learning settings in both theory and practice. For other loss functions such as the cross-entropy loss, the constant $C$ may be unbounded. In such situations, smoothing techniques (as explored in [1, 2]) can be employed to make the bounds applicable.

Overall, the ability to compute $C$ in a wide range of practical scenarios supports the broad applicability of our proposed bounds.

[1] Non-vacuous generalization bounds for large language models. In ICML, 2024.

[2] Unlocking tokens as data points for generalization bounds on larger language models. In NeurIPS, 2024.

Q2: Have you tried other methods of acquiring $\Gamma$? How did it influence your results?

We thank the reviewer for insightful question. Our experiments in Section 4 are really expensive. Therefore, we did not try to optimize our bounds accroding to partition $\Gamma$. An optimal choice of $\Gamma$ can produce tighter estimates about the true error.

The result in the 6th column of Table 2 suggests that our bound is stable w.r.t. different choices of $\Gamma$, for a fixed granularity $K$.

Inspired by the reviewer's question and to reveal more effects of $\Gamma$, we design a controlled ablation as follows:

• Generate 100,000 i.i.d. samples $\{(x_i,y_i)\}$ from the Mixture model (MM) as below:
  • Pick randomly an index $z \sim cat(\theta)$, a categorical distribution with parameter $\theta =(1/K, ..., 1/K) \in R^K$
  • Generate $x \sim Normal(\mu_z, 1)$, a normal distribution with mean $\mu_z = (0, \pi*z) \in R^2$ and variance $1$
  • Return class label $y= 1$ if $z$ is odd, and $y=0$ otherwise
• We considered three types of partitions $\Gamma$ with $K=100$:
  • T1: A uniform grid partition that divides the data space into equally sized regions. However, this strategy may not align with the actual data distribution, potentially resulting in regions with highly imbalanced probability measures.
  • T2: A partition formed by uniformly generating $K$ centroids to define the regions. Like T1, this method may not capture the underlying structure of the data.
  • T3: A partition where the centroids $\mu_1, ..., \mu_K$ of the mixture components are fixed as region centers. This approach tends to yield more balanced regions, where $P(\mathcal{Z}_i) \approx P(\mathcal{Z}_j)$ for all $i, j$, for small variances.
• We then compute the uncertainty term $Unc(\Gamma)=C\sqrt{\hat{u}\alpha \ln\gamma } + g_2$, with $\gamma=0.04^{-1/\alpha}$ and $\delta=0.01$. This term is the main part in our bound (3) that reflects the role of $\Gamma$. The results are below:

For small $\alpha$, there is slight change in $Unc(\Gamma)$ for three different partitions. Furthermore, an increase in $\alpha$ can reduce the difference of the uncertainty. This suggests that our bounds can be more stable as $\alpha$ increases. This behavior is similar with that in Figure 2.

2. Other comments:

C1: The gap between the test error and bound (3) remains substantial. Moreover, bound (4) exceeds 100% in roughly one third of the cases reported in Table 3, raising doubts about its usefulness even for correlation analysis.

Thank you for this insightful comment. We fully agree with the reviewer that, despite certain strengths, Bound (3) remains loose in many cases. This highlights a clear opportunity for future improvements and refinement of our theoretical framework.

That said, we would like to gently emphasize that our bounds, while suboptimal, represent a meaningful step forward in bridging the long-standing gap between theoretical guarantees and practical performance in deep learning. To the best of our knowledge, no existing theory can provide non-vacuous guarantees for the large-scale ImageNet models used in our experiments without significantly altering the models themselves.

Regarding Bound (4), we would like to clarify that its primary goal is not to provide non-vacuous guarantees, but rather to support further exploration of model behavior and to enable meaningful comparisons between models. Although Bound (4) may appear imperfect, it still demonstrates a strong correlation with test error, as we illustrate below.

A careful observation about Tables 2 and 3 suggests that within one architecture (e.g. ResNet) our bounds strongly correlate with the test error. Those observations suggest the practical utility of our bounds in practice.

C2: Only in some cases, the decrease in bound values appears linked to improved test accuracy rather than training accuracy, suggesting that the bounds may not be better predictors of test error than training error alone.

Thank you for raising this important point. We fully agree that our theoretical bounds do not always align perfectly with the test error observed in practice. Nonetheless, we would like to highlight that overall, the bounds exhibit a strong correlation with the test error, as demonstrated in the results below:

A closer examination of Tables 2 and 3 suggests that within a single architecture (e.g., ResNet), our bounds correlate well with the test error. However, the correlation may weaken when comparing across different architectures (e.g., ResNet versus SwinTransformer).

This observation further points to the need for improved architectural normalization in the bound formulation, which we view as a valuable direction for future work.

C3: The selection of $\Gamma$ is crucial, as highlighted in the paper, yet the authors do not provide clear guidelines or analysis on how to choose it.

Thank you very much for highlighting this important point. We agree that the choice of the partition $\Gamma$ is crucial to our bound.

Our intention was to present a general framework that accommodates a wide range of choices for $\Gamma$, depending on the application or the domain knowledge available. In practice, we observe that simple partitions (e.g., uniform grid or clustering-based) can already yield meaningful and non-vacuous bounds, as demonstrated in our experiments. A better partition can lead to a tighter estimate of the test error.

We appreciate the reviewer’s suggestion and agree that a more systematic study of partition selection would be a valuable direction for future work.

C4: The presentation of the experimental results can be improved.

Thank you for this helpful suggestion. This can strengthen our work and we'll revise it accordingly.

Dear Reviewer Nh1T

Thank you very much for your insightful and helpful suggestions. We'd like to address the remaining concerns below.

Q1: using such crude approximations for $C$ might be undesirable, and one might have to fall back to estimating $\sup_{z \in Z} \ell(h, z)$. That is why I want this problem to be treated as a limitation

We fully agree with the reviewer that the examples we previously provided for $C$ are indeed crude approximations. In practice, incorporating domain knowledge or model-specific insights could lead to tighter, more meaningful estimates of $C$, potentially resulting in improved bounds. However, we also acknowledge that in some cases, computing or even approximating $C$ can be challenging. We therefore recognize this as a limitation of our current approach and appreciate the reviewer’s suggestion to highlight it as such.

Q2: Is it possible to extend it to dimensionality of at least $100$ to make the setup more realistic? Is it possible to conduct a similar experiment with at least one real setup?

Thank you for this thoughtful question. To address it, we conducted an additional experiment in a 100-dimensional space:

• We used the same mixture model as before, with the mean of the $z$-th Gaussian component set to $\mu_z = (0, 0, \ldots, 0, \pi \cdot z) \in \mathbb{R}^{100}$.
• We considered the same partitions T2 and T3 as in the 2D setting, with $K = 100$. Partition T1 was omitted due to the difficulty of dividing the high-dimensional space into equal-sized regions.

The results for $\text{Unc}(\Gamma)$ are summarized below.

We observe that increasing the dimensionality from 2 to 100 slightly affects the results for partition T2, while the results for T3 remain largely unchanged. This stability in T3 is likely due to its ability to better balance probability mass across local regions. Consistent with our earlier findings, we also see that increasing $\alpha$ reduces uncertainty differences, suggesting improved bound stability at higher $\alpha$ values.

Regarding real-world datasets: since the underlying data distribution is unknown, constructing an effective partition similar to T3 is non-trivial without additional domain knowledge or assumptions. As such, replicating the exact experimental setup is challenging. However, we have computed our bound (3) under a range of more practical partition strategies:

• Using randomly generated centroids,
• Varying the granularity parameter $K$.

Figure 2 presents results for the ImageNet dataset. Notably, for a fixed $K$, our bound (3) remains stable across different random partitions, further supporting the robustness of our method.

Q3: calculate the same correlations for the train error vs. test error and "bound minus train error" (i.e., the additional terms in (1), (3) and (4)) vs. test error.

Thank you for your insightful suggestion.

We note that with our current choice of $C = 1$, the quantity Bound (3) – train error becomes a constant across models. As a result, computing its correlation with the test error is not meaningful. Instead, we focus on analyzing the correlations between Bound (1) – train error and Bound (4) – train error with the test error. The results are summarized below.

In particular, Bound (1.T) refers to the approximation of Bound (1) using the ImageNet training set, while Bound (1.V) uses the validation set.

The results show that the uncertainty term in Bound (1) and the robustness term in Bound (4) capture meaningful characteristics of the trained models and correlate strongly with the test error. This highlights the practical relevance of our bounds for performance estimation.

While Bound (3) offers a formal guarantee on test error, it does not exhibit the same level of correlation, and is therefore less effective in this specific empirical analysis.

We hope that those further information and discussions can fully address all the concerns of the reviewer. We will be happy to answer any further question.

Dear Reviewer Nh1T

We would like to sincerely thank you for your positive feedback. We'll be happy to discuss further any more concern.

For the constant $C$: We acknowledge that the constant $C$ in our bounds is a valid concern and appreciate the reviewer for raising this point. We recognize that identifying an appropriate value is not always straightforward and may affect the tightness of the bound. We will revise the manuscript to clearly state this limitation.

We would also like to note that this challenge is not unique to our work, but is shared by many existing generalization bounds. For example, the bounds in [3,4] include a constant $\Delta$ that bounds the range of the loss function. Similarly, the bounds in [5,6] rely on a constant $C$ analogous to ours. The bound in [7] further requires knowledge of the Lipschitz constant of the loss, while [8] depends on the total Lipschitz stability constant $\gamma$ of the learning algorithm, both of which are typically harder to compute than our $C$.

We hope this context helps clarify that while the constant presents a limitation, it is a common and often unavoidable aspect of generalization theory.

Again, we appreciate your overall positive assessment and your suggestion to polish the claims and discussions. We will revise the paper accordingly to better reflect its limitations while emphasizing its practical relevance and theoretical novelty. We hope these clarifications and improvements will strengthen your confidence in the contribution and motivate a more favorable score.

Reference:

[3] Non-vacuous generalization bounds for large language models. In ICML, 2024.

[4] Unlocking tokens as data points for generalization bounds on larger language models. In NeurIPS, 2024.

[5] Robustness implies generalization via data-dependent generalization bounds. In ICML, 2022.

[6] Gentle local robustness implies generalization. Machine Learning, 2025.

[7] Slicing Mutual Information Generalization Bounds for Neural Networks. In ICML, 2024.

[8] Algorithmic Stability Unleashed- Generalization Bounds with Unbounded Losses. In ICML, 2024.

We would like to thank the reviewer for praising our work and valuable feedback. We would like to discuss about the remaining concerns below.

1. Main questions

Q1: Why evaluate the only trained model? What about the one near the trained model? Can this framework consider a hypothesis space? Please give more explanations.

We thank the reviewer for this insightful question. In our work, we focus on estimating the true error $F(P, h)$ of a specific trained model (or hypothesis) $h$. The motivation is that $F(P, h)$ directly characterizes the generalization performance of $h$ on unseen data. Accurately estimating this quantity is crucial for providing theoretical guarantees, especially when $h$ is intended to be deployed in real-world, safety-critical applications. For this reason, we evaluate trained neural networks in our experiments to assess the practical utility and tightness of our proposed bounds.

While our framework is designed for evaluating individual models, it can also be applied to any fixed hypothesis, such as one in the neighborhood of a trained model. Additionally, although our bounds can, in principle, be used to analyze finite hypothesis spaces by evaluating each member individually, they are not directly applicable to infinite hypothesis spaces in the same way as some other frameworks (e.g., PAC-Bayes). Extending our approach to broader hypothesis spaces is an interesting direction for future research.

Q2: Please give a more intuitive explanation of why including the partition can help to improve or induce the desired bounds.

We appreciate the reviewer’s question and are happy to provide a more intuitive explanation. Including the partition $\Gamma$ contributes to the strength of our bound for three main reasons:

• Capturing local data properties: The partition $\Gamma$ allows us to examine the data distribution at a finer granularity, effectively dividing the data space into local regions. This enables us to estimate how frequently i.i.d. samples fall into different parts of the space. In Appendix B.3, we develop novel analyses involving binomial and multinomial random variables to formalize this intuition. These local sampling characteristics are then summarized by the quantities $u$ and $g$ in our bound (1). A more fine-grained partition yields a richer summary of the underlying data distribution.
• Analyzing model behavior locally: The partition also helps us understand how the model $h$ behaves across different regions of the input space. Rather than evaluating $h$ globally, we use $\Gamma$ to capture its local performance, which is again reflected in the quantity $g$. This local perspective provides a more nuanced understanding of the model’s generalization behavior.
• Approximating the true error locally: Finally, the partition allows us to construct provable approximations of the true error within each region. By leveraging properties of binomial random variables (Appendix B.3), we can control the approximation error at the local level. These local estimates are then aggregated to produce the overall bound in (1).

In summary, the partition enables a more detailed exploration of both the data distribution and model behavior, which in turn leads to sharper and more informative generalization bounds.

2. Other comments:

C1: Theorem 3.1 shows that the generalization of a model is only dependent on its training error since $Unc(\Gamma)$ is independent of the models, which can not explain why two models share the same training error but different test errors.

The reviewer's concern may refer to Theorem 3.2. We totally agree with the reviewer about the limitation of bound (3) in Theorem 3.2. We also discuss this in our paper. The main reason comes from the use of $g_2$ to upper bound $g$ in Theorem 3.1 (see line 484). Removing this step can result in a better bound such as:

$F(S,h) + C\sqrt{\hat{u}\alpha \ln\gamma } + g(\Gamma,h,\delta)$       (5)

where $g$ is a function of $h$. Therefore, this bound (5) can track the behavior of $h$ better than bound (3), suggesting a better way to compare two models. Unfortunately, $g$ cannot be computed exactly in practice, and approximation is needed.

C2: Besides, the theory results show that a smaller training error implies a smaller test error, which is not always consistent with the experimental results

Thank you for raising this important point. We fully agree that our theoretical bounds do not always align perfectly with the test error observed in practice. Nonetheless, we would like to highlight that overall, the bounds exhibit a strong correlation with the test error, as demonstrated in the results below:

A closer examination of Tables 2 and 3 suggests that within a single architecture (e.g., ResNet), our bounds correlate well with the test error. However, the correlation may weaken when comparing across different architectures (e.g., ResNet versus SwinTransformer).

This observation further points to the need for improved architectural normalization in the bound formulation, which we view as a valuable direction for future work.

C3: Although Theorem 3.2 can provide an attempt to address the mentioned issue of Theorem 3.1, the results are not very satisfactory. On one hand, theoretically, the bound (4) in Theorem 3.2 is looser than the one (3) in Theorem 3.1, which is weird to use loose bounds to compare different models. On the other hand, experimentally, the bound (4) is often vacuous, as illustrated in Table 3.

We sincerely appreciate the reviewer’s thoughtful feedback. We would like to clarify that the primary purpose of Bound (4) is not to ensure non-vacuousness, but rather to enable meaningful comparison between models and provide deeper insights into model behavior. While it may initially seem counterintuitive to use a looser bound for such comparisons, we have found this to be valuable in practice.

In particular, Bound (4) exhibits a stronger empirical correlation with the test error than Bound (3), as shown before. This suggests that although Bound (4) may be looser in a theoretical sense, it can better reflect model performance in some practical settings, especially when the tightest theoretical bound does not align with observed generalization behavior.

To further support this, we repeated the experiments in Table 3 under increased noise variance $\sigma$. The results (in %) are presented in the table below.

We observed that, under appropriate noise settings, Bound (4) successfully recovers the relative quality of models, whereas training error and Bound (3) may provide misleading assessments.

These findings indicate that even a looser bound can be more informative in practice, especially when used to understand or compare models under realistic conditions. We hope this perspective clarifies the intent and utility of Bound (4) in Theorem 3.3.

C4: The generalization bounds only evaluate one hypothesis (the trained model), which might not be fair to the norm-based bound, which considers a hypothesis space including the trained one.

We thank the reviewer for insightful comment. When suitably exploiting some prior knowledge about the hypothesis space, one can expect to obtain a tight estimate about the true error of the trained model $h$. However, none of the existing efforts can succeed at obtaining a non-vacuous norm-based bound.

C5: This paper considers the 0/1 loss instead of the surrogate loss in experiments (or theory), which can be expressed more clearly.

The theory part uses a bounded loss which is general. The experiment part uses the 0/1 loss to enable an easy link with error and accuracy, widely-used in practice.

Dear Reviewer Uu4e

We sincerely thank the reviewer for the valuable suggestions. We appreciate your recognition of the importance of the problem addressed in this work and your acknowledgment of our contributions toward it. Below, we respond to your comments and clarify several points, with the hope that this may address your remaining concerns and support a higher evaluation.

Limitation and model before the final SGD step:

We agree that our model-dependent bounds can be limited in understanding a hypothesis space or learning algorithm. We will note this in the revised manuscript.

While our bounds can be used to analyze some models in the course of training by some methods such as SGD, our focus on the (finally-selected) trained model aligns with practical deployment scenarios, where this is the model actually used in real-world systems. Estimating its true test error remains a crucial and unresolved challenge, and our work provides a step toward addressing it in a principled way.

C3 – Informative value of vacuous bounds: We understand your disagreement and appreciate the chance to clarify. Our intention was not to suggest that vacuous bounds are preferable, but rather that certain looser bounds (e.g., Bound (4)) may correlate better with test error in practice due to how they encode relevant uncertainty information. Our experiments suggest that Bound (4) can have a better correlation than Bound (3). Such a phenomenon is in fact not new, since [1] found that norm-based bounds (which are highly vacuous [2]) may have a strong correlation with the test error. That said, we fully agree that non-vacuous bounds such as Bound (3) are ultimately more desirable and interpretable, and this is exactly the motivation for our work. We will revise the discussion to better reflect this nuance and avoid potential misinterpretation.

C5 – Constant in Bound (3): We acknowledge that the constant in Bound (3) is a valid concern and appreciate the reviewer for raising this point. While $C$ can be easily computed in some settings, we recognize that identifying an appropriate value is not always straightforward and may affect the tightness of the bound. We will revise the manuscript to clearly state this limitation.

We would also like to note that this challenge is not unique to our work, but is shared by many existing generalization bounds. For example, the bounds in [3,4] include a constant $\Delta$ that bounds the range of the loss function. Similarly, the bounds in [5,6] rely on a constant $C$ analogous to ours. The bound in [7] further requires knowledge of the Lipschitz constant of the loss, while [8] depends on the total Lipschitz stability constant $\gamma$ of the learning algorithm, both of which are typically harder to compute than our $C$.

We hope this context helps clarify that while the constant presents a limitation, it is a common and often unavoidable aspect of generalization theory.

Again, we appreciate your overall positive assessment and your suggestion to polish the claims and discussions. We will revise the paper accordingly to better reflect its limitations while emphasizing its practical relevance and theoretical novelty. We hope these clarifications and improvements will strengthen your confidence in the contribution and motivate a more favorable score.

Reference:

[1] Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data. NATURE COMMUNICATIONS, 2021.

[2] Stronger generalization bounds for deep nets via a compression approach. In ICML, 2018.

[3] Non-vacuous generalization bounds for large language models. In ICML, 2024.

[4] Unlocking tokens as data points for generalization bounds on larger language models. In NeurIPS, 2024.

[5] Robustness implies generalization via data-dependent generalization bounds. In ICML, 2022.

[6] Gentle local robustness implies generalization. Machine Learning, 2025.

[7] Slicing Mutual Information Generalization Bounds for Neural Networks. In ICML, 2024.

[8] Algorithmic Stability Unleashed- Generalization Bounds with Unbounded Losses. In ICML, 2024.

Thank you for the detailed response.

Q1&C4: I think this is the limitation of this work, which should be expressed more clearly. Please consider the model before the last (SGD) step of the end (corresponding to the trained model), which can also have promising performance in practice.

Q2&C1&C2: Thanks for the clarification.

C3: If the non-vacuous bound (3) is meaningful, I do not agree with the claim that a looser (vacuous) bound can be more informative in practice.

C5: I have the same concern with the constant $C$ raised in Q1 of Reviewer Nh1T.

Overall, despite the above concerns, I still think this paper provides a good attempt to address a very important problem in learning theory. I suggest that the authors polish the claims and discussions.