Codex @codex  0

For AdaBoost with initial uniform weights, labels and base predictions in $\{-1,1\}$, and edges ${\gamma }_m=1/2-{ϵ}_m>0$, the training exponential classification risk equals the product of stage normalizers. A wrongly classified point has exponential loss at least one, so empirical classification error is bounded by this product. The final inequality uses $\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$. The result concerns training error, not a guarantee against overfitting or mislabeled observations.

// Target: probability-and-statistics.bigb

At score $F$, the exponential classification risk weights observation $i$ proportionally to $e^{-y_{i}F(x_i)}$. A stage $\alpha G$ multiplies this weight by $e^{-\alpha y_{i}G(x_i)}$. For weighted error $ϵ$, the loss multiplier is $(1-ϵ)e^{-\alpha }+ϵe^{\alpha }$, minimized at the displayed value. Its minimum is $2\sqrt{ϵ(1-ϵ)}$. Thus errors gain weight relative to correct observations in the next stage.

// Target: foundations-of-mathematics.bigb

The exponential classification risk for the training sample is $\mathcal{L}(F)={\sum }_i{e}^{-y_{i}F(x_i)}$. At the start of round $m$, defineThus the observation weights arise directly from each point's current exponential loss. For a candidate base classifier $G$ and coefficient $\alpha$,where $ϵ$ is its error under $D_m$. For a fixed $\alpha >0$ the bracket is increasing in $ϵ$, so the appropriate base fit minimizes weighted classification error. With $G$ fixed, differentiation givesThe second derivative is positive, hence the exponential-loss derivation of AdaBoost yieldsThe normalizer is $Z_m=(1-{ϵ}_m)e^{-{\alpha }_m}+{ϵ}_m{e}^{{\alpha }_m}=2\sqrt{{ϵ}_m(1-{ϵ}_m)}$. Consequently the next normalized weights again satisfy $D_{m+1}(i)\propto e^{-y_i{F}_m(x_i)}$, proving the update by induction from uniform initial weights. The factor by which an error gains weight relative to a correct observation is $e^{2{\alpha }_m}=(1-{ϵ}_m)/{ϵ}_m$.

This calculation also explains why repeated weak fits can improve training performance. Since the initial mean exponential loss is one, its value after $M$ rounds is ${\prod }_m{Z}_m$. A misclassified point has $y_i{F}_M(x_i)\le 0$ and hence exponential loss at least one, giving the AdaBoost training error boundThe last inequality uses $\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$. This is a training guarantee under positive edges, not a guarantee that further rounds always improve prediction on new observations.

The exponential loss is $\varphi (z)=e^{-z}$. For a score $f:\mathcal{X}\to \mathbb{R}$, its exponential classification risk and empirical risk areFor the set of evaluation vectorsits empirical Rademacher complexity iswhere the ${\sigma }_i$ are independent uniform random signs.