XGBOOST objective function derivation algebra

Question

I need some help please with the derivation of xgboost objective function. I am following this online tutorial (Math behind GBM and XGBoost)

How do you go from here $$ loss = \sum_{i=1}^{n} \left( g_i \sum_{j=1}^{T} b_{jm}I_{Rjm}(x_i) + \frac{1}{2} k_i \left( \sum_{j=1}^{T} b_{jm}I_{Rjm}(x_i) \right)^2 \right) + \gamma T + \frac{ \lambda }{2} \sum_{j=1}^{T} b_{jm}^2 $$

to here $$ loss = \sum_{j=1}^{T} \left( \sum_{i\in I_{jm}} g_i \right) b_{jm} + \frac{1}{2} \left( \sum_{i\in I_{jm}} (k_i + \lambda) \right) b_{jm} + \gamma T $$

where as I understand, $I_j$ is the set of all training instances that are mapped to leaf $j$

I tried swapping the sums; however, since the second sum is squared I was not sure if they can be swapped.

Example, this is true

$$ \sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij} = \sum_{j=1}^{m} \sum_{i=1}^{n} x_{ij} $$

but not sure if this can be swapped

$$ \sum_{i=1}^{n} \left(\sum_{j=1}^{m} x_{ij} \right)^2 $$

Also, it may be the case that I don't fully understand the $I_{jm}$ function and how it works.

Thank you

Answer 1

The quick answers to your question are:

1. You are absolutely right: it is not generally valid to swap the order of summation when the interior sum is squared. It's not even true when $n=1$ and $m=2$:

$$ \sum_{i=1}^{1} \left(\sum_{j=1}^{2} x_{ij} \right)^2 = (x_{11} + x_{12})^2 = x_{11}^2 + 2x_{11}x_{12} + x_{12}^2 $$

$$ \sum_{j=1}^{2} \left(\sum_{i=1}^{1} x_{ij} \right)^2 = x_{11}^2 + x_{12}^2 $$

2. The blog post has a few mistakes in it, and you would be better working through the (quite nicely written and much better type-scripted) introduction in the XGBoost docs.