The Bayesian Stability Zoo

Summary

This paper aims to establish the equivalences among various definitions of distribution independent stability and different definitions of distribution dependent stability. Furthermore, the authors propose a stability-boosted interpolating learning rule that exhibits logarithmic expansion of KL-stability with respect to the sample size.

Strengths

1. The authors establish the equivalence between different definitions of stability. 2. The stability boosting results presented in Section 2.2 are particularly intriguing and can be considered the primary novelty of this paper. These results demonstrate the effectiveness of the proposed stability-boosted interpolating learning rule.

Weaknesses

1. The paper is not well-written and is lack of self-containment. For example, the abbreviation "PAC" is used throughout the main text without providing its full name when it is initially mentioned, despite it being a well-known concept in machine learning. Additionally, the structure of the paper lacks proper organization, as a significant portion is dedicated to introducing existing results and preliminaries, while the main contributions of Theorem 2.1 and Theorem 2.2 are given relatively little emphasis. 2.The main weakness of the paper lies in the overlap between the main contribution and existing results, leading to insufficient novelty. Many existing studies, such as "From Robustness to Privacy and Back" by Asi et al. and those mentioned in Theorem 1.3 of this paper, have already established the equivalence between distribution independent stability and differential privacy. Consequently, the primary contribution of Theorem 2.1 and Figure 1 appears to be a review of these existing results, which is claimed as the main contribution in this paper. Theorem 2.2, from my perspective, is an interesting and significant novelty in this paper. However, its importance is not adequately emphasized in the main body. After reading the construction of $A^*$ in Theorem 2.2 in the appendix, I believe that this construction should be highlighted in the main body to showcase its novelty. 3. One noticeable limitation of this paper is the lack of empirical evaluation for the weak learning rule $A$ and the stability-boosted learning rule $A^*$ in Theorem 2.2. As a result, it is uncertain whether this construction holds practical significance without empirical evidence.

Questions

According to the weakness mentioned, it would be beneficial for the authors to improve the English writing of the paper and place more emphasis on the main contribution, supported by experimental results.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

1 poor

Contribution

3 good

Limitations

Yes

Summary

The paper is a thorough collection of relations between different notions of stability used in learning theory literature. The authors propose a systematization of the many relations by proposing a bifurcation of the notions into two classes -- distribution-independent stability and distribution-dependent stability, where the distribution here refers to population distribution.

Strengths

The paper is a very thorough organization of the panoply of notions of stability used in learning theory literature and provides an insightful perspective on how to view them in relation to each other.

Weaknesses

The amount of content in the paper is better suited for a journal rather than a mere 8 page conference paper. I found the order of the sections to be weird -- section 3 on preliminaries should be before section 2 for example.

Questions

N/A

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper categories different definitions of stability (approximate/pure DP, replicability, global stability, perfect generalization, TV indistinguishability, mutual information stability and KL divergence stability) in the literature into two families (distribution-dependent stability and distribution-independent Bayesian stability) and provides theoretical equivalences in both groups.

Strengths

This paper provides connections between a series of stability definitions in the literature and proved the equivalence between them, which has potential to generalize new proof techniques between different topics.

Weaknesses

1. This paper introduces a series of definitions without any literature, for example, $D_\alpha$-Stability, etc. Without any backgrounds/intuitions on the definitions and any future direction section, I am not convinced enough on how there results can be applied to other topics. Some discussions and intuitions for the definitions can greatly improve the quality of the paper. 2. The equivalence results in this paper are useful and I expect to see some examples on how the equivalence results can help building bridges between different stability literature. 3. The writing and structure of the paper can be improved.

Questions

Can the authors provide some examples on what the equivalence results can help connecting the literature of different stability literature?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

1 poor

Contribution

2 fair

Limitations

The current version of the paper can be improved by some rigorous introductions on the different definitions of stability introduced in this paper, for example, how these concepts have been applied in different topics, but their connection has rarely been investigated. The current version is more like a list of definitions and theorems, without any intuitions, discussions and future directions. Polishing the paper would greatly strengthen the paper, but given the limitations above, incorporating these into the current paper will require a fair amount of rewriting and editing.

Summary

**Post-rebuttal** I thank the authors for their response. I will keep my score as is. This work aims at building a comprehensive taxonomy of stability definitions showing that many definitions of stability are equivalent to each other.

Strengths

This paper studies the interrelations between different types of algorithmic stability. The goal is to extend the study of equivalences between different notions of stability, and make it more systematic. The main contribution of the paper is to show equivalences between distribution-independent Bayesian notions of stability. The authors also provide a boosting result that enables stability amplification.

Weaknesses

* The paper is very dense. It requires familiarity with a number of concepts related to different notions of stability and also substantial background knowledge about related prior work (all quite recent). Of course since the authors aim at creating a comprehensive taxonomy of stability definitions, this is expected and the paper does a great job at that, both in relation to prior work for the distribution-dependent equivalences, and the new ones for the distribution-independent versions. I could not devote enough time to go through the supplied proofs but overall, am not entirely convinced if a conference venue like NeurIPS is the ideal platform for such a dense and terse presentation. The presentation can perhaps be improved in certain parts to improve readability, e.g., giving more intuition wherever applicable (the current draft does not saturate the 9 page limit). * TV indistinguishability (alluded to in the abstract) is not defined in the main text or supplementary.

Questions

* How is TV indistinguishability related to TV stability?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

I do not foresee any potential negative societal impact of this work.

Summary

The paper shows that many definitions of the "stability" in learning theory are equivalent (according to a specific definition of equivalence). They prove this is the case for various distribution-independent definitions of stability as well as compile the same result for distribution-dependent definitions from previous work. This summary allows a unified view across many stability-related concepts in the literature. The submission also proves a result related to boosting, showing that a weak learner can be amplified to obtain better stability and learning performance.

Strengths

The paper is well-written and has a clear organization. The concept of stability studied in the paper is an important one in learning theory. By showing that multiple definitions of stability are weakly equivalent, the authors obtain important results that allow these definitions to be related to each other in a coherent manner.

Weaknesses

I don't have many complaints about this work. I suggest the authors consider clarifying the details asked in my questions in the following section to make the paper clearer.

Questions

- I'm having some trouble understanding the motivation behind wanting the difference between the prior and the posterior to be small in the description of stability on lines 33–34. It seems to me we actually want the difference between two possible posteriors when applied to two similar realizations of $S$ to be small. What if the data really disagree with the prior; wouldn't we have a large difference between the prior and the posterior regardless? - On line 39, what makes the definition of stability Bayesian exactly? Because we iterate over possible realizations of $S$? - In Section 2.1.1, does the chain mean only Pure DP implies $\text{D}_\infty$-Stability and the like but not vice versa ($\text{D}_\infty$-Stability implying Pure DP)?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors did not discuss any possible limitations of their results, although it might be the case that the discussion doesn't apply due to the nature of the topic.

thanks

I thank the authors for their response. I will keep my score as is.

Response to the rebuttal.

Thank you for your comprehensive response. I am open to revising my rating once I receive satisfactory answers to the following additional questions: 1. Could you kindly elaborate further on the formulation and development of the stability-boosted learning rule $A^*$? Given the absence of empirical validation concerning its effectiveness, I would recommend that the authors furnish more intricate insights into the tightness of this theoretical framework. Alternatively, if available, references to established works supporting this approach would greatly enhance its credibility. 2. In addition to the insights presented in Theorem 2.2, could you highlight any other innovative contributions that distinguish your work from the prior literature as listed in Theorem 1.3? (This question arises from my uncertainty regarding whether the primary contribution of formulating the stability-boosted rule holds sufficient promise, as indicated in Question 1. Should Question 1 receive a satisfactory response even in the absence of an answer to Question 2, I would be happy to revise my rating accordingly.)

Answer to The First Question

**Could you kindly elaborate further on the formulation and development of the stability-boosted learning rule $A^\star$? Given the absence of empirical validation concerning its effectiveness, I would recommend that the authors furnish more intricate insights into the tightness of this theoretical framework. Alternatively, if available, references to established works supporting this approach would greatly enhance its credibility.** Yes, we are happy to provide additional background and support from established works concerning our stability boosting result. **Background** Boosting has been a central topic of study in computational learning theory since its inception in the 1990s by Schapire [1] and Freund [2]. Interestingly, it was originally devised as a proof strategy to show a lower bound on the computational complexity of PAC learning. It is essentially a reduction from standard PAC learning to a (seemingly) easier problem of “weak learning”, similar to the many other reductions in computational complexity (e.g., between NP complete problems). However, it quickly became apparent that this reduction actually provides a very powerful and efficient way to perform PAC learning. The best-known boosting algorithm is AdaBoost [3], which has been extensively studied ([3] has >20k citations), and it is also widely used in practice as an excellent out-of-the-box ML algorithm that requires minimal tuning. Boosting also has rich connections with other topics such as game theory, online learning, and convex optimization (see [4], Ch. 5 in [5], Ch. 7 in [6]). **Our Result** In Theorem 2.2 of our paper, we present a novel boosting result. This results shows that given any learning algorithm $A$ that * Performs slightly better than random guessing (i.e., has expected loss at most $1/2-\gamma$ for some small positive $\gamma$), and * Is slightly KL-stable (i.e., the expected KL divergence from some fixed prior is not infinite), We can construct a new learning algorithm $A^*$ that is a fully-fledged PAC learner (has expected loss $\tilde{O}(1/\sqrt{m})$) and is also quite KL-stable (the expected KL is logarithmic in $m$). Our novel boosting algorithm differs from existing algorithms in that it does not only boost the _accuracy_ of the prediction (reducing the population loss), but also increases the _KL-stability_ (from finite to logarithmic). A brief sketch of the proof establishing these claims appears in Section 2.2.1, and a complete mathematical proof appears in Appendix A. Intuitively, our algorithm $A^*$ operates by pitting the well-known Multiplicative Weights (MW) and the provided “weak” algorithm $A$ against each other, and using the guarantees of each. More fully, it repeatedly: * Uses the MW algorithm to find a distribution over the samples of the training set on which the hypothesis chosen by the provided “weak” algorithm $A$ is likely to perform poorly. * Uses the “weak” algorithm $A$ to find hypotheses that perform slightly better than random guessing on the distribution chosen by the MW algorithm. We then use the online regret bound for the MW algorithm to argue that after a modest number of iterations $T = O(\log(m)/\gamma^2)$, there does not exist any sample in the training set that is misclassified by a majority of the hypotheses selected by the “weak” algorithm $A$. Because the the “weak” algorithm $A$ has bounded KL divergence, and it was invoked only $T$ times, a combination of the data-processing inequality and the chain for Rényi divergence imply that the aggregate hypothesis produced by $A^*$ will have a KL divergence proportional to $T$, which is logarithmic in the number $m$ of samples. This also implies generalization. **Tightness of Our Result** We agree that it would be beneficial if future experimental works evaluate our algorithm empirically. However, there are already strong reasons to believe that our algorithm does indeed perform well in practice: * The accuracy (low population loss) guarantee for our algorithm follows (as described above) from well-understood techniques in the boosting literature that are known to give good results in practice. * For the bound on the KL-stability, which is novel, notice that our bound is an explicit, non-asymptotic numerical bound: $\mathrm{KL}(A^*(S) \| \mathcal{P}^{\star}) \leq T \cdot 2b / \gamma + \log(\pi^2/6 \cdot T^2)$ (Eq. (9) and line 330 in the Supplementary Materials). Seeing as there are no hidden constants that could potentially be large (in Big-O notation etc.), we are confident that our theorem provides a meaningful and straightforward upper bound on the KL divergence of $A^*$. Note also that our result joins a rich literature of _theoretical_ works on boosting (see [4] for an extensive bibliography). Does this address your concern? If there are any specific remaining concerns, please let us know!