Recognizable Information Bottleneck

1 Introduction

Learning representations that are generalized to unseen data is one of the most fundamental goals for machine learning. The IB method [Tishby et al., 2000] is one of the prevailing paradigms. It centers on learning representations that not only sufficiently retain information about the label, but also compress information about the input. The rationale behind the IB is that the information compression of representations penalizes complex hypotheses and guarantees generalization by a probability generalization bound [Shamir et al., 2010; Vera et al., 2018]. It is expected that one can obtain a lower generalization gap through optimizing the IB training objective. However, in finite and continuous data scenarios, such as an image classification task with deep neural networks (DNNs), this upper bound is dominated by a prohibitively large constant with any reasonable probability and becomes vacuous, thus making the information compression term negligible [Rodriguez Galvez, 2019]. This deprives IB method of the theoretical guarantee in real-world scenarios.

∗Corresponding author.

Appendices are available at: https://arxiv.org/pdf/2304.14618.

Recently, motivated by the mutual information (MI)-based generalization bound in the information-theoretic framework [Xu and Raginsky, 2017], Wang et al. [2022] proposed to use the information stored in weights, i.e., the MI between the input dataset and the output weights of the algorithm, to replace the compression term in the IB objective. It is worth noting, however, that the MI-based generalization bound may still be vacuous due to the fact that the MI can easily go to infinity, e.g., in cases where the learning algorithm is a deterministic function of the input data [Bu et al., 2020; Steinke and Zakynthinou, 2020]. More importantly, it is notoriously difficult to estimate the MI between two highdimensional random variables, e.g., weights of model and a training dataset. Although one can recover non-vacuous bound by restricting the prior and posterior of the weights to Gaussian distributions [Dziugaite and Roy, 2017; Wang et al., 2022], the computational burdens (from e.g., MonteCarlo sampling or calculating the second-order curvature information) are still cumbersome.

To address the unbounded nature of MI-based bound, Steinke and Zakynthinou [2020] proposed the celebrated conditional mutual information (CMI) generalization bound, which normalizes each datum to one bit, thus is always bounded. The intuition is that measuring information that "recognizes" an input sample is much simpler than measuring information that "reconstructs" an input sample. Harutyunyan et al. [2021] further extended this idea to a black-box algorithm setting and proposed a functional CMI (f -CMI) generalization bound, which significantly reduces the computational cost by computing the CMI with respect to the low-dimensional predictions rather than the high-dimensional weights. This inspires us to consider the DNN encoder as a black box and the representation as the output predictions, which coincides with the original IB setting. Unfortunately, the computation of the f -CMI bound requires multiple runs on multiple draws of data, there is not yet a practical optimization algorithm to incorporate it into the training of the models.

In this paper, we first formulate the recognizability from the perspective of binary hypothesis testing (BHT) and show the connection between the recognizability of representations and the f -CMI generalization bound. Based on the reasoning that lower recognizability leads to better generalization, we propose a new IB objective, called the Recognizable Information Bottleneck (RIB). A recognizability critic is exploited to optimize the RIB objective using density ratio matching under the Bregman divergence. Extensive experiments on several commonly used datasets demonstrate the effectiveness of the RIB in controlling generalization and the potential of estimating the generalization gap for the learned models using the recognizability of representations.

Our main contributions can be concluded as follows:

• We define a formal characterization of recognizability and then show the connection between the recognizability of representations and the f -CMI bound.
• We propose the RIB objective to regularize the recognizability of representations.
• We propose an efficient optimization algorithm of RIB which exploits a recognizability critic optimized by density ratio matching.
• We empirically demonstrate the regularization effects of RIB and the ability of estimating the generalization gap by the recognizability of representations.

1.1 Other RelatedWork

Information bottlenecks. There have been numerous variants of IB [Alemi et al., 2017; Kolchinsky et al., 2019; G´alvez et al., 2020; Pan et al., 2021; Yu et al., 2021] and have been utilized on a wide range of machine learning tasks [Du et al., 2020; Lai et al., 2021; Li et al., 2022]. However, one pitfall of IBs is that there may be no causal connection between information compression and generalization in realworld scenarios [Saxe et al., 2018; Rodriguez Galvez, 2019; Dubois et al., 2020]. Wang et al. [2022] addressed this issue by introducing an information complexity term to replace the compression term, which turns out to be the Gibbs algorithm stated in the PAC-Bayesian theory [Catoni, 2007; Xu and Raginsky, 2017].

Information-theoretical generalization bounds. The MI between the input and output of a learning algorithm has been widely used to bound the generalization error [Xu and Raginsky, 2017; Pensia et al., 2018; Negrea et al., 2019; Bu et al., 2020]. To tackle the intrinsic defects of MI, Steinke and Zakynthinou [2020] proposed the CMI generalization bound, then Haghifam et al. [2020] proved that the CMIbased bounds are tighter than MI-based bounds. Zhou et al. [2022] made the CMI bound conditioned on an individual sample and obtained a tighter bound. The above bounds are based on the output of the algorithm (e.g. weights of the model) rather than information of predictions which is much easier to estimate in practice [Harutyunyan et al., 2021].

2 Preliminaries

2.1 Notation and Definitions

We use capital letters for random variables, lower-case letters for realizations and calligraphic letters for domain. Let X and Y be random variables defined on a common probability space, the mutual information between X and Y is defined as I(X; Y ) = DKL(PX,Y ∥PX ⊗ PY ), where DKL is the Kullback-Leibler (KL) divergence. The conditional mutual information is defined as I(X; Y |Z) = DKL(PX,Y |Z∥PX|ZPY |Z|PZ) = Ez∼PZ [I(X; Y |Z = z)]. A random variable X is σsubgaussian if E [exp(λ(X -E(X)))] ≤ exp (λ2σ2 /2) for all λ ∈ R.

Throughout this paper, we consider the supervised learning setting. There is an instance random variable X, a label random variable Y , an unknown data distribution D over the Z = X × Y and a training dataset S = (Z1, Z2, . . . , Zn) ∼ Dn consisting of n i.i.d. samples drawn from the data distribution. There is a learning algorithm A : Z n → W and an encoder function fθ : X → T from its class F := {T = EX[1[t = fθ(X)]] : θ ∈ W}. We assume that T is of finite size and consider T as the representation. We define two expressions of generalization, one from the "weight" perspective and one from the "representation" perspective:

1. Given a loss function ℓ : W ×Z → R, the true risk of the algorithm A w.r.t. ℓ is L(w, S) = Ez′∼Dℓ(w, z′ ) and the empirical risk of the algorithm A w.r.t. ℓ is Lemp(w, S) = 1n ∑ni=1 ℓ(w, zi). The generalization error is defined as gen(w, S) = L(w, S) - Lemp(w, S);
2. Given a loss function ℓ : T × Y → R, the true risk of the algorithm A w.r.t. ℓ is L(T, Y ) = Ez′∼Dℓ(t′ , y′ ) and the empirical risk of the algorithm A w.r.t. ℓ is Lemp(T, Y ) = 1n ∑ni=1 ℓ(ti, yi). The generalization error is defined as gen(T, Y ) = L(T, Y ) - Lemp(T, Y ).

2.2 Generalization Guarantees for Information Bottlenecks

The IB method [Tishby et al., 2000] wants to find the optimal representation by minimizing the following Lagrangian:

where β is the Lagrange multiplier. The I(T;X) in Eq. (1) can be seen as a compression term that regularizes the complexity of T. It has been demonstrated to upper-bound the generalization error [Shamir et al., 2010; Vera et al., 2018]. Concretely, for any given δ > 0, with probability at least 1-δ it holds that

where Cδ = O(|T |/√n) is a constant that depends on the cardinality of the space of T. The bound implies that the less information the representations can provide about the instances, the better the generalization of the algorithm. However, since |T | will become prohibitively large with any reasonable choice of δ, this bound is actually vacuous in practical scenarios [Rodriguez Galvez, 2019].

A recent approach PAC-Bayes IB (PIB) [Wang et al., 2022] tried to amend the generalization guarantee of IB by replacing the compression term with the information stored in weights, which leads to the following objective:

The rationale behind the PIB is stem from the input-output mutual information generalization bound which can also be derived from the PAC-Bayesian perspective [Xu and Raginsky, 2017; Banerjee and Mont ´ufar, 2021]. Concretely, assume that the loss function ℓ(w, Z) is σ-subgaussian for all w ∈ W, the expected generalization error can be upper-bounded by

Intuitively, the bound implies that the less information the weight can provide about the input dataset, the better the generalization of the algorithm. However, as we mentioned above, the MI-based bound could be vacuous without proper assumptions and is hard to estimate for two high-dimensional variables such as the weight W and the training dataset S.

2.3 The CMI-based Generalization Bounds

The CMI-based bounds [Steinke and Zakynthinou, 2020; Harutyunyan et al., 2021] characterize the generalization by measuring the ability of recognizing the input data given the algorithm output. This can be accomplished by recognizing the training samples from the "ghost" (possibly the test) samples. Formally, consider a supersample ˜ Z ∈ Z n×2 constructed from n input samples mixed with n ghost samples. A selector variable U ∼ Unif({0, 1}n ) selects the input samples from the supersample ˜ Z to form the training set S = ˜ ZU = ( ˜ Zi,Ui+1)ni=1 . Given a loss function ℓ(w, z) ∈ [0, 1] for all w ∈ W and all z ∈ Z, Steinke and Zakynthinou [2020] bound the expected generalization error by the CMI between the weight W and the selector variable U given the supersample ˜ Z:

The intuition is that the less information the weight can provide to recognize input samples from their ghosts, the better the generalization of the algorithm. In this way, the algorithm that reveals a datum has only CMI of one bit, bounding the CMI by n log 2, while the MI may be infinite. Harutyunyan et al. [2021] extended this idea to a black-box algorithm setting which measures the CMI with respect to the predictions of the model rather than the weight. It is able to further extend the prediction domain to the representation domain, which yields a setting similar to the original IB. Given a loss function ℓ(t, y) ∈ [0, 1] for all t ∈ T and all z ∈ Z, the expected generalization error is upper-bounded by the following f -CMI bound:

From the Markov chain U → W → T and the data processing inequality, it follows that I(T;U| ˜ Z) ≤ I(W; U| ˜ Z), which indicates the bound in Eq. (3) is tighter than the bound in Eq. (2). Similarly, we can learn from the bound that the less information the representations can provide to recognize input samples from their ghosts, the better the generalization of the algorithm. Since the representation T and the selector variable U are relatively lower dimensional than the weight W and the dataset S, respectively, estimating the f -CMI bound is far more efficient than the previous bounds.

3 Methodology

Although the f -CMI bound is theoretically superior to the generalization bounds of existing IBs, it has so far only been used as a risk certificate for the learned model [Harutyunyan et al., 2021]. Since computing the f -CMI bound requires multiple runs on multiple draws of data, there is no immediate way to incorporate it into the training of deep models. In this section, we first give a formal characterization of the recognizability and describe how to use the recognizability of representations to approximate the f -CMI bound. This motivates us to propose the RIB objective and an efficient optimization algorithm using a recognizability critic.

3.1 Recognizability

In order to characterize the recognizability, we first review some basic concepts of binary hypothesis testing (BHT) [Levy, 2008]. Assume that there are two possible hypotheses, H0 and H1, corresponding to two possible distributions P and Q on a space X , respectively,

A binary hypothesis test between two distributions is to choose either H0 or H1 based on the observation of X. Given a decision rule Ξ : X → {0, 1} such that Ξ = 0 denotes the test chooses P, and Ξ = 1 denotes the test chooses Q. Then the recognizability can be defined as follows:

Definition 1 (Recognizability). Let H0,H1, P,Q,X, Ξ be defined as above. The recognizability between P and Q w.r.t. Ξ for all randomized tests PΞ|X is defined as

where Pr(Ξ = 1|H0) is the probability of error given H1 is true and Pr(Ξ = 1|H1) is the probability of success given H0 is true.

Remark. In words, the recognizability is the area of the achievable region for all tests drawn from PΞ|X (see Fig. 1a). For BHT, one would like to select a test such that Pr(Ξ = 1|H0) is as close to zero as possible while Pr(Ξ = 1|H1) is as close to one as possible. However, the extreme case, i.e., (Pr(Ξ = 1|H0) = 0, Pr(Ξ = 1|H1) = 1) or (0, 1), is achievable only if the hypotheses H0 and H1 are completely mutually exclusive, that is, P is mutually singular w.r.t. Q, which indicates that the recognizability ℜΞ(P,Q) = 1 (Fig. 1b). Similarly, when H0 and H1 are equivalent, that is, P and Q are identical, we have the recognizability ℜΞ(P,Q) = 0 (Fig. 1c).

By the celebrated Neyman-Pearson lemma, we have that log-likelihood ratio testing (LRT) is the optimal decision rule, which means all the points in the achievable region are attained by LRT [Neyman et al., 1933]. It is also wellknown that the upper boundary between the achievable and unachievable region is the receiver operating characteristic (ROC) of LRT [Levy, 2008]. Therefore, given a LRT decision rule ξ : X → [0, 1], the recognizability w.r.t. ξ can be computed by

where AUCROCξ is the area under the ROC curve of ξ.

The formulation of recognizability offers us some fresh insights to consider generalization from the perspective of BHT, which leads to a new approach to regularization. Concretely, we rewrite the f -CMI term in Eq. (3) as

where Eq. (5) follows by the uniformity of U. Consider a realization of supersample ˜ z. Let t1, t2, . . . , tn be a sequence drawn i.i.d. according to PT|U, ˜ Z=˜ z , then by the weak law of large numbers we have that

This suggests that the log-likelihood ratio between the distributions PT|U, ˜ Z=˜ z and PT| ˜ Z=˜ z amounts to the KL divergence, and eventually an estimate of I(T ; U|˜ z), which is the single-draw of the f -CMI bound. Thus, the more similar these two distributions are, the more difficult it is for us to determine which hypothesis ti originates from by LRT, namely, the lower the recognizability; we can also verify, in turn, that the KL divergence is minimal when we achieve the lowest recognizability (Fig. 1c). To make this explicit, we theoretically establish the connection between recognizability of representations and the f -CMI bound through the following theorem.

Theorem 1. Let ˜ z be a realization of supersample ˜ Z, T be the representation variable defined as above, ξ : T → [0, 1] be the LRT decision rule and U ∼ Unif({0, 1}n ). The recognizability of representations ℜξ(PT | ˜ Z=˜ z , PT |U, ˜ Z=˜ z ) is upper bound by I(T ; U|˜ z) + log e2 .

Proof. See Appendix A.

Inspired by the above insights, we propose the RIB to constrain the model to learn representations having low recognizability, which utilizes a log-likelihood ratio estimator that we name recognizability critic. We will detail it in the next subsection.

3.2 Recognizable Information Bottleneck

We first define a new objective function that takes the recognizability of representations into consideration. Let ˜ z be a realization of ˜ Z which is composed of a training set S of size n and a ghost set ¯ S of the same size, U ∼ Unif({0, 1}n ) be a random variable indicating the set from which the instance of representation comes. Note that in general the ghost set is built from the validation or test (if available) set with dummy labels, and we will experiment later with ghost from different sources. Now we can write a new IB objective called the Recognizable Information Bottleneck (RIB) as follows:

where the first term enforces empirical risk minimization, the second term regularizes the recognizability of representations and β is the trade-off parameter.

To optimize the second term of Eq. (6), we first train a log-likelihood ratio estimator Vϕ : T 2 → R that we call the recognizability critic. It takes a pair of representations as input, one obtained from the training set S samples and the other from the ghost set ¯ S. The pair of representations is then randomly concatenated and treated as a single draw from the joint distribution PT,U| ˜ Z=˜ z , since the probability of occurrence of the possible outcomes is consistent. Next we train the recognizability critic by maximizing the lower bound on the Jensen-Shannon divergence as suggested in [Hjelm et al., 2019; Poole et al., 2019] by the following objective:

where sp(x) = log(1 + ex ) is the softplus function. Once the critic V reaches the maximum, we can obtain the density ratio by

Since the lowest recognizability achieves when the two distributions are identical, that is, the density ratio R∗ ≡ 1, to regularize the representations, we use a surrogate loss motivated by density-ratio matching [Sugiyama et al., 2012], which optimizes the Bregman divergence between the optimal density ratio R∗ and the estimated density ratio R(˜ t) defined as

Here, F is a differentiable and strictly convex function and ∂F is its derivative. We can derive different measures by using different F. In the experiments we use F(R) = R log R - (1 + R) log(1 + R), at which point the Bregman divergence is reduced to the binary KL divergence. More examples and comparison results are given in Appendix C.

Algorithm 1 Optimization of Recognizable Information Bottleneck (RIB)

Input: training set S = {(xi, yi)}Ni=1 , ghost set ¯ S = {¯xi}Ni=1 , encoder fθ, initial encoder parameter θ0, recognizability critic Vϕ, initial recognizability critic parameter ϕ0, batch size B, learning rate η

Output: trained encoder parameter θ, trained recognizability critic parameter ϕ

• 1: initialize: θ ← θ0, ϕ←ϕ0
• 2: while not converged do
• 3: sample training mini-batch {(xi, yi)}Bi=1 ∼ S
• 5: sample {ui}Bi=1 ∼ Unif({0, 1})
• 4: sample ghost mini-batch {¯xi}Bi=1 ∼ ¯ S
• 6: compute {ti = fθ(xi)}Bi=1 , {¯ ti = fθ(¯xi)}Bi=1

• t = {˜ ti}Bi=1 , where ˜ ti = {ti ◦ ¯ ti, ui = 0 ¯
• 7: set ˜
• 8: compute gradient gϕ by Eq. (7) and update ϕ: ϕ ← ϕ + ηgϕ
• 10: end while
• 9: compute gradient gθ by Eq. (9) and update θ: θ ← θ - ηgθ
• 11: return (θ, ϕ)

Now the objective function for the encoder fθ can be written as

The complete optimization algorithm is described in Algorithm 1. Note that although it is also feasible to directly minimize Eq. (7) with respect to the encoder parameter θ which leads to a minimax game similar to GAN [Goodfellow et al., 2014; Nowozin et al., 2016], we empirically find that this may cause training instability especially when data is scarce (as detailed in the next section). We consider this is due to the randomness of U which leads to large variance gradients and hinders the convergence of the model, while we utilize a fixed ratio for optimization thus it is not affected.

When the recognizability critic finishes training, we can obtain the class probability from the estimated density ratio via the sigmoid function, which gives us the following decision rules:

Then the recognizability of representations can be estimated based on the outputs of ˆ ξ via Eq. (4). We find that the recognizability of representations can be used as an indicator of the generalizability and achieve comparable performance to the f -CMI bound, which will be discussed in the next section.

4 Experiments

In this section, we demonstrate the effectiveness of RIB as a training objective to regularize the DNNs and verify the capability of recognizability critic to estimate generalization gap. Code is available at https://github.com/lvyilin/RecogIB.

4.1 Experimental Setup

Datasets. Our experiments mainly conduct on three widelyused datasets: Fashion-MNIST [Xiao et al., 2017], SVHN [Netzer et al., 2011] and CIFAR10 [Krizhevsky and Hinton, 2009]. We also give the results on MNIST and STL10 [Coates et al., 2011] in Appendix C. We adopt the data setting of [Harutyunyan et al., 2021] to enable the calculation and comparison of f -CMI bound. Concretely, each experiment is conducted on k1 draws of the original training set (to form a supersample ˜ z) and k2 draws of the train-val-split (i.e., k1k2 runs in total), which correspond to the randomness of ˜ Z and T, respectively. In all our experiments, k1 = k2 = 5. Unless otherwise stated, the validation set is used as the ghost set. To demonstrate the effectiveness across different data scales, we perform sub-sampling on the training set with different sizes n ∈ {1250, 5000, 20000}.

Implementation details. We use a DNN model composed of a 4-layer CNN (128-128-256-1024) and a 2-layer MLP (1024-512) as the encoder, and use a 4-layer MLP (10241024-1024-1) as the recognizability critic. We train the learning model using Adam optimizer [Kingma and Ba, 2015] with betas of (0.9, 0.999) and train the recognizability critic using SGD with momentum of 0.9 as it is more stable in practice. All learning rates are set to 0.001, and the models are trained 100 epochs using the cosine annealing learning rate scheme with a batch size of 128. The trade-off parameter β is selected from {10-1 , 100 , 101 , 102 } according to the desired regularization strength as discussed later. All the experiments are implemented with PyTorch and performed on eight NVIDIA RTX A4000 GPUs. More experimental details are provided in Appendix B.

4.2 Regularization Effects of RIB

We report the average performance of RIB over k1k2 draws to show its regularization effects on different data scales. We use cross entropy (CE) loss as the baseline. Furthermore, we compare with two common regularization methods: L2 normalization and dropout [Srivastava et al., 2014]. The strength of the L2 normalization is set to 1e-4 and the dropout rate is set to 0.1. We also compare with four popular IB counterparts: VIB [Alemi et al., 2017], NIB [Kolchinsky et al., 2019], DIB [Yu et al., 2021], and PIB [Wang et al., 2022]. All methods impose regularization on the representations, except for PIB which is on the weights. Their regularization strength is determined by the best result of {10-5 , 10-4 , . . . , 101 }. Table 1 shows that RIB consistently outperforms the compared methods across all datasets and all training set sizes. This demonstrates that regularizing the recognizability of representations as well as reducing the recognizable information contributes significantly to improving the generalization of the model. Another point worth mentioning is that the performance of PIB does not outperform VIB and its variants. We consider that this is because the PIB computes the gradient for the overall data only once per epoch, in order to maintain an affordable computational complexity, while representationbased regularization methods compute the gradient for each iteration efficiently, thus provide more fine-grained information for model training. Furthermore, we credit the improvement of RIB over VIB and its variants to the use of the ghost set, which enables the computation of recognizable information, and the reduction of recognizability of representations to facilitate generalization.

Effectiveness of the surrogate loss. We first examine whether optimizing the Bregman divergence of Eq. (8) is better than optimizing Eq. (7) by adversarial training method using Jensen-Shannon divergence [Nowozin et al., 2016]. The risk curves are illustrated in Fig. 2. We find that: i) training RIB in an adversarial manner may produce unstable gradients when the data is scarce thus making the model difficult to converge; ii) with more data, "RIB-adv" can also regularize the model and perform better than the CE baseline; and iii) the RIB optimized by our surrogate loss consistently outperforms the baselines at different data scales, which demonstrates its effectiveness on regularizing the DNNs.

Results of ghosts with different sources. Although the construction of the ghost set is supposed to be performed on a supersample drawn from a single data domain, it is intriguing to investigate whether it can still achieve similar performance with different data sources. We use the CIFAR10 as the training set and construct the ghost from three sources: i) SVHN, distinct from CIFAR10; ii) CIFAR100 [Krizhevsky and Hinton, 2009], similar to CIFAR10 but with more categories and iii) CIFAR10 for comparison. Table 2 shows that i) the more similar the sources are to the training set, the more effective the regularization will be. This is reasonable because recognizing samples from other domains may be too simple thus not provide useful information. More similar sources can provide more fine-grained recognizable information that is of more benefit to the model. ii) Nevertheless, even data from different sources, such as SVHN, can still provide valuable information to improve generalization when training data is scarce (e.g., n = 1250).

Impacts of β. To investigate the impacts of the regularization term of the RIB objective, we train models using the RIB objective with various β. The results on SVHN and CIFAR10 are illustrated in Fig. 3. We can observe that: i) When training data is scarce, the model obtains the best performance at larger β. This is expected since the model tends to over-fit to the data in this case. ii) SVHN is more tolerant of large β compared to CIFAR10. When increasing the β to more than 103 , the model still outperforms the CE baseline in most cases, while too large β may lead to instability in CIFAR10 training. We consider this because the features of SVHN are easier to learn than those of CIFAR10 and are more likely to be over-fitted to irrelevant features, thus regularization brings greater improvement. This provides us with some indications for choosing the best β based on the characteristics of the dataset.

4.3 Estimation of Generalization Gap

To verify the recognizability of representations can be used to indicate the generalization performance, we conduct experiments on different training set sizes n ∈ {1250, 5000, 20000} with the smaller dataset being a subset of the larger dataset. We first train the models on different dataset sizes respectively, and then train the recognizability critics using the representations obtained from the trained models on the smallest data subset respectively. This allows us to evaluate the generalization to the unseen samples outside the smallest subset. Each experiment is repeated k1k2 times to evaluate the f -CMI bound. As illustrated in Fig. 4, we find that i) both the recognizability of representations and the f -CMI bound reflect the generalization to the unseen data, and the recognizability of representations even obtains better estimates in some cases; ii) since the recognizability of representations is a parameterized approximation rather than an upper bound, the risk may sometimes be underestimated as in Fig. 4b. We also visualize the achievable region corresponding to the recognizability of representations, which is obtained by plotting the ROC curve of the score function and its central symmetry about the point (1/2, 1/2). The symmetry of the achievable region is due to the fact that we can construct an opposite test when any test chooses H0 it chooses H1 and vice versa. The visualization results are illustrated in Fig. 5. We find that the better the generalization performance, the smaller the area of achievable regions, which validates the plausibility of our formulation. Since CIFAR10 features are more difficult to learn thus easier to over-fit, it can be seen that a larger area is covered than the other two datasets.

Recognizability Dynamics. To investigate how the recognizability changes during training, we evaluate the recognizability every 5 epochs and plot the dynamics of recognizability as the number of training epochs changes in Fig. 5d. We observe that recognizability can track the generalization gap as expected and eventually converge to around the f -CMI bound. See Appendix C for more results.

5 Conclusions and FutureWork

In this paper, we establish the connection between the recognizability of representations and the f -CMI bound, and propose the RIB to regularize the recognizability of representations through Bregman divergence. We conducted extensive experiments on several commonly used datasets to demonstrate the effectiveness of RIB in regularizing the model and estimating the generalization gap. Future work can investigate whether RIB is also effective on other tasks such as fewshot learning, out-of-distribution detection, domain generalization, etc.

Acknowledgments

This work was partly supported by the National Natural Science Foundation of China under Grant 62176020; the National Key Research and Development Program (2020AAA0106800); the Beijing Natural Science Foundation under Grant L211016; the Fundamental Research Funds for the Central Universities (2019JBZ110); Chinese Academy of Sciences (OEIP-O-202004); Grant ITF MHP/038/20, Grant CRF 8730063, Grant RGC 14300219, 14302920.