The Rate of Convergence of AdaBoost

Introduction

The AdaBoost algorithm of Freund and Schapire (1997) was designed to combine many “weak” hypotheses that perform slightly better than random guessing into a “strong” hypothesis that has very low error. Despite extensive theoretical and empirical study, basic properties of AdaBoost’s convergence are not fully understood. In this work, we focus on one of those properties, namely, to find convergence rates that hold in the absence of any simplifying assumptions. Such assumptions, relied upon in much of the preceding work, make it easier to prove a fast convergence rate for AdaBoost, but often do not hold in the cases where AdaBoost is commonly applied.

where $\bm{\lambda}=\langle\lambda_{1},\ldots,\lambda_{N}\rangle$ is a vector of weights or parameters. In each iteration, a coordinate descent algorithm moves some distance along some coordinate direction $\lambda_{j}$. For AdaBoost, the coordinate directions correspond to the individual weak hypotheses. Thus, on each round, AdaBoost chooses some weak hypothesis and step length, and adds these to the current weighted combination of weak hypotheses, which is equivalent to updating a single weight. The direction and step length are so chosen that the resulting vector $\bm{\lambda}^{t}$ in iteration $t$ yields a lower value of the exponential loss than in the previous iteration, ${L}(\bm{\lambda}^{t})<{L}(\bm{\lambda}^{t-1})$. This repeats until it reaches a minimizer if one exists. It was shown by Collins et al. (2002), and later by Zhang and Yu (2005), that AdaBoost asymptotically converges to the minimum possible exponential loss. That is,

However, that work did not address a convergence rate to the minimizer of the exponential loss.

Our work specifically addresses a recent conjecture of Schapire (2010) stating that there exists a positive constant $c$ and a polynomial ${\rm poly}()$ such that for all training sets and all finite sets of weak hypotheses, and for all $B>0$,

We provide also a convergence rate of AdaBoost to the minimum value of the exponential loss. Namely, 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. This convergence rate is different from the one discussed above in that it has better dependence on $\epsilon$ (in fact the dependence is optimal, as we show), and does not depend on the best solution within a ball of size $B$. However, this second convergence rate cannot be used to prove (1) since in certain worst case situations, we show the constant $C$ may be larger than $2^{m}$ (although usually it will be much smaller).

Within the proof of the second convergence rate, we provide a lemma (called the decomposition lemma) that shows that the training set can be split into two sets of examples: the “finite margin set,” and the “zero loss set.” Examples in the finite margin set always make a positive contribution to the exponential loss, and they never lie too far from the decision boundary. Examples in the zero loss set do not have these properties. If we consider the exponential loss where the sum is only over the finite margin set (rather than over all training examples), it is minimized by a finite $\bm{\lambda}$. The fact that the training set can be decomposed into these two classes is the key step in proving the second convergence rate.

This problem of determining the rate of convergence is relevant in the proof of the consistency of AdaBoost given by Bartlett and Traskin (2007), where it has a direct impact on the rate at which AdaBoost converges to the Bayes optimal classifier (under suitable assumptions). It may also be relevant to practitioners who wish to have a guarantee on the exponential loss value at iteration $t$ (although, in general, minimization of the exponential loss need not be perfectly correlated with test accuracy).

There have been several works that make additional assumptions on the exponential loss in order to attain a better bound on the rate, but those assumptions are not true in general, and cases are known where each of these assumptions are violated. For instance, better bounds are proved by Rätsch et al. (2002) using results from Luo and Tseng (1992), but these appear to require that the exponential loss be minimized by a finite $\bm{\lambda}$, and also depend on quantities that are not easily measured. There are many cases where ${L}$ does not have a finite minimizer; in fact, one such case is provided by Schapire (2010). Shalev-Shwartz and Singer (2008) have proven bounds for a variant of AdaBoost. Zhang and Yu (2005) also have given rates of convergence, but their technique requires a bound on the change in the size of $\bm{\lambda}^{t}$ at each iteration that does not necessarily hold for AdaBoost. Many classic results are known on the convergence of iterative algorithms generally (see for instance Luenberger and Ye, 2008; Boyd and Vandenberghe, 2004); however, these typically start by assuming that the minimum is attained at some finite point in the (usually compact) space of interest, assumptions that do not generally hold in our setting. When the weak learning assumption holds, there is a parameter $\gamma>0$ that governs the improvement of the exponential loss at each iteration. Freund and Schapire (1997) and Schapire and Singer (1999) showed that the exponential loss is at most $e^{-2t\gamma^{2}}$ after $t$ rounds, so AdaBoost rapidly converges to the minimum possible loss under this assumption.

In Section 2 we summarize the coordinate descent view of AdaBoost. Section 3 contains the proof of the conjecture, with associated lower bounds proved in Section 3.3. Section 4 provides the $C/\epsilon$ convergence rate. The proof of the decomposition lemma is given in Section 4.2.

Coordinate Descent View of AdaBoost

Since each $h_{t}$ is equal to $\hbar_{j_{t}}$ for some $j_{t}$, $F$ can also be written $F(x)=\sum_{j=1}^{{N}}\lambda_{j}\hbar_{j}(x)$ for a vector of values $\bm{\lambda}=\langle\lambda_{1},\ldots\lambda_{{N}}\rangle$ (such vectors will sometimes also be referred to as combinations, since they represent combinations of weak hypotheses). In different notation, we can write AdaBoost as a coordinate descent algorithm on vector $\bm{\lambda}$. We define the feature matrix ${\mathbf{M}}$ elementwise by $M_{ij}=y_{i}\hbar_{j}(x_{i})$, so that this matrix contains all of the inputs to AdaBoost (the training examples and hypotheses). Then the exponential loss can be written more compactly as:

where $({\mathbf{M}}\bm{\lambda})_{i}$, the $i^{\textrm{th}}$ coordinate of the vector ${\mathbf{M}}\bm{\lambda}$, is the (unnormalized) margin achieved by vector $\bm{\lambda}$ on training example $i$.

Coordinate descent algorithms choose a coordinate at each iteration where the directional derivative is the steepest, and choose a step that maximally decreases the objective along that coordinate. To perform coordinate descent on the exponential loss, we determine the coordinate $j_{t}$ at iteration $t$ as follows, where $\mathbf{e}_{j}$ is a vector that is 1 in the $j^{\textrm{th}}$ position and 0 elsewhere:

We can show that this is equivalent to the weak learning step of AdaBoost. Unraveling the recursion in Figure 1 for AdaBoost’s weight vector $D_{t}$, we can see that $D_{t}(i)$ is proportional to

The term in the exponent can also be rewritten in terms of the vector $\bm{\lambda}^{t}$, where $\lambda^{t}_{j}$ is the sum of $\alpha_{t}$’s where hypothesis $\hbar_{j}$ was chosen: $\sum_{t^{\prime}<t}\alpha_{t^{\prime}}\mathbf{1}_{[\hbar_{j}=h_{t^{\prime}}]}=\lambda_{t-1,j}$. The term in the exponent is:

where $(\cdot)_{i}$ denotes the $i$th component of a vector. This means $D_{t}(i)$ is proportional to $e^{-({\mathbf{M}}\bm{\lambda}^{t-1})_{i}}$. Eq. (2) can now be rewritten as

which is exactly the way AdaBoost chooses a weak hypothesis in each round (see Figure 1). The correlation $\sum_{i}D_{t}(i)M_{ij_{t}}$ will be denoted by $r_{t}$ and its absolute value $\left|r_{t}\right|$ denoted by $\delta_{t}$. The quantity $\delta_{t}$ is commonly called the edge for round $t$. The distance $\alpha_{t}$ to travel along direction $j_{t}$ is found for coordinate descent via a linesearch (see for instance Mason et al., 2000):

and dividing both sides by the normalization factor,

just as in Figure 1. Thus, AdaBoost is equivalent to coordinate descent on $L(\bm{\lambda})$. With this choice of step length, it can be shown (Freund and Schapire, 1997) that the exponential loss drops by an amount depending on the edge:

Our rate bounds also hold when the weak-hypotheses are confidence-rated, that is, giving real-valued predictions in $[-1,+1]$, so that $h:\mathcal{X}\to[-1,+1]$. In that case, the criterion for picking a weak hypothesis in each round remains the same, that is, at round $t$, an $\hbar_{j_{t}}$ maximizing the absolute correlation $j_{t}\in\textrm{argmax}_{j}\left|\sum_{i=1}^{m}e^{-({\mathbf{M}}\bm{\lambda}^{t-1})_{i}}M_{ij}\right|$, is chosen, where $M_{ij}$ may now be non-integral. An exact analytical line search is no longer possible, but if the step size is chosen in the same way,

then Freund and Schapire (1997) and Schapire and Singer (1999) show that a similar drop in the loss is still guaranteed:

With confidence rated hypotheses, other implementations may choose the step size in a different way. However, in this paper, by “AdaBoost” we will always mean the version in (Freund and Schapire, 1997; Schapire and Singer, 1999) which chooses step sizes as in (3), and enjoys the loss guarantee as in (4). That said, all our proofs work more generally, and are robust to numerical inaccuracies in the implementation. In other words, even if the previous conditions are violated by a small amount, similar bounds continue to hold, although we leave out explicit proofs of this fact to simplify the presentation.

First convergence rate: Convergence to any target loss

The main result of this section is the following rate upper bound.

The high level idea behind the proof of the theorem is as follows. To show a fast rate, we require a large edge in each round, as indicated by (4). A large edge is guaranteed if the size of the current solution of AdaBoost is small. Therefore AdaBoost makes good progress if the size of its solution does not grow too fast. On the other hand, the increase in size of its solution is given by the step length, which in turn is proportional to the edge achieved in that round. Therefore, if the solution size grows fast, the loss also drops fast. Either way the algorithm makes good progress. In the rest of the section we make these ideas concrete through a sequence of lemmas.

We will also be interested in how they change as captured by

Notice that $\Delta R_{t}$ is always non-negative since AdaBoost decreases the loss, and hence the suboptimality, in each round. Let $T_{0}$ be the bound on the number of rounds in Theorem 1. We assume without loss of generality that $R_{0},\ldots,R_{T_{0}}$ and $S_{0},\ldots,S_{T_{0}}$ are all strictly positive, since otherwise the theorem holds trivially. Also, in the rest of the section, we restrict our attention entirely to the first $T_{0}$ rounds of boosting. We first show that a ${\rm poly}(B,\varepsilon^{-1})$ rate of convergence follows if the edge is always polynomially large compared to the suboptimality.

If for some constants $c_{1},c_{2}$, where $c_{2}>1/2$, the edge satisfies $\delta_{t}\geq B^{-c_{1}}R_{t-1}^{c_{2}}$ in each round $t$, then AdaBoost achieves at most $L(\bm{\lambda}^{*})+\varepsilon$ loss after $2B^{2c_{1}}(\varepsilon\ln 2)^{1-2c_{2}}$ rounds.

Proof From the definition of $R_{t}$ and (4) we have

Combining the above with the inequality $e^{x}\geq 1+x$, and the assumption on the edge

Let $T=\lceil 2B^{2c_{1}}(\varepsilon\ln 2)^{1-2c_{2}}\rceil$ be the bound on the number of rounds in the lemma. If any of $R_{0},\ldots,R_{T}$ is negative, then by monotonicity $R_{T}<0$ and we are done. Otherwise, they are all non-negative. Then, applying Lemma 32 from the Appendix to the sequence $R_{0},\ldots,R_{T}$, and using $c_{2}>1/2$ we get

If either $\varepsilon$ or $L(\bm{\lambda}^{*})$ is greater than 1, then the lemma follows since $L(\bm{\lambda}^{T})\leq L(\bm{\lambda}^{0})=1<L(\bm{\lambda}^{*})+\varepsilon$. Otherwise,

where the second inequality uses $e^{x}\leq 1+(1/\ln 2)x$ for $x\in[0,\ln 2]$. We next show that large edges are achieved provided $S_{t}$ is small compared to $R_{t}$.

In each round $t$, the edge satisfies $\delta_{t}\geq R_{t-1}/S_{t-1}$.

Proof For any combination $\bm{\lambda}$, define $p_{\bm{\lambda}}$ as the distribution on examples $\left\{1,\ldots,m\right\}$ that puts weight proportional to the loss $D_{\bm{\lambda}}(i)=e^{-({\mathbf{M}}\bm{\lambda})_{i}}/(mL(\bm{\lambda}))$. Choose any $\bm{\lambda}$ suffering at most the target loss $L(\bm{\lambda})\leq L(\bm{\lambda}^{*})$. By non-negativity of relative entropy we get

Note that $D_{\bm{\lambda}^{t-1}}$ is the distribution $D_{t}$ that AdaBoost creates in round $t$. The above summation can be rewritten as

Since the previous holds for any $\bm{\lambda}$ suffering less than the target loss, the last expression is at most $\delta_{t}S_{t-1}$. Combining this with (7) completes the proof. To complete the proof of Theorem 1, we show $S_{t}$ is small compared to $R_{t}$ in rounds $t\leq T_{0}$ (during which we have assumed $S_{t},R_{t}$ are all positive). In fact we prove:

For any $t\leq T_{0}$, $S_{t}\leq B^{3}R_{t}^{-2}$.

This, along with Lemmas 2 and 3, immediately proves Theorem 1. The bound on $S_{t}$ in Lemma 4 can be proven if we can first show $S_{t}$ grows slowly compared to the rate at which the suboptimality $R_{t}$ falls. Intuitively this holds since growth in $S_{t}$ is caused by a large step, which in turn will drive down the suboptimality. In fact we can prove the following.

In any round $t\leq T_{0}$, we have $\frac{2\Delta R_{t}}{R_{t-1}}\geq\frac{\Delta S_{t}}{S_{t-1}}$.

Proof Firstly, it follows from the definition of $S_{t}$ that $\Delta S_{t}\leq\lVert\bm{\lambda}^{t}-\bm{\lambda}^{t-1}\rVert_{1}=\left|\alpha_{t}\right|$. Next, using (5) and (3) we may write $\Delta R_{t}\geq\Upsilon(\delta_{t})\left|\alpha_{t}\right|$, where the function $\Upsilon$ has been defined in (Rätsch and Warmuth, 2005) as

It is known (Rätsch and Warmuth, 2005; Rudin et al., 2007) that $\Upsilon(x)\geq x/2$ for $x\in$. Combining and using Lemma 3,

Rearranging completes the proof. Using this we may prove Lemma 4.

Proof We first show $S_{0}\leq B^{3}R_{0}^{-2}$. Note, $S_{0}\leq\lVert\bm{\lambda}^{*}-\bm{\lambda}^{0}\rVert_{1}=B$, and by definition the quantity $R_{0}=-\ln\left(\frac{1}{m}\sum_{i}e^{-({\mathbf{M}}\bm{\lambda}^{*})_{i}}\right)$. The quantity $({\mathbf{M}}\bm{\lambda}^{*})_{i}$ is the inner product of row $i$ of matrix ${\mathbf{M}}$ with the vector $\bm{\lambda}^{*}$. Since the entries of ${\mathbf{M}}$ lie in $[-1,+1]$, this is at most $\lVert\bm{\lambda}^{*}\rVert_{1}=B$. Therefore $R_{0}\leq-\ln\left(\frac{1}{m}\sum_{i}e^{-B}\right)=B$, which is what we needed.

To complete the proof, we show that $R_{t}^{2}S_{t}$ is non-increasing. It suffices to show for any $t$ the inequality $R_{t}^{2}S_{t}\leq R_{t-1}^{2}S_{t-1}$. This holds by the following chain:

where the first inequality follows from $e^{x}\geq 1+x$, and the second one from Lemma 5. This completes the proof of Theorem 1. Although our bound provides a rate polynomial in $B,\varepsilon^{-1}$ as desired by the conjecture in (Schapire, 2010), the exponents are rather large, and (we believe) not tight. One possible source of slack is the bound on $S_{t}$ in Lemma 4. Qualitatively, the distance $S_{t}$ to some solution having target loss should decrease with rounds, whereas Lemma 4 only says it does not increase too fast. Improving this will directly lead to a faster convergence rate. In particular, showing that $S_{t}$ never decreases would imply a $B^{2}/\varepsilon$ rate of convergence. Whether or not the monotonicity of $S_{t}$ holds, we believe that the obtained rate bound is probably true, and state it as a conjecture.

For any $\bm{\lambda}^{*}$ and $\varepsilon>0$, AdaBoost converges to within $L(\bm{\lambda}^{*})+\varepsilon$ loss in $O(B^{2}/\varepsilon)$ rounds, where the order notation hides only absolute constants.

As evidence supporting the conjecture, we show in the next section how a minor modification to AdaBoost can achieve the above rate.

2 Faster rates for a variant

For any $\bm{\lambda}^{*},\varepsilon>0$, AdaBoost.S achieves at most $L(\bm{\lambda}^{*})+\varepsilon$ loss within $3\lVert\bm{\lambda}^{*}\rVert_{1}^{2}/\varepsilon$ rounds.

The proof is similar to that in the previous section. Reusing the same notation, note that proof of Lemma 2 continues to hold (with very minor modifications to that are straightforward). Next we can exploit the changes in AdaBoost.S to show an improved version of Lemma 3. Intuitively, scaling back has the effect of preventing the weights on the weak hypotheses from becoming “too large”, and we may show

In each round $t$, the edge satisfies $\delta_{t}\geq R_{t-1}/B$.

Proof We will reuse parts of the proof of Lemma 3. Setting $\bm{\lambda}=\bm{\lambda}^{*}$ in (6) we may write

The first summation can be upper bounded as in (7) by $\delta_{t}\lVert\bm{\lambda}^{*}\rVert=\delta_{t}B$. We will next show that the second summation is non-positive, which will complete the proof. The scaling step was added just so that this last fact would be true.

In experiments we ran, the scaling back never occurs. For such datasets, AdaBoost and AdaBoost.S are identical. We believe that even for contrived examples, the rescaling could happen only a few times, implying that both AdaBoost and AdaBoost.S would enjoy the convergence rates of Theorem 7. In the next section, we construct rate lower bound examples to show that this is nearly the best rate one can hope to show.

3 Lower-bounds

Suppose the feature matrix ${\mathbf{M}}$ corresponding to a dataset has two rows with $\left\{-1,+1\right\}$ entries which are complements of each other, i.e., there are two examples on which any hypothesis gets one wrong and one correct prediction. Then the number of rounds required to achieve a target loss $L^{*}$ is at least $\inf\left\{\lVert\bm{\lambda}\rVert_{1}:L(\bm{\lambda})\leq L^{*}\right\}/(2\ln m)$.

Proof We first show that the two examples corresponding to the complementary rows in ${\mathbf{M}}$ both satisfy a certain margin boundedness property. Since each hypothesis predicts oppositely on these, in any round $t$ their margins will be of equal magnitude and opposite sign. Unless both margins lie in $[-\ln m,\ln m]$, one of them will be smaller than $-\ln m$. But then the exponential loss $L(\bm{\lambda}^{t})=(1/m)\sum_{j}e^{-({\mathbf{M}}\bm{\lambda}^{t})_{j}}$ in that round will exceed $1$, a contradiction since the losses are non-increasing through rounds, and the loss at the start was $1$. Thus, assigning one of these examples the index $i$, we have the absolute margin $\left|({\mathbf{M}}\bm{\lambda}^{t})_{i}\right|$ is bounded by $\ln m$ in any round $t$. Letting ${\mathbf{M}}(i)$ denote the $i$th row of ${\mathbf{M}}$, the step length $\alpha_{t}$ in round $t$ therefore satisfies

and the statement of the lemma directly follows. When the weak hypotheses are abstaining (Schapire and Singer, 1999), it can make a definitive prediction that the label is $-1$ or $+1$, or it can “abstain” by predicting zero. No other levels of confidence are allowed, and the resulting feature matrix has entries in $\left\{-1,0,+1\right\}$. The next theorem constructs a feature matrix satisfying the properties of Lemma 9 and where additionally the smallest size of a solution achieving $L^{*}+\varepsilon$ loss is at least $\Omega(2^{m})\ln(1/\varepsilon)$, for some fixed $L^{*}$ and every $\varepsilon>0$.

Consider the following matrix ${\mathbf{M}}$ with $m$ rows (or examples) labeled $0,\ldots,m-1$ and $m-1$ columns labeled $1,\ldots,m-1$ (assume $m\geq 3$). The square sub-matrix ignoring row zero is an upper triangular matrix, with $1$’s on the diagonal, $-1$’s above the diagonal, and below the diagonal. Therefore row 1 is $(+1,-1,-1,\ldots,-1)$. Row 0 is defined to be just the complement of row 1. Then, for any $\varepsilon>0$, a loss of $2/m+\varepsilon$ is achievable on this dataset, but with large norms

Therefore, by Lemma 9, the minimum number of rounds required for reaching loss at most $2/m+\varepsilon$ is at least $\left(\frac{2^{m-2}-1}{2\ln m}\right)\ln(1/(3\varepsilon))$.

A picture of the matrix constructed in the above lemma for $m=5$ is shown in Figure 2.

Theorem 10 shows that when $\varepsilon$ is a small constant (say $\varepsilon=0.01$), and $\bm{\lambda}^{*}$ is some vector with loss $L^{*}+\varepsilon/2$, AdaBoost takes at least $\Omega(2^{m}/\ln m)$ steps to get within $\varepsilon/2$ of the loss achieved by $\bm{\lambda}^{*}$, that is, to within $L^{*}+\varepsilon$ loss. Since $m$ and $\varepsilon$ are independent quantities, this shows that a polynomial dependence on the norm of the reference solution is unavoidable, and this norm might be exponential in the number of training examples in the worst case.

Consider feature matrices containing only $\left\{-1,0,+1\right\}$ entries. If, for some constants $c$ and $\beta$, the bound in Theorem 1 can be replaced by $O\left(\lVert\bm{\lambda}^{*}\rVert_{1}^{c}\varepsilon^{-\beta}\right)$ for all such matrices, then $c\geq 1$. Further, for such matrices, the bound ${\rm poly}(1/\varepsilon,\lVert\bm{\lambda}^{*}\rVert_{1})$ in Theorem 1 cannot be replaced by ${\rm poly}(1/\varepsilon,m,N)$.

Proof of Lemma 10. We first lower bound the norm of solutions achieving loss at most $2/m+\varepsilon$. Observe that since rows 0 and 1 are complementary, any solution’s loss on just examples 0 and 1 will add up to at least $2/m$. Therefore, to get within $2/m+\varepsilon$, the margins on examples $2,\ldots,m-1$ should be at least $\ln\left(\left(m-2\right)/\left(m\varepsilon\right)\right)\geq\ln(1/(3\varepsilon))$ (for $m\geq 3$). Now, the feature matrix is designed so that the margins due to a combination $\bm{\lambda}$ satisfy the following recursive relationships:

Therefore, the margin on example $m-1$ is at least $\ln(1/(3\varepsilon))$ implies $\lambda_{m-1}\geq\ln(1/(3\varepsilon))$. Similarly, $\lambda_{m-2}\geq\ln(1/(3\varepsilon))+\lambda_{m-1}\geq 2\ln(1/(3\varepsilon))$. Continuing this way,

for $i=m-1,\ldots,2$. Hence $\lVert\bm{\lambda}\rVert_{1}\geq\ln(1/(3\varepsilon))(1+2+\ldots+2^{m-3})=(2^{m-2}-1)\ln(1/(3\varepsilon))$.

We end by showing that a loss of at most $2/m+\varepsilon$ is achievable. The above argument implies that if $\lambda_{i}=2^{m-1-i}$ for $i=2,\ldots,m-1$, then examples $2,\ldots,m-1$ attain margin exactly $1$. If we choose $\lambda_{1}=\lambda_{2}+\ldots+\lambda_{m-1}=2^{m-3}+\ldots+1=2^{m-2}-1$, then the recursive relationship implies a zero margin on example 1 (and hence example 0). Therefore the combination $\ln(1/\varepsilon)(2^{m-2}-1,2^{m-3},2^{m-4},\ldots,1)$ achieves a loss $(2+(m-2)\varepsilon)/m\leq 2/m+\varepsilon$, for any $\varepsilon>0$. We finally show that if the weak hypotheses are confidence-rated with arbitrary levels of confidence, so that the feature matrix is allowed to have non-integral entries in $[-1,+1]$, then the minimum norm of a solution achieving a fixed accuracy can be arbitrarily large. Our constructions will satisfy the requirements of Lemma 9, so that the norm lower bound translates into a rate lower bound.

Let $\nu>0$ be an arbitrary number, and let ${\mathbf{M}}$ be the (possibly) non-integral matrix with 4 examples and 2 weak hypotheses shown in Figure 3. Then for any $\varepsilon>0$, a loss of $1/2+\varepsilon$ is achievable on this dataset, but with large norms

Therefore, by Lemma 9, the number of rounds required to achieve loss at most $1/2+\varepsilon$ is at least $\ln(1/(2\varepsilon))\nu^{-1}/\ln(m)$.

Proof We first show a loss of $1/2+\varepsilon$ is achievable. Observe that the vector $\bm{\lambda}=(c,c)$, with $c=\nu^{-1}\ln(1/(2\varepsilon))$, achieves margins $0,0,\ln(1/(2\varepsilon)),\ln(1/(2\varepsilon))$ on examples $1,2,3,4$, respectively. Therefore $\bm{\lambda}$ achieves loss $1/2+\varepsilon$. We next show a lower bound on the norm of a solution achieving this loss. Observe that since the first two rows are complementary, the loss due to just the first two examples is at least $1/2$. Therefore, any solution $\bm{\lambda}=(\lambda_{1},\lambda_{2})$ achieving at most $1/2+\varepsilon$ loss overall must achieve a margin of at least $\ln(1/(2\varepsilon))$ on both the third and fourth examples. By inspecting the two columns, this implies

By the triangle inequality, $\lVert\bm{\lambda}\rVert_{1}\geq\lambda_{1}+\lambda_{2}$, and the lemma follows. Note that if $\nu=0$, then the optimal solution is found in zero rounds of boosting and has optimal loss $1$. However, even the tiniest perturbation $\nu>0$ causes the optimal loss to fall to $1/2$, and causes the rate of convergence to increase drastically. In fact, by Theorem 12, the number of rounds required to achieve any fixed loss below $1$ grows as $\Omega(1/\nu)$, which is arbitrarily large when $\nu$ is infinitesimal. We may conclude that with non-integral feature matrices, the dependence of the rate on the norm of a reference solution is absolutely necessary.

When using confidence rated weak-hypotheses with arbitrary confidence levels, the bound ${\rm poly}(1/\varepsilon,\lVert\bm{\lambda}^{*}\rVert_{1})$ in Theorem 1 cannot be replaced by any function of purely $m$, $N$ and $\varepsilon$ alone.

The construction in Figure 3 can be generalized to produce datasets with any number of examples that suffer the same poor rate of convergence as the one in Theorem 12. We discussed the smallest such construction, since we feel that it best highlights the drastic effect non-integrality can have on the rate.

In this section we saw how the norm of the reference solution is an important parameter for bounding the convergence rate. In the next section we investigate the optimal dependence of the rate on the parameter $\varepsilon$ and show that $\Omega(1/\varepsilon)$ rounds are necessary in the worst case.

Second convergence rate: Convergence to optimal loss

In the previous section, our rate bound depended on both the approximation parameter $\varepsilon$, as well as the size of the smallest solution achieving the target loss. For many datasets, the optimal target loss $\inf_{\bm{\lambda}}L(\bm{\lambda})$ cannot be realized by any finite solution. In such cases, if we want to bound the number of rounds needed to achieve within $\varepsilon$ of the optimal loss, the only way to use Theorem 1 is to first decompose the accuracy parameter $\varepsilon$ into two parts $\varepsilon=\varepsilon_{1}+\varepsilon_{2}$, find some finite solution $\bm{\lambda}^{*}$ achieving within $\varepsilon_{1}$ of the optimal loss, and then use the bound ${\rm poly}(1/\varepsilon_{2},\lVert\bm{\lambda}^{*}\rVert_{1})$ to achieve at most $L(\bm{\lambda}^{*})+\varepsilon_{2}=\inf_{\bm{\lambda}}L(\bm{\lambda})+\varepsilon$ loss. However, this introduces implicit dependence on $\varepsilon$ through $\lVert\bm{\lambda}^{*}\rVert_{1}$ which may not be immediately clear. In this section, we show bounds of the form $C/\varepsilon$, where the constant $C$ depends only on the feature matrix ${\mathbf{M}}$, and not on $\varepsilon$. Additionally, we show that this dependence on $\varepsilon$ is optimal in Lemma 31 of the Appendix, where $\Omega(1/\varepsilon)$ rounds are shown to be necessary for converging to within $\varepsilon$ of the optimal loss on a certain dataset. Finally, we note that the lower bounds in the previous section indicate that $C$ can be $\Omega(2^{m})$ in the worst case for integer matrices (although it will typically be much smaller), and hence this bound, though stronger than that of Theorem 1 with respect to $\varepsilon$, cannot be used to prove the conjecture in (Schapire, 2010), since the constant is not polynomial in the number of examples $m$.

The main result of this section is the following rate upper bound. A similar approach to solving this problem was taken independently by Telgarsky (2011).

AdaBoost reaches within $\varepsilon$ of the optimal loss in at most $C/\varepsilon$ rounds, where $C$ only depends on the feature matrix.

Our techniques build upon earlier work on the rate of convergence of AdaBoost, which have mainly considered two particular cases. In the first case, the weak learning assumption holds, that is, the edge in each round is at least some fixed constant. In this situation, Freund and Schapire (1997) and Schapire and Singer (1999) show that the optimal loss is zero, that no solution with finite size can achieve this loss, but AdaBoost achieves at most $\varepsilon$ loss within $O(\ln(1/\varepsilon))$ rounds. In the second case some finite combination of the weak classifiers achieves the optimal loss, and Rätsch et al. (2002), using results from Luo and Tseng (1992), show that AdaBoost achieves within $\varepsilon$ of the optimal loss again within $O(\ln(1/\varepsilon))$ rounds.

Here we consider the most general situation, where the weak learning assumption may fail to hold, and yet no finite solution may achieve the optimal loss. The dataset used in Lemma 31 and shown in Figure 4 exemplifies this situation. Our main technical contribution shows that the examples in any dataset can be partitioned into a zero-loss set and finite-margin set, such that a certain form of the weak learning assumption holds within the zero-loss set, while the optimal loss considering only the finite-margin set can be obtained by some finite solution. The two partitions provide different ways of making progress in every round, and one of the two kinds of progress will always be sufficient for us to prove Theorem 14.

We next state our decomposition result, illustrate it with an example, and then state several lemmas quantifying the nature of the progress we can make in each round. Using these lemmas, we prove Theorem 14.

(Decomposition Lemma) For any dataset, there exists a partition of the set of training examples $X$ into a (possibly empty) zero-loss set $Z$ and a (possibly empty) finite-margin set $F=Z^{c}\stackrel{{\scriptstyle\vartriangle}}{{=}}X\setminus Z$ such that the following hold simultaneously :

The optimal loss considering only examples within $F$ is achieved by some finite combination $\bm{\eta}^{*}$.

There is a constant $\mu_{\max}<\infty$, such that for any combination $\bm{\eta}$ with bounded loss on the finite-margin set, $\sum_{i\in F}e^{-({\mathbf{M}}\bm{\eta})_{i}}\leq m$, the margin $({\mathbf{M}}\bm{\eta})_{i}$ for any example $i$ in $F$ lies in the bounded interval $[-\ln m,\mu_{\max}]$.

A proof is deferred to the next section. The decomposition lemma immediately implies that the vector $\bm{\eta}^{*}+\infty\cdot\bm{\eta}^{\dagger}$, which denotes $\left(\bm{\eta}^{*}+c\bm{\eta}^{\dagger}\right)$ in the limit $c\to\infty$, is an optimal solution, achieving zero loss on the zero-loss set, but only finite margins (and hence positive losses) on the finite-margin set (thereby justifying the names).

Before proceeding, we give an example dataset and indicate the zero-loss set, finite-margin set, $\bm{\eta}^{*}$ and $\bm{\eta}^{\dagger}$ to illustrate our definitions. Consider a dataset with three examples $\left\{a,b,c\right\}$ and two hypotheses $\left\{\hbar_{1},\hbar_{2}\right\}$ and the feature matrix ${\mathbf{M}}$ in Figure 4. Here $+$ means correct ($M_{ij}=+1$) and $-$ means wrong ($M_{ij}=-1$). The optimal solution is $\infty\cdot(\hbar_{1}+\hbar_{2})$ with a loss of $2/3$. The finite-margin set is $\left\{a,b\right\}$, the zero-loss set is $\left\{c\right\}$, $\bm{\eta}^{\dagger}=(1/2,1/2)$ and $\bm{\eta}^{*}=(0,0)$; for this dataset these are unique. This dataset also serves as a lower-bound example in Lemma 31, where we show that $2/(9\varepsilon)$ rounds are necessary for AdaBoost to achieve loss at most $(2/3)+\varepsilon$.

Since $({\mathbf{M}}\bm{\eta}^{\dagger})_{i}=\sum_{j}\eta^{\dagger}_{j}({\mathbf{M}}\mathbf{e}_{j})_{i}$, we may rewrite the edge $\delta_{X}(\bm{\eta}^{\dagger};\bm{\lambda}^{t-1})$ as follows:

If the set $F$ were empty, then Lemma 16 implies an edge of $\gamma$ is available in each round. This in fact means that the weak learning assumption holds, and using (4), we can show an $O(\ln(1/\varepsilon)\gamma^{-2})$ bound matching the rate bounds of Freund and Schapire (1997) and Schapire and Singer (1999). So henceforth, we assume that $F$ is non-empty. Note that this implies that the optimal loss $K$ is at least $1$ (since any solution will get non-positive margin on some example in $F$), a fact we will use later in the proofs.

Lemma 16 says that the edge is large if the loss on the zero-loss set is large. On the other hand, when it is small, Lemmas 17 and 18 together show how AdaBoost can make good progress using the finite margin set. Lemma 17 uses second order methods to show how progress is made in the case where there is a finite solution. Similar arguments, under additional assumptions, have earlier appeared in (Rätsch et al., 2002).

We next lower bound possible values of the second derivative as follows:

A standard second-order result is (see e.g. Boyd and Vandenberghe, 2004, eqn. (9.9))

Notice the quantity inside the max is precisely the edge $\delta_{F}(\mathbf{e}_{j};\bm{\lambda})$ in direction $j$. Combining everything, the maximum possible edge is

where we define $C_{0}=2\lambda_{\min}^{2}N^{-1}m^{-1}e^{-\mu_{\max}}$.

So, if $\delta$ is the maximum edge in any direction, then

where, for the last inequality, we again used $K+\theta\leq m$. Therefore the loss after one more step is at most $(K+\theta)\sqrt{1-\delta^{2}}\leq(K+\theta)(1-\delta^{2}/2)\leq K+\theta-\frac{C_{0}}{4m}\theta$. Setting $C_{2}=C_{0}/(4m)$ completes the proof.

If $K+\theta_{t}$ denotes the loss in round $t$, then the above claim implies $\theta_{t}-\theta_{t+1}\geq C_{3}\theta_{t}^{2}$. Applying Lemma 32 to the sequence $\left\{\theta_{t}\right\}$ we have $1/\theta_{T}-1/\theta_{0}\geq C_{3}T$ for any $T$. Since $\theta_{0}\geq 0$, we have $T\leq 1/(C_{3}\theta_{T})$. Hence to achieve loss $K+\varepsilon$, $C_{3}^{-1}/\varepsilon$ rounds suffice. $\blacksquare$

2 Proof of the decomposition lemma

For any sequence $\bm{\eta}_{1},\bm{\eta}_{2},\ldots,$ of admissible combinations of weak classifiers, we can find a subsequence $\bm{\eta}_{(1)}=\bm{\eta}_{t_{1}},\bm{\eta}_{(2)}=\bm{\eta}_{t_{2}},\ldots,$ whose losses converge to zero on all examples in some fixed (possibly empty) subset $Z$ (the zero-loss set), and losses bounded away from zero in its complement $X\setminus Z$(the finite-margin set)

Proof We will build a zero-loss set and the final subsequence incrementally. Initially the set is empty. Pick the first example. If the infimal loss ever attained on the example in the sequence is bounded away from zero, then we do not add it to the set. Otherwise we add it, and consider only the subsequence whose $t^{\textrm{th}}$ element attains loss less than $1/t$ on the example. Beginning with this subsequence, we now repeat with other examples. The final sequence is the required subsequence, and the examples we have added form the zero-loss set. We apply Lemma 19 to some admissible sequence converging to the optimal loss (for instance, the one found by AdaBoost). Let us call the resulting subsequence $\bm{\eta}^{*}_{(t)}$, the obtained zero-loss set $Z$, and the finite-margin set $F=X\setminus Z$. The next lemma shows how to extract a single combination out of the sequence $\bm{\eta}^{*}_{(t)}$ that satisfies the properties in Item 1 of the decomposition lemma.

Suppose ${\mathbf{M}}$ is the feature matrix, $Z$ is a subset of the examples, and $\bm{\eta}_{(1)},\bm{\eta}_{(2)},\ldots,$ is a sequence of combinations of weak classifiers such that $Z$ is its zero loss set, and $X\setminus Z$ its finite loss set, that is, (8) holds. Then there is a combination $\bm{\eta}^{\dagger}$ of weak classifiers that achieves positive margin on every example in $Z$, and zero margin on every example in its complement $X\setminus Z$, that is:

Proof Since the $\bm{\eta}_{(t)}$ achieve arbitrarily large positive margins on $Z$, $\lVert\bm{\eta}_{(t)}\rVert$ will be unbounded, and it will be hard to extract a useful single solution out of them. On the other hand, the rescaled combinations $\bm{\eta}_{(t)}/\lVert\bm{\eta}_{(t)}\rVert$ lie on a compact set, and therefore have a limit point, which might have useful properties. We formalize this next.

We prove the statement of the lemma by induction on the total number of training examples $|X|$. If $X$ is empty, then the lemma holds vacuously for any $\bm{\eta}^{\dagger}$. Assume inductively for all $X$ of size less than $m>0$, and consider $X$ of size $m$. Since translating a vector along the null space of ${\mathbf{M}}$, $\ker{\mathbf{M}}=\left\{\mathbf{x}:{\mathbf{M}}\mathbf{x}=\mathbf{0}\right\}$, has no effect on the margins produced by the vector, assume without loss of generality that the $\bm{\eta}_{(t)}$’s are orthogonal to $\ker{\mathbf{M}}$. Also, since the margins produced on the zero loss set are unbounded, so are the norms of $\bm{\eta}_{(t)}$. Therefore assume (by picking a subsequence and relabeling if necessary) that $\lVert\bm{\eta}_{(t)}\rVert>t$. Let $\bm{\eta}^{\prime}$ be a limit point of the sequence $\bm{\eta}_{(t)}/\lVert\bm{\eta}_{(t)}\rVert$, a unit vector that is also orthogonal to the null-space. Then firstly $\bm{\eta}^{\prime}$ achieves non-negative margin on every example; otherwise by continuity for some extremely large $t$, the margin of $\bm{\eta}_{(t)}/\lVert\bm{\eta}_{(t)}\rVert$ on that example is also negative and bounded away from zero, and therefore $\bm{\eta}_{(t)}$’s loss is more than $m$, a contradiction to admissibility. Secondly, the margin of $\bm{\eta}^{\prime}$ on each example in $X\setminus Z$ is zero; otherwise, by continuity, for arbitrarily large $t$ the margin of $\bm{\eta}_{(t)}/\lVert\bm{\eta}_{(t)}\rVert$ on an example in $X\setminus Z$ is positive and bounded away from zero, and hence that example attains arbitrarily small loss in the sequence, a contradiction to (8). Finally, if $\bm{\eta}^{\prime}$ achieves zero margin everywhere in $Z$, then $\bm{\eta}^{\prime}$, being orthogonal to the null-space, must be $\mathbf{0}$, a contradiction since $\bm{\eta}^{\prime}$ is a unit vector. Therefore $\bm{\eta}^{\prime}$ must achieve positive margin on some non-empty subset $S$ of $Z$, and zero margins on every other example.

Next we use induction on the reduced set of examples $X^{\prime}=X\setminus S$. Since $S$ is non-empty, $|X^{\prime}|<m$. Further, using the same sequence $\bm{\eta}_{(t)}$, the zero-loss and finite-loss sets, restricted to $X^{\prime}$, are $Z^{\prime}=Z\setminus S$ and $(X\setminus Z)\setminus S=X\setminus Z$ (since $S\subseteq Z$) $=X^{\prime}\setminus Z^{\prime}$. By the inductive hypothesis, there exists some $\bm{\eta}^{\prime\prime}$ which achieves positive margins on $Z^{\prime}$, and zero margins on $X^{\prime}\setminus Z^{\prime}=X\setminus Z$. Therefore, by setting $\bm{\eta}^{\dagger}=\bm{\eta}^{\prime}+c\bm{\eta}^{\prime\prime}$ for a large enough $c$, we can achieve the desired properties. Applying Lemma 20 to the sequence $\bm{\eta}^{*}_{(t)}$ yields some convex combination $\bm{\eta}^{\dagger}$ having margin at least $\gamma>0$ (for some $\gamma$) on $Z$ and zero margin on its complement, proving Item 1 of the decomposition lemma. The next lemma proves Item 2.

The optimal loss considering only examples within $F$ is achieved by some finite combination $\bm{\eta}^{*}$.

3 Investigating the constants

In this section, we try to estimate the constant $C$ in Theorem 14. We show that it can be arbitrarily large for adversarial feature matrices with real entries (corresponding to confidence rated weak hypotheses), but has an upper-bound doubly exponential in the number of examples when the feature matrix has $\left\{-1,0,+1\right\}$ entries only. We also show that this doubly exponential bound cannot be improved without significantly changing the proof in the previous section.

By inspecting the proofs, we can bound the constant in Theorem 14 as follows.

The constant $C$ in Theorem 14 that emerges from the proofs is

where $m$ is the number of examples, $N$ is the number of hypotheses, $\gamma$ and $\mu_{\max}$ are as given by Items 1 and 3 of the decomposition lemma, and $\lambda_{\min}^{2}$ is the smallest positive eigenvalue of ${\mathbf{M}}_{F}^{T}{\mathbf{M}}_{F}$ (${\mathbf{M}}_{F}$ is the feature matrix restricted to the rows belonging to the finite margin set $F$).

Our bound on $C$ will be obtained by in turn bounding the quantities $\lambda_{\min}^{-1},\gamma^{-1},\mu_{\max}$. These are strongly related to the singular values of the feature matrix ${\mathbf{M}}$, and in general cannot be easily measured. In fact, when ${\mathbf{M}}$ has real entries, we have already seen in Section 3.3 that the rate can be arbitrarily large, implying these parameters can have very large values. Even when the matrix ${\mathbf{M}}$ has integer entries (that is, $-1,0,+1$), the next lemma shows that these quantities can be exponential in the number of examples.

There are examples of feature matrices with $-1,0,+1$ entries and at most $m$ rows or columns (where $m>10$) for which the quantities $\gamma^{-1},\lambda^{-1}$ and $\mu_{\max}$ are at least $\Omega(2^{m}/m)$.

Next we provide an example showing $\mu_{\max}$ can be $\Omega(2^{m}/m)$. Consider an $m\times(m-1)$ matrix ${\mathbf{M}}$. The bottom row of ${\mathbf{M}}$ is all $+1$. The upper $(m-1)\times(m-1)$ submatrix of ${\mathbf{M}}$ is a lower triangular matrix with $-1$ on the diagonal and $+1$ below the diagonal. Observe that if $\mathbf{y}^{T}=(2^{m-2},2^{m-3},\ldots,1,1)$, then $\mathbf{y}^{T}{\mathbf{M}}=\mathbf{0}$. Therefore, for any vector $\mathbf{x}$, the inner product of the margins ${\mathbf{M}}\mathbf{x}$ with $\mathbf{y}$ is zero: $\mathbf{y}^{T}M\mathbf{x}=0$. This implies that achieving positive margin on any example forces some other example to receive negative margin. By Item 1 of the decomposition lemma, the zero loss set in this dataset is empty, and all the examples belong to the finite loss set. Next, we choose a combination with at most $m$ loss that nevertheless achieves $\Omega(2^{m}/m)$ positive margin on some example. Let $\mathbf{x}^{T}=(1,2,4,\ldots,2^{m-2})$. Then $({\mathbf{M}}\mathbf{x})^{T}=(-1,-1,\ldots,-1,2^{m-1}-1)$. Then the margins using $\varepsilon\mathbf{x}$ are $(-\varepsilon,\ldots,-\varepsilon,\varepsilon(2^{m-1}-1))$ with total loss $(m-1)e^{\varepsilon}+e^{\varepsilon(1-2^{m-1})}$. Choose $\varepsilon=1/(2m)\leq 1$, so that the loss on examples corresponding to the first $m-1$ rows is at most $e^{\varepsilon}\leq 1+2\varepsilon=1+1/m$, where the first inequality holds since $\varepsilon\in$. For $m>10$, the choice of $\varepsilon$ guarantees $1/(2m)=\varepsilon\geq(\ln m)/(2^{m-1}-1)$, so that the loss on the example corresponding to the bottom most row is $e^{-\varepsilon(2^{m-1}-1)}\leq e^{-\ln m}=1/m$. Therefore the net loss of $\varepsilon\mathbf{x}$ is at most $(m-1)(1+1/m)+1/m=m$. On the other hand the margin on the example corresponding to the last row is $\varepsilon(2^{m-1}-1)=(2^{m-1}-1)/(2m)=\Omega(2^{m}/m)$. The above result implies any bound on $C$ derived from Corollary 23 will be at least $2^{\Omega(2^{m}/m)}$ in the worst case. This does not imply that the best bound one can hope to prove is doubly exponential, only that our techniques in the previous section do not admit anything better. We next show that the bounds in Lemma 24 are nearly the worst possible.

Suppose each entry of ${\mathbf{M}}$ is $-1,0$ or $+1$. Then each of the quantities $\lambda_{\min}^{-1},\gamma^{-1}$ and $\mu_{\max}$ are at most $2^{O(m\ln m)}$.

The proof of Lemma 25 is rather technical, and we defer it to the Appendix. Lemma 25 and Corollary 23 together imply a convergence rate of $2^{2^{O(m\ln m)}}/\varepsilon$ to the optimal loss for integer matrices. This bound on $C$ is exponentially worse than the $\Omega(2^{m})$ lower bound on $C$ we saw in Section 3.3, a price we pay for obtaining optimal dependence on $\varepsilon$. In the next section we will see how to obtain ${\rm poly}(2^{m\ln m},\varepsilon^{-1})$ bounds, although with a worse dependence on $\varepsilon$. We end this section by showing, just for completeness, how a bound on the norm of $\bm{\eta}^{*}$ as defined in Item 2 of the decomposition lemma follows as a quick corollary to Lemma 25.

Suppose $\bm{\eta}^{*}$ is as given by Item 2 of the decomposition lemma. When the feature matrix has only $-1,0,+1$ entries, we may bound $\lVert\bm{\eta}^{*}\rVert_{1}\leq 2^{O(m\ln m)}$.

Proof Note that every entry of ${\mathbf{M}}_{F}\bm{\eta}^{*}$ lies in the range $[-\ln m,\mu_{\max}=2^{O(m\ln m)}]$, and hence $\lVert{\mathbf{M}}_{F}\bm{\eta}^{*}\rVert\leq 2^{O(m\ln m)}$. Next, we may choose $\bm{\eta}^{*}$ orthogonal to the null space of ${\mathbf{M}}_{F}$; then $\lVert\bm{\eta}^{*}\rVert\leq\lambda_{\min}^{-1}\lVert{\mathbf{M}}_{F}\bm{\eta}^{*}\rVert\leq 2^{O(m\ln m)}$. Since $\lVert\bm{\eta}^{*}\rVert_{1}\leq\sqrt{N}\lVert\bm{\eta}^{*}\rVert$, and the number of possible columns $N$ with $\left\{-1,0,+1\right\}$ entries is at most $3^{m}$, the proof follows.

Improved Estimates

In this section we shed more light on the rate bounds by cross-application of techniques from Sections 3 and 4. We obtain both new upper bounds for convergence to the optimal loss, as well as lower bounds for convergence to an arbitrary target loss. We also indicate what we believe might be the optimal bounds for either situation.

We first show how the finite rate bound of Theorem 1 along with the decomposition lemma yields a new rate of convergence to the optimal loss. Although the dependence on $\varepsilon$ is worse than in Theorem 14, the dependence on $m$ is nearly optimal. We will need the following key application of the decomposition lemma.

For feature matrices with $-1,0,+1$ entries, AdaBoost converges to within $\varepsilon$ of the optimal loss within $2^{O(m\ln m)}\varepsilon^{-(1+o(1))}$ rounds.

We next focus on lower bounds on the convergence rate to arbitrary target losses discussed in Section 3. We begin by showing the rate dependence on the norm of the solution as given in Lemma 9 holds for much more general datasets.

Suppose a feature matrix has only $\pm 1$ entries, and the finite loss set is non-empty. Then, for any coordinate descent procedure, the number of rounds required to achieve a target loss $\phi^{*}$ is at least

Proof It suffices to upper-bound the step size $\left|\alpha_{t}\right|$ in any round $t$ by at most $1+\ln m$. Notice that when the feature matrix has $\pm 1$ entries, a step in a direction that does not end up increasing the loss is at most of length $(1/2)\ln\left(\left(1+\delta\right)/\left(1-\delta\right)\right)$, where $\delta$ is the edge in that direction. Therefore, if $\delta_{t}$ is the maximum edge achievable in any direction, we have

Further, by (4), a large edge $\delta_{t}$ ensures that for some coordinate step, the new vector $\bm{\lambda}^{t}$ will have much smaller loss than the vector $\bm{\lambda}^{t-1}$ at the beginning of round $t$: $L(\bm{\lambda}^{t})\leq L(\bm{\lambda}^{t-1})\sqrt{1-\delta_{t}^{2}}$. On the other hand, before the step, the loss is at most $1$, $L(\bm{\lambda}^{t-1})\leq 1$, and after the step the loss is at most $1/m$ (since the optimal loss on a dataset with non-empty finite set is at least $1/m$): $L(\bm{\lambda}^{t})\geq 1/m$. Combining these inequalities we get

that is, $\sqrt{1-\delta_{t}^{2}}\geq 1/m$. Now the step length can be bounded as

We end by showing a new lower bound for the convergence rate to an arbitrary target loss studied in Section 3. Corollary 11 implies that the rate bound in Theorem 1 has to be at least polynomially large in the norm of the solution. We now show that a polynomial dependence on $\varepsilon^{-1}$ in the rate is unavoidable too. This shows that rates for competing with a finite solution are different from rates on a dataset where the optimum loss is achieved by a finite solution, since in the latter we may achieve a $O\left(\ln(1/\varepsilon)\right)$ rate.

Consider any dataset (e.g. the one in Figure 4) for which $\Omega(1/\varepsilon)$ rounds are necessary to get within $\varepsilon$ of the optimal loss. If there are constants $c$ and $\beta$ such that for any $\bm{\lambda}^{*}$ and $\varepsilon$, a loss of $L(\bm{\lambda}^{*})+\varepsilon$ can be achieved in at most $O(\lVert\bm{\lambda}^{*}\rVert_{1}^{c}\varepsilon^{-\beta})$ rounds, then $\beta\geq 1$.

Conclusion

For the second kind of convergence, using entirely separate techniques, we derived a $C/\varepsilon$ upper bound, and showed that this is tight up to constant factors. In the process, we showed a certain decomposition lemma that might be of independent interest. We also study the constants and show how they depend on certain intrinsic parameters related to the singular values of the feature matrix. We estimate the worst case values of these parameters, and considering feature matrices with only $\left\{-1,0,+1\right\}$ entries, this leads to a bound on the rate constant $C$ that is doubly exponential in the number of training examples. Since this is rather large, we also include bounds polynomial in both the number of training examples and the accuracy parameter $\varepsilon$, although the dependence on $\varepsilon$ in these bounds is non-optimal.

Finally, for each kind of convergence, we conjecture tighter bounds that are not known to hold presently. A table containing a summary of the results in this paper is included in Figure 5.

This research was funded by the National Science Foundation under grants IIS-1016029 and IIS-1053407. We thank Nikhil Srivastava for informing us of the matrix used in Theorem 10. We also thank Aditya Bhaskara and Matus Telgarsky for many helpful discussions.

Appendix

For any $\varepsilon<1/3$, to get within $\varepsilon$ of the optimum loss on the dataset in Table 4, AdaBoost takes at least $2/(9\varepsilon)$ steps.

Proof Note that the optimal loss is $2/3$, and we are bounding the number of rounds necessary to get within $(2/3)+\varepsilon$ loss for $\varepsilon<1/3$. We will compute the edge in each round analytically. Let $w^{t}_{a},w^{t}_{b},w^{t}_{c}$ denote the normalized-losses (adding up to 1) or weights on examples $a,b,c$ at the beginning of round $t$, $h_{t}$ the weak hypothesis chosen in round $t$, and $\delta_{t}$ the edge in round $t$. The values of these parameters are shown below for the first 5 rounds, where we have assumed (without loss of generality) that the hypothesis picked in round 1 is $\hbar_{b}$:

Based on the patterns above, we first claim that for rounds $t\geq 2$, the edge achieved is $1/t$. In fact we prove the stronger claims, that for rounds $t\geq 2$, the following hold:

One of $w^{t}_{a}$ and $w^{t}_{b}$ is $1/2$.

$\delta_{t+1}=\delta_{t}/(1+\delta_{t})$.

Since $\delta_{2}=1/2$, the recurrence on $\delta_{t}$ would immediately imply $\delta_{t}=1/t$ for $t\geq 2$. We prove the stronger claims by induction on the round $t$. The base case for $t=2$ is shown above and may be verified. Suppose the inductive assumption holds for $t$. Assume without loss of generality that $1/2=w^{t}_{a}>w^{t}_{b}>w^{t}_{c}$; note this implies $w^{t}_{b}=1-(w^{t}_{a}+w^{t}_{c})=1/2-w^{t}_{c}$. Further, in this round, $\hbar_{a}$ gets picked, and has edge $\delta_{t}=w^{t}_{a}+w^{t}_{c}-w^{t}_{b}=2w^{t}_{c}$. Now for any dataset, the weights of the examples labeled correctly and incorrectly in a round of AdaBoost are rescaled during the weight update step in a way such that each add up to $1/2$ after the rescaling. Therefore, $w^{t+1}_{b}=1/2,w^{t+1}_{c}=w^{t}_{c}\left(\frac{1/2}{w^{t}_{a}+w^{t}_{c}}\right)=w^{t}_{c}/(1+2w^{t}_{c})$. Hence, $\hbar_{b}$ gets picked in round $t+1$ and, as before, we get edge $\delta_{t+1}=2w^{t+1}_{c}=2w^{t}_{c}/(1+2w^{t}_{c})=\delta_{t}/(1+\delta_{t})$. The proof of our claim follows by induction.

Next we find the loss after each iteration. Using $\delta_{1}=1/3$ and $\delta_{t}=1/t$ for $t\geq 2$, the loss after $T$ rounds can be written as

Notice almost all the terms cancel, except for the first term of the first product, and the last term of the second product. Therefore, the loss after $T$ rounds is

where the inequality holds for $T\geq 1$. Since the initial error is $1=(2/3)+1/3$, therefore, for any $\varepsilon<1/3$, the number of rounds needed to achieve loss $(2/3)+\varepsilon$ is at least $2/(9\varepsilon)$.

Suppose $u_{0},u_{1},\ldots,$ are non-negative numbers satisfying

for some non-negative constants $c_{0},c_{1}$. Then, for any $t$,

Proof By induction on $t$. The base case is an identity. Assume the statement holds at iteration $t$. Then,

Thus it suffices to show $1/u_{t+1}^{c_{1}}-1/u_{t}^{c_{1}}\geq c_{1}c_{0}$. Multiplying both sides by $u_{t}^{c_{1}}$ and adding 1, this is equivalent to showing $(u_{t}/u_{t+1})^{c_{1}}\geq 1+c_{1}c_{0}u_{t}^{c_{1}}$. We will in fact show the stronger inequality

Since $(1+a)^{b}\geq 1+ba$ for $a,b$ non-negative, (9) will imply $\left(u_{t}/u_{t+1}\right)^{c_{1}}\geq\left(1+c_{0}u_{t}^{c_{1}}\right)^{c_{1}}\geq 1+c_{1}c_{0}u_{t}^{c_{1}}$, which will complete our proof. To show (9), we first rearrange the condition on $u_{t},u_{t+1}$ to obtain