← Back to papers
2015 ICML ICML 2015

Optimal and Adaptive Algorithms for Online Boosting

Abstract

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. The second algorithm is adaptive and parameter-free, albeit not optimal.

🧭 Keyword Pioneer — strong learner
🐣 Hot Topic Early Bird — sample complexity
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Data Science & Analytics, Deep Learning, Machine Learning, Mathematics & Optimization, Reinforcement Learning, Robotics

Authors

Alina Beygelzimer , Satyen Kale , Haipeng Luo

Topics

Machine Learning > Learning Types > Weakly Supervised Learning Machine Learning > Learning Types > Online Learning Machine Learning > Optimization & Theory > Online Algorithms Machine Learning > Learning Types > Ensemble Methods

Keywords

sample complexity weak learner online boosting strong learner
Download PDF

Related papers

PeakSeg: constrained optimal segmentation and supervised penalty learning for peak detection in count data 2015
The Benefits of Learning with Strongly Convex Approximate Inference 2015
Tracking Approximate Solutions of Parameterized Optimization Problems over Multi-Dimensional (Hyper-)Parameter Domains 2015
Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds 2015
Unsupervised Riemannian Metric Learning for Histograms Using Aitchison Transformations 2015