Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization

Thank you for your comments and positive rating.

Weaknesses

"Despite addressing several known counter examples, the interest of the new bounds is only assessed on very simple settings (linear, quandratic)."

We appreciate the opportunity to clarify the motivation and contribution of our paper. Our work focuses on stochastic convex optimization (SCO), a commonly used framework in theoretical machine learning, in particular for rigorously analyzing generalization in overparameterized models. SCO encompasses classical algorithms such as (stochastic) gradient descent, and is not limited to linear or quadratic losses.

Following [42, 43], we considered linear/quadratic losses in order to derive fully explicit and tight bounds. These setups are simple yet nontrivial, and allow for rigorous derivations that reveal concrete insights into generalization, compressibility, and memorization. This strategy allows us to precisely characterize certain phenomena and illustrate our main theorems, which are of the form: there exists an instance in the class of SCO such that the generalization bound exhibits a specific behavior. These examples should therefore be considered as concrete instances where our analysis and discussion apply, rather than as restrictions of the general SCO framework.

That said, linear losses are not the only ones we considered: in Section 4.4, we go beyond them by analyzing generalized linear models, which form a larger, nonlinear class. Given that computations and proofs are already nontrivial in the setings we cover, exploring richer nonlinear instances remains an interesting yet challenging research direction.

"In the abstract, applications to random subspace algorithms, SGD and SGLD are mentioned but these are not discussed in the main text."

Thank you for pointing this out. We will remove the last sentence of the abstract to clarify the main text's content, but we will still refer to these applications at the end of our introduction.

"The main paper ends abruptly"

We will add the following paragraph as a conclusion section at the end of our paper.

"In this work, we revisit recent limitations identified in conditional mutual information-based generalization bounds. By incorporating stochastic projections and lossy compression mechanisms into the CMI framework, we derive bounds that remain informative in stochastic convex optimization, thereby offering a new perspective on the results in [42,43]. Our approach also provides a constructive resolution to the memorization phenomenon described in [43], by showing that for any algorithm and data distribution, one can construct an alternative model that does not trace training data while achieving comparable generalization.

Limitations and open questions. Like prior work on information-theoretic bounds, our analysis applies to stochastic convex optimization. A natural, open question is whether and how these results can be extended to more general learning settings. Another key direction is to translate our theoretical findings into actionable design principles for learning algorithms with controlled generalization and compressibility."

Other remarks

"I think some notations have not been introduced, for instance: $M_1(Z)$."

Thank you for noting this: $M_1(Z)$ denotes the set of probability measures on $Z$. We will precise it in Definition 3.

"Also $A^{(d)}$ has not been defined in theorem 1, is it a typo?"

This is indeed a typo: the correct notation is $\mathcal{A}$.

"When the data distribution $\mu$ depends on $n$, maybe it should be denoted $\mu_n$"

For readability, we chose to omit this dependence in the notation. We acknowledge this may cause some confusion and will thus clarify this choice at the beginning of Section 3.

Questions

the constructed data distribution seems to depend on $n$, which seems restrictive

We agree that this is a relevant question, and note that this restriction is not specific to our work. To the best of our knowledge, there is no counter-example in the literature where the data distribution and dimensionality do not depend on $n$. This dependence seems crucial in existing approaches, including in Attias et al. (2024), where counter-examples involve (C)MI terms that grow with $D$. Intuitively, the higher $D$, the more likely one finds a coordinate that makes the training and test data distinguishable. Therefore, to obtain bounds that shrinks with $n$ increasing, it is typically necessary for $D$ to grow faster than $n$.

Is it also possible to show the same alternate algorithm have similar empirical risk

We can indeed provide additional guarantees on the population risk of the projected-quantized model in Theorem 7. Based on your feedback, we were able to show that for any $r< 1/2$, there exists an auxiliary model $\Theta \hat{W}$ that cannot trace data and such that $|\mathbb{E}\_{P_{S_n,W}P_{\hat{W} | \Theta^T W}}[\mathcal{L}(W) - \mathcal{L}(\Theta \hat{W})] | \leq \mathcal{O}(n^{-r}),$ which is achieved with $d=n^{2r}$.

Alternatively, for any $r\in[R]$, we can guarantee the existence of an auxiliary model $\Theta \hat{W}$ that cannot trace data and satisfies $\mathbb{E}\_{P_{S_n,W}P_{\hat{W} | \Theta^T W}}[\mathcal{L}(W) - \mathcal{L}(\Theta \hat{W})] \leq \mathcal{O}(n^{-r}),$ achieved for $d=r\log(n)$.

The proof closely follows that of Theorem 7, with a slight modification: $\bar{Z}$ is replaced by $Z$, which results in convergence rates roughly $\sqrt{n}$ larger than the current ones. For example, in the first case, this strategy yields $\mathbb{E}\_{\Theta}\big[\big|\mathbb{E}\_{\hat{W}, W, S_n}[\mathcal{L}(W)-\mathcal{L}(\Theta \hat{W})] \big|\big] \leq e^{-0.21 d(1-c_w^2)^2} + \mathcal{O}(d^{-1/2}),$ which is in $\mathcal{O}(n^{-r})$ for $d=n^{2r}$. Furthermore, since $r<1/2$, $\mathsf{CMI}^{\Theta}({\mu},\hat{\mathcal{A}}) \leq d \log\left(\frac{c_w+\nu}{\nu}\right) = o(n)$ which completes the proof.

We thank the reviewer for raising this interesting question, which has helped us extending our results. We will incorporate the above discussion in the paper.

"Is it possible to demonstrate that the new bounds are tightest on a more complex problem class?"

This is a natural and interesting question. Currently, we have not formally established that our bounds are tightest for more complex problem classes beyond those studied in the main text, and we view this as a direction for future work.

That said, despite its simple characterization, we emphasize that stochastic convex optimization already captures relevant aspects for overparameterized models. It also enables nontrivial analytical derivations and encompasses standard algorithms in modern ML (e.g., stochastic gradient descent and accelerated variants). These explain its popularity in theoretical ML research. We refer to [42, 43] for detailed explanations and references.

Regarding memorization (Section 5), we also focused on SCO to allow clear theoretical analysis and to align our setting with that of [43], since our primary goal was to demonstrate the value of incorporating compression in their analysis. Extending both analyses ([43] and ours) to more complex function classes, such as non-convex losses or deep networks, would indeed be a valuable extension.

We thank the reviewer for the positive rating and feedback. We are glad that they enjoyed reading the paper and answer their questions below.

Question 1. This is a good and valid point: one could indeed question whether the fact that our approach yields bounds with the desired behavior truly implies that the limitations are not inherent to the CMI framework, especially given the technical work required to make CMI successful, as the reviewer noted.

Nonetheless, we would like to maintain this claim for two main reasons:

• First, while the machinary of suitable stochastic projection and lossy compression is indeed essential (notably, the way we control simultaneously the projection dimension and incurred distortion in the generalization error of the projected-quantized surrogate model), our final bounds are still within the CMI framework (not from another one).
• Second, although seemingly so, the core analysis is not excessively more complex. In particular, when controlling the distortion $\epsilon$ induced by the compression, we do not need to account for the statistical dependencies between the original model $W$ and the data $S$, which simplifies the bounding steps. We elaborate on this point below.

The main difficulty in bounding the generalization error of stochastic learning algorithms is essentially due to the dependence of $W$ on $S$. Otherwise, bounding the generalization error would reduce to a classical concentration problem, e.g., for a fixed model. A common approach to overcome this difficulty is the change-of-measure trick, which comes at the expense of, e.g., a KL-divergence term. MI and CMI bounds fall into this category of approaches.

Our general framework consists of two main steps: i) we apply projection-quantization to the original model and study the induced distortion, then ii) we study the generalization error of the projected-quantized model.

Step i: We consider the expected difference of the generalization errors for $W$ and $\Theta \hat{W}$. Since we construct $\hat{W}$ suitably from $\Theta^\top W$, we do not need to account for the dependence between $W$ and $S$ at this stage. Instead, the analysis involves developing expected concentration bounds by taking expectations over three sources of randomness: the projection matrix ($\Theta$), quantization noise ($V_{\nu}$, see l. 1076), and the empirical deviation of the distribution of $S$ from $\mu$. As shown in the proofs, the analysis of the distortion term often reduces to classical concentration problems with well-known (near)-tight bounds.

Step ii: We then consider the joint distribution of $(S,\Theta \hat{W})$, and leverage CMI to establish generalization bounds. Projection-quantization reduces the dependence between the model and training data.

In short, our approach decomposes the generalization error into two components, where the first can often be bounded near-optimally using classical concentration techniques.

That said, we agree with the reviewer that the statement that our claim "the aforementioned limitations are not inherent to the CMI framework" may be questioned by readers, so we will add this discussion to clarify this point accordingly.

Question 2. Theorem 4 is primarily given to show that there are no counterexamples to our extended CMI bound of Theorem 1, not even within the broader class of generalized linear stochastic optimization. Regarding the order of the bound in Theorem 4, we acknowledge that it is likely suboptimal and conjecture that a refined analysis could achieve a rate of $\sqrt{\log(n)/n}$. The intuition is as follows.

As stated in our response to Question 1, analyzing the distortion requires bounding some expectations over the randomness on the projection-quantization and the dataset. However, the current distortion analysis in the proof of Theorem 4 only averages over the projection-quantization randomness and considers the worst-case scenario among all data samples. We think that a more refined analysis, which incorporates a concentration bound related to the deviation of empirical distribution of $S$ from $\mu$, could lead to a better rate. We will include this discussion in the paper.

Question 3. This is actually a typo: $W$ should read $\Theta \hat{W}$. Thank you for pointing it out.

On the extension to other variants of CMI: Thank you for these suggestions and for pointing us these additional references. We agree that the wording in our introduction lacks precision, and we understand it may overstate the scope of our results. As you correctly note, our intention was to emphasize that Theorem 1 improves upon standard CMI bounds. We did not mean to imply that it dominates all the proposed variants, especially since, to the best of our knowledge, those approaches have not been explicitly shown to fail on the counterexamples of Attias et al. (2024) and Livni (2023).

We will thus revise the introduction accordingly. More precisely, we will clearly state that our bound improves on standard hypothesis-based CMI bounds in a provable sense; acknowledge that other CMI variants, such as those you referred in [1–4] are not directly addressed in our paper.

Limitations: Indeed, the CMI framework applies to parameterized models. We will add this potential limitation in the checklist.

Thank you for your careful reading and positive rating. We are grateful for your detailed comments in the 'Pros' section, and your appreciation of our results and discussion.

"Section 5, Memorization, is very interesting. However, packing it all into 2 pages ... just feels like too much."

We acknowledge that Section 5 is dense, and we have revised it to improve readability. Based on your comment, we made the discussion after Lemma 1 more concise and to the point (see details below). Additionally, we have shortened Section 4.4 and move part of its content to the appendix. This allows us to add more background on the recall game. We hope these changes improve clarity, and we would be happy to receive any further suggestions you may have on this section.

"after Lemma 1, there is a confusing sentence"

The reviewer's interpretation is correct, and we agree that sentence could be much clearer. We also agree that the first three cases are trivial. These were included for two reasons: to provide simple examples of the recall game that help readers build intuition; to emphasize that considering the soundness or recall criterion alone is not sufficient. For instance, it is possible to achieve either $\xi = 0$ or $q = 1$, or both small $\xi$ and large $q$ when $m=o(n)$. Therefore, an adversary is considered good if it achieves a small $\xi$ or large $q$ simultaneously, with a non-negligible value of $m$.

Regarding (iii), stating $\xi \geq q$ is "achievable" is highlighted because Theorems 6 and 7 show that when $m$ is not $o(n)$ and $\mathsf{CMI}(\mu,{\mathcal{A}_n}) = o(n)$, no adversary can outperform a "dummy" adversary.

Based on your feedback, we will thus rephrase lines 333-339 as follows: "In particular, Lemma 1 shows that even a dummy adversary can $(m,q,\xi)$-trace the data in several cases: when $\xi$ is small, when $q$ is large, when $\xi \geq q$, or when $\xi$ is small $q$ is large, provided that $m=o(n)$ and there exists a subset $\mathcal{B}\subseteq \mathcal{W}$ such that $\mathbb{P}\left(W \in \mathcal{B}\right)=1-\xi$. Hence, $(m,q,\xi)$-memorization does not always translate ... "

Minor comments: Thank you for your thorough comments: we have corrected the typos in l.96 and 275, and we provide further clarifications on your other points below.

"In Theorem 1, it may be helpful to explicitly clarify that $W | \tilde{\mathbf{S}}$ means that $W$ is trained on the entire double sample $\tilde{\mathbf{S}}$"

This notation actually refers to a random variable drawn from the conditional distribution $P_{W | \tilde{\mathbf{S}}} = \mathbb{E}_{P_{\mathbf{J}}}[P_{W |\tilde{\mathbf{S}}_\mathbf{J}}]$ (as in l.1055). Therefore, $W$ is in fact trained on $n$ samples (not $2n$). We thank you for pointing out this ambiguity, and will clarify it in the statement of Theorem 1.

"In the statement of Theorem 1, first math display, the notation $\mathcal{A}^{(d)}$ was never defined."

While your interpretation of $\mathcal{A}^{(d)}$ is correct (see the definition in Section B, l.941), it should not appear in Theorem 1: the correct notation here is $\mathcal{A}$. We have now fixed it. We emphasize that this typo does not affect our results and conclusions.

Questions:

1. Thank you for pointing this out, we realize that our writing was ambiguous. There are two sources of distortion in our framework: (i) the (stochastic) projection from a high- to low-dimensional space, which is inherently lossy, (ii) a second, intentional lossy compression step applied after projection.

   The reason for step (ii) is that, in order to control the distortion introduced by step (i) (projection), we follow a standard approach inspired by lossy source coding. This helps us obtain quantized representations that are easier to analyze and leads to tighter bounds. This procedure is analogous to $\epsilon$-net covering.

   We will revise l.234-235 as follows: "Since this dimension reduction technique is lossy, controlling the induced distortion is essential. To do so, we introduce an additional lossy compression step by adding independent noise in the lower-dimensional space. This approach is inspired by lossy source coding and allows us to obtain tighter bounds on the quantized, projected model."

2. Your interpretation aligns with ours. Our results show that an adversary's ability to memorize or trace training data from the learning model does not necessarily imply poor generalization: one can construct a quantized, projected representation of the model with similar generalization error that does not memorize the data.

3. Indeed, we have fixed the typo, thank you!

4. Thank you for your careful reading: we meant the discretized model, so $W$ should be replaced by $\Theta \hat{W}$ in Theorem 7(ii). We have corrected this typo.

Thank you for your feedback and positive evaluation: we appreciate you find our approach novel and sound. We have corrected the identified typos.

"Illustrations could have been helpful to help understanding the main concepts (MI, CMI, J, projection and Θ, lossy compression)."

We agree that illustrations could help clarify these concepts, and observe that such visual aids are generally lacking in the existing literature. If the paper is accepted we will add a diagram that depicts pictorially our approach, i.e., stochastic projection onto a smaller dimension space followed by lossy compression that preserves the generalization; and, on top of all the CMI framework.

"there is no conclusion"

We will add the following paragraph as a conclusion section at the end of our paper.

"In this work, we revisit recent limitations identified in conditional mutual information-based generalization bounds. By incorporating stochastic projections and lossy compression mechanisms into the CMI framework, we derive bounds that remain informative in stochastic convex optimization, thereby offering a new perspective on the results in [42,43]. Our approach also provides a constructive resolution to the memorization phenomenon described in [43], by showing that for any algorithm and data distribution, one can construct an alternative model that does not trace training data while achieving comparable generalization.

Limitations and open questions. Like prior work on information-theoretic bounds, our analysis applies to stochastic convex optimization. A natural, open question is whether and how these results can be extended to more general learning settings. Another key direction is to translate our theoretical findings into actionable design principles for learning algorithms with controlled generalization and compressibility."

"To what extent can the bounds be evaluated (e.g., plotted) and used to design new algorithms?"

Please note that our CMI-based generalization bounds are primarily intended as diagnostic tools. A direct major utility of them is to uncover which properties of learning algorithms lead to generalization. But they can of course also be used in the construction of suitable regularizes for new algorithms that are generalization-aware (similar to in [45]). On this latter aspect, we mention that some estimation strategies have been proposed in prior art that can be applied within our framework. For example, the CMI term can be upper-bounded by the KL divergence between the conditional distribution of the parameters given the data and a prior [38] or, for countable hypothesis spaces, by a deterministic (but potentially loose) quantity [§4.1, 10] (see our Section D.2).

We thank the reviewer for the positive feedback and relevant suggestions. As requested, we clarify our contributions and how we think should be positioned with respect to prior work.

For convenience, this is a summary of our formal claim and how it reconcilies with the impossibility results of Attias et al. (2024). Details will follow.

Our proof of Theorem 7 actually allows two forms for the statement of the result: one that is explicit (the current one), and one that is implicit and can easily be implied by the very same proof. The two statements differ among them through the degree of algorithm randomness that is shared with the adversary and the order of quantifiers.

• The current statement of Theorem 7 holds for $\Theta$ being deterministic and shared with the adversary. It asserts that for any learning algorithm $\mathcal{A}(S)=W$ and data distribution $\mu$, there exists a suitable projected-quantized model $\hat{\mathcal{A}}(S,\Theta)=\Theta \hat{W}$ for which no adversary would be able to trace the data. As correctly observed by the Reviewer, this statement indeed does not preclude the existence of data distributions and adversaries which would be able to trace that data from the output of the new algorithm $\hat{\mathcal{A}}(S,\Theta)=\Theta \hat{W}$. Note, however, that the impossibility result of Attias et al. does not apply to the new algorithm $\hat{\mathcal{A}}(S,\Theta)$ (see below); and, so, while our result of Theorem 7 in its current form does not rule out the existence of such distributions and adversaries for the new algorithm $\hat{\mathcal{A}}(S,\Theta)$, that of Attias et al. does not guarantee that existence either.
• Easily implied by the very same proof, a second form of Theorem 7 holds for $\Theta$ being random and shared with the adversary (not deterministic as for the current statement!); and its statement is exactly that of the current one but with an added extra expectation over the projection matrix $\Theta$ in the LHS of the inequality (6) -- See the section Randomized projections and quantization below). This alternate form of statement of Theorem 7 asserts that if for a given $W$ a random $\Theta$ is chosen and revealed to the adversary, then the projected-quantized model which uses that $\Theta$ guarantees that: (i) for any data distribution, no adversary can trace the data; and (ii) on average over $\Theta$, the corresponding generalization error is comparable to that of the original model $W$. This means that the order of quantifiers here is the same as for the impossibility result of Attias et al. (2024).

We hasten to mention that none of these two forms of statement contradicts the impossibility result of Attias et al. (2024). This is because the result of Attias et al. does not apply to our projected-quantized algorithm $\hat{\mathcal{A}}(S,\Theta)$. In particular, athough equally universal the seemingly contracting above alternate statement of Theorem 7 does actually not contradict the impossiblity result of Attias et al. (2024). More precisely, their main assumption on the boundednes of model's norm (used in the proof of their Theorem 4.1, e.g., right before equation (12) in the PMLR version of their paper) would require that $\mathbb{E}\left[\|\Theta \Theta^\top W\|^2\right]=\frac{D+d+1}{d}\|W\|^2 \leq 1$, which cannot be statisfied with a dimension $D$ that grows with $n$ as $O(n^4 \log n)$. The same argument holds for the current statement of Theorem 7.

If the reviewer agrees with, we will keep the statement of Theorem 7 as is but add in the revised paper a discussion on the order of quantifiers and relation to Attias et al., as well as how a slightly modified form of the statement can be inferred from the very same proof but with a result that holds with the same universality as Attias et al. (2024) and, finally, how/why the result of Attias et al. (2024) applies to none of the two versions of statement.

On the formal claim, order of quantifiers, and disclosure of the randomness of the algorithm: Thank you for taking the time to carefully read our paper and write thorough comments. Regarding the randomness, in addition to the standard randomness already present in the process of learning from samples, our method introduces two further sources of randomness: the stochastic projection matrix $\Theta$ and the quantization noise (the random variable $V_{\nu}$, see l.1076). Depending on whether these sources are fixed and shared with the decoder or not, Theorem 7 can be stated in slightly different ways, resulting in distinct levels of generality:

• Partially deterministic (deterministic projection and random quantization): Theorem 7, as stated now, assumes a fixed projection matrix $\Theta$ that is known to the adversary, in addition to a random (quantization noise) $V_{\nu}$ which is unknown to the adversary. The randomness on $V_{\nu}$ is used merely to properly quantize the projected hypothesis space, as is common in rate-distortion theory literature. Alternatively, one could use a "fixed" quantization technique similar to $\epsilon$-net covering in order to map the projected models to the closest points on the $\epsilon$-net mesh. However, there would still exists some level of randomness that is unknown to the adversary (related to how such a mapping is performed as the adversary only observes the centroid points on the $\epsilon$-net). We note that even with common learning algorithms (i.e., in the absence of any stochastic projection and/or lossy compression, such as using standard mini-batch SGD), there are sources of randomness (related, e.g. to the choices of mini-batch size, initialization, and other choices) that are unknown to the adversary.

  For this setting, we show that for any learning algorithm $\mathcal{A}(S)=W$ and data distribution $\mu$, there exists a suitable projected-quantized model $\hat{\mathcal{A}}(S,\Theta)=\Theta \hat{W}$ for which no adversary can trace the data. Such statement indeed does not preclude the existence of data distributions and adversaries which could trace some amount of the data by directly observing the output of the new algorithm $\hat{\mathcal{A}}(S,\Theta)=\Theta \hat{W}$. However, as we argue (see the argument in the above summary in the beginning of this response) the impossibility result of Attias et al. does not apply to this new algorithm $\hat{\mathcal{A}}(S,\Theta)$.

• Randomized projections and quantization: In the actual proof of Theorem 7, we begin by establishing a version of the inequality (6) that holds in-expectation over $\Theta$. Namely, the same inequality (6) but with an extra expectation over $\Theta$ in the LHS of the inequality (and, actually, this is the exact argument that we then use to infer the existence of at (least) one value of $\Theta$ for which the inequality holds without the expectation).

As a result, Theorem 7 also holds if $\Theta$ is randomly generated and revealed to the adversary (provided that one adds the mentioned extra expectation over $\Theta$ in the LHS of (6)). For this setting (i.e., for a given $W$, a random $\Theta$ chosen and revealed to the adversary) we get that the projected-quantized model which uses that $\Theta$ guarantees that: (i) for any data distribution, no adversary can trace the data; and (ii) on average over $\Theta$, the corresponding generalization error is comparable to that of the original model $W$.

This new statement makes the claim more general and somewhat similar to that of Attias et al. in its universality (which it does not contradict, as explained above), but at the expense of more randomness in designing the learning algorithm.

We will add these discussions to avoid any confusion.

On the terminology usage "tracing vs. memorizing the data:" Indeed; it would be better to refer to the adversary as being able to "trace or not trace" the data instead of it memorizing or not that data. We will revise the document using this terminology, which is better.

On the relation to the prior art ICML 2020 paper "In Defense of Uniform Convergence: Generalization via Derandomization with an Application to Interpolating Predictors": Thank you for pointing out to us the connection with this work, which we were not aware of. In that work, the generalization error of an algorithm is studied indirectly using a "surrogate algorithm" and by controlling the distortions induced for the population and empirical risks, in a way that is essentially similar to lossy compression in rate-distortion theory. Note that although there is indeed a high level connection, in our case: (i) the surrogate or lossy algorithm is achieved through suitable stochastic projection (onto a proper smaller dimension space) followed by quantization, not just lossy compression, (ii) the quantization is a very careful one, chosen in a manner that the generalization error of the surrogate algorithm has comparable generalization error with the original algorithm, and (iii) we accomodate the CMI framework to the used stochastic projection and lossy compression. Nontheless it is indeed useful to the reader to reference this paper, which we will do; and discuss relationship to our work.

On the order of dimension: In the latest version of the PMLR paper by Attias et al. (2024), the condition is written as $n^4\log(n)$. However, as the reviewer mentioned, this ordering does not affect our results.

Regarding the practical method for constructing the model: The reviewer is right. However, it should be noted that similar high-probability bounds also hold for the used Johnson-Lindenstrauss projection. This means that if we take a random matrix $\Theta$ whose entries are chosen i.i.d. from the distribution $\mathcal{N}(0,1/d)$ then, with high probability, the new algorithm will have comprable generalization error to that of the original algorithm.