AdaBoost as exact line search on the exponential loss

ProofAdvanced⏱ 30 minClassical MLadaboostexponential losscoordinate descentline search

Problem

Show that minimising $\sum_iw_ie^{-\beta y_ih(x_i)}$ over $\beta$ , with $w_i\propto e^{-y_iF_{t-1}(x_i)}$ , gives $\beta = \tfrac12\log\frac{1-\eps}{\eps}$ where $\eps$ is the weighted error, and that the weight update in AdaBoost is exactly the re-normalisation of $w_i$ after the step.

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
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 drives training error to zero exponentially	Classical ML	Proof	Advanced	1 hour
Gradient descent with exact line search on a quadratic	Optimization	Proof	Advanced	1 hour