Boosting: From Weak Learners to Gradient Models

Boosting constructs an additive predictor. Each new learner is trained to improve the current ensemble rather than solve the full problem independently.

That loop is also a descent procedure, and the reading of it was published twice, independently, within two years. Mason and three co-authors gave it in 1999 as boosting algorithms as gradient descent. Friedman gave it again in 2001, in The Annals of Statistics, where the tree version is named TreeBoost and the algorithms are written out for least-squares, least-absolute-deviation, Huber-M and multiclass logistic losses.

Friedman's abstract states the whole move in two sentences: “Function estimation/approximation is viewed from the perspective of numerical optimization in function space, rather than parameter space. A connection is made between stagewise additive expansions and steepest-descent minimization.” That is exactly what the stages below are doing. The ensemble is the current point. The weak learner approximates the step direction. The scaling is the step size. The optimization happens over functions, not over a fixed parameter vector.

AdaBoost increases attention on the examples the current classifier misclassifies. Later learners therefore spend more capacity on the difficult cases, and the final classifier combines the weak learners with weights related to their performance. Freund and Schapire introduced it in 1997, and ACM SIGACT and EATCS awarded them the 2003 Gödel Prize for it. The view is intuitive. It can also become sensitive to mislabeled or extreme examples, because those cases attract weight again every round.

Gradient boosting generalizes the stagewise idea. Instead of defining difficulty only by which examples the classifier gets wrong, it treats learning as numerical optimization in function space. Each new learner approximates a direction that reduces the chosen loss. With squared error this resembles fitting residuals. For other losses, the target is a negative gradient or related pseudo-residual. The loss therefore determines what the next learner is trying to correct. Saying that gradient boosting ‘fits residuals’ is exact for some objectives and a useful intuition for others, but not a universal literal description.

The two views are not rival accounts, and there is a dated paper that says so. Three years before the Gödel Prize, in April 2000, Friedman and two co-authors had already re-derived the reweighting algorithm from the statistical side. Their abstract puts the equivalence plainly: “For the two-class problem, boosting can be viewed as an approximation to additive modeling on the logistic scale using maximum Bernoulli likelihood as a criterion.” Reweighting and additive modelling are one procedure seen from two sides.

These methods all build the model additively. They differ in what signal corrects the next learner, and in engineering choices. Those engineering choices are published, and they make specific claims.

LightGBM has two mechanisms. Gradient-based One-Side Sampling drops most small-gradient instances when information gain is estimated. Exclusive Feature Bundling groups features that rarely take nonzero values together, and the paper proves its optimal form NP-hard. Eight authors published the system in December 2017. What the pair buys is stated as a speed claim with an accuracy caveat attached, not as an accuracy claim: “Our experiments on multiple public datasets show that, LightGBM speeds up the training process of conventional GBDT by up to over 20 times while achieving almost the same accuracy.”

CatBoost's contribution is stranger, because it is an argument that the correction signal itself is contaminated. Ordinary gradient boosting, its authors argued at NeurIPS in December 2018, contains a built-in target leak. Each step estimates its gradients using the target values of the same points the current model was fitted on. The result is a prediction shift. Their abstract says what the paper's two techniques exist to do: “Both techniques were created to fight a prediction shift caused by a special kind of target leakage present in all currently existing implementations of gradient boosting algorithms.” Their fix, ordered boosting, changes neither the loss nor the tree. It scores each example using only the examples that precede it in a chosen permutation.

Boosting hyperparameters work as a system, so tuning them one at a time misses how tightly they are coupled. There is a published setting that shows it. The Higgs Boson Machine Learning Challenge ran on Kaggle from 12 May to September 2014. It drew 1,785 teams and gave them 250,000 training and 550,000 test simulated events with 30 features. Chen and He describe their boosted-tree entry in a single sentence: “We set the maximum depth of the tree to 6, the step size shrinkage to 0.1 and the number of trees to 120.”

Those three numbers were reported together because they only mean anything together. On identical settings the entry scored AMS 3.64655, against 3.55236 for python-sklearn and 3.38356 for R-gbm. Tuning raised it to 3.71142, and to 3.72370 with added physics features. A γ/λ ablation showed nearly all models with γ = 0.1 beating those with γ = 0, so the penalty was carrying weight rather than decorating the configuration. The entry won the challenge's special High Energy Physics meets Machine Learning Award. The software it introduced was XGBoost.

This sequence keeps the method interpretable enough to debug. Establish simple baselines first: a linear model and a single constrained tree. Choose the loss deliberately, so the objective matches the business error and the label structure. Start shallow, limiting depth or leaves before increasing interaction capacity. Track staged validation, recording metrics after each boosting round and using early stopping. Inspect slices and residuals to find groups where later stages help, hurt, or exploit shortcuts. Then retest under distribution shift, checking temporal or domain holdouts before production approval. None of it is optional polish.

A boosted model can fail in four ways: overfitting, leakage, poor calibration, or a mismatch between the loss and the decision. Five curves catch them. Training loss shows whether the additive sequence continues fitting the chosen objective. Validation loss reveals when additional stages stop improving held-out objective value. The decision metric tracks the thresholded or ranked outcome that the product actually uses. Calibration error checks whether score magnitudes remain meaningful after aggressive fitting. Slice performance exposes groups where the global curve hides deterioration. One global curve can hide the failure that matters.