§3.2 — cross-entropy decomposition
ProvedMLManagesComplexity.cross_entropy_decompositioncomputational-complexitycryptographyinformation-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let and be probability distributions on a finite set . Write for the Kullback–Leibler divergence, for the cross-entropy, and for the Shannon entropy, the divergence and the cross-entropy being when some has . Then
The decomposition explains why minimising over models is the same as minimising the cross-entropy (the training loss): does not depend on .
Formalization Note The identity is stated in the extended reals, so the infinite case is included.
Differences from the source:
- generalization: distributions over {0,1}^n → distributions on an arbitrary finite type Ω; reason: the identity holds on every finite set; Ω = {0,1}^n is the source's case
- encoding: KL-divergence and cross-entropy (possibly infinite, p.5: "even infinite if for some x, τ(x) > µ(x) = 0") → the published
klBits/crossEntropyinEReal,⊤exactly on a support mismatch, logarithms base 2; reason: Lean convention; same values
Preamble
import Mathlib import Definitions.Def_AutoregressiveCompression_Main_Information set_option autoImplicit false open AutoregressiveCompression.Main
Formal statement
namespace MLManagesComplexity
/-- **Cross-entropy decomposition** (Fortnow, *How Does Machine Learning Manage Complexity?*, arXiv:2604.07233 (version of 2026-10-31, sha256 4874d83f…), §3.2, printed p.4, PDF p.5: "KL(τ‖μ) =
E_{x∼τ}[log(1/μ(x))] − H(τ)"). For distributions `τ, μ` on a finite set, the KL divergence of
`τ` from `μ` equals the cross-entropy of `τ` under `μ` minus the Shannon entropy of `τ`, in bits.
**Formalization Note** `klBits`, `crossEntropy` and `entropy` are the published
`AutoregressiveCompression.Main` ones (base 2; `klBits` and `crossEntropy` are `⊤` exactly when
some `x` has `τ(x) > 0 = μ(x)`). The identity is in `EReal`, so the infinite case
(`⊤ = ⊤ − H(τ)`) is included. -/
theorem cross_entropy_decomposition {Ω : Type} [Fintype Ω] (τ μ : PMF Ω) :
klBits τ μ = crossEntropy τ μ - (entropy τ : EReal) := by sorry
end MLManagesComplexity
Source
Fortnow, How Does Machine Learning Manage Complexity?, arXiv:2604.07233 (version of 2026-10-31, sha256 4874d83f…), §3.2, cross-entropy decomposition, p.4 (PDF p.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.