Source-linked AI summary
Optimal and Adaptive Algorithms for Online Boosting
Alina Beygelzimer, Satyen Kale, Haipeng Luo
TL;DR
Online boosting asks how to convert weak online learners into strong ones without relying on smooth data distributions. The paper introduces Online BBM and AdaBoost.OL under a new weak-learnability definition. Online BBM is essentially optimal in weak-learner count and sample complexity, whereas AdaBoost.OL provides adaptivity and parameter-free operation but is theoretically suboptimal.
Problem
Online boosting seeks to convert any weak online learner into a strong online learner, extending the practical success of batch boosting to sequential data.
Method
The paper develops Online BBM from potential-based boosting and AdaBoost.OL from online loss minimization, supporting both importance weighting and rejection sampling.
Results
Online BBM is optimal in the number of weak learners and sample complexity, while AdaBoost.OL is adaptive and parameter-free but theoretically suboptimal.
Takeaways & Limitations
The two algorithms provide complementary choices: optimality with Online BBM or adaptivity with AdaBoost.OL, whose empirical performance can surpass the optimal algorithm.
Takeaways & Limitations
No algorithm in the paper is both adaptive and optimal; obtaining one remains an open question.
Abstract
from arXiv · showhide
We study online boosting, the task of converting any weak online learner into a strong online learner. Based on a novel and natural definition of weak online learnability, we develop two online boosting algorithms. The first algorithm is an online version of boost-by-majority. By proving a matching lower bound, we show that this algorithm is essentially optimal in terms of the number of weak learners and the sample complexity needed to achieve a specified accuracy. This optimal algorithm is not adaptive however. Using tools from online loss minimization, we derive an adaptive online boosting algorithm that is also parameter-free, but not optimal. Both algorithms work with base learners that can handle example importance weights directly, as well as by rejection sampling examples with probability defined by the booster. Results are complemented with an extensive experimental study.
1 Introduction
The paper develops online boosting methods that convert weak online learners into strong learners without smooth-distribution assumptions. Online BBM is optimal in learner count and sample complexity, while AdaBoost.OL is adaptive and parameter-free but theoretically suboptimal.
- 1 Introduction: Online boosting is motivated by the batch success of boosting, but online methods receive examples sequentially and generally avoid stochastic data assumptions.Prior online boosting work includes methods that tolerate even adversarially generated data.
- 1 Introduction: Online BBM uses a weaker online-learning assumption than prior work and avoids requiring weighted online learning through sampling.Its assumption directly analogizes the standard batch weak-learning assumption, and the booster can reject examples instead of requiring importance-weight handling.
- 1 Introduction: Online BBM is asymptotically optimal: no online booster achieves the same error rate with fewer weak learners or examples.The comparison tracks N weak learners and T examples needed to reach error rate ǫ, with γ measuring weak-learner inaccuracy.
- 1 Introduction: AdaBoost.OL is adaptive and parameter-free but theoretically suboptimal in N and T, while often outperforming OSBoost and sometimes Online BBM empirically.Adaptivity addresses unknown γ and allows unequal treatment of weak learners according to their performance.
- 1 Introduction: The paper derives Online BBM from potential-based drifting-game methods and AdaBoost.OL from online loss minimization.These are distinct methodological routes to online boosting rather than direct generalizations of smooth-distribution batch techniques.
- 1 Introduction: Experiments on benchmark data are used to show that the new algorithms improve over previous work.
2 Setup and Assumptions
The setup defines weak and strong online learners against adaptively chosen example sequences, then builds a booster from multiple weak learners. Under the proposed weak-learning assumption, the resulting booster achieves near-optimal sample complexity.
- 2 Setup and Assumptions: At each round, an adversary reveals x_t, the learner predicts a label, incurs 0-1 loss, and then updates immediately after y_t is revealed.Predictions may be randomized, and the sequence can be chosen adaptively.
- 2 Setup and Assumptions: A weak online learner has edge γ and excess loss S when its predictions satisfy the high-probability weak-learning bound on any adaptively chosen sequence.The excess-loss term provides a sample-complexity scale because the learner needs sufficiently many examples before its edge becomes distinct from random guessing.
- 2 Setup and Assumptions: For target error ǫ, Theorem 1 constructs a strong online learner from a weak learner with edge γ and excess loss S.The theorem’s bound uses the booster’s number of weak learners and its resulting excess loss to establish the target error guarantee.
- 2 Setup and Assumptions: The booster maintains N weak learners, combines their predictions by weighted majority, and updates each learner using carefully chosen sampling probabilities.The weak learners have internal state, so their predictions depend on the examples previously passed to them.
- 2.1 Handling Importance Weights: Importance-weighted base learners can receive every example with a weight, while sampling-based learners receive examples probabilistically; experiments found importance weighting performed better.The analysis can substitute the importance-weighted inequality for the sampling-based bound and obtain a slightly tighter theorem.
- 2.2 Discussion of Weak Online Learning Assumption: Theorem 1 therefore yields an online boosting algorithm with near-optimal sample complexity.The conclusion follows when the weak learner is derived from an agnostically online learnable, sufficiently rich hypothesis class.
3 An Optimal Algorithm
The paper develops a potential-based online boost-by-majority algorithm with optimal weak-learner complexity and near-optimal sample complexity, then establishes matching lower bounds up to logarithmic factors.
- 3.1 A Potential Based Family and Boost-By-Majority: Online BBM generalizes potential-based batch boosting and achieves an optimal number of weak learners with near-optimal sample complexity.The construction uses non-increasing potential functions and extends the drifting-games framework to examples arriving sequentially.
- 3.1 A Potential Based Family and Boost-By-Majority: The potential choice matters because the term ˜S∥wi∥∞ penalizes the final error, while exponential potentials can make wi exponentially large.BBM potentials instead produce small weights and therefore avoid this drawback.
- 3.1 A Potential Based Family and Boost-By-Majority: The algorithm passes each training example to weak learner WLi with probability pi, enabling online boosting through rejection sampling.This avoids requiring weighted online learning.
- 3.1 A Potential Based Family and Boost-By-Majority: Theorem 2 and Lemma 3 provide high-probability mistake bounds for the online boosting scheme and its general potential-based form.The analysis repeatedly relates successive learners’ potential sums and applies concentration inequalities.
4 An Adaptive Algorithm
The section introduces AdaBoost.OL, an adaptive online boosting algorithm that uses online loss minimization to avoid knowing the weak learners’ edge in advance. It is parameter-free and can exploit differing learner performance, but its learner and sample requirements are suboptimal.
- Online loss minimization: The method treats boosting as online loss minimization and uses low-regret updates to approach the best fixed learner weight in hindsight.The construction restricts weights to [−2, 2] and applies online gradient descent with projection onto that interval.
- Adaptive online boosting: AdaBoost.OL selects among experts formed from successive weak learners using importance weights based on their previous performance.Each expert combines the first i weak learners, and the final predictor samples experts according to their importance weights.
- Adaptive online boosting: AdaBoost.OL is adaptive and does not require knowing γ in advance, unlike Online BBM.The algorithm defines learner-specific quantities γ_i and can assign negative weights when flipping a learner’s predictions is beneficial.
- Guarantees: Under the weak-learner condition, AdaBoost.OL provides a high-probability mistake bound and a sufficient learner count for achieving error rate ϵ.The supplied theorem passages state the bound and the resulting condition on N, while the displayed expressions are incomplete in the excerpt.
- Limitations: AdaBoost.OL is appealing because it is adaptive, but its number of weak learners and excess loss are suboptimal, leaving adaptive optimal boosting open.The paper explicitly leaves obtaining an algorithm that is both adaptive and optimal as an open question.
5 Experiments
The experiments evaluate several online boosting algorithms on 13 public datasets using VW as the weak learner. Online BBM performs best on most datasets and achieves the largest reported average improvement over the strong VW baseline.
- Experimental setup: The study evaluated Online BBM, AdaBoost.OL, OSBoost, OSBoost.OCP, and AdaBoost.OL.S using VW implementations across 13 public datasets.The datasets came from UCI, KDD Cup challenges, and the HCRC Map Task Corpus.
- Experimental setup: Reported performance is 0-1 loss on held-out test data after an 80% training and 20% testing split with progressive-validation tuning.Learning rate, learner count, and γ were tuned for all methods except AdaBoost.OL.
- Results: Online BBM had the best performance on most datasets, improving average loss over the VW baseline by 5.14%.The baseline is described as already strong, and Table 3 reports per-dataset 0-1 test loss.
- Results: AdaBoost.OL improved over the VW baseline by 2.57% on average, while sampling-based AdaBoost.OL.S improved by 2.67%.The experiments compare both importance weighting and sampling implementations.
A Proof of Lemma 1
The proof establishes concentration properties for the examples sampled by a weak learner, conditioning first on learner randomness and then removing that conditioning. A union bound combines the resulting inequalities.
- Randomness handling: The high-probability inequalities remain valid unconditionally after averaging over each weak learner’s internal randomness.The proof explicitly conditions on learner randomness before taking its expectation.
- Concentration argument: Martingale concentration bounds control the sampled-example process for each weak learner with high probability.The proof fixes learner randomness, defines the relevant conditional expectation, and applies concentration to a martingale difference sequence.
- Conclusion: A union bound makes inequalities (16), (17), and (18) hold simultaneously with high probability.The simultaneous event is then used to derive the desired bound.
B Proof of Lemma 4
The proof of Lemma 4 analyzes a binomial weak-learner quantity through a Gaussian approximation. Berry–Esseen bounds the approximation error, using the variance lower bound implied by γ.
- Binomial formulation: The proof models the relevant quantity as X ∼ B(m,p), with m = N − i and p = 1/2 + γ/2.It also defines q = 1 − p and uses the CDF of X.
- Gaussian approximation: The binomial variable is approximated by G ∼ N(mp, mpq), and Berry–Esseen controls the difference between their CDFs.The argument converts CDF approximation into a bound on point probabilities.
- Variance control: The approximation uses pq = 1/4 − γ^2/4 ≥ 3/16 to obtain a uniform variance lower bound.This lower bound supports the stated Gaussian approximation error control.