- 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 -divergences and generalized cumulant generating functions (CGFs). Assuming different stability notions, more concrete bounds are obtained with different -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
-
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.
-
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 -divergences. Moreover, it can imply tight bounds in some practical applications, e.g., the three examples considered in Section 5.
-
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
-
Generalization bounds using -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.
-
The mean-p-norm stability introduced in Def 9 generalizes the mean-square stability (Kale et al., 2011) by allowing rather than . This contribution seems modest if such generalization does not cause new difficulty in analysis, which the authors should explain somewhere after introducing it.
-
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:
-
Most results established in the paper involve , 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.
-
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 ?
-
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?
-
One minor suggestion regarding the presentation of in Definitions 2 and 5. It is more rigorous to specify "let be as defined in Definition 1" rather than saying "defined above" to avoid ambiguity.
3 comments
Thank you for the detailed reply. My Q1–Q4 are now largely resolved. Appendix L answers my question on , 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:
This is a classical stability argument taken in expectation, which needs no bounded kernel. In Example 4 it gives , the of Theorem 3 at . Bound (163) multiplies this by the average of , so it can beat only when that average is below 1. Reading Figure 3, the plotted -bound is about 1.5-2.2 times at every . 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 under implies for every . Theorem 2 applies this with , and . For , Corollary 3 is their Example 10, the Hammersley–Chapman–Robbins bound. For general , both terms in (24) follow from Hölder's inequality applied to with and . 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 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 , while Theorem 3 requires for the chosen . For , take the scalar linear kernel and a Pareto covariate with for , where . Then , but . This way, Theorem 3 gives finite mean--norm stability, whereas the direct bound is vacuous.
-
Corollary~3 can improve on the direct bound. Consider one-dimensional ridge logistic regression with uniform on and independent of . It can be exactly calculated that and Corollary 3 gives , which is tighter than the direct bound .
-
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--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 -stability literature. The existing -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 -stability condition with an information measure. We view such combinations as valuable and as our main contribution.
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>1 is not, by itself, a major technical contribution. This extension plays the role of connecting the stability condition to an f-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-p-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′) measures the information the original hypothesis W reveals about Zi when the neighboring hypothesis Wi′ 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-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 21log2 while the stability factor decreases as n1. 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.