Towards a Unified Information-Theoretic Framework for Generalization

Abstract:
In this work, we investigate the expressiveness of the “conditional mutual information” (CMI) framework of Steinke and Zakynthinou [1] and the prospect of using it to provide a unified framework for proving generalization bounds in the realizable setting. We first demonstrate that one can use this framework to express non-trivial (but sub-optimal) bounds for any learning algorithm that outputs hypotheses from a class of bounded VC dimension. We then explore two directions of strengthening this bound: (i) Can the CMI framework express optimal ti l a ti l bounds for VC classes? (ii) Can the CMI framework be used to analyze algorithms whose output hypothesis space is unrestricted t i t r s r e c e t i t r r (i.e. has an unbounded VC dimension)? With respect to Item (i) we prove that the CMI framework yields the optimal bound on the expected risk of Support Vector Machines (SVMs) for learning halfspaces. This result is an application of our general result showing that stable compression schemes [2] of size k have uniformly bounded CMI of order O(k). We further show that an inherent limitation of proper learning of VC classes contradicts the existence of a proper learner with constant CMI, and it implies a negative resolution to an open problem of Steinke and Zakynthinou [3]. We further study the CMI of empirical risk minimizers (ERMs) of classH and show that it is possible to output all consistent classifiers (version space) with bounded CMI if and only if H has a bounded star number [4]. With respect to Item (ii) we prove a general reduction showing that “leave-one-out” analysis is expressible via the CMI framework. As a corollary we investigate the CMI of the one-inclusion-graph algorithm proposed by Haussler et al. [5]. More generally, we show that the CMI framework is universal in the sense that for every consistent algorithm and data distribution, the expected risk vanishes as the number of samples diverges if and only if its evaluated CMI has sublinear growth with the number of samples.

heading: 1 Introduction
text: In this work, we study the expressiveness of generalization bounds in terms of information-theoretic measures of dependence between the output of a learning algorithm and input data. Informationtheoretic techniques for proving generalization bounds are powerful; they can provide generalization ∗Part of the work was done the author was an intern at Element AI, a ServiceNow company. †This work was carried out while the author was at ServiceNow. It was finalized at Google Brain.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
bounds that are algorithm-dependent, data-dependent, and distribution-dependent. This approach was initiated by Russo and Zou [6, 7] and Xu and Raginsky [8] and has since been extended by a number of authors [9–19]. More recently, attention has shifted to whether these techniques can also characterize worst-case (minimax) rates for certain learning problems.
Let D be an unknown distribution on a space Z , and let H be a set of classifiers. Consider a (randomized) learning algorithm A = (An)n≥1 that selects an element ĥ in H, based on n i.i.d. samples Sn ∼ D⊗n, i.e., ĥ = ĥn = An(Sn). The initial focus of this line of work was on the mutual information I(An(Sn);Sn) between the input and the output of a learning problem. This quantity is sometimes referred to as the input–output mutual information (IOMI) of an algorithm and denoted by IOMID(An). A natural question is whether the IOMI framework can provide a sharp characterization of the learnability of Vapnik–Chervonenkis (VC) classes, for which we have strong generalization guarantees. A negative resolution was provided by Bassily et al. [12] for the concept class of thresholds in one dimension. Follow up work by Nachum et al. [13] extended the argument in [12], proving the following result:
Theorem 1.1 (Thm. 1, [13]). For every d ∈ N and every n ≥ 2d2, there exists a finite input space X and a concept classH ⊆ {0, 1}X of VC-dimension d such that, for all proper and consistent learning algorithmAn, there exists a realizable distribution D such that IOMID(An) = Ω(d log log(|X |/d)).
Livni and Moran [18] extended this result even further, showing that, for the class of one-dimensional thresholds over {1, . . . ,m}, m ∈ N,3 for every learning algorithm A there exists a realizable distribution such that either the risk (population loss) is large or the IOMID(An) scales with the cardinality of the space, m. These results highlight an important limitation of the IOMI framework: given an unbounded input space, for any “good” learning algorithm there are always scenarios in which IOMID(An) is unbounded. Therefore, the distribution-free learnability of VC classes cannot be expressed using the IOMI framework.
In this paper, we focus on the “conditional mutual information” (CMI) framework, proposed by Steinke and Zakynthinou [1]. In order to reason about the generalization error of a learning algorithm, they introduce a super sample that contains the training sample as a random subset and compute the mutual information between the input and output conditional on the super sample (formal definitions are provided in Section 2.1). Improvements of this framework and its application in studying the generalization of specific learning algorithms have been studied in [20–25].
The current paper revolves around the following fundamental question: For which learning problems and learning algorithms is the CMI framework expressive enough to accurately estimate the generalization error? We will focus in particular on whether we can recover optimal worst case (minimax) rates for VC classes satisfying certain properties. The answer to these question provide evidence that the CMI framework provides a unifying framework for studying generalization.
For VC classes, Steinke and Zakynthinou [1] revealed a stark separation between the CMI framework and IOMI framework. They showed the existence of an empirical risk minimization (ERM) algorithm whose CMI is no larger than d log n + 2 for learning every VC class of dimension d given n i.i.d. training samples. In contrast to Theorem 1.1, CMI does not scale with the cardinality of the space. However, the bound on the CMI combined with Steinke and Zakynthinou’s CMI-based generalization bound, leads to a bound on the expected excess risk that is suboptimal in some cases by a log n factor. (For an overview of the known bounds for learning VC classes, please refer to Appendix A.) The suboptimality of their bound prompted Steinke and Zakynthinou [3] to conjecture that the CMI bound for proper learners of VC classes can be improved to O(d). Moreover, Steinke and Zakynthinou connected CMI framework to the sample compression framework of [26] by showing that a sample compressionAn of size k has CMID(An) ≤ k log 2n. Their bound for sample compression schemes is also suboptimal in some cases by a log n factor.

heading: 1.1 Contributions
text: In this paper we extend the reach of the CMI framework by demonstrating its unifying nature for obtaining optimal or near-optimal bounds for the expected excess risk of the various algorithms in the realizable setting.
3This concept class can be defined as follows. Let X = {1, ...,m}. Let k ∈ N and hk : X → {0, 1} define as hk(x) = 1[x > k]. Then, the class of one-dimensional thresholds over {1, ...,m} is Hm = {hk|k ∈ N}.
1. We demonstrate that one can use the CMI framework to express non-trivial (but sub-optimal) bounds for every improper learning algorithm that outputs a hypothesis from a class with a bounded VC dimension. This is achieved by an empirical variant of CMI defined by [1].
2. We study the CMI of SVMs for learning half spaces and show that the CMI framework yields optimal bounds on the expected excess risk. Our bound on the CMI of SVM is an application of our general result giving optimal CMI bounds for stable sample compression schemes [2, 27], which improve on CMI bounds for general sample compression schemes [1] by a log n factor.
3. In the context of proper learning of VC classes, we exhibit VC classes for which the CMI of any proper learner cannot be bounded by any real-valued function of the VC dimension. Then, we consider VC classes with finite star number [4], and prove the existence of a learner with bounded CMI. Finally, we show that the release of the set of all consistent classifiers in H has bounded CMI if and only if H has finite star number.
4. We show that CMI framwork is universal in the realizable setting. More precisely, for every data distribution and consistent learner, the bound on excess risk obtained by the CMI framework vanishes if and only if the excess risk also vanishes as the number training samples diverges. We then show that any learning algorithm with a “leave-one-out” bound of order O(1/n) yields an evaluated-CMI bound of order O(log n). As an application, we study the classical one-inclusion graph algorithm of Haussler et al. [5] for improper learning of VC classes, and provide a nearly optimal bound on its expected excess risk using the CMI framework. We also prove there exists a randomized one-inclusion graph which learns point functions (singleton) with bounded CMI.
Our results indicate that CMI is a very expressive generalization framework, and one that can tie together existing frameworks. Although most of our results are stated for binary classification in the distribution-free setting, it is interesting to note that the CMI framework is known to provide numerically non-vacuous generalization error guarantees for some modern deep learning models and datasets in the distribution-dependent setting [21, 25]. These developments in a range of different problem settings highlight the importance of understanding the expressiveness of the CMI framework.

heading: 2 Preliminaries
text: We consider the problem of binary classification, with inputs in some space X assigned labels in Y = {0, 1}. A concept (or hypothesis) class H ⊆ YX is a set of functions h : X → Y . We say H shatters (x1, . . . , xm) ∈ Xm if for all (y1, . . . , ym) ∈ {0, 1}m, there exists h ∈ H, such that, for all i ∈ [m], we have h(xi) = yi. The VC dimension ofH, denoted by d, is the largest m ∈ N for which there exists (x1, . . . , xm) ∈ Xm shattered byH. If no such finite m exists, then d =∞. Let D be a distribution on Z = X × Y . The empirical (classification) risk of a classifier h : X → Y on a sample s = ((x1, y1), . . . , (xn, yn)) ∈ Zn is R̂s(h) = n−1 ∑ i∈[n] `(h, (xi, yi)), where `(h, (x, y)) = 1[h(x) 6= y]. Let Sn ∼ Dn, i.e., let Sn be a sequence of i.i.d. random elements in Z with common distribution D. (We can view Sn itself as a random element in Zn.) The risk of h is RD(h) = ER̂Sn(h), where E denotes the expectation operator. (The risk has, of course, no dependence on n due to the data being i.i.d.)
A distribution D is realizable by a class H ⊆ YX if there exists h ∈ H such that RD(h) = 0. A sequence ((x1, y1), . . . , (xn, yn)) is said to be realizable by H, if for some h ∈ H, h(xi) = yi for all i ∈ [n] = {1, . . . , n}. Note that if a distribution is realizable byH, it implies that with probability one over Sn ∼ Dn, the training sample Sn is realizable byH. Let A = (An)n≥1 denote a (potentially randomized) learning algorithm, which, for any positive integer n, maps Sn to an element of X → Y . We say that A is a proper learner for a class H ⊆ X → Y if the codomain ofAn is a subset ofH for every n. We sayAn is a consistent algorithm (learner) if R̂Sn(An(Sn)) = 0 a.s. Our primary interest in this paper is the expected generalization error of An with respect to D, defined as EGED(An) = E[RD(An(Sn))− R̂Sn(An(Sn))], where we average over both the choice of training sample and the randomness within the algorithm An.

heading: 2.1 Conditional mutual information (CMI) of an algorithm
text: In order to study generalization, and avoid some of the pitfalls of earlier approaches based on mutual information, Steinke and Zakynthinou [1] propose to study the information contained in a
“supersample”Z, a training sample Sn taken from the supersample, and the hypothesisAn(Sn) output by a possibly randomized learning algorithm, given Sn as input. Formally, let Z = (Zi,j)i∈{0,1}, j∈[n] to be an array of i.i.d. random elements in the spaceZ of labeled examples, with a common distribution D. In order to choose a training sample Sn of size n from Z, let U = (U1, U2, . . . , Un) be a sequence of i.i.d. Bernoulli random variables in {0, 1}, independent from Z, with P(Ui = 0) = 1/2. Define Sn = ZU = (ZUj ,j) n j=1. The conditional mutual information (CMI) of An, denoted CMID(An), is defined to be the mutual information between An(Sn) and U given Z, denoted I(An(Sn);U |Z). This quantity is equivalent to I(An(Sn);Sn|Z) when D is atomless, since (U1, . . . , Un) is a.s. measurable with respect to Sn and Z. Because Z and U are independent, CMID(An) ≤ H(U |Z) = H(U) = n log 2. We now pause to introduce this and other information-theoretic quantities formally.

heading: 2.2 Measures of divergence and information
text: Let P,Q be probability measures on a measurable space. (We ignore measure-theoretic pathologies for clarity.) For a P -integrable or nonnegative function f , let P [f ] = ∫ fdP . When Q is absolutely continuous with respect to P , denoted Q P , write dQdP for (an arbitrary version of) the Radon– Nikodym derivative (or density) of Q with respect to P . The KL divergence (or relative entropy) of Q with respect to P , denoted KL(Q ‖P ), is defined as Q[log dQdP ] when Q P and infinity otherwise.
For a random element X in some measurable space X , let P[X] denote its distribution, which lives in the spaceM1(X ) of all probability measures on X . Given another random element, say Y in T , let PY [X] denote the conditional distribution ofX given Y . IfX and Y are independent, PY [X] = P[X] a.s. For an event, say X ∈ A, PY [X ∈ A] denotes the event’s conditional probability given Y , which is defined to be the conditional expectation of the indicator random variable 1[X ∈ A] given Y , denoted EY 1[X ∈ A].4 By the chain (aka tower) rule, EEF = E for any σ-algebra F . The mutual information between X and Y is I(X;Y ) = KL(P[(X,Y )] ‖P[X]⊗ P[Y ]), where ⊗ forms the product measure. Writing PZ [(X,Y )] for the conditional distribution of the pair (X,Y ) given a random element Z, the disintegrated mutual information between X and Y given Z, is
IZ(X;Y ) = KL(PZ [(X,Y )] ‖PZ [X]⊗ PZ [Y ]). Then the conditional mutual information of X and Y given Z is I(X,Y |Z) = EIZ(X,Y ). Let µ = P[X] and let κ(Y ) = PY [X] a.s. If X concentrates on a countable set V with counting measure ν, the (Shannon) entropy of X is H(X) = −µ[log dµdν ] = − ∑ x∈V P(X = x) logP(X = x). The disintegrated entropy of X given Y is defined by HY (X) = −κ(Y )[log dκ(Y )dν ], while the conditional entropy of X given Y is H(X|Y ) = E[HY (X)]. Note that H(X|Y ) ≤ H(X). We will make use of the following lemma whose proof can be found in [28]. Lemma 2.1. Let (X1, X2, . . . , Xn) be a discrete random vector, and Y be an arbitrary random variable. Then, H(X1, . . . , Xn|Y ) ≥ ∑n i=1 H(Xi|X−i, Y ), where X−i = (Xj : j ∈ [n], j 6= i).
Steinke and Zakynthinou establish a range of generalization bounds in terms of CMI. Our primary interest is in bounds for algorithms that have vanishing empirical risk. For [0, 1]-bounded loss, Steinke and Zakynthinou show that
ERD(An(Sn)) ≤ 2ER̂S(An(Sn)) + 3CMID(An)
n . (1)
For consistent learners (i.e., those that achieve zero empirical error a.s.), they also establish
ERD(An(Sn)) ≤ CMID(An) n log 2 . (2)
Steinke and Zakynthinou also introduce a variant of CMI based on the information revealed by the learner’s losses on Z, rather than by the output hypothesis, An(Sn), directly. Definition 2.2 (Evaluated CMI, [1, §6.2.2]). Let L ∈ {0, 1}2×n be the array with entries Li,j = `(An(Sn), Zi,j) for i ∈ {0, 1}, j ∈ [n]. The evaluated conditional mutual information of An with respect to D, denoted by eCMID(`(An)), is the conditional mutual information I(L;U |Z).
4By definition, PY [X] is a σ(Y )-measurable random element in M1(X ), i.e., PZ [U ] = κ(Z) a.s. for some measurable map κ : T → M1(X ). More generally, if, say F = σ(Y,Z) is the σ-algebra generated by Y and Z, then a conditional distribution/probability/expectation given F is a measurable function of Y and Z.
By the data processing inequality, eCMID(`(An)) ≤ CMID(An). Therefore, eCMID(`(An)) is also bounded above by n log 2. For consistent learners, Steinke and Zakynthinou show
ERD(An(Sn)) ≤ 1.5 eCMID(`(An))
n . (3)
For consistent learners An with bounded CMI or eCMI, these results imply their expected excess risk is of order O(1/n). The following result gives a nearly optimal bound for the generalization error for VC classes in term of the evaluated CMI. The proof (Appendix B) uses standard arguments, controlling the cardinality of the support of L using the Sauer–Shelah lemma. Theorem 2.3. For every n, let An : Zn → Hn, where Hn is a concept class with VC dimension dn. Then, for every n and distribution on Z, IZ(L;U) ≤ dn log 6n a.s. In particular, supD eCMID(`(An)) ∈ O(dn log n). Remark 2.4. Markov’s inequality and Eq. (2) imply P(RD(An(Sn)) ≥ ) ≤ CMID(An)/(log(2)n ) for consistent learners. By [21, Thm. 2.1], I(An(Sn);U |Z) ≤ I(An(Sn);Sn). This observation, combined with [12, Prop. 11], implies there is an input space, data distribution, and consistent learning algorithm for which this tail bound’s dependence on n is tight. If one were to obtain sample complexity bounds via such tail bounds, one would only prove that O(1/( δ)) samples suffice to find a hypothesis with estimation error with probability at least 1− δ. The linear dependence on 1/δ is, however, suboptimal. As such, it seems that the CMI framework cannot be used to obtain optimal sample complexity bounds in the PAC framework. Recent proposals for disintegrated notions of CMI in [22] might provide a framework for studying the sample complexity of PAC learning using an information-theoretic framework. /

heading: 3 Optimal CMI Bound for SVM and Stable Compression Schemes
text: In this section, we show that the CMI framework can be used to derive an optimal excess risk bound for the SVM algorithm learning half spaces in Rd. To show this, we establish optimal CMI bounds for the subclass of stable sample compression schemes, which imply this section’s main result: Theorem 3.1. Let An be the SVM algorithm for learning the class of half spaces in Rd. Then, for every n > d/2 and realizable distribution D in Rd, we have CMID(An) ≤ 2(d+ 1) log 2.
Combining this result with Eq. (2) gives ERD(An(Sn)) ≤ 2(d+1)/n. The lower bound for expected excess risk of linear classifiers in [29] shows this bound is optimal up to a constant factor.

heading: 3.1 CMI of Stable Compression Schemes
text: Littlestone and Warmuth [26] introduced compression schemes, which capture the idea that a consistent hypothesis can be defined in terms of a fixed number of samples. Formally, for a concept class H ⊆ YX , a sample compression scheme of size k ∈ N is a pair (κ, ρ) of maps such that, for all samples s = ((xi, yi))ni=1 of size n ≥ k, the map κ compresses the sample into a length-k subsequence κ(s) ⊆ s which the map ρ uses to reconstruct an empirical risk minimizer ĥ = ρ(κ(s)). Steinke and Zakynthinou prove the following upper bound on the CMI of a sample compression scheme. Theorem 3.2 ([1, Thm. 4.1]). Let H be a hypothesis class that has a sample compression scheme (κ, ρ) of size k. Then, CMID(An) ≤ k log(2n) where An(·) = ρ(κ(·)).
Note that the bound in Theorem 3.2 cannot be improved from O(k log n) to O(k) for every sample compression scheme, and so the bound in Theorem 3.2 is tight, and cannot be improved without further information about the compression scheme. The proof of the optimally stems from the fact that there exists compression schemes of size k and data distributions D such that there is a lower bound E[RD(An)] = Ω(k log(n)/n) where An(·) = ρ(κ(·)) [30, 31]. Combining this lower bound with Eq. (2) proves the optimally of Theorem 3.2.
Nevertheless, we can circumvent this lower bound by considering an important subclass of the sample compression schemes. Many natural compression schemes are also stable in the sense that removing any training example that was not in the compressed sequence does not alter the resulting classifier. To give a formal definition, we write s ⊆ s′ for two sequences s, s′ if, under some permutation, s is a subsequence of s′.
Definition 3.3 (Stable sample compression scheme; [2]). A sample compression scheme (κ, ρ) of size k is said to be stable if κ is symmetric (i.e., invariant to permutation of its input) and, for every realizable sample s of size n ≥ k, and every sequence s′ such that κ(s) ⊆ s′ ⊆ s, we have ρ(κ(s)) = ρ(κ(s′)). Due to the symmetry of κ, we refer to its output as the compression set, although the equivalence class of sequence under permutations is the structure of a multiset, not a set.
The concept of a stable compression scheme has its roots in the analysis of the SVM for learning half-spaces in Rd [32], which is the quintessential example of a stable sample compression scheme. For SVMs, the compression (multi)set contains at most d+ 1 distinct “support vectors” for any given training set. The reconstruction map outputs the max-margin classifier over the set of support vectors. By stability, removing any training example that is not a support vector does not change the resulting classifier [33, Sec. 5.3.2]. In the next theorem, we present a uniform CMI bound over realizable distributions for every stable sample compression scheme. Our bound removes the log n factor from Theorem 3.2 and is optimal up to a constant factor in the distribution-free setting. Theorem 3.4. LetH be a concept class with a stable compression scheme (κ, ρ) of size k. Then, for every realizable data distribution D and n ≥ k, CMID(An) ≤ 2k log 2, where An = ρ(κ(·)). Remark 3.5. Steinke and Zakynthinou [1, Sec. 4.4] propose an algorithm for learning threshold functions (positive rays) in the realizable setting over R that achieves CMID(An) ≤ 2 log 2. It is interesting to note that their algorithm can be viewed as a stable compression scheme. Specifically, for a realizable training set s, let x? = min{x ∈ R : (x, 1) ∈ s} if s has any sample with label 1, otherwise let x? = ∞. Then the algorithm proposed by Steinke and Zakynthinou is An(Sn) = ĥ, where ĥ(x) = 1[x ≥ x?]. Steinke and Zakynthinou present a bespoke analysis of this special algorithm. It is straightforward to see that the algorithm is a stable compression scheme of size one and the compression map here is symmetric. Therefore, the result of Theorem 3.4 gives CMID(An) ≤ 2 log 2. /
Proof of Theorem 3.4. Let W = An(ZU ) = ρ(κ(ZU )) and note that An is deterministic. We have H(U |Z) = n log 2 due to independence of U and Z and the independence of components of U . Then, by the definition of mutual information in terms of entropy, and Lemma 2.1,
CMID(An) = H(U |Z)−H(U |W,Z) ≤ n log 2− n∑ i=1 H(Ui|W,Z,U−i). (4)
Fix i ∈ [n], and define Ui→b , (U1, . . . , Ui−1, b, Ui+1, . . . , Un) for b ∈ {0, 1}. Using this notation, we can define two training sets Si→b = ZUi→b for b ∈ {0, 1}. Let Fi be the σ-algebra σ(W,Z,U−i) and let E be the event ρ(κ(Si→0)) = ρ(κ(Si→1)). Then, by the non-negativity of entropy,
H(Ui|W,Z,U−i) = E [ HFi(Ui) ] ≥ E [ HFi(Ui)1[E] ] . (5)
Note that, conditional on the sub-σ-algebra Gi = σ(Z,U−i),W takes on at most two values. However, on the event E (or equivalently, conditioning further on the event E, since E is Gi-measurable), W is now nonrandom because it takes on a single value. It follows that, conditional on Gi and the event E, W is trivially independent of every random variable, including Ui. Ergo, on E, EGi [Ui] = EFi [Ui] = PFi [Ui = 1]. But Ui is independent of Gi, and so EGi [Ui] = E[Ui] = 12 . Thus, on E, PFi [Ui = 1] = 12 and so H Fi(Ui) = Hb( 1 2 ) = log 2. Therefore,
H(Ui|W,Z,U−i) ≥ log 2 · P ( ρ(κ(Si→0)) = ρ(κ(Si→1)) ) . (6)
We can bound the probability of E from below using the stability property of the compression scheme. For any (x1, x̃1, x2, . . . , xn) ∈ Xn+1 and h ∈ H, consider two multisets S = {(x1, h(x1)), (x2, h(x2)), . . . , (xn, h(xn))} and S̃ = {(x̃1, h(x̃1)), (x2, h(x2)), . . . , (xn, h(xn))}, where S and S̃ differ only in the first element. Define the multiset S∪S̃ = { (x1, h(x1)), (x̃1, h(x̃1)),
(x2, h(x2)), . . . , (xn, h(xn)) }
. We claim that if (x1, h(x1)) and (x̃1, h(x̃1)) are not the members of the compression set S ∪ S̃, then (x1, h(x1)) and (x̃1, h(x̃1)) are not in the compression set of S and S̃, respectively. To prove this claim, since (x1, h(x1)) is not in the compression set S ∪ S̃ by the stability of κ, we have ρ(κ(S ∪ S̃)) = ρ(κ(S ∪ S̃ \ {(x1, h(x1))})). By the definition of S and S̃, S ∪ S̃ \ {(x1, h(x1))} = S̃. Thus, combining facts that (x1, h(x1)) is not in the compression set S ∪ S̃ and κ(S ∪ S̃) = κ(S ∪ S̃ \ {(x1, h(x1))}) = κ(S̃), we obtain (x̃1, h(x̃1)) is not in the
compression set S̃. Similarly, we can prove (x1, h(x1)) is not a member of the compression set S by switching x1 with x̃1 in the argument. By this argument,
P ( ρ(κ(Si→0)) = ρ(κ(Si→1)) ) ≥ P ( Z0,i 6∈ κ(Si→0 ∪ Si→1) ∧ Z1,i 6∈ κ(Si→0 ∪ Si→1) ) . (7)
Recall that the elements of Z are i.i.d., hence exchangeable. Since the size of the sample compression is k and κ is symmetric, we have
P ( Z0,i 6∈ κ(Si→0 ∪ Si→1) ∧ Z1,i 6∈ κ(Si→0 ∪ Si→1) ) ≥ ( n−1 k ) / ( n+1 k ) . (8)
Combining Eqs. (6) to (8) yields H(Ui|W,Z,U−i) ≥ log 2 · ( n−1 k ) / ( n+1 k ) ≥ (1 − 2k/n) log 2. Finally, the result follows by substitution of this bound into Eq. (4).
The result for SVMs (Theorem 3.1) follows immediately from Theorem 3.4 and the fact that the SVM may be expressed as a stable compression scheme of size d+ 1.

heading: 4 CMI of Proper Learning of VC classes
text: Following their paper introducing CMI, Steinke and Zakynthinou posed several open problems asking whether VC classes under realizibility admit learners with bounded CMI. We will restate their conjectures, and then showing that there exist some VC classes for which it is not possible to find a proper learner with bounded CMI under realiziblity. We then consider a subset of VC classes, namely VC classes with finite star number, and show that for such concept classes, there exists an ERM with bounded CMI.
We first state the main result of [1] on the CMI of proper learners. Theorem 4.1 (Thm. 4.12, [1] ). LetH be a concept class with VC dimension d. Then for all n ∈ N, there exists a proper ERM algorithm An for learningH such that for every realizable distribution D, CMID(An) = O ( d log n ) .
Remark 4.2 (Comparison of Theorem 4.1 and Theorem 2.3). First, note that Theorem 4.1 does not hold for every ERM algorithm. As discussed in [1], we can construct pathological ERMs with nearly maximal CMI by simply encoding the information U into the “lower-order” bits of W . It is also worth noting that our result in Theorem 2.3 is more general. There we show that a bound O ( d log n ) holds for evaluated CMI of any algorithm that outputs a hypothesis from VC class, whereas Theorem 4.1 holds for a specific proper algorithm. /

heading: 4.1 A Limitation of Proper Learning
text: Steinke and Zakynthinou [3] propose two conjectures regarding CMI for proper learning of VC classes under the realizability assumption, both of which can be seen as special cases of the following statement: Statement 1. There exists a real-valued function f and constant c ≥ 0 such that, for every nonnegative integer d and VC class H ⊆ X → Y of dimension d, there exists a proper learning algorithm A forH such that, for every n ≥ d, CMID(An) ≤ f(d) for all D and, for every realizable s ∈ Zn, ER̂s(An(s)) ≤ c d/n, where the expectation is taken only over the randomness in An.
Steinke and Zakynthinou [3] conjecture that Statement 1 holds for f linear. In this section, we show that Statement 1 is false in general: it is not possible to find a proper learning algorithm for every VC class that removes the log(n) factor from Theorem 4.1. For a class H ⊆ X → Y , let MHprop( , δ) denote the proper optimal sample complexity of ( , δ)-PAC learningH, i.e.,MHprop( , δ) is the least integer n, for which there exists a proper learning algorithm A such that, for every realizable distribution D, P(RD(An(Sn)) ≥ ) ≤ δ. The following result provides a lower-bound on the sample complexity of proper learning: Theorem 4.3 (Thm. 11, [2]). Let ∈ (0, 1/8) and δ ∈ (0, 1/100). There exists a concept class with VC dimension d. for which we haveMHprop( , δ) ≥ c̃ (dLog 1 + Log 1 δ ) for a fixed numerical constant c̃ > 0, where Log(x) = max{1, log(x)} for x ≥ 0.
We now present the main result: for VC classes, we show that the existence of a learning algorithm with bounded CMI contradicts the lower bound on the sample complexity in Theorem 4.3. The proof can be found in Appendix C.
Theorem 4.4. Statement 1 is false. Remark 4.5. Consider a modified Statement 1, seeking a proper learner with bounded eCMI instead. We can show that this modified statement is also false. /

heading: 4.2 VC Classes with Finite Star Number
text: Theorem 4.4 states that it is not possible to find a proper learning algorithm with bounded CMI for every VC class. Note that this limitation does not imply a failure of the CMI framework for characterizing the expected excess risk of learning VC classes. Instead, the impossibility can be attributed to an inherent limitation of proper learning algorithms, since there exist VC classes such that no proper learning algorithmAn satisfies E[RD(An)] = O(1/n) [2]. In this section, we consider a family of VC classes for which we can show the existence of a learner with bounded CMI. We begin with some definitions.
Two sequences ((x1, y1), . . . , (xn, yn)) and ((x′1, y ′ 1), . . . , (x ′ n, y ′ n)) are neighbours if xi = x ′ i for all i ∈ [n], and yi = y′i for all but exactly one i ∈ [n]. Fix any concept class H ⊆ YX . Star number of H [4, Def. 2], denoted by s, is the largest integer n such that there exists a realizable s ∈ (X × Y)n, and every neighbour of s is realizable byH. If no such largest integer n exists, then s =∞. Hanneke and Yang [4, Sec. 4.1] calculate the star number of some common concept classes. It is straightforward to see that d ≤ s. For any n ∈ N, and s = ((x1, y1), . . . , (xn, yn)) ∈ (X ×Y)n, define a version space of s with respect toH as VH[s] = {h ∈ H : R̂s(h) = 0}, a set of classifiers that are consistent with s.

heading: 4.2.1 Star Number, Version Space, and CMI
text: Fix any concept classH, and assume that, after observing a training sample Sn, we want to output the version space VH[Sn], i.e., the set of all classifiers consistent with Sn. We are interested in the following question: for which concept classes does the version space carry little information about the training samples conditioned on the supersample? More precisely, for which classes is I(VH[Sn];U |Z) = O(1)? Note that bounding the “CMI” of the version space provides a bound on the CMI of a broad class of algorithms that choose a particular ERM based solely on the version space, potentially under further constraints, such as privacy, fairness, etc.
In this section, we give a complete characterization of when I(VH[Sn];U |Z) = O(1), and show that it is possible if and only if H has finite star number. In particular, given a class with infinite star number, we demonstrate that I(VH[Sn];U |Z) = Ω(n). We begin with an upper bound, whose proof can be found in Appendix D. Theorem 4.6. Let n ∈ N,H be a concept class with star number s, andD be a realizable distribution. Let Z, U , and Sn be as defined in the beginning of this section. Then for every n ≥ s, we have I(VH[Sn];U |Z) ≤ 2s log 2.
We can use the data processing inequality and Theorem 4.6 to obtain the following: Corollary 4.7. LetH be a concept class with the star number s. Consider any ERM algorithm An for which the Markov chain Sn−VH[Sn]−An(Sn) holds; in other words, the output of the algorithm and the training set are conditionally independent given the version space. Then, for any such an algorithm, for every n ≥ s, and every realizable distribution D, we have CMID(An) ≤ 2s log 2.
In Corollary 4.7, by assuming the Markov structure Sn−VH[Sn]−An(Sn) we restrict the information of the ERM algorithm An(Sn). One might try to extend our result in Corollary 4.7 such that it holds for any ERM without any constraints. However, for the class of one-dimensional threshold over R, whose star number is two, one can construct an ERM with maximal CMI [1, Sec. 4.3]. Therefore, the Markov chain assumption cannot be removed. The next theorem shows s < ∞ is a necessary condition, for otherwise, there exist learning scenarios under which we cannot output the version space, even with merely sublinear CMI. Theorem 4.8. For every n ∈ N, n ≥ 2 and for every concept class H with star number s with s ≥ 2 over input space X , there exists a realizable data distribution D on X × Y such that I(VH[Sn];U |Z) = Ω(min{s, n}).
Proof sketch: Let X = [n] and consider the concept class H = {h0, h1, . . . , hn : X → Y}, where h0(x) = 0 is the zero function and ht(x) = 1[x = t], for t ∈ [n], are point functions. It is easy to
see that this concept class has star number n on X . Let D correspond to the uniform distribution on X and target function h0. Consider the bijection between H and {0, 1, . . . , n} ⊇ X . For every training sequence, the version space contains 0 and every point in X not observed in Sn = ZU . The key observation is that, in each column of Z, one point was not selected for training, and so each column contains zero or one points in the version space. Whenever there is one point, the value of Ui is revealed for that column. We show that the number of columns with this property is a lower bound on I(VH[Sn];U |Z). A coupon collector’s argument yields a lower bound the number of such columns. The formal proof can be found in Appendix E.

heading: 4.2.2 An ERM whose CMI is logarithmic in star number
text: In the next theorem, we show that there exists an ERM for learning VC classes with a finite star number for which the CMI is upper bounded by a constant and its dependence on star number is logarithmic. The proof is provided in Appendix F. Theorem 4.9. LetH be a concept class with VC dimension d and star number s. Then, there exists an ERM An for learning H such that for every n ≥ s and for every realizable distribution D, we have CMID(An) = O ( d log(s/d) ) .
Note that Theorem 4.9 shows the existence of a specific ERM with constant CMI, whereas in Corollary 4.7 we show a broad class of ERMs has bounded CMI.

heading: 5 Universality of eCMI and Improper Learning of VC Classes
text: The eCMI, introduced in Definition 2.2, is an appropriate information-theoretic notion for analyzing learning algorithms when there is no natural parameterization of the set of possible predictors, such as for improper or transductive algorithms. In this section, we show that eCMI is universal in the realizable setting. Then, we show that the CMI framework can be used to obtain a near-optimal bound on the expected excess risk of any algorithm with a leave-one-out error guarantee. As an application, we study CMI of the classical one-inclusion graph prediction algorithm, which was first proposed by Haussler et al. [5] as an optimal improper learner for VC classes. The next theorem is the main result of this section, whose proof can be found in Appendix G. Theorem 5.1. Let n ≥ 2 ∈ N, let An be a learning algorithm, and let D be a distribution on Z . Assume with probability one R̂Sn(An(Sn)) = 0. Then,
2/3RD(An) (a) ≤ eCMID(`(An))/n (b)
≤ Hb(RD(An)) +RD(An) log(2), (9) where Hb(·) is the binary entropy function, and RD(An) = E[RD(An(Sn))].
The inequality (a) in Eq. (9) implies that, if eCMID(`(An))/n vanishes as n diver2ges, thenRD(An) vanishes as well. The inequality (b) is more interesting: it implies that, if RD(An) vanishes as n diverges, then eCMID(`(An))/n also vanishes. Assume that a consistent algorithm A satisfies RD(An) = θ/n for θ ∈ R ≥ 1. Then, it is straightforward to see from Direction (b) in Eq. (9) that eCMID(`(An))/n = O(θ log(n)). Also, for an algorithm with RD(An) = θ log(n)/n the upper bound in Eq. (9) is given by O(θ(log(n))2). This observation suggests that our upper bound for eCMID(`(An))/n in Eq. (9) provides a bound on the expected excess risk which is sub-optimal by a log(n) factor in some interesting cases. Remark 5.2. Note that the result in Theorem 5.1 does not imply our results in former sections. In particular our results in Theorem 2.3, Theorem 3.4, Corollary 4.7, and (later in) Theorem 5.6 show that CMI framework provides optimal characterization of the expected excess risk in the considered scenarios. /
The following corollary summarizes our result for the consistent algorithms with a leave-one-out error guarantee. Corollary 5.3. Let n ∈ N and θ ∈ R+, such that n ≥ 2θ. Let An be a consistent learning algorithm. Let D be a distribution on Z and assume that, with probability one over a sequence S = (Z1, . . . , Zn+1) ∼ Dn+1, we have 1n+1 ∑n+1 i=1 ES [`(An(S−i), Zi)] ≤ θ n+1 , where the expectation is taken only over the randomness in An. Then, eCMID(`(An)) ≤ θ log((n+ 1)/θ) + 2θ log 2.

heading: 5.1 The One-Inclusion Graph Prediction Strategy
text: Haussler et al. [5] proposed an improper learning rule for learning VC classes based on the one-inclusion graph [34]. We provide a description of this algorithm in Appendix I. The deterministic version of this prediction rule satisfies the following property. Let H be a concept class with VC dimension d. For every n ∈ N, h ∈ H, and (x1, . . . , xn+1) ∈ Xn+1, let S = ((x1, h(x1)), . . . , (xn+1, h(xn+1))). Then 1n+1 ∑n+1 i=1 `(An(S−i), (xi, h(xi))) ≤ d n+1 . A direct application of Corollary 5.3 gives the following results. Corollary 5.4. Let An denote the deterministic one-inclusion graph for learning classH with VC dimension d. Then, for every realizable distribution D and n ≥ 2d, we have eCMID(`(An)) ≤ d log((n+ 1)/d) + 2d log 2. Remark 5.5. In Theorem 2.3 we provide a bound on eCMI of any proper ERM. However, for improper learners, we can construct a consistent algorithm with maximal eCMI. For instance, consider X = [0, 1], DX = Unif([0, 1]), the concept class of threshold with target function h?(x) = 1[x ≥ 1/2]. Consider a learning algorithm that gives the correct predictions on the points that are in the training set, and for a point that is not in the training set it always predicts one. One can show that eCMI of this consistent algorithm is Ω(n). /
Haussler et al. [5] showed that the one-inclusion graph algorithm achieves ERD(An(Sn)) ≤ d/n for learning a classH with VC dimension d. Corollary 5.4 implies that eCMID(`(An)) = O(d log(n)) for every deterministic one-inclusion graph prediction rule. Combining this result with Eq. (3) provides a bound on the excess risk which is suboptimal by a log n factor. In the next theorem, we show that, in at least one interesting special case, it is possible to remove the logarithmic factor from eCMI by exploiting a randomized one-inclusion graph prediction algorithm. Theorem 5.6. Let H denote the class of singletons (point functions) on X = R. There exists a randomized one-inclusion graph prediction ruleAn for learning classH such that for every realizable distribution D and n ≥ 2, we have eCMID(`(An)) = O(1).

heading: 6 Remaining Gaps and Open Questions
text: For proper learning of VC classes, Hanneke [35] showed the assumption s <∞ is a necessary and sufficient condition for the existence of a distribution-free bound on the expected risk of all ERMs converging at a rate O(1/n). In Corollary 4.7 and Theorem 4.9 , we showed the same rate for the expected risk of a broad class of ERMs can be obtained using the CMI framework. It is an open question to show that for a class with finite star number, every ERM has bounded eCMI.
An important open problem is to show that for every VC class with finite dual Helly number [2] there exists a proper learning algorithm such that for every data distribution its expected empirical risk converges at a rate of O(1/n) and it has bounded CMI. Combining the generalization guarantees that one can retrieve from Eq. (2) the expected excess risk of the learner with these properties matches the optimal rate from Bousquet et al. [2].
For improper learning of VC classes, we showed a general result for the deterministic one-inclusion graph prediction rule which is suboptimal by a log n factor. We conjecture that for every VC class with dimension d there exists a probability assignment for the randomized one-inclusion graph for which eCMI is O(d). In Theorem 5.6, we showed this claim holds for the class of point functions.
We also remark that if the answers to the above questions are affirmative, then it can be argued that the CMI framework is expressive enough so that it can explain generalization properties of VC classes. Otherwise, a negative answer to any of the questions implies that there is gap between CMI framework and VC theory.
In Theorem 5.1 we proved that eCMI is universal in the realizable setting. A fundamental question to ask is whether for every data distribution D and consistent learner A, eCMID(`(An))/n vanishes as the number training samples n diverges at the same rate with the excess risk, i.e., RD(An).

heading: Acknowledgments
text: The authors would like to thank Blair Bilodeau, Mufan Bill Li, and Jeffery Negrea for feedback on drafts of this work.
Funding
M. Haghifam is supported by the Vector Institute, University of Toronto, and a MITACS Accelerate Fellowship with Element AI. S. Moran is a Robert J. Shillman Fellow and is supported by the ISF, grant no. 1225/20, by an Azrieli Faculty Fellowship, and by BSF grant 2018385. D. M. Roy was supported, in part, by an NSERC Discovery Grant, Ontario Early Researcher Award, and a stipend provided by the Charles Simonyi Endowment. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute www.vectorinstitute.ai/partners.

Review summaries:
The paper discusses using the Conditional Mutual Information (CMI) framework to express bounds for generalization error. The authors discuss the use of CMI for several settings. In particular, they (i) show that their main result yields a tight bound for SVMs, (ii) answer a conjecture in the negative, and (iii) show that their result yields near-optimal bounds on algorithms with a "leave-one-out error guarantee".

The paper studies the ability of the recently proposed conditional mutual information framework (CMI) to characterize distribution-free generalization bounds of the expected excess risk for learning algorithms in the classification realizable setting of VC classes. They first show that CMI can be used to yield rates (sub-optimal in some cases) for any improper learning algorithm whose output hypotheses belong to a VC class. Next, they show that the CMI framework yields optimal bounds on the expected excess risk for stable sample compression schemes. An application shows that CMI yields optimal rates for the SVM algorithm. As for proper learning, it is shown that in some cases the CMIF cannot yield optimal rates by showing that the CMI cannot be bounded in terms of the VC-dimension alone. They also show that a finite star number (a recently introduced combinatorial property of VC classes) implies a finite CMI. Lastly, for non-VC classes, they show that any learning algorithm with a “leave-one-out” bound of order $O(1/n)$ yields an (empirical) CMI bound of order $O(log n)$. As an application, they obtain near-optimal bounds for the one-inclusion graph algorithm of Haussler et al. [5] for improper learning of VC classes and give an example where the rates are optimal. Open questions regarding the characterization are also discussed.

This work investigates the expressiveness of the CMI framework introduced in [1]. The main contributions of this paper are:  1. The authors show that an empirical variant of CMI can be easily used to express bounds every improper learning.  2. The authors apply their general CMI bound on SVM, and improve previous results by a logarithmic factor.  3. VC classes for which proper learning cannot be bounded by any function of the VC dimension are considered 4. They prove a general reduction showing that the leave-one-out is expressible via the CMI framework.