Information Theoretic Lower Bounds for Information Theoretic Upper Bounds

Summary

This paper provides a lower bound on the mutual information between the output weights and the input training data in the context of stochastic convex optimization to examine the tightness of the mutual information-based generalization bound. It is shown in the paper that mutual information grows with the dimension of the parameter, which implies that existing information-theoretic generalization bounds fall short in capturing the generalization capabilities of SGD and regularized ERM, which have dimension-independent sample complexity.

Strengths

It is important to consider the lower bound (converse) result to understand the fundamental limits of information-theoretic analysis in characterizing the generalization of learning algorithms. To my understanding, pessimistic analysis can be more insightful than some ad-hoc method for tightening existing bounds.

Weaknesses

1. It is hard for me to understand why Theorem 1 holds for any learning algorithm. Let us take the Gibbs algorithm considered in Section 4.3 of (Xu and Raginsky [2017]) and further investigated in the following paper as an example. 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. The above reference provides an exact characterization of generalization error using information measures. It has been shown in their proof of Theorem 2 that the mutual information $I(S;W_S)$ can be upper bound by $O(1/n)$, which is independent of d. Thus, it is hard for me to digest the result presented in Theorem 1. 2. This paper mainly criticizes the tightness of the MI bound in (Xu and Raginsky [2017]) and the CMI bound in (Steinke and Zakynthinou [2020]). However, these issues are well-known in the literature. For example, MI can be infinite for deterministic learning algorithms. There are results tightening these results by considering the MI (or CMI) between W and each individual sample $Z_i$ (see below). Is there a way to show that these bounds also suffered from the same issue described in the paper? Bu, Yuheng, Shaofeng Zou, and Venugopal V. Veeravalli. "Tightening mutual information-based bounds on generalization error." IEEE Journal on Selected Areas in Information Theory 1, no. 1 (2020): 121-130. Zhou, Ruida, Chao Tian, and Tie Liu. "Individually conditional individual mutual information bound on generalization error." IEEE Transactions on Information Theory 68, no. 5 (2022): 3304-3316.

Questions

1. Line 212, to my understanding it should be d^{1/7}/m^{6/7}. Please double-check. 2. Line 280, it is said that CMI_m(A)=O(m). Can you provide a reference or insights into why it is the case? 3. Line 20 “inorder” should be “in order”. 4. The term suboptimality is often referred to as excess risk in literature.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

No potential negative societal impact was observed.

Summary

This paper challenges the tightness of some information-theoretic upper bounds on the generalization error in the stochastic convex optimization (SCO) setting (i.e. convex, Lipschitz, bounded loss on a bounded domain). More precisely, it challenges the bound from Xu and Raginksy that (vaguely) states that the generalization error is bounded from above by a function of the mutual information between the dataset and the output of the learning algorithm. With this purpose, the authors derive lower bounds on the mutual information that grows with the dimension of the input space. This, in turn, shows that there is a distribution over an input space such that the mutual information is arbitrarily large. Therefore the mutual information-based bounds are vacuous for that distribution. These lower bounds are obtained by means of three essential tricks: 1) Noting that one may only study discrete algorithms and discrete distributions over the inputs. The fact of considering discrete distributions over the input comes naturally from the fact that they are looking for lower bounds. Then, restricting to discrete algorithms is possible since (i) the loss is Lipschitz and the generalization error of a discretization of the parameters can at most incur into a constant multiplicative penalty and since (ii) the mutual information will only be smaller by the data processing inequality. 2) Employing a fingerprinting lemma from Kamath et al. (2019). For random variables $(X\_i)\_{i=1}^m \in \lbrace -1, 1 \rbrace$ such that $\mathbb{E}[X\_i]=p$. This lemma essentially states that the MSE of an estimator of $p$ decreases the more correlated the error of the estimator is with the error of the empirical mean. That is, a good estimator of $p$ is highly correlated with the empirical mean. 3) Noting that if two random variables $X$ and $Y$ are correlated with $\mathbb{E}[XY] = \beta$, then the mutual information $I(X;Y)$ is grows as $\Omega(\beta^4)$. Overly simplifying, this way, they construct an example where the loss function is $f(w,z) = \lVert w - z \rVert^2$. Then, by the fingerprinting lemma, any algorithm that attains a good error is necessarily correlated with the empirical mean. Therefore, the mutual information between the output of the algorithm and the empirical mean is bounded from below. Finally, by the data processing inequality, the mutual information between the output of the algorithm and the dataset is also bounded from below. The use of the chain rule makes sure that this scales with the dimension of the input.

Strengths

The problem studied is interesting. While Bassily et al. (2019) presented some lower bounds of the mutual information for learning thresholds and Haghifam et al. (2022) showed lower bounds of the mutual information, conditional mutual information, and its variants for gradient descent (GD) in the SCO setting, studying general lower bounds for any algorithms in this setting is important. As mentioned in the summary, the realization of being able to only consider discrete algorithms and the usage of the fingerprinting lemma to find lower bounds on the mutual information of algorithms in the SCO setting is original and interesting. Moreover, formalizing the expected result that correlated random variables have large mutual information is valuable in its own right.

Weaknesses

- The authors sometimes fail to position the related literature correctly. - They only glass over Haghifam et al. (2022) in Section 1.1 and they say that the paper finds lower bounds on the mutual information (MI) and the conditional mutual information (CMI) of GD and a variant of GD with a perturbation on the final iterate. They also find lower bounds for the individual sample versions of the MI and CMI as well as the evaluated CMI for the GD algorithm. Moreover, they mention that the bounds have a logarithmic dependence on the dimension. This is not accurate, while the dependence is logarithmic for the perturbed version of GD, for vanilla GD the bounds grow with the square root of the dimension. - In line 257 it seems they forgot to cite Bassiliy et al. (2018). In the same sub-subsection (CMI-bounds) it seems that they also forgot to mention the existing lower bounds from Haghifam et al. (2022). - Also in the CMI-bounds sub-subsection they describe wrong the CMI. The CMI is not $I(w\_S;S|Z)$, it is $I(w\_S; U|Z)$, where $U$ is a sequence of Bernoulli random variables whose realization is used to select between $z\_i^0$ and $z\_i^1$ to generate the dataset $S$. - The paper is not very clear. - Most of the citations in the paper are not in the correct format (that is, they are not within brackets in the \citep style of natbib, but directly written in the \citet style of natbib), difficulting readability. - Sometimes the sentences are a little overstated: e.g. in line 174 they say "Theorem 1 shows that any algorithm with non-trivial learning guarantees must carry a dimension-dependent amount of information on the sample or require a large sample". This is not completely accurate. To be precise, for every algorithm $A$, there is a distribution $D$ over a space $\mathcal{Z}$ and a convex, Lipschitz function $f$ such that if the algorithm achieves a non-trivial learning guarantee, then it must carry a dimension-dependent amount of information on the sample or require a large sample. - The sub-subsection CMI-bounds seems a little disconnected. The whole paper focuses on finding lower bounds of the mutual information, showing limitations to these bounds. Haghifam et al. (2022) show that at least for GD one can have a population risk of $O(1/\sqrt{m})$ while having a CMI of $\Omega(m)$, which would go in the direction of obtaining lower bounds. Moreover, it is not clear why $O(1/\sqrt{m})$ is chosen for the population risk and $o(\sqrt{m})$ is chosen for the CMI. The subsampling statement above seems to try to clarify this, but why would not one choose to subsample $O(m^{1/4})$ or $O(\log m)$? There seems to be no justification. - Lemma 3 is used without any proof in the Appendix of the supplementary material, which is in the template of the submission to another conference whose main text differs in some places from the main text submitted. - The final part of the paper (from line 333 on) seems disconnected from the rest of the text. Small mistakes: - In 237-238 it states that "for any algorithm such that $\Delta\_S(w\_S) = O(1/m)$ we will have that the bound in Eq. (2) is order of $\mathbb{E}[\Delta\_D (w\_S)] = \tilde{O}(\sqrt{d/m})$. This is not correct, the bound is of that order, but not $\mathbb{E}[\Delta\_D (w\_S)] $. - In Appendix A, it should be $\lbrace -1 / \sqrt{d}, 1 / \sqrt{d} \rbrace$, right?

Questions

- Why is there a vector $p$ such that for $d / (10^6 m \epsilon)$ of the coordinates (22) holds? Why is it not possible that less cordinates have that value be much larger than 1/108? - Why can you employ the data processing inequality after (24)? X\_p(t) depends both on $Z\_i$ and $W\_S$, and $Y\_p(t)$ depends on $W\_S$? - Could the techniques from this paper be employed to also find lower bounds on stronger information-theoretic bounds on the generalization such as the individual MI from Bu, Zhou, and Veeravalli (2020)? **References** Y.Bu, S. Zhou, and V. V. Veeravalli. "Tightening Mutual Information-Based Bounds on Generalization Error". Journal on Selected Areas in Information Theory. 2020.

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

2 fair

Contribution

3 good

Limitations

Some limitations are touched on in the comparison of the results with uniform convergence bounds in lines 239-256. However, there is not a large discussion of the limitations of the paper. For instance, what happens if an algorithm chooses another loss function? or, could one just consider a stronger information-theoretic notion such as the individual MI and then achieve bounds with a good rate? Maybe the space from lines 333 onwards could be used to reflect more on these issues in the Discussion section.

Summary

This work considers the setting of stochastic convex optimization in $\mathbb{R}^d$ with learning algorithms that achieve less than $\epsilon$ expected excess risk when at least $m(\epsilon)$ examples are given. The main result of this work (Theorem 1) states that such algorithms have $\tilde{\Omega}\left(\frac{d}{\epsilon^5 m(\epsilon)^5}\right)$ amount of Shannon mutual information between the input and the output (i.e., $I(w_S; S)$ with $w_S$ being the output on input sample $S$). The significance of this lower bound is that there is a linear dependence on dimension $d$, which renders the bound of Xu and Raginsky [2017] dimension-dependent in case $m(\epsilon)=o(d^{1/5})$. For example, if one considers minimax optimal learning algorithms (that have $\frac{1}{\epsilon}$ or $\frac{1}{\epsilon^2}$ sample complexity depending on assumptions about the loss function), the generalization gap bounds with input-output mutual information become dimension dependent and can be vacuous when $d \gg m$.

Strengths

**Strength #1: Significance.** Recently information-theoretic generalization bounds have gained a lot of attention, partly because they are algorithm and distribution-dependent and some variants of them are nonvacuous in practical setting for deep learning. Understanding limitations of information-theoretic generalization bounds is thus important and relevant for the NeurIPS community. The lower bound derived in this work is a good contribution to the list of already known limitations. **Strength #2: Originality.** To my best knowledge the derived lower bound is novel. The related work is cited adequately.

Weaknesses

**Weakness #1: Soundness.** I couldn't verify some parts of the proof of Theorem 1. Some clarifications are needed. - In the line after equation (17), "Next, for fixed $p$ we define two random variables": Is $p$ a vector here or a constant? Should it be $\frac{1-9p(t)^2}{9-9p(t)^2}$ instead? - In the line after equation (18), "Applying Lemma 1, ...": It was hard for me to follow the proof. I suggest to clearly write what $f$ is, verify that $f$ has the signature $f: \\{-1,1\\}^m \rightarrow [-1/3, +1/3]$ as required by Lemma 1, and clearly write what $X_i$ of Lemma 1 are in your construction. As I understand $X_i$ of Lemma 1 correspond to $\sqrt{d} z_i(t)$, but in that case $\hat{p}(t)$ is not a function of $\\{\sqrt{d}z_i(t)\\}_{i=1}^m$. - In the line after equation (20), "Write $Z = \mathbb{E}_{S\sim D^m(p)}\left[ X_p(t) Y_p(t)\right]$": I suggest to use another letter instead of $Z$, which is already used to denote the input. Additionally, in order to apply Paley-Zygmund inequality, $Z$ needs to be positive. I think this should be verified. As I understand, the algorithm can be such that it fails to be positively correlated with the mean for some choices of $p$. For those choices of $p$, $Z$ can be zero or negative. - I could verify the proof after equation (21). **Weakness #2: Clarity & Presentation [minor].** The paper would benefit a lot from improvements in terms of clarity and presentation. It was hard for me to read and understand the details, as there were many small mistakes, some parts of derivations were not detailed enough, and some parts of the main text made sense only after reading the later parts of the paper. Please see more detailed comments and suggestions below. **Weakness #3: Limitations [minor].** Deriving a lower-bound for the input-output mutual information is does not have strong implications about the line of information-theoretic generalization bounds. It is well-known that information-theoretic generalization bounds that depend on input-output mutual information have many limitations. For example, they can be infinite for well-generalizing continuous learning algorithms. For this reason many techniques of improving such bounds were proposed. 1. Bu et al. [1] derived an improved expected generalization gap bound that depends on $\sum_i I(w_S; Z_i)$ rather than $I(w_S, S)$ with $S=(Z_1,\ldots,Z_m)$ being the sample. 2. As discussed in the paper, there are conditional mutual information bounds that are dimension independent. These CMI bounds of Steinke and Zakynthinou have been improved a lot subsequently: (a) deriving sample wise bounds $\sum_i I(w_S; J_i | \tilde{Z})$ (where $J$ is the train-test split variable and $\tilde{Z} \in \mathcal{Z}^{n\times 2}$ is the supersample) [2], (b) conditioning on individual pair of supersample examples: $\sum_i I(w_S; J_i | \tilde{Z}_i)$ [3]; (c) measuring information in function space [4]; and (d) leave-one-out bounds [5]. To my understanding, the result of this paper does not extend to these stronger bounds. Final note: the main determinant of the score assigned below is the weakness #1. I am willing to increase the score if the concerns are properly addressed. **References** [1] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 2020. [2] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. NeurIPS 2020. [3] H. Harutyunyan, M. Raginsky, GV. Steeg, and A. Galstyan. Information-theoretic generalization bounds for black-box learning algorithms. NeurIPS 2021. [4] B. Rodríguez-Gálvez, G. Bassi, R. Thobaben, and M. Skoglund. On random subset generalization error bounds and the stochastic gradient Langevin dynamics algorithm. IEEE ITW 2021. [5] M. Haghifam, S. Moran, DM. Roy, and GK. Dziugiate. Understanding generalization via leave-one-out conditional mutual information. IEEE ISIT 2022.

Questions

- Please use `\citep` or `\citet` (depending on whether authors are a part of the sentence or not) rather than `\cite`. - Lines 74-78: Need to be rewritten to improve clarity. - Line 116: Calling $\Delta_S(w)$ "empirical risk" is confusing. It is better to call it "excess empirical risk". - Line 116: "With the optimality" -> "with the suboptimality". - Line 117: Typo in "Leranbility". - Lines 117-118: As I understand from the expectation in between lines 121-122, only deterministic algorithms are considered. Does the main result of Theorem 1 extend to stochastic algorithms? - Just below line 187: it should be $\le$ in the first equation line. - Appendix A. Proof of Theorem 1, first paragraph: It should be $z \in \\{-1/\sqrt{d}, 1/\sqrt{d}\\}$. Also, in "each coordinate z(t) is chosen uniformly" the word "uniformly" should be removed or replaced by "independently". - Lines 200-201: It is clear what is the main message here, but the information-theoretic bound applies to the generalization gap and should not be directly compared with the suboptimality rate. - In equation between lines 212 and 213, it should be $d^{1/7}$. - The CMI bound in eq. (7) instead of $I(w_S; S | Z)$ it should be $I(w_S; J | Z)$ where $J$ denotes the selection variables. Note that $I(w_S; J | Z) = I(w_S; S | Z) + I(w_S; J | Z, S)$ and the last term is not always zero (e.g., when $\mathcal{Z}$ is a finite domain with small size). - Line 282: It should be $O(\sqrt{f(m)/m})$. - Lines 280-286: Subsampling will result in dimension-independent *generalization gap* bounds, but one might not be able to convert that into an excess risk bound. - In a few places throughout the paper we see "true risk", does it refer to the excess risk (suboptimality) or the expected loss? - In the equation below line 315, there should be parentheses for the logarithm to indicate that the $\frac{c^2}{\beta^2}$ part is inside the logarithm.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

See weakness #3.

Summary

The paper shows that there exist stochastic convex optimization problems, which are easy to learn but for which the mutual information based generalization bound of [Xu-Raginsky, 2017] scales at least linearly in the dimension of the parameter space.

Strengths

The paper presents the limitation of mutual information based generalization bound of [Xu-Raginsky 2017] in capturing dimension dependency. The work improves on the previous results of [Haghifam et al 2022] in this respect, in which the lower bound scales logarithmically with dimension and is restricted to gradient descent. I did not carefully check all proofs but they look fine.The results of this paper are original. This work is among the very few that point to the limitations of information-theoretic upper bounds for generalization errors of learning algorithms. Such results are important for the learning theory community to developed improved information-theoretic tools that overcome such limitations. The paper is also very well written. The presentation is clear to this reviewer. The presented results are very well positioned in the related literature.

Weaknesses

NONE

Questions

NONE

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

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

4 excellent

Limitations

NONE

Answer to rebuttal

Thank you for your rebuttal. I agree with the authors that the score given was lower than needed. My main motivation for the score was the lack of a proof of Lemma 3, which in turn was needed to prove Lemma 2, which was needed to prove Theorem 1 (the main result of the paper). Admittedly, having the supplementary material with a different formatting, and a main text very similar to the main text submitted but with some distinctions confused me. It made me look only at the Appendix of the pdf given as the supplementary material. Now I realized that the proof of Lemma 3 **is given** in the main text of the supplementary material, something I missed in the first round. The proof seems correct. This essentially dissipates my main concern. I apologize for missing that and I will take that into account for the final evaluation. Most of my minor issues and questions are also addressed. Some smaller things: * My question and doubts about the CMI subsection remain. Could you discuss them a little further? * I still believe the statement in 174 is overstated. The statement "any algorithm with non-trivial learning guarantees must carry a dimension-dependent amount of information on the sample or require a large sample" seems to imply that this always happens. But it is only shown that there is at least a situation where it happens. To me something of the style "for any algorithm with non-trivial learning guarantees, there is at least one scenario where it must carry a dimension-dependent amount of information on the sample or require a large sample" would represent better the presented result. Do you agree?

Reviewer response

Thank you for the clarifications. I recommend to improve the proof of Theorem 1 in future revisions, especially where Lemma 1 is applied. It should be mentioned that $f$ is a function of not only $z_i(t)$, but also of $z_i(t')$ where $t'\neq t$. Therefore, one has to first fix these other variables, verify that Lemma 1 applies, apply Lemma 1, and then take expectation over $z_i(t')$ and $t$. With these clarifications and corrections in place, this submission is improved and I will adjust my score accordingly.

Thanks for the response

I thank the authors for providing a detailed response. The rebuttal addresses all my concerns, and I would like to increase my score to 6. Although the review process does not allow the reviewer to enforce any required changes, I would like to emphasize that the authors should include the discussion on the Gibbs algorithm and the result of individual samples bound into the final version of the main paper. Also, it would be insightful to add a concluding section to discuss the interpretation of this lower-bound result and possible future directions. I feel that this kind of converse analysis can be very helpful in improving the existing understanding of generalization, and I echo with the author, "The paper does not rule out the possibility of exploiting MI-type bounds in general, but to simply observe that some excess information is necessary for some distributions."