The irreducible loss is the conditional entropy

ProofIntermediate⏱ 30 minLLMsentropylower boundscaling lawsirreducible loss

Theory: Language Modelling, Cross Entropy and Perplexity →

Problem

Prove that the expected cross-entropy of any model is at least the conditional entropy of the true distribution, with equality iff the model is exact. Relate this to the $\mathcal L_\infty$ term in scaling-law fits and to the interpretation of a model's reported loss.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Maximum likelihood is KL minimisation	LLMs	Proof	Beginner	15 min
Perplexity is not comparable across tokenisers	LLMs	Numerical	Beginner	15 min
The cross-entropy gradient is the prediction error	LLMs	Proof	Beginner	15 min
Concave impurity gives non-negative information gain	Classical ML	Proof	Intermediate	30 min
Derive the compute-optimal allocation	LLMs	Proof	Intermediate	30 min