nucleation

LIT-236: Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms

2 min read

Properties5
StatusActive — read 2026-10-14 (NOTE-780) in full; worth reading as the source of the lossy generalisation bound |E gen| ≤ √(2σ²·R_E(ε)/n) + ε, where R_E(ε) is the least I(S;Ŵ) over surrogate outputs within ε in expected generalisation error (Theorem 4), of which Xu–Raginsky's bound is the lossless case, and of its Lipschitz, rate-distortion-dimension and tail forms (Corollaries 6–7, Theorem 10). Read it knowing that the block-coding meaning is proved only for finite alphabets, that in general spaces Theorem 4 is Xu–Raginsky applied to a surrogate, that every bound depends on the unknown data distribution, that no bound is evaluated for a learned model, and that the one worked example mixes squared and unsquared distortion, so its d/n rate is unsupported.
Version3
Tagslearning-theory, information-theory, anthology-candidate
Cited as “paper” byNOTE-200 — Rate-distortion generalization bounds, NOTE-780 — Sefidgaran, Gohari, Richard & Şimşekli — Rate-Distortion Theoretic Generalization Bounds
Cited as “source” byTHEORY-248 — The expected generalisation error of a learning algorithm is at most √(2σ²R/n) + ε, where R is the least information about the sample carried by any surrogate output whose expected generalisation error is within ε; I(S;W) is the lossless case, and for an L-Lipschitz loss R is at most the rate-distortion function of the output's law at distortion ε/(2L), so the bound is finite wherever that function is, including where I(S;W) is infinite

Graph View

Milad Sefidgaran, Amin Gohari, Gaël Richard, Umut Şimşekli (2022), Conference on Learning Theory (COLT) 2022, PMLR 178 (pp. 4416–4463 as cited by LIT-233); arXiv preprint — ARXIV-2203.02474

Key takeaways

From the reading, NOTE-780.

  • What is compressed. Not one trained model. It is a block of m independent training runs, (S_i, W_i), covered by a book of e^{mR} candidate output blocks to within average distortion ε in generalisation error (Def. 1).
  • The bound. |E gen(S, W)| ≤ √(2σ²·R_E(ε)/n) + ε, with R_E(ε) the least I(S; Ŵ) over surrogates within ε (Theorem 4). For general spaces the proof is Xu–Raginsky applied to Ŵ.
  • Lossless is Xu–Raginsky. At ε = 0 it is |E gen| ≤ √(2σ²I(S;W)/n) (Corollary 5). For finite alphabets I(S;W) is an achievable lossless rate (Theorems 2–3).
  • Lossy and Lipschitz. RD(ε/(2L); P_W, ρ) of the output’s marginal law replaces I(S;W) (Corollary 6), and as ε → 0 the rate-distortion dimension of P_W (Corollary 7, under a uniform-convergence assumption).
  • Tail. With probability ≥ 1 − δ, gen ≤ √(2σ²(R_p(δ, ε) + log(1/δ))/n) + ε, with R_p a supremum over laws within KL log(1/δ) of P_{S,W} (Theorem 10). It is one-sided, and can be worse than Hoeffding when S and W are independent.
  • Also recovered. Steinke–Zakynthinou’s CMI bound and VC bounds, in expectation and in tail form (Appendix A).
  • Limits. Every bound depends on μ. None is computed for a network. The Gaussian-mean example’s d/n rate rests on a units slip.

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-780. It is the record’s source for the lossy, surrogate-based extension of the input–output information bound, filed as THEORY-248.

It extends Xu–Raginsky (LIT-347), which THEORY-028 holds with Russo–Zou (LIT-356). THEORY-028 still describes this paper as unread, and the reading gives it a third remedy for infinite I(S;W) and a tail form. Its data-dependent successor is LIT-233. The paper has no Kolmogorov complexity and no sufficient statistic. Its tie to the heading is only that I(S;W) is read as a code length. 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.

Backlinks