acceptodds
Under review as a conference paper at ICLR 2027

A Unified Framework for Change of Measure Inequalities: Applications to Generalization, Memorization and Privacy

Abstract

Change of measure inequalities translate divergences between probability measures into explicit bounds on event probabilities, and play an important role in deriving probabilistic guarantees in learning theory, information theory, and statistics. We propose novel change of measure inequalities via a unified framework based on the data processing inequality, which is surprisingly elementary yet powerful enough to yield novel, tighter inequalities. We provide change of measure inequalities in terms of a broad family of information measures, including -divergences (with Kullback-Leibler divergence and -divergence as special cases), R\'enyi divergence, and -mutual information (with maximal leakage as a special case). We apply these results to generalization error analysis, PAC-Bayesian theory, differential privacy, and data memorization, obtaining stronger guarantees while recovering best-known results through simplified analyses.

Primary area:
learning theory
Keywords:
Generalization error, change of measure inequalities, information theory, f-divergence, PAC-Bayesian

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_MyoSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a unified framework for deriving change of measure inequalities via the data processing inequality (DPI) applied to an indicator channel. The framework is applied to generalization error analysis, PAC-Bayesian theory, and data memorization.

Critical strengths
  • The proposed framework avoids complex variational representations by reducing the problem to the DPI of a Bernoulli channel, mathematically simplifying the derivations.
  • The exact event-DPI relations (e.g., for the hockey-stick divergence) yield tighter theoretical bounds than the classical strong converse lemma.
Critical weaknesses
  • Although the authors claim that their scheme "eliminates the parameters... that can be hard to optimized" compared to Picard-Weibel & Guedj (2022), the derived KL divergence bound in Eq.10 still introduces an auxiliary parameter c>0c>0. The authors fail to theoretically justify why optimizing this new parameter c in practice is fundamentally easier than tuning the parameters in existing variational approaches.

  • In Theorem 4.2, the authors do not provide any guidance on how to constructively find or approximate the optimal Orlicz function ψ\psi in practical learning algorithms. This renders the theorem computationally infeasible in practice. -In Eq (24), the parameter M≤1/P(E)−1M \le 1/P(E) - 1 inherently depends on the unknown target test probability P(E)P(E). Although the authors attempt to remedy this flaw by setting a hard cutoff value QmaxQ_{max}, this ad hoc truncation appears quite hasty.

  • The authors show that the proposed bounds are only evaluated on a toy Gibbs learner (n=50) and a synthetic Gaussian setup. However, they fail to prove whether these DPI-derived bounds become vacuously loose when applied to high-dimensional real-world datasets and deep neural networks.

Questions for authors

Please refer to the Weaknesses

5 comments
AuthorsOpenReview ↗

Clarifications on Theoretic Contributions

We thank the reviewer for recognizing the simplicity of our DPI approach and its improvements over existing inequalities through simpler derivations. We agree that several statements regarding optimization and practical applicability should be more carefully qualified. We have used the permitted additional page to further clarify and strengthen the manuscript, with all changes highlighted in blue. We provide detailed responses to the reviewer's comments below. We hope that our revisions and responses adequately address the reviewer's concerns, and we would be grateful if the reviewer could consider increasing their rating accordingly.

The KL bound has a parameter cc (Weakness 1). This observation is correct. Eq. (10) has a form involving parameter cc, same to Picard-Weibel and Guedj (2022). However, we note that this is the only inequality in our paper that involves such a free parameter. Compared with existing approaches, the advantage of our derivation lies in its simplicity: the Bernoulli reduction gives a direct one-dimensional characterization via the upper Bernoulli-KL envelope sup⁡{p∈[q,1]:kl(p∥q)≤DKL(P∥Q)}\sup\{p\in[q,1]: kl(p\Vert q)\leq D_{\mathrm{KL}}(P\Vert Q)\} for 0<q<10<q<1. The approach is a transparent scalar calculation, and only in the KL and χ2\chi^2 cases do we match the existing inequalities, while in the other cases our simple DPI approach yields tighter inequalities (please refer to Table 1). We have removed the overbroad "eliminates the parameter" claim and will acknowledge this.

Choice of the Orlicz function (Weakness 2). We thank the reviewer for raising this point. Theorem 4.2 is intended as a flexible family of sufficient inequalities rather than a claim that one can efficiently optimize over the entire infinite-dimensional class of Orlicz functions. In practice, one can restrict to familiar parametric subclasses chosen according to the available moment or tail information. We kindly point out that this constructive viewpoint is already partially present in the manuscript: Lemma D.1 notes that power Orlicz functions recover the standard H"older inequality; Theorem D.2 develops a further two-Orlicz generalization of Theorem 4.2; Appendix E.3-E.4 uses a power-Orlicz choice to derive the Sibson α\alpha-mutual-information bound; and Appendix G applies Theorem 4.2 in the CMI setting. We will make this practical interpretation more explicit and visible in the main sections.

A concrete example may help clarify this point. Let β>1\beta>1, r=β/(β−1)r=\beta/(\beta-1), and choose ψ(t)=trr\psi(t)=\frac{t^r}{r} and ψ⋆(u)=uββ\psi^\star(u)=\frac{u^\beta}{\beta}.

Writing L=dP/dQL=dP/dQ and q=Q(E)q=Q(E), the two norm factors in Theorem 4.2 can be evaluated explicitly:

1ψ−1(1/q)=(qr)1/r,\frac{1}{\psi^{-1}(1/q)}=\left(\frac{q}{r}\right)^{1/r}, and ∥(L−γ)+∥ψ⋆A,Q=r1/r(EQ[max⁡L−γ,0β])1/β.\Vert (L-\gamma)_+\Vert _{\psi^\star}^{A,Q} = r^{1/r} (\mathbb{E}_Q [ \max\\{L-\gamma,0\\}^{\beta}] )^{1/\beta}.

Hence, Theorem 4.2 reduces exactly to the standard Hölder-type specialization:

P(E)≤γQ(E)+Q(E)(β−1)/β(EQ[max⁡dP/dQ−γ,0β])1/β,γ∈R.P(E)\leq\gamma Q(E)+Q(E)^{(\beta-1)/\beta}\left(\mathbb{E}_Q\left[\max\\{dP/dQ-\gamma,0\\}^{\beta}\right]\right)^{1/\beta},\qquad \gamma\in\mathbb{R}.

This is essentially the same power-Orlicz mechanism already used in Appendix E at γ=0\gamma=0, while keeping γ\gamma free provides an additional computable refinement. For every fixed β>1\beta>1 for which the required β\beta-th moment is finite, the right-hand side is a convex function of γ\gamma: indeed, γ↦(L−γ)+\gamma\mapsto(L-\gamma)_+ is convex, and its Lβ(Q)L^\beta(Q) norm preserves convexity by monotonicity and Minkowski's inequality. Thus the optimal γ\gamma can be obtained by a one-dimensional convex optimization, while β\beta can be selected over a finite grid or by a one-dimensional numerical search. This provides a concrete and tractable specialization of Theorem 4.2 without claiming that optimization over all possible Orlicz functions is computationally tractable.

The parameter MM in Eq. (24) and the cutoff u0u_0 in Eq. (25) (Weakness 2). We agree that the assumption P(E)≤1/(M+1)P(E)\leq1/(M+1) used to display Eq. (24) should not be treated as directly verifiable when P(E)P(E) is the unknown quantity. The subsequent Eq. (25), however, does not rely on an arbitrary cutoff. For β>1\beta>1, put p=P(E)p=P(E), q=Q(E)q=Q(E), and A=1+(β−1)Hβ(P∥Q)A=1+(\beta-1)H_\beta(P\Vert Q). The Bernoulli-DPI inequality is pβq1−β+(1−p)β(1−q)1−β≤Ap^\beta q^{1-\beta}+(1-p)^\beta(1-q)^{1-\beta}\leq A. Dropping the nonnegative complementary-event term first yields the proved upper bound p≤u0:=min⁡1,(Aqβ−1)1/βp\leq u_0:=\min\\{1, (Aq^{\beta-1})^{1/\beta}\\}. Hence (1−p)β≥(1−u0)β(1-p)^\beta\geq(1-u_0)^\beta, and substitution into the original inequality gives

\Bigl(A-(1-u_0)^\beta(1-q)^{1-\beta}\Bigr)\right]^{1/\beta}.$$ Thus, $u_0$ is a computable consequence of the DPI bound, not a heuristic truncation or a parameter that must be fitted using the unknown $p$. The refinement may become uninformative when $u_0=1$; we will state this explicitly in the updated manuscript.
AuthorsOpenReview ↗

New Experimental Evidence and Summary

Practical significance and Experimental Evidence (Weakness 3)

We thank the reviewer for highlighting the need to test whether the DPI refinements remain informative beyond our two analytical examples. Although we would like to note that our contribution is mainly theoretical (similar to the closest work, Picard-Weibel and Guedj (2022)), we have now conducted additional experiments on real data. This part, together with visualizations in figures, has been added to our submitted manuscript (see Page 10).

We show our bounds are nonvacuous and can be tighter than existing bounds on high-dimensional real-world datasets and deep neural networks. We use MNIST/LeNet and CIFAR-10/ResNet-18, with Gaussian randomized predictors. For the most extensive CIFAR-10 study, the ResNet-18 feature extractor is trained on an independent prior-data split; a Gaussian posterior over its 5130-dimensional classification head is then optimized using the remaining n=37500n=37500 examples, explicitly regularizing posterior--prior divergence.

Non-vacuous PAC-Bayes Bound. On the ResNet experiment, Corollary 5.2 yields non-vacuous population-risk upper certificates for all 432432 trained posterior configurations. The best bound across the three seeds are 27.1127.11\\%, 29.6129.61\\%, and 29.2629.26\\%, establishing non-vacuity on a trained deep-network representation, and improves Ohnishi--Honorio power-divergence bound on some configurations.

Strict improvements. For a fixed sample ss, let Es=w:∣gen(s,w)∣≥ηE_s=\\{w:|\mathrm{gen}(s,w)|\geq\eta\\}, ps=PW∣s(Es)p_s=P_{W|s}(E_s), and qs=π(Es)q_s=\pi(E_s) for the independent prior π\pi. By our bound, at η=0.014\eta=0.014 the exact power-divergence relation gives non-vacuous upper bounds of 2.712.71\\%, 2.762.76\\%, and 2.622.62\\% across the three seeds. For my seed 0, the explicit retained-complement refinement gives 2.742.74\\%, compared with 3.343.34\\% for the optimized classical Rényi/Hölder relaxation using the same power divergence, a 17.917.9\\% relative reduction. Separately, at η=0.10\eta=0.10, the optimized hockey-stick bound gives 5.5535.553\\%, 5.1935.193\\%, and 0.9870.987\\%, versus 5.8455.845\\%, 5.4705.470\\%, and 1.0551.055\\% for the classical strong-converse relaxation, corresponding to relative reductions of 5.05.0--6.56.5\\%.
The figure in Page 10 of the updated manuscript summarizes these comparisons.

Summary of our response

We sincerely thank Reviewer MyoS again for the careful and constructive feedback. In response, we have substantially revised the manuscript to clarify the precise novelty and scope of our DPI framework, distinguish new results from classical special cases, provide constructive interpretations of the Orlicz bound, and clarify the roles of the auxiliary parameters. Importantly, we conducted new experiments on MNIST/LeNet and CIFAR-10/ResNet-18, demonstrating that our bounds can remain non-vacuous on real deep-learning problems and that the retained-complement power-divergence and hockey-stick bounds can be strictly tighter than their corresponding classical relaxations.

We believe these revisions address the reviewers' main technical and presentation concerns and substantially strengthen both the theoretical positioning and practical evidence of the paper. We remain confident in the value of the work and would be very grateful if the reviewer could kindly reconsider the evaluation in light of these clarifications, corrections, and new results! Thank you for your time!

Reviewer_MyoSOpenReview ↗

Response

Thank you for the detailed clarifications—my main concerns have been addressed. I have another question: can this generalization analysis be applied to DNNs, particularly when training dynamics are taken into account? And do the theoretical results provide new insights into how to control the generalization behavior of DNNs?

Reviewer_LkauOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper provides a unified framework for obtaining information-theoretic change of measure results. It uses the data processing inequality (DPI) to relate ff-divergence between two measures PP and QQ to a ff-divergence between event probabilities. It also presents applications for learning theory, including generalization and memorization.

Critical strengths

Application of Equation (10) to obtain a stronger result than Fano-type weakening of Bernoulli divergence for memorization is a good point, which is less used in the literature. Further, the improvement when CMI vanishes is the most interesting point of the paper.

Critical weaknesses

Using event indicator in DPI is a well-established trick in information theory and statistics. Just to name a few: it was used in proving Fano inequalities and its generalizations such as metric Fano, also used in the weak converse proof of Stein exponent for hypothesis testing (see for example, Polyanskiy and Wu), it was also used with Renyi divergence to prove the strong converse proof. From an information theoretic point of view this paper has little novelty.

The applications, except for the memorization aspect, lack fascination. They yield results that are comparable to those already established in the literature and fail to introduce novel valuable insights or techniques for investigating generalization and privacy.

Questions for authors
  1. In the context of generalization bounds, how do the bounds in equation (18) compare to the mutual information bound and the CMI? When do these bounds significantly outperform the CMI?

  2. Since the first part of the paper consider general f-divergence, I am curious about the significance of using general f-divergence rather than usual KL, Hellinger and \chi^2. In this regard I have two questions:

    • In the context of generalization bounds, how do the bounds in equation (18) compare to the mutual information bound and the CMI? When do these bounds significantly outperform the CMI?
    • In the context of memorization, the author employed a metric Fano-type inequality. Can other f-divergences outperform the standard KL-divergence significantly in this scenario?
4 comments
AuthorsOpenReview ↗

Clarifying the Contributions, Novelty and MI/CMI Bounds

We thank the reviewer Lkau for the technically detailed assessment, and especially for recognizing the contribution of retaining the Bernoulli-KL constraint in the memorization result.
We agree with the historical point: applying DPI to an event indicator is an established technique in information theory. Our claim is not that this reduction itself is new, as we already acknowledge in the paper. Rather, we would like to highlight how the exact Bernoulli event constraint provides a unified and simple route to change-of-measure inequalities: for example, it can recover/improve/ bounds by Picard-Weibel and Guedj (2022) through substantially simpler analysis, while applying naturally to generalization, privacy, and memorization. Beyond this unifying perspective, we provide new retained-complement refinements and an event-level optimality characterization, and we numerically demonstrate that these bounds can remain non-vacuous and yield strict improvements in deep neural network with real data.

We provide detailed responses to the reviewer's comments below. We have also used the permitted additional page to further clarify and strengthen the manuscript, with all changes highlighted in blue.

Novelty: What is new beyond the DPI trick?

1. Optimality of Bernoulli Reduction. Let p=P(E),q=Q(E)p=P(E), q=Q(E). For Gf(p,q):=qf(p/q)+(1−q)f((1−p)/(1−q))G_f(p,q):=qf(p/q)+(1-q)f((1-p)/(1-q)), the indicator-DPI gives Gf(p,q)≤Df(P∥Q)G_f(p,q)\leq D_f(P\Vert Q). Our point is to retain this exact constraint rather than immediately relax one of its two terms, which is what existing literature does. In Section 4.1 we show that, once the observable of interest is the event EE, this Bernoulli reduction is optimal within the corresponding event-measurable variational class. This gives a direct route for recovering the approaches of Picard-Weibel and Guedj (2022) and Esposito et al. (2021) as we showed in Page 5, but through a scalar Bernoulli calculation rather than the full variational machinery. To the best of our knowledge, this explicit optimality characterization is new.

2. New PAC-Bayesian bound. Corollary 5.2 gives a new PAC-Bayesian bound obtained from our DPI approach. Its dependence on the power-divergence complexity is logarithmic, and Section 5.3 identifies explicit finite-sample regimes in which it is strictly tighter than the existing Ohnishi--Honorio power-divergence bound.

3. New Approximate-DP Generalization Bound. The privacy section also contains new consequences. Using approximate max-information control for (ϵ,δ)(\epsilon,\delta)-DP algorithms, Proposition 6.3 converts this control into a finite Eγ(PSW∥PSPW)E_\gamma(P_{SW}\Vert P_SP_W) bound. Combining this with our the hockey-stick inequality from DPI, it yields the explicit high-probability generalization guarantee for approximate-DP algorithms stated immediately after Proposition 6.3.

4. Memorization. We agree with the reviewer that this is the clearest application-level novelty of the paper. Theorem 7.1 strengthens Sefidgaran et al. (2025, Theorem 5(ii)) by retaining the full Bernoulli-KL constraint rather than applying a Fano relaxation. In particular, when the CMI vanishes, the selector-recovery envelope removes the Θ(1/n)\Theta(1/n) Fano slack, and under sublinear CMI our theorem yields P(Fn>βn)≥q−o(1)P(F_n>\beta n)\geq q-o(1) for any β<α\beta<\alpha, which gives a strictly stronger asymptotic false-positive conclusion than the previous result. We have substantially revised the memorization section in the main paper to make it more visible and better presented.

We will further revise the presentation to clearly separate the classical ingredient from the contributions of the paper, and to highlight the new results in the paper, together with the newly added experimental results on deep neural networks with real data (Page 10).

Compare to MI/CMI Bounds (Question 1)

For the event Eη=(s,w):∣gen(s,w)∣≥ηE_\eta=\\{(s,w):|\mathrm{gen}(s,w)|\geq\eta\\}, take P=PSWP=P_{SW}, Q=PSPWQ=P_SP_W, and qη=Q(Eη)q_\eta=Q(E_\eta). We have

\leq D_{\mathrm{KL}}(P_{SW} \Vert P_SP_W)=I(S;W)$$ where $kl(p \Vert q)=p\log(p/q)+(1-p)\log[(1-p)/(1-q)]$. Consequently, for $0<q_\eta<1$, the exact event-level upper envelope is $$P(E_\eta)\leq\sup\\{u\in[q_\eta,1]:kl(u \Vert q_\eta)\leq I(S;W)\\}.$$ The Fano-type relaxation, $kl(p \Vert q)\geq p\log(1/q)-\log2$, instead yields $$P(E_\eta)\leq\min\left\\{1, \frac{I(S;W)+\log2}{\log(1/q_{\eta})}\right\\}.$$ With the same MI budget, direct binary-KL inversion cannot be weaker than this particular relaxation. \ For CMI bounds, in Appendix G, we already provide a new CMI-based result of the Orlicz constructio. We do not claim a universal improvement over CMI bounds. In the revised manuscript, we have evaluated our bounds (e.g., Eq. (18)) on deep neural networks with real data to show that they are non-vacuous and can be tighter than existing bounds. Though we do not claim that our approach dominates CMI, we will also numerically compare with CMI bounds.
AuthorsOpenReview ↗

New Memorization Results and Conclusion

Can other ff-divergences improve the memorization bound? (Question 2)

Yes, although an important qualification is that there is no universal dominance across different information measures. If only a KL/CMI budget is known, replacing KL by a higher-order divergence generally requires stronger information about the learner. Our main memorization result therefore uses KL/CMI, for which such control is naturally available. Nevertheless, when other ff-divergences can be controlled, the same Bernoulli-DPI framework can yield qualitatively stronger selector-recovery guarantees.

To make this concrete, consider the supersample setting of Appendix N: let qt=2−n∑j=0⌊nt⌋(nj)q_t = 2^{-n}\sum_{j=0}^{\lfloor nt\rfloor}\binom{n}{j} for 0≤t<120\leq t< \frac{1}{2}, which is the probability that an independent uniform selector lies in a Hamming ball of radius ntnt. Let ptp_t denote the corresponding selector-recovery probability under the coupled learner--selector law. For every ff-divergence that can be controlled, our DPI framework directly gives Gf(pt,qt)≤Df(P∥Q)G_f(p_t,q_t)\leq D_f(P\Vert Q).

An example shows that the choice of divergence can change the rate substantially. Suppose the learner memorizes exactly the first k≥1k\geq1 selected training samples, with kk fixed as n→∞n\to\infty, and suppose the data distribution is continuous so that the samples identify the corresponding selector bits almost surely.

Let P0=PWZ~JP_0=P_{W\widetilde ZJ} and Q0=PZ~PW∣Z~PJQ_0=P_{\widetilde Z}P_{W|\widetilde Z}P_J. Under Q0Q_0, the likelihood ratio L=dP0/dQ0L=dP_0/dQ_0 satisfies

\begin{cases} 2^k, & \text{with $Q_0$-probability }2^{-k},\\\\ 0, & \text{otherwise}. \end{cases}$$ Consequently, $$\begin{aligned} D_{\mathrm{KL}}(P_0\Vert Q_0) &=k\log 2,\\\\ \chi^2(P_0\Vert Q_0) &=2^k-1,\\\\ H^2(P_0,Q_0) &=2-2^{1-k/2},\\\\ D_{\beta}(P_0\Vert Q_0) &=k\log 2,\qquad \beta>1,\\\\ E_{2^k}(P_0\Vert Q_0) &=0. \end{aligned}$$ Thus all of these divergence quantities remain independent of $n$ for fixed $k$, but their induced event-probability bounds behave very differently. For fixed $t<1/2$, we have $q_t = \exp [ -n(\log 2-h(t))+o(n) ]$, where $h(t)$ is the binary entropy in nats. The binary-KL constraint $kl(p_t\Vert q_t)\leq k\log 2$ gives only $$p_t=O (\frac{1}{n} ).$$ In contrast, the ${\chi}^2$ inequality gives $$p_t \leq= q_t+\sqrt{q_t(1-q_t)(2^k-1)}= \exp [-\frac{n}{2} \bigl(\log2-h(t)\bigr)+o(n) ].$$ For power divergence, since $$1+(\beta-1) H_{\beta}(P_0\Vert Q_0) = \exp ((\beta-1)D_{\beta}(P_0\Vert Q_0)) = 2^{k(\beta-1)},$$ even the relaxation obtained by dropping the complementary-event term yields $$p_t \leq 2^{k(\beta-1)/\beta} q_t^{(\beta-1)/\beta} = \exp [ -\frac{\beta-1}{\beta} n(\log2-h(t))+o(n) ].$$ Hence every $\beta>2$ gives a strictly better exponential rate than the $\chi^2$ bound, while our power-divergence inequality can only further tighten the estimate. The hockey-stick divergence is still stronger. Since $E_{2^k}(P_0\Vert Q_0)=0$, Proposition 2.1 gives $$p_t\leq 2^k q_t = \exp \left[ -n\bigl(\log2-h(t)\bigr)+O(1) \right].$$ For exact selector recovery, $t=0$ and $q_0=2^{-n}$, so $p_0\leq 2^k2^{-n}=2^{-(n-k)}$. This is in fact exact: after the learner reveals the first $k$ selector bits, the remaining $n-k$ independent selector bits must still be guessed, whose success probability is precisely $p_0=2^{-(n-k)}$. Therefore, in this explicit memorization model the difference between information measures is qualitative: KL gives only a polynomial $O(1/n)$ recovery guarantee, $\chi^2$ gives an exponential rate with exponent $1/2$, higher-order power divergences give the larger exponent $(\beta-1)/\beta$, and the hockey-stick divergence recovers the full exponential rate and is exact for $t=0$. This does not mean that a higher-order $f$-divergence universally improves upon KL under the same information assumption: controlling such divergences can itself be substantially stronger than controlling KL/CMI. Rather, it demonstrates the benefit of our general $f$-divergence formulation: when the algorithm admits control of a stronger information measure, the same DPI machinery can immediately translate it into substantially sharper memorization guarantees. Under only the standard CMI assumption, our principal improvement remains the inverse binary-KL envelope used in Theorem 7.1, which removes the Fano relaxation and yields the sharper vanishing-CMI behavior discussed above. ### Conclusion We hope that our responses adequately address the reviewer’s concerns , and we have revised the paper accordingly. We presented an explicit memorization exampl to show that other $f$-divergences can yield stronger guarantees. In the revised manuscript, we added real-data deep-network experiments showing that our bounds can remain non-vacuous and can strictly improve existing ones in concrete regimes. **Based on the clarifications, corrections, and new results, we would be grateful if the reviewer could kindly reconsider the evaluation.** Thanks for your time!

I thank the authors for their thorough response. I have read it and reviewed the revised manuscript, but my main concerns remain. The paper offers several incremental improvements, but I find the memorization result to be its only substantial contribution.

Example 3, which illustrates Corollary 5.2, uses an algorithm that is independent of the training sample SS. As a result, the generalization gap in this example reduces to the deviation of an empirical mean of a sub-Gaussian loss from its population mean. Standard sub-Gaussian concentration already gives a one-sided deviation bound of 2σ2nlog⁡1δ\sqrt{\frac{2\sigma^2}{n}\log\frac{1}{\delta}} with probability at least 1−δ1-\delta. Thus, although Corollary 5.2 improves on the previous bound, the example does not demonstrate an advantage over standard concentration or illustrate what the corollary offers when the algorithm depends on the training data.

Regarding differential privacy, the bound following Proposition 6.3 requires δn=o(n−4)\delta_n=o(n^{-4}), which is much more restrictive than the commonly used benchmark δn≍1/n\delta_n\asymp 1/n. At that benchmark, the bound is vacuous. The result therefore applies to a regime in which δn\delta_n is extremely small, and it is unclear what new insight it offers for approximate differential privacy at more typical values of δn\delta_n. The case δ=0\delta=0 (pure-DP) also appears comparable to existing results in the literature.

I appreciated the authors’ answer to my question about ff-divergences. I think that direction merits further development in a separate paper with a different focus.

For these reasons, I maintain my previous score.

Hi! We sincerely thank you for the careful follow-up and for the time you have spent reading our paper. We understand that reading a theory paper requires substantial effort, and we truly appreciate the time you have put into the review. Regardless of the final decision, your comments have helped us significantly improve both the presentation and the positioning of the paper.

We would like to clarify that the primary purpose of this work is to provide a simple yet powerful unified framework for change-of-measure inequalities. Many of the resulting bounds may look incremental at first glance because the corrresponding existing results are already quite strong. Our main point in the first part of the contribution is that these results can be recovered, and in many cases improved, through a unified elementary argument, rather than through the more involved techniques (see our explicit recovery of Picard-Weibel & Guedj (2022) and Esposito et al. (2021) in Section 4.1).

In this sense, we agree with your comments on both examples. The Gaussian example for Corollary 5.2 was intended only as an analytically tractable comparison showing how the dependence on power divergence differs from Ohnishi-Honorio. Prop 6.3 is mainly intended to showcase how approximate-DP control can be translated through the same framework, and we agree that the bound is kind of restrictive in the typical regime. We only focused on the case of δ>0\delta>0 rather than pure DP. We will state these points more modestly.

Our second part of contribution is the memorization result, which we are glad you also find more substantial. We will make this part more visible, and incorporate the clarifications/results developed during the rebuttal so that the improvement over the previous result and its implications are easier to access. We also very much appreciate your positive comments on our clarification regarding general ff-divergences. We will use those observations to further strengthen the paper.

We fully understand that you maintain your score. Nevertheless, we sincerely thank you again for the time and effort you have put into our paper. We still believe that the unifying viewpoint, together with the broader memorization results via ff-divergences, provides meaningful contribution, and we will continue improving the paper regardless of the final outcome.

Reviewer_mKheOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper tries to unify several existing results of the form P(E)≤ξ(Q(E),dP/dQ)P(E) \leq \xi(Q(E), dP/dQ) through a very simple data processing inequality. The authors show that this provides bounds at least as tight as those currently known, as well as a much simpler way to apply them. The authors also show that is it easy to see that such a technique is essentially optimal via a variational form of the ff-divergence. Then, the authors apply this new technique to prove various generalization bounds and a results about memorization. Most of these appear not to be new arguments, but an application of the strengthened change-of-measure inequality.

I quite liked this paper, and see its major contribution as greatly simplifying the existing literature instead of proving novel results. Personally, I would like to see more of this sort of work at the conferences, although I feel that such a paper is harmed by the conference paper format (see Weakness 1). Overall, I support acceptance.

I am not very familiar with the surrounding literature, so it is hard for me to verify the many claims the authors make about comparisons to existing results, as well as novelty. But the claims all sound reasonable to me. I have not checked correctness carefully either, and have skimmed the appendices.

Critical strengths
  1. The change of measure proof is extremely simple and intuitive and much easier to use than previous known-results while also extending to some more cases.
  2. The paper is well-written and easy to follow, especially for someone (i.e., me) not so acquainted with the literature.
Critical weaknesses
  1. A potential weakness is that this paper seems to be more of a review-type paper that unifies previous results, and I think this sort of paper is harmed by the 9-page limit. For instance, the setup of section 7 is entirely relegated to the appendices, and the main paper is essentially not readable without referring to it. Another place is Theorem 4.2, which essentially, in the main text, has no stated relationship to the rest of the paper. It appears that several appendix results rely on Theorem 4.2, but the authors do not explain the significance of their theorem. Despite this, I believe the work is quite important. I am not really sure how to consider this in the review process and will leave it to the ACs.
  2. The applications in the second half of the paper all appear very straightforward instances of prior work, and I am unsure what additional insights can be garnered from the applications.
Questions for authors

questions/concerns:

  1. This paper uses f(t)=(1−t)2f(t) = (1 - \sqrt{t})^2 as convention for the H2H^2 divergence, whereas the Picard-Weibel and Guedj use f(t)=1−tf(t) = 1 - \sqrt{t}, which results in ff-divergences that are off by a factor of 2. This same factor of 2 seems to show up in line 1194 and is used to claim that the result of the paper is tighter than that of Picard-Weibel and Guedj, which I think is likely due to not reconciling these two divergences. Is this correct?

  2. Appendix I is empty?

  3. Can you explain a bit how Theorem 4.2 is utilized/related to the rest of the results of the paper? Currently, in the main text, there seems to be nothing accompanying it other than some definitions.

comments:

  1. [line 111]: I find the notations for the distributions quite confusing from the perspective of someone not familiar with the literature. To my understanding, PW∣SP_{W|S} is a conditional distribution over W\mathcal{W}, and that when given a distribution PSP_S (e.g., the data), it induces this joint distribution P=PSWP = P_{SW} as well as QQ. I would like some more clarity on how these are actually defined at some point in the paper's main text.
  2. [line 150]: it seems that the power divergence is never defined until we get to the table on page 5; maybe make a note to refer there?
  3. [lines 240-241]: I find these sentences to be very important to the paper, and think some extra care should be taken to explain it more thoroughly (in addition to fixing what appears to be a run-on).
  4. [line 295]: The statement of 5.1 is pretty confusing -- I think that we should define PP and QQ first before asserting P≪QP \ll Q. We also fix γ\gamma then seem to vary γ\gamma later. Also, what is u0u_0?
  5. [line 414]: In 6.2, shouldn't we require P≪QP \ll Q?

typos:

A. [line 409]: denote -> denoting? B. [line 413]: Ap(p)endix H C. [line 472]: framewor(k) D. [line 293]: take->taking E. [line 1233]: (A)memiya F. [line 1239]: capitalize t in then

4 comments
AuthorsOpenReview ↗

Thank You for the Support and Addressing the Weaknesses

We sincerely thank Reviewer mKhe for the careful, constructive, and supportive assessment. We particularly appreciate the reviewer's view that the simplicity and unification of change-of-measure arguments are valuable contributions. We agree that the original page limit made several important connections unnecessarily difficult to follow, and that some of our comparisons and novelty statements should be presented more carefully.

We have also used the permitted additional page to further clarify and strengthen the manuscript, with all changes highlighted in blue. We have included more details on memorization results, which should improve the readibility of that section.
We respond point by point below.

Weakness 1: Main-text self-containment and the role of Theorem 4.2

We agree with this criticism. Two places in particular were too compressed in the original submission.

Section 7 / memorization setup. The original main text stated the memorization theorem without introducing enough of the supersample construction. We have substantially revised the manuscript. In the revision, we move the essential definitions into the main paper before Theorem 7.1: the supersample Z~\widetilde Z, the selector J∈{0,1}nJ\in\{0,1\}^n, the learner output WW, the conditional mutual information I(W;J∣Z~)I(W;J\mid \widetilde Z) and the meanings of the training and fresh positive counts TnT_n and FnF_n. This allows the theorem and its interpretation to be understood without first consulting Appendix N.

The key consequence is also stated more explicitly. If P(Tn≥αn)≥qP(T_n\geq \alpha n)\geq q and I(W;J∣Z~)=o(n)I(W;J\mid\widetilde Z)=o(n) then for every fixed β<α\beta<\alpha, P(Fn>βn)≥q−o(1)P(F_n>\beta n)\geq q-o(1). Thus a persistent linear separation between training and fresh samples is incompatible with the sublinear-CMI regime.

Role of Theorem 4.2. We agree that the original main text did not explain why Theorem 4.2 is included. Its purpose is to provide an Orlicz-norm route to change-of-measure inequalities that complements the direct ff-divergence specializations of Theorem 4.1. It is subsequently used in Appendix D to obtain the two-level Orlicz generalization result, in Appendix E for α\alpha-mutual-information specializations, and in Appendix G in the CMI setting.

A concrete power-Orlicz choice also makes the theorem directly interpretable. Let r=ββ−1,ψ(t)=trr,ψ⋆(u)=uββr=\frac{\beta}{\beta-1}, \psi(t)=\frac{t^r}{r}, \psi^\star(u)=\frac{u^\beta}{\beta}, Theorem 4.2 reduces to P(E)≤γQ(E)+Q(E)(β−1)/β(EQ[(L−γ)+β])1/βP(E) \leq \gamma Q(E) + Q(E)^{(\beta-1)/\beta} \left( \mathbb E_Q[(L-\gamma)_+^\beta] \right)^{1/\beta}. For a fixed β\beta, the right-hand side can be optimized over the scalar γ\gamma. We have added this example and a short map of the theorem's later uses to the main text. We will further revise the paper to make the use of Theorem 4.2 more visible in the main texts.

Weakness 2: What additional insights come from the applications?

We agree that our original presentation did not sufficiently distinguish straightforward recoveries from the genuinely new consequences. We have revised the manuscript accordingly.

First, several results are intentionally recoveries: one goal of the framework is to show that apparently different change-of-measure arguments can be obtained from the same exact Bernoulli constraint with substantially simpler analysis.

There are nevertheless several application-level consequences that go beyond such recoveries.

PAC-Bayesian Bound. Corollary 5.2 gives a new power-divergence PAC-Bayesian bound. We do not claim uniform superiority over classical PAC-Bayes inequalities, but Section 5.3 gives explicit finite-sample and asymptotic regimes where it is strictly tighter than the corresponding Ohnishi-Honorio power-divergence bound.

Approximate DP. Based on the approximate max-information, in Section 6 we obtain the high-probability generalization guarantee of approximate DP algorithms, stated after Proposition 6.3.

Memorization. Theorem 7.1 strengthens Sefidgaran et al. (2025, Theorem 5(ii)) by retaining the full Bernoulli-KL constraint rather than applying the usual Fano relaxation. In particular, when the CMI vanishes, the inverse binary-KL envelope removes the Θ(1/n)\Theta(1/n) Fano slack.

Finally, motivated by the reviewers' requests concerning practical relevance, we have added experiments on MNIST/LeNet and CIFAR-10/ResNet-18. The new experiments show that our proposed bounds can remain non-vacuous on stochastic predictors based on real deep networks, and empirically tighter than existing bounds in some cases.

AuthorsOpenReview ↗

Responses to Questions and Summary

Question 1: Hellinger normalization and the comparison

The reviewer is correct. We used the unnormalized squared Hellinger divergence Hours2(P,Q)=∫(dPdQ−1)2dQH_{\mathrm{ours}}^2(P,Q)=\int(\sqrt{\frac{dP}{dQ}}-1)^2dQ whereas the convention in the cited Picard-Weibel--Guedj comparison is HPWG2(P,Q)=1−∫dPdQH_{\mathrm{PWG}}^2(P,Q)=1-\int\sqrt{dP dQ} and hence Hours2(P,Q)=2HPWG2(P,Q)H_{\mathrm{ours}}^2(P,Q)=2H_{\mathrm{PWG}}^2(P,Q).

The factor of two identified by the reviewer therefore comes entirely from the differing normalizations. After expressing the two formulas under the same convention, the expressions compared around the original line 1194 coincide.

We sincerely thank the reviewer for catching this issue, and will correct this in the revision. This affects the claimed comparison with prior work, but not the validity of the Bernoulli-DPI Hellinger relation itself.

Question 2: Appendix I appears empty

We thank the reviewer for reading the appendix carefully. Appendix I was used for Figure 3, which is shown on the next page. We will correct this inconsistency and make this clear.

Question 3: How is Theorem 4.2 used?

We thank the reviewer again for asking this. We have answered this in our previous response to Weakness 1. Nevertheless, we also briefly explain it here. We agree that this connection was not visible enough, and we will revise further in the revision.

As described above, Theorem 4.2 is not an isolated result: it provides the Orlicz-norm branch of our framework. Specifically, it is used to derive the two-level Orlicz generalization result in Appendix D, α\alpha-mutual-information specializations in Appendix E, and CMI-based consequences in Appendix G.

The power-Orlicz specializationψ(t)=trr,ψ⋆(u)=uββ,1r+1β=1,\psi(t)=\frac{t^r}{r},\qquad\psi^\star(u)=\frac{u^\beta}{\beta},\qquad\frac1r+\frac1\beta=1, recovers a familiar Hölder-type control and gives a concrete example of how the theorem can be used. We have added this explanation immediately after Theorem 4.2 so that its purpose is clear before the appendices.

Comment 1: Clarifying PW∣SP_{W|S}, PSWP_{SW}, and the reference distribution

We agree that the notation was too compressed for readers unfamiliar with information-theoretic generalization.

We now explicitly define the objects in the main text. The learner is a Markov kernel PW∣SP_{W|S} from a dataset SS to a hypothesis WW. Together with the data distribution PSP_S, it induces the joint law PSW=PSPW∣SP_{SW}=P_S P_{W|S}. Its marginal hypothesis law is PW(A)=∫PW∣S=s(A)dPS(s)P_W(A) = \int P_{W|S=s}(A) dP_S(s) and the product/reference law used in the information-theoretic generalization analysis is Q=PSPWQ=P_S P_W. Thus the comparison in Section 5 is between the actual coupled law PSWP_{SW} and the law PSPWP_SP_W in which the same marginals are made independent. We will further revise the paper to make the definitions clearer.

Comment 2: Definition of power divergence

We thank the reviewer for noticing this. We have defined (Hβ(P∥Q)=1β−1[∫(dPdQ)βdQ−1]H_\beta(P\Vert Q) = \frac{1}{\beta-1} [ \int (\frac{dP}{dQ})^\beta dQ -1 ]) before Eq. (7) in the revised manuscript, and then we state its one-to-one relation with Rényi divergence. The changes are made in blue.

Comment 3: Explanation of the optimality statement in Section 4.1.

We agree that these sentences are very important to the paper and deserve a clearer explanation. In the revised paper, we have already rewritten the discussion, fixed the run-on sentence, and we will try to further make the scope of the optimality statement more explicit.

Comment 4: Statement of Theorem 5.1

We thank the reviewer again. We agree that the original statement was unnecessarily difficult to parse. In the revised paper, we have updated Theorem 5.1 where the changes are marked in blue. We no longer fix γ\gamma in a way that conflicts with subsequent optimization; the hockey-stick statement is written for every admissible γ\gamma, after which one may optimize over it.

Comment 5: Absolute continuity in Lemma 6.2

We agree. We have added this condition to Lemma 6.2 in the revised version.

Typos:

We thank the reviewer for carefully identifying these issues. We have corrected all listed typographical errors.

Summary

We sincerely thank the reviewer again for the careful, constructive, and supportive review. We hope that our point-by-point responses have clarified the issues raised and adequately addressed the reviewer’s concerns. We have also substantially revised the manuscript in response to these comments, with all changes highlighted in blue.

We are confident in the contributions of our work, and we hope that the additional explanations, corrections, and new results further strengthen the reviewer’s understanding of and confidence in the paper. If the reviewer finds our responses and revisions satisfactory, we would be very grateful if they could kindly consider updating their confidence accordingly, which would also help the Area Chair better assess the paper in the final decision. Thank you so much!

Hi--thank you for your revisions and thorough response.

I apologize for backtracking a bit from my original review, especially at this time, but upon rereading some parts, I have some more reservations about the overall presentation of the paper. If a major goal is to simplify the existing literature, I believe some more additional care should be put into the presentation, still. If anything, I felt that some of the changes that were made induced more confusion, unfortunately.

Question 3:

I still don't quite find the explanation for 4.2 in the revision sufficient, especially for one reading it for the first time. I do not really feel that the revision clarifies much, as it seems to expect the reader to derive this on the spot. It seems still unclear what this has to do with the rest of the section, and the proposed addition seems very superficial and even harder to understand.

Upon rereading, I also believe the theorem statement for 4.2 should say something like "Fix an Orclicz function ψ\psi. Then, for all measurable EE [...]."

Comment 2 (on power divergence)

The revision seems to have changed this and removed the words "power divergence"?

Comment 1 (on notation)

The changes promised seemed not to be in the text (maybe meant for the future)?


Overall, I think my weaknesses still stand.

I still do not quite remain convinced that the new PAC bounds nor the DP bound tell us that much more about the fundamental problems at hand, rather than a new bound. If the authors believe that there is substantial insight in these, I think it would be nice to discuss why so, or how such results compare to our current understandings.

I have read the other reviews and still remain in support of this paper, although I will not be increasing my confidence score.

Thank you very much for rereading the revision and for the additional comments! We are sorry that some of our previous changes made the presentation less clear. We are still working to improve the presentation.

We have just found time to update some of the notation as we promised (in red\color{red}{\text{red}}, to distinguish it from previous revisions) and to incorporate some minor revisions you suggested. If possible, we will find more time tomorrow to further improve the presentation of the paper. The rebuttal period is coming to an end in 10 hours, but regardless of the final outcome of the paper, you and the other reviewers have already significantly helped us improve the paper, and we will continue to make it clearer and better.

Question 3: Theorem 4.2

We agree with the suggested quantifier order. In the revised version, we have updated the theorem statement accordingly and strengthened the explanation after Theorem 4.2 to make its role explicit. As you know, the space limit prevents us from further clarifying this point here, but we plan to shorten the discussions on PAC-Bayes and DP to make more space and add further clarification on this point.

Comment 2: Power divergence

We have added it back; we had removed it to save some space, which was unnecessary.

Comment 1: Promised notation update

Yes, we intended to update it later; now we have added more clarifications at the beginning of Section 5. We will further polish it.

PAC and DP bounds

We appreciate this concern and agree that they are not strong, fundamental contributions. The PAC-Bayes bounds and Prop. 6.3 are, from our perspective, viewed mainly as showcases of our unified framework, which is simple yet powerful. Beyond the unified framework itself, we plan to place more emphasis on the memorization results, where our DPI approach leads to stronger conclusions. We have also been discussing this point with Reviewer Lkau, especially the extensions through ff-divergences, and we will incorporate those clarifications and results more prominently into the paper, making this part the main contributions beyond our unified framework.

Thank you again for the careful rereading and for continuing to support the paper! We recognize the considerable effort required to carefully read a theory paper, and we sincerely appreciate the time and attention you have devoted to our work.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Author Response Summary and Manuscript Revisions

We sincerely thank the Area Chair and all reviewers for their careful evaluations, constructive comments, and valuable suggestions.

In response, we have provided detailed point-by-point replies to each reviewer and substantially revised the manuscript using the permitted additional page, with all changes highlighted in blue. Our main revisions and additions include:

  1. Clarified novelty and theoretical positioning. We now more clearly distinguish the classical indicator-DPI ingredient from our contributions, including the optimality proof, PAC-Bayesian generalization, approximate DP, memorization, and more numerical evidences on the strength of our generalization bounds.

  2. Strengthened and corrected the theoretical presentation. We clarified the role and constructive use of the Orlicz result, improved the self-contained presentation of the memorization framework, clarified notation and theorem statements, and addressed the reviewers' technical and presentation comments throughout.

  3. Strengthened the memorization results and discussion of general ff-divergences. We clarified how to improve the Fano-type relaxation by keeping the exact Bernoulli-KL constraint, and added results illustrating how other ff-divergences can provide qualitatively stronger guarantees when the corresponding information measures are controlled.

  4. Added new real-data and deep-network experiments. We evaluated the proposed bounds on MNIST/LeNet and CIFAR-10/ResNet-18, demonstrating that the bounds are non-vacuous in high-dimensional learning settings. We also identify concrete regimes in which our power-divergence and hockey-stick bounds are strictly tighter than their corresponding existing relaxations.

We believe these revisions substantially improve the clarity, theoretical positioning, and empirical support of the paper, and address the main concerns raised during the review.

We warmly welcome any further questions, comments, or discussion from the reviewers and the Area Chair. If the reviewers find our responses and revisions satisfactory, we would be very grateful if they could kindly reconsider their assessments and ratings in light of the clarifications, corrections, and new results.

Thank you again for your time, consideration, and constructive feedback!

AuthorsOpenReview ↗

Summary of Contributions and Rebuttal Revisions for the Area Chair

Dear Area Chair,

As the discussion period concludes, we would like to briefly summarize our main contributions and the additional theoretical and empirical evidence provided during the rebuttal to facilitate your assessment.

1. Main Contributions and Novelty

Our central contribution is a unified, elementary, yet powerful framework for change-of-measure inequalities, together with novel theoretical consequences for learning theory, particularly data memorization.

  • Unified framework and optimality: While applying DPI to an event indicator is a classical technique, our contribution is to identify its broad and powerful use change-of-measure inequalities for and establish itsoptimality. This recovers and improves existing inequalities, including those of Picard-Weibel & Guedj (2022) and Esposito et al. (2021), through substantially simpler analyses.

  • Novel memorization guarantees: Theorem 7.1 strengthens Sefidgaran et al. (2025) by retaining the exact Bernoulli-KL constraint rather than applying the Fano relaxation.

  • Generalization and privacy: We use generalization and privacy bounds to demonstrate the flexibility and broad applicability of our unified framework.

2. Main Additions and Clarifications During Rebuttal

We have substantially revised the manuscript, with the initial revisions highlighted in blue and the latest revisions highlighted in red.

  • Stronger memorization results via general ff-divergences: Motivated by Reviewer Lkau's questions, we established additional Rényi-divergence and approximate-max-information guarantees (Corollary 7.2 and Proposition 7.3). We also constructed an explicit memorization example where the KL-based bound decays polynomially, while higher-order divergences yield exponential decay and the hockey-stick bound achieves the exact selector-recovery probability.

  • New real-data and DNN experiments: Evaluated MNIST/LeNet and CIFAR-10/ResNet-18, obtaining non-vacuous PAC-Bayesian risk certificates for all 432 trained ResNet-head posterior configurations. Our power-divergence refinement achieves a 17.9% tighter event-probability bound than the optimized classical Hölder relaxation, while the hockey-stick bound improves the strong-converse relaxation by 5.0–6.5%.

  • New connections to DNN architecture and training dynamics: Motivated by Reviewer MyoS's follow-up, we established connections between our framework, layerwise strong DPI contraction, and iteration-dependent information control (Appendix O). Additional training-trajectory analyses demonstrate the importance of controlling posterior–prior divergence to maintain non-vacuous generalization guarantees.

  • Theoretical positioning and presentation: Clarified the distinction between classical ingredients and novel results, strengthened the self-contained presentation of memorization, provided constructive interpretations of the Orlicz bound, and corrected the theoretical comparisons, notation, and theorem statements.

We particularly appreciate Reviewer mKhe's continued support for acceptance (rating 4), Reviewer MyoS's acknowledgment that their main concerns have been addressed, and Reviewer Lkau's recognition of the significance of our memorization results and the potential of their general ff-divergence extensions.

We respectfully emphasize that our paper makes two complementary contributions: a simple and unified theoretical framework that substantially simplifies the existing literature and gives stronger memorization guarantees that demonstrate the framework's ability to yield qualitatively new insights. We believe that they are valuable to the information theory and machine learning communities.

We sincerely thank the Area Chair and all reviewers for their time, constructive feedback, and consideration.

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.