Interpreting AdaBoost As Coordinate Descent

From Weighted Errors to Directions in a Score Function

AdaBoost can be described as repeatedly adding a weak rule to an additive score. The rule supplies a direction, and its coefficient specifies how far to move in that direction. The connection to coordinate descent is useful because it explains why the algorithm chooses rules using the current weighted errors: those errors determine the exact change in exponential loss along each candidate direction.

Fix a training sample $(x_i,y_i)$, $i=1,\ldots,n$, with labels $y_i\in\{-1,+1\}$. Let $\mathcal H=\{h_1,\ldots,h_M\}$ be a finite set of candidate binary rules, where each $h_j(x_i)\in\{-1,+1\}$. An additive score based on these rules has the form $F(x)=\sum_{j=1}^M\beta_jh_j(x)$, with coefficients $\beta_j\geq 0$. The empirical exponential loss is

\mathcal L(\beta)=\sum_{i=1}^n \exp\!\left(-y_i\sum_{j=1}^M\beta_jh_j(x_i)\right).

The sign of $F(x)$ gives the corresponding classifier when $F(x)\ne 0$. Here the object of interest is the loss as a function of the coefficients, not a new classification rule or a bound on its error.

Definition: At a current score $F$, define the normalized example weights and the weighted error of a candidate rule $h$ by $$ D_i=\frac{\exp(-y_iF(x_i))}{\sum_{k=1}^n\exp(-y_kF(x_k))}, \qquad \epsilon(h)=\sum_{i=1}^nD_i\,\mathbf 1\{h(x_i)\ne y_i\}. $$ The weights are positive and sum to one. The weighted error is the total current weight of the observations that the rule classifies incorrectly.

For any candidate $h$, a step of size $\alpha\geq 0$ replaces $F$ by $F+\alpha h$. The coefficient is constrained to be nonnegative because AdaBoost adds a rule in its chosen direction; it does not initially consider a negative step along that direction.

Deriving the One-Direction Loss

Write $L(F)=\sum_i\exp(-y_iF(x_i))$ for the loss at the current score. On an observation correctly classified by $h$, $y_ih(x_i)=+1$, so the new exponential-loss term is multiplied by $e^{-\alpha}$. On an incorrectly classified observation, $y_ih(x_i)=-1$, so that term is multiplied by $e^\alpha$. Dividing the new loss by the old one therefore gives

\frac{L(F+\alpha h)}{L(F)} =\sum_{i=1}^nD_i\exp(-\alpha y_ih(x_i)) =(1-\epsilon(h))e^{-\alpha}+\epsilon(h)e^\alpha =:g_{\epsilon(h)}(\alpha).

Thus, once the current weights are fixed, minimizing the loss along a candidate direction is a one-variable problem. The normalization by the current loss is positive and does not depend on the candidate or on $\alpha$, so minimizing this ratio is equivalent to minimizing the new loss itself.

Worked Example: Comparing Three Candidate Directions

Suppose the current normalized weights on four observations are $D=(0.4,0.3,0.2,0.1)$. Candidate $h_A$ makes an error only on observation 3; $h_B$ makes an error only on observation 2; and $h_C$ makes errors on observations 1 and 3. Their weighted errors are

\epsilon(h_A)=0.2,\qquad \epsilon(h_B)=0.3,\qquad \epsilon(h_C)=0.4+0.2=0.6.

For $h_A$, the minimizing step, derived below, is $\alpha_A=\tfrac12\log((1-0.2)/0.2)=\tfrac12\log 4$. Its loss ratio is $2\sqrt{0.2(0.8)}=0.8$.

For $h_B$, the minimizing step is $\alpha_B=\tfrac12\log(0.7/0.3)$, and its loss ratio is $2\sqrt{0.3(0.7)}=\sqrt{0.84}\approx0.9165$. For $h_C$, the error exceeds one half, so its best allowed step is $\alpha_C=0$, with ratio $1$. Therefore $h_A$ gives the largest decrease in loss among these three directions. The comparison concerns the loss after each direction has been optimized, not merely the errors before a step is chosen.

The Exact Nonnegative Step

Theorem: Let a candidate rule have weighted error $\epsilon\in[0,1]$. For the loss ratio $g_\epsilon(\alpha)=(1-\epsilon)e^{-\alpha}+\epsilon e^\alpha$, minimized over finite $\alpha\geq0$:

If $0<\epsilon<1/2$, the unique minimizer is $\alpha^*=\tfrac12\log((1-\epsilon)/\epsilon)$, and the minimum ratio is $2\sqrt{\epsilon(1-\epsilon)}$.
If $1/2\leq\epsilon\leq1$, the minimizer is $\alpha^*=0$, and the minimum ratio is $1$.
If $\epsilon=0$, the infimum is $0$, but no finite $\alpha$ attains it.

Proof. The derivative and second derivative are

g_\epsilon'(\alpha)=-(1-\epsilon)e^{-\alpha}+\epsilon e^\alpha, \qquad g_\epsilon''(\alpha)=(1-\epsilon)e^{-\alpha}+\epsilon e^\alpha.

For $0<\epsilon<1$, the second derivative is positive, so the function is strictly convex. A stationary point solves $\epsilon e^\alpha=(1-\epsilon)e^{-\alpha}$, or $e^{2\alpha}=(1-\epsilon)/\epsilon$. If $0<\epsilon<1/2$, this gives a positive $\alpha^*=\tfrac12\log((1-\epsilon)/\epsilon)$; strict convexity makes it the unique minimizer. Substitution yields \[ g_\epsilon(\alpha^*)=(1-\epsilon)\sqrt{\frac{\epsilon}{1-\epsilon}} +\epsilon\sqrt{\frac{1-\epsilon}{\epsilon}} =2\sqrt{\epsilon(1-\epsilon)}. \] If $1/2\leq\epsilon<1$, then $g_\epsilon'(0)=2\epsilon-1\geq0$. Since $g_\epsilon'$ is increasing, $g_\epsilon$ is nondecreasing on $[0,\infty)$, and its minimum is $g_\epsilon(0)=1$. This also covers $\epsilon=1/2$, where the derivative at zero is zero and is positive for $\alpha>0$. At $\epsilon=1$, $g_\epsilon(\alpha)=e^\alpha$, whose minimum over the allowed range is likewise $1$ at zero. Finally, if $\epsilon=0$, then $g_0(\alpha)=e^{-\alpha}>0$ for every finite $\alpha$, while $e^{-\alpha}\to0$ as $\alpha\to\infty$. The infimum is zero but is not attained. $\square$

Worked Example: Updating the Weights After a Step

Suppose the current weights are $D=(0.5,0.3,0.2)$, and a candidate rule is correct on observations 1 and 2 but wrong on observation 3. Its weighted error is $0.2$, so the exact step is $\alpha=\tfrac12\log 4=\log 2$. The loss ratio is

Z=(0.8)e^{-\alpha}+0.2e^\alpha =0.8(0.5)+0.2(2)=0.8.

The updated normalized weights are obtained by multiplying correct examples by $e^{-\alpha}=0.5$, incorrect examples by $e^\alpha=2$, and dividing by $Z$:

D_1'=\frac{0.5(0.5)}{0.8}=0.3125,\qquad D_2'=\frac{0.3(0.5)}{0.8}=0.1875,\qquad D_3'=\frac{0.2(2)}{0.8}=0.5.

These weights are positive and sum to $0.3125+0.1875+0.5=1$. The rule’s previously misclassified observation now carries half the total weight. This change is why the next round’s candidate errors must be calculated under the updated weights, rather than under the original distribution.

Why the Smallest Weighted Error Is the Best Direction

For a finite candidate set, optimizing each rule’s nonnegative step produces a direct comparison. The optimized ratio is $2\sqrt{\epsilon(1-\epsilon)}$ when the error is below one half, and $1$ when the error is at least one half. On $[0,1/2]$, the function $2\sqrt{\epsilon(1-\epsilon)}$ is increasing: if $0\leq u<v\leq1/2$, then $v(1-v)-u(1-u)=(v-u)(1-u-v)\geq0$. It follows that a smaller error in this range cannot have a larger optimized loss ratio.

Theorem: Let $\mathcal H$ be a finite set of candidate binary rules, and let $\epsilon_{\min}=\min_{h\in\mathcal H}\epsilon(h)$. If $0<\epsilon_{\min}<1/2$, then every rule attaining $\epsilon_{\min}$, paired with its exact nonnegative line-minimizing step, attains the smallest possible loss ratio among all candidate rules. The minimum ratio is $2\sqrt{\epsilon_{\min}(1-\epsilon_{\min})}$.

Proof. Any candidate with error $\epsilon\geq1/2$ has minimum ratio $1$. A candidate with error in $[\epsilon_{\min},1/2)$ has minimum ratio $2\sqrt{\epsilon(1-\epsilon)}$, which is at least $2\sqrt{\epsilon_{\min}(1-\epsilon_{\min})}$ by the monotonicity just shown. Since $0<\epsilon_{\min}<1/2$, this latter ratio is strictly less than $1$. A candidate attaining $\epsilon_{\min}$ therefore has a strictly smaller optimized ratio than any candidate with error at least one half, and no candidate with error between $\epsilon_{\min}$ and one half can do better. This proves the claim. $\square$

The condition on $\epsilon_{\min}$ matters. If $\epsilon_{\min}=0$, a perfect rule has loss ratio $e^{-\alpha}$, which approaches zero but has no finite minimizing step. If every candidate has error at least one half, the best permitted step for each is zero; choosing the smallest error then does not produce a positive loss decrease. These cases should not be folded into a claim about an attained, positive coefficient.

Worked Example: A Perfect Rule Has No Finite Best Step

Suppose one candidate classifies every training observation correctly under the current weights, so $\epsilon=0$. Its loss ratio after a step $\alpha$ is $g_0(\alpha)=e^{-\alpha}$. At $\alpha=2$, the ratio is $e^{-2}\approx0.1353$; at $\alpha=5$, it is $e^{-5}\approx0.0067$. Every finite step leaves a positive ratio, and increasing the step makes the ratio smaller. Thus the infimum is zero, but there is no finite coefficient that attains it. In an implementation, a finite step cap or other convention may be used, but that is an additional choice rather than the exact line minimizer.

What “Coordinate Descent” Means Here

For a fixed dictionary of rules, each rule is a direction in the vector of training scores. If $H$ is the $n\times M$ matrix with entries $H_{ij}=h_j(x_i)$, then the score vector is $H\beta$, and the loss is $\sum_i e^{-y_i(H\beta)_i}$. Holding the current score fixed and considering the change $F\mapsto F+\alpha h_j$ is a one-coordinate line search: all other contributions are held fixed while the coefficient of direction $h_j$ is increased by $\alpha$. The current weighted error determines the exact best nonnegative increment along that ray.

AdaBoost is most precisely viewed as forward stagewise coordinate descent. At each round it selects a direction from the finite candidate set and adds a nonnegative increment. This differs from unrestricted coordinate descent on a fixed coefficient vector: unrestricted minimization of an already-positive coefficient could also decrease it, whereas the standard AdaBoost step only adds to the current score. If a rule is selected again, its new increment adds to its existing total coefficient; the algorithm does not generally revisit that coefficient to optimize it freely in both directions.

This interpretation separates two decisions that are sometimes conflated. The weak-rule selection chooses the direction, by comparing weighted errors; the line search chooses the size of the step, by the formula for $\alpha^*$. The equivalence between smallest error and largest loss reduction holds for the exact one-direction optimization under the stated condition, not for arbitrary step sizes or every conceivable optimization over all coefficients at once.

Common Mistake

Wrong reasoning: “A rule with the smallest weighted error always has a finite optimal coefficient, so AdaBoost can exactly minimize the loss in that direction.”

Correction: A smallest error of zero is possible. Then the loss ratio is $e^{-\alpha}$, whose infimum is approached only as $\alpha$ grows without bound. The exact finite minimizer formula applies when the error is strictly between zero and one half. Errors at least one half have best nonnegative step zero. Keep these boundary cases explicit when interpreting a line search.

Key takeaway: With current example weights fixed, the exponential-loss ratio for adding a binary rule is $(1-\epsilon)e^{-\alpha}+\epsilon e^\alpha$. For an error strictly between zero and one half, its exact minimizing step is $\tfrac12\log((1-\epsilon)/\epsilon)$; among a finite candidate set whose smallest error lies in that interval, the smallest-error rule gives the largest exact loss reduction.

Check Your Understanding

Use the one-direction loss ratio to answer these questions.

For a candidate with weighted error $0.25$, calculate its exact nonnegative minimizing step and the resulting loss ratio.
Explain why a rule with weighted error $0.7$ should receive a zero step when step sizes are constrained to be nonnegative.
What happens to the line minimization when the weighted error is exactly zero? Is the infimum attained?
State the condition under which a smallest-weighted-error rule among finitely many candidates is guaranteed to yield the largest exact loss reduction.
In what sense is AdaBoost stagewise coordinate descent, and how does its nonnegative increment differ from unrestricted coordinate minimization?