Milad Sefidgaran, Abdellatif Zaidi (2023), IEEE Transactions on Information Theory 70(9) (2024) 6572-6595 — ARXIV-2303.05369
Key takeaways
From the reading, NOTE-806.
- Variable-size books. Only the first e^{Σ_i R_{S_i,W_i}} codewords may cover a given block of runs (Def. 2). Then gen(S, W) ≤ √(4σ²(R_{S,W} + log(√(2n)/δ))/(2n − 1) + ε) with probability ≥ 1 − δ (Theorem 1).
- PAC-Bayes is the lossless case. The rate log dP_{W|S}/dP(W) against a fixed prior meets the coding condition at ε = 0 (Theorem 2, finite alphabets). The bound is then the disintegrated PAC-Bayes bound. The rate is a Shannon code-length difference, as in Blum–Langford’s PAC-MDL.
- One family. Theorems 3–5 are general change-of-measure bounds on any f(S, W). They recover Rivasplata et al.’s PAC-Bayes bound, Bégin et al.’s Rényi bound, Xu–Raginsky, and LIT-236’s tail bound.
- Lossy PAC-Bayes (Proposition 1). A surrogate within ε keeps the bound finite for deterministic algorithms with continuous parameters, where classical PAC-Bayes is infinite.
- Trajectories (Theorem 7). The mean generalisation error over iterations is at most √((RD(S, ε; π_S) + log(√(2n)M/δ))/(2n − 1) + 4Lε). RD is the trajectory’s rate-distortion function for the given sample. M depends on μ and absorbs I(W^T; S).
- The experiment tests an ordering, not the bound. On CIFAR-10, with M and 4Lε dropped, the estimated rate and the test gap both fall with the learning rate. For FCN4 the plotted term is about 3, vacuous for 0–1 loss.
- A hand-built surrogate gives O(1/n) on Haghifam et al.’s example, where Xu–Raginsky’s bound is Ω(1) (Appendix A).
Standing in the record
Filed on 2026-09-26 at the owner’s request, from a list they grouped under the heading Relating K-complexity to minimum sufficient statistics. Read in full on 2026-10-14 in NOTE-806. It is the record’s source for the variable-rate framework that joins rate-distortion and PAC-Bayes bounds, filed as THEORY-263, and for the trajectory bound, filed with its caveats as THEORY-266.
It generalises LIT-236 and recovers Xu–Raginsky (LIT-347), so it bears on THEORY-028, which still calls it unread. The answer to the question the seed left, whether the variable rate is MDL in disguise, is: in the PAC-Bayes case it is a Shannon code length against a prior, not a Kolmogorov or two-part code, and no link to minimal sufficient statistics is made. The same group’s LIT-245 applies the framework to representations. No instruction for machine-learning practice.
Tagged anthology-candidate (ADR-005) at the owner’s request on 2026-10-14, as LIT-245 is: its subject is generalisation theory for learning algorithms, which an anthology topic could hold.