The AdaBoost algorithm was designed to combine many "weak" hypotheses that
perform slightly better than random guessing into a "strong" hypothesis that
has very low error. We study the rate at which AdaBoost iteratively converges
to the minimum of the "exponential loss." Unlike previous work, our proofs do
not require a weak-learning assumption, nor do they require that minimizers of
the exponential loss are finite. Our first result shows that at iteration $t$,
the exponential loss of AdaBoost's computed parameter vector will be at most
$\epsilon$ more than that of any parameter vector of $\ell_1$-norm bounded by
$B$ in a number of rounds that is at most a polynomial in $B$ and $1/\epsilon$.
We also provide lower bounds showing that a polynomial dependence on these
parameters is necessary. Our second result is that within $C/\epsilon$
iterations, AdaBoost achieves a value of the exponential loss that is at most
$\epsilon$ more than the best possible value, where $C$ depends on the dataset.
We show that this dependence of the rate on $\epsilon$ is optimal up to
constant factors, i.e., at least $\Omega(1/\epsilon)$ rounds are necessary to
achieve within $\epsilon$ of the optimal exponential loss.

本文研究了 AdaBoost 算法的收敛速度，证明了其迭代收敛速度具有多项式上界，同时提供了针对多项式依赖的下界，在不需要弱学习假设和指数损失最小值有限等限制的情况下实现了优化的结果。

AdaBoost 算法的收敛速度

The Rate of Convergence of AdaBoost

We present a new online boosting algorithm for adapting the weights of a
boosted classifier, which yields a closer approximation to Freund and
Schapire's AdaBoost algorithm than previous online boosting algorithms. We also
contribute a new way of deriving the online algorithm that ties together
previous online boosting work. We assume that the weak hypotheses were selected
beforehand, and only their weights are updated during online boosting. The
update rule is derived by minimizing AdaBoost's loss when viewed in an
incremental form. The equations show that optimization is computationally
expensive. However, a fast online approximation is possible. We compare
approximation error to batch AdaBoost on synthetic datasets and generalization
error on face datasets and the MNIST dataset.

我们提出了一种新的在线增强算法，用于调整分类器权重，该算法与 Freund 和 Schapire 的 AdaBoost 算法更接近，同时还贡献了一种得出在线算法的新方法，其将以前的在线增强工作联系在一起。