XGBoost

Input: training set ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{N}}$, a differentiable loss function ${\displaystyle L(y,F(x))}$, a number of weak learners ${\displaystyle M}$ and a learning rate ${\displaystyle \alpha }$.

Algorithm:

1. Initialize model with a constant value:
   $${\displaystyle {\hat {f}}_{(0)}(x)={\underset {\theta }{\arg \min }}\sum _{i=1}^{N}L(y_{i},\theta ).}$$

   
2. For m = 1 to M:
   1. Compute the 'gradients' and 'hessians':
      $${\displaystyle {\begin{aligned}{\hat {g}}_{m}(x_{i})&=\left[{\frac {\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}}\right]_{f(x)={\hat {f}}_{(m-1)}(x)}.\\{\hat {h}}_{m}(x_{i})&=\left[{\frac {\partial ^{2}L(y_{i},f(x_{i}))}{\partial f(x_{i})^{2}}}\right]_{f(x)={\hat {f}}_{(m-1)}(x)}.\end{aligned}}}$$

      
   2. Fit a base learner (or weak learner, e.g. tree) using the training set ${\displaystyle \left\{x_{i},-{\dfrac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}\right\}_{i=1}^{N}}$ by solving the optimization problem below:
      $${\displaystyle {\hat {\phi }}_{m}={\underset {\phi \in \mathbf {\Phi } }{\arg \min }}\sum _{i=1}^{N}{\frac {1}{2}}{\hat {h}}_{m}(x_{i})\left[\phi (x_{i})-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}\right]^{2}.}$$

      
      $${\displaystyle {\hat {f}}_{m}(x)=\alpha {\hat {\phi }}_{m}(x).}$$

      
   3. Update the model:
      $${\displaystyle {\hat {f}}_{(m)}(x)={\hat {f}}_{(m-1)}(x)+{\hat {f}}_{m}(x).}$$

      
3. Output ${\displaystyle {\hat {f}}(x)={\hat {f}}_{(M)}(x)=\sum _{m=0}^{M}{\hat {f}}_{m}(x).}$