We provide novel information-theoretic generalization bounds for stochastic gradient Langevin dynamics (SGLD) under the assumptions of smoothness and dissipativity, which are widely used in sampling and non-convex optimization studies. Our bounds are time-independent and decay to zero as the sample size increases, regardless of the number of iterations and whether the step size is fixed. Unlike previous studies, we derive the generalization error bounds by focusing on the time evolution of the Kullback--Leibler divergence, which is related to the stability of datasets and is the upper bound of the mutual information between output parameters and an input dataset. Additionally, we establish the first information-theoretic generalization bound when the training and test loss are the same by showing that a loss function of SGLD is sub-exponential. This bound is also time-independent and removes the problematic step size dependence in existing work, leading to an improved excess risk bound by combining our analysis with the existing non-convex optimization error bounds.
Paper
Similar papers
Peer review
Summary
The paper provides novel information-theoretic generalization bounds for the SGLD. They derive the generalization error bounds by focusing on the time evolution of the Kullback–Leibler divergence. The bound is time-independent and removes the step size dependence in previous works.
Strengths
1. This paper provides novel generalization bounds for SGLD by using the Kullback–Leibler (KL) divergence between the distributions of parameters learned from different training datasets. 2. The authors provide the first information-theoretic generalization error bound and the excess risk bound without surrogate losses.
Weaknesses
1. Although the authors claim they provide the first information-theoretic generalization error bound and the excess risk bound without surrogate losses, they indeed use the dissipativity to fix the non-convexity in the proofs. 2. I feel a little overclaimed on the stepsize because you use the dissipativity, which can be a kind of weak "strongly convexity". In the strongly convex case of SGLD, the stepsize can also be improved.
Questions
see weakness part.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Yes
Summary
This paper provides novel generalization bounds for SGLD under smooth and dissipative loss conditions via the information-theoretic approach. The proposed bounds are time-independent and decay to zero as the sample size increases, regardless of the number of iterations and whether the step size is fixed. In addition, the proposed bound also leads to an improved excess risk bound by combining the analysis with the existing non-convex optimization error bounds.
Strengths
The combination of information-theoretic bounds and Fokker–Planck (FP) equation establishes the tighter bounds provided in the paper, which is impressive.
Weaknesses
I did not note any significant weakness in the paper.
Questions
It is shown in [1] that the generalization error of the Gibbs algorithm equals the symmetrized KL information between W and S. Under the sub-Gaussian condition, it can be further proved that the generalization error of the Gibbs algorithm has the order of $O(1/n)$ independent of dimension d and time t. As shown in Table 1, it seems that the bound provided by Farghly and Rebeschini is able to recover this 1/n rate for the generalization error Gibbs distribution but with an extra term $\eta^{1/2}$ for SGLD. However, the bound provided in this paper only scales in the order of $O(1/\sqrt{n})$. Could you please provide more insights into whether this gap is due to the mismatch between the Gibbs distribution and the SGLD or it is due to the looseness of mutual information-based bound? My guess would be the issue of mutual information-based bound, and maybe the techniques developed in the following recent paper [2,3] might be helpful. [1] Aminian, Gholamali, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. "An exact characterization of the generalization error for the Gibbs algorithm." Advances in Neural Information Processing Systems 34 (2021): 8106-8118. [2] Zhou, Ruida, Chao Tian, and Tie Liu. "Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem." arXiv preprint arXiv:2305.00876 (2023). [3] Wu, Xuetong, Jonathan H. Manton, Uwe Aickelin, and Jingge Zhu. "Fast rate generalization error bounds: Variations on a theme." In 2022 IEEE Information Theory Workshop (ITW), pp. 43-48. IEEE, 2022.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The limitations of the proposed method have been addressed well in the last section of the paper.
Summary
The paper develops "time-independent" information-theoretic generalization bounds for SGLD. The key ingredients are: assuming the smoothness and dissipativity assumptions of the loss function , tracking evolution of the weight densities for two independent training sets, and their KL divergence. Such an approach avoids accumulation of the mutual information quantities over iterations.
Strengths
The overall approach taken appears correct, and the results, if correct, are interesting and novel. It is unfortunate that the paper is not written clear enough for me assess the correctness of the results.
Weaknesses
I think some important aspects of the paper are not presented clearly or contain errors. 1. The definition of dissipativity appears wrong in Assumption 3: the right-hand side of the inequality is a not a scalar. Although this is easily fixable, it is upsetting to this reviewer that a central concept of the paper is not treated with care. 2. In section 4 when the authors try to develop generalization bounds of SGLD without a surrogate loss. It is not clear to me how one would perform SGLD on say, the 0-1 loss, instead of on a differentiable surrogate loss: How would you get a gradient signal? -- In the opening paragraph of section 4, the paper states $l=f$. I speculate that the authors may be considering the case where SGLD is run on a differentiable surrogate loss but the generalization error is evaluated using the true loss (say 0-1 loss). If that is the case, I would imagine that somewhere a relationship between the true loss and the surrogate loss be given or assumed. But nowhere I can find it. That confused me and stopped me from further decoding what the authors intend to mean. [After Rebuttal] I have read the authors' rebuttal and raised my rating to Weak Accept.
Questions
I am not familiar with dissapative losses. Assuming dissipativity is defined properly, are dissipative losses practically relevant? Can the authors give some loss functions that we use in practice satisfying this condition?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
1 poor
Contribution
2 fair
Limitations
NONE
Summary
In the literature, there are two approaches to obtain generalization performance bounds. One approach is to study the algorithmic stability and there are well-known results that can bound the generalization error using the algorithmic stability bounds. Another approach is the information-theoretic analysis, which is the approach adopted in this paper. One major contribution of the paper is that it provides generalization bounds that do not grow linearly in time, and moreover, it also avoids an unnatural dependence on the stepsize. In addition, the paper provides additional results that provide information-theoretic generalization bound and the excess risk bound without relying on the surrogate losses. The author(s) are very familiar with the literature and the comparisons with the existing literature is ample and the contributions of the paper are clear.
Strengths
One major contribution of the paper is that it provides generalization bounds that do not grow linearly in time, and moreover, it also avoids an unnatural dependence on the stepsize. In addition, the paper provides additional results that provide information-theoretic generalization bound and the excess risk bound without relying on the surrogate losses. The author(s) are very familiar with the literature and the comparisons with the existing literature is ample and the contributions of the paper are clear.
Weaknesses
One weakness is that even though the paper claims that the bound is independent of time $T$, I think some additional analysis is needed in Theorem 4 to make it more clear. For example, in Theorem 4, there is the term $V_{\nabla}:=\max_{t\in[0,T]}\beta\text{Var}[\nabla F(W_t,B_t)]$. I think the paper should include a lemma or something like that in the Appendix to explain how to provide an upper bound on $V_{\nabla}$ that is uniform in $T$. My guess is that Lemma 6 in the Appendix or something like that can help. But it is better to provide an upper bound on $V_{\nabla}$ to make it more clear your bound is uniform in $T$.
Questions
(1) In the last sentence of Theorem 1, ``an training dataset’’, here ``an’’ should be ``a’’. (2) In the paragraph before Theorem 1, can you provide a reference to the claim that ``This assumption is necessary to obtain the information-theoretic generalization bound.’’? (3) Assumption 4 seems to be a bit restrictive. Is it possible for example to relax this assumption to mixture of Gaussians or relax it in some other directions? (4) In eqution (10), use \left( and \right). (5) Page 6. ``By integratng Eq. (12) over $t\in[0,\eta]$, we have’’ This does not seem to be rigorous. It seems to be that you should consider $\partial/\partial t(KL*e^{\frac{1}{2\beta c_{LS}}t})$ in (12) instead and then integrate over it. (6) In the statements of Corollary 1 and Corollary 2, ``holds’’ should be ``hold’’. (7) In remark 4, can you double check it is $s^2>1$? It seems to me it should be $s^2<1$ instead. (8) In Remark 3 ``we often assume’’. It is better to write ``It is often assumed’’. (9) In equation (19) on page 14, what is the integral $\int\left(\frac{\rho_{t}}{\gamma_{t}}\frac{\partial\gamma_{t}}{\partial t}\right)$ w.r.t.? Did you miss $dw$ or what? Please double check the other integrals on page 14 and page 15 as well. (10) At the end of the first paragraph on page 17, what is $\mathcal{W}[A]$? What does $[A]$ stand for? (11) In the equation before equation (28), what does the notation $w^{d}$ stand for?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors have adequately discussed the limitations.
Further clarifications from the AC
Dear authors, I would like for some further clarifications that would help me, AC, be more focused in the discussion. I would like to reiterate and restate a concerns that was raised by Reviewer oJ4H. Can you provide a concrete example (even toy example) of a dissipative function, where the aforementioned bound yields a non trivial generalization bound? I would like to consider the following two points which makes me wonder if such an example might exist - As shown by [SSSS'08], there exists a convex problem where the unique solution of the ERM fails to generalize. As such, any optimization algorithm that is ran for infinite horizon must do one of two: Either it never converges to the minimum, or it fails to generalize. Taken with your result I am guessing that the SGLD algorithm will just fail to converge to the minimum even after infinite many iterations, which makes me wonder if it will have any guarantees on the population loss. - It was also recently showsn [L'22] that every algorithm that guarantees non-trivial population loss on convex problems, must carry dimension-dependent information on the sample. Together with your Thm4, that means that if the temperature is dimension independent, then SGLD will not achieve non-trivial population loss on the (convex) construction in [L'22]. Alternatively, one could choose dimension dependent temperature in SGLD but then algorithmic-independent generalization bounds can be easily (and have been) obtained via standard covering number argument/ uniform convergence. In that case, then, the fact that the generalization doesn't depend on the horizon is insignificant. Both points do not contradict your result, but they do make me wonder if you could actually provide a concrete example where the aforementioned techniques yield an interesting bound. SSS'08 -- Stochastic Convex Optimization L'22 -- Information theoretic lower bounds for information theoretic upper bounds.
Acknowledgements
Dear Area Chair vJFH, We appreciate you taking the time to consider our paper and raising very interesting questions in the context of the information-theoretic analysis under the dissipative loss assumption. We have read the references you provided and would like to carefully consider your questions before answering. We would greatly appreciate it if you could grant us about two days to send our response, given that we understand our discussion time is limited. Thank you very much for your understanding. Sincerely, Authors
Author responses (1)
First and foremost, we would like to express our gratitude for the intriguing questions regarding our paper and the information-theoretic (IT) analysis based on the dissipative assumption. In our opinion, the concerns related to the convergence of the generalization error bounds mentioned, as well as the concerns regarding dimension dependence, are fundamental drawbacks within the context of IT-based generalization analysis for SGLD when dealing with (non-)convex loss functions. We believe these are significant issues that warrant further discussion within the entire research community. Therefore, it might be challenging to provide examples that demonstrate non-trivial upper bounds capable of addressing these concerns based on the dissipativity assumption; however, we would like to provide an example of a dissipative loss function such that our approach is at least useful for analyzing the generalization error. Our response consists of the following four elements: ***(i) Background of introducing the dissipativity assumption***, ***(ii) Difference in motivation between bounds based on IT analysis and bounds for uniform convergence (including our contribution)***, ***(iii) Relevance to [sss'08] and [L'22]***, and ***(iv) Specific examples demonstrating the effectiveness of our approach (IT-based analysis with dissipative assumption)***. --- ## Part (i): Background of introducing the dissipativity assumption SGLD updates the model parameters using the stochastic gradient, which is utilized in SGD, multiplied by the learning rate, and augmented with added Gaussian noise. Introducing Gaussian noise to the stochastic gradient allows for escaping local minima and facilitates global parameter exploration. SGLD has garnered attention as a means for theoretically analyzing the performance of models with non-convex losses, such as neural networks (NN), which are commonly used in recent machine learning applications. Given that NN models are often trained in SGD, SGLD is a promising theoretical tool due to its similarity to SGD and its ability to perform global parameter exploration in the non-convex optimization context. When conducting theoretical analysis on models with non-convex losses based on the SGLD algorithm, ensuring ergodicity is essential to guarantee convergence to the target distribution and to the (local) minima. To assure ergodicity for a non-convex potential function, the concept of dissipativity is introduced, relaxing the assumption of convexity. In other words, the dissipative assumption is considered to enable theoretical analysis centered on non-convex losses through the SGLD algorithm. Since convex losses inherently satisfy dissipativity, employing this assumption in the realm of convex analysis may not yield non-trivial results, such as addressing your concern about convergence to the minima or the dimension dependence concerns in SGLD. However, at least within the context of IT-based analysis, we have discovered that our proposed analysis with dissipativity can yield intriguing results even when dealing with convex losses. The details will be explained in Part (iii).
Author responses (2)
## Part (ii): Difference in motivation between bounds based on IT analysis and bounds for uniform convergence (including our contribution) In order to effectively address your concerns from [SSS'08, L'22], we would like to explain the differences in motivation between IT analysis and generalization analysis based on uniform convergence as well as our contributions within this context. --- ### Part (ii)-1: Differences of each bound The generalization error bound based on the notion of uniform convergence (UC) is established from the perspective of the worst-case scenario regarding the generalization performance offered by the trained model. This bound guarantees, as you know, that the generalization error of all hypotheses in the algorithm’s output space simultaneously vanishes as the size of the training data increases, ensuring the convergence of generalization error. Furthermore, this bound asserts that within the ERM principle, it suffices to output any hypothesis from the class that minimizes empirical risk, and by measuring model complexities such as VC dimension or Rademacher complexity, one can evaluate generalization performance. In other words, this bound offers non-trivial guarantees when the hypothesis class utilized by the algorithm, along with its complexity, is moderately constrained. On the other hand, deep learning models are included in vast hypothesis classes where the model complexity drastically increases with the size and depth of the network. When applied to such models, UC-based bounds turn into a vacuous metric due to the exceedingly large model complexity. Furthermore, bounds based on UC rely solely on the hypothesis space and are unable to leverage beneficial statistics obtained from algorithms or datasets, which sometimes results in an inability to capture the true essence of generalization performance. For instance, the gradient variance w.r.t. model parameters exhibit a strong correlation with the generalization performance of deep learning [Jiang et al., 2020]; however, this correlation cannot be represented within UC-type bounds. (We refer [Amit et al., 2022] for details.) This observation leads to the recent interest in data and algorithmic-dependent generalization error bounds, such as the PAC-Bayes and IT generalization error bounds. The strength of the IT-based analysis lies in its capacity to directly incorporate the algorithm- and data-dependent statistics related to the generalization performance, such as the gradient variance instead of the model complexity, into the generalization error upper bounds. Especially, the gradient variance is empirically known to have a stronger correlation with the generalization performance of NNs [Jiang et al., 2020] in comparison to statistics appearing in uniform convergence analysis contexts (e.g., VC dimension, the number of parameters $d$, and the norm of parameters). Therefore, the gradient variance has been an increasingly significant metric in recent generalization analyses. Although the gradient variance implicitly depends on the dimension of parameters $d$, it is widely recognized that, in practice, the gradient variance becomes reasonably small as the training proceeds [Jiang et al., 2020]. Consequently, IT-based bounds offer a sensible generalization error bound even in models with significantly high complexity, such as NN models. This is why it has gained attention in the context of SGLD's generalization analysis. In short, the core aim of IT-based analysis is to offer practical bounds that effectively account for models with high complexity, like NN models, by directly integrating empirically validated statistics associated with generalization obtained from datasets and an algorithm. Active discussions within the realm of IT-based analysis revolve around how to analyze the generalization performance of NN, which involve non-convex losses, to derive bounds that lead to an accurate understanding of generalization performance.
Author responses (3)
### Part (ii)-2: Our contributions Our study follows this context and proposes a theoretical analysis method to provide a more accurate understanding and evaluation of generalization bounds while taking advantage of the strengths of IT-based analysis. Existing IT-based generalization error bounds expressed with the gradient variance have a structure that involves summing up gradient variances across all time steps, leading to divergence unless sufficiently decreasing the step size with $t$ (please see Theorem 2 of our paper). Additionally, it's worth highlighting that the gradient variance at the initial time step doesn't exhibit a significant correlation with generalization, as noted by [Jiang et al., 2020]. This observation implies that uniformly treating the value of gradient variance at each step might not be a practical approach. Against this backdrop, we have conjectured that we could achieve a more practically relevant analysis of generalization performance by avoiding summing up gradient variances equally across all time steps. Under this hypothesis, we focused on how the KL-divergence of two different parameter distributions obtained by the SGLD algorithm changes under the different training datasets instead of recursively analyzing the MI across all steps (please see Lemma 1 in our paper). As shown in Eq. (9), thanks to the LSI inequality, the contribution of the gradient variance at the early time step to the final bound decreases geometrically, and thus our bound does not diverge as increasing the time step $T$, and the gradient variance around final steps become dominant, which is consistent with the empirical study [Jiang et al., 2020].
Author responses (4)
## Part (iii): Relevance to [SSS'08] and [L'22] --- ### Part (iii)-1: Related to [SSS'08] As you pointed out, the obtained parameters via SGLD do not converge to the (local) minima under a fixed temperature parameter ($\beta$) for the Gaussian noise coefficient. These converge rather to a stationary distribution known as the Gibbs posterior $\pi(\mathrm{d}w) \propto e^{-\beta F(W, S)}\mathrm{d}w$ when $\beta$ is fixed over time step since SGLD is a ***sampling*** method from a target distribution based on the concept of Langevin dynamics, where $F(W, S)$ represents the training loss. In essence, the trajectory of parameters via the SGLD algorithm gets closer to the minima and then explores its vicinity due to the addition of Gaussian noise to the gradient. Therefore, while ***convergence to a target distribution*** occurs, convergence to the minima itself is not achieved without controlling the noise via $\beta$. Although SGLD does not converge to the minima, as elucidated earlier, it boasts a distinct edge in its ability to explore parameters globally, even within non-convex problems, thanks to the Gaussian noise. This property enables the evaluation of how the obtained ***expected loss*** w.r.t. the stationary distribution deviates from that with the global minima. Specifically, we can evaluate this difference by factors that depend on parameter dimensions $d$, $\beta$, and the constants appearing in the assumptions for the potential function, such as dissipativity and smoothness, as elaborated in Appendix D.5 of our paper. Furthermore, we can also derive the upper bounds for the population risk and excess risk both for convex and non-convex losses (please see [Raginsky et al., 2017; Xu et al., 2018]). --- ### Part (iii)-2: Related to [LL'22] Here, we discuss the dependence on the parameter dimension $d$ pointed out in [L'22]. Unfortunately, removing this dependence is difficult or unavoidable even if our framework is utilized when analyzing the ***excess risk*** of discretized Langevin dynamics such as SGLD through the mutual information (MI) between the dataset and parameters. This difficulty comes from the property that SGLD is the sampling method, as mentioned in Part (iii)-1. On the other hand, concerning the generalization error, existing IT-based bounds are expressed using gradient variance, explicitly independent of parameter dimension $d$ (we will mention this property in the specific example introduced in Part (iv)). And the empirical fact that gradient variance decreases as learning progresses substantiates the significance and advantages of such algorithm- and data-dependent bounds, as we said in Part (ii). Despite the above merit, the gradient variance implicitly depends on the dimension of parameters $d$, as we mentioned in Part (ii) (it is known that the gradient variance gets small as training proceeds empirically, though). In order to theoretically mitigate this reliance on dimensionality, it could be imperative to explore an alternative approach to evaluating generalization that deviates from the mutual information (MI) between parameters and data, which forms the cornerstone of this paper. One possible avenue is, for instance, the utilization of conditional mutual information (CMI) involving super-samples (e.g., [Wang and Mao, 2023]), as highlighted in [L'22], as well as methods to quantify the MI between the ***learned hypothesis*** and dataset (hMI), instead of focusing on the parameters [Harutyunyan et al., 2021]. However, the drawback of these approaches is that it becomes challenging to explicitly incorporate statistics directly obtained from algorithms, such as the gradient variance, into the understanding and evaluation of generalization despite being analyses of algorithm-dependent generalization performance. Seeking IT-based bounds that not only represent algorithm- and data-dependent statistics related to generalization performance, such as gradient variance but also theoretically eliminate dimension dependence constitutes a significant future work in the context of the IT-based generalization analysis field.
Author responses (5)
## Part (iv) Specific examples demonstrating the effectiveness of our approach. In our analysis, as mentioned in Part (iii)-2, we upper bound the KL divergence by $\textrm{(KL-divergence at the previous time step)} \cdot e^{- \textrm{Const.}} + \textrm{(gradient variance at the previous time step)} + (\textrm{an additional term} c_3\eta$ (please refer to Eq. (7) in Lemma 1). If the third term is absent, the final KL divergence is dominantly expressed by the gradient variance at around the final time step. This is because the gradient variance at the early time-step geometrically diminishes due to the term $e^{- \textrm{Const.}}$ (please recall that this KL-divergence term is expressed recursively via one-step old gradient variance at each step). As for the third term in Eq. (7), this term explicitly depends on the algorithm-independent statistics, such as the smoothness parameter of the loss function and the dimension of the model. As a result, the inherent advantage of IT-based generalization error analysis, which allows for a concise explanation of generalization performance through gradient variance, is somewhat compromised (this is a limitation of our approach). On the other hand, we have found that in certain cases, such as ERM with convexity losses or with L2 regularization, we can eliminate this problematic third term ($c_3\eta$), i.e., bounds evaluated solely based on gradient variances. Furthermore, in this bound, the (initial) gradient variance from two or more time steps ago decreases geometrically, which is the ideal result we were aiming for. We explain the details below. For simplicity, we consider Langevin dynamics (LD) in the continuous limit instead of SGLD, which is the same setup as in Eq. (9) in Sec. 3.3 of our paper. As one particular case, i) we assume that the training loss $F(w,z)$ is $R$-strongly convex ($0 < R< \infty$). We note that $R$-strongly convex losses satisfy dissipativity. As the other case, ii) we consider the ERM with $l_{2}$ regularization and the Gaussian initial distribution, i.e., $F(w,z)=F_0(w,z)+\frac{\lambda}{2}\||w\||^2$ ($0 < \lambda< \infty$), where the Gaussian initial distribution is given as $\pi_0\propto e^{-\beta\frac{\lambda}{2}\||w\||^2}$. We also assume that $F_0(w,z)$ is $C$-bounded ($0 \leq C < 0$). Note that we can use non-convex losses in this case if the above assumption holds because we add $l_{2}$ regularization so that $F(w,z)$ becomes a dissipative function. Under the above settings, we can derive the following inequality, which corresponds to Eq. (7) in Lemma 1. In the case i), when considering $R$-strongly convex ($0 < R< \infty$) loss and assume that $T=\eta K$ for $K\in \mathbb{N}$, we have $\mathrm{KL}(\rho_{\eta K}|\gamma_{\eta K}) \leq e^{-\frac{\eta}{2\beta R}}\mathrm{KL}(\rho_{\eta (K-1)}|\gamma_{\eta (K-1)})+\frac{\beta}{2} \int_{\eta (K-1)}^{\eta K}e^{-\frac{(\eta-t)}{2\beta R}} \mathbb{E}\|| \nabla F(W_t,S) - \nabla F(W_t,S')\||^{2}\mathrm{d}t$. In case ii), when considering $l_{2}$ regularization with $C$-bounded loss function, we obtain the same result as above by only replacing $R\to \frac{\lambda}{e^{8\beta C}}$. Unlike Eq. (7) in Lemma 1, which is shown under general dissipative loss functions, this new bound is expressed only in terms of the gradient variance, without the third term $c_3\eta$. Thanks to this result, only the gradient variance closer to the end time of the algorithm contributes to the bound values since the old gradient variances are geometrically reduced. This behavior is closer to the fact that past gradient variance, especially in the early time step, does not correlate well with the generalization performance of NNs [Jiang et al., 2020]. We also show the generalization error bound based on the above new bound; $|\mathrm{gen}(\mu,P_{W_T|S})|\leq \sqrt{\frac{\beta \sigma_g^2}{n}\sum_{k=0}^{K-1}\int_{\eta k}^{\eta(k+1)}e^{-\frac{(\eta (K-k)-t)}{2\beta R}} \mathbb{E}\|| \nabla F(W_t,S)- \nabla F(W_t,S')\||^{2}\mathrm{d}t}$. The difference from Theorem 4 in our paper is that the bound can be expressed only in terms of the gradient variance at each time step. We note that the new bound does not lose the property of time independence and geometrical reduction of the gradient variance at early time steps. *(Continue to the next thread)*
Author responses (6)
*(Continued from previous thread)* In the case of SGLD (LD with discretization), a similar bound can be derived using conditional variance, as shown in Appendix C-1. This result cannot be obtained simply by applying data processing inequality to the MI between the dataset and parameters evaluated in the existing Information-theoretic bounds. This is the non-trivial result derived by our approach based on the geometric information that SGLD is a Markov diffusion process given by a stochastic differential equation called LD and that the amount of Fisher information at each time point is bounded by the KL-divergence. Also, this bound is closely related to Proposition 9 of [Mou et al., 18], which evaluated the generalization in terms of the ***gradient norm***. The bound of that paper evaluates the generalization error bound through the norm of the gradient, whereas our bound is expressed by the gradient variance, a statistic that is related to the stability of the algorithm. As a conclusion to this part, we provide the facts we used in proving this bound. In the case of strongly convex losses, we utilize local Logarithmic Sobolev inequality from [Bakry, 2013]; in the case of bounded losses + L2 regularization, we use Lemma 34 in [Li et al., 2020]. The complete proof will be organized in Appendix E. --- ## Acknowledgement & Conclusion We genuinely appreciate your insightful remarks and the opportunity to consider specific examples where our approach is also valid in the context of convex analysis. It's truly gratifying to know that we could come up with such interesting examples as mentioned above. Additionally, I'm grateful for your acknowledgment of the concerns related to the dependence on parameter dimensions and convergence of optimization. As pointed out not only in the paper by [L’22] but also in [Haghifam et al., 2023], limitations of information-theoretic generalization bounds for gradient descent methods in stochastic convex optimization], this is an issue that pertains to the entire community of generalization analysis based on information-theoretic approaches, including ours. Ensuring consistency with convergence properties is indeed a crucial direction for the future, without a doubt. The bounds introduced in Part (iii) seem to provide important and intriguing insights, and we believe they should be added to the main part of our paper. Therefore, we will create a new subsection (Section 3.4) and explain the above. Furthermore, discussions regarding convergence properties and dimension dependence will be included and the new appendix section (Appendix E.: Additional discussion of limitations and related studies in our study) --- ## New References - [Jiang et al., 2020]: Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. ``Fantastic Generalization Measures and Where to Find Them.’’ In The Eighth International Conference on Learning Representations, 2020. https://openreview.net/pdf?id=SJgIPJBFvH - [Amit et al., 2022]: R. Amit, B. Epstein, S. Moran, and R. Meir. ``Integral Probability Metrics PAC-Bayes Bounds.’’ In Advances in Neural Information Processing Systems, vol. 35, pp. 3123–3136, 2022. https://openreview.net/pdf?id=H547BtAyOJ4 - [Wang and Mao, 2023]: Z. Wang and Y. Mao. ``Tighter information-theoretic generalization bounds from supersamples.’’ In Proceedings of the 40th International Conference on Machine Learning, 2023. https://openreview.net/pdf?id=y6gg68aGiq - [Harutyunyan et al., 2021]: H. Harutyunyan, M. Raginsky, G. Ver Steeg, and A. Galstyan. ``Information-theoretic generalization bounds for black-box learning algorithms.’’ In Advances in Neural Information Processing Systems, vol. 34, pp.24670–24682, 2021. https://openreview.net/pdf?id=L_cN8vD0XdT - [Mou et al., 18]: W. Mou, L. Wang, X. Zhai, and K. Zheng. ``Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints.’’ In Proceedings of the 31st Conference On Learning Theory, volume 75, pages 605–638, 2018. http://proceedings.mlr.press/v75/mou18a/mou18a.pdf - [Li et ai., 2020]: J. Li, X. Luo, and M. Qiao. ``On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning.’’ In The Eighth International Conference on Learning Representations, 2020. https://openreview.net/pdf?id=SkxxtgHKPS - [Haghifam et al., 2023]: M. Haghifam, B. Rodríguez-Gálvez, R. Thobaben, M. Skoglund, D. M. Roy, and G. K. Dziugaite. ``Limitations of information-theoretic generalization bounds for gradient descent methods in stochastic convex optimization.’’ In Proceedings of the 34th Conference On Learning Theory, volume 201, pages 663–706, 2023. https://proceedings.mlr.press/v201/haghifam23a/haghifam23a.pdf
Thank you for your clarification
I now understand the setting for Section 4 and appreciate the clarification on dissipative losses. I will raise my rating to above the acceptance threshold. But regarding the error on the definition of dissipativity, I still find it upsetting. I would like to advise the authors that such an error (i.e, one on a central concept or result) should never occur in a submitted technical document by a professional. As a reviewer, I would think: if the authors are so sloppy on the key definitions, how could I trust their derivations that are more technical and might require subtle considerations? -- The reviewers are volunteers, spending their own time trying to understand your paper. If you do not demonstrate a professional attitude and take your own paper seriously, on what ground would you expect the reviewers to be serious about your work?
Sincere Apologies
Dear Reviewer oJ4H, We would like to express our genuine gratitude for taking the time to confirm our paper and our response and for providing valuable feedback. We are pleased that the clarification we provided in our response helped you better understand the setting. Your willingness to reconsider the score is also deeply appreciated. We wholeheartedly understand your frustration and deeply regret any disappointment or concern the error in the definition of dissipativity may have caused. You are absolutely right in highlighting that errors in fundamental concepts should never be present in a professional technical document. We would like to assure you that we have sincerely rectified this error. We understand the significance of your concerns regarding the potential impact of such inadvertent errors on the credibility of our derivations and technical explanations. We are committed to continually ensuring that our professionalism and attention to detail are evident in our present and future endeavors. We also wish to emphasize our profound appreciation for your time and effort in comprehending and reviewing our work. In responding to this dedication, we are keenly aware of our responsibility to meet the standards you rightfully expect. Once again, please accept our sincere apologies for any frustration or doubts caused by our error. We are truly grateful for your patience and understanding. Sincerely, Authors.
Decision
Accept (poster)