nucleation

LIT-347: Information-theoretic analysis of generalization capability of learning algorithms

1 min read

Properties5
StatusActive — read in full 2026-09-29 (NOTE-306); worth reading as the short, clean source of the input–output mutual-information generalisation bound, and of "a learning algorithm is a channel P_{W|S}", whose capacity is sup_μ I(S;W). The bound is in expectation and is vacuous for deterministic algorithms on continuous hypotheses, which is what the later compression and rate–distortion refinements (LIT-236, LIT-233) address.
Version2
Tagslearning-theory, information-theory, anthology-candidate
Cited as “paper” byNOTE-306 — Information-theoretic analysis of generalization capability of learning algorithms
Cited as “source” byTHEORY-028 — The expected bias of any data-dependent choice, and the expected generalisation error of any learning algorithm, is at most √(2σ²·I) for σ-subgaussian losses, where I is the information the output carries about the data

Graph View

Aolin Xu, Maxim Raginsky (2017), NeurIPS 2017 — ARXIV-1705.07809

Standing in the record

Registered on 2026-09-29 at the owner’s request, because the owner’s prior-art novelty map (a private working document on concepts as projectors, the linear representation hypothesis and their neighbours) cites it: row 12 must-cite: information-theoretic generalization. It is seeded from metadata and published descriptions and has not been read here.

Identification notes: Not held in the anthology (the anthology “Raginsky” hit, ANTH-LIT-726, is a different paper).

It was filed Deferred, unread. NOTE-306 is the close reading of 2026-09-29, and it placed the work: Active — worth reading as the short, clean source of the input–output mutual-information generalisation bound, and of “a learning algorithm is a channel P_{W|S}”, whose capacity is sup_μ I(S;W). The bound is in expectation and is vacuous for deterministic algorithms on continuous hypotheses, which is what the later compression and rate–distortion refinements (LIT-236, LIT-233) address.

Backlinks