Optimal and Adaptive Algorithms for Online Boosting

1 Introduction

We study online boosting, the task of boosting the accuracy of any weak online learning algorithm. The theory of boosting in the batch setting has been studied extensively, leading to a huge practical success. See the book by [Schapire and Freund, 2012] for a thorough discussion.

In the batch setting, we typically have a fixed training set S drawn from the underlying distribution. A boosting algorithm assumes access to a weak learner that achieves error at most 12 -γ on any distribution over S, for some fixed small "edge" γ > 0. Each round of boosting typically makes a pass over S, reweighting the examples and running a copy of the weak learner on this specially reweighted dataset.

On the other hand, online learning algorithms receive examples one by one, updating the predictor after seeing each new example. An online booster has to operate in the same fashion, reweighting and passing each example through all copies of the online weak learner before seeing any subsequent examples. In contrast to the batch setting, online learning algorithms typically do not make any stochastic assumptions about the data. They are often much faster, more memory-efficient, and can adapt to the best predictor changing over time.

The success of boosting in batch learning prompted an investigation of whether online learning algorithms can be boosted as well [Oza and Russell, 2001; Grabner and Bischof, 2006; Liu and Yu, 2007; Grabner et al., 2008; Chen et al., 2012; 2014]. From a theoretical viewpoint, the work by [Chen et al., 2012] is perhaps most interesting. The authors proposed an online generalization of the batch weak learning

Haipeng Luo

haipengl@cs.princeton.edu Princeton University Princeton, NJ 08540

assumption, and made a connection between online boosting and batch boosting that produces smooth distributions over the training examples. The resulting algorithm is guaranteed to achieve an arbitrarily small error rate as long as the number of weak learners and the number of examples are sufficiently large. No assumptions need to be made about how the data is generated, e.g., the data can be generated by an adversary.

We present a new online boosting algorithm, based on the boost-by-majority (BBM) algorithm of [Freund, 1995]. This algorithm, called Online BBM, improves upon the work of [Chen et al., 2012] in several ways:

1. Our assumption on online weak learners is weaker and can be seen as a direct online analogue of the standard batch weak learning assumption.
2. Our algorithm does not require importance weighted online learning, instead using a sampling technique similar to the one used in boosting by filtering in the batch setting [Freund, 1992; Bradley and Schapire, 2008].
3. Our algorithm is optimal in the sense that no online boosting algorithm can achieve the same error rate with fewer weak learners or examples asymptotically.

The following table presents a comparison of the two papers for the setting where the weak learner is derived from an online learning algorithm with an O(pT) regret bound. Here N is the number of weak learners and T is the number of examples needed to achieve error rate ✏, and γ is an online analog of the "edge" of the weak learning oracle. 1

A clear drawback of both Online BBM and the algorithm in [Chen et al., 2012] is their lack of adaptivity. These algorithms require knowledge of γ as a parameter. More importantly, this also means that the algorithm treats each weak learner equally and ignores the fact that some weak learners are actually doing better than the others. The best example of adaptive boosting algorithm is the well-known parameterfree AdaBoost algorithm [Freund and Schapire, 1997], where each weak learner is naturally weighted by how accurate it is. In fact, adaptivity is known to be one of the key features that lead to the practical success of AdaBoost, and therefore should also be essential to the performance of online boosting algorithms. In Section 4, we propose AdaBoost.OL, an adaptive and parameter-free online boosting algorithm. As shown in the table, AdaBoost.OL is theoretically suboptimal in terms of N and T. However, empirically it generally outperforms OSBoost and sometimes even beats the optimal Online BBM (see Section 5).

1 In this paper, we use the ˜O(·) and ˜⌦(·) notation to suppress dependence on polylogarithmic factors in the natural parameters.

Our techniques are also very different from those of [Chen et al., 2012], which rely on the smooth boosting algorithm of [Servedio, 2003]. As far as we know, all other work on smooth boosting [Bshouty and Gavinsky, 2003; Bradley and Schapire, 2008; Barak et al., 2009] cannot be easily generalized to the online setting, necessitating completely different methods not relying on smooth distributions. Our Online BBM algorithm builds on top of a potential based family that arises naturally in the batch setting as approximate minimax optimal algorithms for so-called drifting games [Schapire, 2001; Luo and Schapire, 2014]. The decomposition of each example in that framework naturally allows us to generalize it to the online setting where example comes one by one. On the other hand, AdaBoost.OL is derived by viewing boosting from a different angle: loss minimization [Mason et al., 2000; Schapire and Freund, 2012]. The theory of online loss minimization is the key tool for developing AdaBoost.OL.

2 Setup and Assumptions

We describe the formal setup of the task of online classification by boosting. At each time step t = 1↪ ▷ ▷ ▷ ↪ T, an adversary chooses an example (xt↪ yt) 2 X ⇥¶-1↪ 1♦, where X is the domain, and reveals xt to the online learner. The learner makes a prediction on its label ˆ yt 2 ¶-1↪ 1♦, and suffers the 0-1 loss 1¶ˆ yt 6= yt♦. As is usual with online algorithms, this prediction may be randomized.

For parameters γ 2 (0↪ 12 ), δ 2 (0↪ 1), and a constant S > 0, the learner is said to be a weak online learner with edge γ and excess loss S if, for any T and for any input sequence of examples (xt↪ yt) for t = 1↪ 2↪ ▷ ▷ ▷ ↪ T chosen adaptively, it generates predictions ˆ yt such that with probability at least 1 - δ,

The excess loss requirement is necessary since an online learner cannot be expected to predict with any accuracy with too few examples. Essentially, the excess loss S yields a kind of sample complexity bound: the weak learner starts obtaining a distinct edge of ⌦(γ) over random guessing when T ≫ Sγ . Typically, the dependence of the high probability bound on δ is polylogarithmic in 1δ ; thus in the following we will avoid explicitly mentioning δ.

For a given parameter ✏ > 0, the learner is said to be a strong online learner with error rate ✏ if it satisfies the same conditions as a weak online learner except that its edge is 12 -✏, or in other words, the fraction of mistakes made, asymptotically, is ✏. Just as for the weak learner, the excess loss S yields a sample complexity bound: the fraction of mistakes made by the strong learner becomes O(✏) when T ≫ S✏ .

2.1 Discussion of Weak Online Learning Assumption

We now justify our definition of weak online learning, viz. inequality (1). In the standard batch boosting case, the corresponding weak learning assumption (see for example [Schapire and Freund, 2012]) made is that there is an algorithm which, given a training set of examples and an arbitrary distribution on it, generates a hypothesis that has error at most 12 - γ on the training data under the given distribution. This statement can be interpreted as making the following two implicit assumptions:

1. (Richness.) Given an edge parameter γ 2 (0↪ 12 ), there is a set of hypotheses, H, such that given any training set (possibly, a multiset) of examples U, there is some hypothesis h 2 H with error at most 12 - γ, i.e.

1. (Agnostic Learnability.) For any ✏ 2 (0↪ 1), there is an algorithm which, given any training set (possibly, a multiset) of examples U, can compute a nearly optimal hypothesis h 2 H, i.e.

Our weak online learning assumption can be seen as arising from a direct generalization of the above two assumptions to the online setting. Namely, the richness assumption stays the same, whereas the agnostic learnability of H assumption is replaced by an agnostic online learnability of H assumption (c.f. [Ben-David et al., 2009]). I.e., there is an online learning algorithm which, given any sequence of examples, (xt↪ yt) for t = 1↪ 2↪ ▷ ▷ ▷ ↪ T , generates predictions ˆ yt such that

where R : N ! R+ is the regret, a non-decreasing, sublinear function of the number of prediction periods T . Since online learning algorithms are typically randomized, we assume the above bound holds with high probability. The following lemma shows that richness and agnostic online learnability immediately imply our online weak learning assumption (1). 2

Lemma 1. Suppose the sequence of examples (xt↪ yt) is obtained from a data set for which there exists a hypothesis class H that is both rich for edge parameter 2γ and agnostically online learnable with regret R(·). Then, the agnostic online learning algorithm for H satisfies the weak learning assumption (1), with edge γ and excess loss S = maxT (R(T )-γT ).

2 All proofs can be found in [Beygelzimer et al., 2015].

Algorithm 1 Online BBM

• 1: for t = 1 to T do
• 2: Receive example xt.
• 5: for i = 1 to N do
• 3: Predict ˆ yt = sign(PNi=1 WLi (xt)), receive label yt. 4: Set s0t = 0.
• 6: Set sit = si-1 t + ytWLi (xt).
• 7: Set ki t = b N-i-si-1 t +1 2 c.
• 9: Pass training example (xt↪ yt) to WLi with probability pit = pN-i+1 4 wi t .
• 8: Set wi t = (N-i ki t ) ( 12 + γ2 )ki t ( 12 - γ2 )N-i-ki t .
• 10: end for
• 11: end for

Various agnostic online learning algorithms are known to have a regret bound of O(qT ln( 1δ )), e.g., Hedge [Freund and Schapire, 1995]. If we use such an online learning algorithm as a weak online learner, then a simple calculation implies, via Lemma 1, that it has excess loss ⇥( ln( 1δ ) γ ).

3 An Optimal Algorithm

The Online BBM algorithm (see Algorithm 1) is an optimal online boosting algorithm, as indicated in Theorem 1 below. The algorithm (hereafter referred to as "booster") works by maintaining N copies of the weak online learner, for some positive integer N to be specified later. Denote the weak online learners WLi for i = 1↪ 2↪ ▷ ▷ ▷ ↪N. At time step t, the prediction of i-th weak online learner is given by WLi (xt) 2 ¶-1↪ 1♦. Note the slight abuse of notation here: WLi is not a function, rather it is an algorithmwith an internal state that is updated as it is fed training examples. Thus, the prediction WLi (xt) depends on the internal state of WLi , and for notational convenience we avoid reference to the internal state.

In each round t, the booster works by taking a majority vote of the weak learners' predictions. That is, the prediction is sign(PNi=1 WLi (xt)), where sign(·) is 1 if the argument is nonnegative and -1 otherwise. After making the prediction, the true label yt is revealed by the environment. The booster then updates WLi by passing the training example (xt↪ yt) to WLi with a carefully chosen sampling probability pit (and not passing the example with the remaining probability). The sampling probability pit is obtained by computing a weight wi t and setting pit = pN-i+1 4 wi t .

We can prove the following performance guarantee for the Online BBM algorithm:

Theorem 1. Given a weak online learning algorithm with edge γ and excess loss S and any target error rate ✏ > 0, the Online BBM boosting algorithm constructs a strong online learning algorithm with error rate ✏ using O( 1 γ 2 ln( 1✏ )) copies of the weak online learner, and with excess loss ˜O( Sγ + 1 γ 2 ). Its sample complexity is thus ˜O( 1✏ ( Sγ + 1 γ 2 )). Further-

Algorithm 2 AdaBoost.OL

• 1: Initialize: 8i : vi1 = 1↪ ↵i1 = 0. 2: for t = 1 to T do 3: Receive example xt. 4: for i = 1 to N do 5: Set ˆ yi t = sign(Pij=1 ↵j t WLj (xt)). 6: end for 7: Randomly pick it with Pr[it = i] / vi t . 8: Predict ˆ yt = ˆ yit t , receive label yt. 9: Set s0t = 0. 10: for i = 1 to N do 11: Set zi t = ytWLi (xt). 12: Set sit = si-1 t +↵it zi t . 13: Set ↵it+1 = ⇧ ⇣↵it + ⌘tzi t 1+exp(sit ) ⌘ with ⌘t = 4◁pt. 14: Pass example (xt↪ yt) to WLi with probability pit = wi t = 1◁(1 + exp(si-1 t )). 15: Set vi t+1 = vi t · exp(-1¶yt 6= ˆ yi t ♦). 16: end for 17: end for

more, if S ≥ ˜⌦( 1 γ ), then the number of weak online learners is optimal up to constant factors, and the sample complexity is optimal up to polylogarithmic factors.

The requirement that S ≥ ˜⌦( 1 γ ) in the lower bound is not very stringent; this is precisely the excess loss one obtains when using standard online learning algorithms with regret bound O(pT), as is explained in the discussion following Lemma 1. Furthermore, since we require the bound (1) to hold with high probability, typical analyses of online learning algorithms will have an ˜O(pT) deviation term, which also leads to S ≥ ˜⌦( 1 γ ).

4 An Adaptive Algorithm

Although the Online BBM algorithm is optimal, it is unfortunately not adaptive since it requires the knowledge of γ as a parameter, which is unknown ahead of time. As discussed in the introduction, adaptivity is essential to the practical performance of boosting algorithms such as AdaBoost. We now design an adaptive online boosting algorithms using the theory of online loss minimization.

We conceptually define N different "experts" giving advice on what to predict on the current example xt. In round t, expert i predicts by combining the first i weak learners using a weighted majority rule with weights ↵j t forWLj , as follows:

Now as in the batch boosting algorithm AdaBoost.L [Schapire and Freund, 2012, Chapter 7], the weight wi t for WLi is obtained by computing the logistic loss of the prediction of expert i-1, i.e. `(si-1 t ), and then setting wi t to be the negative derivative of the loss:

In terms of the weight of WLi , i.e. ↵it , ideally we wish to mimic AdaBoost.L and use a fixed ↵i for all t such that the total logistic loss is minimized: ↵i = argmin↵ PTt=1 `(si-1 t + ↵zi t ). Of course this is not possible because ↵i depends on the future unknown examples. Nevertheless, it suffices to restrict the ↵it 's to the set [-2↪ 2] and tune them using online gradient descent [Zinkevich, 2003], which allows us perform almost as well as the best fixed choice (↵i ) in hindsight. This is implemented in step 13 of the algorithm:

where ⌘t is a time-varying learning rate and ⇧ represents projection onto the set [-2↪ 2], i.e., ⇧(·) = max¶-2↪ min¶2↪ ·♦♦.

Finally, it remains to specify the algorithm's final prediction ˆ yt. It turns out that at least one of the N experts will have high accuracy. Using the well-known Hedge algorithm [Littlestone and Warmuth, 1994; Freund and Schapire, 1997], we can (almost) achieve the performance of the best expert. This is implemented in steps 7 and 15 of the algorithm.

We call the final resulting algorithm AdaBoost.OL, 3 and

summarize it in Algorithm 2. Note that as promised, AdaBoost.OL is an adaptive online boosting algorithm and does not require knowing γ in advance. In fact, in the analysis we do not even have to assume that the weak learners satisfy the bound (1). Instead, define the quantities γi , wi ·zi 2kwi k1 for each weak learner WLi . This can be interpreted as the (weighted) edge over random guessing that WLi obtains. Note that γi may even be negative, which means flipping the sign of WLi 's predictions performs better than random guessing. Nevertheless, the algorithm can still make accurate predictions even with negative γi since it will end up choosing negative weights ↵it in that case. The performance of AdaBoost.OL is provided below.

Theorem 2. For any T and N, with high probability, the number of mistakes made by AdaBoost.OL is bounded by

3 O stands for online and L stands for logistic loss.

Moreover, if the weak learners satisfy (1), then the number of mistakes is bounded by

Thus, in order to achieve error rate ✏, it suffices to use N ≥ 8 ✏γ 2 weak learners, giving an excess loss ˜O( Sγ + 1 ✏γ 4 ).

5 Experiments

While the focus of this paper is a theoretical investigation of online boosting, we also performed an experimental evaluation. We extended the Vowpal Wabbit open source machine learning system 4 to include the algorithms studied in this paper. Since VW can handle importance weights, we implemented versions of our boosting algorithms (Online BBM.W and AdaBoost.OL.W) that use the probabilities pit as importance weights, as well as OSBoost (using uniform weighting on the weak learners) and OSBoost.OCP from [Chen et al., 2012]. To compare importance weighting versus sampling, we also implemented AdaBoost.OL from Algorithm 2, which samples examples sent to VWwith the pit probabilities.

All experiments were done on a diverse collection of 13 publicly available datasets. For each dataset, we performed a random split with 80% of the data used for single-pass training and the remaining 20% for testing. We tuned the learning rate, the number of weak learners, and the edge parameter γ (for all but the two versions of AdaBoost.OL) using progressive validation 0-1 loss on the training set. Progressive validation is a standard online validation technique, where each training example is used for testing before it is used for updating the model [Blum et al., 1999]. Reported in Table 1 is the 0-1 loss on the test set.

It should be noted that the VW baseline is already a strong learner. For most datasets, Online BBM.W had the best performance. The average improvement of Online BBM.W over the baseline was 5.14%. For AdaBoost.OL.W, it was 2.57%. Using sampling in AdaBoost.OL boosts the average to 2.67%. The average improvement for OSBoost.OCP was 1.98%, followed by OSBoost with 1.13%.

4 https://github.com/JohnLangford/vowpal wabbit/wiki