acceptodds
Under review as a conference paper at ICLR 2027

An Information-Theoretic Framework for Stability-Based Generalization Bounds

Abstract

We derive a family of novel bounds on the expected generalization error of learning algorithms. Our bounds simultaneously leverage two properties of the learning algorithm: 1) algorithmic stability and 2) information measures of the dependence between the training data and the learned hypothesis. Our approach establishes a general bound based on -divergences and allows for various specializations under a series of new stability conditions. These conditions are weaker than established notions of stability from the literature which makes them applicable to a wider range of learning scenarios, especially when the loss function is unbounded. When evaluated with several concrete examples, our bounds strictly improve upon both the classical stability-based and information-theoretic bounds.

Primary area:
learning theory
Keywords:
learning theory, information theory, generalization bound

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_oREoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper bounds the expected generalization error of a possibly randomized algorithm by combining algorithmic stability with information measures. Several new stability notions (except strong uniform stability) are introduced, which form a hierarchy and strong uniform stability implies all of them. Lemma 2 and Theorem 2 provide the general generalization bound obtained from ff-divergences and generalized cumulant generating functions (CGFs). Assuming different stability notions, more concrete bounds are obtained with different ff-divergences in Corollaries 1-4. Section 5 focuses on several practical examples with known data distributions and shows that the established generalization bounds are tight (up to constants).

Critical strengths
  1. Several new stability notations are introduced in the paper, with a clear hierarchy map in Figure 1 indicating which ones are stronger. These new notations can be of independent interest and potentially stimulate related research on algorithmic stability.

  2. The established bounds by combining stability and information measures are general in the sense that it can be instantiated with many other stability notions and ff-divergences. Moreover, it can imply tight bounds in some practical applications, e.g., the three examples considered in Section 5.

  3. The paper disproves some results (e.g., Corollary 3.1) from Wang and Mao (2023a) in Appendix O, which is valuable and appears to be correct.

Critical weaknesses
  1. Generalization bounds using ff-divergences and the generalized-CGF bounds seem already exist in Agrawal and Horel (2021). Also, Corollary 4 follows from their Lemma 87, as acknowledged in the paper p.7. However, a detailed discussion of how do the results (especially Lemma 2 and Theorem 2) compare with those in Agrawal and Horel (2021) is not provided.

  2. The mean-p-norm stability introduced in Def 9 generalizes the mean-square stability (Kale et al., 2011) by allowing p>1p>1 rather than p=2p=2. This contribution seems modest if such generalization does not cause new difficulty in analysis, which the authors should explain somewhere after introducing it.

  3. While the generalization bounds can be tight in some applications as shown in Section 5, they all require ERM algorithms and the underlying probability distribution (e.g., Gaussian or Bernoulli distribution). These requirements would somewhat limit the practical value of the results established, since in most real applications neither is accessible. That said, I understand this issue can be hard to address in general under the mild assumptions and information-based analysis, but providing at least one concrete example with non-ERM algorithm would be much appreciated.

Questions for authors

See the weakness dicussion above. Additionally, I would also like to ask the following questions:

  1. Most results established in the paper involve I(W;Zi∣Wi′)I(W;Z_i\mid W_i'), which is a bit abstract just looking at its definition. Could you add some explanation or visualization of this quantity (e.g., when it is small)? This would improve the readability to readers not familiar with this concept.

  2. The weaker version of uniform stability as in Eq. (1) is not considered in the main results, can you explain if it fits into Theorem 2? also, can it be placed somewhere in the hierarchy map in Figure ?

  3. In the abstract, the sentence "These conditions are weaker than established notions of stability..." seems a bit overstated in its current form. Can you specify the comparison or revise it?

  4. One minor suggestion regarding the presentation of in Definitions 2 and 5. It is more rigorous to specify "let ff be as defined in Definition 1" rather than saying "defined above" to avoid ambiguity.

3 comments

We thank the reviewer for the helpful suggestions on clarification and presentation. Our responses aim to distinguish our contribution from the existing literature. Below, we respond to your questions and concerns point-by-point.

W1 - Comparison with Agrawal & Horel (2021)

We thank the reviewer for this question. Please notice that Agrawal and Horel (2021) does not study the generalization error of learning algorithms (in particular, there are no results on generalization error in this paper). The cited lemma is used as a proof step in our paper for Corollary 4.

W2 - Comparison with Kale et al. (2011)

We thank the reviewer for this observation. Similar to the above, this definition was introduced in Kale et al. (2011) to study cross-validation. To the best of our knowledge, we are the first to apply this mean-square stability and further extend it to develop generalization bounds. We agree that extending the mean-square stability to p>1p>1 is not, by itself, a major technical contribution. This extension plays the role of connecting the stability condition to an ff-information generalization bound, which we view as our main contribution.

W3 - Non-ERM examples

Thank you for this suggestion. The new Section 5.4 now includes regularized learning in reproducing kernel Hilbert spaces (RKHS) and a logistic-regression example. These learners are typical non-ERM algorithms as they minimize empirical loss plus a regularization term. Our new analysis provides an explicit bound (Theorem 3) on the proposed mean-pp-norm stability. Furthermore, we also provide a new example of regularized logistic regression to exhibit a wider applicability of our stability analysis. In this example, the bounded-kernel assumption of Bousquet & Elisseeff (2002, Theorem 22) does not hold, while our new bound applies. The numerical comparison in Section~5.4 reports a tighter proposed bound than the evaluated ISMI bound. Hence, our bound outperforms both classical stability-based and information-theoretic bounds, which demonstrates the benefit of their combinations.

Q1 - Evaluation of information measure

Appendix L now explains that I(W;Zi∣Wi′)I(W;Z_i | W_i') measures the information the original hypothesis WW reveals about ZiZ_i when the neighboring hypothesis Wi′W_i' is known. We also compares it with the existing information measures, including ISMI (Bu et al., 2020), erasure information (Raginsky et al., 2016), and sample-conditioned hypothesis CMI (Wang & Mao, 2023), and χ2\chi^2-information. Numerical evaluations of these quantities are provided in Appendix M, N, O for specific examples. In particular, for the Gaussian mean estimation, the information term tends to 12log⁡2\frac12\log2 while the stability factor decreases as 1n\frac1n. This implies that small stability parameters do not necessarily imply small information measures, illustrating the separate roles of stability and information in our bounds.

Q2 - Weaker uniform stability

For deterministic learning algorithms, Eq. (1) coincides with Eq. (11). However, for general randomized algorithms, Eq. (1) cannot fit into Theorem 2 and thus is not placed in the hierarchy graph.

Q3 - Clarifying abstract

We agree that the comparison should be specific. The revised abstract now states that the proposed conditions are implied by strong uniform stability. This identifies the relation established by the hierarchy in Figure 1, rather than suggesting that our conditions are weaker than every existing notion of stability.

Q4 - Clarifying definitions

Thank you for the suggestion. Definitions 2 and 5 now refer explicitly to Definition 1.

Thank you for the detailed reply. My Q1–Q4 are now largely resolved. Appendix L answers my question on I(W;Zi∣Wi′)I(W;Z_i\mid W_i'), and the abstract and definitions are now precise. I also appreciate the honesty on W2 and the new Section 5.4. However, I still have the following concerns.

1. Example 4 (W3). Theorem 3 and its proof look correct to me. However, the rebuttal's claim that the bound outperforms classical stability-based bounds does not hold. Evaluating the Lipschitz loss at the training point and combining (8) with your (159) gives a bound without any information term:

gen‾≤σ22λn(E[K(X,X)]+(E[K(X,X)])2)≤σ2E[K(X,X)]λn.\overline{\mathrm{gen}}\le\frac{\sigma^2}{2\lambda n}\Bigl(\mathbb{E}[K(X,X)]+\bigl(\mathbb{E}[\sqrt{K(X,X)}]\bigr)^2\Bigr)\le\frac{\sigma^2\mathbb{E}[K(X,X)]}{\lambda n}.

This is a classical stability argument taken in expectation, which needs no bounded kernel. In Example 4 it gives d/(λn)=20/nd/(\lambda n)=20/n, the β\beta of Theorem 3 at p=2p=2. Bound (163) multiplies this β\beta by the average of Iχ2(W;Zi∣Wi′)\sqrt{I_{\chi^2}(W;Z_i\mid W_i')}, so it can beat 20/n20/n only when that average is below 1. Reading Figure 3, the plotted χ2\chi^2-bound is about 1.5-2.2 times 20/n20/n at every nn. Please add this baseline to Figure 3 and qualify the statement that classical stability analysis does not apply. Please also describe the Monte Carlo estimator of the information measures and its accuracy.

2. Positioning (W1, W2). I agree that Agrawal & Horel (2021) do not study generalization. My concern is on the technical side. Their Corollary 44 shows that Λf;g≤ψ\Lambda_{f;g}\le\psi under ν\nu implies Df(μ∥ν)≥ψ∗(μ(g)−ν(g))D_f(\mu\Vert\nu)\ge\psi^{\ast}(\mu(g)-\nu(g)) for every μ\mu. Theorem 2 applies this with μ=PW,Wi′,Zi\mu=P_{W,W_i',Z_i}, ν=PW,Wi′PZi\nu=P_{W,W_i'}P_{Z_i} and g=Δg=\Delta. For p=2p=2, Corollary 3 is their Example 10, the Hammersley–Chapman–Robbins bound. For general pp, both terms in (24) follow from Hölder's inequality applied to Eμ[Δ]=Eν[(dμ/dν−c)Δ]\mathbb E_\mu[\Delta]=\mathbb E_\nu[(\mathrm{d}\mu/\mathrm{d}\nu-c)\Delta] with c=1c=1 and c=0c=0. This specialization is useful, but the paper should say so. A short paragraph separating the imported inequality from the new elements (replace-one coupling, centering (10), stability conditions, examples) would make the contribution clear. On W2, Definition 9 is the replace-one form of the LqL^q stability of Celisse & Guedj (2016, arXiv:1608.06412). Abou-Moustafa & Szepesvári (ALT 2019) describe that notion as extending mean-square stability to higher moments, and they use it for generalization bounds. Please cite these works and adjust the novelty claim.

Overall, the revision improves the paper. However, my main concerns about novelty and the advantage over existing bounds remain, so I remain my score for now.

Q1 - Example 4

Thank you for deriving the new bound and pointing out that it is tighter in Example 4. We argue that this new result would not weaken our contributions for the following reasons.

  • Theorem 3 gives finite stability control in settings where the direct bound is vacuous. The new bound requires E[K(X,X)]<∞\mathbb E[K(X,X)]<\infty, while Theorem 3 requires E[K(X,X)p/2]<∞\mathbb E[K(X,X)^{p/2}]<\infty for the chosen p>1p>1. For 1<p<21<p<2, take the scalar linear kernel K(x,x′)=xx′K(x,x')=xx' and a Pareto covariate X≥1X\geq1 with Pr⁡(X>t)=t−a\Pr(X>t)=t^{-a} for t≥1t\geq1, where p<a<2p<a<2. Then E[K(X,X)p/2]=E[Xp]<∞\mathbb E[K(X,X)^{p/2}]=\mathbb E[X^p]<\infty, but E[K(X,X)]=E[X2]=∞\mathbb E[K(X,X)]=\mathbb E[X^2]=\infty. This way, Theorem 3 gives finite mean-pp-norm stability, whereas the direct bound is vacuous.

  • Corollary~3 can improve on the direct bound. Consider one-dimensional ridge logistic regression with XX uniform on {−1,1}\{-1,1\} and Y∼Bernoulli⁡(1/2)Y\sim\operatorname{Bernoulli}(1/2) independent of XX. It can be exactly calculated that Iχ2(W;Zi∣Wi′)=(n+1)/(2n)I_{\chi^2}(W;Z_i\mid W_i')=(n+1)/(2n) and Corollary 3 gives 1λnn+12n\frac{1}{\lambda n}\sqrt{\frac{n+1}{2n}}, which is tighter than the direct bound 1λn\frac{1}{\lambda n}.

  • Contribution of Theorem 3. The main purpose of Example 4 is to demonstrate two benefits of our framework over the conventional approaches. Compared with the classical uniform stability result of Bousquet & Elisseeff (2002, Theorem 22), Theorem 3 gives an explicit stability guarantee for an unbounded kernel. Compared with the ISMI bound, our numerical evaluation gives a tighter result as shown in Figure 3. It is helpful to optimize the parameter setting to find the superiority over the direct bound, but we believe the current results are illustrative enough. Beyond Example 4 that we consider in our paper. The new binary example above gives an exact case in which the information measure improves on the corresponding direct stability bound.

  • Monte Carlo estimator We have illustrated our simulation setup in Appendix Q.3.

Q2 - Corollary 3 as a specialization

Thank you for pointing out these connections. We agree that Hölder’s inequality and the Hammersley–Chapman–Robbins inequality can be applied to prove Corollary 3. However, we prefer to state and prove Corollary 3 as a specialization of Theorem 2 because this shows how mean-pp-norm stability fits into the same variational framework as our other stability conditions. We have added such connections in Appendix I.

Q3 - Stability definition

Thank you for pointing us to the earlier LqL_q-stability literature. The existing LqL_q-stability is based on the delete-one setting while ours is built on the replace-one setting. We have cited both works and clarified this distinction. However, to the best of our knowledge, Corollary 3 is the first bound on the expected generalization error that combines this replace-one LqL_q-stability condition with an information measure. We view such combinations as valuable and as our main contribution.

Reviewer_5p2kOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper introduces new notions of algorithmic stability, which are a weakening of the uniform notion of stability. Subsequently, it employs these notions to establish information-theoretic generalization bounds that bridge between stability-based generalization bounds and information-theoretic ones. The new notion is reminiscent of weakening the notion of Lipschitz random process to the notion of sub-Gaussian random process in the high-dimensional probability texts (e.g. van Handel HDP lecture notes), if we endow the space with the Hamming metric.

Critical strengths

The new notion of stability is theoretically interesting, and the generalization bounds unify some primary results on information-theoretic generalization bounds and stability-based ones.

Critical weaknesses

The paper seems stronger as a conceptual framework than as a technically deep or broadly applicable result.

The main inequalities are fairly direct. The derivation of Lemma 2 as the fundamental building block of other concepts begins with a standard step. The variational formula is widely used in all information-theoretic proofs of generalization. The only notable difference lies in the specific variation formula employed (Lemma 5), which is less frequently utilized in other research. However, when applied to KL divergence, it becomes the well-known Donsker-Varadhan formula.

Verifiability is the principal weakness and the examples are restrictive. Defining stability through an MGF bound does not itself explain how to establish stability for learning algorithms.

There are really two quantities to control:

  • the tail or moment behavior of Δ\Delta;
  • the conditional information I(W;Zi∣Wi′)I(W;Z_i\mid W_i').

The Gaussian example is useful as a consistency check and an illustration of cancellation in the loss difference. But exact Gaussian calculations do not establish that the framework is tractable beyond special models. Also, matching the 1/n1/n rate in such an example is weaker evidence than proving a broadly applicable sufficient condition.

I would want a result for, say, regularized ERM or a class of iterative algorithms, deriving these quantities from recognizable assumptions rather than calculating them exactly.

Questions for authors
  1. The Bernoulli example demonstrates that the bound presented in the paper can surpass the basic CMI bound. In comparison, how do the bounds in the paper compare to the CMI (and its recent generalizations) in general, or at least in more realistic scenarios?

  2. The literature definition of subGamma does not impose the constraint t>0t>0 (see “Concentration inequalities: A Nonasymptotic Theory of Independence”). Regarding this, two notions of subExp and subGamma are equivalent: (β,b)(\beta,b)-SubExp yields (β,b)(\beta,b)-SubGamma (which is stated in the paper). However, (β,c)(\beta,c)-SubGamma also implies (β/2,2c)(\sqrt{\beta/2},2c)-SubExp. Could you please explain why Corollaries 1 and 2 appear different at least in certain regimes of β\beta and cc? Is it because of the t>0t>0 constraint?

  3. In general, any conditional probability PA∣BP_{A|B} can be represented as a function A=h(A,R)A=h(A,R), where RR can be considered as local randomness. However, this representation is not unique. The Definition 7 stipulates that the local randomness used to generate WW and W’iW’_i must be identical. Since RR is not unique, we can imagine different coupling between WW and W’iW’_i. How can this coupling be incorporated into the definition? In this way, it may possible to get sharper bounds using optimal coupling in some sense.

  4. The statement of Lemma 2 is not precise. Its proof shows that the prior QWW’iQ_{WW’_i} should have same marginals. Further, W~\tilde{W} is not required to be a copy of WW.

1 comment

We thank the reviewer for the thoughtful review which has motivated us to strengthen the paper substantially by including applications to practical learning scenarios. We provide detailed responses to the reviewer's comments below.

W1 - The main inequalities are fairly direct We agree that the variational change-of-measure argument is a standard tool. We view the most valuable insight of this work as the possibility of combining the two notions (stability and information measure), although the two notions have been explored separately for a long time. Our contribution is to apply the variational change-of-measure formulas to connect stability conditions with ff-information measures. The resulting generalization bounds can capture benefits from both notions and better characterize the generalization error.

W2 - Verifiability is the principal weakness and the examples are restrictive

We agree that both quantities should be controlled. Section 5.4 now addresses the stability component for the class of regularized learning in reproducing kernel Hilbert spaces (RKHS). Our new analysis establishes an explicit bound (Theorem 3) for the proposed mean-pp-norm stability from recognizable assumptions. We also present a specific regularized logistic regression example, where our new theorem gives β≤dλn\beta \leq \frac{d}{\lambda n} while the previous stability analysis of Bousquet & Elisseeff (2002, Theorem 22) does not apply. For the information measure, it is difficult to provide an analytical bound. This is the common limitation for all information-theoretic bounds, as mentioned in our limitation discussions. We therefore empirically estimate the χ2\chi^2-information for the logistic regression example. The numerical comparison in Section 5.4 reports a tighter proposed bound than the evaluated ISMI bound. The new theorem supplies an explicit stability control, while bounding the information term more broadly remains an open part of the analysis.

Q1 - Comparison with CMI bounds

We have added Appendix L to compare the information measures. The new Proposition 1 specifies the improvement from the CMI measure. In particular, using the same strong uniform stability parameter, the specialization of the CMI bound from Wang & Mao (2023, Theorem 4.1) is no looser than the corresponding specialization of Theorem 1. Beyond this common assumption, the considered bounds involve different forms of stability notions, and hence the information comparison alone does not determine their relative tightness. In Section 5.2, Figure 2 now evaluates the HC-CMI bound of Wang & Mao (2023, Theorem 4.1) and ff-CMI bound of Wang & Mao (2024, Theorem 4.1). It is observed that the proposed Corollary 3 is still tighter than the recent CMI bounds for the considered setting.

Q2 - Implications between stability notions

We have checked Section 2.4 of the textbook referred by the reviewer and find that the subGamma is defined for 0<λ<1/c0<\lambda<1/c. With λ\lambda replaced by tt, the definition in our paper is consistent with the right-tail definition from the textbook. Using this right-tail definition, we assert the implication from (β,c)(\beta,c)-SubGamma to (β/2,2c)(\sqrt{\beta/2},2c)-SubExp does not hold.

Q3 - Coupling of neighbouring hypotheses

We agree that the coupling matters. Our definitions use a particular setting where W=A(Z[n],R)W=\mathcal A(Z_{[n]},R) and Wi′=A(Z[n]∼i,R)W_i'=\mathcal A(Z_{[n]\sim i},R) share the common randomness RR. The resulting stability and information terms rely on that coupling. Changing couplings could also change both terms, and thus an extension would optimize the complete bound over different couplings. We will clarify the role of the chosen coupling and identify its optimization as future work.

Q4 - Clarifying Lemma 2

Thank you for identifying the ambiguity. The revised statement of Lemma 2 now explicitly imposes QW=QWi′=PWQ_W=Q_{W_i'}=P_W.

Reviewer_94PMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents generalization bounds based on the concept of algorithmic stability and information theory for algorithms under i.i.d. data assumption. For contributions, according to my understanding, it provides two types of information theory-based upper bounds and presents several new stability definitions that are weaker than the uniform stability and impose less limiting requirements on the learning algorithm such that endowing wilder applicability. The paper is mainly focus on theoretical contributions, thereby there is no related validations.

Critical strengths

By my own view, the paper has two advantages: the first is building the connection between information theory and stability, and the other is deriving bounds without the bounded ℓ\ell assumption. And I consider the last is quiet interesting, as the bounded ℓ\ell is basically a common setup in many recent studies on learning theory, particularly for those based on the concentration inequalities.

Critical weaknesses

I am very delight that the paper gives the angle from the stability and information theory to the generalization bounds, and me-self happens to be very familiar with both these two aspects. However, there are several issues should be noticed, and I hope that all can be addressed during the rebuttal.

  1. Since the definition on uniform stability is directly related with the datasets Z[n]Z_{[n]} and Z[n]∼iZ_{[n] \sim i}, then it follows directly by McDiarmid's inequality [1]: P[L(W)−L^(W)≥ϵ]≤e−2ϵ2∑i=1nβ2.{\mathbb P}[L(W) - \hat L(W) \ge \epsilon ] \le e^{\frac{-2 \epsilon^2}{\sum^n _{i=1} \beta^2 } } . This is also does not depend on the bounded ℓ\ell assumption, and this bound will be tighter when β≤M\beta \le M comparing with Hoeffding's type bounds, where 0≤ℓ≤M0 \le \ell \le M. The paper focus on the information-type bound, then how it can be tighter than exponential decay bounds? Consequently, the related lower bounds should be provided for the tightness.

  2. About the strong stability definition (Definition 6) in the paper, the dentition in [1] on the uniform stability is defined on A(Z[n]∖i)A(Z_{[n]\setminus i}) instead of A(Z[n]∼i)A(Z_{[n]\sim i}). Please clarify this change.

  3. I suppose that the paper introduces the sub-Gaussian condition for weakening the bounded ℓ\ell assumption. By the paper introduces many sub-Gaussian related stability definitions, there are new parameters, such as tt, pp, and bb. Thus, I wonder what the advantages for these parameters comparing the solely bounded ℓ\ell assumption are.

  4. The last that I argue is the most important. For algorithmic stability, the main core is to find β\beta. For example, in [1], the kk-NN classifier w.r.t. 0,1\\{0, 1\\}-loss has hypothesis stability β≤4mk2π,\beta \le \frac{4}{m}\sqrt{\frac{k}{2 \pi}}, where mm denotes the number of samples. In [2], the structural risk minimization algorithm has error stability β≤2σ2κ2λEN+β∗,\beta \le \frac{2 \sigma^2 \kappa^2}{\lambda EN} + \beta ^{*}, where $ E N $ denotes the number of samples and $\beta ^{*} $ is assumed to be the optimal stability. However, despite providing many upper bounds for the generalization error, the paper let β\beta remain unexplored. Namely, I suppose that the paper does not get the deeper understanding on the concept of stability.

[1]. Bousquet O, Elisseeff A. Stability and generalization. Journal of machine learning research. 2002;2(Mar):499-526.

[2]. Zheng H. Can Domain Generalization be Guaranteed in Small-Sample Learning?. arXiv preprint arXiv:2609.39512. 2026 Sep 30.

Questions for authors

Please, refer to the above weaknesses. If all the above can be addressed during the rebuttal, I can rise the score.

2 comments

We thank the reviewer for the constructive questions about stability and the applicability of our bounds. Our responses clarify the tightness of the bounds, the definition of the replace-one setting, and the advantage of stability beyond bounded loss functions. The new analysis on regularization in reproducing kernel Hilbert space (RKHS) provides an explicit stability bound. In the following, we give a detailed point-by-point response to your comments.

W1 - Justification of tightness

  • Unlike (Bousquet & Elisseeff, 2002) which mainly focuses on the uniform stability with bounded loss functions, the contribution of our work goes beyond by introducing weaker stability notions that can be applied to unbounded loss functions. Examples 1,2 and 4 provide several learning scenarios where the loss function is unbounded and the uniform stability does not hold. In such examples, the proposed bounds still apply and some of them are asymptotically tight up to a constant.

  • For tightness justifications, Appendix M.4 gives an information-based lower bound of order 1n\frac{1}{n}, matching the exact Gaussian generalization error 2σ2n\frac{2\sigma^2}{n}. This implies that our upper bound can be exactly tight in some cases.

W2 - Inconsistent definitions

Thank you for pointing out the distinction. Bousquet & Elisseeff (2002) defined the uniform stability based on the delete-one dataset Z[n]∖iZ_{[n]\setminus i}, while our Definition 6 uses the replace-one dataset Z[n]∼iZ_{[n]\sim i}, following Wang and Mao (2023). The revised definition now cites the latter source.

W3 - Advantages of stability notions

  • The advantage is that we control the change in loss caused by replacing one training sample, rather than requiring the loss itself to be bounded. The loss difference can have finite moments or controlled tails even when the loss is unbounded, as in Gaussian mean estimation with quadratic loss. In such cases, our results can provide useful bounds.

  • The parameters play different roles: β\beta describes the scaling law of the loss difference Δ\Delta, bb or cc controls the range of the moment bound of Δ\Delta, pp specifies the available moment. Figure 1 and Lemmas 1, 3, and 4 describe how the conditions and parameters relate, providing a path to determine which generalization bound can be used.

W4 - Control of stability

We agree that explicit control of the stability parameter is essential. To address this, we have now added a new section, Section 5.4, which presents an analysis of regularization learning algorithms, following the setup of Bousquet & Elisseeff (2002, Section 5.2). Our new analysis provides an explicit bound (Theorem 3) on the proposed mean-pp-norm stability from a recognizable assumption on the kernel. Furthermore, we also provide a new example of regularized logistic regression to exhibit a wider applicability of our stability analysis. In this example, the bounded-kernel assumption of Bousquet & Elisseeff (2002, Theorem 22) does not hold, while our new bound applies. The numerical comparison in Section 5.4 reports a tighter proposed bound than the evaluated ISMI bound. Hence, our bound outperforms both classical stability-based and information-theoretic bounds, which demonstrates the benefit of their combinations.

Thank you for your feedback, and I think the novelty of the paper is sufficient. However, for the first question, I originally mean that, since your bounds is an information type instead of a concentration type, the corresponding lower bounds are necessary for the tightness rather than examples. For the last question, I originally expect that the novel bound for β\beta may be presented based on the information theory, instead of imitating the β\beta bound by Bousquet et al. Moreover, the β\beta bound in the revision only holds in the limit, i.e., lim⁡t→0+[⋅]\lim _{t \to 0^+} [\cdot]. I think the new angle for the β\beta bound will significantly contribute the ML studies. Thus, I will remain my score unchanged.

Reviewer_KNAfOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies information-theoretic generalization bounds for stable learning algorithms. Based on the neighboring-hypothesis construction of Wang and Mao (2023), it applies a generalized ff-divergence framework to the loss difference between models trained on neighboring datasets. The resulting bounds use sub-Gaussian, sub-exponential, sub-gamma, and finite-moment stability conditions, which generalize or relax several assumptions in previous work. Applications cover Gaussian and Bernoulli mean estimation and scalar linear regression.

Critical strengths
  1. Controlling the neighboring loss difference under the decoupled distribution is a useful technique. In particular, the moment-based bounds remain applicable to quadratic losses with Gaussian data, where uniform loss-difference bounds are unavailable.
  2. The unified treatment makes the tradeoff between assumptions on the loss difference and the chosen information measure explicit. The analytical examples provide calculations that can be checked against known generalization errors.
  3. Theorem 1 provides a valid counterpart to the rightmost bound in Wang and Mao (2023, Theorem 3.1), using the same conditional mutual information term I(W;Zi∣Wi′)I(W;Z_i\mid W'_i) while replacing SCH-A stability with a sub-Gaussian condition on the neighboring loss difference under the decoupled distribution. Appendix O also provides convincing counterexamples to the Section 3 claims of Wang and Mao (2023). The difference between unconditional independence and independence conditional on the learned hypothesis is important and correctly identified.
Critical weaknesses
  1. While Appendix O correctly identifies failures in the Section 3 MI bounds of Wang and Mao (2023), the applicable CMI bounds, particularly Theorem 4.1, should also be compared. Let Ti=(W,Wi′)T_i=(W,W'_i), Ji=I(Z^i;Ui∣Ti)J_i=I(\hat Z_i;U_i\mid T_i), and Ki=I(W;Zi∣Wi′)K_i=I(W;Z_i\mid W'_i), where Z^i=Zi\hat Z_i=Z_i for Ui=0U_i=0 and Z^i=Zi′\hat Z_i=Z'_i for Ui=1U_i=1, with UiU_i an independent fair bit. Under the replace-one construction with shared algorithmic randomness, exchangeability and the chain rule give Ki=Ji+I(Ti;Z^i)K_i=J_i+I(T_i;\hat Z_i). Thus, with the same strong-uniform stability parameter β\beta, the specialization of their Theorem 4.1, βn∑i2Ji\frac{\beta}{n}\sum_i\sqrt{2J_i}, is no larger than the corresponding specialization of Theorem 1 in this paper. Additionally, in Example 2, the first part of their Theorem 4.1 gives exactly 2θ(1−θ)2log⁡2n\frac{2\theta(1-\theta)\sqrt{2\log 2}}{n} as its RHS for every n≥1n\geq1 and θ∈(0,1)\theta\in(0,1). Here E[Δ1(Ti)]=2θ(1−θ)/n\mathbb E[\Delta_1(T_i)]=2\theta(1-\theta)/n, and the pointwise CMI equals log⁡2\log 2 when W≠Wi′W\ne W'_i and zero otherwise. Evaluating Corollary 3 with p=2p=2 using the exact quantities in Eqs. (102) and (113) improves this constant asymptotically at θ=1/2\theta=1/2, but gives an asymptotically looser bound at θ=0.1\theta=0.1.

  2. Note that Eq.(20) in Corollary 1 is incorrect as stated. Let v=I(W;Zi∣Wi′)v=I(W;Z_i\mid W'_i). Taking the infimum of v/t+β2t/2v/t+\beta^2t/2 over 0<t<1/b0<t<1/b gives β2v\beta\sqrt{2v} when v≤β2/(2b2)v\leq\beta^2/(2b^2), and bv+β2/(2b)bv+\beta^2/(2b) otherwise, as Appendix F, Eq. (44), itself states. This is not the minimum of the two expressions, and clearly the affine expression is always at least the square-root expression. The stated bound can fail within the paper's learning setup. For example, take n=1n=1, ZZ uniform on 16 symbols, W=Z1W=Z_1, and ℓ(w,z)=1{w≠z}\ell(w,z)=\mathbf 1\{w\ne z\}. Then gen=15/16\mathrm{gen}=15/16 and v=log⁡16v=\log16. The algorithm satisfies the sub-exponential stability condition in Definition 8 with β=3/8\beta=3/8 and b=1b=1, under the decoupled distribution, log⁡E[etΔ]=log⁡[1+15128(cosh⁡t−1)]≤9t2128,∣t∣<1.\log\mathbb E[e^{t\Delta}]=\log\left[1+\frac{15}{128}(\cosh t-1)\right]\leq\frac{9t^2}{128},\qquad |t|<1. However, Eq. (20) gives approximately 0.8830.883, below 15/16=0.937515/16=0.9375. Please replace Eq. (20) with the piecewise bound and check its downstream uses.

  3. The demonstrated applicability is relatively limited to mean estimation and scalar linear regression. I consider the correction of Wang and Mao (2023) and the extension to weaker stability assumptions and ff-information valuable, which makes me lean toward acceptance. However, a broader application would help establish the significance of the framework. For example, [R1] and [R3] identify limitations of specific MI/CMI bounds in stochastic convex optimization, while [R2] shows that projection and quantization can overcome some such limitations. An analysis or discussion of one representative SCO setting, including any obstacles to applying the framework, would clarify when the proposed bounds improve on existing approaches and whether the gain comes from stability control, the information measure, or their combination.

Questions for authors

Questions For Authors:

  1. Can you correct Eq. (20) to the piecewise expression in Eq. (44) and confirm which subsequent statements and evaluations are affected?
  2. Can you add a direct comparison with Wang and Mao (2023, Theorem 4.1), including the explicit bound above for your Bernoulli example? Which improvements arise from weaker assumptions or smaller stability parameters, and which arise from a different information measure?
  3. What is the precise sampling model and population-risk definition in Example 3? Which assumptions on the sequence of designs justify the stated asymptotic rates and constants?
  4. Could you compare the proposed framework with [R4], which develops conditional ff-information bounds for unbounded losses, including finite-moment or Hölder specializations? The two frameworks use different loss differences and reference distributions, but there is a concrete common benchmark: for Bernoulli mean estimation with θ=1/2\theta=1/2, the C=0C=0, q=1q=1, α=β=2\alpha=\beta=2 specialization of its Theorem 4.1 obtains the exact generalization error 1/(2n)1/(2n), since both E[(ΔLi)2]\mathbb E[(\Delta L_i)^2] and Iχ2(ΔLi;Ui)I_{\chi^2}(\Delta L_i;U_i) equal 1/(2n)1/(2n). Here ΔLi\Delta L_i is the loss difference defined in [R4], rather than the neighboring-hypothesis loss difference in the present paper. This holds for every nn, whereas the present Corollary 3 evaluated at p=2p=2 is only asymptotically exact.

[R1] Idan Attias et al. "Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization, and Tracing." ICML 2024.

[R2] Milad Sefidgaran, Kimia Nadjahi, and Abdellatif Zaidi. "Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization." NeurIPS 2025.

[R3] Mahdi Haghifam et al. "Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization." ALT 2023.

[R4] Ziqiao Wang and Yongyi Mao. "Generalization Bounds via Conditional f-Information." NeurIPS 2024.

3 comments

We sincerely appreciate the reviewer for the careful technical assessment and helpful comparisons. In the following, we give a point-by-point response to the reviewer's comments.

W1 - Comparison with CMI

  • Thank you for this careful comparison. Proposition 1 and Appendix L now establish the information comparison. We agree that, with the same strong uniform stability parameter, Wang and Mao (2023, Theorem 4.1) is no larger than the corresponding specialization of our Theorem 1. Beyond this common assumption, the considered bounds involve different forms of stability notions, and hence the information comparison alone does not determine their relative tightness.

  • Section 5.2 and Figure 2 now compare Corollary 3 with the CMI bound of their Theorem 4.1. In Figure 2, our Corollary 3 with p=2p=2 is tighter for the considered setting. We stress that this gain comes from the stability control which compensates for a larger information term.

W2 - Incorrect statement

Thank you for identifying this error and providing a counterexample. In Corollary 1 of the revised manuscript, we have revised Eq. (20) by using the piecewise function rather than the minimum of the two expressions. We have confirmed that all reported evaluations are unaffected.

W3 - Applicability of bounds

  • Thank you for suggesting these references. We agree that a broader application is needed to demonstrate how the stability assumptions can be verified. Section 5.4 now provides an analysis for regularized learning in reproducing kernel Hilbert spaces (RKHS). Our new analysis allows for unbounded kernels which is not permitted in the previous stability analysis of Bousquet & Elisseeff (2002, Theorem 22). We also present a regularized logistic regression example where our bound can be much tighter than the ISMI bound.

  • The above addition addresses the stability side of the framework. However, it does not resolve the common limitations of information-theoretic bounds in the SCO setting you mention. In particular, our information term still needs a separate bound. We consider such extensions in a future research avenue (which is openly discussed in the Limitations section).

Q1 - Correcting Corollary 1

Yes. Corollary 1 now states the correct piecewise expression. We have confirmed that all reported evaluations are unaffected.

Q2 - Comparison with Wang and Mao (2023)

Yes. Appendix L now establishes I(Z^i;Ui∣W,Wi′)≤I(W;Zi∣Wi′)≤Iχ2(W;Zi∣Wi′)I(\hat Z_i;U_i\mid W,W_i')\leq I(W;Z_i\mid W_i')\leq I_{\chi^2}(W;Z_i\mid W_i').

  • With the same strong uniform stability parameter, the CMI bound of Wang and Mao (2023, Theorem 4.1) is no larger than the corresponding specialization of our Theorem 1. Beyond this common uniform stability assumption, the considered bounds involve different forms of stability notions, and hence the information comparison alone does not determine their relative tightness.

  • Corollary 3 instead uses the larger χ2\chi^2-information, which, however, does not necessarily degrade the complete bound. As shown in Figure 2, the proposed χ2\chi^2-information bound is tighter than the CMI bound, despite using the larger χ2\chi^2-information. This implies that the gain arises from the stability control and compensates for the looser information measure. Separately, the proposed weaker mean-square stability condition allows a wider range of applications where the SCH-C stability and its bounds do not apply, as Examples 1 and 3 illustrate.

Q3 - Linear regression model

  • The calculations in Example 3 use a fixed-design model: x1,…,xnx_1,\ldots,x_n are deterministic and Yi=w∗xi+NiY_i=w^*x_i+N_i, with independent Ni∼N(0,σ2)N_i\sim\mathcal N(0,\sigma^2). The observations YiY_i are independent but generally not identically distributed when the features xix_i differ. Our description of them as i.i.d. was therefore inaccurate. We have revised our statement using "independent" instead of "i.i.d."

  • The general expected population risk is formally defined in line 33. In the linear regression example, the expected population risk is defined accordingly as EWEN[(Y−Wx)2]\mathbb E_W \mathbb E_N [(Y - W x)^2], where WW is the ERM output calculated by W=w∗+∑i=1nxiNi∑i=1nxi2W = w^* + \frac{\sum_{i=1}^n x_i N_i}{\sum_{i=1}^n x_i^2}, Y=w∗x+NY = w^* x + N and NN is an independent Gaussian noise. We omitted this specialization due to space limit.

  • As required by the calculations of the bounds, we assume that Cn=max⁡i∣xi∣min⁡i∣xi∣C_n=\frac{\max_i|x_i|}{\min_i|x_i|} is bounded. A sufficient design assumption is ∣xi∣<∞|x_i| < \infty for each i∈[n]i \in [n].

Q4 - Comparison with Wang and Mao (2024)

  • Thank you for pointing out this relevant comparison. We refer to Wang & Mao (2024, Theorem 4.1) as the ff-CMI bound. Their framework considers the loss difference between two supersamples (Zi,Zi′)(Z_i, Z'_i) evaluated at the same learned hypothesis WW, whereas ours uses the loss difference between two neighboring hypotheses (W,Wi′)(W, W'_i) at the same sample ZiZ_i. The resulting moment conditions and information measures therefore differ. In this sense, it is hard to compare two bounds in general.

  • We agree that the Bernoulli example provides a concrete benchmark for the comparison of two bounds. Figure 2 now includes the specialized ff-CMI bound with C=0C=0, q=1q=1 and α=β=2\alpha=\beta=2, evaluated at θ∈{0.1,0.4}\theta \in \{0.1, 0.4\}. Although this specialization is exactly tight at θ=0.5\theta=0.5, our numerical results show that Corollary 3 is significantly tighter at larger nn for the considered values of θ\theta. Other parameter choices may improve the ff-CMI bound, but optimizing over these choices is computationally intractable in our evaluation. We therefore do not claim that our bound is tighter than the fully optimized bound. However, since our result is asymptotically tight, improvement from such optimizations would be limited to a constant factor. We would welcome further discussion for this comparison if needed.

Reviewer_KNAfOpenReview ↗

On your rebuttal

Thank you for the detailed response, and my main concerns are addressed. One minor clarification remains, that is, in Example 3, pointwise finiteness of ∣xi∣|x_i| alone may not ensure that CnC_n is uniformly bounded as nn grows. I would suggest to state the required uniform assumption explicitly.

Overall, I remain inclined to recommend acceptance.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of main changes in the revised version

We sincerely thank the reviewers for the time and effort they have devoted to providing comments that have helped us to make substantial improvements to the paper. We have paid particular attention to the shared concern regarding the practical applicability issue in our original submission. In this post, we briefly summarize the main changes we have made to the paper (new and revised texts are highlighted in blue in the uploaded manuscript). For detailed responses to individual comments made by the reviewers, please see our comments posted on each of the reviews.

  • Comparisons with existing works. We have added numerical comparisons in Section 5.2 and theoretical comparisons in Appendix L. These better justify the benefit of the proposed framework.
  • Stability analysis for regularized learning. We have added a new section, Section 5.4, to show that our framework enables a stability analysis of regularization learning algorithms. This addresses the most emphasized concern about verifying our stability condition beyond the original examples.
  • Example of regularized logistic regression. We have added a new practical example of regularized logistic regression (Example 4) where the existing results are either inapplicable or significantly looser.
  • Clarifications and discussions. We now also make clarifications and add additional discussions to address the other concerns raised by the reviewers. For details, see our individual responses to the reviews below.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.