SketchBoost: Fast Gradient Boosted Decision Tree for Multioutput Problems

• URL: http://arxiv.org/abs/2211.12858v1
• Date: Wed, 23 Nov 2022 11:06:10 GMT
• Title: SketchBoost: Fast Gradient Boosted Decision Tree for Multioutput Problems
• Authors: Leonid Iosipoi and Anton Vakhrushev
• Abstract summary: Gradient Boosted Decision Tree (GBDT) is a widely-used machine learning algorithm. We propose novel methods aiming to accelerate the training process of GBDT in the multioutput scenario. Our numerical study demonstrates that SketchBoost speeds up the training process of GBDT by up to over 40 times.
• Score: 3.04585143845864
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Gradient Boosted Decision Tree (GBDT) is a widely-used machine learning algorithm that has been shown to achieve state-of-the-art results on many standard data science problems. We are interested in its application to multioutput problems when the output is highly multidimensional. Although there are highly effective GBDT implementations, their scalability to such problems is still unsatisfactory. In this paper, we propose novel methods aiming to accelerate the training process of GBDT in the multioutput scenario. The idea behind these methods lies in the approximate computation of a scoring function used to find the best split of decision trees. These methods are implemented in SketchBoost, which itself is integrated into our easily customizable Python-based GPU implementation of GBDT called Py-Boost. Our numerical study demonstrates that SketchBoost speeds up the training process of GBDT by up to over 40 times while achieving comparable or even better performance.

Related papers

• Generating and Imputing Tabular Data via Diffusion and Flow-based Gradient-Boosted Trees [11.732842929815401]
  Tabular data is hard to acquire and is subject to missing values. This paper introduces a novel approach for generating and imputing mixed-type (continuous and categorical) data. In contrast to prior methods that rely on neural networks to learn the score function or the vector field, we adopt XGBoost.
  arXiv  Detail & Related papers  (2023-09-18T17:49:09Z)
• GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent [10.27211960475599]
  Decision Trees (DTs) are commonly used for many machine learning tasks. In this paper, we propose a novel approach to learn DTs using a greedy algorithm. We propose backpropagation with a straight-through operator on a dense DT representation, to jointly optimize all tree parameters.
  arXiv  Detail & Related papers  (2023-05-05T13:24:35Z)
• Accelerating Barnes-Hut t-SNE Algorithm by Efficient Parallelization on Multi-Core CPUs [59.18990342943095]
  t-SNE remains one of the most popular embedding techniques for visualizing high-dimensional data. BH t-SNE algorithm is inefficient on existing CPU implementations. Acc-t-SNE is up to 261x and 4x faster than scikit-learn and the state-of-the-art BH t-SNE implementation from daal4py.
  arXiv  Detail & Related papers  (2022-12-22T06:38:40Z)
• PromptBoosting: Black-Box Text Classification with Ten Forward Passes [61.38341243907045]
  We describe PromptBoosting, a query-efficient procedure for building a text classifier from a neural language model (LM) without access to the LM's parameters, gradients, or hidden representations. Experiments show that PromptBoosting achieves state-of-the-art performance in multiple black-box few-shot classification tasks, and matches or outperforms full fine-tuning in both few-shot and standard learning paradigms, while training 10x faster than existing black-box methods.
  arXiv  Detail & Related papers  (2022-12-19T06:04:54Z)
• High-Order Optimization of Gradient Boosted Decision Trees [1.4047579643483785]
  We introduce high-order optimization for GBDTs based on numerical optimization theory. We show that high-order optimization has faster per-iteration convergence that leads to reduced running time.
  arXiv  Detail & Related papers  (2022-11-21T11:33:16Z)
• Quantized Training of Gradient Boosting Decision Trees [84.97123593657584]
  We propose to quantize all the high-precision gradients in a very simple yet effective way in the GBDT's training algorithm. With low-precision gradients, most arithmetic operations in GBDT training can be replaced by integer operations of 8, 16, or 32 bits. We observe up to 2$times$ speedup of our simple quantization strategy compared with SOTA GBDT systems on extensive datasets.
  arXiv  Detail & Related papers  (2022-07-20T06:27:06Z)
• Accelerated Stochastic Gradient for Nonnegative Tensor Completion and Parallel Implementation [0.3670422696827525]
  We adopt the alternating optimization framework and solve each nonnegative matrix completion problem via a variation of the gradient accelerated algorithm. We develop a shared-memory implementation of our algorithm using the multi-threaded API OpenMP, which attains significant speedup.
  arXiv  Detail & Related papers  (2021-09-20T13:32:12Z)
• Sparse Communication for Training Deep Networks [56.441077560085475]
  Synchronous gradient descent (SGD) is the most common method used for distributed training of deep learning models. In this algorithm, each worker shares its local gradients with others and updates the parameters using the average gradients of all workers. We study several compression schemes and identify how three key parameters affect the performance.
  arXiv  Detail & Related papers  (2020-09-19T17:28:11Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)
• 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)

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.