The Bayesian Stability Zoo
Authors: Shay Moran
Hilla Schefler
Jonathan Shafer
Venue: NeurIPS 2023 poster (2023)
Keywords: Algorithmic stability
Replicability
Differential Privacy
KL Stability
Mutual Information Stability
Global Stability
Perfect Generalization
PAC Learning
Littlestone Dimension
Clique Dimension
PAC Bayes

Abstract: We show that many definitions of stability found in the learning theory literature are equivalent to one another. 
We distinguish between two families of definitions of stability: distribution-dependent and distribution-independent Bayesian stability. Within each family, we establish equivalences between various definitions, encompassing approximate differential privacy, pure differential privacy, replicability, global stability, perfect generalization, TV stability, mutual information stability, KL-divergence stability, and Rényi-divergence stability. Along the way, we prove boosting results that enable the amplification of the stability of a learning rule. This work is a step towards a more systematic taxonomy of stability notions in learning theory,  which can promote clarity and an improved understanding of an array of stability concepts that have emerged in recent years.

The Bayesian Stability Zoo
Shay Moran
Department of Mathematics
& Department of Computer Science
Technion - Israel Institute of Technology;
smoran@teechionn.cc ac
Hilla Schefler
Jonathan Shafer Computer Science Division
Department of Mathematics
Technion Israel Institute of Technology hillas hillas@campus technion. an.iin.......................... il
UC Berkeley shaferjo@berkeley.coo
Abstract
We show that many definitions of stability found the learning theory literature are equivalent to one another. We distinguish between two families of definitions stability: distributionddepeedent and crrrrbution-ndepeeddee
Bayesian stability. Within each family, we establish equivalences between various definitions, encom- passing approximate differential privacy, pure differential privacy, replicability, global stability, perfect generalization, TV stability, mutual information stability, KL-divergence stability, and diver-dieeeeence stability. Along the way, we prove boosting results that enable the amplification of the stability of a learning rule. This work is a step towards a more systematic taxonomy of stability notions in learning theory, which can promote clarity and an improved understanding of array of stability concepts that have emerged in recent years.
Introduction
Algorithmic stability is major theme in learning theory, where seminal results have firmly es- tablished its close relationship with generalization. Recent research has further highlighted the intricate interplay between stability and additional properties of interest beyond statistical gen- cralization. These properties encompass privacy [DMNS06], fairness [HKRR18], replicability [BGH+23, ILPS222, adaptive data analysis [DFH+ 15b, DFH 15a], and mistake bounds in online learning [ALMM19, BLM20].
This progress has with proliferation of formal definitions of stability, including pure and ap- proximate Differential Privacy [DMNS06, DKM 06), Perfect Generalization [CLN* 16), Global Sta- bility [BLM20], KL-Stability [McA99], TV- TV-Stability [KKMV23], f-Divergence Stability [EGI20], Rényi Divergence Stability [EGI20), and Mutual Information Stability [XR17, BMN+ 18), as well as related combinatorial quantities such the Littlestone dimension [Lit87] and the clique dimension [AMSY23].
It is natural to wonder to what extent these various and sundry notions of stability actually differ from one another. The type of equivalence we consider between definitions of stability is as follows.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Definition A and Definition B are weakly equivalent if for every hypothesis class H. the following holds:
H has a PAC learning rule that is H has PAC learning rule that is stable according to Definition
stable according to Definition
This type of equivalence is weak because it does not imply that a learning rule satisfying one definition also satisfies the other.
Recent results show that many stability notions appearing in the literature are in fact weakly equivalent. The work of [BGH + 23] has shown sample efficient reductions between approximate differential privacy, replicability, and perfect generalization. Combined with the work of [ABL*2] 1 ILPS22, KKMV23, MM22], rich web of equivalences being uncovered between approximate differential privacy and other definitions of algorithmic stability (see Fig. 1).
In this paper we extend the study of equivalences between notions of stability, and make it more systematic. Our starting point is the following observation: many of the definitions mentioned above belong to a broad family of definitions of stability, which we informally call Bayesian definitions of stability. Definitions in this family roughly take the following form: learning rule A is considered stable if the quantity
d d(A(S).P)
is small enough, where:
d is measure of dissimilarity between distributions.
P a specific prior distribution over hypotheses;
. A(S) is the posterior distribution, i.e., the distribution of hypotheses generated by the learning rule when applied to the input sample S.
Namely, a Bayesian definition of stability is parameterized by choice of d, choice of P, and specification of how small the dissimilarity is required be."
To understand our choice of the name Bayesian stability, recall that the terms prior and posterior come from Bayesian statistics. In Bayesian statistics the analyst has some prior distribution over possible hypothesis before conducting the analysis, and chooses posterior distribution over hypotheses when the analysis is complete. Bayesian stability is defined in terms of the dissimilarity between these two distributions.
Remark 1.1.
central insight of this paper is that there exists a meaningful distinction between two types of Bayesian definitions, based on whether the choice of the prior P depends on the population distribution D:
(DI) stability. These are Bayesian definitions of stability in which P is some fixed prior that depends only on the class and the learning rule A, and does not depend on the population distribution D. Namely, they take the form:
Distribution-indepeenee
prior P population D Vm E N: d(A(S), P) is small,
where S ~ D
Distribution-dependen (DD) stability. Here, the prior may depend also on D, so each population distribution might have a different prior. Namely:
Y population D prior Pd Vm E N: d(A(S). Pb) is small.
A substantial body of literature has investigated the interconnections among ceterrbuutiondeeeeded definitions. In Theorem 1.4, we provide a comprehensive summary of the established equivalences. A
'An example an application in the context of generalization theorem assures that for every population distribution and any given prior P. the difference between the
classic PAC Bayes Theorem. The
population error of an algorithm A and the empirical error of A is bounded by ò (V [M(A(())PP) where m is the size of the input sample S, and the KL divergence is the "measure of dissimilarity" between the prior and the posterior See e.g. Theorem 3.2.

---

natural question arises as to whether similar web of equivalences exists for distribution distribution-iddeeendde independent definitions. Our principal contribution to affirm that, indeed, such network exists. Identifying such equivalences is a step towards creating comprehensive taxonomy of stability definitions.
1.1 Our Contribution
Our first main contribution is equivalence between distribution-indeeedder definitions of stability,
Theorem (Informal Version of Theorem 2.1). The following definitions of stability are weakly equivalent:
1. Pure Differential Privacy;
(Definition 3.5)
2. Distributtinn Independent KL-Stability;
(Definition 3.6)
3. Distribution ciarbuutoo-Indepeddenn One-Way Pure Perfect Generalization:
(Definition 3.7)
(Definition 3.6) Where Da is the Rényi divergence of order a. Furthermore, a hypothesis class H. has PAC learning rule that is stable according to one of these definitions if and only if H. has finite fractional clique dimension (See Appendix B.
4. Distributiin Ienepeeddnn--ddeeeddeettttt Da- Da-Stability for E (1)
Remark 1.2. Observe that DI KL-stability is equivalent to DI Dy-stability, and DI one-way pure perfect generalization is equivalent to DI Dee -stabiliiy Therefore, The above theorem can be viewed as stating weak equivalence between pure differential privacy and Da -tabbiiyyyyy for E [1, oo].
Remark 1.3. In this paper we focus purely on the ceemmattionthhoreee aspects of learning under stability constraints, and therefore we consider learning rules that are mathematical functions, and disregard considerations of computability and computational complexity.
Table summarizes the distribution-indeeenden definitions discussed in Theorem 2.1. All the definitions in each row are weakly equivalent.
Table I: Distriutioon-indeeendent Bayesian definitions of stability.
Name
Dissimilarity
Definition
KL-Stability
Ps KL(A(S) P) < o(m)
2 21-011
3.6
Da-Stability
Ps Da (A(S) P) S o(m) 21 ((1)
3.6
Pure Perfect Generalization
Ps Fs[vO: : (()) S (e(m))((()) 21 21-o(1) o(1)
3.7
One example for how the equivalence results can help build bridges between different stability notions in the literature is the connection between pure differential privacy and the PAC-Bayes theorem. Both of these are fundamental ideas that have been extensively studied. Theorem 2.1 states that hypothesis class admits a pure differentially private PAC learner and only it admits distribution independent KL-stable PAC learner. This is an interesting and non-trivial connection between two well studied notions. As a concrete example of this connection, recall that thresholds over the real line cannot be learned by differentially private learner [ALMM19]. Hence, by Theorem 2. there does not exist a PAC learner for thresholds that is KL-stable. Another example is half-spaces with margins in Rd. Half-spaces with margins are differentially private learnable [?], therefore there exists a PAC learner for half-spaces with margins that KL-stable.
Our second main contribution is boosting result for weak learners that have bounded KL-divergence with respect to a ioiiiiutiooninddeedeeen prior. Our result demonstrates that distribution-in iiiiiuutioonnnddeeedeen KL-stability is boostable. It is interesting to see that one can simultaneously boost both the stability and the learning parameters of an algorithm.
Theorem (Informal Version of Theorem 2.2). Let H. be hypothesis class. If there exists weak learner A for H. and there exists a prior distribution P such that the expectation of KL(A(S) P) is bounded, then there exists KL-stable PAC learner that admits logarithmic divergence bound.
The proof of Theorem 2.2 relies on connections between boosting of PAC learners and online learning with expert advice.
3

---

9
DD Perfect Generalization
Max Information
Finite Clique Dimension
DD TV-Stability
17
11
10
8
15
16
Replicability
Approximate DP
MI-Stability
12
7
5
3
6
4
Global Stability
Finite Littlestone Dimension
DD KL-Stability
weakly implies
assuming countable domain
algorithm
assuming finite domain
Edge key:
1. Lemma C.6
Thearem 17. [BLM2
Theorem 1, [KKMV23]
2. Lemma C.13 ([NNG22)
8. Cerollary 3B1H 231
14. Theorem 2. [KKMV23
Lemma C.11
Lemma [BGII*23] 231
[KKMV23]
4. Lemma C (1 (LLM20))
10. Theorem 3.17, [BGH 23]
16. Theorem 3, [KKMV23]
Corollary [ALMM19]
11. Theorem 3.19, [BGH
Theorems 2.2, [AMSY23)
6. Theorem 10, [BLM20]
12. Theorem 3.1. (BCH
Figure 1: A summary of equivalences between distribution-dependee definitions of stability (Theorem 1.4). A solid black arrow from B means that definition weakly implies definition B. dashed blue arrow from means that weakly implies only if domain X' is countable. dotted red arrow from A to means that A weakly implies B only if the domain A' is finite. A double brown arrow from A to B means that every learning rule that satisfies definition A also satisfies definition B.
Lastly, after conducting an extensive review of the literature, we have compiled a comprehensive network of equivalence results for distributioon-deeeneent definitions of stability. This network is presented in Theorem 1.4, Figure and Table 2.
Theorem 1.4 (Distribution-Dependlll KKMV23J). The following definitions of stability are weakly equivalent with respect to an arbitrary hypothesis class H:
Equivalences; [ABL+ ILPS22, MM22, PNG22, BGH+
1. Approximate Differential Privacy:
(Definition 3.5)
2. Instibuttion-Depender KL-Stability;
(Definition 3.6)
3. Mutual- Inforatnnooooaaioon Stability;
(Definition 3.12)
4. Global Stability.
(Definition 3.11)
the domain countable then the following are also weakly equivalent the above:
5. Distribution-Dependennt TV-Stability;
(Definition 3.13)
6. Replicability
(Definition 3.8)
If the domain is finite then the following are also weakly equivalent to the above:
7. One-Way Way Perfect Generalization;
(Definition 3.7)
8. Max Information.
(Definition 3.14)
Furthermore, for any hypothesis class H. the following conditions equivalent:

---

H. has PAC learning rule that is stable according to one of the definitions to 6 (and the cardinality of the domain as described above);
H. has finite Littlestone dimension;
(Definition C.3)
H has finite clique dimension.
(Definition C.5)
We emphasize that Theorem 1.4 is a summary of existing results, and is not a new result. We believe that our compilation serves as a valuable resource, and that stating these results here unified framework helps to convey the conceptual message of this paper. Namely, the fact that large number of disparate results can neatly be organized based on our notions of distribution-depe dependdd and cittriutioo-indeeeene
definitions of stability is a valuable observation that can help researchers make sense of the stability landscape.
Table 2: -etpbedde Bayesian definitions of stability.
Name
Dissimilarity
Definition
References
KL-Stability
Ps|KL(A(S)) Pp) S o(m)) 2 1 o(1)
3.6
[McA99]
TV-Stability
Es (V(, S o(1)
3.13
[KKMV23]
MI-Stability
Es (LL(AS)) Pp) PP ((m)
3.12
[XR17, BMN 18]
Perfect Generalization
Vs (O)) <e
3.7
[CLN+ 16)
Global Stability
P PSAApP
[A(S) hi] 21
3.11
[BLM20]
Replicability
PAWR P.S.h..PP, [A(S;r) (A(S:)) = hpl N2
3.10
[BGHT23 23, ILPS22]
1.2 Related Works
The literature on stability is vast. Stability has been studied in the context of optimization, statistical estimation, regularization (e.g., [Tik43] and [Phi62]), the bias-variance tradeoff, algorithmic stability (e.g., [BE02]; see bibliography in Section 13.6 of [SB 14B, bagging [Bre96], online learning and optimization and bandit algorithms (c.g.. [Han58]; see bibliography Section 28.6 of [LS20]), and other topics.
There are numerous definitions of stability, including pure and approximate Differential Privacy [DMNS06, DKM+06) 06), Perfect Generalization [CLN+ 16], Global Stability [BLM20], KL-Stability [McA99], TV- Stabiibilyty [KKMV23], f f-Divergence Stability [EGI20], Rényi Divergence Stability [EGI20], and Mutual Information Stability [XR17, BMN 18].
Our work most directly related to the recent publication by Bun al. [BGH*23], They established connections and separations between replicability. approximate differential privacy, max- max-information and perfect generalization for a broad class of statistical tasks. The reductions they present are sample-efficient, and nearly all are computationally efficient and apply to a general outcome space. Their results are central the understanding of equivalences between notions of stability laid out in the current paper.
concurrent work by Kalavasis et al. [KKMV23] showed that TV-stability, replicability and approx- imate differential privacy are equivalent; this holds for general statistical tasks on countable domains, and for PAC learning on any domain. They also provide statistical amplification and TV-stability boosting algorithm for PAC learning countable domains.
Additionally, recent works [AUZ23, HKMN23] have shown an equivalence between differential privacy and robustness for estimation tasks.
Theorem 2.2 a boosting result. Boosting has been a central topic of study in computational learning theory since its inception in the 1990s by Schapire [?] and Freund [Fre95]. The best-known boosting algorithm is AdaBoost [FS97], which has been extensively studied. Boosting also has rich connections with other topics such game theory, online learning, and convex optimization (sec [SF12], Chapter 10 in [SB14], 14], and Chapter in [MRT18]).
2 Technical Overview
This section presents the complete versions of Theorems 1.4 and 2.2. We provide a concise overview of the key ideas and techniques employed in the proofs. All proofs appear in the appendices.
5

---

Please refer to Section 3 for complete overview of preliminaries, including all technical terms and definitions.
2.1 Equivalences between DI Bayesian Notions of Stability
The following theorem, which is one of the main results of this paper, shows the equivalence between different distribution-ine innpeeendnnnndeeeeeeenee definitions. The content of Theorem 2.1 is summarized in Table 1.
Theorem 2.1 (Distrbuttion-Indeeeeddd Equivalences). Let H be hypothesis class. The following equivalent.
1. There exists a learning rule that PAC learns H and satisfied pure differential privacy (Definition 3.5).
2. H has finite fractional clique dimension.
3. For every petribbttionindependdene Da Da-stability (Definition 3.6).
[o], there exists learning rule that PAC learns H. and satisfied
4. For every a E [1, oc], there exists a distribution- stabta PAC learner for H. that satisfies the following:
(i) A is interpolating almost surely. Namely, for every H-realizable distribution D. P Dm [Ls(A(S)) = =
(ii A admits a divergence bound of [m) O(log m)) with confidence 3(m) l.e., for every H-realizable distribution D, D., (A(S)) P) < O(log m) with probability 1, where S DD and P a prior distribution independent of
(iii) For every H--realizalee distribution D, the expected population loss of A with respect to D satisfies E5.Dm [T.(([((()))))))) S (
In particular, plugging 1 in Item (ii) implies KL-stability with divergence bound of [mm (loo m) and confidence ((m) = 0. Plugging a = oc implies distribution-indeeendddd one-way E-pure perfect generalization, with s(m) S Olog m) and confidence 3(m) = O.
2.1.1 Proof Idea for Theorem 2.1
We prove the following chain of implications:
Pure DP Do Stabilityy
D, -taSbiibllity Ya E [0] Pure DP.
Pure DP = D Stabilityy The first step towards proving implication (1) is to define a suitable
prior distribution P over hypotheses. The key tool we used in order to define P is the characterization of pure DP via the fractional clique dimension [AMSY23], In nutshell, [AMS Y23] proved that (i) class H pure DP learnable if and only if the fractional clique dimension of H. is finite; (ii) the fractional clique dimension is finite if and only if there exists a polynomial ((m) and a distribution over hypothesis P... such that for every realizable sample S of size m, we have
Ph~Pan m [Ls (h) =
q(m)
(For more details please refer to Appendix B.1.) Now, the desired prior distribution P is defined to be a mixture of all the P.,. 's.
The next step in the proof is to define a learning rule A: (i) sample hypotheses from the prior P; (ii) return the first hypothesis that consistent with the input sample (i.e. Ls(h) = 0). A is well- defined since with high probability it will stop and return hypothesis after Rs g(m) re-samples from
P. Since the posterior
A(S) is supported on (h (h) = 0), simple calculation which follows from Equation (I) shows that for every realizable distribution D. D (A(S) | P) log(g(m)) almost surly where S ~ m
Finally, since for E oo] the Rényi divergence D. || Q2) is non-decreasing in (see Lemma A. we conclude that KL(A(S) || PP) S O(log m). hence by PAC-Bayes theorem A generalizes.
D Staabiiliyty - Dt-Stibilliyy Va E oo]. divergence D (1 || 22) is mon-decreasing a.
This implication is immediate since the Rényi

---

Pure DP. In fact, it suffices to assume KL-stability. We prove that the promised prior P satisfies that for every realizable sample of size m, we have Ph~p (T.p (h) = 0] 2 poly(ma). and conclude that H is pure DP learnable. Given realizable sample S of size m, we uniformly sample z m log m examples from S and feed the new sample S' the promised KL-stable learner A. By noting that if KL(A(S") (P) is small, one can lower bound the probability of an event according P by probability according A(5"). The proof then follows by applying standard concentration argument.
Da Du-Stability Va E [o]
2.2 Stability Boosting
We prove a boosting result for weak learners with bounded KL with respect distribution- independent prior. We show that every leamnr with bounded KL that slightly beats random guessing can be amplified to learner with logarithmic KL and expected loss of O O(Vm" m- log m).
Theorem 2.2 (Boosting Weak Learnrr with Bounded KL). Let X be set, let H S 13* be hypothesis class, and let A be learning rule. Assume there exists
and y > 0 such that
1
vD E Realizable(P)) BSwD=|LL(ACC S 7
(2)
and there exists E ((0, and such that
vD E Realizable(HI) ES (KL(A P)] <
Then, there exists an interpolating learning rule A that PAC learns H with logarithmic KL-stability. More explicitly, there exists a prior distribution P E ((00, 1)²¹) and function b' and e* that depend on and such that
VD E Realizable(H) Vm E::
PS-DM (KLOKK(LAA P*) < (m)) O(log(m)) = 1, and
(4)
Es-Dm (lo=m((D(AA(S))) s < =0 =o(v (log(m)
(5)
m
2.2.1 Proof Idea for Theorem 2.2
The strong learning rule A* is obtained by simulating the weak learner A on Ollog m/>²) samples of constant size (which are carefully sampled from the original input sample S). Then, A returns an aggregated hypothesis - the majority vote of the outputs of A. As it turns out, A satisfies logarithmic KL-stability with respect to the prior P that mixture of majority votes the original prior P. The analysis involves reduction regret analysis of online learning using expert advice, and also uses properties of the KL-divergence.
3 Preliminaries
3.1 Divergences
The Rényi a-divergence is a measure of dissimilarity between distributions that generalizes many common dissimilarity measures, including the Bhattacharyya cocfficient (a = 1/2), the Kullback- Leibler divergence (a = 1), the log of the expected ratio (a = 2), and the log of the maximum ratio (a xc)
Definition 3.1 (Rényi divergence; [Rén61, vEH14]). Let E (1, The Rényi divergence of order of the distribution P from the distribution Q is
P(x)
a-1
D. 2)
log
Enwp
Q(x))
7

---

For a = 1 and a = oo the Rényi divergence is extended by taking limit. In particular. the limit - gives the Bettback--eibble divergence.
P(z) a (ax)
Di(P || 2 = Eanp
log
KL(PP)
|| 2),
and
css sup P(x)
D (P Q) log
((x)
with the conventions that 0/0 = and z/0 = 00 for x > 0.
3.2 Learning Theory
We use standard notation from statistical learning (e.g.. [SB14]). Given hypothesis : X +
{0, 13, the empirical loss of & with respect to a sample S = { vi)..., (.m. Fm)} is defined [[,(x;) + y.]. A learning rule A is interpolating if for every input sample S, S, m - i=1
as (h)
(h) 0 The population loss of h with respect to population distribution 'D over X' x {0, 1] is defined as (D(h) = ((..)))D((<<t A v/. A population DD over labeled examples is realizable with respect to a class H. if inf Lp (h) = O. We denote the set of all realizable population distributions of a class H by Realizable(?H) (H). Given learning rule A and input sample S of size m, the population loss of A(S) with respect to population D is defined as E [L (h)].
A hypothesis class H is Probably Approximately Correct ( (PAC) learnable if there exists learning rule A such that for all D E Realizable(PF) and for all m E N, we have ES~D [L (A(5)) I a(m). where lim,, +00 {mm) O.
Theorem 3.2 (PAC-Bayee Bound: [McA99, LSMO1, McA03]; Theorem 31.1 in [SB (B])... Let X be set, let H C 10 and let D E A(X x (0, For any (0, 1) and for any P A(H),
K P) + In( mmmm3)
P Sm
VQ E A(H)) (2( S Ls( +
2 21-B. B.
2(m 1)
3.3 Definitions of Stability
Throughout the following section, let X' be a set called the domain, let H S 10, be a hypothesis class, and let m E N be sample size. A randomized learning rule, or learning rule for short, is function : (X' x (0, + A (101 that takes a training sample and outputs a distribution over hypotheses. population distribution a distribution D E A x {0, 1}) over labeled domain elements, and prior distribution distribution P A ((10, 1)²) over hypotheses.
3.3.1 Differential Privacy
Differential privacy is property of an algorithm that guarantees that the output will not reveal any meaningful amount of information about individual people that contributed data to the input (training data) used by the algorithm. See [DR14] for introduction.
Definition 3.3. Let E, Rz0, and let P and Q be two probability measures over a measurable space (2, F). We say that P and Q are (s, 8) iniistiiinguiieb and write P 2 Q. if for every event E F. P(O) S E 2(0) + and ((O) S -POO++ +8.
Definition 3.4 (Differential Privacy; [DR14J). Let 8 8 E I2z- A learning rule A is (e, dd-fffer-- entially private for every pair of training samples S, E (X' x (0,1))m that differ on a single example, A(S) and A(S") are ( indistinguushable.
Typically, is chosen to be small constant (e.g.. E < 0.1) and d is negligible (i.e., 8(m) S -w()). When we say that A satisfies pure differentially privacy.
Definition 3.5 (Private PAC Learning). H is privately learnable or DP learnable if it is PAC learnable by learning rule A which (e(m), (((m))((m)))) selddferentially-priivee where E(m) S and 8(m) = m -w()) A is pure DP learnable if the same holds with d(m) =0.
3.3.2 D., D,,Sttabiliy and KL-Stability
Definition 3.6 (D..-Stability). Let a E 00). Let be learning rule, and let f - R and 8 N. + [0, 1] satisfy fmm = o(m) and 3(m) = o( o()).
8

---

1. A is dnstrbuationiiddeeenaee Da-stable if
(D. prior P'V population D Vm NN: PS-DD [D. (A(5) | P)) f(m)] 1 -B(m).
2. A is distribution-dependder Do-stable if
population D 3 prior PD Vm E : PSWDI ( (A(S) | PD) & f(m)) 2 3(m).
The function f is called the divergence bound and B is called the confidence. The special case of is referred as KL-stability [McA99].
3.3.3 Perfect Generalization
Definition 3.7 (One-Way Perfect Generalization). Let A be a learning rule, and let B: - [0,
satisfy ((m) = o(1).
1. L N + IR satisfy s(m) = o(m). A is é-pure perfectly generalizing with confidence 33
3 prior P population D D'vm N: PSwDD VVO A(S)(O) e(t)) 2 - 3(m).
2. (ICLN* 16]:) E E Rz0. is (5.6) (aproxxaixi perfectly generalizing with confi- dence 3 if
A population D prior PD Vm N: PS A(S)(O) S ctPb(O) +6 3(m).
3.3.4 Replicability
Definition 3.8 (Replicability; [BGH 23, ILPS22]). Let E Rzo and let R. be a distribution over random strings. learning rule p-replicable if
Y population D, Vm P PR
[A(S1:)) = A(Sar)) 2 P.
where represents the random coins of A.
Remark 3.9. Note that both (BGH 23] and in [ILPS22] the definition of p-replicability is slightly different. In their definition, they treat the parameter as the failure probability, i.e., A is a replicable learning rule by their definition if the probability that A(S1rr) A(S2;r) at least 1 1-p.
There exists an alternative 2- p-arameeter definition of replicability introduced in [ILPS22].
Definition 3.10 (( -)-peplicability; [BGH 23, ILPS22)). Let v E R>0 and let R be distribu- tion over random strings. Coin tosses are g-good for a learning rule A with respect a population distribution D if there exists a canonical output hy such that for every m, PS-D (A(Sr) r) = hr] 2 A learning rule A is (n) re-rrlclaa if
V population D: PP-R(P is n-good, 2 V.
3.3.5 Global Stability
Definition 3.11 (Global Stability; [BLM20J). Let > 0 be global stability parameter. learning rule A is (m,, n) -loobbbylyy stable with respect to population distribution D if there exists canonical output such that IP[((S) hi] 2 n, where the probability is over S S~ DD as well as the internal randomness of A.
3.3.6 MI-Stability
Definition 3.12 (Mutual Information Stability; [XR17, BMN+ 18]). A learning rule A is MI-stable if there exists f N + N with f = o(m) such that
Y population D vm E N: I(A(S), < f(m),
where S ~ Dm

---

3.3.7 TV-Stability
Definition 3.13 (TV-Stability; Appendix A.3.1 in [KKMV23]). Let A be learning rule, and let f:N + N satisfy f(m) = o11)
1. A is distribution-iie inneeeeddon- TV-stable if
3 prior P population D'Vm N: (IS. S f(m).
2. A is distribution depeeddttoo-deeeeeentt TV-stable if
A population D 3 prior PD Vm E N: ESwDm (TV( - f(m).
3.3.8 Max Information
Definition 3.14. Let A be a learning rule, and let e, R2o- has (ex0)-maxxnnooooaaii with respect to product distributions for every event O we have
P((A(S),S) E Ol e'P((((S)))))) 0 where are S, are independent samples drown i.i.d from population distribution D.
Acknowledgements
SM is Robert J. Shillman Fellow: he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by an Azricli Faculty Fellowship. by Israel VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS). and by the the European Union (ERC, GENER- ALIZATION, 101039692). HS acknowledges support by ISF grant 1225/20, and by the the European Union (ERC, GENERALIZATION of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. IS was supported by DARPA (Defense Advanced Research Projects Agency) contract #HR001 120C0015 and the Simons Collaboration on The Theory of Algorithmic Fairness.
101039692). Views and opinions expressed are however those
References
[ABL*22] Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. Journal of the ACM, 69(4):28:1-28:34, 2022. doi: 1051145/3526774
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Comput- ing. STOC 2019, Phoenix, AZ, USA, June 23-26. 2019, pages 852-860 ACM, 2019, doi: 11...111//311376....
[AMSY23] Noga Alon, Shay Moran, Hilla Schefler, and Amir Yehudayoff. A unified characteriza- tion of private learnability via graph theory. CoRR, abs/2200400399. 2023, 2304.03994 doi: 00.4485//xXii.2344.000
[AUZ23] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness privacy and back. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 1121-1146. PMLR, 2023. URL https: https://proceedingg mlr. Tress/vv02// asi23b httl.
[BB02] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Ma- chine Learning Research, 2:499-526, 2002. URL http://jmiz: org/ hatg/apprs/vvve v2/ bousquet02a. html.
[BGH+23]
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections be- tween replicability, privacy, and adaptive generalization. In Bamna Saha and Rocco A.
10

---

Servedio, editors. Proceedings of the 55th Anmual ACM Symposium on Theory of Com- puting, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 520-527. ACM, 2023. doi: 10. (e..1144//56444.355522222
[BLM20] Mark Bun, Roi Livni, and Shay Moran, An equivalence between private classification and online prediction. In Sandy Irani, editor, 61st IEEE Annual Symposium on Founda- tions of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 389-402. IEEE, 2020, doi: 100:1..111990OO 100//0CS467000000000000
[BMN 18]
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. Learn- ers that use little information. In Firdaus Janoos, Mehryar Mohri, and Karthik Sridharan, editors, Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, volume 83 of Proceedings of Machine Learning Research, pages 25-55. PMLR, 2018. URL http: proceedings....o p mlr www..ppee///ee v83/ bassily18a, html.
[BPS09]
Shai Ben- David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning, In COLT 2009 The 22nd Conference on Learming Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009, URL http:://wwtt 032. 332.pdf#page-1
[Bre96]
Leo Breiman. Bagging predictors. Machine Learning, 24(2):123-140, 1996. doi: 10. 10070//0000558555
[CLN+ 16]
Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. Adaptive learning with robust generalization guarantees. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory. COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 772- 7128814. JMLR.org, 2016. URL mlr. www.spressvveee http//cmmmnnnnn//eeeeee html.
[DFH* 15a] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity adaptive data analysis. Science, 349(6248):636- 638, 2015.
[DFH* + 15b] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Anmual ACM Symposium Theory of Computing. STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 117-126. ACM, 2015. 10. 145/2776539,,7766888
[DKM 06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay, editor, Advances in Cryptology EUROCRYPT 2006, 25th Annual International Conference the Theory and Applications of Cryplographic Techniques, St. Petersburg, Russia, May 28 June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 486-503. Springer, 2006. doi: 10. (007/1176167992)
[DMNS06]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. 1bi:10.1007/// 1681878_14.
[DR14)
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential pri- vacy. Foundations and Trends in Theoretical Computer Science, 9(3-4)211-4077, 2014. doi: 10. 11.1156///0000000422
[EG120]
Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Robust generalization via f -mutual information. In IEEE International Symposium on Information Theory, ISIT 2020, Los Angeles, CA, USA, June 21-26, 2020, pages 2723-2728. IEEE, 2020.
[Fre95]
Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256-255, 1995, 100.100000//NN01199....1

---

[FS97]
Yoav Freund and Robert E. Schapire. A decision -hetiot-teeerticccc generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139, 1997. doi: (006/JCSS.1997..
[Han58]
James Hannan. Approximation to Bayes risk in repeated play. In Contributions to the Theory of Games (AM-39), Volume III, pages 97-140, Princeton, 1958. Princeton University Press. doi:doi: 10. (0.111//78810008821111
[HKMN23] Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan, Ro- bustness implies privacy statistical estimation. In Barna Saha and Rocco A. Serve- dio, editors. Proceedings of the 55th Annual ACM Symposium Theory of Comput- ing, STOC 2023, Orlando, FI., USA, June 20-23, 2023, pages 497-506. ACM, 2023. doi: Ne::10.115/35662 00011145/566424.35551111
[HKRR18]
Úrsula Héhert-Johnson, Michael Kim, Omer Reingold, and Guy N. Rothblum. Multi- calibration: Calibration for the coomputationall--ieenffffii masses. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Ma- chine Learning, ICML 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, volume 80 Proceedings of Machine Learning Research, pages 1944-1953, PMLR, 2018. URL http: htttp://proceeeinng: mlr wwwppereeesr massss/v80/ebbere www.eeerrrroooooonaaa..... jwwnson18a...... htm.l.................mmmm.mmm.1
[ILPS22] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 818 831. ACM, 2022. doi: 10::10.111 11111//511933335199973
[KMM233]
Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference Machine Learning, ICML 2023, 23-29 July 2023, Hon- olulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 15586-15623 PMLR, 2023. URL htttps:/pproceedingg mlr press/v202) kalavasis23a html.
[Lit87]
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. Machine Learning, 2(4):285-318, 1987. doi: 10. 1007/BF001 16827.
[LM20]
Roi Livni and Shay Moran. A limitation of the PAC-Bayes framework. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: oareaa/cc81116662200006666663333 Abstrecttbtttttttaaee html.
wweerips.cc/ppppeee /2020/
[LS200]
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 101:7/0777 108571401
[LSMO1]
John Langford, Matthias W. Seeger, and Nimrod Megiddo. An improved predictive accuracy bound for averaging classifiers. In Carla E. Brodley and Andrea Pohoreckyj Danyluk, editors, Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28- July 1, 2001, pages 290-297. Morgan Kaufmann, 2001.
[McA99] David A. McAllester: Some PAC-Bayesian theorems. Machine Learning, 37(3):355- 363, 1999.
[McA03] David A. McAllester. Simplified PAC- PAC-Bayesian margin bounds. In Bernhard Schölkopf and Manfred K. Warmuth, editors, Computational Learning Theory and Kernel Ma- chines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pages 203-215 Springer, 2003. 16.
doi: 11110000777733400055111111
[MM22]
Maryanthe Malliaris and Shay Moran. The unstable formula theorem revisited. CoRR,
12

---

Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learn- ing: From Theory to Algorithms. Cambridge University Press, 2014. http:///ddo.oor/1100001///7//110 abs/2212.05050, 2022, 2212.05050. do:110.8550//7112222..5555
[MRT88]
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, second edition, 2018. URL fattps:/nni //te://miittttsssesseeee mit. wtw.t..du/9780000 edu.977802622399400
[Phi62] David L. Phillips. A technique for the numerical solution of certain integral equations of the first kind. Journal of the ACM, 9(1):84 97, 1962. doi:10. 145/321 105. 114.
[PNG22]
Aditya Pradeep. Ido Nachum, and Michael Gastpar. Finite Littlestone dimension implies finite information complexity, IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, June 26 July 1, 2022, pages 3055-3060. IEEE, 2022. doi: 10. 1091101100666...... 201.566662222.8844455577
[PW]
Yury Polyanskiy and Yihong Wu. Cambridge University Press. URL Information Theory: From Coding to Learning. .idd..d.... wwt.:e/ddeepppaaeeeeeee data/itbook export pdf. Unpublished manuscript, 2023.
[Rén61]
Alfréd Rényi On measures of entropy and information. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contribu- tions to the Theory of Statistics, volume 4, pages 547-562. University of California Press, 1961.
[SB14]
[SF12]
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT
Press, 2012. do..hutps:/ddoi.or//1..... / (.00:2299.001.000 1.00.0001.
[She90]
Saharon Shelah. Classification Theory: And the Number of Non-Isomorphic Models, volume 92 of Studies Logic and the Foundations of Mathematics. second edition, 1990.
[Tik43]
A. Tikhonov. On the stability of inverse problems. Proceedings of the USSR Academy of Sciences. 39:195-198, 1943. URL Attacc////pp.....aaa..cc.ca.a semanticscholar. org/CorpusID: 202866372.
[vEH14]
Tim van Erven and Peter Harremoës. Rényi divergence and Kullback-Leiblr divergence. IEEE Trans. Inf. Theory, 60(7):379733820, 2014. 1oi: 109111110000T22242222555
[XR17]
Aolin Xu and Maxim Raginsky. information-thhoreee analysis of generalization capa- bility of learning algorithms. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2524-2533 2017. URL ptt.:./R.tttsss/prrreeeeeaa hww.:/eeeeeddin..e.eee.eee.eeee. nwwrips....... http:///gg...i.rppc//////////111 hat.://a...B2222266666e0eeeeeede
html.
13

---

A Proof for Theorem 2.2 (Stability Boosting)
A.1 Information Theoretic Preliminaries
Lemma A.1 (Monotonicity of Rényi divergence; Theorem 3 in [vEH14]). Let 0 S < B I co. Then (P || Q) < (2 lI Q). Furthermore, the inequality an equality if and only if equals the conditional Q(- A) for some event A.
Lemma A.2 (Data Processing Inequality: Theorem and Eq. 13 [vEH14]). Ler E [0, o0). Let X and Y be random variables, and let Fyix be the law of Y given X. Let Py, Qy be the distributions of Y when X sampled from Px, 2x, respectively. Then
(Py || Qr) (xx Qx).
One interpretation of this that processing an observation makes more difficult to determine whether it came from Px or Qx.
Definition A.3 (Conditional KL-divergence; Definition 2.12 in [PW]). Given joint distributions P(z, v). ((r, u). the KL KL-divergence of the marginals (vylz), (2y(z) is
P(ya)) Q
KL(P(yl<)) @(vl=)) Σ P(x)
p log
Lemma A.4 (Chain Rule for KL-divergence; Theorem 2.13 in [PW]). P(x, v), Q( v) be joint distributions. Then,
(L(P(Z, v) || ((r,))) = KL(P(z) ((=)) + (L(P(v)z) Q(vl=)).
Lemma A.5 (Conditioning increases KL-divergence; Theorem 2. (4)) in [PW]). For a distribution Px and conditional distributions x Qy let Py = Prix o Px and Qy Qrix Px. where
'o' denotes composition (see Section 2.4 in [PW]) Then
KL(Py || Qx) KL (Prix Qrix Px).
with equality if and only if KL (XXIY |l 2xIx Pv) B=)=0 =0.
A.2 Online Learning Preliminaries
Following is some basic background on the topic online learning with expert advice. This will be useful in the proof of Theorem 2.2.
Let Z {z1...., 2m3 be of experts and be a of instances. For any instance E I and expert z E Z, following the advice of expert z on instance i provides utility u(z, E {0, 1).
The online learning setting is perfect-infoormtion zero-sum game between players, learner and an adversary. In each round = 1,...,77 ,
1. The learner chooses distribution w, A(Z) over the set of experts.
2. The adversary chooses an instance i4 E J.
3. The learner gains utility u, Eg [u(2, ét)].
The total utility learner strategy C for the sequence of instances chosen by the adversary is
T
U(C,T)
Σ
The regret of the learner is the difference between the utility of the best expert and the learner's utility. Namely, for each z E Z,
U(2,T) Σ u(2,)e)
be the utility the learner would have gained had they chosen wx(2) 1 (== 2,) for all t [2]. Then the regret is
Regret(C,T)) max U(, - U(C,T).
14

---

There are several well-studied algorithms for online learing using expert advice that guarantee regret sublinear T for every possible sequence of instances. A classic example is the Mulriplicative Weights algorithm (e.g., Section 21.2 in [SB14]), which enjoys the following guarantee.
Theorem A.6 (Online Regret Bound). In the setting of online learning with expert advice, there exists a learner strategy L such that for any sequence of T instances selected by the adversary,
Regret 22T log(),
where is the number of experts.
A.3 Proof
Theorem (Theorem 2.2, Restatement). Let X be a set, ler H S [0, be a hypothesis class, and let A be learning rule. Assume there exists lo E N and y 0 such that
VD E Realizable(H)) ES (tp((((p())))) (A())) _
(6)
and there exists P ((00, 1)*) and b such that
vD E Realizable(H)) ES-DA (KL(A(S) P)] b.
(7)
Then, there exists an interpolating learning rule A that PAC learns H with logarithmic KL KL-stability. More explicitly, there exists a prior distribution P E ((00,) on y and such that
b" and g* that depend
VD Realizable(H) Vm ::
PS-D "s>Dm|KL(AM())) [KL(A*(S) P*) (*) (m) O(logmm))]
(8)
and
Es-Dm (AoDm(L((AA(S))) < 5*(mm = =0 (o(voog(m)
(9)
Assumptions:
7.b> b> 0; m. k E.
((11,1)) v1)..... (mmm } is an H-realizable sample. Os is the online learning algorithm of Appendix A.2, using expert set S.
T = [8 log(ml) (m)gm//2²
A satisfies Eqs. (6) and (7) (with respect to k; b, 7).
AS))
for / = 1.....77 T:
Wt expert distribution chosen by Os for round do:
sample S, +- (w;) )
while KL(A(S.) || P) > 26/7
See Remark A.7
ft 155A(1 A(S.)
Os receives instance fa and gains utility Exz,g) [1(((()) + +
return Maj
Algorithm The stability-boosted learning rule A+, which uses A as subroutine.
Proof of Theorem 2.2. Let D E (calizable(A)) and m E N. Learning rule A operates as follows. Given sample S = ((x {= (((,,,1)) (1),,,....... (I': }m)).. A simulates an online learning game, which {0, 1ixx is the set of 'instances", and the learner's utility for playing expert
the set of "experts', (z,, y) on instance / F is 1 (f(x) + y). Namely, in this game the learner attempting to select an (zz, y) pair that disagrees with the instance f.
15

---

In this simulation, the learner executes an instance of the online learning algorithm of Appendix A.2 with expert Denote this instance Og.-
The adversary's i strategy is as follows. Recall that at each round t, Os chooses distribution over S. Note that if S realizable then so wt At each round f, the adversary selects an instance f E F by executing A on training set sampled from wy, as in Algorithm 1.
We prove the following:
1. A interpolates, namely (( = =0] =1
2. A has logarithmic KL-stability, in Eq. (8).
3. A PAC learns H. as in Eq. (9).
For Item assume for contradiction that A does not interpolate. Maj(S)....;fr)) there exists an index E [m]] such that
Seeing
A outputs
T
2 S Σ
v.) v.) = U(i,T),
(10)
where U(i, T) is the utility of always playing expert i throughout the game.
Let & denote the event that St was resampled (i.e., there were multiple iterations of the dh-we loop in round t). Eq. (7) and Markov's inequality imply
P (((.(A(S.) || P) 2 2b/7| S 7/2.
(11)
The utility of Os at time t is
Oy Ur
[f((x) * v)] f(rA(Se)
Lww (A(S:)) - + P -
-
where the last inequality follows from Eqs. (6) and (1 1). Hence, the utility of Os throughout the game is
U(Os, T)
Σ
4
O. <
2 2
? T.
(12)
t=1
Combining Eqs. (10) and (12) and Theorem A.6 yields
7 T s U(, U(Os, T) I Regret(Os,, T) 27 log(m),
which is contradiction for our choice of T' This establishes Item 1.
For Item 2, for every É N let Pj- A( 1)*²) be the distribution of Maj(gi..... .e),, where (gI.....go 9t) pt. Let p Eee P2/e where Σi 1/62 7²/6 6 normalization factor.
For any E (X' x (0,1))
(S) || P+) = KL(Maj( /1, fT) (ei()))..,,9)))
KL((S...... fr) || (91..... gr))
(By Lemma A.2)
Σ (L((fllfe)) (grle<)))
(By Lemma A.4)
(L((Al)E))) 9l)
(gs 's are independent)
Σ KL(A(S)) PP) < T 26/7 = O(log(m)),
(13)
16

---

where the last inequality is due to the do-while loop in Algorithm 1. For any S E (A' x {0, (0,1))",
Pa-(s((1)) )
KL(AM(S) || P*) = PA-PA
log
(*(h)
log (h)(s)(h)
)]
BA~PA-(S)
pT(h)/(2TT))
KL(AT(8) PT) + +O(log(T)) O(log(m)).
(By Eq. (13))
This establishes Item
Item 3 follows by plugging 3 I and Items 1 and 2 in the PAC-Bayes theorem (Theorem 3.2), yielding
LD(A o ( (loBmm)
1
IP
m
m
This implies Item 3 because the 0-1 loss is at most 1.
Remark A.7. Our definition of the learning rule A depends A and P. The mapping Se
KL(A(S)) P) is well-defined, so A is well-defined learning rule.
B Proof of Theorem 2.1 (DI Equivalences)
In this section, we prove Theorem 2.1.
Theorem (Theorem 2.1, Restatement). Let be a hypothesis class. The following is equivalent.
1. There exists a learning rule that PAC learns H and satisfied pure differential privacy (Definition 3.5).
2. H has finite fractional clique dimension.
3. For every
(o), there exists learning rule that PAC learns H and satisfied distribution-inue -nribedioo--ddeeeedeen Da-stabilin (Definition 3.6).
4. For every E [1, so), there exists distribution-independde stastable PAC learner A for H. that satisfies the following:
(i) A is interpolating almost surely. Namely, for every H-realizable distribution D, P PSwamm [Ls(A(()) =
(ii) A admits divergence bound of f(m) O(log m), with confidence 3(m) = 0. Lee. for every H-realizable distribution D, (A(S) < Ollo m) with probability 1, where S ~ m and P is a prior distribution independent of
(iii) For every H--rellizable distribution D, the expected population loss of A with respect D satisfies Es-D=|LD(AAe (L)AA))) < (Vm-> lon--logmo log
In particular, plugging 1 in Item (ii) implies KL-stability with divergence bound of fmm Olog m) and confulecce ((m) = Plugging a = oc implies distribution-ndeeeedder one-way E-pure perfect generalization, with E(m) I O(log m.) and confidence 3mm) = 0.
The next subsections contain Theorem B. which is a useful result from [AMSY23), followed by the statements and proofs of Lemmas B.2 and B.4. which rely Theorem B. and our boosting result (Theorem 2.2). The proof of Theorem 2.1 is a consequence of these results, as follows.
"We remark that if A is randomized Turing machine, then KL(A(S.) || P)) can be estimated arbitrary precision by Turing machine with oracle access the function P. Namely, consider Turing machine that can query an oracle for the value of P(h) up to precision 2 for any and q E N of its choosing. To see that such a machine can estimate KL(A(S.) P)) observe that A uses some finite number of random coins, then A(S,) has finite support, and so computing (L(A(S,) P) involves querying P finite number of locations. Moreover, if A
number R of random coins, which is itself random variable that may be unbounded but satisfies B[R] < oo, then by Markov's inequality there exists an explicit algorithm A' that uses most E[R]/o /a random coins, such that TV(A(S.). (S:)) < a. Hence, KL(A (S.)) || PP) can be estimated to arbitrary precision as before. Taking small enough values of a yields a modified version of A" that can be shown satisfy the requirements of Theorem 2.2.
17

---

Proof of Theorem 2.1. The proof follows from:
Theorem..
Lemma B.2
(+)
Item Lemma B.4
Item
Item 2
Item 4
Item 2,
where (+) is immediate.
B.1
Characterization of Pure DP Learnability via the Fractional Clique Dimension
For every hypothesis class H. they define quantity w win (H), called the fractional clique number of H. The definition of wi,, involves an LP relaxation of clique numbers on a certain graph corresponding to H. but for our purposes it will be more convenient to use the following alternative characterization (Eq. 6 and Theorem 2.8 in [AMSY23]):
Vm E N: W
sup inf P (h) = 0), R<P
(14)
where the supremum is taken over distributions over H. and the infimum is taken over distributions samples of size that are realizable by H. In words, 1/w is the value of game in which player selects a distribution of hypotheses over H. player selects a distribution over realizable samples of size m, and player wins if and only if the hypothesis correctly labels all the points in the sample.
The fractional clique number characterizes pure DP learnability, as follows:
Theorem B.1 (Restatement of Theorems 2.3 and 2.6 in [AMSY23]. For any hypothesis class H. exactly one of the following statements holds:
1. H is pure DP learnable (as in Definition 3.5), and there exists a polynomial such that wm (H) & p(m) for all m N.
2. H is not pure DP learnable, and w;, (H() = 2mh for all m E E.N
The fractional clique dimension of HL is defined by CD* sup {m N: w (HL 2 So in other words, Theorem B.1 states that H is pure DP learnable and only if CD' is finite.
B.2 Finite Fractional Clique Dimension = DI Rényi-Stability
Lemma B.2. In the context of Theorem 2.1: Item 2 = Item 4.
Proof of Lemma B.2. Given that H. is DP learnable, we define learning rule A and a prior P, and show that A PAC learns H subject distribution distribution-indeeeedeen KL-stability with respect to P.
By Theorem B.1 there exists polynomial such that w (HL S p(m) for all m N. By Eq. (14), for every m E N, there exists a prior P... E A (10, 1)²) such that for any H-realizable sample S (X x {0, 1))
1 w
I hnP
[s(h)
p(m)
Let
P.
p m²
m=1
be a mixture, where = Em 1/m² = x² 22/6 is a normalization factor. P a valid distribution over {0, 1
For every m E N and for any H-realizable sample S E (X x 1)
1
1
P
Ls(h) = 2
P [Ls(h) 0] 2 2m²p(m) zm2 h-Pan
(15)
h-p
q(m))
where ((m) 2m3 =m²
For any sample S, let Cs {n (0.1)* Ls(h) = 0} be the set of hypotheses consistent with S. Let A be randomized learning rule given by S Qs E A(00, 1)²) such that @s(h) P(h Cs) if h E C's, and @s(h) 0 otherwise. A can be written explicitly rejection sampling algorithm:
18

---

A(S):
do:
sample/ 1 <- P while (h) > return h
Algorithm A terminates with probability 1, because for any realizable sample S of size m N and any E N,
PPAA did not terminate after iterations] = (IP (Psw) 0))* v (1- (-m/mm)) L00, 0,
where the inequality follows by Eq. (15).
To complete the proof, show that A satisfies (f), (ii) and (iil) in Item 4.
Item (i) is immediate from the construction of A. For Item (ii), let m N. For any sample S of size and hypothesis h E Cs.
@s(h) = P(h Cs) P(sh)n(s) P(Cs) S <(()) P(h),
(16)
where the inequality follows from Eq. (15). Hence,
2s(h)
(2s || P) = log
ess sus
P(h)
Qs
g(m)
P(h)
< log
sup
(from Eq. (16) and Qs(Cs) 1)
P(h)
2s
< log(((mm) (log(mm))
Item (ii) follows from monotonicity of D. with respect (Lemma A.1). In particular, KL Qs (P) = O(l)gmm)).
Item (iii) follows from the PAC-Bayes theorem (Theorem 3.2). Indeed, take B 1 and note that Lg( @s) = for all realizable Then for any H-realizable distribution D, m
KL PP) + 2
1 m
P
(D(S))
SmDm
2(m - 1)
This implies that for any H-realizable distribution D,
E SmDm
1 (AA(S))
KL(Os P) + Inm
O
log m
m 2(m 1)
desired.
Remark B.3. The 'furthermore' section of Lemma A.I implies that in the foregoing proof.
D. Qs || (P) D2(2s || for any a, c0).
B.3 DI Rényi-Stability
Finite Fractional Clique Dimension
Lemma B.4. In the context Theorem 2. Item 3 = Item 2.
Proof of Lemma B.4. By Theorem B.1 and Eq. (14) it suffices show that there exist m and prior P such that for every H-realizable sample S E (X x 10)
1
[T)(h) 0] > hop
P
(17)
2
By the assumption (Item 3) and Theorem 2.2, there exists an interpolating learning rule A prior P*, and constant C' >> 0 such that for every D E Realizable(?)), the equality
Ps-p= (KLAAA(S)) || P*) < Cllg(m)) =
(18)
19

---

holds for all m E N large enough. Fix such an m. We show that taking P = p* satisfies Eq. (17) for this m.
Let Q denote the distribution of AT")") where S ~
(U(S)) = Ps. U(S) is the uniform distribution over S, and m' (n(1m))m) 4m). The proof follows by noting that if KL( P*) small then one can lower bounding the probability of an event according to P by its probability according
To see that the KL is indeed small, let ss)) and PH*,St be two joint distributions. The variable S' has marginal Ps in both distributions, (*") ~ Q depends on S", but H ~ p is independent of S". Then,
KL(Q P*) = KL(PA-(S)) PH-)
< KL (A-(S)))s)) PH--I Ps.))
(Lemma A.5)
KL -KL(PAr(SS)) PH- Ps'
(H* (I*-S")
= Es (SL(AK()A PP)]
(Definition of conditional KL) (By Eq. (18) and choice of m)
S (loggmmm.
(19)
Taking k = 2C 2Cloo)(m)
P log 2(h) (*(h)
KL P*) 1
P*)
2 2k
(20)
k
2
holds by Markov's inequality and the definition of the KL divergence. We are interested in the probability of the event & = =t {0,1)* Ls(h) = -}. Because A" is interpolating,
m
IS C S*) 2 (1 (S')
3
Q(E) 2 PP
S' (U(()))
2
(21)
4
Finally, we lower bound (E( as follows.
((h)
P*(E) 2 P A log (*) s
hwp.
I hap.
[E A (*(h) 2 k 2(h)]
E (*(h)= 2 2 k. 2(h) 2-
h
Q(h)
P a~2
3 A
log
2
p-(h)
2(1)
Q(E)
P
log
S
2-
(De Morgan's union bound)
hvQ
(*(h))
(By Eqs. (20) and (21) and choice of k:)
4m 20
poly(m)
This establishes Eq, (17), as desired.
C Proof of Theorem 1.4 (DD Equivalences)
C.1 Preliminaries
C.1.1 Littlestone Dimension
The Littlestone dimension is combinatorial parameter which captures mistake and regret bounds in online learning [Lit87, BPS09].
Definition C.1 (Mistake Tree), A mistake tree is binary decision tree whose nodes are labeled with instances from X and edges are labeled by 0 or such that euch internal node hus one outgoing edge labeled 0 and one outgoing edge labeled 1. A root-to-leaf puth in mistake tree can be described as a sequence of labeled examples (I1, ,,,,,, ..., (I's ya). The point xa is the label of the i-th internal node in the path, and ys is the label of its outgoing edge the next node in the path.
20

---

Definition C.2 (Shattering). Let H. be hypothesis class and let T be mistake tree. H. shatters T if every root-to-leaf path
realizable by H.
Definition C.3 (Littlestone Dimension). Let H. be a hypothesis class. The Littlestone dimension H, denoted LDH),, is the largest number such that there exists a complete mistake tree of depth d shattered by H. H shatters arbitrarily deep mistake trees then LD(H) oc.
C.1.2 Clique Dimension
Definition C.4 (Clique; [AMSY23]). Let H be a hypothesis class and let m E N. A clique in H of order m is a family S of realizable samples of size such that (i) |S| 2m; (ii) every two distinct
samples 5" S" E contradicts, i.e., there exists a common example x E X such that (z, 0) E S and (xx 1) S".
Definition C.5 (Clique Dimension; [AMSY23). Let H be a hypothesis. The clique dimension of H. denoted CD(H), is the largest number m such that H contains clique of order m. If H contains cliques of arbitrary large order then we write CD(H) = cc.
C.2 Global Stability
=
Replicability
Lemma C.6. Let H be hypothesis class and let A be a (m, (t..n))glbblll stable learner for H. Then, A an n-replicable learner for H.
This follows immediately by noting that global stability is equivalent to 2-parameters replicability. which is qualitatively equivalent to 1-parameter replicability (II.PS22..
Lemma C.7 (ILPPS22). For every P, V E [0,
1. Every p-replicable algorithm is also ( -replccbblee
2. Every (n, reeplliaabl algorithm is also (17 + 2v 2)-replicable.
Proof of Lemma C.6. By the assumption, there exists an hypothesis such that for every population D. we have IP RR-R RR sm (A(S;r) = h] 2 ni = 1. Hence A is (n, 1errepicca, and by Lemma C.7 is also nyreplicabbe.
C.3 DD KL-Stability = Finite Littlestone Dimension
Lemma C.8. Let H be hypothesis class that is distribution-dlepeneen KL-stable. Then H. has finite Littlestone dimension.
This lemma an immediate result of the relation between thresholds and the Littlestone dimension, and the fact that the class of thresholds on the natural numbers does not admit any learning rule that satisfies a non-vacuous PAC-Bayes bound [LM20]. The next lemma is corollary of Theorem 2 in [LM20].
Theorem C.9 (Corollary of Theorem 2 [LM20]). Let m E N and let N E N. Then, there exists N large enough such that the following holds. For every learning rule A of the class thresholds over (n], H., = {1l [a [n] + {0, 13 k [n]], there exists realizable population distribution
D DA such that for any prior distribution P,
IP SmD m
KL(A(S) 1| N or Lp(A(S)) >
2 16
4
Theorem C.10 (Littlestone dimension and thresholds [Shc90]). Let H. be hypothesis class. Then,
1. LDH) 2 then contains [log d] thresholds.
2. If H contains d thresholds then LD(H) > [logd].
Proof of Lemma C.8. If by contradiction the Littlestone dimension of H is unbounded, then by Theorem C0 H contains copy of H. the class of thresholds over [n], for arbitrary large n n's. Hence, by Theorem C.9 H does not admit PAC learner that is KL-stable.
D
21

---

C.4 MI-Stabiliity DD KL-Stability
Lemma C.11. Ler H. be a hypothesis class and let A a mutual information stable learner with information bound f(m) = o(1. (L.e for every population distribution DD I (A(S); S f fmm where ~ "Dm Then, A a distribution-dependee KL-stable learner with KL bound g g(m) VJ(m) m and confidence ((m) Vf(m)/m
The following statement is an immediate corollary.
Corollary C.12. Let H be a hypothesis class that is mutual information stable. Then distribution- dependent KL-stable.
Proof of Lemma C.I1. Let D be population distribution. Define a prior distribution Pp Es(A(()) ((S)], i.. Pp(h) (Ps-D"[A( = h]. We will show that A is KL stable with respect to the prior PD. We use the identity [() = KL(Px,y, P.Pr). Let (S))). be the joint distribu- tion of the training sample S and the hypothesis selected by A when given S as input, and let PA(S) Ps be the product of the marginals. Note that PA(Sy Ps equal in distribution to PA(S Ps.
where is an independent copy of S. Hence,
I(A(S):)) = (L(PA(S),S: Ps) (L((Ass) Ps, P Ps),
= KL, Ps) + Esn.s
(Chain rule)
Ex-Ps
KL (K(A PA(S))S==))
P3 KL (PA()))SSS: PA
Note that ParsS)) and the prior PD identically distributed, and PA(S)]==a is exactly the posterior produced by given the input sample 8. By Markov's 's inequality,
KL(A(S) Pb) 2 Vm. (IA(((A(S)))) S I(A(S):))
P 9~Dm
(A(S:)
I(A(S):))
(22)
m
Since I(A(S):S) ((m), by Eq. (22)
KL(A(S) Pb) Z Vf(m) m 1/ f(m)
8-1
Note that since (mm)=((m) o(m), indeed / fm m m0000
0 and
v f(m)
o(m).
C,5 Finite Littlestone Dimension =
MI-Stability
Lemma C.13. Let H be a hypothesis class with finite Littlestone dimension. Then H admits information stable learner.
This lemma is a direct result of Theorem 2 in [PNG22).
Definition C.14. The information complexity of a hypothesis class is
IC(H) sup inf sup I S)
|s] A
where the supremum is over all sample sizes |S| E N and the infimum is over all learning rules that PAC learn H.
Theorem C.15 (Theorem 2 [PNG22]). Let H be a hypothesis class of with Littlestone dimension d. Then the information complexity of H. is bounded by
3
IC(H) < 2d log(d +) eln
Proof of Lemma C.I3. Since finite information complexity implies that 7/ admits an information stable learner, the proof follows from Theorem C.15
22


Reviews:
[{"review_id": "7rPDqrTuT2", "reviewer": "Reviewer_c5ne", "summary": "The paper shows that many definitions of the \"stability\" in learning theory are equivalent (according to a specific definition of equivalence).\nThey 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.\nThis summary allows a unified view across many stability-related concepts in the literature.\nThe submission also proves a result related to boosting, showing that a weak learner can be amplified to obtain better stability and learning performance.", "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.\nIt seems to me we actually want the difference between two possible posteriors when applied to two similar realizations of $S$ to be small.\nWhat if the data really disagree with the prior; wouldn't we have a large difference between the prior and the posterior regardless?\n- On line 39, what makes the definition of stability Bayesian exactly? Because we iterate over possible realizations of $S$?\n- 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)?", "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.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and has a clear organization.\nThe concept of stability studied in the paper is an important one in learning theory.\nBy 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.\nI suggest the authors consider clarifying the details asked in my questions in the following section to make the paper clearer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.**\n\nConsidering the \"distance\" between a prior distribution and the posterior is very common. (The word \"distance\" is in quotation since the measure of dissimilarity between them does not need to be a metric, e.g. the Kullback–Leibler divergence.) \nFor example, in the context of generalization, PAC Bayes Theorem assures that for every population distribution and any given prior $\\mathcal{P}$, the difference between the population error of an algorithm $A$ and the empirical error is bounded by $\\tilde{O}\\left(\\frac{\\sqrt{\\mathtt{KL}(A(S),\\mathcal{P})}}{m}\\right)$, where $A(S)$ is the posterior distribution, $\\mathtt{KL}(A(S),\\mathcal{P})$ is the KL divergence between the prior and the posterior (``measure of dissimilarity\"), and $m$ is the size of the input sample $S$. See e.g. Theorem 31.1 in [1].\n\n**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?**\n\nYour suggestion of measuring the dissimilarity between two posterior distributions is widely used as well, this is very related to the definition of Replicability. In the paper we proved that those notions of stability are equivalent.\n    \n**On line 39, what makes the definition of stability Bayesian exactly? Because we iterate over possible realizations of $S$?**\n\nOur choice of the name *Bayesian* stability is inspired by Bayesian statistics, which uses the terms *prior* and *posterior*. In Bayesian statistics the analyst has some prior distribution over possible hypothesis before conducting the analysis, and chooses a posterior distribution over hypotheses when the analysis is complete. Bayesian stability is defined in terms of the dissimilarity between these two distributions.\nWe will happily add this remark to the final version of the paper to clarify our choice of the term `Bayesian stability'.\n    \n**In Section 2.1.1, does the chain mean only Pure DP implies $D_\\infty$-Stability and the like but not vice versa ($D_\\infty$-Stability implying Pure DP)?**\n\nNo, $D_\\infty$-stability does imply pure DP, since $D_\\infty$-stability implies $D_\\alpha$-stability for every $\\alpha\\in[1,\\infty]$, which in turn implies pure DP.\n\n\n[1] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine\nLearning– From Theory to Algorithms. Cambridge University\nPress, 2014."}, {"review_id": "MoPeefsGwm", "reviewer": "Reviewer_uUZW", "summary": "**Post-rebuttal**\n\nI thank the authors for their response. I will keep my score as is.\n\n\nThis work aims at building a comprehensive taxonomy of stability definitions showing that many definitions of stability are equivalent to each other.", "questions": "* How is TV indistinguishability related to TV stability?", "limitations": "I do not foresee any potential negative societal impact of this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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).\n\n\n* TV indistinguishability (alluded to in the abstract) is not defined in the main text or supplementary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " **TV indistinguishability (alluded to in the abstract) is not defined in the main text or supplementary. How is TV indistinguishability related to TV stability?**\n    \n\nThey are the same. [1] used the term TV-indistinguishability and we preferred to use the term TV-stability, we believe that it emphasises the fact that this definition is a form of algorithmic stability. We do note that [1] defined TV-indistinguishability slightly different from our definition of TV-stability (see Definition 4 in [1]), but they also showed in Appendix A.3.1 that their definition is equivalent to ours (up to some constant factors).\nThe term \"TV-indistinguishability'' appears only once (in the abstract), we will change this to \"TV-stability'' to eliminate this potential confusion.\n    \n**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).**\n\n We will add more background and intuition about the various notions of stability studied in this paper and the connections between them.\n\n\n[1] Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas.\nStatistical indistinguishability of learning algorithms, 2023.\n"}, {"review_id": "mcrIuMFJI3", "reviewer": "Reviewer_RbiN", "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.", "questions": "Can the authors provide some examples on what the equivalence results can help connecting the literature of different stability literature?", "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.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "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.\n\n2. 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.\n\n3. The writing and structure of the paper can be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**This paper introduces a series of definitions without any literature, for example, $\\mathsf{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.**\n    \n$D_\\alpha$ is well motivated. $D_1$ corresponds to KL-divergence and $D_\\infty$ corresponds to Perfect Generalization -- both of which are well-studied notions. Therefore, it is natural to consider $D_\\alpha$ stability for $\\alpha \\in (1,\\infty)$.\n\nMoreover, there is also literature regarding $D_\\alpha$-Stability as well. For example, [1] showed a generalization bound using R\\'{e}nyi divergence (Theorem 2 and Corollary 5).\n        \n**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.**\n \nOne example is the connection between pure differential privacy and the PAC-Bayes theorem. Both of these are fundamental ideas that have been extensively studied. Theorem 2.1 states that a hypothesis class admits a pure differentially private PAC learner if and only if it admits a distribution independent KL-stable PAC learner. This is an interesting and non-trivial connection between two well studied notions.\n        \nAs a concrete example of this connection, recall that thresholds over the real line cannot be learned by a differentially private learner. Hence, by Theorem 2.1, there does not exist a PAC learner for thresholds that is KL-stable. Another example is half-spaces with margins in $\\mathbb{R}^d$. Half-spaces with margins are differentially private learnable [2], therefore there exists a PAC learner for half-spaces with margins that is KL-stable. Those are examples of the type of connections that our paper elucidates. (There are many many other possible examples.)\n        \n\n**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.**\n\nWe will add further discussion and background about the definitions of stability that we study.\n\n\n\n**References**\n\n[1] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Robust\ngeneralization via $\\alpha$-mutual information. CoRR, abs/2001.06399,\n2020.\n\n[2] Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005, June). Practical privacy: the SuLQ framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (pp. 128-138)."}, {"review_id": "4Mx6vngcf3", "reviewer": "Reviewer_V99Z", "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.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**I found the order of the sections to be weird -- section 3 on preliminaries should be before section 2 for example.**\n\nThe current order was chosen so that the main contributions of the paper will appear as early as possible (this is common practice in some conferences). However, we agree that it makes sense to have the preliminaries appear before the technical overview, and we are happy to swap the order of these sections."}, {"review_id": "GJQo67rYKu", "reviewer": "Reviewer_xEWt", "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.", "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.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. The authors establish the equivalence between different definitions of stability.\n2. 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.\n\n2.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.\n\nTheorem 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " **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.**\n\nPAC learnability is defined on line 193 of the paper. You are correct that we neglected to state the full unabbreviated name (\"Probably Approximately Correct''). We believe most readers would be familiar with this abbreviation, but nonetheless we will add the full unabbreviated name in the final version.\n   \n**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.**\n        \nWe believe that this work has to include a fair amount of previous work and preliminaries, because it studies connections between many notions of stability that exist in the literature. We agree with this reviewer that it is important that the paper be self-contained (as they mentioned), and this requires providing sufficient detail on existing notions. \n\nWe are also happy to add additional discussion about our main theorems, including their intuitive meaning and significance.\n  \n**The main weakness of the paper lies in the overlap between the main contribution and existing results, leading to insufficient novelty. [...] 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.**\n\nThis is not accurate. Theorem 2.1 (which the reviewer mentions) is in fact an original contribution of this paper and is NOT a review of existing results. It involves a non-trivial proof, an relies on our stability boosting result (Theorem 2.2). These are meaningful original contributions.\n\nRegarding Theorem 1.3 and Figure 1, these are indeed summaries of existing results. However, we believe that these parts of the paper constitute a meaningful conceptual contribution. Namely, our observation that a large number of disparate results can neatly be organized based on our notions of distribution-dependent and distribution-independent notions of stability is a valuable contribution that could help researchers make sense of the stability landscape.\n\n**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.**\n\nThe paper from \"Robustness to Privacy and Back'' studies connections between privacy and *robustness to adversarial perturbations of the input*. This form of robustness is technically different from the baysian stability notions considered in our paper.\n\n**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^\\star$ in Theorem 2.2 in the appendix, I believe that this construction should be highlighted in the main body to showcase its novelty.**\n\nThank you for this positive appreciation! We are happy to further highlight the value and novelty of our construction in the final version of the paper.\n    \n**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^\\star$ in Theorem 2.2. As a result, it is uncertain whether this construction holds practical significance without empirical evidence.**\n\nIndeed, it would be valuable to perform an empirical evaluation of our work. Our work is purely theoretical/mathematical, and we leave experimental evaluations to future research.\n"}]

Author rebuttal:

Meta-review: This manuscript concerns various notions of "stability" in Bayesian procedures that have appeared in the literature and establishes some novel equivalences among this "zoo" of possible choices.

Overall, the reviewers felt this topic was compelling and would be of interest to the NeurIPS community. No major objections were raised during the review or discussion period.

However, the discussion period did prove fruitful in revealing and clarifying a number of confusing elements in the manuscript as submitted. I strongly suggest that the authors carefully reflect on this feedback in preparing an updated version of their manuscript.
Decision: Accept (poster)