17 papers · ranked by Valyu relevance
Y. Coadou
Boosted decision trees are a very powerful machine learning technique. After introducing specific concepts of machine learning in the highenergy physics context and describing ways to quantify the performance and training quality of classifiers, decision trees are described. Some of their shortcomings are then…
Amira Abbas, Yanlin Chen, Tuyen Nguyen, Ronald de Wolf
The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple "weak learners"—hypotheses that are only slightly better than random guessing—into a single "strong…
Ping Li, Weijie Zhao
This report presents the open-source package https://github.com/pltrees/abcboost which implements the series of boosting works over the past many years (Li, 2008, 2009, 2010a,b; Li and Zhao, 2022a,c). In particular, this package includes mainly three lines of techniques, among which the following two techniques are…
Mikael Møller Høgsgaard, Kasper Green Larsen, Markus Engelund Mathiasen
'Markus Engelund Mathiasen'] Boosting is an extremely successful idea, allowing one to combine multiple low accuracy classifiers into a much more accurate voting classifier. In this work, we present a new and surprisingly simple Boosting algorithm that obtains a provably optimal sample complexity. Sample optimal…
Ryotaro Mitsuboshi, Kohei Hatano, Eiji Takimoto
Some boosting algorithms, such as LPBoost, ERLPBoost, and C-ERLPBoost, aim to solve the soft margin optimization problem with the `1-norm regularization. LPBoost rapidly converges to an -approximate solution in practice, but it is known to take Ω(m) iterations in the worst case, where m is the sample size. On the other…
Arthur da Cunha, Mikael Møller Høgsgaard, Kasper Green Larsen
Recent works on the parallel complexity of Boosting have established strong lower bounds on the tradeoff between the number of training rounds p and the total parallel work per round t. These works have also presented highly non-trivial parallel algorithms that shed light on different regions of this tradeoff. Despite…
Suneel Babu Chatla
We investigate L2 boosting in the context of kernel regression. Kernel smoothers, in general, lack appealing traits like symmetry and positive definiteness, which are critical not only for understanding theoretical aspects but also for achieving good practical performance. We consider a projection-based smoother (Huang…
Xin Lyu, Hongxun Wu, Junzhao Yang
- First, we prove a tight lower bound, showing that even "slight" parallelization of boosting requires an exponential blow-up in the complexity of training. Specifically, let γ be the weak learner's advantage over random guessing. The famous AdaBoost algorithm produces an accurate hypothesis by interacting with the…
Fang, Haimo, Kevin Tan, Giles Hooker
Gradient boosting is widely popular due to its flexibility and predictive accuracy. However, statistical inference and uncertainty quantification for gradient boosting remain challenging and under-explored. We propose a unified framework for statistical inference in gradient boosting regression. Our framework…
Richard Nock, Ehsan Amid, Manfred K. Warmuth
One of the most popular ML algorithms, ADABOOST, can be derived from the dual of a relative entropy minimization problem subject to the fact that the positive weights on the examples sum to one. Essentially, harder examples receive higher probabilities. We generalize this setup to the recently introduced tempered…
Richard Nock, Yishay Mansour
Boosting is a highly successful ML-born optimization setting in which one is required to computationally efficiently learn arbitrarily good models based on the access to a weak learner oracle, providing classifiers performing at least slightly differently from random guessing. A key difference with gradient-based…
Paul Liautaud, Pierre Gaillard, Olivier Wintenberger
We study boosting for adversarial online nonparametric regression with general convex losses. We first introduce a parameter-free online gradient boosting (OGB) algorithm and show that its application to chaining trees achieves minimax optimal regret when competing against Lipschitz functions. While competing with…
Jian Qian, Shu Ge
We formalize this stability property as (α, β)-boostability. We show that geometric median aggregation achieves (α, β)-boostability for a broad class of divergences, with tradeoffs that depend on the underlying geometry. For vector-valued prediction and conditional density estimation, we characterize boostability under…
Chapman Siu
We study the online variant of GentleAdaboost, where we combine a weak learner to a strong learner in an online fashion. We provide an approach to extend the batch approach to an online approach with theoretical justifications through application of line search. Finally we compare our online boosting approach with…
Perceval Beja-Battais
| 1 | Introduction, problematic & notations | | 3 | | --- | --- | --- | --- | | | 1.1 | Introduction | 3 | | | 1.2 | Problematic | 4 | | | 1.3 | Notations | 4 | | 2 | | Views of AdaBoost | 5 | | | 2.1 | The original view: a PAC learning algorithm | 5 | | | | 2.1.1 What is a PAC learning algorithm? | 5 | | | | 2.1.2…
Amin Karbasi, Kasper Green Larsen
The aim of boosting is to convert a sequence of weak learners into a strong learner. At their heart, these methods are fully sequential. In this paper, we investigate the possibility of parallelizing boosting. Our main contribution is a strong negative result, implying that significant parallelization of boosting…
Dimitris Bertsimas, Vasiliki Stoumpou
Random Forests have been one of the most popular bagging methods in the past few decades, especially due to their success at handling tabular datasets. They have been extensively studied and compared to boosting models, like XGBoost, which are generally considered more performant. Random Forests adopt several…