SnapBoost: A Heterogeneous Boosting Machine
- URL: http://arxiv.org/abs/2006.09745v2
- Date: Fri, 25 Sep 2020 07:58:04 GMT
- Title: SnapBoost: A Heterogeneous Boosting Machine
- Authors: Thomas Parnell, Andreea Anghel, Malgorzata Lazuka, Nikolas Ioannou,
Sebastian Kurella, Peshal Agarwal, Nikolaos Papandreou, Haralampos Pozidis
- Abstract summary: We study a Heterogeneous Newton Boosting Machine (HNBM) in which the base hypothesis class may vary across boosting iterations.
We describe how SnapBoost is implemented, with a focus on the training complexity.
We present experimental results, using OpenML and Kaggle datasets, that show that SnapBoost is able to achieve better generalization loss than competing boosting frameworks.
- Score: 9.532706363790053
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modern gradient boosting software frameworks, such as XGBoost and LightGBM,
implement Newton descent in a functional space. At each boosting iteration,
their goal is to find the base hypothesis, selected from some base hypothesis
class, that is closest to the Newton descent direction in a Euclidean sense.
Typically, the base hypothesis class is fixed to be all binary decision trees
up to a given depth. In this work, we study a Heterogeneous Newton Boosting
Machine (HNBM) in which the base hypothesis class may vary across boosting
iterations. Specifically, at each boosting iteration, the base hypothesis class
is chosen, from a fixed set of subclasses, by sampling from a probability
distribution. We derive a global linear convergence rate for the HNBM under
certain assumptions, and show that it agrees with existing rates for Newton's
method when the Newton direction can be perfectly fitted by the base hypothesis
at each boosting iteration. We then describe a particular realization of a
HNBM, SnapBoost, that, at each boosting iteration, randomly selects between
either a decision tree of variable depth or a linear regressor with random
Fourier features. We describe how SnapBoost is implemented, with a focus on the
training complexity. Finally, we present experimental results, using OpenML and
Kaggle datasets, that show that SnapBoost is able to achieve better
generalization loss than competing boosting frameworks, without taking
significantly longer to tune.
Related papers
- How to Boost Any Loss Function [63.573324901948716]
We show that loss functions can be efficiently optimized with boosting.
We show that boosting can achieve a feat not yet known to be possible in the classical $0th$ order setting.
arXiv Detail & Related papers (2024-07-02T14:08:23Z) - TRBoost: A Generic Gradient Boosting Machine based on Trust-region
Method [0.0]
This study proposes a new generic Gradient Boosting Machine called Trust-region Boosting (TRBoost)
In each iteration, TRBoost uses a constrained quadratic model to approximate the objective and applies the Trust-region algorithm to solve it and obtain a new learner.
convergence analysis and numerical experiments conducted in this study confirm that TRBoost is as general as first-order GBMs and yields competitive results.
arXiv Detail & Related papers (2022-09-28T02:42:15Z) - ProBoost: a Boosting Method for Probabilistic Classifiers [55.970609838687864]
ProBoost is a new boosting algorithm for probabilistic classifiers.
It uses the uncertainty of each training sample to determine the most challenging/uncertain ones.
It produces a sequence that progressively focuses on the samples found to have the highest uncertainty.
arXiv Detail & Related papers (2022-09-04T12:49:20Z) - Lassoed Tree Boosting [53.56229983630983]
We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation.
Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
arXiv Detail & Related papers (2022-05-22T00:34:41Z) - Quantum Boosting using Domain-Partitioning Hypotheses [0.9264464791978363]
Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework.
We show that Q-RealBoost provides a speedup over Q-AdaBoost in terms of both the bias of the weak learner and the time taken by the weak learner to learn the target concept class.
arXiv Detail & Related papers (2021-10-25T10:46:13Z) - To Boost or not to Boost: On the Limits of Boosted Neural Networks [67.67776094785363]
Boosting is a method for learning an ensemble of classifiers.
While boosting has been shown to be very effective for decision trees, its impact on neural networks has not been extensively studied.
We find that a single neural network usually generalizes better than a boosted ensemble of smaller neural networks with the same total number of parameters.
arXiv Detail & Related papers (2021-07-28T19:10:03Z) - Improved Quantum Boosting [1.0660480034605238]
Arunachalam and Maity gave the first quantum improvement for boosting, by combining Freund and Schapire's AdaBoost algorithm with a quantum algorithm for approximate counting.
In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio's SmoothBoost algorithm.
arXiv Detail & Related papers (2020-09-17T15:16:42Z) - Soft Gradient Boosting Machine [72.54062017726154]
We propose the soft Gradient Boosting Machine (sGBM) by wiring multiple differentiable base learners together.
Experimental results showed that, sGBM enjoys much higher time efficiency with better accuracy, given the same base learner in both on-line and off-line settings.
arXiv Detail & Related papers (2020-06-07T06:43:23Z) - A Generic First-Order Algorithmic Framework for Bi-Level Programming
Beyond Lower-Level Singleton [49.23948907229656]
Bi-level Descent Aggregation is a flexible and modularized algorithmic framework for generic bi-level optimization.
We derive a new methodology to prove the convergence of BDA without the LLS condition.
Our investigations also demonstrate that BDA is indeed compatible to a verify of particular first-order computation modules.
arXiv Detail & Related papers (2020-06-07T05:18:50Z) - Fully-Corrective Gradient Boosting with Squared Hinge: Fast Learning
Rates and Early Stopping [29.485528641599018]
We propose an efficient boosting method with theoretical generalization guarantees for binary classification.
We derive a fast learning rate of the order $cal O((m/log m)-1/4)$ for the proposed boosting method.
Both derived learning rates are the best ones among the existing generalization results of boosting-type methods for classification.
arXiv Detail & Related papers (2020-04-01T00:39:24Z) - BoostTree and BoostForest for Ensemble Learning [27.911350375268576]
BoostForest is an ensemble learning approach using BoostTree as base learners and can be used for both classification and regression.
It generally outperformed four classical ensemble learning approaches (Random Forest, Extra-Trees, XGBoost and LightGBM) on 35 classification and regression datasets.
arXiv Detail & Related papers (2020-03-21T19:52:13Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.