When is Gradient Descent invoked on the objective function while running XGboost?
I thought of throwing some historical perspective into this...

The initial algorithm is called AdaBoost. Unlike most of machine learning, this algorithm has its genesis in hard theory. The authors were trying to answer the following theoretical question:


  Is it possible somehow to combine weak models and create a very accurate predictor?


Weak models are models that are hardly better than chance. Think about this question. It is quite a philosophical question... And, as it happens, it can be answered by hard mathematics.

They actually demonstrated that yes. Their paper is actually worth reading. They have since published a lot of interesting papers from different perspectives, for instance using game theory.

The AdaBoost algorithm is also very simple and worth checking because it is the basis of xgboost.

AdaBoost works with any model. The only restriction is that the model supports giving weights to each observation. This is because it trains models sequentially by increasing (or decreasing) the weight associated to each observation to make that observation more important (or less important).

The cool thing is that the algorithm is very unlikely to overfit. But notice that this is an empirical claim, not a theoretical one. The algorithm can overfit, but it has been found (empirically) to be very resilient.

This algorithm has been expanded into Gradient Boosting, which has more flexible loss functions. This algorithm is an AdaBoost adaption by the same guy that invented random forests. They are not concerned about theoretical questions like the authors of AdaBoost, they just want to make the algorithm more flexible and efficient. For instance, they also update the weights using all previous weak models, not just the last trained model.

xgboost is just an intelligent implementation of Gradient Boosting. You can see the basic algorithm in wikipedia. Each decision tree is trained sequentially and weights are computed based on the errors from the current ensemble.

I can hear you say:


  What? xgboost trains trees in sequence? How is xgboost so fast then?


This website explains it very well. While trees are trained sequentially, each individual decision tree is trained in parallel by using highly creative techniques. Most importantly, nodes in the same depth do not depend in each other, so you can paralelize them.

Long story short: the loss function is applied between training models.

When it comes to making predictions, then the entire ensemble can be used in parallel.