{'fraction_non_alphanumeric': 0.04437390684718533, 'fraction_numerical': 0.008745222517328496, 'mean_word_length': 4.204821308159137, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stochastic Chaining and Strengthened Information-Theoretic Generalization Bounds

We propose a new approach to apply the chaining technique in conjunction with information-theoretic measures to bound the generalization error of machine learning algorithms. Different from the deterministic chaining approach based on hierarchical partitions of a metric space, previously proposed by Asadi et al., we propose a stochastic chaining approach, which replaces the hierarchical partitions with an abstracted Markovian model borrowed from successive refinement source coding. This approach has three benefits over deterministic chaining: 1) the metric space is not necessarily bounded, 2) facilitation of subsequent analysis to yield more explicit bound, and 3) further opportunity to optimize the bound by removing the geometric rigidity of the partitions. The proposed approach includes the traditional chaining as a special case, and can therefore also utilize any deterministic chaining construction. We illustrate these benefits using the problem of estimating Gaussian mean and that of phase retrieval. For the former, we derive a bound that provides an order-wise improvement over previous results, and for the latter we provide a stochastic chain that allows optimization over the chaining parameter.


Motivation
Bounding the generalization error of machine learning algorithms has been studied extensively in the literature. Classical results in this area, such as the VC dimension and the Rademacher complexity, focused mostly on capturing the structural constraints of the hypothesis class. Despite the considerable insights offered by such bounds, they do not explain well the performance of powerful learning algorithms such as deep neural networks [1]. There has been significant recent interest in finding information-theoretic bounds to capture more data-dependent and distribution-dependent structures which may lead to strengthened bounds.
Asadi et al. [2] introduced the chaining technique, which has traditionally been used in bounding random process, into the derivation of information-theoretic generalization bounds. The technique resolves the issue that certain unbounded mutual information quantity leads to a vacuous bound, and may also yield a tighter bound in general. The main idea behind the result in [2] can be summarized as follows. The generalization error can be viewed as a random process {X t } t∈T indexed by the hypothesis parameters. If (T , d) is a bounded metric space under the metric d, then T can be divided into finer and finer partitions, with each coarse partition embedded into the next layer finer partition, and the partition cells having decreasing radius. The generalization error can then be represented by a sum of chained quantities, each relating to two adjacent partition layers. Since the partitions are becoming finer and finer, each of these decomposed quantities can be bounded more effectively, eventually resulting in an overall tighter bound. This approach is referred to as chaining mutual information.
Despite the success of the chaining mutual information approach, we observe several difficulties in applying the chaining technique in this manner, which motivated the current work: • Restriction on the metric space to be bounded: This chaining approach assumes a bounded metric space (T , d). However, even in some of the simplest settings, the parameter space may not be bounded (or impractical to assume the bound on (T , d) is known).
• Difficulty in computation: Using these deterministic and hierarchical partitions, the information measures involved in the bounds can be difficult to compute or bound analytically. Figure 1: Multilevel quantization of a random value W using quantizers of different stepsize and the corresponding information-theoretic successive refinement source coding model.
• Restrictions in the partitions: The hierarchical partitions place certain unnecessary geometric constraints on the covering radius sequence of the required partitions, which can impact the bound.
To make these difficulties more concrete, consider the following two simple examples.
• Example-1: The training samples are drawn i.i.d. following a normal distribution with an unknown mean µ, and the algorithm wishes to estimate this mean. Here the parameter space is T = R, which is unbounded under any meaningful metric, and particularly so for the natural Euclidean distance. Moreover, since the induced measure on T will not be uniform, computing the series sum of mutual information is rather difficult if not impossible.
• Example-2: Let Z := (G 1 , G 2 ) ∼ N (0, I 2 ) be standard normal vectors in R 2 . The learner needs to identify the phase of the vector through certain means, and the learned result is modeled as the true phase with certain additive noise. Here T is the bounded interval of the angle [0, 2π). A natural sequence of partitions is to reduce the stepsize by an integer factor γ. However, this would preclude any non-integer γ values, which potentially makes the bound looser.

Main contribution: stochastic chaining
The sequence of refining partitions of the metric space associated with the chaining technique is reminiscent of multilevel quantization in data compression. For example, a scalar source W distributed on the real line can be quantized with stepsize of 2 −k for the k-th level quantization, resulting in its quantized representation W k . As the index k increases, the stepsize reduces and the accuracy of the quantization improves; see the left side of Fig. 1 for an illustration.
The information-theoretic model for multilevel quantization is usually referred to as successive refinement source coding [3,4]. Particularly useful to us is a stochastic abstraction in this framework. For example, assume there are a total of K-levels, then one possible stochastic representation of the reconstructionŴ k is W k that is written as where N i 's are mutually independent random noises, also independent of W , and α k 's are certain fixed scalar coefficients; see the right side of Fig. 1. It is seen that the relation among W and {W k } K k=1 is captured by the joint probability distribution among them, and we can measure the "distance" between W and W k using Ed(W, W k ), in contrast to the conventional chaining approach which uses the covering radius.
The main idea of this work is that these abstracted stochastic versions of {W k } K i=1 can be used to replace the partition-based quantized versions in bounding the generalization error. This new approach helps to resolve the difficulties mentioned above: firstly the restriction for the metric space to be bounded is naturally removed, and secondly, it helps to simplify the computation, and lastly, the abstract model can remove the geometric constraints in designing the hierarchical partitions in some cases.
The proposed stochastic chaining approach essentially allows more flexible constructions of the chains than the more traditional deterministic chaining. One can attempt to further optimize the construction of stochastic chains based on the existing knowledge regarding the underlying metric space and the corresponding probability distribution for the given problem setting. On the other hand, when such knowledge is not available, we can safely fall back to the default construction of the original deterministic chaining partitions, which is essentially a special case of the stochastic chaining.
We obtain two generalization bounds using stochastic chaining instead of the deterministic chaining in [2], built on the mutual information bound given in [5] and the individual sample mutual inforamtion bound given in [6], respectively. We further show that the proposed bound can reduce to the VC-dimension bound correctly. We then illustrate the benefits of this new approach in the context of the two examples. For the problem of estimating the Gaussian mean mentioned above, we can obtain a bound that is order-wise stronger than previously given in the literature. For the phase retrieval problem considered in [2], the bound can be naturally improved by optimizing over a continuous parameter.

Related works
The approach of using information-theoretic tools to develop generalization error bounds was pioneered by Russo and Zou [7], and then extended by Xu and Rakinsky [5]. The bound in [5] was later tightened by Bu et al. in [6], using the individual sample mutual information instead of sample set mutual information. Steinke and Zakynthinou [8] proposed a conditional mutual information based bound by introducing pseudo samples and split them into training and testing samples. Combining the idea of error decomposition [6] and the conditional mutual information bound in [8], Haghifam et al. [9] provided a sharpened bound based on conditional individual mutual information. Hafez-Kolahi et al. proposed a streamlined view of several bounding techniques proposed in the literature [10]. Rodriguez-Galvez et al. [11] and Zhou et al. [12] provide further improved on conditional individual mutual information type of bound. Hellstrom and Durisi [13,14] used information density to unify several existing bounds and bounding approaches. Similar bounds using other measures can be found in [15]. The information-theoretic bounds have been used to bound generalization errors in noisy and iterative learn algorithms [16,17,18,9,11].

Organization of the paper
The rest of the paper is organized as follows. In Section 2, we introduce the necessary notation and general background on the chaining technique and successive refinement source coding. The main results are given in Section 3 with a few important discussions. In Section 4, we return to the two motivating examples to illustrate the benefits of the proposed bound, and Section 5 concludes the paper.

Generalization error
Consider the supervised learning setting, and denote the data domain as Z := X ×Y, where X is the instance domain and Y is the label domain. The hypothesis class is denoted as H W = {h W : W ∈ W} ⊆ Y X , where W is the parameter space, or more generally the index set of the hypothesis class. A learning algorithm has access to a sequence of training samples Z [n] = (Z 1 , Z 2 , . . . , Z n ), where each Z i is drawn independently from Z following some unknown probability distribution ξ, and the notation [n] is used to denote the set {1, 2, . . . , n}. The mapping from the data set Z [n] to the hypothesis can be represented by the kernel P W |Z [n] .
Under a loss function : W × Z → R, the population risk is given as For training using the data set Z [n] , the empirical risk of a given hypothesis h w is The generalization error for the given data set is defined as The expected generalization error is defined as where the expectation is taken over the joint distribution P (W, Z [n] ) = ξ n ⊗ P W |Z [n] . Our goal is to bound gen(ξ, P W |Z [n] ) in this work. Generalization error can also be written in a different form by defining Clearly gen(ξ, It is worth noting that the distribution P W |Zi is obtained by marginalizing over P (W, Z [n] ) (and dividing ξ).

Random process and partitions
Let {X t } t∈T be a random process with the index set T . There is a metric d on T which describes the dependence among the random variables in the random process. For simplicity, {X t } t∈T is written as X T whenever it does not cause confusion.
The following definitions are standard.
Definition 1 (Separable process). The random process X T on the metric space (T , d) is called separable if there is a dense countable set T 0 ⊂ T such that for any t ∈ T , there exists a sequence (s n ) in T 0 such that s n → t and X sn → X t a.s..
All the random processes considered in this paper are separable.
Definition 2 (Sub-Gaussian process). The random process X T on the metric space Let W be a random variable on the set W. From here on, we use capital letter (such as W ) to denote a random variable, and its lower case letter (such as w) to indicate a realization. In the particular setting of generalization bound, the random variable W is the index (or the parameters) of the hypothesis chosen by the possibly randomized learning algorithm using the stochastically generated data set Z [n] . The random process is A well known tool in bounding a random process is the chaining technique [19]. The notion of an increasing sequence of -partition of the metric space (T , d) is particularly important in this setting.
Definition 3 (Increasing sequence of -partition). A partition P = {A 1 , A 2 , . . . , A m } of the set T is called an -partition of the metric space (T , d) if for all i = 1, 2, . . . , m, A i can be contained within a ball of radius . A sequence of partitions {P k } ∞ k=m of a set T is called an increasing sequence if for any k ≥ m and each A ∈ P k+1 , there exists B ∈ P k such that A ⊆ B.
In the context of bounding the generalization error, when it is viewed as a random process X T , we are interested in the expectation E[X W ].

Information theory and successive refinement source coding
For a discrete random variable X, the entropy is denoted as H(X), and for a continuous random variable Y , its differential entropy is denoted as h(Y ). The mutual information between two random variables X, Y is denoted as I(X; Y ), regardless whether they are discrete or continuous. We use natural logarithm in this work, and thus information is measured in terms of nats.
Successive refinement source coding considers the problem of encoding a source X in a total of K stages, each with rate R k nats of coding budget, and the end user uses the encoded information in all previous stages, i.e., stages 1, 2, . . . , k, to reconstruct the source at stage k. The achievable rate region, i.e., the set of encoding rate vectors, is given as the collection of nonnegative rates (R 1 , R 2 , . . . , R K ) such that where X k is a random variable representing the stochastic reconstruction of X at stage-k, which guarantees , the distortion is less than or equal to the given distortion budget D k ; see [3] for more details. One particular useful choice is to make X ↔ X K ↔ X K−1 ↔ · · · ↔ X 1 a Markov chain. The simplification is immediate since in this case. When the choice of X K , X K−1 , . . . , X 1 satisfying the Markov chain also yields the optimal coding rates among all possible choices of auxiliary X K , X K−1 , . . . , X 1 random variables, the source X is called successively refinable [4]. More results on this problem can be found in [20,21].
3 Main results

Main Theorems
We define a new notion of stochastic chain as follows.
Definition 4 (Stochastic chain of random process and random variable pair). Let (X T , W ) be a random process and random variable pair, where W is a random variable in the set T . A sequence of random variables {W k } ∞ k=k0 , each distributed in the set T , is called a stochastic chain of the pair (X T , W ), if 1) We allow k 0 to take the value of −∞ instead of providing another parallel definition to that effect. We are now ready to present the first main theorem of this work.
Moreover, we have The following theorem is based on the individual sample mutual information bound of [6]. Then Moreover, we have These two theorems are given in the context of bounding generalization errors, which are obtained using a more general result on bounding random processes.
Moreover, we have By using a deterministic sequence of partitions to form {W k } ∞ k0 , we recover the result in [2] which was obtained for bounded metric space (T , d).
k=k0 be an increasing sequence of partitions of T , where for each k ≥ k 0 , P k is a 2 −k -partition of the bounded metric space (T , d), and 2 −k0 ≥ diam(T ). Let W k be the center of the covering ball of the partition cell that W belongs to in the partition P k , then for separable process X T on (T , d), The proof of Theorem 3 can be found in the supplementary material. To obtain Theorem 1 from Theorem 3, we let T := W, and X w := gen(w) for w ∈ W. Due to the Markov chain for all k ≥ k 1 , we can apply the data processing inequality for KL divergence [22] and that for mutual information, respectively, to arrive at , from which Theorem 1 follows immediately. Theorem 2 can be obtained similarly. When the process is not sub-Gaussian, more general forms of these bounds can also be found in terms of the cumulant generating function. This result is given in the supplementary material.

Relations to existing results
Connection to VC theory: For binary classification problems, i.e., |Y| = 2 with zero-one loss (w, (x, y)) = I(h w (x) = y), the generalization error of any classifier W is upper bounded as gen(ξ, where d V C (W) is the VC-dimension of the classification function class H W (c.f., [23] Ch. 6). The generalization error bound in Theorem 3, or more precisely the proposed stochastic chaining approach, can naturally recover the VC-dimension based bound, and we establish this connection in the supplementary material.
Discussion on the chaining construction: The conventional deterministic chaining places certain structural constraints on the hierarchical partitions. For example, consider a partition of a bounded 2-D space using congruent hexagon cells; the next partition at the higher level will be collections of such hexagons. This subsequently implies that hierarchy must follow a certain relation between consecutive levels, and the analysis of such hierarchical partitions can be complex. The stochastic chaining technique can remove the geometric constraints in the design of hierarchical partitions as in Corollary 1 in many cases. In the example above, we can replace the partition using either an additive Gaussian noise or additive noise with a uniform distribution on hexagons (see the second example in the next section where a similar uniform additive noise is used).
Since stochastic chains include conventional partition-based chaining as a special case, it is not more difficult to construct. In fact, the construction can be more straightforward due to its flexibility. For example, for bounded metric space, we can use the following generic construction: let p(W k−1 |W k ) be uniformly distributed on a metric ball of radius 2 −k centering at W k . If more information regarding the distribution of W is known, we can further optimize the chain, e.g., by adjusting the radius such that they are dependent on the density value of W k ; more specifically, we can let the radius be larger for W k values of lower density, and vice versa. If the metric space is also a vector space, it can be convenient to let p(W k−1 |W k ) be some vector Gaussian distribution with covariance scaling like 2 −k . This allows more opportunity for optimization for stronger bounds in a parametric form. In contrast, it is impossible to design partitions (or deterministic mappings [10]) to mimic such behaviors, let alone finding analytic bound. This issue in fact has a natural origin in source coding: deterministic quantization design vs. probabilistic forward test channel modeling. The latter is used in source coding for mathematically precise characterization, and for analytic optimization.
Comparison to the chaining technique in [10]: The alternative chaining method proposed by Hafez-Kolahi et al. (Theorem 6 in [10]) used a different chaining construction, which does not require hierarchical partitions, and to some extent it helps resolve the difficulty in designing such hierarchical partitions. However, this simplification came with a heavy price: the learning algorithm must be deterministic, the hypothesis space W still needs to be bounded (since the core steps rely on [2]), and there is a factor of 2 loss in the bound. The restrictions make it inapplicable in the two examples we study in the next section. In contrast, the proposed method applies to unbounded metric space, and does not require the learning algorithm to be deterministic.

Two examples: estimating the Gaussian mean and phase retrieval
We analyze two simple settings, which demonstrate the effectiveness of the proposed stochastic chaining technique. The purpose for discussing the following two examples is by no means to literally characterize the generalization error, since the generalization error can be calculated directly due to the simplicity of the examples. We aim to show the effectiveness of the proposed stochastic chaining technique in these two examples by comparing with the underlining generalization error and some previous generalization error bound.

Estimating the Gaussian Mean
Consider the case when the training samples Z [n] are drawn i.i.d. following N (µ, σ 2 ) for some unknown µ.
Here T = R, and a natural choice of the metric on this space is the (scaled) Euclidean distance. The loss function is (w, Z) = (w − Z) 2 , and by definingZ n := 1 n n i=1 Z i , the random process (indexed by w) of interest can be written as It follows that The learner deterministically estimates µ by averaging the training samples, i.e., W =Z n . We shall use Theorem 1 to bound the generalization error in this case.
To build a stochastic chain, select a sequence of mutually independent Gaussian noise {N i } i∈N , which is independent of W , and N i ∼ N (0, σ 2 i ), where σ 2 i = σ 2 2 i n . Define the cumulative noise where σ 2 k = σ 2 2 k n . The stochastic chain is designed as where 2 k−1 +1 , which relies on the relations between W k and W k−1 in (23) and the detailed calculation is given in the supplementary material. The mutual information can be upper bounded as where the inequality is due to the data processing inequality over the Markov chain Z [n] ↔ W ↔ W k and the equality is by the Gaussian channel nature of the stochastic chain design. The detailed proof steps are given in the supplementary material. A bound of the following form can then be obtained Note that the series sum on the right hand side of (25) converges, and thus the bound is of order O(σ 2 /n). Bounding the series sum using numerical methods, we can then obtain E[X W ] ≤ 13σ 2 n . Due to the simplicity of the setting, the generalization error can in fact be calculated exactly to be 2σ 2 n . It can be seen that the generalization bound offered by Theorem 1 has the same O(σ 2 /n) order as the true generalization error. In contrast, the authors of [6] derived a generalization error bound of the order O(σ 2 / √ n) using the individual sample mutual information approach. Thus the proposed approach results in an order-wise improvement in this example case. More importantly, it can be seen that the proposed chaining approach allows us to overcome the limitation of bounded metric space (i.e., the chaining mutual information approach [2] does not even apply in this setting), and also simplify the calculation due to the introduced dependence structure in the chain. In the supplementary material, we further derive an improved bound (with a slightly better constant factor) using Theorem 2.

Phase retrieval
In the phase retrieval example given in [2], the data Z := (G 1 , G 2 ) ∼ N (0, I 2 ) is a standard normal vector in R 2 . The hypothesis class is W = [0, 2π), and through the transformation t = (cos w, sin w) for w ∈ W, it is in fact the same as T = {t ∈ R 2 : ||t|| 2 = 1}; we will use them interchangeably. Define the loss function (t, Z) = − t, Z , which implies that the learner wishes to estimate an angle for the underlying data, and the generalization error process is a Gaussian process X t := t, Z . The metric d is the Euclidean distance, and the process X T is sub-Gaussian. Suppose the learned parameter is where ζ is independent of X T , and has an atom with a mass on 0, and 1 − that is uniformly distributed in [0, 2π). Note that arg max φ∈[0,2π) X φ is exactly the phase of (G 1 , G 2 ), which will be the hypothesis learned by an ERM learner, and W being retrieved here is a noisy version of the phase. The stochastic chain can be given as where N k = ∞ i=k+1 N i , and N k is uniformly distributed on [−γ −k π, γ −k π) for some γ > 1 to be specified later; N k 's are mutually independent and also independent of the hypothesis parameter W .
Since W ⊕ N −1 is independent of Z and uniformly distributed on [0, 2π), we have E[X W−1 ] = E[ W + N −1 , Z ] = 0. It is also clear that W k → W when k → ∞ a.s., and thus E[X W ] = lim k→∞ E[X W k ] since the process is Gaussian. Since W k−1 − W k is exactly N k , the Euclidean distance between W k and W k−1 (using their vector representations) is bounded by the length of the arc, i.e., d(W k , W k−1 ) ≤ γ −k π. We can now apply Theorem 1, where The second term can be bounded as using the fact that more conditioning reduces the differential entropy. Due to the structure of the distribution of N k+1 and Z, the density of N k+1 ⊕ ζ can be written down explicitly as Thus we can bound h(N k ⊕ ζ) and subsequently I(W k ; X T ) using this density function, which eventually gives When choosing γ = 2, this is almost identical to the result given in [2] using the partition based chaining, except the slightly better coefficient √ 2π instead of 6 √ 2. This improved coefficient is mainly due to the more explicit bound on d(W k , W k−1 ) inherent in the Euclidean space, instead of the same distance derived in a generic metric space.
One advantage of the proposed approach is that we can further optimize γ over R. Observe that the series has a faster decaying tail if γ is large, however, the first term, i.e., k = 0, approaches ∞ when γ → ∞. Thus there is an optimal γ value in between for this bound. Numerical result suggests γ * ≈ 3.75, which provides a slight improvement comparing to γ = 2. As noted in [2], in this toy setting, we can in fact calculate the exact true value E[X W ] = √ π 2 . A comparison of several bounds is given in Table. 1. To obtain (31), we have in fact relaxed this bound in (29) for convenience using a simple property of the entropy function, and therefore loosen the bound to some extent. Moreover, we have chosen to use the geometric sequence γ k to produce the stochastic chain, and it is possible other sequences can produce tighter bounds.
The individual sample mutual information bound in [6] requires multiple samples. In this phase retrieval example, however, there is only one sample G 2 , and this bound degrades to the mutual information based bound in [5], which in this case is vacuous since I(W ; X T ) is in fact infinite.

Conclusion
We proposed a new chaining-based approach to bound the generalization error by replacing the hierarchical partitions with a stochastic chain. The proposed approach can firstly remove naturally the restriction for the metric space to be bounded, and secondly, it helps to simplify the computation, and lastly, it can remove the geometric constraints in designing the hierarchical partitions in some cases. Two examples are used to illustrate that the proposed approach can overcome some difficulties in applying the chaining mutual information approach. The roles that chaining can play in bounding generalization error on conjunction with other information-theoretic approach, such as the conditional mutual information [8], information density [14], and Wasserstein distance [15], as well as the possible application in noisy and stochastic learning algorithms, call for further research.

A Proof of Theorem 3.3
To prove the theorem, we start by writing , and it follows that By the Donsker-Varadhan variational representation of the KL divergence, the expectation of a function g(Y ) with respect to the measure P defined on Y can be bounded as where Q is another measure on Y.
In our setting, let Y = g(Y ) = ∆X w k ,w k−1 , P = P ∆Xw k ,w k−1 |w k ,w k−1 , and Q = P ∆Xw k ,w k−1 , then we have where the second inequality is because the process X T is sub-Gaussian on (T , d).
The fact that {W k } ∞ k=k0 is a stochastic chain also implies that lim k→∞ E[X W k ] = E[X W ], and thus DenoteX T as an independent copy of X T such thatX T and X T are independent and have the same distribution. P ∆ k is the distribution of ∆X W k ,W k−1 conditioned on W k , W k−1 . By the data processing inequality for the KL divergence, we have from which the second inequality follows. Let us now consider the mutual information based bound. It is seen that Combing with (33) we arrive at which concludes the proof.

B A chaining bound in a more general form
In this section we provide a more general bound without the assumption on sub-Gaussianity, and replace it with a more general form on the measure concentration.
Definition 5. Let X be a real-valued random variable. The cumulant generating function of X is Λ X (λ) := log E[e λX) ] for λ ∈ R.
Lemma 4. Assume that ψ(0) = ψ (0) = 0, then ψ * (x) is a non-negative convex and non-decreasing function on [0, ∞) with ψ * (0) = 0. Moreover, its inverse function ψ * −1 (y) = inf{x ≥ 0 : ψ * (x) ≥ y} is concave, and can be written as Theorem 5. Assume X T is a random process defined on the metric space (T , d), with E[X t ] = 0 for all t ∈ T and log E e λ(X t −Xs ) d(t,s) ≤ ψ(λ), for all t, s ∈ T , λ ≥ 0, where ψ is convex and ψ(0) = ψ (0) = 0. Let {W k } ∞ k=k0 be a stochastic chain for the random process and random variable pair (X T , W ), then Proof. To prove the theorem, we start by writing Because {W k } ∞ k=k0 is a stochastic chain for (X T , W ), we have E[X W k 0 ] = 0, and it follows that By the Donsker-Varadhan variational representation of the KL divergence, the expectation of a function g(X) with respect to the measure P defined on X can be bounded as where Q is another measure on X . In our setting, let P = P ∆ k |w k ,w k−1 , Q = P ∆ k , and g(X) = X w k − X w k−1 , then we have where the second inequality is by assumption (42). The fact that {W k } ∞ k=k0 is a stochastic chain also implies that lim k→∞ E[X W k ] = E[X W ], and thus we arrive at Moreover, since {W k } ∞ k=k0 is a stochastic chain, the Markov condition implies that and thus from which, the first inequality in (43) follows. If d(W k , W k−1 ) ≤ σ k , then we have where the last inequality is due to Jensen's inequality and E D(P X T |W k ||P X T ) = I(X T ; W k ) by definition.

C Connection to VC dimension
Consider the binary classification problem with zero-one loss with hypothesis class parameterized by W and data Z [n] ∼ ξ n . We follow the similar approach as in [10]. Independent random variables Z + [n] ∼ ξ n , Z − [n] ∼ ξ n and R [n] ∼ Rademacher n determines the random process X W with By Hoeffding's lemma, X w − X u given Z ± [n] is sub-Gaussian with parameter Define the RHS of the inequality above as d 2 (w, u). Given Z ± [n] , if a stochastic chain {W k } k≥k0 exists for the conditional process X T |Z ± [n] , we know where I Z ± [n] (X W ; W k ) := D(P X W ,W k |Z ±

[n]
), and the last equality is due to Markov chain X W ↔ W k ↔ W k−1 .