Concave impurity gives non-negative information gain

ProofIntermediate⏱ 30 minClassical MLentropyginiconcavitysplitting

Problem

Prove that for concave $\Phi$ on the simplex, any split has non-negative gain $\Phi(p) - w_L\Phi(p_L)-w_R\Phi(p_R)\ge0$ , and that strict concavity gives strict gain unless $p_L = p_R$ . Then explain why misclassification error is a poor splitting criterion.

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
Gradient boosting fits the negative functional gradient	Classical ML	Proof	Intermediate	30 min
The bagging variance formula	Classical ML	Proof	Intermediate	30 min
The irreducible loss is the conditional entropy	LLMs	Proof	Intermediate	30 min
AdaBoost as exact line search on the exponential loss	Classical ML	Proof	Advanced	30 min
AdaBoost drives training error to zero exponentially	Classical ML	Proof	Advanced	1 hour