An Exact Characterization of the Generalization Error for the Gibbs Algorithm
Authors: Gholamali Aminian
Yuheng Bu
Laura Toni
Miguel R. D. Rodrigues
Gregory Wornell
Venue: NeurIPS 2021 Poster (2021)
Keywords: Gibbs algorithm
generalization error
information-theoretic bounds
PAC-Bayesian bounds

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.

An Exact Characterization of the Generalization Error for the Gibbs Algorithm
Gholamali Aminian University College London g. aminian @ucl. uk
Yuheng Bu Massachusetts Institute of Technology buyuheng@mit, edu
Laura Toni University College London toni@ucl.ac.....
Miguel Rodrigues University College London
m. www.roigguuuuu.... ac uk
Gregory Wornell
Massachusetts Institute of Technology gwwêmit. edu
Abstract
Various approaches have been developed to upper bound the generalization error of 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 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 KI. information between the input training samples and the output hypothesis. Our result 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 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.
Introduction
Evaluating the generalization error of learning algorithm is of the most important challenges in statistical learning theory. Various approaches have been developed [55], including VC dimension- based bounds [66], algorithmic stability-basee bounds [16], algorithmic robustness-based bounds [72], PPA--Baysiie bounds [45], and information iefommation-thhoretiic bounds [71].
However, upper bounds generalization error may not entirely capture the generalization ability of learning algorithm. One apparent reason is the tightness issue, some upper bounds [9] can 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 supervised learning problem. For example, VC dimension-based bounds depend only on the hypothesis class, and algorithmic stability- bounds only exploit the properties of the learning algorithm. As consequence, both methods fail to capture the fact that generalization error depends strongly on the interplay between the hypothesis class, learning algorithm, and the
Eqqual contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

underlying data-gent gentratinn distribution, as discussed in [71, 73]. This paper overcomes the above limitations by deriving an exact characterization the generalization error for specific supervised learning algorithm, namely the Gibbs algorithm.
1.1 Problem Formulation
Let S (= be the training set, where each Z; is defined on the same alphabet 2. Note that Z 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, where W is a hypothesis class. The performance of the hypothesis is measured by non-negative loss function
W + ED and we can define the empirical risk and the population risk associated with given hypothesis w as
LE(w,s) s) - Σ ((w,22) and Ps) 2 Eps [L S)], 1=1
(1)
respectively. A learning algorithm can be modeled randomized mapping from the training set onto an hypothesis W W according to the conditional distribution Pwis- Thus, the expected generalization quantifying the degree of over-fitting can be written
gen(Pwis: P's) (W,.ssLp(W,W - LeW,
(2)
where the expectation is taken over the joint distribution Pw.s Pwis @ Ps.
In this paper we focus on the generalization error of the Gibbs algorithm (a.k.a. Gibbs posterior [21]). The (a, π (w), fw,, s)) - distribution, which was first proposed by [28] in statistical mechanics and further investigated by [35] in information theory, is defined as:
pa Wis((lls) (w))--ar (w)())))
a a
(3)
V(s,a)
where a is the inverse temperature, π (w) is an arbitrary prior distribution of W, f(w,, 8) is energy function, and Vis, a.) ((w))-af(w;)) 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(PI)) & fx log
dP
dP.
aQ
If Q is also absolutely continuous with respect P, then the symmetrized KL divergence (a.k.a. Jeffrey's divergence [36]) is
DSKL (PIlQ) & D(PII)) P)Q
(4)
The mutual information between two random variables X and is defined as the KL divergence between the joint distribution and product-of-margnnal distribution [(X; Y) & D(Px,y [| & Py), or equivalently, the conditional KL divergence between Pyxx and Py averaged over Px. D(Pyix PPx A Jx PI
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 & Px,)) Finally, the symmetrized KL information between X and Y is given by [6]:
(5) Throughout the paper, upper-case letters denote random variables (e.g., 2), 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 (p, Σ)) denotes the Gaussian distribution with mean f and covariance matrix Σ.
(x; (Px, ||xx & Py) I(X; + L(X:Y).
1.2 Contributions
The core contribution of this paper (see Theorem 1) is 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 PW 5. Ps) ISKL. (W:S)

---

This result highlights the fundamental role of such an information quantity in learning theory that does not appear have been recognized before. We also discuss some general properties of the symmetrized KI. 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 (Proposition and 2), show how to our method characterize the asymptotic behavior of the generalization error for Gibbs algorithm under large inverse tem- perature limit a - 3o, where Gibbs algorithm converges 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 data- dependent regularizer using symmetrized KL information, which provides some insights on how to reduce the generalization error using regularization.
1.3 Motivations for the Gibbs Algorithm
As we discuss below, the choice of Gibbs algorithm is not arbitrary since it arises naturally in many different applications and is sufficiently general model many learning algorithms used in practice:
The (a, T(w), Læ(w, s) Giibbs algorithm can be viewed as a ran- domized version of the empirical risk minimization (ERM) algorithm if we specify the energy function fww, 8) = Lg(w, s). As the inverse temperature a + oo, the prior distribution T(w) becomes negligible, and the Gibbs algorithm converges to the standard ERM algorithm.
Empirical Risk Minimization:
Information Risk Minimization:
The Gibbs algorithm also arises when conditional KL-divergence used 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
PW Pis arg inf
(
D(Pwis (P())ss((W)))Ps)
Pwis
corresponds to the (a, (w), LE(w, --bbbs distribution. The inverse temperature a 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 proba- bility at least 1 - 5 for 0 < 8 < 1, and 0 < A < 2 under distribution Ps.
EP s- LL s) D(Pwis =
(EWis==s|[((C [[])[]])))))))))))]])())())))[ + log( 2ym 8
E Ewwis (W, Ps)]
X(1 2 n
If fix X, (w)) and optimize over Pwis os the distribution that minimizes the PAC-Bayes bound in (7) would be the (nλ, T(w), Lgw,, (edw,))))GGbbbl 3)bbbs distribution. Similar bounds proposed in [21, Theorem 1.2.1] and [65, Lemma 10], where optimizing over posterior distribution would result in Gibbs distribution.
SGLD Algorithm: The Stochastic Gradient Langevin Dynamics (SGLD) can be viewed as the discrete version of the continuous-ting Langevin diffusion, and it is defined as follows:
23
Wa = WE- 3VLE 8) +
CR. =
where Ça a standard Gaussian random vector and > 0 is the step size. [51], it is proved that un- der some conditions loss function, the conditional distribution PwLs induced by SGLD algorithm is close to (ax, π (Wo), [E(.,, -G)bbs distribution in 2- 2-Wasserstein distance for sufficiently large k. Under some conditions on the loss function E(w,, z), [22, 42] shows that in the continuous-tin Langevin diffusion, the stationary distribution of hypothesis W is the Gibbs distribution.

---

1.4 Other Related Work
Information-theorriic generalization error bounds: Recently, [58, 71] propose 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-basee 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. Information- theoretic generalization error bounds using other information quantities are also studied, such as, f-divergence [37], a- cé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 information- theoretic 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- AAC-Bayesian bounds, including using different information measures other than the KI. divergence [3, 14, 32, 48] and considering data- dependent priors (prior depends on the training data) [5, 13, 21, 23, 24, 53] or distribution distribution-dependee dependent priors (prior depends on data-generating distribution) [20, 40, 50, 54J. In [27], a more general PAC- Bayesian framework is proposed, which provides 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- -aC-Bsysiinn theorem is explored by considering Gibbs posterior and negative log loss function.
Generalization error of Gibbs algorithm: Both information -hheorttiiit and PAC- AAC-Bayesian ap- proaches have been used bound the generalization error of the Gibbs algorithm. An information- theoretic upper bound with a convergence rate of O (a/ / is provided in [52] for the Gibbs algorithm with bounded loss function, and PAC--ayesian bounds using a variational approximation
Gibbs upper bound on the excess risk of the Gibbs algorithm under sub-Gaussian assumption. [39] focuses on the excess risk the Gibbs algorithm and a similar generalization bound with rate of O (a/n) is provided under sub-Gaussian assumption. Although these bounds are tight in terms the sample complexity n, they become vacuous when the inverse temperature ERM algorithm.
posteriors are studied in [4]. [11, Appendix D] provides
oc, hence are unable to capture the behaviour of the
Our work differs from this body of research in the sense that we provide 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.
Generalization Error of Gibbs Algorithm
Our main result, which characterizes the exact expected generalization error of the Gibbs algorithm with prior distribution x(w), is as follows:
Theorem 1. For (a, Tww), Lg(w, s))-Gibbs algorithm,
Pi ( =(w)e-aLan aLL(w,,)
a O,
(9)
V(s,a)
the expected generalization error is given by
ISKL (W;:)
gen
po w: Ps)
(10)
Sketch of Proof: It can be shown that the symmetrized KL information can be written as
ISKL (W: :) Erw. [log( (PW]s)] Erw & [log(WW)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-margine distribution. Note that Pw.s and Pw @ Ps share the same marginal distribution, we have Epw. (lo.sllog π (W))

---

EPw [log T (W),, and EPw.s llgg ((S, a)] = Eps [log (SS, a)]. 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 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 KI. information. In Section 2.2, we provide a mean estimation example to show that the symmetrized KI. information can be computed exactly for squared loss with Gaussian prior.
2.1 General Properties
By Theorem 1, some basic properties of the expected generalization error, including non-negativity and concavity, can proved directly from the properties of symmetrized KL information.
The non-negativity of the expected generalization error, i.e., gen( WIs+ Ps) 2 O, follows by the non-negativity of the symmetrized KI. 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 uub-Gaussian loss function.
It is shown in [6] that the symmetrized KL information ISKI. (X; Y) is a concave function of Px for fixed Py Py|x. and a convex function of PY|x for fixed Px. Thus, we have the following corollary. Corollary 1. For a fixed (a, T(w), LE (E s))-Gibbs algorithm wis the expected generalization error gen Pw w Ps) is concave fumction of Ps-
The concavity of the generalization error for the Gibbs algorithm Wis can be immediately used to explain why training 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 random variable D, such that D ++ S ++ W holds. Then, Ps = Ep, [Ptp] can be viewed as the mixture of the data-generating distribution across all domains. From Corollary and Jensen's 's inequality, we have
gen Pi Ps) 2 Er, gen(Piin PsID)].
(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 PsIp.
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.
2.2 Example: Mean Estimation
We now consider 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 E IR of a random vector Z using i.i.d training samples { [z _ We assume that the covariance matrix of satisfies Σz o2 Ia with unknown ož We adopt the mean-squared loss E(w, z) = =|| -w|( w|/3. and assume a Gaussian prior for the mean π (w) = N ((un, Ia).). we set inverse-temperatuue a = 2Øz, then the NN, IīIa), LE(w, s))-Gibbs algorithm is given by the following posterior distribution [47].
of Σ Ze, oTTa) with of no o² 0²
Piis Piis(wlZ") ~ N
(13)
i=1
Since p is Gaussian, the mutual information and lautum information are given by
2doãoz I(S:W) 2(no, + =Z)
(14)
ndo3o2
of uo σ² n.
no?
L(S:W) 2(noz 02)00 + D(PWINN(Hw, with μo
(15)
of
5

---

For additive Gaussian channel Pwis, 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. addition, symmetrized KI. information [sKI(W;; S) is independent of the distribution of Pz, as long as Σg = =02 Ta-
From Theorem I, the generalization error of this algorithm can be computed exactly as:
gen(P Ps) (W:))
2 20 no 0² π + 2a
(16)
a
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-base bound in
[71, Theorem I]. gives sub-optimal bound with order (1/vn). as -> so, (see Appendix B.4).
3 Tighter Generalization Error Upper Bounds
In this section, we show that by combining Theorem 1 with existing information-theoredt 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.
3.1 Expected Generalization Error Upper Bound
The following upper bound on the expected generalization error for the Gibbs algorithm can be obtained by combining our Theorem I with the information-theoretie bound proposed in [71] under i..d and sub- Gaussian assumptions.
Theorem 2. (proved in Appendix C.I) Suppose that the training samples S {Z]]= are i.i.d
generated from the distribution Pz, and the non-negative loss function E(w, Z) is --sub-Gaussian
on the left-tail* under distribution Pz for all W. If we further assume Cg T(W:5) for some
L(W:S)
Ce 2 0, then for the (ax, (()), LE(W, 3))-Gib algorithm, we have
20²0
0 S gen PWIs: Ps) S (1+Cg))
(17)
Theorem 2 establishes the convergence rate ((a/n) of the generalization error of Gibbs algorithm with i.i.d training samples, and suggests that smaller inverse temperature a leads to tighter upper bound. Note that all the r-sub-Gaussian loss functions are also the same distribution (loss function in Section 2.2 is sub-Ga Gaussian on the left-tail under Pz. but not sub-Gaussian) Therefore, our result also applies to any bounded loss function é: W x Z + [a, b). since bounded functions are ( (A==))-ubb-Gaae Jsub-Gaussian.
on the left-tail under
Remark (Previous Results). Using the fact that Gibbs algorithm is differentially private [46] for bounded loss functions é. E [0, 1), directly applying [71, Theorem 1] gives sub-optimal bound Wis: Ps)l S T By further exploring the bounded loss assumption using Hoeffding's 's lemma, (gen(Pa a lighter upper bound [gen( PW|s: Ps)) S
a is obtained in [52], which has the similar decay rate 2n
(e P order of O (a//n). In (39, Theorem 1], the upper bound gen( Wis+ Ps) < 4a2a is derived with different assumption, i.e., E(W,2) 2) is a-sub-Gauud Gaussian under Gibbs algorithm Pat Pw1s In Theorem 2, we assume the loss function is a-sub- Gaussian on left-tail under data- calla-generating distribution Pz for all w E W. which is more general as we discussed above. Our upper bound is also improved by factor of 2[1CC)) compared to the result in [39].
Remark 2 (Choice of Cg). Since L(W; S) > O when 1(W; > 0, setting CE = 0 is always valid in Theorem which gives gen( (p Ps) < 20aa As shown in /49, Theorem 15), T(S; W) 2
A random variable X is o-sub-Gaussian if log Ex
VV IR and X is a-sub-Gaussian 22x2 2
the left-tail if log Ele MX--X) z²1² 2 5.

---

[S: W) holds for any Gaussian channel Pwis. In addition, it is discussed in [49, Example 1], if either the entropy of training S or the hypothesis W is small, [(S; W) would be smaller than L(S; L(S (as 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 sub- Exponential on left-tail in Appendix C.2.
3.2 PAC-Bayesian Upper Bound
As discussed in Section 1.4, the prior distribution used in PAC-Bayesial bounds is different from the prior in Gibbs algorithm, since the former priors can be chosen arbitrarily 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-depeedenn using (a, π (w), (ww, Ps)) -Gibbs distribution as the PAC-Bayes BaC-BByesian prior.
bound proposed in [40]
As the data data-generating distribution Ps is unknown in practice. we consider the (a, (()),, Lw P) distribution the following discussion, where Ps is an arbi- trary data gata-generating distribution. Since (a, ((w), Lr(w, )s-))) J-iibs distribution is independent of the samples and only depends on the population risk (pw,, Ps+), we can denote it as PW
By exploiting the connection between the symmetrized KL divergence DSKL (1@ || and the KL divergence term D | in the PAC-Bayesian bound from [40], the following PAC-Bayesian bound can obtained under i.i.d and sub-Gaussian assumptions.
Theorem 3. (proved in Appendix D) Suppose that the training samples S = {Z:}%=] are i.i.d generated from the distribution Pz, and the non-negative loss function [ww, Z) is a-sub- Gaussian under data-ge gentratgnnnningggg distribution Pz for all w E W. If we use the (a, T (w), Lp(w, Ds-))-Githl distribution as the PAC-Bayesiad prior, where Ps an arbitrary chosen (and known) distribution, the following upper bound holds for the generalization error of (a, (w)), Lg(u, s)) s))--ibbs algorithm with probability at least
25, 0 <
8 < 1 under distribution Ps.
2
Ja (1 (r())))) (1 [1+Cr) Cr(s))n +2
20²a
Epp Eppis- WIS-
(L, LE(W. })
(+20"D P2) + +c) +
where e A V 20 1og(1/6) and Cp(s) S p( [[w]s-))
for some Cp(s) 20
Remark 3 (Previous Result). We could recover the distribution disprebutionddependeent bound in [40, Theorem 6] by setting Pz: Pz, choosing bounded loss function in [0, 1] and Cr(s) 0 in our Theorem 3. Note that multiple terms in our upper bound in Theorem are tightened by a factor of 1/(1 Cr(s)) and we also consider naah-Gasssinn loss functions.
Remark (Choice of Cp(s)). Since the distribution Pz can be set arbitrurily, the prior distribution Pw palle is accessible. Then, can set Cr(s) (pp D poy to tighten the bound, as it can be computed exactly using the training set.
Asymptotic Behavior of Generalization Error for Gibbs Algorithm
In this section, we consider the asymptotic behavior of the generalization error for Gibbs algorithm as the inverse temperature a - oc. Note that the upper bounds obtained in the previous section, as well as the ones in the literature, have the order O (. ). which becomes vacuous in this regime. However, it known that the Gibbs algorithm will converge to ERM as a + oc, 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
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 unique (S) that minimizes the empirical risk, i.e., W*(S)= = arg min L (w, S).
(18)
wEW
7

---

It is shown in [33] that if HS)S) A V.Le(w, (s, is not singular, then Riis N(W"(S), 1 "5) in distribution. Thus, the symmetrized KL information in Theorem can be a evaluated using this Gaussian approximation, which gives the following result.
Proposition 1. (proved in Appendix E. In the single-well case, if the Hessian matrix H* is not singular, then the generalization error of the (oo, T (w), LE(w, s))-Gibbs algorithm is
gen( P wis: Ps) RAw. GWT (S)W]
(19)
2
Eps (W* (S)) (H' E(T))
(H
where E. W. [(W,S)) é erw ors [S(W BBw.s [SW,
Proposition shows that the generalization error of the Gibbs algorithm in the limiting regime - oc highly depends the landscape of the empirical risk function.
obtain the generalization error of the maximum likelihood estimates (MLE) in the asymptotic regime n + oc. 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(2; /w) } where w E W C Rd denotes the parameter. Here, the true data-ge generatinn distribution may not belong to the parametric family, i.e., Pz * f((ww) for E W. If we use the log-loss f(w, 2) - log [= ww) in the Gibbs algorithm, as - co, it converges to the ERM algorithm, which is equivalent to MLE, i.e.,
As an example, we use Proposition
(S( = WML A arg max log f(Z)ww).
(20)
WEW
As n + oo, under regularization conditions (details Appendix E.2) which guarantee that W*(S) is unique, the asymptotic normality of the MLE [64] states that the distribution of WML converges to
N(w", 1 J[w")) I(x"
with w= A arg min D(Pz)[(()w))
WEW
J(w) A Ez V log f( [Z|2r)] and I(w) A Ez V log (Z] log f(Z uv) J]
In addition, the Hessian matrix HT* (S) [wv") ) as n co, which is independent of the training samples S. Thus, w H (S)WW O, and Proposition 1 gives
gen P Ps) (((((()))(("))
(21)
n When the true model is in the parametric family Pz (-1w*), we have I(w") = J(w") and the above expression reduces to gen( Pr
gen(PW W|s+ Pz) L. 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 (S) such that
(S) E min (g(w, S), u E {1, M).
(22)
wEW
where M is a fixed constant, and all the minimizers (S) are isolated, meaning that a sufficiently small neighborhood of each (S) contains a unique minimum.
In this multiple-wel. case, it is shown in [12] that the the Gibbs algorithm can be approximated by Gaussian mixture, as long as HC(S) A V2 LeW, S) s) not singular for all u e (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 under the assumption that π (W) is uniform distribution over W.
Proposition 2. (proved in Appendix E.1) If we assume that π rW) is a uniform distribution over W, and the Hessian matrices H (S) are not singular for all u E ....... MM }. then the generalization error of the (2o, ((w) LE(W, -Gb-bs algorithm in the multiple-well case can be bounded as
1 W. H:(SW.
gen(PW s Ps) <
Eaw..
M
+ Eps (W) - (W:(S))=(WW(9)))
H. (VV ((W:())
(23)
8

---

Comparing with Proposition 1, Proposition 2 shows that the global generalization enror in the multiple- well 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 loose generalization error bound with the order O 2. Thus, our method can also be used to obtain lighter characterizatiio of the excess risk for the Gibbs algorithm.
In Appendix E.3, 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 Bemnteiin-vnn-Mise theorem [38] and the asymptotic normality of the MLE.
5 Regularized Gibbs Algorithm
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- indeeedne regularizer, as it may also depend on the training samples. There are many applications of such data-dependent regularization in the literature-e-g_ e.g. data-dependent spectral norm regularization is proposed in [57], & regularizer over data-dependent hypothesis space studied in [70] and dropout modeled data-dependent l regularization in [68].
In the following proposition, we consider the Gibbs algorithm with a regularization term It : W x z" + IRJ and characterize the generalization error of this (a, r(w), LE (w, s) + Af(w, s))-Gibbs algorithm, which is the solution the following regularized ERM problem:
Pwis= = arg inf (Lr,s + AR(W, + D(Pwis D(PWis|((W)))P) (WW)P))) Pwis
(24)
where x 2 0 controls the regularization term.
Proposition (proved in Appendix F.1) For (a, x(w), LE s) + AR(w, s)).ss))iGGGb algorithm, its expected generalization error is given by
[W: AEAW.. (RWW
gen W S. Ps)
(25)
where EAw. [R(W, S)] S o [[W E. [R(W,)))
Proposition holds for non-i.i.d samples and any non-negative loss function, and shows that to improve the generalization ability of the Gibbs algorithm, the data-dependent regularizer needs to 1) minimize the symmetrized KL information (W: :S) and 2) maximize the Eaw.s [R(W, S)] term which corresponds to "generalization error" defined with the regularization term R(W,S) S).
Remark 6. If the regularizer is independent of the data, i.e., R( R(w,s) = R(w), we have Eaw,s [RW S)] 0, and Proposition 3 gives (en(PW1s: Ps) JskI, (W:)) which implies that the inta-dndeeendent regularizer needs to improve the generalization ability of learning algorithm by reducing the symmetrized KL information IsKI(W;; SW:
a
Inspired by the data dett-deepnndett regularizer proposed in [61] for support vector machines, we consider a similar data- -ata-dependent E Ez-regularizer in the following proposition.
Proposition 4. (proved in Appendix F.I) Suppose that adopt the lz-regularizer R(w, s) [[)))l, where T(.) is an arbitrary deterministic function T 2" W. Then, the expected generalization error of (ax, x (w), Ln(w, 8) XR(w, GGbbbs algorithm is
gen gen(PW Ps) ISKL IsKL(W; (W;S) >tr(Cox(W,TT(S)),
(26)
where Cov IW, T(S) denotes the covariance matrix between W and T(5).
Our result suggests that to reduce the generalization error with data deta-deeendent Ez-regularizer, the function T T(S) should be chosen in a way, such that the term ir(Cov W 7 (S))) is maximized. One way is to leave 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 detendepn regularizer are provided in Appendix F.2.

---

Conclusion
We provide an exact characterization of the generalization error for the Gibbs algorithm using sym- metrized KL information. We demonstrate the power and versatility of our approach in multiple applications, including tightening expected generalization error and PAC-Bayesian bounds, character- izing 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 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
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. NIFRI M92656. Yuheng Bu is supported, in part, by NSF under Grant CCF-171766 and by the MIT-IBM Watson Al Lab.
References
[1] MBOUS-MOUTAAA, K., AND SZEPESVÁRI, ÁRT, C. An exponential Efron-Stein inequality for Tug stable learning rules. In Algorithmic Learning Theory (2019), PMLR, pp. 31-63.
[2] AKAIKE, H. Information theory and an extension of the maximum likelihood principle. In Selected papers of hirotugu akaike. Springer, 1998, pp. 199-213.
[3] ALQUIER, P., AND GUEDJ, B. Simpler PAC-Bayesie bounds for hostile data. Machine Learning 107, 5 (2018), 887-902.
[4] ALQUIER, P., RIDGWAY, J., AND CHOPIN, N. On the properties of variational approximations of Gibbs posteriors. The Journal of Machine Learning Research 17, (2016), 3374-8414.
[5] AMBROLADZE, A., PABRADO-HERNANDEZ E., AND SHAWE-TAYLOR J. Tighter PAC- Bayes bounds. Advances in neural information processing systems 19 (2007),
[6] AMINIAN, G., ARIMANDI, H., GOBARI,, A., NASIRI-KENARL M., AND MITRA, U. Capacity of iuffusion-based molecular communication networks over LTI-Poisson channels. IEEE Transactions on Molecular, Biological and Multi- Scale Communications 2 (2015), 188-201.
[7] AMINIAN, G., TONI, L., AND RODRIGUES, M. R. Censen-Shanner information based characterization of the generalization error of learning algorithms. In 2020 IEEE Information Theory Workshop (/TW) (2020), IEEE.
[8] AMINIAN, G., TONI, I.., AND RODRIGUES, R. Information-theoress bounds on the moments of the generalization error of learning algorithms. In IEEE International Symposium on Information Theory (ISIT) (2021).
[9] ANTHONY, M., AND BARTLETT, P. L. Neural network learning: Theoretical foundations. cambridge university press, 2009.
[10] ASADI, A., ABBE, E., AND VERDÚ, S. Chaining mutual information and tightening general- ization bounds. In Advances in Neural Information Processing Systems (2018), pp. 7234-7243,
[1]] ASADI, A. R., AND ABBE, E. Chaining meets chain rule: Multilevel entropic regularization and training of neural networks. Journal of Machine Learning Research 21, 139 (2020), 1-32.
[12] ATHREYA, K., AND HWANG, C.-R. Gibbs measures asymptotics. Sankhya A 72, (2010), 191-207.
[13] BANERJEE, P. K., AND MONTUFAR, G. Information complexity and generalization bounds. In IEEE International Symposium on Information Theory (ISIT) (2021).
[14] BÉGIN, L., GERMAIN, P., LAVIOLETTE, F., AND Roy, J.-F. PAC-Bayesian bounds based on the Rényi divergence. In Artificial Intelligence and Statistics (2016), PMLR, pp. 435-444.
10

---

[15] BOUCHERON, S., LUGOSI, G., AND MASSART, P. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
[16] BOUSQUET, O., AND ELISSEEFF, A. Stability and generalization. Journal of Machine Learning Research 2, Mar (2002), 499-526.
[17] BU, Y., GAO, W.. Zou, S., AND VEERAVALLI, V. V. Information -hhorreti understanding of population risk improvement with model compression. In Proceedings of the AAAI Conference on Artificial Intelligence (2020), vol. 34, pp. 3300-3307.
[18] BU, Y.. GAO, W., Zou, S., AND VEERAVALLI, V. V. Population risk improvement with model compression: An cooomatioo-theorette approach. Entropy 23, 10 (2021), 1255.
[19] BU, Y., Zou, S., AND VEERAVALLI, V. V. Tightening mutual information-base bounds on generalization error. IEEE Journal on Selected Areas in Information Theory 1, (2020), 121-130.
[20] CATONI, O. A PAC-Bayesian approach to adaptive classification. preprint 840 (2003).
[21] CATONI, O. PAC-Bayesian supervised classification: the thermodynamies of statistical learning. arXiv preprint arXiv:0712.0248 (2007).
[22] CHIANG, T.-S., HWANG, C.-R., AND SHEU, S. J. Diffusion for global optimization in IR..
SIAM Journal on Control and Optimization 25, 3 (1987), 737-753.
[23] DZIUGAITE, G. K., AND ROY, D. Entropy-SGD optimizes the prior of PAC-Bayes bound: Generalization properties of entropy-SGD and data-dependent priors. In International Confer- ence on Machine Learning (2018), PMLR, pp. 1377-1386.
DZIUGAITE, G. K., AND ROY, D. M. Data-dependent PAC-Bayes priors via differential [24]
privacy. In Advances in Neural Information Processing Systems (2018), pp. 8440-8450.
[25] ESPOSITO, A. R., GASTPAR, M., AND ISSA, I. Generalization error bounds via Rényi-, f-divergences and maximal leakage. IEEE Transactions Information Theory (2021).
[26] GERMAIN, P., BACH, F., LACOSTE, A., AND LACOSTE-JULIES S. PAC-Bayesian theory meets Bayesian inference. In Advances in Neural Information Processing Systems (2016),
pp. 1884-1892.
[27] GERMAIN, P., LACASSE, A., LAVIOLETTE, F., MARCH, M., AND Roy, J.-F. Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm. Journal of Machine Learning Research 16, 26 (2015), 787-860.
[28] GIBBS, J. W. Elementary principles of statistical mechanics. Compare 289 (1902), 314.
[29] GUEDJ, B., AND PUJOL, L. Still no free lunches: the price to pay for tighter PAC-Bayes bounds. arXiv preprint arXiv: 1910. 1.0.044400111 (2019).
[30]
MAFEZ-KOLAHL H., GOLGOONI, Z., KASAEI, S., AND SOLEYMANI, M. Conditioning and processing: Techniques to improve information -eetmaatio--thorettic generalization bounds. Advances in Neural Information Processing Systems 33 (2020).
[31] HAGHIFAM, M., NEGREA, J., KHISTI, A., ROY, D. M., AND DZIUGAITE, G. K. Sharpened generalization bounds based conditional mutual information and application to noisy, iterative algorithms. Advances in Neural Information Processing Systems (2020).
[32] HELLSTRÖM, F., AND DURISI, G. Generalization bounds via information density and condi- tional information density. IEEE Journal on Selected Areas in Information Theory (2020).
[33] HWANG, C.-R. Laplace's ss method revisited: weak convergence of probability measures. The Annals of Probubility (1980), 1177-1182.
[34] ISSA. I., ESPOSITO, A. R., AND GASTPAR, M. Strengthened information-theoree bounds on the generalization error. In 2019 IEEE International Symposium Information Theory (ISIT) (2019), IEEE, pp. 582-586.
[35] JAYNES, E. T. Information theory and statistical mechanics. Physical review 106, (1957), 620.
[36] JEFFREYS, H. An invariant form for the prior probability in estimation problems. Proceedings the Royal Society of London. Series A. Mathematical and Physical Sciences 186, 1007 (1946), 453 453-461.
11

---

[37] JIAO, J., HAN, Y., AND WEISSMAN, T. Dependence measures bounding the exploration bias for general measurements. In 2017 IEEE International Symposium on Information Theory (ISTT) (2017), IEEE, pp. 1475-1479.
[38] KLEIN, B. J., VAN DER VAART, A. W., ET AL. The Bernstein-von-Mises theorem under misspecification. Electronic Journal of Statistics 6 (2012), 354-381.
[39] KUZBORSKIJ, I., CESA-BIANCHI, N., AND SZEPESVÁRI, C. Distribution-dependnnt analysis of Gibbs-ERM principle. In Conference on Learning Theory (2019), PMLR, pp. 2028-2054.
[40] LEVER, G., LAVIOLETTE, F., AND HHAWE-TAYLOR J. Tighter PAC-Bayes bounds through distribution-dependee
priors. Theoretical Computer Science 473 (2013), 4-28.
[41] LOPEZ, A. T., AND JOG, V. Generalization error bounds using Wasserstein distances. In 2018 IEEE Information Theory Workshop (ITW) (2018), IEEE, pp. 1-5.
[42] MARKOWICH, P. A., AND VILLANI, C. On the trend to equilibrium for the Fokker-Plande equation: an interplay between physies and functional analysis. Mal. Contemp 19 (2000), 1-29.
[43] MASIHA, M. S., GOHARI, A., YASSAEE, M. H., AND AREF, M. Learning under distribution mismatch and model misspecification. In IEEE International Symposium on Information Theory (ISIT) (2021).
[44] MCALLESTER, D. A. Some PAC-Bayesian theorems. Machine Learning 37, 3 (1999), 355-363.
[45] MCALLESTER, D. PAC-Bayesian stochastic model selection. Machine Learning 51, (2003), 5-21.
[46] McSHERRY, F., AND TALWAR, K. Mechanism design via differential privacy. In 48th Anmual
IEEE Symposium on Foundations of Computer Science (FOCS (2007), IEEE, pp. 903.
[47] MURPHY, K. P. Conjugate Bayesian analysis of the Gaussian distribution. def 1, 2o2 (2007),
16.
[48] OINISIII Y., AND HONORIO, J. Novel change of measure inequalities with applications PAC-Bayesian bounds and Monte Carlo estimation. In International Conference on Artificial Intelligence and Statisties (2021), PMLR, pp. 1711-1719.
[49] PALOMAR, D. P., AND VERDÚ, S. Lautum information. IEEE transactions information theory 54, 3 (2008), 964-975
[50] HARRADO-HERNÁNDEES E., AMBROLADZE, A., SHAWE-TAYLORS J., AND SUN, S. PAC- Bayes bounds with data dependent priors. The Journal of Machine Learning Reseurch 13, 1 (2012), 3507-3531.
[51] RAGINSKY, M., RAKHLIN, A., AND TELGARSKY, M. Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory (2017), PMLR, pp. 1674-1703.
[52] RAGINSKY, M., RAKHLIN, A., TSAO, M., WU, Y., AND Xu, A. -eformation-thhortiicc analysis of stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (ITW) (2016), IEEE, pp. 26-30.
[53] RIVASPLATA, O., KUZBORSKIJ, I., SZEPESVÁRI, C., AND SHAWR-TAYL.OR, J. PAC-Bayes analysis beyond the usual bounds. Advances in Neural Information Processing Systems (2020).
[54] RIVASPLATA, O., PARRADO-HERNÁNTE
E., SHAWE-TAYLOOR, J., SUN, S., AND SZEPESVÁRT, C. PAC-Bayes bounds for stable algorithms with instance-dependent priors. In
NeurIPS (2018).
[55] RODRIGUES, M. R., AND ELDAR, Y. C. Anformation-Theorette Methods in Data Science. Cambridge University Press, 2021.
[56] RODRÍGUEZ-GÁLVERR B., BASSI, G., THOBABEN, R., AND SKOGLUND, M. Tighter expected generalization error bounds via Wasserstein distance. arXiv preprint arXiv:2101.0933 (2021).
[57] ROTH, K., KILCHER, Y., AND HOFMANN, T. Adversarial training is a form of data-dependent operator regularization. In Advances in Neural Information Processing Systems (2020), vol. 33, pp. 14973-14993
[58] Russo, D., AND ZoU, J. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions Information Theory 66, (2019), 302-323.
12

---

[59] SASON, I., AND VERDÚ, S. f-divergence inequalities. IEEE Transactions on Information Theory 62, 11 (2016), 5973-69070 6006.
[60] SHAWE-TAYLOR, AND WILLIAMSON, R. C. PAC analysis of Bayesian estimator, In Proceedings of the tenth annual conference on Compulational learning theory (1997), pp. 2-9.
[61] SHIVASWAMY, P. K., AND JEBARA, T. Maximum relative margin and data-dependent regular- ization. Journal of Machine Learning Research 11, (2010).
[62] STEINKE, T., AND ZAKYNTHINOU, L. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory (2020), PMLR, pp. 3437-3452.
[63] THIEMANN, N., IGEL, C., WINTENBERGER. O., AND SELDIN, Y. A strongly quasiconvex PAC-Bayesian bound. In International Conference on Algorithmic Learning Theory (2017),
PMLR, pp. 466-492.
[64] VAN DER VAART, A. W. Asymptotic statistics, vol. 3. Cambridge university press, 2000.
[65]
VAN ERVEN, T. PAC- BaC-Bayes mini-tutorial: a continuous union bound. arXiv preprint 1405 1580 (2014).
[66] VAPNIK, V. An overview of statistical learning theory. IEEE transactions on neural networks
10, 5 (1999), 988-999.
[67] VERSHYNIN, R. High-dimensional probability: An introduction with applications in data science, vol. 47. Cambridge university press, 2018.
[68] WAGER, S., WANG, S., AND LIANG, P. Dropout training as adaptive regularization. In Advances Neurul Information Processing Systems (2013), pp. 351-359.
[69] WANG, H., DIAZ, M., SANTOS FILIOO, J. C. S., AND CALMON, F, P. An information-theoredd view of generalization via Wasserstein distance. In 2019 IEEE International Symposium on Information Theory (ISIT) (2019), IEEE, pp. 577-581.
[70] XIAO, Q.- Q.-W., ZHoU, D.-X., AL. Learning by nonsymmetric kernlls with data dependent spaces and (' reguulariizer. Taiwanese Journal of Mathematics 14, (2010), 1821-1836.
[71] XU, A., AND RAGINSKY, M. Information-theorett analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems (2017), pp. 2524- 2533.
[72] Xu, H., AND MANNOR, S. Robustness and generalization. Machine learning 86, (2012), 391-423.
[73] ZHANG, C., BENGIO, S., HARDT, M., RECHT, B., AND VINYALS, O. Understanding deep learning (still) requires rethinking generalization. Communications the ACM 64, (2021), 107-115.
[74] ZHANG, H., AND CHEN, S. Concentration inequalities for statistical inference. arXiv preprint arXiv:2011.0225. (2020).
[75] ZHANG, T. information-theortticc theoretic upper and lower bounds for statistical estimation. IEEE Transactions on Information Theory 52, 4 (2006), 1307-1321.
[76] ZhaNg, T., AL.. From e-entropy to KL-ennroopy: Analysis of minimum information complexity density estimation, The Annals of Statistics 34, 5 (2006), 2180-2210.
13


Reviews:
[{"review_id": "hNRgFuUPmf", "reviewer": "Reviewer_DrrA", "summary": "This paper gives an exact characterization of the expected generalization error for the Gibbs algorithm by way of a symmetrized KL divergence between the input training data and the output hypothesis. This allows for tightening some existing generalization bounds under certain assumptions. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The Gibbs algorithm is an idealized model of learning and can be thought of as a soft version of the ERM algorithm. The generalization error of the Gibbs algorithm is a well-studied topic and I believe the characterization obtained in this paper is novel and useful. The authors show that the characterization can sometimes yield fast rate convergence bounds (depending on the inverse temperature parameter) under certain assumptions. The presentation can be improved in some places but overall the writing is clear. Below are some comments. \n\nComments: \n\n-- In l.26-29, the authors write, \"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 underlying data-generating distribution.\" There are many works that addressed this before (e.g., the mutual information-based bounds, Xu and Raginsky, 2017 and related work). This should be acknowledged. \n\n-- For the asymptotic analysis (Section 4) of the single-well case, the regularity conditions (Appendix E.2) for the asymptotic normality of the MLE estimate is almost never satisfied for many practical learning models (e.g., deep learning models, which are singular). A brief comment to that order can be included in relation to the validity of the results in such settings. Ditto for the multi-well case, which again relies on related assumptions (such as a full-rank Hessian). \n\nFormatting:\n\n-- In the References section, follow the standard NeurIPS formatting guidelines. ref [12] has a different format than similar ones from arxiv/preprints.\n\n**** Post-rebuttal:\n\nI have read the authors' response and maintain my original score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed by the authors. I do not foresee any potential negative societal impact of this work", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "two and half"}, "extra_text": {}}, {"review_id": "aBi2OrKQmT3", "reviewer": "Reviewer_9Z7C", "summary": "This paper is concerned with characterizing (and more generally deriving upper bounds on) \nthe expected generalization error (as defined at (2)) for the Gibbs algorithm.\nAfter giving some motivation for considering the Gibbs algorithm,\nthe authors state their key result: an exact characterization of the expected risk of the\nalgorithm, in terms of the symmetrized KL information between training sample and model, \nand the temperature parameter of the Gibbs distribution.\nThis allows the authors to recover some known upper bounds under \niid sampling and bounded loss function, as well as deriving a new upper bound \nwhen the loss function enjoys well-behaved tails \n(sub-gaussian, sub-exponential, sub-gamma, but possibly unbounded).\nThis approach also yields a PAC-Bayes upper bound,\nand an analysis of the behavior of the expected generalization error\nwhen the temperature parameter shoots to infinity.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, the results improve in an elegant manner over the state-of-the-art in a well detailed manner, and the problem appears significant.  The results seem to be new, but it is possible that the reviewer is not aware of similar results having been published elsewhere. Good paper.\n\n* This reviewer wonders whether the characterization in terms of symmetrized KL information is not well suited to also derive lower bounds.\n\n* Minor comments\n    * L.112 α-Réyni → α-Rényi\n    * L.198 Gibbs algorithm → the Gibbs algorithm", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MhH5nAyjXzv", "reviewer": "Reviewer_pGbj", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has a nice contribution in writing the expected generalization error of the Gibbs distribution as an information measure, i.e., the symmetrized KL information. It contributes to the recent line of work on the intersection of machine learning and information theory, more specifically information-theoretic generalization bounds. The proofs look correct to me, however, I did not verify them completely. The paper is well-written and well-organized, and compares the results to prior work in the literature. My only complaint with respect to citing prior works is that the paper seems to have missed in lines 128-133 mentioning the results and excess risk bounds on the Gibbs distribution found in [10, Appendix D]. The well-known paper by Jaynes “Information theory and statistical mechanics” (1957) which proves that the Gibbs distribution is the maximizer of energy minus entropy is better to be cited as well.\n\nMinor comments:\n1. In line 160, it is more convenient for the reader to mention exactly which result of [36] deals with non-negativity.  \n2. The proof of Theorem 4 is simple and incremental with respect to Theorem 1. Thus, it is better to be stated either as a corollary or a proposition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LT8V0H_K_fc", "reviewer": "Reviewer_3ZSG", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper appears to present an advance in the analysis of the Gibbs algorithm, however I am not conversant enough with the previous work to be confident of its originality.  The improvement of other bounds seems interesting and significant.  \n\nThe quality of the work seems good - with only light checking it seems to be technically correct with appropriate techniques. \nThe focus on the important Gibbs algorithm is well-motivated, and seems to connect with a variety of previous work, but the\nresults do seem restricted to that algorithm.\n\n It is generally clear and well-written, but is a little heavy.  That seems to be the case with most information theoretical work.  \nWhen reading the improved $\\alpha \\rightarrow \\infty$ bounds, I wondered how they compared with bounds on ERM in those settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It seems unlikely that the techniques would generalize beyond the Gibbs algorithm, I didn't understand the concluding comment about over-parameterized Gibbs algorithms.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the Gibbs posterior (called Gibbs algorithm in the paper), an extension of the posterior in Bayesian statistics, where the negative log-likelihood is replaced by a general loss function. The Gibbs posterior is motivated by information theory, PAC-Bayes bounds and many approaches that aim at generalizing the Bayesian techniques in ML.

The main result of the paper (Theorem 1) is an exact characterization of the Gibbs posterior expected risk, as the symmetrized KL information between the sample and the parameter over the inverse-temperature.

The authors then provide applications of this result: improvements of existing PAC-Bayes bounds in the sub-Gaussian case (Section 4), and asymptotic study in this case where the inverse temperature grows to infinity (Section 5; this case is not covered by existing PAC-Bayes bounds).

Finally, in Section 6, the author(s) generalize Theorem 1 to the case where one adds a possibly data-dependent regularizer to the loss function.

Theorem 1 is new. It leads to interesting generalization or improvements of existing results. The paper should be of interest for researchers not only in the PAC-Bayes community, but more generally for all researchers in Bayesian ML. My opinion is that the paper is overal very well written. This is also the opinion of all the Reviewers, even though some of them mentioned that the paper is a little dense in parts. Some of them raised minor points / typos, please take them into account.

I would just point out what I believe is a major terminology problem. The probability distribution in (3) is sometimes refered to as "pseudo-posterior", "generalized posterior", "Gibbs posterior" (e.g. [4]) or "Gibbs estimator" (e.g. [19]). It is sipply a Gibbs distribution, but "posterior" or "estimator" emphasize the fact that in this case, this distribution is used as a tools for statistics / machine learning. This is the first case I see it refered to as "Gibbs algorithm", and this is problematic for two reasons:
- this is not an algorithm,
- the term "Gibbs algorithm" is sometimes used to refer to the "Gibbs sampling" algorithm https://en.wikipedia.org/wiki/Gibbs_sampling introduced and studied by [Geman, S., & Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6), 721-741].
To keep calling "Gibbs algorithm" the generalized posterior in (3) would thus lead to confusion. I strongly recommend to the authors to change for "generalized posterior", "Gibbs posterior" or even "Gibbs distribution".

For these reasons, I strongly recommend to change the name of the paper from "Gibbs algorithm", for example to "Gibbs posterior".
Decision: Accept (Poster)