An Exact Characterization of the Generalization Error for the Gibbs Algorithm
Year: 2022

Abstract:
Various approaches have been developed to upper bound the generalization error of a supervised learning algorithm. However, existing bounds are often loose and lack of guarantees. As a result, they may fail to characterize the exact generalization ability of a learning algorithm. Our main contribution is an exact characterization of the expected generalization error of the well-known Gibbs algorithm (a.k.a. Gibbs posterior) using symmetrized KL information between the input training samples and the output hypothesis. Our result can be applied to tighten existing expected generalization error and PAC-Bayesian bounds. Our approach is versatile, as it also characterizes the generalization error of the Gibbs algorithm with data-dependent regularizer and that of the Gibbs algorithm in the asymptotic regime, where it converges to the empirical risk minimization algorithm. Of particular relevance, our results highlight the role the symmetrized KL information plays in controlling the generalization error of the Gibbs algorithm.

heading: 1 Introduction
text: Evaluating the generalization error of a learning algorithm is one of the most important challenges in statistical learning theory. Various approaches have been developed [55], including VC dimensionbased bounds [66], algorithmic stability-based bounds [16], algorithmic robustness-based bounds [72], PAC-Bayesian bounds [45], and information-theoretic bounds [71].
However, upper bounds on generalization error may not entirely capture the generalization ability of a learning algorithm. One apparent reason is the tightness issue, some upper bounds [9] can be far away from the true generalization error or even vacuous when evaluated in practice. More importantly, existing upper bounds do not fully characterize all the aspects that could influence the generalization error of a supervised learning problem. For example, VC dimension-based bounds depend only on the hypothesis class, and algorithmic stability-based bounds only exploit the properties of the learning algorithm. As a consequence, both methods fail to capture the fact that generalization error depends strongly on the interplay between the hypothesis class, learning algorithm, and the
⇤Equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
underlying data-generating distribution, as discussed in [71, 73]. This paper overcomes the above limitations by deriving an exact characterization of the generalization error for a specific supervised learning algorithm, namely the Gibbs algorithm.

heading: 1.1 Problem Formulation
text: Let S = {Zi}ni=1 be the training set, where each Zi is defined on the same alphabet Z . Note that Zi is not required to be i.i.d generated from the same data-generating distribution PZ , and we denote the joint distribution of all the training samples as PS . We denote the hypotheses by w 2 W , where W is a hypothesis class. The performance of the hypothesis is measured by a non-negative loss function ` : W ⇥ Z ! R+0 , and we can define the empirical risk and the population risk associated with a given hypothesis w as
LE(w, s) , 1
n
nX
i=1
`(w, zi), and LP (w,PS) , EPS [LE(w, S)], (1)
respectively. A learning algorithm can be modeled as a randomized mapping from the training set S onto an hypothesis W 2 W according to the conditional distribution PW |S . Thus, the expected generalization error quantifying the degree of over-fitting can be written as
gen(PW |S , PS) , EPW,S [LP (W,PS) LE(W,S)], (2) where the expectation is taken over the joint distribution PW,S = PW |S ⌦ PS .
In this paper we focus on the generalization error of the Gibbs algorithm (a.k.a. Gibbs posterior [21]). The (↵,⇡(w), f(w, s))-Gibbs distribution, which was first proposed by [28] in statistical mechanics and further investigated by [35] in information theory, is defined as:
P ↵ W |S(w|s) ,
⇡(w)e ↵f(w,s)
V (s,↵) , ↵ 0, (3)
where ↵ is the inverse temperature, ⇡(w) is an arbitrary prior distribution of W , f(w, s) is energy function, and V (s,↵) , R ⇡(w)e ↵f(w,s)dw is the partition function.
If P and Q are probability measures over space X , and P is absolutely continuous with respect to Q, the Kullback-Leibler (KL) divergence between P and Q is given by D(PkQ) , R X log ⇣ dP dQ ⌘ dP . If Q is also absolutely continuous with respect to P , then the symmetrized KL divergence (a.k.a. Jeffrey’s divergence [36]) is
DSKL(PkQ) , D(PkQ) +D(QkP ). (4)
The mutual information between two random variables X and Y is defined as the KL divergence between the joint distribution and product-of-marginal distribution I(X;Y ) , D(PX,Y kPX ⌦ PY ), or equivalently, the conditional KL divergence between PY |X and PY averaged over PX , D(PY |XkPY |PX) , R X D(PY |X=xkPY )dPX(x). By swapping the role of PX,Y and PX ⌦ PY in mutual information, we get the lautum information introduced by [49], L(X;Y ) , D(PX ⌦ PY kPX,Y ). Finally, the symmetrized KL information between X and Y is given by [6]:
ISKL(X;Y ) , DSKL(PX,Y kPX ⌦ PY ) = I(X;Y ) + L(X;Y ). (5) Throughout the paper, upper-case letters denote random variables (e.g., Z), lower-case letters denote the realizations of random variables (e.g., z), and calligraphic letters denote sets (e.g., Z). All the logarithms are the natural ones, and all the information measure units are nats. N (µ,⌃) denotes the Gaussian distribution with mean µ and covariance matrix ⌃.

heading: 1.2 Contributions
text: The core contribution of this paper (see Theorem 1) is an exact characterization of the expected generalization error for the Gibbs algorithm in terms of the symmetrized KL information between the input training samples S and the output hypothesis W , as follows:
gen(P↵W |S , PS) = ISKL(W ;S)
↵ .
This result highlights the fundamental role of such an information quantity in learning theory that does not appear to have been recognized before. We also discuss some general properties of the symmetrized KL information, which could be used to prove the non-negativity and concavity of the expected generalization error for the Gibbs algorithm.
Building upon this result, we further expand our contributions in various directions:
• In Section 3, we tighten existing expected generalization error bound (see Theorem 2) and PAC-Bayesian bound (see Theorem 3) for Gibbs algorithm under i.i.d and sub-Gaussian assumptions by combining our symmetrized KL information characterization with the existing bounding techniques.
• In Section 4 (Proposition 1 and 2), we show how to use our method to characterize the asymptotic behavior of the generalization error for Gibbs algorithm under large inverse temperature limit ↵ ! 1, where Gibbs algorithm converges to the empirical risk minimization algorithm. Note that existing bounds, such as [39, 52, 71], become vacuous in this regime.
• In Section 5, we characterize the generalization error of the Gibbs algorithm with datadependent regularizer using symmetrized KL information, which provides some insights on how to reduce the generalization error using regularization.

heading: 1.3 Motivations for the Gibbs Algorithm
text: As we discuss below, the choice of Gibbs algorithm is not arbitrary since it arises naturally in many different applications and is sufficiently general to model many learning algorithms used in practice:
Empirical Risk Minimization: The (↵,⇡(w), LE(w, s))-Gibbs algorithm can be viewed as a randomized version of the empirical risk minimization (ERM) algorithm if we specify the energy function f(w, s) = LE(w, s). As the inverse temperature ↵ ! 1, the prior distribution ⇡(w) becomes negligible, and the Gibbs algorithm converges to the standard ERM algorithm.
Information Risk Minimization: The Gibbs algorithm also arises when conditional KL-divergence is used as a regularizer to penalize over-fitting in the information risk minimization framework. In particular, it is shown in [71, 75, 76] that the solution to the following regularized ERM problem
P ? W |S = arg inf
PW |S
✓ EPW,S [LE(W,S)] + 1
↵ D(PW |Sk⇡(W )|PS)
◆ , (6)
corresponds to the (↵,⇡(w), LE(w, s))-Gibbs distribution. The inverse temperature ↵ controls the regularization term and balances between over-fitting and generalization.
PAC-Bayesian Bound: The following upper bound on population risk from [63] holds with probability at least 1 for 0 < < 1, and 0 < < 2 under distribution PS ,
EPW |S=s [LP (W,PS)]  EPW |S=s [LE(W, s)]
1 2 +
D(PW |S=sk⇡(W )) + log( 2 p n )
(1 2 )n . (7)
If we fix , ⇡(w) and optimize over PW |S=s, the distribution that minimizes the PAC-Bayes bound in (7) would be the (n ,⇡(w), LE(w, s))-Gibbs distribution. Similar bounds are proposed in [21, Theorem 1.2.1] and [65, Lemma 10], where optimizing over posterior distribution would result in a Gibbs distribution.
SGLD Algorithm: The Stochastic Gradient Langevin Dynamics (SGLD) can be viewed as the discrete version of the continuous-time Langevin diffusion, and it is defined as follows:
Wk+1 = Wk rLE(Wk, s) +
r 2
↵ ⇣k, k = 0, 1, · · · , (8)
where ⇣k is a standard Gaussian random vector and > 0 is the step size. In [51], it is proved that under some conditions on loss function, the conditional distribution PWk|S induced by SGLD algorithm is close to (↵,⇡(W0), LE(wk, s))-Gibbs distribution in 2-Wasserstein distance for sufficiently large k. Under some conditions on the loss function `(w, z), [22, 42] shows that in the continuous-time Langevin diffusion, the stationary distribution of hypothesis W is the Gibbs distribution.

heading: 1.4 Other Related Work
text: Information-theoretic generalization error bounds: Recently, [58, 71] propose to use the mutual information between the input training set and the output hypothesis to upper bound the expected generalization error. However, those bounds are known not to be tight, and multiple approaches have been proposed to tighten the mutual information-based bound. [19] provides tighter bounds by considering the individual sample mutual information, [10, 11] propose using chaining mutual information, and [30, 31, 62] advocate the conditioning and processing techniques. Informationtheoretic generalization error bounds using other information quantities are also studied, such as, f -divergence [37], ↵-Rényi divergence and maximal leakage [25, 34], Jensen-Shannon divergence [7] and Wasserstein distance [41, 56, 69]. Using rate-distortion theory, [17, 18, 43] provide informationtheoretic generalization error upper bounds for model misspecification and model compression.
PAC-Bayesian generalization error bounds: First proposed by [44, 45, 60], PAC-Bayesian analysis provides high probability bounds on the generalization error in terms of KL divergence between the data-dependent posterior induced by the learning algorithm and a data-free prior that can be chosen arbitrarily. There are multiple ways to generalize the standard PAC-Bayesian bounds, including using different information measures other than the KL divergence [3, 8, 14, 32, 48] and considering datadependent priors (prior depends on the training data) [5, 13, 21, 23, 24, 53] or distribution-dependent priors (prior depends on data-generating distribution) [20, 40, 50, 54]. In [27], a more general PACBayesian framework is proposed, which provides a high probability bound on the convex function of the expected population and empirical risk with respect to the posterior distribution, whereas in [26] the connection between Bayesian inference and PAC-Bayesian theorem is explored by considering Gibbs posterior and negative log loss function.
Generalization error of Gibbs algorithm: Both information-theoretic and PAC-Bayesian approaches have been used to bound the generalization error of the Gibbs algorithm. An informationtheoretic upper bound with a convergence rate of O (↵/n) is provided in [52] for the Gibbs algorithm with bounded loss function, and PAC-Bayesian bounds using a variational approximation of Gibbs posteriors are studied in [4]. [11, Appendix D] provides an upper bound on the excess risk of the Gibbs algorithm under sub-Gaussian assumption. [39] focuses on the excess risk of the Gibbs algorithm and a similar generalization bound with rate of O (↵/n) is provided under sub-Gaussian assumption. Although these bounds are tight in terms of the sample complexity n, they become vacuous when the inverse temperature ↵ ! 1, hence are unable to capture the behaviour of the ERM algorithm.
Our work differs from this body of research in the sense that we provide an exact characterization of generalization error of the Gibbs algorithm in terms of the symmetrized KL information. Our work also further leverages this characterization to tighten the existing expected and PAC-Bayesian generalization error bounds in literature.

heading: 2 Generalization Error of Gibbs Algorithm
text: Our main result, which characterizes the exact expected generalization error of the Gibbs algorithm with prior distribution ⇡(w), is as follows: Theorem 1. For (↵,⇡(w), LE(w, s))-Gibbs algorithm,
P ↵ W |S(w|s) =
⇡(w)e ↵LE(w,s)
V (s,↵) , ↵ > 0, (9)
the expected generalization error is given by
gen(P↵W |S , PS) = ISKL(W ;S)
↵ . (10)
Sketch of Proof: It can be shown that the symmetrized KL information can be written as ISKL(W ;S) = EPW,S [log(P↵W |S)] EPW⌦PS [log(P↵W |S)]. (11)
Just like the generalization error, the above expression is the difference between the expectations of the same function evaluated under the joint distribution and the product-of-marginal distribution. Note that PW,S and PW ⌦ PS share the same marginal distribution, we have EPW,S [log ⇡(W )] =
EPW [log ⇡(W )], and EPW,S [log V (S,↵)] = EPS [log V (S,↵)]. Then, combining (9) with (11) completes the proof. More details together with the full proof are provided in Appendix B.1.
To the best of our knowledge, this is the first exact characterization of the expected generalization error for the Gibbs algorithm. Note that Theorem 1 only assumes that the loss function is non-negative, and it holds even for non-i.i.d training samples.
In Section 2.1, we discuss some general properties of the expected generalization error that can be learned directly from the properties of symmetrized KL information. In Section 2.2, we provide a mean estimation example to show that the symmetrized KL information can be computed exactly for squared loss with Gaussian prior.

heading: 2.1 General Properties
text: By Theorem 1, some basic properties of the expected generalization error, including non-negativity and concavity, can be proved directly from the properties of symmetrized KL information.
The non-negativity of the expected generalization error, i.e., gen(P↵W |S , PS) 0, follows by the non-negativity of the symmetrized KL information. Note that the non-negativity result could also be proved using [39, Appendix A.2] under much more stringent assumptions, including i.i.d samples and a sub-Gaussian loss function.
It is shown in [6] that the symmetrized KL information ISKL(X;Y ) is a concave function of PX for fixed PY |X , and a convex function of PY |X for fixed PX . Thus, we have the following corollary. Corollary 1. For a fixed (↵,⇡(w), LE(w, s))-Gibbs algorithm P↵W |S , the expected generalization error gen(P↵W |S , PS) is a concave function of PS .
The concavity of the generalization error for the Gibbs algorithm P↵W |S can be immediately used to explain why training a model by mixing multiple datasets from different domains leads to poor generalization. Suppose that the data-generating distribution is domain-dependent, i.e., there exists a random variable D, such that D $ S $ W holds. Then, PS = EPD [PS|D] can be viewed as the mixture of the data-generating distribution across all domains. From Corollary 1 and Jensen’s inequality, we have
gen(P↵W |S , PS) EPD ⇥ gen(P↵W |S , PS|D) ⇤ , (12)
which shows that the generalization error of Gibbs algorithm achieved with the mixture distribution PS is larger than the averaged generalization error for each PS|D.
More discussions about other properties of symmetrized KL divergence, including data processing inequality ( symmetrized KL divergence is an f -divergence), variational representation, chain rule, and their implications in learning problems are provided in Appendix B.2.

heading: 2.2 Example: Mean Estimation
text: We now consider a simple learning problem, where the symmetrized KL information can be computed exactly, to demonstrate the usefulness of Theorem 1. All details are provided in Appendix B.3.
Consider the problem of learning the mean µ 2 Rd of a random vector Z using n i.i.d training samples S = {Zi}ni=1. We assume that the covariance matrix of Z satisfies ⌃Z = 2ZId with unknown 2 Z . We adopt the mean-squared loss `(w, z) = kz wk22, and assume a Gaussian prior for the mean ⇡(w) = N (µ0, 20Id). If we set inverse-temperature ↵ = n 2 2 , then the ( n 2 2 ,N (µ0, 2 0Id), LE(w, s))-Gibbs algorithm is given by the following posterior distribution [47],
P ↵ W |S(w|Z
n) ⇠ N ⇣ 2 1
2 0
µ0 + 2 1
2
nX
i=1
Zi, 2 1Id ⌘ , with 21 =
2 0 2
n 2 0 +
2 . (13)
Since P↵W |S is Gaussian, the mutual information and lautum information are given by
I(S;W ) = nd
2 0 2 Z
2(n 20 + 2) 2
D PW kN (µW , 21Id) , (14)
L(S;W ) = nd
2 0 2 Z
2(n 20 + 2) 2
+D PW kN (µW , 21Id)), with µW =
2 1 2 0 µ0 + n 2 1 2 µ. (15)
For additive Gaussian channel PW |S , it is well known that Gaussian input distribution (which also gives a Gaussian output distribution PW ) maximizes the mutual information under a second-order moment constraint. As we can see from the above expressions, the opposite is true for lautum information. In addition, symmetrized KL information ISKL(W ;S) is independent of the distribution of PZ , as long as ⌃Z = 2ZId.
From Theorem 1, the generalization error of this algorithm can be computed exactly as:
gen(P↵W |S , PS) = ISKL(W ;S)
↵ =
2d 20 2 Z
n 2 0 +
2 =
2d 20 2 Z
n( 20 + 1 2↵ )
, (16)
which has the decay rate of O (1/n). As a comparison, the individual sample mutual information (ISMI) bound from [19], which is shown to be tighter than the mutual information-based bound in [71, Theorem 1], gives a sub-optimal bound with order O (1/ p n), as n ! 1, (see Appendix B.4).

heading: 3 Tighter Generalization Error Upper Bounds
text: In this section, we show that by combining Theorem 1 with existing information-theoretic and PAC-Bayesian approaches, we can provide tighter generalization error upper bounds for the Gibbs algorithm. These bounds quantify how the generalization error of the Gibbs algorithm depends on the number of samples n, and are useful when directly evaluating the symmetrized KL information is hard.

heading: 3.1 Expected Generalization Error Upper Bound
text: The following upper bound on the expected generalization error for the Gibbs algorithm can be obtained by combining our Theorem 1 with the information-theoretic bound proposed in [71] under i.i.d and sub-Gaussian assumptions. Theorem 2. (proved in Appendix C.1) Suppose that the training samples S = {Zi}ni=1 are i.i.d generated from the distribution PZ , and the non-negative loss function `(w,Z) is -sub-Gaussian on the left-tail ⇤ under distribution PZ for all w 2 W . If we further assume CE  L(W ;S) I(W ;S) for some CE 0, then for the (↵,⇡(w), LE(w, s))-Gibbs algorithm, we have
0  gen(P↵W |S , PS)  2 2↵
(1 + CE)n . (17)
Theorem 2 establishes the convergence rate O(↵/n) of the generalization error of Gibbs algorithm with i.i.d training samples, and suggests that a smaller inverse temperature ↵ leads to a tighter upper bound. Note that all the -sub-Gaussian loss functions are also -sub-Gaussian on the left-tail under the same distribution (loss function in Section 2.2 is sub-Gaussian on the left-tail under PZ , but not sub-Gaussian). Therefore, our result also applies to any bounded loss function ` : W ⇥ Z ! [a, b], since bounded functions are ( b a2 )-sub-Gaussian. Remark 1 (Previous Results). Using the fact that Gibbs algorithm is differentially private [46] for bounded loss functions ` 2 [0, 1], directly applying [71, Theorem 1] gives a sub-optimal bound |gen(P↵W |S , PS)|  p ↵ n . By further exploring the bounded loss assumption using Hoeffding’s lemma, a tighter upper bound |gen(P↵W |S , PS)|  ↵ 2n is obtained in [52], which has the similar decay rate order of O (↵/n). In [39, Theorem 1], the upper bound gen(P↵W |S , PS)  4 2↵ n is derived with a different assumption, i.e., `(W, z) is -sub-Gaussian under Gibbs algorithm P↵W |S . In Theorem 2, we assume the loss function is -sub-Gaussian on left-tail under data-generating distribution PZ for all w 2 W , which is more general as we discussed above. Our upper bound is also improved by a factor of 12(1+CE) compared to the result in [39].
Remark 2 (Choice of CE). Since L(W ;S) > 0 when I(W ;S) > 0, setting CE = 0 is always valid in Theorem 2, which gives gen(P↵W |S , PS)  2 2↵ n . As shown in [49, Theorem 15], L(S;W )
⇤A random variable X is -sub-Gaussian if logE[e (X EX)]  2 22 , 8 2 R, and X is -sub-Gaussian on the left-tail if logE[e (X EX)]  2 22 , 8  0.
I(S;W ) holds for any Gaussian channel PW |S . In addition, it is discussed in [49, Example 1], if either the entropy of training S or the hypothesis W is small, I(S;W ) would be smaller than L(S;W ) (as it is not upper-bounded by the entropy), which implies that the lautum information term is not negligible in general.
We extend Theorem 2 by considering other types of tail behavior including sub-Gamma and subExponential on left-tail in Appendix C.2.

heading: 3.2 PAC-Bayesian Upper Bound
text: As discussed in Section 1.4, the prior distribution used in PAC-Bayesian bounds is different from the prior in Gibbs algorithm, since the former priors can be chosen arbitrarily to tighten the generalization error bound. In this section, we provide a tighter PAC-Bayesian bound based on the symmetrized KL divergence, which is inspired by the distribution-dependent PAC-Bayesian bound proposed in [40] using (↵,⇡(w), LP (w,PS))-Gibbs distribution as the PAC-Bayesian prior.
As the data-generating distribution PS is unknown in practice, we consider the (↵,⇡(w), LP (w,PS0))-Gibbs distribution in the following discussion, where PS0 is an arbitrary data-generating distribution. Since (↵,⇡(w), LP (w,PS0))-Gibbs distribution is independent of the samples S and only depends on the population risk LP (w,PS0), we can denote it as P ↵,L0P W .
By exploiting the connection between the symmetrized KL divergence DSKL P ↵ W |S=s
P↵,L 0 P
W
and
the KL divergence term D P ↵ W |S=s
P↵,L 0 P
W
in the PAC-Bayesian bound from [40], the following
PAC-Bayesian bound can be obtained under i.i.d and sub-Gaussian assumptions. Theorem 3. (proved in Appendix D) Suppose that the training samples S = {Zi}ni=1 are i.i.d generated from the distribution PZ , and the non-negative loss function `(w,Z) is -sub-Gaussian under data-generating distribution PZ for all w 2 W . If we use the (↵,⇡(w), LP (w,PS0))-Gibbs distribution as the PAC-Bayesian prior, where PS0 is an arbitrary chosen (and known) distribution, the following upper bound holds for the generalization error of (↵,⇡(w), LE(w, s))-Gibbs algorithm with probability at least 1 2 , 0 < < 12 under distribution PS , EP↵
W |S=s [LP (W,PS) LE(W, s)]
 2 2↵
(1 + CP (s))n + 2
s 2↵
(1 + CP (s))n
⇣ 4 p 2 2D(PZ0kPZ) + ✏ ⌘ + ✏2,
where ✏ , 4 q
2 2 log(1/ ) n , and CP (s)  D P
↵,L0P W P↵W |S=s
D P↵ W |S=s
P↵,L 0 P
W
for some CP (s) 0.
Remark 3 (Previous Result). We could recover the distribution-dependent bound in [40, Theorem 6] by setting PZ0 = PZ , choosing a bounded loss function in [0, 1] and CP (s) = 0 in our Theorem 3. Note that multiple terms in our upper bound in Theorem 3 are tightened by a factor of 1/(1+CP (s)), and we also consider -sub-Gaussian loss functions. Remark 4 (Choice of CP (s)). Since the distribution PZ0 can be set arbitrarily, the prior distribution P ↵,L0P W is accessible. Then, we can set CP (s) = D P ↵,L0P W P↵W |S=s /D P ↵ W |S=s P↵,L 0 P W to tighten the bound, as it can be computed exactly using the training set.

heading: 4 Asymptotic Behavior of Generalization Error for Gibbs Algorithm
text: In this section, we consider the asymptotic behavior of the generalization error for Gibbs algorithm as the inverse temperature ↵ ! 1. Note that the upper bounds obtained in the previous section, as well as the ones in the literature, have the order O(↵n ), which becomes vacuous in this regime. However, it is known that the Gibbs algorithm will converge to ERM as ↵ ! 1, which has finite generalization error with bounded loss function. To resolve this issue, we provide an exact characterization of the generalization error in this regime using Theorem 1.
It is shown in [12, 33] that the asymptotic behavior of the Gibbs algorithm depends on the number of minimizers for the empirical risk, so we consider the single-well case and multiple-well case separately.
Single-well case: In this case, there exists a unique W ⇤(S) that minimizes the empirical risk, i.e., W
⇤(S) = argmin w2W LE(w, S). (18)
It is shown in [33] that if H⇤(S) , r2wLE(w, S) w=W⇤(S) is not singular, then P↵W |S ! N (W ⇤(S), 1↵H
⇤(S) 1) in distribution. Thus, the symmetrized KL information in Theorem 1 can be evaluated using this Gaussian approximation, which gives the following result. Proposition 1. (proved in Appendix E.1) In the single-well case, if the Hessian matrix H⇤(S) is not singular, then the generalization error of the (1,⇡(w), LE(w, s))-Gibbs algorithm is
gen(P1W |S , PS) = E W,S ⇥1 2 W > H ⇤(S)W ⇤
(19)
+ EPS h (W ⇤(S) E[W ⇤(S)])>(H⇤(S)W ⇤(S) E[H⇤(S)W ⇤(S)]) i ,
where E W,S [f(W,S)] , EPW⌦PS [f(W,S)] EPW,S [f(W,S)]. Proposition 1 shows that the generalization error of the Gibbs algorithm in the limiting regime ↵ ! 1 highly depends on the landscape of the empirical risk function.
As an example, we use Proposition 1 to obtain the generalization error of the maximum likelihood estimates (MLE) in the asymptotic regime n ! 1. More specifically, suppose that we have n i.i.d. training samples generated from the distribution PZ , and we want to fit the training data with a parametric distribution family {f(zi|w)}ni=1, where w 2 W ⇢ Rd denotes the parameter. Here, the true data-generating distribution may not belong to the parametric family, i.e., PZ 6= f(·|w) for w 2 W . If we use the log-loss `(w, z) = log f(z|w) in the Gibbs algorithm, as ↵ ! 1, it converges to the ERM algorithm, which is equivalent to MLE, i.e.,
W ⇤(S) = ŴML , argmax
w2W
nX
i=1
log f(Zi|w). (20)
As n ! 1, under regularization conditions (details in Appendix E.2) which guarantee that W ⇤(S) is unique, the asymptotic normality of the MLE [64] states that the distribution of ŴML converges to
N (w⇤, 1
n J(w⇤) 1I(w⇤)J(w⇤) 1), with w⇤ , argmin w2W D(PZkf(·|w)),
J(w) , EZ ⇥ r 2 w log f(Z|w) ⇤ and I(w) , EZ ⇥ rw log f(Z|w)rw log f(Z|w) >⇤ .
In addition, the Hessian matrix H⇤(S) ! J(w⇤) as n ! 1, which is independent of the training samples S. Thus, E W,S [ 12W > H ⇤(S)W ] = 0, and Proposition 1 gives
gen(P1W |S , PS) = tr(I(w⇤)J(w⇤) 1)
n . (21)
When the true model is in the parametric family PZ = f(·|w⇤), we have I(w⇤) = J(w⇤) and the above expression reduces to gen(P1W |S , PZ) = d n , which corresponds to the well-known Akaike information criterion (AIC) [2] used in MLE model selection.
Multiple-well case: In this case, there exist M distinct W ⇤u (S) such that W
⇤ u (S) 2 argmin
w2W LE(w, S), u 2 {1, · · · ,M}, (22)
where M is a fixed constant, and all the minimizers W ⇤u (S) are isolated, meaning that a sufficiently small neighborhood of each W ⇤u (S) contains a unique minimum.
In this multiple-well case, it is shown in [12] that the the Gibbs algorithm can be approximated by a Gaussian mixture, as long as H⇤u(S) , r2wLE(w, S)
w=W⇤u (S) is not singular for all u 2 {1, · · · ,M}. However, there is no closed form for the symmetrized KL information for Gaussian mixtures. Thus, we provide the following upper bound of the generalization error by evaluating Theorem 1 under the assumption that ⇡(W ) is a uniform distribution over W . Proposition 2. (proved in Appendix E.1) If we assume that ⇡(W ) is a uniform distribution over W , and the Hessian matrices H⇤u(S) are not singular for all u 2 {1, · · · ,M}, then the generalization error of the (1,⇡(w), LE(w, s))-Gibbs algorithm in the multiple-well case can be bounded as
gen(P1W |S , PS)  1
M
MX
u=1
 E Wu,S ⇥1 2 W > u H ⇤ u(S)Wu ⇤
+ EPS h (W ⇤u (S) E[W ⇤u (S)])>Hu(W ⇤u (S) E[W ⇤u (S)]) i . (23)
Comparing with Proposition 1, Proposition 2 shows that the global generalization error in the multiplewell case can be upper bounded by the mean of the generalization errors achieved by each local minimizer. Remark 5. In [39], a similar Gaussian approximation technique is used to bound the excess risk of Gibbs algorithm in both single-well and multiple-well cases. However, their result is based on a loose generalization error bound with the order O(↵n ). Thus, our method can also be used to obtain a tighter characterization of the excess risk for the Gibbs algorithm.
In Appendix E.3, we consider a slightly different asymptotic regime, where the Gibbs algorithm converges to the Bayesian posterior instead of ERM. A similar result as in (21) can be obtained from Bernstein–von–Mises theorem [38] and the asymptotic normality of the MLE.

heading: 5 Regularized Gibbs Algorithm
text: In this section, we show how regularization will influence the generalization error of the Gibbs algorithm. Our definition of the regularizer is more general compared to the standard data-independent regularizer, as it may also depend on the training samples. There are many applications of such data-dependent regularization in the literature—e.g., data-dependent spectral norm regularization is proposed in [57], `1 regularizer over data-dependent hypothesis space is studied in [70] and dropout is modeled as data-dependent `2 regularization in [68].
In the following proposition, we consider the Gibbs algorithm with a regularization term R : W ⇥ Z
n ! R+0 and characterize the generalization error of this (↵,⇡(w), LE(w, s) + R(w, s))-Gibbs
algorithm, which is the solution of the following regularized ERM problem:
P ? W |S = arg inf
PW |S
✓ EPW,S [LE(W,S) + R(W,S)] + 1
↵ D(PW |Sk⇡(W )|PS)
◆ , (24)
where 0 controls the regularization term. Proposition 3. (proved in Appendix F.1) For (↵,⇡(w), LE(w, s) + R(w, s))-Gibbs algorithm, its expected generalization error is given by
gen(P↵W |S , PS) = ISKL(W ;S)
↵ E W,S [R(W,S)], (25)
where E W,S [R(W,S)] = EPW⌦PS [R(W,S)] EPW,S [R(W,S)].
Proposition 3 holds for non-i.i.d samples and any non-negative loss function, and it shows that to improve the generalization ability of the Gibbs algorithm, the data-dependent regularizer needs to 1) minimize the symmetrized KL information ISKL(W ;S) and 2) maximize the E W,S [R(W,S)] term which corresponds to a “generalization error” defined with the regularization term R(W,S). Remark 6. If the regularizer is independent of the data, i.e., R(w, s) = R(w), we have E W,S [R(W,S)] = 0, and Proposition 3 gives gen(P↵W |S , PS) = ISKL(W ;S) ↵ , which implies that the data-independent regularizer needs to improve the generalization ability of learning algorithm by reducing the symmetrized KL information ISKL(W ;S).
Inspired by the data-dependent regularizer proposed in [61] for support vector machines, we consider a similar data-dependent `2-regularizer in the following proposition. Proposition 4. (proved in Appendix F.1) Suppose that we adopt the `2-regularizer R(w, s) = kw T (s)k22, where T (·) is an arbitrary deterministic function T : Zn ! W . Then, the expected generalization error of (↵,⇡(w), LE(w, s) + R(w, s))-Gibbs algorithm is
gen(P↵W |S , PS) = ISKL(W ;S)
↵ tr Cov[W,T (S)] , (26)
where Cov[W,T (S)] denotes the covariance matrix between W and T (S).
Our result suggests that to reduce the generalization error with data-dependent `2-regularizer, the function T (S) should be chosen in a way, such that the term tr(Cov[W,T (S)]) is maximized. One way is to leave a part of the training set and learn the T (S) function. Note that similar idea has been explored in the development of PAC-Bayesian bound with data-dependent prior [5]. More discussions and results about data-dependent regularizer are provided in Appendix F.2.

heading: 6 Conclusion
text: We provide an exact characterization of the generalization error for the Gibbs algorithm using symmetrized KL information. We demonstrate the power and versatility of our approach in multiple applications, including tightening expected generalization error and PAC-Bayesian bounds, characterizing the behaviors of the Gibbs algorithm with large inverse temperature and the regularized Gibbs algorithm.
This work motivates further investigation of the Gibbs algorithm in a variety of settings, including extending our results to characterize the generalization ability of an over-parameterized Gibbs algorithm, which could potentially provide more understanding of the generalization ability for deep learning.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their valuable feedback, which helped us to improve the paper greatly. Gholamali Aminian is supported by the Royal Society Newton International Fellowship, grant no. NIF\R1 \192656. Yuheng Bu is supported, in part, by NSF under Grant CCF-1717610 and by the MIT-IBM Watson AI Lab.

Review summaries:
This paper obtains an exact characterization of the expected generalization error of the celebrated Gibbs distribution (algorithm) using symmetrized KL information between the input training samples and the output hypothesis. The paper then obtains tighter generalization error bounds for the Gibbs distribution and studies the asymptotic behavior of that distribution when the temperature tends to zero. The effect of regularization on the generalization error of the Gibbs distribution is also studied.

This paper shows the generalization error (actually, the population loss minus the empirical  loss) of the Gibbs algorithm is the symmetric KL divergence between the sample distribution and the Gibbs distribution on hypotheses divided by the inverse temperature.  This formulation is then used to tighten existing generalization bounds on the Gibbs algorithm in several settings.  It allows for improved bounds as the inverse temperature $\alpha$ goes to infinity (and the Gibbs algorithm approaches empirical risk minimization), as existing bounds on the Gibbs algorithm seem to behave as $O( \alpha / n)$.   The author's also consider regularized Gibbs algorithms and use their formulation to deduce when the regularizer will be beneficial. 

This paper is concerned with characterizing (and more generally deriving upper bounds on)  the expected generalization error (as defined at (2)) for the Gibbs algorithm. After giving some motivation for considering the Gibbs algorithm, the authors state their key result: an exact characterization of the expected risk of the algorithm, in terms of the symmetrized KL information between training sample and model,  and the temperature parameter of the Gibbs distribution. This allows the authors to recover some known upper bounds under  iid sampling and bounded loss function, as well as deriving a new upper bound  when the loss function enjoys well-behaved tails  (sub-gaussian, sub-exponential, sub-gamma, but possibly unbounded). This approach also yields a PAC-Bayes upper bound, and an analysis of the behavior of the expected generalization error when the temperature parameter shoots to infinity.