Randomized Gradient Boosting Machine
From MaRDI portal
Publication:4971024
DOI10.1137/18M1223277zbMATH Open1451.90122arXiv1810.10158OpenAlexW3091997330MaRDI QIDQ4971024FDOQ4971024
Authors: Haihao Lu, Rahul Mazumder 
Publication date: 8 October 2020
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1810.10158
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
convex optimizationensemble methodsgradient boostingcoordinate descentfirst order methodscomputational guarantees
Cites Work
- A decision-theoretic generalization of on-line learning and an application to boosting
- MLlib: machine learning in Apache Spark
- Scikit-learn: machine learning in Python
- Greedy function approximation: A gradient boosting machine.
- Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
- Title not available (Why is that?)
- Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
- A primal-dual convergence analysis of boosting
- Boosting with early stopping: convergence and consistency
- Stochastic gradient boosting.
- SLOPE-adaptive variable selection via convex optimization
- Title not available (Why is that?)
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Coordinate descent algorithms
- On the convergence of block coordinate descent type methods
- Logistic regression, AdaBoost and Bregman distances
- Error bounds and convergence analysis of feasible descent methods: A general approach
- On the convergence of the coordinate descent method for convex differentiable minimization
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- Some theory for generalized boosting algorithms
- A new condition number for linear programming
- A new perspective on boosting in linear regression via subgradient optimization and relatives
- The rate of convergence of AdaBoost
- Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version
- Towards a deeper geometric, analytic and algorithmic understanding of margins
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.
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)
