Gradient boosting

XGBoost (short for eXtreme Gradient Boosting) is an efficient implementation of gradient boosting (Jerome Friedman, "Greedy function approximation: a gradient boosting machine", 2001) for classification and regression problems. Gradient boosting is also known as Gradient Boosting Machine (GBM) or Gradient Boosted Regression Tree (GBRT). A special case is LambdaMART for ranking applications. Apart from XGBoost; other implementations are Microsoft's Light Gradient Boosting Machine (LightGBM), and Yandex's Catboost.

Gradient Boosted Trees is an ensemble of trees. This is similar to Bagging algorithms such as Random Forest; however, since this is a boosting algorithm, each tree is computed to incrementally reduce the error. With each new iteration a tree is greedily chosen and its prediction is added to the previous predictions based on a weight term. There is also a regularization term that penalizes complexity and reduces overfitting, similar...