Source-linked AI summary
Accelerated Gradient Boosting
Gérard Biau, Benoît Cadre, Laurent Rouvìère
TL;DR
Gradient tree boosting builds predictors through an infinite-dimensional optimization problem, while accurate prediction from massive, high-dimensional data motivates accelerated methods. The paper introduces AGB, which incorporates Nesterov’s acceleration into Friedman’s tree-boosting procedure. The reported comparison finds similar prediction with at least an order-of-magnitude smaller optimal iteration count for AGB.
Problem
Gradient tree boosting builds predictors through an infinite-dimensional optimization problem, and accurate prediction from massive, high-dimensional data motivates accelerated methods.
Source: §1 · p. 2, §2.1 · p. 5Method
AGB incorporates Nesterov’s acceleration mechanism into Friedman’s original tree-boosting procedure.
Source: §1 · p. 2Results
With similar prediction, AGB’s optimal iteration count is at least one order of magnitude smaller than standard gradient boosting’s.
Source: §1 · p. 3Takeaways & Limitations
The authors report that AGB retains predictive performance comparable to standard gradient tree boosting while producing remarkably sparse models.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
Gradient tree boosting is a prediction algorithm that sequentially produces a model in the form of linear combinations of decision trees, by solving an infinite-dimensional optimization problem. We combine gradient boosting and Nesterov's accelerated descent to design a new algorithm, which we call AGB (for Accelerated Gradient Boosting). Substantial numerical evidence is provided on both synthetic and real-life data sets to assess the excellent performance of the method in a large variety of prediction problems. It is empirically shown that AGB is much less sensitive to the shrinkage parameter and outputs predictors that are considerably more sparse in the number of trees, while retaining the exceptional performance of gradient boosting.
1 Introduction
Gradient boosting builds prediction committees from simple learners, while demand for accurate prediction on massive, high-dimensional data motivates accelerated methods. AGB incorporates Nesterov’s mechanism into Friedman’s tree-boosting procedure, with comparable predictive performance and substantially fewer optimal iterations reported.
1 Introduction
- Gradient boosting combines simple predictors into a committee whose performance improves over that of its individual members.The introduction notes that decision trees are typically used as the base learners.Source: §1 · p. 1
- Nesterov’s accelerated descent reaches the smooth convex minimum at rate 1/t^2, versus O(1/t) for vanilla gradient descent at the same computational complexity.The introduction connects accelerated first-order methods with the demand for accurate prediction from massive, high-dimensional data.Source: §1 · p. 2
- AGB combines Nesterov’s acceleration with Friedman’s tree-boosting procedure and is reported to have predictive performance comparable to standard gradient tree boosting.The paper describes numerical experiments on synthetic and real-life data sets.Source: §1 · pp. 2–3
- With similar prediction, AGB’s optimal iteration count is at least one order of magnitude smaller than standard gradient boosting’s.The introduction illustrates this comparison using test error by iteration and shrinkage for both methods.Source: §1 · p. 3, Figure 1 · p. 3
- The paper compares AGB with Friedman’s gradient tree boosting and emphasizes how learning rate relates to the size of optimal models.The simulations and figures’ code is reported as publicly available.Source: §1 · pp. 3–4
2 (Accelerated) gradient boosting
Gradient boosting minimizes empirical risk by sequentially adding trees to an additive predictor. AGB combines this tree-fitting procedure with Nesterov-style acceleration, using companion sequences to update the model.
2.1 Gradient boosting at a glance
- Each base learner is a binary decision tree using axis-parallel cuts, with a small fixed number of terminal leaves.A tree is represented by leaf-specific values over a tree-structured partition of the input space.Source: §2.1 · p. 4
- Gradient boosting builds an additive predictor by sequentially adding trees to address empirical-risk minimization over linear combinations of base learners.The optimization is infinite-dimensional, and each iteration adds one component.Source: §2.1 · pp. 4–5
- At each iteration, gradient boosting seeks a tree aligned with the negative empirical-risk gradient, fitting it by least squares when the exact direction is unavailable in the base class.For squared loss, the negative gradient equals the current residuals, which the tree fits.Source: §2.1 · p. 5
2.2 The AGB algorithm
- AGB adds a companion sequence to gradient boosting, sliding the model iterates according to recursive parameters while outputting the final predictor from the other sequence.The two sequences correspond to Nesterov’s accelerated scheme.Source: §2.2 · pp. 6–7
- AGB fits a regression tree to the current descent direction, then updates the model using a separate optimal weight for each tree region.The algorithm initializes with an optimal constant model and scales the approximate-gradient contribution by the shrinkage parameter ν.Source: §2.2 · pp. 6–7
- The shrinkage parameter ν and iteration count T jointly control training risk; smaller ν usually requires more trees for the same training risk.Larger ν can reduce tree count, but values that are too large may disrupt the gradient-descent dynamic.Source: §2.2 · p. 7
3 Numerical studies
The numerical studies compare AGB with standard gradient tree boosting on simulated and real-life data, and also compare both boosting methods with the Lasso and random forests.
3.1 Description of the data sets
- The simulated tasks span uncorrelated and correlated designs, regression and classification, additive and interaction models, and a sparse high-dimensional problem; five UCI data sets add real-life cases.Source: §3.1 · pp. 7–8
- Regression used least-squares loss and classification used AdaBoost loss; logit-loss results were similar to AdaBoost and are not reported.Source: §3.1 · p. 8
- Experiments used two-terminal-node trees, five shrinkage values, 100 simulated replications or 20 real-data permutations, and training/validation/test splits of 50/25/25.Source: §3.1 · pp. 8–9
3.2 Gradient boosting vs accelerated gradient boosting
- At ν=0.01, validation errors at the selected iteration are comparable, while AGB's selected model uses far fewer components, a difference attributed to Nesterov's acceleration.Source: §3.2 · pp. 9–10, Figure 3 · p. 9
- Across simulated and real-life data, predictive performance is close, best test errors occur for ν below 0.1, and AGB uses fewer iterations and is less sensitive to ν.For standard boosting, 10,000 iterations are generally insufficient when ν is below 0.01; AGB reaches its optimal model in considerably fewer iterations for each tested ν.Source: §3.2 · p. 10, Figure 4 · p. 11, Figure 5 · p. 12
3.3 Comparison with the Lasso and random forests
- Across data sets, boosting methods often perform best and uniformly well; AGB has no clear accuracy edge over standard boosting but is less sensitive to ν and yields more parsimonious models.Source: §3.3 · p. 14