Towards a Unified Information-Theoretic Framework for Generalization
Authors: Mahdi Haghifam
Gintare Karolina Dziugaite
Shay Moran
Daniel M. Roy
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: information-theoretic generalization
conditional mutual information
leave-one-out
sample compression schemes
SVM

Abstract: In this work, we investigate the expressiveness of the "conditional mutual information" (CMI)  framework of Steinke and Zakynthinou (2020)  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 bounds for VC classes? (ii) Can the CMI framework be used to analyze algorithms whose output hypothesis space is unrestricted (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 Bousquet al. (2020) 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 (2020).  We further study the CMI of empirical risk minimizers (ERMs) of class $H$ 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 (Hanneke and Yang (2015)). 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. (1994). 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.

Towards a Unified Information-Theoreti Framework for Generalization
Mahdi Haghifam" University of Toronto,
Gintare Karolina Dziugaite Mila
Shay Moran Technion,
Vector Institute
Google Research
Daniel M. Roy University of Toronto, Vector Institute
Abstract
In this work, we investigate the expressiveness of the "conditional mutual informa- tion" (CMI) framework of Steinke and Zakynthinou [1] and the prospect of using it to provide a unified framework for proving generalization bounds the realizable setting. We first demonstrate that one (but sub-optimal) bounds for any learning algorithm that outputs hypotheses from class of bounded VC dimension. We then explore two directions of strengthening this bound: (i) Can the CMI framework express optimal bounds for VC classes? (ii) Can the CMI framework be used analyze algorithms whose output hypothesis space is unrestricted (i.e. has an unbounded VC dimension)?
this framework to express non-trivial
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 have uniformly bounded CMI of order Okk).
We further show that an inherent limitation of proper learning of VC classes contradicts the existence of proper learner with constant CMI, and it implies a negative resolution to open problem of Steinke and Zakynthinou [3]. We further study the CMI of empirical risk minimizers (ERMs) of class H. and show that it is possible to output all consistent classifiers (version space) with bounded CMI if and only if has 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 corollary investigate the CMI of the one-inclusion-gran generally, 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.
algorithm proposed by Haussler et al. [5]. More
Introduction
In this work, we study the expressiveness generalization bounds terms of information-theome measures of dependence between the output of a learning algorithm and input data. Information- theoretic techniques for proving generalization bounds are powerful; they can provide generalization
Part the work was done author was an intern at Element AI, ServiceNow company. This work was carried out while the author was ServiceNow. It was finalized at Google Brain.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

bounds that are algorithm-dependee data-dependent, and distribution-dependenn 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)n21 that selects an element h in H. based on n i.i.d. samples Sn ~ Den i.e., h = hn = (Sn). The initial focus of this line of work was the mutual information I (SA);
between the input and the output of a learning problem. This quantity is sometimes referred to as the input-oulpul mutual information (IOMI) of an algorithm and denoted by IOMI (An). A natural question is whether the IOMI framework can provide a sharp characterization of the learnability of "apnik-Cherrooenniss (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. 2 2d., there exists a finite input space X and concept class H S 13 of VC-dimession d such that, for all proper and consistent learning algorithm An, there exists a realizable distribution 'D such that (OM) = (og log(1 (od))))
Livni and Moran [18] extended this result even further, showing that, for the class of one-dimensional thresholds over {1..... m. m E N for every learning algorithm A there exists realizable distribution such that either the risk (population loss) is large or the IOMI (AA)) 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 IOMI 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]. 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 accurately estimate the general- ization 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 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 dl 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 '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 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 (d). Moreover, Steinke and Zakynthinou connected CMI framework to the sample compression framework of [26] by showing that a sample compression An, of size i has CMI,(A,) < l log 2n. Their bound for sample compression schemes is also suboptimal in some cases by a log n factor.
1.1 Contributions
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.
"This concept class can be defined as follows. Let X = (1, m). Let & E N and hu : x {0, 1) define has (x) = 1 > k). Then, the class of one-dimensiona thresholds over (1,..,m) m) is Hm (he lk E N).
-
2

---

1. We demonstrate that one can use the CMI framework to express non-trivial (but sub-optimal) bounds for every improper learning algorithm that oulputs 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-valuee function of the VC dimension. Then, consider VC classes with finite star number [4], and prove the existence 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 vamishes if and only if the excess risk also vanishes as the number training samples diverges. We then show that any learning algorithm with a "lcave-onc-out" bound of order ((1/n) yields an evaluated-CMM bound of order (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- me-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-dependee setting [21, 25J. These developments in a range of different problem settings highlight the importance of understanding the expressiveness of the CMI framework.
2 Preliminaries
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 C yd is set of functions h: X' V. We say H shatters (Ii,..., 3m) E x if for all (yI,..., Vm) E {0, 1 1)m there exists h E H. such that, for all i [m]. we have h(:;;) yt- The VC dimension of H. denoted by d, is the largest E N for which there exists (Zi,..., 3 E x shattered by H. If no such finite m exists, then d = cc. oc.
Let D be distribution on Z X x V. The empirical (classification) risk of a classifier h X + y on sample s (( 31 ) ... (In, Un)) 2" is (h) n-! Eiein E(h, (2t, y:)), where ((,, (xr, v)) 1 (xxx) * v). Let S, D", i.e., let S, be a sequence of i.i.d. random elements in 2 with common distribution D. (We can view Sn itself as a random element in 2".) The risk of h is (h) = ERs,, (h), where E denotes the expectation operator. (The risk has, of course, no dependence on due to the data being i.i.d.)
A distribution D is realizable by a class H C yd if there exists h E H such that RD = 0. A sequence (x1,,)),, -.)),-... (Ias )n is said be realizable by H. if for some h E H. h(r,) = yi for all i E [m] = (1....,m.. n... Note that if a distribution is realizable by H, it implies that with probability one over Sn ~ D", the training sample S,, is realizable by H.
Let = (An)n21 denote a (potentially randomized) learning algorithm, which, for any positive integer n, maps S,, to an element of X + V. We say that A is a proper learner for class H X + y' if the codomain of A,, is a subset of H. for every n. We say An is a consistent algorithm (learner) if R.s., (S.)) = 0 a.s. Our primary interest in this paper is the expected generalization error of An with respect to D, defined as EGED((,, (AA,) = (An, - Rs., (S,)), where we average over both the choice of training sample and the randomness within the algorithm An.
2.1 Conditional mutual information (CMI) of an algorithm
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
3

---

"supersample" Z, a training sample S, taken from the supersample, and the hypothesis (S,,) output by a possibly randomized learning algorithm, given S, as input. Formally, let Z (Z,,) (0.1). (0.1)) jejv]
to be an array of i.i.d. random elements in the space 2 of labeled examples, with a common distribution D. In order to choose a training sample S,, of size n from Z, let U = (U,, U2..... Un) be sequence of i...d. Bernoulli random variables in {0. 1), independent from Z, with P(U, = 0) = 1/2. Define S, = Zu = (Zv,,s) The conditional mutuall information (CMI) of An. denoted (M defined to be the mutual information between A,, and U given Z, denoted [(A,, This quantity is equivalent to I [AA,, (S,): S, Z) when DD is atomless, since (U1,.... Un) is a.s. measurable with respect to S, and Z. Because Z and are independent, CMIp(A,) I H(U = H(U) = n log 2. We now pause to introduce this and other anfformatiinntheorettt quantities formally.
().
2.2 Measures of divergence and information
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 Pi]]= - fdP. When Q is absolutely continuous with respect to P. denoted Q < P. write dQ JP for (an arbitrary version of) the Radon- Nikodym derivative (or density) of Q with respect P. The KL divergence (or relative entropy) of Q with respect to P. denoted (L(Q || P). is defined as Q[log aP] when Q P and infinity otherwise.
For random element X in some measurable space X. let P[X] denote its distribution, which lives in the space M₁ (2') of all probability measures on X. Given another random element, say Y in T, let PY [X] denote the conditional distribution of X given Y. If X and Y are independent, TP [X] = P[X] a.s. For an event, say X E A, [X E A] denotes the event's 's conditional probability given Y. which is defined to be the conditional expectation of the indicator random variable [[X E A] given Y, denoted EY 1[X E AJ.' By the chain (aka tower) rule, EE = E for any o-algebra F.
The mutual information between X and Y is I(X;Y) [L(P[(X, |[ @ P(Y1), where & forms the product measure. Writing P² 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
(x:)) KL(Pp [x, Y)] 12 [X] @ (Y]).
Then the conditional mutual information of X and Y given Z is T(X, YIZ) = 1
Let Je- = [[[]] and let k(Y)= = - [X] a.s. If X concentrates on countable set V with counting measure v, the (Shannon) entropy of X is H(X) = -m(log du
du = Evev P(X = x) log PPX = r). The disintegrated entropy of X given Y is defined by H (X) = - x(Y) dx(Y),, while the du
conditional entropy of X given Y is H(X = EE (X)). Note that H(XIV) S H()). We will make use of the following lemma whose proof can be found in [28].
Lemma 2.1. Let (X1,X, X2,... X,) be discrete random vector, and Y be an arbitrary random variable. Then, H(X1,...,, x,
Y) 2 Σn H(X.|X_;,, Y), where X_; (X, j [m],] # 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, -ounddd loss, Steinke and Zakynthinou show that
ERD(A, S (A,) + 3CMI
n
For consistent learners (i.e., those that achieve zero empirical error a.s.). they also establish
CMI,(An)
(A,((A, <
n log
Steinke and Zakynthinou also introduce a variant of CMI based on the information revealed by the learner's 's losses Z, rather than by the output hypothesis, An (Sa), directly.
Definition 2.2 (Evaluated CMI, [1, $6.2.21. Let L E {0, 1 be the array with entries Li, = ((,,(S)), Zz for i E (0,1). E [m]. The evaluated conditional mutual information of A,, with respect to D. denoted by (C(.)) is the conditional mutual information 1 [(L;U[Z).
"By definition, PP [X] is a (Y measurable random element in (2)), i.e., 1²] x(2) a.s. for some measurable map x T (X)). More generally, if, say F = oYY, 2) is the o-algebra generated by Y and Z, then conditional distribtioorypobbbilllyyaaaatttd given F is measurable function of Y and Z.

---

By the data processing inequality, eCMlp(e(A.)) I (A,). Therefore, cCMIp(((An)) is also bounded above by log2. 2. For consistent learners, Steinke and Zakynthinou show
ERD(A. - 1.5 (CML)(((AA))
(3)
n
For consistent learners A. with bounded CMI or eCMI, these results imply their expected excess risk is of order (1/nn). The following result gives 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 2" + Hn. where Hn is concept class with VC dimen- sion d, Then, for every n and distribution on Z, 1 (L;U) S supp (CMID(((A.)
d,, log 6n a.s. particular.
E (dd, log log
Remark 2.4. Markov's 's inequality and Eq. (2) 20 SCML) for consistent learners. By [21, Thm. 2.11. (S,); s (SA..))): This observation, combined with [12, Prop. 1 11], implies there is an input space, data distribution, and consistent learning algorithm for which this tail bound's dependence on is light. If one were obtain sample complexity bounds via such tail bounds, one would only prove that ((1/(c))) samples suffice to find a hypothesis with estimation error with probability at least 8. 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 framework for studying the sample complexity of PAC learning using an information-thee -hterorttcccc framework.
3 Optimal CMI Bound for SVM and Stable Compression Schemes
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 Rdd To show this, we establish optimal CMI bounds for the subclass of stable sample compression schemes, which imply this section's 's main result:
Theorem 3.1. Let An be the SVM algorithm for learning the class of half spaces in Rdd Then, for every n > 2/2 and realizable distribution D in Rd, we have CMIp(An) S 2(d + 1) log
Combining this result with Eq. (2) gives ERp (A,, (A.. (S,)) < 2(d+1)/n. The lower bound for expected excess risk of linear classifiers in [29] shows this bound is optimal up to constant factor.
3.1 CMI of Stable Compression Schemes
Littlestone and Warmuth [26] introduced compression schemes, which capture the idea that a consistent hypothesis can be defined in terms of fixed number of samples. Formally, for a concept class H C y a sample compression scheme of size E N is a pair (x. of maps such that, for all samples subsequence <(s) C s which the map p uses to reconstruct empirical risk minimizer h = p()( Steinke and Zakynthinou prove the following upper bound on the CMI of a sample compression scheme.
((z4,):))
):) of size 2 k. the map x compresses the sample into length-k
Theorem 3.2 ([1, Thm. 4.1J). Let H be hypothesis class that has sample compression scheme (K, p) size Then, CMIp (An) & k log(2n) where An(-)) = p(x(-)).
Note that the bound in Theorem 3.2 cannot be improved from O(k log to O(k) for every sample compression scheme, and so the bound in Thcorem 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 & and data distributions D such that there is lower bound (ERR((A))
Q(k log(n)/n) where (.) p(x(:)) [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 C s' for two sequences 8, s' if, under some permutation, is subsequence of s'.
5

---

Definition 3.3 (Stable sample compression scheme; [2]). A sample compression scheme (H. p) of size is said be stable if k. is symmetric (i.e., invariant to permutation of its input) and, for every realizable sample of size 2 k. and every sequence s' such that k(s) C s' S we have p(x{(s) = ((x(s')). Due to the symmetry of Ks, 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 I [32], which is the quintessential example of stable sample compression scheme. For SVMs, the compression (multi)set contains at most d 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 not a support vector does not change the resulting classifier [33, Sec. 5.3.2]. In the next theorem, present 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 constant factor in the distribution frre setting.
Theorem 3.4. Let H. be a concept class with stable compression scheme (K. p) of size k. Then, for every realizable data distribution 'D and ni 2 k, CMIp(A..) S 2k log 2, where An = -(xx()).
Remark 3.5. Steinke and Zakynthinou [1, Sec. 4.4] propose algorithm for learning threshold functions (positive rays) in the realizable setting over IR that achieves CMI < 2 log 2. It is interesting to note that their algorithm can be viewed as stable compression scheme. Specifically, for a realizable training set 8, let x² = min 1 E R : (I, 1) E 8} if 8 has any sample with label 1, otherwise let x² = co. Then the algorithm proposed by Steinke and Zakynthinou is (S,) = h, where h(x) 1 [sr x*). Steinke and Zakynthinou present 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(A.) S 2 2.
and note that An is deterministic. We have H(U]Z)= 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,
Proof of Theorem 3.4. Let W- = (z))
(MI)(AA) = H(U - H(U Z) S n log 2- Σ HUU-),
(4)
Fix i E [n]. and define U.-- A (U,, (U1,.... U,- l....... Un) for b E 10, Using this notation, we can define two training sets Si-sb = Zu, 10 for be (0. 1). Let Fi be the o-algebra a (W, Z, U-) and let E. be the event (()(S:)))) = ((x(Si-)))) Then, by the non-negativity of entropy,
H(U, E F. 2 (H
(5)
Note that, conditional on the sub-o- Gi = UZ, W takes on at most two values. However, on the event E' (or equivalently, conditioning further on the event E, since E is (--meauurable), W is now nonrandom because takes on a single value. It follows that, conditional on Gi and the event E. W is trivially independent of every random variable, including Uj. Ergo, on E, EC. [U.] [U.] = F.F. [U, 1]. But U, is independent of 9,, and so E [U,] E[U.] 2- Thus, on F, F. IU, = 1] 1/2 and so F (U,) = ()) = log2. Therefore,
H(U, 2, U.) > log 2 2 (()( = p(K(S:-1))).
(6)
We can bound the probability of E from below using the stability property of the compres- sion scheme. For any $1,, .2. vn) E 1n+1 and h E H. consider two multisets S {1x1, (z1)). (22, (a22)),... ... (zn, h(x))) and S ((ē,, I(ā))), (I2, h(x2)), (In, h(xx))))) })]. where S and S differ only in the first element. Detine the multiset SUŠ {(11, h(x1)), (# h(ā,)) (x2, (x22), .... (wn, h(..))). We claim that if (Ii, M(x1)) and (ā1, h(ā))) are not the members of the compression set S SUS. S, then (æ1, Mxx1) and (0a, h(r1)) )) are not in the compression set of S and Š, respectively. To prove this claim, since (a), I((x)) is not in the compression set S U $ by the stability of K, we have p(k(S U 5)) = p(x(S US Š \ {(x), h(z1))))) By the definition of S and S, S.S. 5 {(21, h(x1))) = S. Thus, combining facts that (x1, h((1)) )) is not in the compression x(S), we obtain (Ā1, h(āz)) is not in the
set S US S and KSSU 8) x(S US

---

compression set S. Similarly, we can prove (æ1, ((x1)) is not member of the compression set S by
switching 21 with ž in the argument. By this argument,
P(p(<(S.-n)) - p()(SS-.1)) 2 Zo : & x(S,_o U A Zi, (( U ).
(7)
Recall that the elements of Z are i.i.d., hence exchangeable. Since the size of the sample compression and & is symmetric, we have
P(Zo,: E (S U S A Zr, & 105 2 (*x)) ((*))
(8)
Combining Eqs. (6) (8) yields [W, Z, U-+) 2 log 2 Finally, the result follows by substitution of this bound into Eq. (4).
2 (1- 2k/2// /n) log
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 1.
4
CMI of Proper Learning of VC classes
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 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 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]). Let H be concept class with VC dimension d. Then for all n E N, there exists proper ERM algorithm An for learning H such that for every realizable distribution 'D CMT (An.) = Od n)..
Remark 4.2 (Comparison of Theorem 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 bound (dlog n) holds for evaluated CMI of any algorithm that outputs hypothesis from VC class, whereas Theorem 4.1 holds for a specific proper algorithm.
4.1 A Limitation of Proper Learning
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 2 O such that, for every nonnega- tive integer d and VC class H C X + y of dimension d, there exists a proper learning algorithm forr H such that, for every 2 d, CMIp(An) S (dd) for all 'D and, for every realizable E 2", ER, (S)) ed/n, where the expectation is taken only over the randomness in An
Steinke and Zakynthinou [3] conjecture that Statement 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 class H C X - y, let M (c, d) denote the proper optimal sample complexity of (c, 8PC learning H. i.e., M (ooop 5) the least integer n, for which there exists a proper learning algorithm A such that, every realizable distribution D, P(R (S,)) 2 <) < 6. The following result provides a lower-bound on the sample complexity of proper learning:
Theorem 4.3 (Thm. 11, [2]). Lerc (0, 1/8) and 8 E 10,0/100). There exists concept class with VC dimension d. for which we have M prop (e, 8) 2 Ld + Log 1 for a fixed numerical constant
ē > 0, where Log(z)= = max(1, log(z) for o 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.
7

---

Theorem 4.4. Statement is false.
Remark 4.5. Consider modified Statement 1, seeking proper learner with bounded eCMI instead. We can show that this modified statement is also false.
4.2 VC Classes with Finite Star Number
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 algorithm An, satisfies (A..)).)) = O /n) [2]. In this section, we consider a family of VC classes for which we can show the existence of learner with bounded CMI. We begin with some definitions.
Two sequences ((x1, m/),...,, Mn)) and ((11,11),. Vi)..... (1r v/w)) are neighbours if 24 x² for all [na]. and Y/ v/ for all but exactly one [m]. Fix any concept class H. C y Star number of H [4, Def. 2), denoted by s, is the largest integer n such that there exists a realizable E (X' x 37y", and every neighbour of is realizable by H. If no such largest integer exists, then 5 = co. Hanneke and Yang [4, Sec. 4.1] calculate the star number of some common concept classes. It is straightforward
see that d S s. For any n E N. and ((z1, v1), ....... (I': Vn)) E (X x 3")",
define a version space of with respect to H as Vx(s] = (h E H: R.(h) 0}, a set of classifiers that are consistent with 8.
4.2.1 Star Number, Version Space, and CMI
Fix any concept class H. and assume that, after observing training sample S,,, we want to output the version space [H([,,). i.e., the set of all classifiers consistent with S., 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 [V [V*[S,]; UIZ) (()) 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(V [VN[SA] = 0(1), and show that it is possible if and only if H has finite star number. In particular, given class with infinite star number, we demonstrate that [(V (V=(S.,; UIZ) = 2(n). We begin with an upper bound, whose proof can be found in Appendix D.
Theorem 4.6. Let n E N, be a concept class with star number s, and be a realizable distribution. Let Z, U, and S, be defined in the beginning of this section. Then for every 2 have [[V*[S,):U1Z S 2s log
We can use the data processing inequality and Theorem 4.6 to obtain the following:
Corollary 4.7. Let H be concept class with the star number s. Consider any ERM algorithm An for which the Markov chain S, 55-Va, (n,))) holds; in other words, the output of the algorithm and the training set are conditionally independent given the version space. Then, for any such algorithm, for every n 2 s, and every realizable distribution D, we have CMl)(A,) S 2s log 2.
In Corollary 4.7, by assuming the Markov structure S, - [x[[S,]-An (S,.) we restrict the information of the ERM algorithm An (S.). 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 oie-dimensional threshold over R, whose star number is two, one construct an ERM with maximal CMI [1, Sec. 4.3]. Therefore, the Markov chain assumption cannot be removed. The next theorem shows s < oc 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 TL N, n 2 and for every concept class H with star number s with $ > over input space X, there exists a realizable data distribution D on x y such that I(V I[Vn[S.]: UlZ) (minn(s,))
Proof sketch: Let X [n] and consider the concept class H (ho, bi,..., hn X - >}}, where ho(x) 0 is the zero function and he(x) 1/x t). for torte E [mn] are point functions. It is casy to
8

---

see that this concept class has star number n on X. Let D correspond to the uniform distribution on X' and target function hgg Consider the bijection between H. and [0.1,....,7) 2 X. For every training sequence, the version space contains O and every point in X' not observed in S, = 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 U, is revealed for that column. We show that the number of columns with this property is lower bound on I(VH|S U columns. The formal proof can be found in Appendix E.
Z) A coupon collector's argument yields a lower bound the number of such
4.2.2 An ERM whose CMI is logarithmic in star number
In the next theorem, we show that there exists an ERM for learning VC classes with 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. Let H. 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 and for every realizable distribution D, we have CMIp(A,, = Oddlog(s/d)) (og(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.
5 Universality of eCMI and Improper Learning of VC Classes
The eCMI, introduced in Definition 2.2, is an appropriate informatiionthhoreee notion for analyzing learning algorithms when there 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-ous 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 Appendix G.
Theorem 5.1. Let 2 2 E N. let An be learning algorithm, and let 'D be distribution on Z. Assume with probability one Rss,, (Sn(S.)) = 0. Then,
(b) S Ha + (D( where Ho(-) is the binary entropy function, and Ro(AA)) = (RR
2/3RD(An) - (a)
The inequality (a) in Eq. (9) implies that, if (feCMII(((A.))) /n vanishes as n diver2ges, then (AA,)) vanishes as well. The inequality (b) is more interesting: implies that, if (A,) vanishes as diverges, then (CMI)(((A,,.))
also vanishes.
Assume that consistent algorithm A satisfies (D(AA) 0/n for 0 R 1. Then, it is straightforward to see from Direction (b) in Eq. (9) that (CMIp(e(AA))/) for algorithm with (A,,), 0 log(n)/n the upper bound in Eq. (9) is given by (((l))())) This observation suggests that our upper bound for (((A)) 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.
((llgg()), Also,
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 E and 0 E I.,,, such that n 2 20. Let An be a consistent learning algorithu. Let D be distribution on Z and assume that, with probability one over sequence S (Zz,..., Zn+1)
D=+1, have -1 E.=! E ((((A,(S-))) Zi)l 9 n+1
nt1 where the
expectation is taken only over the randomness in An- Then,
eCMl)(((A.)) S loog(n + 1)/0) + 20 log

---

5.1 The One-Inclusion Graph Prediction Strategy
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 de- terministic version of this prediction rule satisfies the following property. Let H. be a concept class with VC dimension d. For every E N, h E H. and (t,...,,xn+1)) E x let S ((x1, h(z1)),...,, (Fn+,, ((xn+1))). Then n+1 ΣE= ((An(())) (zi, I a+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 class H with VC
dimension d. Then, for every realizable distribution DD and n 2 2d, we have eCMlo(((A.)) S d llog((nn + 1)/d)= + 2d log 2.
Remark 5.5. In Theorem 2.3 we provide bound on eCMI of any proper ERM. However, for improper
learners, we can construct a consistent algorithm with maximal eCMI. For instance, consider = [0, 11, Dx- = (n, IJ), the concept class of threshold with target function h (=)) = 1|x 2 1/2]. Consider learning algorithm that gives the correct predictions on the points that are the training set, and for point that is not in the training set it always predicts one. One can show that eCMI of this consistent algorithm is ((n).
Haussler al. [5] showed that the one-inclusion graph algorithm achieves ERD (S,, S d/n for learning class H with VC dimension d. Corollary 5.4 implies that cC cCMIp(e(An) = (og)o)()) for every deterministic one- one-inclusion graph prediction rule. Combining this result with Eq. (3) provides a bound on the excess risk which is suboptimal by log factor. In the next theorem, we show that, at least one interesting special case, is possible to remove the logarithmic factor from eCMI by exploiting randomized one-inclusion graph prediction algorithm.
Theorem 5.6. Let H denote the class of singletons (point functions) on X' R. There exists randomized one-inclusion graph prediction rule for learning class H such that for every realizable distribution and n 2 2, we have eCMI (E(D(E(AA)) = 0(1).
6 Remaining Gaps and Open Questions
For proper learning of VC classes, Hanneke [35] showed the assumption a < 00 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(1nn). In Corollary 4.7 and Theorem 4.9, we showed the same rate for the expected risk of 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 proper learning algorithm such that for every data distribution its expected empirical risk converges at rate of ((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 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 (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 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, (((A.) vanishes as the number training samples n diverges at the same rate with the excess risk, i.e., RD (An).
Acknowledgments
The authors would like to thank Blair Bilodeau, Mufan Bill Li, and Jeffery Negrea for feedback on drafts of this work.
10

---

Funding
M. Haghifam supported by the Vector Institute, University of Toronto, and MITACS Accelerate Fellowship with Element AI. S. Moran is 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 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. wwctorinst titetttteeaiiei.....a ai ai/partners......
References
[1] T. Steinke and L. Zakynthinou. "Reasoning About Generalization via Conditional Mutual Information". ", In: Proceedings of 33rd Conference On Learning Theory, Ed. by Abernethy and S. Agarwal. Vol. 125. Proceedings of Machine Learning Research. PMLR, July 2020,
pp. 3437-3452 arXiv: 2001.09122. 09122.
[2] O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy. "Proper Learning, Helly Number, and an Optimal SVM Bound". In: Proceedingy of the 33rd Conference On Learning Theory. Ed. by J. Abernethy and S. Agarwal. Vol. 125. Proceedings of Machine Learning Research. PMLR, July 2020. pp. 582-609.
[3] T. Steinke and L. Zakynthinou. "Open Problem: Information Complexity of VC Learning". In: Proceedings of the 33rd Conference On Learning Theory. Ed. by J. Abernethy and S. Agarwal.
Vol. 125. Proceedings of Machine Learning Research. PMLR, July 2020, pp. 3857-3863,
[4] S. Hanneke and L.. Yang. "Minimax analysis of active learning." J. Mach. Learn. Res. 16.12 (2015), pp. 3487-3602.
[5] D. Haussler, N. Littlestone, and M. K. Warmuth. "Predicting {0, f)-functions randomly drawn points". Information and Computation 115.2 (1994), pp. 248-29222
[6] D. Russo and J. Zou. How much does your data exploration overfit? Controlling bias via information usage. 2015. arXiv: 1511 ..2299.
[7] D. Russo and J. Zou. "Controlling Bias in Adaptive Data Analysis Using Information Theory". In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Ed. by A. Gretton and C. C. Robert. Vol. 51. Proceedings Machine Learning Research. Cadiz, Spain: PMLR, 2016, pp. 1232-1240.
[8] A. Xu and M. Raginsky. "Information-theone
analysis of generalization capability of learning algorithmss". In: Advances Neurul Information Processing Systems. 2017, pp. 2524-2533,
[9] M. Raginsky, A. Rakhlin, M. Tsao, Y. Wu, and A. Xu. stability and bias of learning algorithms". In: 2016 IEEE Information Theory Workshop (ITW). IEEE. 2016, pp. 26-30.
analysis of
[10] A. Asadi, E. Abbe, and S. Verdú, "Chaining mutual information and tightening generalization bounds". In: Advances in Neural Information Processing Systems 32, 2018.
[11] A. Pensia, V. Jog, and P.-L. Loh. "Generalization error bounds for noisy, iterative algorithms".
In: 2018 IEEE International Symposium on Information Theory (ISIT). 2018, pp. 546-550.
[12] R. Bassily, S. Moran. I. Nachum, J. Shafer, and A. Ychudayoff. "Learners that Use Little Information". In: Algorithmic Learning Theory. 2018, pp. 25-55.
[13] I. Nachum, J. Shafer, and A. Yehudayoff. "A direct sum result for the information complexity of learning". In: Conference On Learning Theory. PMLR. 2018, pp. 1547-1568.
[14] I. Nachum and A. Ychudayoff. "Average-case information complexity of learning". In: Algo-
rithmic Learning Theory. PMLR. 2019, pp. 633-646.
[15] I. Issa, A. R. Esposito, and M. Gastpar. "Strengthened information-theonee Bounds on the Generalization Error". In: 2019 IEEE International Symposium on Information Theory (ISIT). 2019, pp. 582-586.
[16] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. "Information- Theorrtic Generalization Bounds for SGLD via Data-Dependent Estimates", In: Advances in Neural Information Processing Systems. 2019, pp. 1013-11023.
[17] Y. Bu, S. Zou, and V. V. Veeravalli. "Tightening Mutual Information- Bounds on Gener- alization Error". IEFE Journal on Selected Areas Information Theory (2020), pp. 121- 130.
11

---

[18] R. Livni and S. Moran. "A Limitation of the PAC-Bayes Framework". In: Advances in Neural Information Processing Systems. Vol. 33. 2020, pp. 20543-20557
[19] G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. "Information-Theorree Bounds for Stochastic Gradient Descent". In: Proceedings of Thirty Fourth Conference on Learning Theory. Ed. by M. Belkin and S. Kpotufe. Vol. 134. Proceedings of Machine Learning Research, PMLR, 15-19 Aug 2021, pp. 5526-3545.
Generalization
[20] H. Hafez-Kolahi, Z. Golgooni. S. Kasaei, and M. Soleymani. "Conditioning and Processing: Techniques to Improve Information- Cnoommation-Thoorttee
Theoretic Generalization Bounds". In: Advances in Neural
Information Processing Systems 34. 2020.
[21] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. "Sharpened Generalization Bounds based Conditional Mutual Information and an Application to Noisy, Iterative Algorithms". In: Advances in Neural Information Processing Systems. 2020, pp. 9925-9935,
[22] F. Hellström and G. Durisi. "Generalization Bounds via Information Density and Conditional Information Density". IEEE Journal on Selected Areas in Information Theory 1.3 (2020), pp. 824-839.
[23] B. Gadve, G. Bassi, R. Thobaben, and M. Skoglund. "On Random Subset General- ization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm". In: IEEE Information Theory Workshop (ITW). IEEE. 2020.
[24] R. Zhou, C. Tian, and T. Liu. "Individually Conditional Individual Mutual Information Bound on Generalization Error". In: 202/ IEEÉ International Symposium on Information Theory (ISIT). 2021, pp. 670-675.
[25] F. Hellström and G. Durisi. "Fast-Rate Loss Bounds via Conditional Information Measures with Applications to Neural Networks". In: 202/ IEEE International Symposium on Information Theory (ISTT). 2021, pp. 952-957.
[26] N. Littlestone and M. Warmuth. "Relating data compression and learnability" (1986).
[27]
S. Hanneke and A. Kontorovich. "Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound", In: Algorithmic Learning Theory. PMLR. 2021, pp. 697-
721.
[28] M. Madiman and P. Tetali. "Sandwich bounds for joint entropy". In: 2007 IEEE International Symposium on Information Theory. IEEE. 2007, pp. 511-515.
[29] P. M. Long and R. Long. "On the complexity of proper distribution-fred learning of linear classifiers" In: Algorithmic Learning Theory. PMLR. 2020, pp. 583-591.
[30] S. Hanneke and A. Kontorovich. "A sharp lower bound for agnostic learning with sample compression schemes". In: Algorithmic Learning Theory. PMLR. 2019, pp. 489-505. [31] S. Floyd and M. Warmuth. "Sample compression, learnability, and the Vapnik-Chervonenkis dimension".. Machine learning 21.3 (1995), pp. 269-304.
[32] V. Vapnik and A. Chervonenkis. Theory of pattern recognition. 1974.
[33] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
[34] N. Alon, D. Haussler, and E. Welzl. "Partitioning and geometric embedding of range spaces of finite Hapnik-Chervonenll dimension". In: Proceedings of the third annual symposium Computational geomerry. 1987, pp. 331-340.
[35] S. Hanneke. "Refined eтror bounds for several learning algorithms". . The Journal of Machine Learning Research 17.1 (2016), pp. 4667-4721.
[36] S. Hanneke. "The optimal sample complexity of PAC learning". The Journal of Machine Learning Research 17.1 (2016), pp. 1319-1333.
[37] S. Moran and A. Yehudayoff. "Sample compression schemes for VC classes". Journal of the ACM (JACM) 63.3 (2016), pp. 1-10.
[38] S. Hanneke. "Teaching dimension and the complexity of active learning". In: International Conference on Computational Learning Theory. Springer. 2007, pp. 66-81.
[39] R. EI- Yaniv and Y. Wiener. "On the Foundations of Noise-free Selective Classification".. Journal of Machine Learning Research 11.5 (2010).
[40] E. Zermelo. "Untersuchungen über die Grundlagen der Mengenlehre. I". Mathematische Annalen 65.2 (1908), pp. 261-281.
12


Reviews:
[{"review_id": "pmdyqObTNEW", "reviewer": "Reviewer_dG22", "summary": "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\".", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Originality\n\nThe authors compare adequately with the work of Steinke and Zakynthinou, and provide some references to other work.\n\n2. Quality\n\nThe claims are purely theoretical. A minor point:\n\na. In line 190, the authors say that \"the bound in Theorem 3.2 cannot be improved from O(k log n) to O(k)... so the bound in Theorem 3.2 is optimal\". This is not logically sound,  since there are other orders between k and k log n (such as k log (log n))---is there a proof that  O(k log n) is the \"best possible\"? \n\n3. Clarity\n\nThe paper is not written very clearly. For example, in Theorem 1, the basic terms n is not defined. The same issue also occurs in the first paragraph, where the IOMI is denoted by \"IOMI_D(A_n)\" but both D and n are not defined.  Although the definitions come later on in the text, it might be better to have definitions appear earlier. \n\nThe wording is unclear in many places, and I think it would be helpful to add clear definitions and/or descriptions to make reading easier:\n\na. In Line 39 what does \"class of one-dimensional thresholds over {1,...,m}\" mean?\n\nb. In Line 81 what does \"release of the set of all consistent classifiers\" mean?\n\nc. The definitions within the paragraph at Line 128 along with footnote 2 can perhaps be thinned down a bit.\n\n4. Significance\n\nUnderstanding guarantees of algorithms helps both researchers and practitioners gain confidence of using these algorithms, and therefore from this perspective, the results of this paper may be important. It is however unclear from this paper the significance of looking at CMI compared to other measures such as the usual risk. It might be helpful if some of the proofs are moved to the appendix and the space is used to address the importance of these results. Finally, I believe that improving clarity within later revisions would also help to clarify significance and importance.\n\n5. Additional comments\n\nSome typos:\n\na. \"in realizable\" in Line 3 doesn't make sense.\n\nb. In line 127, is the definition of KL divergence missing an integral somewhere?\n\nc. In line 253 \"showing\" is probably \"show\".\n\nd. In line 310 \"the sample the supersample\" may be a typo.\n\n6. Update after reading rebuttal and other reviews: The authors have addressed my concerns and I am adjusting my scores. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion on societal impact is available.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "om6MitmJnY2", "reviewer": "Reviewer_EVBd", "summary": "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.\nThey 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.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is well written with novel, interesting and important results. The results seem technically correct, but I didn't verify all the proofs. I only have some minor comments on the presentation.\n\n- To make the context clearer, I'm missing a clear statement in the introduction of what are the achievable optimal rates in the realizable setting for proper and improper learning, and more generally, when rates of O(d/n) and O(dlogn/n) are optimal. I hope the authors can refine their discussion in this regard in lines 56-66 (in particular, the phrase \"some cases\" in line 61 is unclear) and in the contribution list. A discussion on whether the compression framework characterizes optimal rates will also be beneficial (but might be considered as out of scope).\n\n- At the end, I could not readily say when the CMI framework might fail to characterize optimal rates in the proper/improper learning cases. For example, it is known there are cases where no proper learning algorithm can achieve the optimal rate O(d/n). According to item 3 in Contributions, CMI does not yield O(d/n) for proper learning in some cases as well. So how are these two cases related?\n\n- Please give more details in the Statement of Theorem 4.4, indicating clearly in what way Statement 1 fails. I believe that a clear discussion on the implications of this Theorem for the ability of the CMI framework to characterize optimal rates for proper learning would be beneficial to the reader.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "9ZrVvdIWY9-", "reviewer": "Reviewer_6q6T", "summary": "This work investigates the expressiveness of the CMI framework introduced in [1]. The main contributions of this paper are:\n\n1. The authors show that an empirical variant of CMI can be easily used to express bounds every improper learning. \n2. The authors apply their general CMI bound on SVM, and improve previous results by a logarithmic factor. \n3. VC classes for which proper learning cannot be bounded by any function of the VC dimension are considered\n4. They prove a general reduction showing that the leave-one-out is expressible via the CMI framework. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "That paper is well-written, motivated, and significantly improve our understanding of the CMI framework. \nThe results are quite interesting, and I found the proofs of Theorems 3.4 and 5.4 beautiful and non-trivial. \nTo me, this is a solid contribution, and I do not have any interesting comments/concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes progress in a new approach for proving generalization bounds.
Decision: Accept (Spotlight)