Randomized Gradient Boosting Machine
From MaRDI portal
Publication:4971024
Abstract: Gradient Boosting Machine (GBM) introduced by Friedman is a powerful supervised learning algorithm that is very widely used in practice---it routinely features as a leading algorithm in machine learning competitions such as Kaggle and the KDDCup. In spite of the usefulness of GBM in practice, our current theoretical understanding of this method is rather limited. In this work, we propose Randomized Gradient Boosting Machine (RGBM) which leads to substantial computational gains compared to GBM, by using a randomization scheme to reduce search in the space of weak-learners. We derive novel computational guarantees for RGBM. We also provide a principled guideline towards better step-size selection in RGBM that does not require a line search. Our proposed framework is inspired by a special variant of coordinate descent that combines the benefits of randomized coordinate descent and greedy coordinate descent; and may be of independent interest as an optimization algorithm. As a special case, our results for RGBM lead to superior computational guarantees for GBM. Our computational guarantees depend upon a curious geometric quantity that we call Minimal Cosine Angle, which relates to the density of weak-learners in the prediction space. On a series of numerical experiments on real datasets, we demonstrate the effectiveness of RGBM over GBM in terms of obtaining a model with good training and/or testing data fidelity with a fraction of the computational cost.
Recommendations
- Random gradient boosting for predicting conditional quantiles
- Stochastic gradient boosting.
- Stochastic boosting algorithms
- Stochastic boosting algorithms
- Accelerated gradient boosting
- Randomized machine learning procedures
- Optimization by Gradient Boosting
- Ensemble of fast learning stochastic gradient boosting
Cites work
- scientific article; zbMATH DE number 3860199 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- A decision-theoretic generalization of on-line learning and an application to boosting
- A new condition number for linear programming
- A new perspective on boosting in linear regression via subgradient optimization and relatives
- A primal-dual convergence analysis of boosting
- Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
- Boosting with early stopping: convergence and consistency
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- Coordinate descent algorithms
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
- Greedy function approximation: A gradient boosting machine.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Logistic regression, AdaBoost and Bregman distances
- MLlib: machine learning in Apache Spark
- On the convergence of block coordinate descent type methods
- On the convergence of the coordinate descent method for convex differentiable minimization
- SLOPE-adaptive variable selection via convex optimization
- Scikit-learn: machine learning in Python
- Some theory for generalized boosting algorithms
- Stochastic gradient boosting.
- The rate of convergence of AdaBoost
- Towards a deeper geometric, analytic and algorithmic understanding of margins
- Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version
Cited in
(9)- A new accelerated proximal boosting machine with convergence rate \(O(1/t^2)\)
- Subgradient regularized multivariate convex regression at scale
- Random gradient boosting for predicting conditional quantiles
- Accelerated gradient boosting
- Greedy function approximation: A gradient boosting machine.
- Temporal mixture ensemble models for probabilistic forecasting of intraday cryptocurrency volume
- Randomized machine learning procedures
- Driving detection based on the multifeature fusion
- Stochastic gradient boosting.
Describes a project that uses
Uses Software
This page was built for publication: Randomized Gradient Boosting Machine
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4971024)
