AdaBoost drives training error to zero exponentially

ProofAdvanced⏱ 1 hourClassical MLadaboosttraining errorweak learningbound

Problem

Prove that if every weak learner satisfies $\eps_t\le\tfrac12-\gamma$ , then the training error of $F_T$ is at most $e^{-2\gamma^2T}$ . State what the theorem does not say about test error.

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
The round-trip error bound	Quantization	Proof	Foundation	15 min
Concave impurity gives non-negative information gain	Classical ML	Proof	Intermediate	30 min
Gradient boosting fits the negative functional gradient	Classical ML	Proof	Intermediate	30 min
The bagging variance formula	Classical ML	Proof	Intermediate	30 min
AdaBoost as exact line search on the exponential loss	Classical ML	Proof	Advanced	30 min