- 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 . 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 in practical learning algorithms. This renders the theorem computationally infeasible in practice. -In Eq (24), the parameter inherently depends on the unknown target test probability . Although the authors attempt to remedy this flaw by setting a hard cutoff value , 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
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 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 trained posterior configurations. The best bound across the three seeds are , , and , 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 , let , , and for the independent prior .
By our bound, at the exact power-divergence relation gives non-vacuous upper bounds of , , and across the three seeds. For my seed 0, the explicit retained-complement refinement gives , compared with for the optimized classical Rényi/Hölder relaxation using the same power divergence, a relative reduction. Separately, at , the optimized hockey-stick bound gives , , and , versus , , and for the classical strong-converse relaxation, corresponding to relative reductions of --.
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!
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?
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 c (Weakness 1). This observation is correct. Eq. (10) has a form involving parameter c, 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)} for 0<q<1. The approach is a transparent scalar calculation, and only in the KL and χ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 α-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, r=β/(β−1), and choose ψ(t)=rtr and ψ⋆(u)=βuβ.
Writing L=dP/dQ and q=Q(E), the two norm factors in Theorem 4.2 can be evaluated explicitly:
ψ−1(1/q)1=(rq)1/r, and ∥(L−γ)+∥ψ⋆A,Q=r1/r(EQ[maxL−γ,0β])1/β.
Hence, Theorem 4.2 reduces exactly to the standard Hölder-type specialization:
P(E)≤γQ(E)+Q(E)(β−1)/β(EQ[maxdP/dQ−γ,0β])1/β,γ∈R.
This is essentially the same power-Orlicz mechanism already used in Appendix E at γ=0, while keeping γ free provides an additional computable refinement. For every fixed β>1 for which the required β-th moment is finite, the right-hand side is a convex function of γ: indeed, γ↦(L−γ)+ is convex, and its Lβ(Q) norm preserves convexity by monotonicity and Minkowski's inequality. Thus the optimal γ can be obtained by a one-dimensional convex optimization, while β 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 M in Eq. (24) and the cutoff u0 in Eq. (25) (Weakness 2). We agree that the assumption P(E)≤1/(M+1) used to display Eq. (24) should not be treated as directly verifiable when P(E) is the unknown quantity. The subsequent Eq. (25), however, does not rely on an arbitrary cutoff. For β>1, put p=P(E), q=Q(E), and A=1+(β−1)Hβ(P∥Q). The Bernoulli-DPI inequality is pβq1−β+(1−p)β(1−q)1−β≤A. Dropping the nonnegative complementary-event term first yields the proved upper bound p≤u0:=min1,(Aqβ−1)1/β. Hence (1−p)β≥(1−u0)β, 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.