I'm reading through the math of xgboost:


Under the ADDITIVE TRAINING section of the objective function, I saw that in the derivation of the objective at step $t$, a claim is made about how the GENERAL form of the objective function for any loss function (MSE, logistic loss, etc.) takes on the form of a 2nd order Taylor expansion. How do we know this is true in general? Is there a mathematical explanation of this that I'm just not seeing?

I basically want to know how we are able to conclude that the following is the GENERAL form of the objective at step $t$:

$$\text{obj}^{(t)} = \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) + constant$$

where the $g_i$ and $h_i$ are defined as:

$$\begin{split}g_i &= \partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)})\\ h_i &= \partial_{\hat{y}_i^{(t-1)}}^2 l(y_i, \hat{y}_i^{(t-1)}) \end{split}$$

  • 1
    $\begingroup$ If I understand your question correctly...they're not saying that the loss function is equivalent to its second order Taylor expansion. Rather, they take a second order Taylor expansion as a local approximation of the loss function. This can't work in general because it requires that the loss function be twice differentiable. $\endgroup$
    – user20160
    Commented Sep 23, 2017 at 3:30
  • $\begingroup$ Oh... I think I totally misunderstood what I was reading ^^; that makes a lot more sense than what I had in mind. Thank you for clarifying! Just out of curiosity... why not use a higher order Taylor expansion to approximate? $\endgroup$ Commented Sep 23, 2017 at 3:50
  • $\begingroup$ Using the Hessian makes xgboost analogous to Newton's method the same way regular gradient boosting is analogous to gradient descent. People don't tend to use 3rd and higher order derivatives in optimization problems in general. This would require that the objective function is at least 3x differentiable, which could be limiting. Memory requirements could also scale poorly. I recall reading somewhere that higher order derivatives may not be well behaved for the purpose of optimization, but can't find the reference now (so take that with a grain of salt). $\endgroup$
    – user20160
    Commented Sep 23, 2017 at 4:04
  • $\begingroup$ Wow... at what point is the Hessian matrix used in xgboost? I'm new to the package and am trying to wrap my head around everything! $\endgroup$ Commented Sep 23, 2017 at 5:05
  • $\begingroup$ I just noticed this, but why does the loss function in $obj^{(t)}$ look at $\hat{y}_i^{(t-1)}$ instead of $\hat{y}_i^{(t)}$? $\endgroup$ Commented Oct 26, 2017 at 3:09