0
$\begingroup$

I'm reading through the math of xgboost:

https://xgboost.readthedocs.io/en/latest/model.html

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}$$

$\endgroup$
  • 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 Sep 23 '17 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$ – clueless_undergrad37 Sep 23 '17 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 Sep 23 '17 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$ – clueless_undergrad37 Sep 23 '17 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$ – clueless_undergrad37 Oct 26 '17 at 3:09